Efficient algorithms for collision avoidance at intersections
Open accessThe DOI matches its Crossref record; 23 of the 24 references it cites were found in a registry or an index.
Abstract
We consider the problem of synthesising the least restrictive controller for collision avoidance of multiple vehicles at an intersection. The largest set of states for which there exists a control that avoids collisions is known as the maximal controlled invariant set. Exploiting results from the scheduling literature we prove that, for a general model of vehicle dynamics at an intersection, the problem of checking membership in the maximal controlled invariant set is NP-hard. We then describe an algorithm that solves this problem approximately and with provable error bounds. The approximate solution is used to design a supervisor for collision avoidance whose complexity scales polynomially with the number of vehicles. The supervisor is based on a hybrid algorithm that employs a dynamic model of the vehicles and periodically solves a scheduling problem.
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
Citations
Cites
Adhi Harmoko, S., M.Komp, Jacquard, J. M., Zuse, K., & Eniac (2005) · Cited by 18,035
Scheduling: Theory, Algorithms, and Systems
(1996) · IIE Transactions · doi:10.1080/15458830.1996.11770714 · Cited by 6,210
Applied Optimal Control: Optimization, Estimation, and Control
Bryson, A. E., & Ho, Y.-C. (2018) · Routledge eBooks · doi:10.1201/9781315137667 · Cited by 6,015
Optimization by Vector Space Methods
(1970) · Students Quarterly Journal · doi:10.1049/sqj.1970.0088 · Cited by 6,004 · cited 1×
“In the case of equations (17), the optimization problem on U is solved analytically using standard variational calculus [16, 20].”
MethodOptimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
Graham, R. L., Lawler, E. L., Lenstra, J. K., & Kan, A. H. G. R. (1979) · Annals of Discrete Mathematics · doi:10.1016/s0167-5060(08)70356-x · Cited by 5,854
Introduction to Lattices and Order
Davey, B. A., & Priestley, H. A. (2002) · Cambridge University Press eBooks · doi:10.1017/cbo9780511809088 · Cited by 4,901
Differential equations with discontinuous right hand sides
(1989) · Mathematics and Computers in Simulation · doi:10.1016/0378-4754(89)90171-7 · Cited by 4,893
Differential Equations with Discontinuous Righthand Sides
Filippov, A. F. (1988) · Mathematics and Its Applications · doi:10.1007/978-94-015-7793-9 · Cited by 4,720
Introduction to Algorithms, third edition
Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009) · Cited by 2,309
Complexity of Machine Scheduling Problems
Lenstra, J. K., Rinnooy Kan, A. H. G., & Brucker, P. (1977) · Annals of Discrete Mathematics · doi:10.1016/s0167-5060(08)70743-x · Cited by 2,197
Research works printed but not linked: 9
- Cormen T. H., 2009, MIT Press
- Dacorogna B., 2008, Springer
- 10.5555/1703775.1703935 · doi:10.5555/1703775.1703935
- Hafner M. R., 2011, Proc. of ITS World Congress
- Bryson E., 1969, Ginn and Company
- Khalil H. K., 2002, Prentice-Hall
- Luenberger D. G., 1969, Wiley
- Pinedo M. L., 2008, Springer
- U.S. Department of Transportation, 2010, ITS Strategic Research Plan, 2014
Cited by
Items 101–151 of 151
Robust multirobot coordination using priority encoded homotopic constraintsPreprint
Grégoire, J., Bonnabel, S., & Fortelle, A. D. L. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1306.0785 · Cited by 7
“The method is inspired by the works [18, 20, 21] for the coordination of two vehicles (the priority graph being then reduced to one oriented edge).”
BackgroundMethodDistributed Games With Jumps: An Α-Potential Game ApproachPreprint
Guo, X., Li, X., & Zhang, Y. (2025) · SSRN Electronic Journal · doi:10.2139/ssrn.5377841 · Cited by 7
Optimization based coordination of autonomous vehicles in confined areas
Kojchev, S., Hult, R., & Fredriksson, J. (2022) · IEEE International Conference on Intelligent Transportation Systems (ITSC) · doi:10.1109/itsc55140.2022.9922180 · Cited by 6
Experimental Validation of Distributed Optimal Vehicle Coordination
Zanon, M., Hult, R., Gros, S., & Falcone, P. (2018) · European Control Conference (ECC) · doi:10.23919/ecc.2018.8550569 · Cited by 6
“While computing the global optimum is NP-hard [4], the development of tailored algorithms will make it possible to compute approximated solutions in real time.”
BackgroundRobust Supervisors for Intersection Collision Avoidance in the Presence of Legacy Vehicles
Ahn, H., Rizzi, A., & Colombo, A. (2019) · International Journal of Control Automation and Systems · doi:10.1007/s12555-018-0768-4 · Cited by 6
Self-citationSistem Penghindar Tabrakan Frontal Berbasis Logika Fuzzy
Basjaruddin, N. C., Kuspriyanto, K., Saefudin, D., & Putra, G. (2016) · Jurnal Nasional Teknik Elektro dan Teknologi Informasi (JNTETI) · doi:10.22146/jnteti.v5i3.261 · Cited by 5
“Penelitian dalam pengembangan HCAS pada bagian algoritme dilakukan antara lain pada [8] dan [9].”
BackgroundRobust Supervisors for Intersection Collision Avoidance in the Presence of Uncontrolled VehiclesPreprint
Ahn, H., Rizzi, A., Colombo, A., & Vecchio, D. D. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1603.03916 · Cited by 5
Self-citationSafe and Efficient Intersection Control of Connected and Autonomous Intersection TrafficPreprint
Lu, Q. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1801.09361 · Cited by 5
“An interesting result about collision avoidance at intersection is shown in [11], that it is an NP-hard problem to check the membership in the maximal controlled invariant set, which is the largest set of states for which there exists a control that avoids collisions.”
BackgroundPriority-based coordination of mobile robots
Grégoire, J. (2014) · theses.fr (ABES) · doi:10.70675/daf6c01az28ddz481bz9dbaz31bd4b72defe · Cited by 5
Comparative Study of Intersection Management Algorithms for Autonomous Vehicles
Yu, C., Xiao, Z., Zhang, J., Xu, Z., & Mai, Z. (2024) · International Conference on Machine Learning, Big Data and Business Intelligence (MLBDBI) · doi:10.1109/mlbdbi63974.2024.10823727 · Cited by 4
Energy Efficient Optimization-Based Coordination of Electric Automated Vehicles in Confined Areas
Kojchev, S., Hult, R., & Fredriksson, J. (2023) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc49753.2023.10383878 · Cited by 4
Flexible MPC-based Conflict Resolution Using Online Adaptive ADMM
An, J., Giordano, G., & Liu, C. (2021) · European Control Conference (ECC) · doi:10.23919/ecc54610.2021.9655090 · Cited by 4
“Due to the coupling in the constraints and objective function, primal decomposition cannot be applied to problem (1), which is shown to be NP-hard in [14].”
MethodOptimization-Based Coordination of Automated and Human-Driven Vehicles in Confined Sites
Kojchev, S., Hult, R., Kneissl, M., & Fredriksson, J. (2024) · IEEE Transactions on Control Systems Technology · doi:10.1109/tcst.2024.3417068 · Cited by 3
“This combinatorial decision is the predominant component in the complexity of the coordination problem that is formally proven to be NP-hard [4].”
Arfvidsson, K. M., Jiang, F. J., Johansson, K. H., & Mårtensson, J. (2024) · IEEE International Conference on Intelligent Transportation Systems (ITSC) · doi:10.1109/itsc58415.2024.10919683 · Cited by 3
“Proving that behavior is safe poses major challenges [10].”
Distributed RSU-Based Potential Crash Detection and Avoidance Mechanism for Unsignaled Intersections
Sharma, S., & Awasthi, S. K. (2025) · Journal of Network and Systems Management · doi:10.1007/s10922-025-09957-6 · Cited by 3
“In [27–30], and [31], the authors used the collision set (or critical set) technique to reserve the entire intersection area for colliding cars sequentially.”
Reap-SoS: A Requirement Engineering Approach for System of Systems
Duarte, F. L., de Castro, A. F., & Queiroz, P. G. G. (2018) · doi:10.5121/csit.2018.80510 · Cited by 3
“The context of ITS is directly related to a relevant theme, which is the "Smart Cities", which can be seen as a set of steps that a citizen takes, together with services and technologies to make the city a more habitable environment/comfortable, with more efficient services and ready to suit any situation.”
BackgroundChen, B., Liao, L., Zou, F., & Zheng, Y. (2020) · Advances in intelligent systems and computing · doi:10.1007/978-981-15-3308-2_16 · Cited by 3
Forghani, M., McNew, J. M., Hoehener, D., & Vecchio, D. D. (2015) · Proceedings of the ... American Control Conference/Proceedings of the American Control Conference · doi:10.1109/acc.2015.7170786 · Cited by 3
“class of systems, called order preserving systems, that allow computationally efficient solutions [4]–[8].”
BackgroundAiding Autonomous Vehicles with Fault-tolerant V2V CommunicationPreprint
Savić, V., Schiller, E. M., & Papatriantafilou, M. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1710.00692 · Cited by 3
“The work in [14] focuses on semi-autonomous vehicles with the controller that can override the driver and prevent potential collision at the intersections.”
BackgroundIntelligent Autonomous Intersection ManagementPreprint
Gunarathna, U., Karunasekera, S. A., Borovica‐Gajic, R., & Tanin, E. (2022) · arXiv (Cornell University) · doi:10.48550/arxiv.2202.04224 · Cited by 3
“Previous efforts exhibit high computational time [6] as they rely on mathematical programming or analytical methods.”
BackgroundLayered Controller Synthesis for Dynamic Multi-agent Systems
Clément, E., Perrin, N., & Schlehuber-Caissier, P. (2023) · Lecture notes in computer science · doi:10.1007/978-3-031-42626-1_4 · Cited by 2
Ensuring Drivability of Planned Motions from Simple Models Using Formal Methods
Schürmann, B., Heß, D., Eilbrecht, J., Stursberg, O., Köster, F., & Althoff, M. (2017) · elib (German Aerospace Center) · Cited by 2
Muthugama, L., Xie, H., Tanin, E., Karunasekera, S. A., & Gunarathna, U. (2022) · ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (SIGSPATIAL GIS) · doi:10.1145/3557915.3561018 · Cited by 2
“In fact, optimizing traffic flow alone is NP-hard due to its large alternative solution space, which leads to the development of approximate solutions [3].”
BackgroundInfluentialKooperative Bewegungsplanung autonomer Fahrzeuge unter Verwendung von Manöver-Templates
Manzinger, S., Leibold, M., & Althoff, M. (2017) · mediaTUM (Technical University of Munich) · Cited by 2
Semi-autonomous control of multiple heterogeneous vehicles for intersection collision avoidance
Ahn, H. (2014) · DSpace@MIT (Massachusetts Institute of Technology) · Cited by 2
Discrete Event System Methods for Control Problems Arising in Cyber-physical Systems.
Dallal, E. (2014) · Deep Blue (University of Michigan) · Cited by 2
Computer Science & Information Technology
(2018) · doi:10.5121/csit.2018.80500 · Cited by 2
Masi, S. (2021) · theses.fr (ABES) · doi:10.70675/6e99605dz2be4z4130z858fz11ec2da874ef · Cited by 2
Safe Navigation Strategies within Cluttered Environment
Ioan, D. (2021) · theses.fr (ABES) · doi:10.70675/33523f96zd69fz4074z90e1za495c429362b · Cited by 2
A Decision Transformer for Generalizable Multi-Vehicle Coordination at Unsignalized Intersections
Lee, E., Kang, M., Choi, Y., & Ahn, H. (2026) · IEEE Intelligent Vehicles Symposium · doi:10.1109/iv66570.2026.11623990 · Cited by 1
A Safety Reasoning Copilot Design for Future Uncrewed Ground Vehicles (UGVs)
Frederick, P. A. (2023) · SAE technical papers on CD-ROM/SAE technical paper series · doi:10.4271/2024-01-4069 · Cited by 1
Kojchev, S., Hult, R., Kneissl, M., & Fredriksson, J. (2024) · IEEE Transactions on Intelligent Transportation Systems · doi:10.1109/tits.2024.3492029 · Cited by 1
“In general, the coordination problem is difficult to solve and has formally been shown to be NP-hard [3].”
Reghelin, R. (2014) · Americanae (AECID Library) · Cited by 1
A Feasibility-Enforcing Primal-Decomposition SQP Algorithm for Optimal Vehicle CoordinationPreprint
Zanon, M., Hult, R., Gros, S., & Falcone, P. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1704.01081 · Cited by 1
“While this class of problems has a high complexity and is known to be NP-hard [3], by designing tailored optimisation algorithms and heuristics one can aim at computing approximated solutions in a rather short time.”
BackgroundOrganizing intelligent vehicles at traffic lights to decrease travel time in a double lane road
Reghelin, R., & da Silva, E. (2016) · IEEE International Conference on Intelligent Computer Communication and Processing (ICCP) · doi:10.1109/iccp.2016.7737163
“Recently proposals use job scheduling techniques [12] [13] and optimal control [14] .”
BackgroundReliability of Packet Transmissions in Vehicular Networks
Steinmetz, E. (2015) · Chalmers Publication Library (Chalmers University of Technology)
An Adaptive Cruise Control Model based on PDLCA for Efficient Lane Selection and Collision Avoidance
Rashid, K. I., Ding, N., Tahir, M., & Ahmed, A. (2018) · International Journal of Advanced Computer Science and Applications · doi:10.14569/ijacsa.2018.090408
“The author considers it as an NP-hard issue and is around illuminated in this paper, by receiving concentrated approach in light of supervisor having provable error bound [14].”
BackgroundMahmoud, A. A. H. (2017) · VTechWorks (Virginia Tech)
Simulasi Perangkat Keras Sistem Penghindar Tabrakan Frontal Berbasis Logika Fuzzy
Basjaruddin, N. C., Saefudin, D., & Putra, G. (2015) · Prosiding Industrial Research Workshop and National Seminar · doi:10.35313/irwns.v6i0.240
Safe and Efficient Intelligent Intersection Control of Autonomous Vehicles
Lu, Q. (2019) · Digital Commons - DU (University of Denver)
Decentralized Conflict Resolution for Autonomous Vehicles
An, J. (2020) · Research Repository (Delft University of Technology)
Rodriguez, M. A. (2021) · University Libraries (University of Maryland) · doi:10.13016/dyou-vm1t
A Strategic Approach for Dense, Integrated, Vehicle Navigation
Malekpour, M. R. (2023) · AIAA SciTech Forum · doi:10.2514/6.2023-2623
Hult, R., Mario, Z., Gros, S., & Falcone, P. (2018) · Chalmers Research (Chalmers University of Technology)
On Optimization-Based Coordination of Automated Vehicles in Confined Sites
Kojchev, S. (2024) · Chalmers Research (Chalmers University of Technology)
Lane-free crossing of connected and autonomous vehicles through intersections
Amouzadi, M. (2023) · Sussex Research Online (University of Sussex)
Sistema de conducción autónoma aplicado a rotondas simulado en Gazebo y Controlado en ROS 2
Vicente Vidal, P. (2023) · Archivo Digital UPM (Universidad Politécnica de Madrid)
Coordination and control for connected and automated vehicles at signal-free intersections (本文)
ノル, モ. ハ. ビ. モ., & Nor, M. H. B. M. (2020) · Institutional Repositories DataBase (IRDB)
Vehicle localization based on scene perception
Liu, L. (2021) · theses.fr (ABES) · doi:10.70675/43424a72z2eedz41d7z9829z41cfa8ff911a
Tomar, U. P. S. (2025) · Advances in Nonlinear Variational Inequalities
Kumar, G., & Ratnoo, A. (2026) · Journal of Guidance Control and Dynamics · doi:10.2514/1.g009851
Metadata
- Authors
- Colombo, A., & Del Vecchio, D.
- Affiliations
- Massachusetts Institute of Technology (US)
- MIT, Cambridge, USA
- ORCID
- Colombo, Alessandro
- Venue
- Proceedings of the 15th ACM international conference on Hybrid Systems: Computation and Control
- Publisher
- ACM
- Published
- 2012-04-17
- Pages
- 145-154
- OpenAlex
- W2085865324
- Cited by
- 134
- References
- 24
- Citations by year
- 2026: 1 · 2025: 1 · 2024: 6 · 2023: 10 · 2022: 8 · 2021: 10 · 2020: 10 · 2019: 11 · 2018: 17 · 2017: 14 · 2016: 13 · 2015: 16 · 2014: 10 · 2013: 6 · 2012: 1
- FWCI
- 16.92
- Type
- conference paper
- Language
- en
- Open access
- green
- hdl.handle.net
- Licence
- Locations
- ACM International Conference on Hybrid Systems: Computation and Control (HSCC) (publishedVersion)
- DSpace@MIT (Massachusetts Institute of Technology) (submittedVersion, cc-by-nc-sa)
- Virtual Community of Pathological Anatomy (University of Castilla La Mancha) (submittedVersion)
- Topics
- Physical Sciences › Engineering › Control and Systems Engineering › Traffic control and management
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Formal Methods in Verification
- Physical Sciences › Engineering › Control and Systems Engineering › Robotic Path Planning Algorithms
- Keywords
- collision avoidance, NP-hardness, approximate algorithms, error bounds, supervisor design, hybrid algorithm, vehicle scheduling, multi-vehicle control, vehicle dynamics
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.