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
A Survey of Motion Planning and Control Techniques for Self-Driving Urban Vehicles
Paden, B., Cap, M., Yong, S. Z., Yershov, D., & Frazzoli, E. (2016) · IEEE Transactions on Intelligent Vehicles · doi:10.1109/tiv.2016.2578706 · Cited by 2,585
A Survey of Autonomous Driving: Common Practices and Emerging Technologies
Yurtsever, E., Lambert, J., Carballo, A., & Takeda, K. (2020) · IEEE Access · doi:10.1109/access.2020.2983149 · Cited by 1,889
“Level two is partial automation to which advanced assistance systems such as emergency braking or collision avoidance [33], [34]”
BackgroundCooperative Intersection Management: A Survey
Chen, L., & Englund, C. (2016) · IEEE Transactions on Intelligent Transportation Systems · doi:10.1109/tits.2015.2471812 · Cited by 488
“The authors would like to thank the anonymous reviewers for their invaluable comments that help improve the quality of this paper significantly.”
BackgroundExplanations in Autonomous Driving: A Survey
Omeiza, D., Webb, H., Jirotka, M., & Kunze, L. (2022) · IEEE Transactions on Intelligent Transportation Systems · doi:10.1109/tits.2021.3122865 · Cited by 355
“assistance system components such as emergency braking or collision avoidance [130], [131].”
BackgroundCooperative Collision Avoidance at Intersections: Algorithms and Experiments
Hafner, M. R., Cunningham, D., Caminiti, L., & Del Vecchio, D. (2013) · IEEE Transactions on Intelligent Transportation Systems · doi:10.1109/tits.2013.2252901 · Cited by 301
“More recently, work that employs job-scheduling techniques [8], [17] and optimal control [19] for ICA has appeared.”
Background
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
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Efficient algorithms for collision avoidance at intersections. https://app.cochat.ai/papers/10.1145/2185632.2185656
- The paper
- Colombo, A., & Del Vecchio, D. (2012). Efficient algorithms for collision avoidance at intersections. Proceedings of the 15th ACM international conference on Hybrid Systems: Computation and Control. https://doi.org/10.1145/2185632.2185656
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.