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
Direct Methods in the Calculus of Variations
(2007) · Applied Mathematical Sciences · doi:10.1007/978-0-387-55249-1 · Cited by 1,668
Angeli, D., & Sontag, E. D. (2003) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2003.817920 · Cited by 664
Controllers for reachability specifications for hybrid systems
Lygeros, J., Tomlin, C., & Sastry, S. (1999) · Automatica · doi:10.1016/s0005-1098(98)00193-9 · Cited by 608 · cited 2×
“…[Arti.cial Intelligence]: Problem Solving, Control Methods, and Search Control theory, Scheduling ; I.2.9 [Arti.cial Intelligence]: Robotics Autonomous vehicles General Terms Algorithms, Theory Keywords Intelligent transportation system, collision, complexity, hybrid, safety, scheduling 1.”
BackgroundInfluentialComputational techniques for the verification of hybrid systems
Tomlin, C. J., Mitchell, I., Bayen, A. M., & Oishi, M. (2003) · Proceedings of the IEEE · doi:10.1109/jproc.2003.814621 · Cited by 353 · cited 1×
“Computing this set for systems with large state space is known to be a hard problem, and research has been focusing on calculating approximations [23].”
BackgroundTwo-Processor Scheduling with Start-Times and Deadlines
Garey, M. R., & Johnson, D. S. (1977) · SIAM Journal on Computing · doi:10.1137/0206029 · Cited by 236
Scheduling Unit–Time Tasks with Arbitrary Release Times and Deadlines
Garey, M. R., Johnson, D. S., Simons, B. B., & Tarjan, R. E. (1981) · SIAM Journal on Computing · doi:10.1137/0210018 · Cited by 206
Provable Systemwide Safety in Intelligent Intersections
Kowshik, H., Caveney, D., & Kumar, P. R. (2011) · IEEE Transactions on Vehicular Technology · doi:10.1109/tvt.2011.2107584 · Cited by 151 · cited 1×
“A much harder problem, both from a technological and a computational point of view, is that of preventing collisions caused by drivers mistakes when vehicles traverse an intersection.”
BackgroundDevelopment of a Scaled Vehicle With Longitudinal Dynamics of an HMMWV for an ITS Testbed
Verma, R., Vecchio, D. D., & Fathy, H. K. (2008) · IEEE/ASME Transactions on Mechatronics · doi:10.1109/tmech.2008.915820 · Cited by 94 · cited 1×
“Notice that the presented algorithm can handle more general models, including linear and nonlinear friction terms, such as those discussed in [25].”
BackgroundAutomated Vehicle-to-Vehicle Collision Avoidance at Intersections
Häfner, M., Cunningham, D., Caminiti, L., & Vecchio, D. D. (2011) · 18th ITS World CongressTransCoreITS AmericaERTICO - ITS EuropeITS Asia-Pacific · Cited by 45
Hafner, M. R., & Vecchio, D. D. (2011) · SIAM Journal on Control and Optimization · doi:10.1137/090761203 · Cited by 39 · cited 1×
“A number of solutions have been proposed Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for pro.t or commercial advantage and that copies bear this notice and the full…”
BackgroundDesaraju, V., Ro, H. C., Yang, M., Tay, E., Roth, S., & Del Vecchio, D. (2009) · 2009 IEEE International Conference on Robotics and Automation · doi:10.1109/robot.2009.5152656 · Cited by 34 · cited 1×
“A number of solutions have been proposed Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for pro.t or commercial advantage and that copies bear this notice and the full…”
BackgroundSupervisory control of differentially flat systems based on abstraction
Colombo, A., & Vecchio, D. D. (2011) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2011.6160759 · Cited by 23 · cited 1×
“…been proposed Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for pro.t or commercial advantage and that copies bear this notice and the full citation on the .rst page.”
BackgroundSelf-citationFormal design of a provably safe robotic roundabout system
Duperret, J. M., Hafner, M. R., & Del Vecchio, D. (2010) · 2010 IEEE/RSJ International Conference on Intelligent Robots and Systems · doi:10.1109/iros.2010.5649789 · Cited by 18 · cited 1×
“A number of solutions have been proposed Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for pro.t or commercial advantage and that copies bear this notice and the full…”
Background
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
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.