{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,8]],"date-time":"2026-07-08T15:56:30Z","timestamp":1783526190722,"version":"3.55.0"},"reference-count":26,"publisher":"Association for Computing Machinery (ACM)","issue":"5s","license":[{"start":{"date-parts":[[2019,10,8]],"date-time":"2019-10-08T00:00:00Z","timestamp":1570492800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100004663","name":"Ministry of Science and Technology, Taiwan","doi-asserted-by":"publisher","award":["MOST-108-2636-E-002-011, MOST-106-2628-E-002-019-MY3, MOST-108-2221-E-002-099-MY3"],"award-info":[{"award-number":["MOST-108-2636-E-002-011, MOST-106-2628-E-002-019-MY3, MOST-108-2221-E-002-099-MY3"]}],"id":[{"id":"10.13039\/501100004663","id-type":"DOI","asserted-by":"publisher"}]},{"name":"MediaTek Inc.","award":["MTKC-2018-0167, MTKC-2019-0070"],"award-info":[{"award-number":["MTKC-2018-0167, MTKC-2019-0070"]}]},{"name":"Ministry of Education, Taiwan","award":["NTU-107V0901, NTU-108V0901"],"award-info":[{"award-number":["NTU-107V0901, NTU-108V0901"]}]},{"name":"Global Unichip Corp."},{"name":"TSMC Ltd."},{"name":"Synopsys Inc."}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Embed. Comput. Syst."],"published-print":{"date-parts":[[2019,10,31]]},"abstract":"<jats:p>Intersection management is one of the most representative applications of intelligent vehicles with connected and autonomous functions. The connectivity provides environmental information that a single vehicle cannot sense, and the autonomy supports precise vehicular control that a human driver cannot achieve. Intersection management solves the fundamental conflict resolution problem for vehicles\u2014two vehicles should not appear at the same location at the same time, and, if they intend to do that, an order should be decided to optimize certain objectives such as the traffic throughput or smoothness. In this paper, we first propose a graph-based model for intersection management. The model is general and applicable to different granularities of intersections and other conflicting scenarios. We then derive formal verification approaches which can guarantee deadlock-freeness. Based on the graph-based model and the verification approaches, we develop a centralized cycle removal algorithm for the graph-based model to schedule vehicles to go through the intersection safely (without collisions) and efficiently without deadlocks. Experimental results demonstrate the expressiveness of the proposed model and the effectiveness and efficiency of the proposed algorithm.<\/jats:p>","DOI":"10.1145\/3358221","type":"journal-article","created":{"date-parts":[[2019,10,10]],"date-time":"2019-10-10T13:13:05Z","timestamp":1570713185000},"page":"1-21","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":29,"title":["Graph-Based Modeling, Scheduling, and Verification for Intersection Management of Intelligent Vehicles"],"prefix":"10.1145","volume":"18","author":[{"given":"Yi-Ting","family":"Lin","sequence":"first","affiliation":[{"name":"National Taiwan University, Taipei, Taiwan"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Hsiang","family":"Hsu","sequence":"additional","affiliation":[{"name":"National Taiwan University, Taipei, Taiwan"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Shang-Chien","family":"Lin","sequence":"additional","affiliation":[{"name":"National Taiwan University, Taipei, Taiwan"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Chung-Wei","family":"Lin","sequence":"additional","affiliation":[{"name":"National Taiwan University, Taipei, Taiwan"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Iris Hui-Ru","family":"Jiang","sequence":"additional","affiliation":[{"name":"National Taiwan University, Taipei, Taiwan"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Changliu","family":"Liu","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2019,10,8]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.trc.2012.11.004"},{"key":"e_1_2_1_2_1","volume-title":"ACM International Conference on Hybrid Systems: Computation and Control (HSCC). 185--194","author":"Ahn H.","unstructured":"H. Ahn and D. Del Vecchio . 2016. Semi-autonomous intersection collision avoidance through job-shop scheduling . In ACM International Conference on Hybrid Systems: Computation and Control (HSCC). 185--194 . H. Ahn and D. Del Vecchio. 2016. Semi-autonomous intersection collision avoidance through job-shop scheduling. In ACM International Conference on Hybrid Systems: Computation and Control (HSCC). 185--194."},{"key":"e_1_2_1_3_1","volume-title":"ACM\/IEEE International Conference on Cyber-Physical Systems (ICCPS). 1--10","author":"Azimi S. R.","unstructured":"S. R. Azimi , G. Bhatia , R. R. Rajkumar , and P. Mudalige . 2013. Reliable intersection protocols using vehicular networks . In ACM\/IEEE International Conference on Cyber-Physical Systems (ICCPS). 1--10 . S. R. Azimi, G. Bhatia, R. R. Rajkumar, and P. Mudalige. 2013. Reliable intersection protocols using vehicular networks. In ACM\/IEEE International Conference on Cyber-Physical Systems (ICCPS). 1--10."},{"key":"e_1_2_1_4_1","volume-title":"ACM\/IEEE International Conference on Cyber-Physical Systems (ICCPS). 1--12","author":"Azimi S. R.","unstructured":"S. R. Azimi , G. Bhatia , R. R. Rajkumar , and P. Mudalige . 2014. STIP: Spatio-temporal intersection protocols for autonomous vehicles . In ACM\/IEEE International Conference on Cyber-Physical Systems (ICCPS). 1--12 . S. R. Azimi, G. Bhatia, R. R. Rajkumar, and P. Mudalige. 2014. STIP: Spatio-temporal intersection protocols for autonomous vehicles. In ACM\/IEEE International Conference on Cyber-Physical Systems (ICCPS). 1--12."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/TITS.2015.2471812"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/356586.356588"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2014.2381453"},{"key":"e_1_2_1_8_1","unstructured":"T. H. Cormen C. E. Leiserson R. L. Rivest and C. Stein. 2009. Introduction to Algorithms Third Edition (3rd ed.). The MIT Press.  T. H. Cormen C. E. Leiserson R. L. Rivest and C. Stein. 2009. Introduction to Algorithms Third Edition (3rd ed.). The MIT Press."},{"key":"e_1_2_1_9_1","volume-title":"American Control Conference. 4380--4386","author":"Dallal E.","unstructured":"E. Dallal , A. Colombo , D. Del Vecchio , and S. Lafortune . 2013. Supervisory control for collision avoidance in vehicular networks using discrete event abstractions . In American Control Conference. 4380--4386 . E. Dallal, A. Colombo, D. Del Vecchio, and S. Lafortune. 2013. Supervisory control for collision avoidance in vehicular networks using discrete event abstractions. In American Control Conference. 4380--4386."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1530873.1530881"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/1622655.1622672"},{"key":"e_1_2_1_12_1","volume-title":"IEEE Intelligent Vehicles Symposium. 932--937","author":"Jin Q.","unstructured":"Q. Jin , G. Wu , K. Boriboonsomsin , and M. Barth . 2012. Advanced intersection management for connected vehicles using a multi-agent systems approach . In IEEE Intelligent Vehicles Symposium. 932--937 . Q. Jin, G. Wu, K. Boriboonsomsin, and M. Barth. 2012. Advanced intersection management for connected vehicles using a multi-agent systems approach. In IEEE Intelligent Vehicles Symposium. 932--937."},{"key":"e_1_2_1_14_1","doi-asserted-by":"crossref","unstructured":"R. M. Karp. 1972. Reducibility among combinatorial problems. In Complexity of Computer Computations. The IBM Research Symposia Series. 85--103.  R. M. Karp. 1972. Reducibility among combinatorial problems. In Complexity of Computer Computations. The IBM Research Symposia Series. 85--103.","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"e_1_2_1_15_1","unstructured":"J. Kleinberg and E. Tardos. 2006. Algorithm Design. Pearson Addison Wesley.  J. Kleinberg and E. Tardos. 2006. Algorithm Design. Pearson Addison Wesley."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVT.2011.2107584"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1956-0078686-7"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIV.2017.2788209"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.1979.234181"},{"key":"e_1_2_1_20_1","volume-title":"International Conference on Intelligent Transportation Systems. 818--823","author":"Naumann R.","unstructured":"R. Naumann , R. Rasche , J. Tacken , and C. Tahedi . 1997. Validation and simulation of a decentralized intersection collision avoidance algorithm . In International Conference on Intelligent Transportation Systems. 818--823 . R. Naumann, R. Rasche, J. Tacken, and C. Tahedi. 1997. Validation and simulation of a decentralized intersection collision avoidance algorithm. In International Conference on Intelligent Transportation Systems. 818--823."},{"key":"e_1_2_1_21_1","volume-title":"Petri nets. Comput. Surveys 9, 3","author":"Peterson J. L.","year":"1977","unstructured":"J. L. Peterson . 1977. Petri nets. Comput. Surveys 9, 3 ( 1977 ). J. L. Peterson. 1977. Petri nets. Comput. Surveys 9, 3 (1977)."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2010.2098270"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/2.43525"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1049\/iet-its.2013.0093"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCT.1963.1082116"},{"key":"e_1_2_1_26_1","volume-title":"IEEE International Conference on Smart Computing (SMARTCOMP). 1--8.","author":"Zheng B.","unstructured":"B. Zheng , C. Lin , H. Liang , S. Shiraishi , W. Li , and Q. Zhu . 2017. Delay-aware design, analysis and verification of intelligent intersection management . In IEEE International Conference on Smart Computing (SMARTCOMP). 1--8. B. Zheng, C. Lin, H. Liang, S. Shiraishi, W. Li, and Q. Zhu. 2017. Delay-aware design, analysis and verification of intelligent intersection management. In IEEE International Conference on Smart Computing (SMARTCOMP). 1--8."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.trc.2015.01.006"}],"container-title":["ACM Transactions on Embedded Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3358221","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3358221","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:23:07Z","timestamp":1750202587000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3358221"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,10,8]]},"references-count":26,"journal-issue":{"issue":"5s","published-print":{"date-parts":[[2019,10,31]]}},"alternative-id":["10.1145\/3358221"],"URL":"https:\/\/doi.org\/10.1145\/3358221","relation":{},"ISSN":["1539-9087","1558-3465"],"issn-type":[{"value":"1539-9087","type":"print"},{"value":"1558-3465","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,10,8]]},"assertion":[{"value":"2019-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-10-08","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}