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.”
BackgroundMixed-Integer Linear Programming for Optimal Scheduling of Autonomous Vehicle Intersection Crossing
Fayazi, S. A., & Vahidi, A. (2018) · IEEE Transactions on Intelligent Vehicles · doi:10.1109/tiv.2018.2843163 · Cited by 246
“[21] view the time interval that each vehicle spends in an intersection as the length of the job to be executed.”
BackgroundAn MPC-Based Approach to Provable System-Wide Safety and Liveness of Autonomous Ground Traffic
Kim, K.-D., & Kumar, P. R. (2014) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2014.2351911 · Cited by 166
“An interesting result shown in [12] is that it is NP-hard to check membership in the maximal controlled invariant set which is the largest set of states for which there exists a control that avoids collisions, and an algorithm is proposed to solve such a problem approxi-”
BackgroundCollision Avoidance: A Literature Review on Threat-Assessment Techniques
Dahl, J., de Campos, G. R., Olsson, C., & Fredriksson, J. (2018) · IEEE Transactions on Intelligent Vehicles · doi:10.1109/tiv.2018.2886682 · Cited by 154
“The approaches proposed in [54] and [36] are based on the solution of two separate problems: (i) the Verification Problem, that determines if there exists an input signal that leads all vehicles safely through the intersection; and (ii) the Supervisor Problem, returning a safe overriding control signal when safety”
BackgroundMethodInfluentialLeast Restrictive Supervisors for Intersection Collision Avoidance: A Scheduling Approach
Colombo, A., & Vecchio, D. D. (2015) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2014.2381453 · Cited by 150
“Determining the maximal controlled invariant set is often a computationally difficult problem, and has been proved to be NP-hard in the case of some collision avoidance A. Colombo is with DEIB at Politecnico di Milano, Italy, e-mail: alessandro.colombo@polimi.it.”
BackgroundSelf-citationCoordination of Cooperative Autonomous Vehicles: Toward safer and more efficient road transportation
Hult, R., de Campos, G. R., Steinmetz, E., Hammarstrand, L., Falcone, P., & Wymeersch, H. (2016) · IEEE Signal Processing Magazine · doi:10.1109/msp.2016.2602005 · Cited by 150
An Intersection Game-Theory-Based Traffic Control Algorithm in a Connected Vehicle Environment
Elhenawy, M. M. Z., Elbery, A. A., Hassan, A. A., & Rakha, H. A. (2015) · IEEE International Conference on Intelligent Transportation Systems (ITSC) · doi:10.1109/itsc.2015.65 · Cited by 135
“solved this problem by finding the maximum controlled invariant set and checking membership in this set using an algorithm that approximated the solution [9].”
MethodA Survey on Intersection Management of Connected Autonomous Vehicles
Khayatian, M., Mehrabian, M., Andert, E., Dedinsky, R., Choudhary, S., Lou, Y., & Shirvastava, A. (2020) · ACM Transactions on Cyber-Physical Systems · doi:10.1145/3407903 · Cited by 131
“References [28, 36] look at the intersection management as a verification problem where the goal is to check if there exists an input such that the system can avoid the set of Bad States or an un-safe situation.”
BackgroundArchitecture and key technologies for Internet of Vehicles: A survey
Yang, F., Li, J., Lei, T., & Wang, S. (2017) · Journal of Communications and Information Networks · doi:10.1007/s41650-017-0018-6 · Cited by 129
“In order to avoid a hybrid collision, Colombo et al. [67] indicated a method, which utilizes the vehicles dynamic model to solve the vehicle scheduling problems.”
MethodA Comprehensive Survey on Cooperative Intersection Management for Heterogeneous Connected Vehicles
Gholamhosseinian, A., & Seitz, J. (2022) · IEEE Access · doi:10.1109/access.2022.3142450 · Cited by 122
“Researchers in [361] and [362] addressed measurement and input uncertainties via some approximation algorithms for collision avoidance heuristically.”
BackgroundOptimal Coordination of Automated Vehicles at Intersections: Theory and Experiments
Hult, R., Zanon, M., Gros, S., & Falcone, P. (2018) · IEEE Transactions on Control Systems Technology · doi:10.1109/tcst.2018.2871397 · Cited by 114
“, [3] or [5], and means that no vehicle ever reverses.”
BackgroundCooperative receding horizon conflict resolution at traffic intersections
de Campos, G. R., Falcone, P., Wymeersch, H., Hult, R., & Sjoberg, J. S. (2014) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2014.7039840 · Cited by 113
“Our solution relies on a cooperatively pre-determined decision order (enabling sequential decision making) combined with a receding horizon implementation to compute optimal collision-free trajectories (contrary to [11], which focuses on feasible crossings sequences and not optimality).”
BackgroundMethodde Campos, G. R., Falcone, P., Hult, R., Wymeersch, H., & Sjoberg, J. S. (2017) · IEEE Intelligent Transportation Systems Magazine · doi:10.1109/mits.2016.2630585 · Cited by 112
“Unsurprisingly, the centralized problem as been shown to be NP-hard [35], [36] and therefore exact solutions become intractable for practical problem sizes.”
BackgroundMiculescu, D., & Karaman, S. (2019) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2019.2921659 · Cited by 107
“However, the scheduling problem is computationally challenging; in fact, computing the optimal schedule was shown to be NP-hard [23].”
BackgroundAn approximate solution to the optimal coordination problem for autonomous vehicles at intersections
Hult, R., de Campos, G. R., Falcone, P., & Wymeersch, H. (2015) · Proceedings of the ... American Control Conference/Proceedings of the American Control Conference · doi:10.1109/acc.2015.7170826 · Cited by 86
“Email: {robert.hult,gabriel.campos,paolo.falcone, henkw}@chalmers.se maker is assumed, which manage time-space reservations in the intersection to avoid collisions [4–8].”
BackgroundConvex modeling of conflict resolution at traffic intersections
Murgovski, N., de Campos, G. R., & Sjoberg, J. S. (2015) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2015.7402953 · Cited by 76
“Among others, [2], [16], [17] exploited hybrid systems theory and [18], [19], [20], [21] a scheduling-based approach.”
BackgroundSafety Verification and Control for Collision Avoidance at Road Intersections
Ahn, H., & Vecchio, D. D. (2017) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2017.2729661 · Cited by 76
“In [20]–[24], the safety verification problem is solved exactly with the assumption that the paths of vehicles intersect only at a single conflict point.”
BackgroundPolling-systems-based control of high-performance provably-safe autonomous intersections
Miculescu, D., & Karaman, S. (2014) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2014.7039600 · Cited by 70
“Similar problems were also studied from the perspective of hybrid control systems [12], [13] and air traffic management [14], [15].”
BackgroundReal-Time Cooperative Vehicle Coordination at Unsignalized Road Intersections
Luo, J., Zhang, T., Hao, R., Li, D., Chen, C., Na, Z., & Zhang, Q. (2023) · IEEE Transactions on Intelligent Transportation Systems · doi:10.1109/tits.2023.3243940 · Cited by 67
“The authors in [20]–[25] adopted similar rules that the whole intersection area was reserved for conflicting vehicles one after another, namely collision set (or critical set) strategy.”
BackgroundLu, G., Shen, Z., Liu, X., Nie, Y. M., & Xiong, Z. (2021) · Transportation Research Part B Methodological · doi:10.1016/j.trb.2021.10.012 · Cited by 62
Ding, N., Meng, X., Xia, W., Wu, D., Li, X., & Chen, B. (2019) · IEEE Transactions on Industrial Informatics · doi:10.1109/tii.2019.2959795 · Cited by 57
“In addition to the infrastructure planning and traffic management [3], research works on roundabouts mainly focus on vehicle strategies and path planning [4], [5].”
BackgroundPrimal decomposition of the optimal coordination of vehicles at traffic intersections
Hult, R., Zanon, M., Gros, S., & Falcone, P. (2016) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2016.7798649 · Cited by 54
“Coordination of communicating automated vehicles at intersections, on-ramps, and in other traffic scenarios where roads merge or cross is a topic that has attracted a lot of attention in recent years, see, e.g., [3],[4], [8] or [12].”
BackgroundEnsuring drivability of planned motions using formal methods
Schürmann, B., Hes, D., Eilbrecht, J., Stursberg, O., Köster, F., & Althoff, M. (2017) · IEEE International Conference on Intelligent Transportation Systems (ITSC) · doi:10.1109/itsc.2017.8317647 · Cited by 54
“An approach for safely entering an intersection is presented in [12].”
MethodAutomation of a T-intersection Using Virtual Platoons of Cooperative Autonomous Vehicles
Medina, A. I. M., van de Wouw, N., & Nijmeijer, H. (2015) · IEEE International Conference on Intelligent Transportation Systems (ITSC) · doi:10.1109/itsc.2015.275 · Cited by 53
“There are several approaches for the underlying decision algorithm, such as: vehicle trajectory prediction to identify conflict situations [2], modeling the intersection as an scheduling problem [3], and the analysis of the so-called conflict zone plots to determine a priority map [4].”
MethodSharing is Caring: Socially-Compliant Autonomous Intersection Negotiation
Buckman, N., Pierson, A. N., Schwarting, W., Karaman, S., & Rus, D. L. (2019) · IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) · doi:10.1109/iros40897.2019.8967997 · Cited by 52
“Thus, many approaches look to find locally-optimal solutions, using control policies that guarantee safe passage [2], [3], [4], [5], [6], game theoretic approaches [7], learning-based control methods [8], [9], and decentralized algorithms [10], [11].”
BackgroundAoki, S., & Rajkumar, R. (2019) · IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA) · doi:10.1109/rtcsa.2019.8864572 · Cited by 51
“A motion-planning approach has also been studied [34], [35], [36].”
MethodLi, D., Zhang, J., & Liu, G. (2024) · IEEE Transactions on Intelligent Transportation Systems · doi:10.1109/tits.2023.3346048 · Cited by 50
“As for MVC, a smart management system is responsible to allocate the time and space resources of intersection, so as to realize the unified control of all vehicles to optimize the overall safety and efficiency [4], [5], [6].”
BackgroundCollision free autonomous ground traffic: a model predictive control approach
Kim, K.-D. (2013) · ACM/IEEE International Conference on Cyber-Physical Systems (ICCPS) · doi:10.1145/2502524.2502532 · Cited by 50
“An interesting result about collision avoidance at intersection is shown in [2], viz.”
BackgroundOptimisation-based coordination of connected, automated vehicles at intersections
Hult, R., Zanon, M., Gros, S., Wymeersch, H., & Falcone, P. (2020) · Vehicle System Dynamics · doi:10.1080/00423114.2020.1755446 · Cited by 49
Ballroom Intersection Protocol: Synchronous Autonomous Driving at Intersections
Azimi, R., Bhatia, G., Rajkumar, R., & Mudalige, P. (2015) · IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA) · doi:10.1109/rtcsa.2015.20 · Cited by 48
“Advanced Driver-Assist Systems (ADAS), such as adaptive cruise control, lane keeping, stability control and automated valet parking, provide driving control with less and less driver intervention.”
BackgroundSupervisory control for intersection collision avoidance in the presence of uncontrolled vehicles
Ahn, H., Colombo, A., & Vecchio, D. D. (2014) · Proceedings of the ... American Control Conference/Proceedings of the American Control Conference · doi:10.1109/acc.2014.6859163 · Cited by 48
“The parallel composition of equation (1) and (2) for all n vehicles describes the system dynamics. ẋ = f(x,u,d) y = h(x) (3) Assume that this system has a unique solution which continuously depends on the input and the disturbance.”
BackgroundMethodInfluentialSelf-citationAutonomous Intersection Management: A Heuristic Approach
Chouhan, A. P., & Banda, G. (2018) · IEEE Access · doi:10.1109/access.2018.2871337 · Cited by 48
“Various dedicated works have been established for avoiding collision of vehicles at intersection under a connected vehicle environment as in [17], [18], and [26].”
BackgroundRobust multi-agent collision avoidance through scheduling
Bruni, L., Colombo, A., & Vecchio, D. D. (2013) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2013.6760492 · Cited by 47
Self-citationHigh Throughput Vehicle Coordination Strategies at Road Intersections
Liu, C., Zhang, Y., Zhang, T., Wu, X., Gao, L. X., & Zhang, Q. (2020) · IEEE Transactions on Vehicular Technology · doi:10.1109/tvt.2020.3029933 · Cited by 47
“are current mainstream coordination strategies [17], [18].”
BackgroundOptimal cooperative motion planning for vehicles at intersectionsPreprint
Grégoire, J., Bonnabel, S., & Fortelle, A. D. L. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1310.7729 · Cited by 45
Wymeersch, H., de Campos, G. R., Falcone, P., Svensson, L., & Ström, E. G. (2015) · 2012 International Conference on Computing, Networking and Communications (ICNC) · doi:10.1109/iccnc.2015.7069408 · Cited by 42
“It can be shown that this control problem is NP-hard [24], but”
BackgroundInfluentialSemi-autonomous Intersection Collision Avoidance through Job-shop Scheduling
Ahn, H., & Vecchio, D. D. (2016) · International Conference on Hybrid Systems: computation and control · doi:10.1145/2883817.2883830 · Cited by 41
“While maintaining the same structure of the supervisor as in [10, [10, 11].”
Priority-based intersection management with kinodynamic constraints
Grégoire, J., Bonnabel, S., & Fortelle, A. D. L. (2014) · European Control Conference (ECC) · doi:10.1109/ecc.2014.6862377 · Cited by 36
“I. INTRODUCTION”
Lu, Q., & Kim, K.-D. (2018) · Applied Intelligence · doi:10.1007/s10489-018-1357-1 · Cited by 36
“In this paper, among many research problems like vehicle path planning [6], autonomous parking control [7], collision avoidance [8], [9], relation between occupant experience and intersection capacity [10], intersection management of mixed traffic [11] etc. that should be addressed toward this…”
BackgroundAn abstract model for proving safety of autonomous urban traffic
Schwammberger, M. (2018) · Theoretical Computer Science · doi:10.1016/j.tcs.2018.05.028 · Cited by 36
A Survey of Safety Warnings Under Connected Vehicle Environments
Li, H., Zhao, G., Qin, L., Aizeke, H., Zhao, X., & Yang, Y. (2020) · IEEE Transactions on Intelligent Transportation Systems · doi:10.1109/tits.2020.3026309 · Cited by 35
“try hard to find ways to synthesize controllers with the least restriction to avoid multiple vehicles colliding at the intersection [45].”
BackgroundHuman-like driving decision at unsignalized intersections based on game theory
Li, D., Liu, G., & Xiao, B. (2022) · Proceedings of the Institution of Mechanical Engineers Part D Journal of Automobile Engineering · doi:10.1177/09544070221075423 · Cited by 34
Priority-based coordination of robotsPreprint
Grégoire, J., Bonnabel, S., & Fortelle, A. D. L. (2014) · HAL · Cited by 33
Optimal Coordination of Automated Vehicles at Intersections with Turns
Hult, R., Zanon, M., Gros, S., & Falcone, P. (2019) · European Control Conference (ECC) · doi:10.23919/ecc.2019.8795770 · Cited by 32
“While the coordination of automated vehicles naturally fits in the OC framework, the resulting problems are known to be NP-hard [1].”
BackgroundAn Asynchronous Algorithm for Optimal Vehicle Coordination at Traffic Intersections
Zanon, M., Gros, S., Wymeersch, H., & Falcone, P. (2017) · IFAC-PapersOnLine · doi:10.1016/j.ifacol.2017.08.2124 · Cited by 31
Evasion planning for autonomous vehicles at intersections
Au, T.-C., Fok, C., Vishwanath, S., Julien, C., & Stone, P. (2012) · IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) · doi:10.1109/iros.2012.6385936 · Cited by 31
“Colombo and Vecchio studied the least restrictive controller for collision avoidance of vehicles at an intersection via computing the maximal controlled invariant set [8].”
BackgroundAn Abstract Model for Proving Safety of Autonomous Urban Traffic
Hilscher, M., & Schwammberger, M. (2016) · Lecture notes in computer science · doi:10.1007/978-3-319-46750-4_16 · Cited by 30
Ho, F., Gonçalves, A., Rigault, B., Geraldes, R., Chícharo, A., Cavazza, M., & Prendinger, H. (2021) · IEEE Intelligent Transportation Systems Magazine · doi:10.1109/mits.2021.3100062 · Cited by 29
“Scheduling is a widespread problem in traffic management for ground [26], [27] or air vehicles [28].”
BackgroundMethodOptimal Lane-Free Crossing of CAVs Through Intersections
Amouzadi, M., Orisatoki, M. O., & Dizqah, A. M. (2022) · IEEE Transactions on Vehicular Technology · doi:10.1109/tvt.2022.3207054 · Cited by 28
Evolution of VANETS to IoV: Applications and Challenges
Lone, F. R., Verma, H. K., & Sharma, K. P. (2021) · Tehnički glasnik · doi:10.31803/tg-20210205104516 · Cited by 27
“An algorithm that can handle a large number of vehicles based on time slots has been proposed in [30].”
BackgroundSurvey on vehicle collision prediction in VANET
Raut, S. B., & Malik, L. (2014) · IEEE International Conference on Computational Intelligence and Computing Research (ICCIC) · doi:10.1109/iccic.2014.7238552 · Cited by 27
Control of a City Road Network: Distributed Exact Verification of Traffic Safety
Colombo, A., de Campos, G. R., & Rossa, F. D. (2017) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2017.2676464 · Cited by 26
“Computation of the capture set in a multivehicle system was proved to be NP-hard in [11] and [12], therefore most verification algorithms are only applicable to fairly small systems (about 2 to 6 vehicles in [8] and [12]–[17]) unless approximations are employed [8], [18] or vehicle dynamics is greatly simplified [19]–…”
BackgroundMethodSelf-citationDriving strategy selection for cooperative vehicles using maneuver templates
Manzinger, S., Leibold, M., & Althoff, M. (2017) · IEEE Intelligent Vehicles Symposium · doi:10.1109/ivs.2017.7995791 · Cited by 26
Ahn, H., Rizzi, A., Colombo, A., & Del Vecchio, D. (2015) · 2015 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) · doi:10.1109/iros.2015.7354056 · Cited by 25
“While this supervisor is validated through experiments, several theorems that support the design, such as the non-blocking property of the supervisor, must still be provided as in [25], [13], [12].”
MethodSelf-citationA configurable synchronous intersection protocol for self-driving vehicles
Aoki, S., & Rajkumar, R. (2017) · IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA) · doi:10.1109/rtcsa.2017.8046306 · Cited by 25
“[8] modeled an intersection as a point, and formulated the intersection passing as a maximal”
BackgroundCollaboration and Optimal Conflict Resolution at an Unsignalized Intersection
Belkhouche, F. (2018) · IEEE Transactions on Intelligent Transportation Systems · doi:10.1109/tits.2018.2867256 · Cited by 25
“Results from scheduling literature are used in [37] to derive algorithms for collision avoidance at the intersection.”
MethodAdapting the Virtual Platooning Concept to Roundabout Crossing
Masi, S., Xu, P., & Bonnifait, P. (2018) · IEEE Intelligent Vehicles Symposium · doi:10.1109/ivs.2018.8500611 · Cited by 25
“While it is common to find papers in the literature that propose strategies to handle a crossroad intersection [2], [5], even focalized on cooperative driving control as [8], much fewer researches have been conducted regarding roundabouts.”
BackgroundCooperation of autonomous vehicles using a hierarchy of auction-based and model-predictive control
Rewald, H., & Stursberg, O. (2016) · IEEE Intelligent Vehicles Symposium · doi:10.1109/ivs.2016.7535523 · Cited by 24
“…the coordination of several autonomous cars, including work on real-time and safe coordination of vehicle networks [2], [3], coordination for intersection control [4], [5], [6], [7], [8], cooperative mechanisms for platooning [9], [10] or for achieving more general car formations [11], and for…”
BackgroundHult, R., Zanon, M., Frison, G., Gros, S., & Falcone, P. (2020) · Optimal Control Applications and Methods · doi:10.1002/oca.2592 · Cited by 24
“Moreover, the vehicle state and control trajectories are subject to constraints of the form Dixi(t) + Giui(t) ≥ bi, (2)”
BackgroundSupervisory control for collision avoidance in vehicular networks with imperfect measurements
Dallal, E., Colombo, A., Vecchio, D. D., & Lafortune, S. (2013) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2013.6760885 · Cited by 23
“edu algorithms that easily handle hundreds of vehicles, but cannot yet deal with uncontrolled agents or complex, realistic road topologies [3].”
BackgroundMethodSelf-citationChalaki, B., & Malikopoulos, A. A. (2019) · IEEE Conference on Control Technology and Applications (CCTA) · doi:10.1109/ccta.2019.8920448 · Cited by 23
“The problem of coordinating CAVs at the intersection is a typical scheduling problem [20], [21], [25].”
BackgroundGrégoire, J., & Frazzoli, E. (2016) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2016.7798646 · Cited by 23
“[19]).”
de Campos, G. R., Rossa, F. D., & Colombo, A. (2015) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2015.7402456 · Cited by 22
“The standard, non-optimal implementation of the Supervisor Problem proposed in [18], [20]–[23] is equivalent to solving (1) with cost function J(udes,u) := {”
BackgroundMethodSelf-citationSupervisory control for collision avoidance in vehicular networks using discrete event abstractions
Dallal, E., Colombo, A., Vecchio, D. D., & Lafortune, S. (2016) · Discrete Event Dynamic Systems · doi:10.1007/s10626-016-0228-3 · Cited by 22
“On the other hand, the scheduling meth-ods of Colombo and Del Vecchio (2012), Bruni et al. (2013), and Ahn et al. (2014) do not explicitly pre-compute sets of states from which there exist solutions to the corresponding scheduling problems, but instead perform verification on-line.”
BackgroundSelf-citationCommunication analysis for centralized intersection crossing coordination
Steinmetz, E., Hult, R., de Campos, G. R., Wildemeersch, M., Falcone, P., & Wymeersch, H. (2014) · International Symposium on Wireless Communication Systems · doi:10.1109/iswcs.2014.6933465 · Cited by 22
“More specifically, [2], [3] present a supervisory controller that overrides the driver’s commands if these take the vehicle out of the maximum control invariant set with respect to a collision inside the intersection.”
BackgroundSupervisory control for collision avoidance in vehicular networks using discrete event abstractions
Dallal, E., Colombo, A., Vecchio, D. D., & Lafortune, S. (2013) · Proceedings of the ... American Control Conference/Proceedings of the American Control Conference · doi:10.1109/acc.2013.6580514 · Cited by 21
Self-citationReal-Time Intelligent Autonomous Intersection Management Using Reinforcement Learning
Gunarathna, U., Karunasekera, S. A., Borovica‐Gajic, R., & Tanin, E. (2022) · IEEE Intelligent Vehicles Symposium · doi:10.1109/iv51971.2022.9827188 · Cited by 18
Merging Vehicles at Junctions using Mixed-Integer Model Predictive Control
Bali, C., & Richards, A. G. (2018) · European Control Conference (ECC) · doi:10.23919/ecc.2018.8550577 · Cited by 18
“Colombo and Del Vecchio [13] studied the full hybrid problem of crossing at junctions, noting the importance of invariance, in terms of complexity of the scheduling.”
BackgroundA Computationally Efficient Bi-Level Coordination Framework for CAVs at Unsignalized Intersections
Luo, J., Zhang, T., & Zhang, Q. (2023) · IEEE Transactions on Vehicular Technology · doi:10.1109/tvt.2023.3321335 · Cited by 17
“However,centralizedstrategies confrontchallengesduetothecontradictionbetweenstringent real-timeactuationrequirementsandthehighcomputational complexityrequiredforoptimizations[13],[14].”
Design of Driver-Assist Systems Under Probabilistic Safety Specifications Near Stop Signs
Forghani, M., McNew, J. M., Hoehener, D., & Vecchio, D. D. (2015) · IEEE Transactions on Automation Science and Engineering · doi:10.1109/tase.2015.2499221 · Cited by 17
“A number of automotive companies have already released automated braking systems that, based on on-board sensors, warn the driver and reduce the vehicle’s speed when the vehicle approaches an obstacle [3], [4], [31].”
BackgroundEfficiently Bounding the Probabilities of Vehicle Collision at Intelligent Intersections
Thunberg, J., Sidorenko, G., Sjöberg, K., & Vinel, A. V. (2021) · IEEE Open Journal of Intelligent Transportation Systems · doi:10.1109/ojits.2021.3058449 · Cited by 14
“It is an NP hard problem to determine the largest set of states for multiple vehicles passing an intersection, for which there are controllers such that collisions are avoided [5].”
BackgroundColombo, A. (2014) · International Symposium on Wireless Communication Systems · doi:10.1109/iswcs.2014.6933395 · Cited by 14
“The results presented here improve over the current state of the art, in particular extending the results in [9], [10], allowing to solve the verification problem (VP) exactly over a network with an arbitrary number of intersections, provided that these verify a sparsity condition.”
BackgroundSelf-citationRobustness of Bio-Inspired Visual Systems for Collision Prediction in Critical Robot Traffic
Fu, Q., Sun, X., Liu, T., Hu, C., & Yue, S. (2021) · Frontiers in Robotics and AI · doi:10.3389/frobt.2021.529872 · Cited by 13
“The risk of intersection could also be alleviated by sensor fusion strategy, or other algorithms in intelligent transportation system (Colombo and Vecchio, 2012).”
BackgroundInfluentialRoad Capacity and Throughput for Safe Driving Autonomous Vehicles
Wang, Y., & Wei, H. (2020) · IEEE Access · doi:10.1109/access.2020.2995312 · Cited by 12
“In general, intersection management without further restrictions is a multi-agent, and thus NP-hard problem [21].”
BackgroundSuicidal Pedestrian: Generation of Safety-Critical Scenarios for Autonomous Vehicles
Yang, Y., Kujanpää, K., Babadi, I. A., Pajarinen, J., & Ilin, A. (2023) · IEEE International Conference on Intelligent Transportation Systems (ITSC) · doi:10.1109/itsc57777.2023.10422034 · Cited by 11
“Two approaches have emerged: modular driving systems that design and train each sub-module separately according to its functions [1], [2], and end-to-end models that directly perform decisions based on raw sensor inputs [3], [4].”
BackgroundCSIP: A Synchronous Protocol for Automated Vehicles at Road Intersections
Aoki, S., & Rajkumar, R. (2019) · ACM Transactions on Cyber-Physical Systems · doi:10.1145/3226032 · Cited by 11
“Colombo et al. [11] modeled an intersection as a point, and formulated the intersection passing as a maximal controlled invariant set problem.”
BackgroundEstimation for decentralized safety control under communication delay and measurement uncertainty
Bresch‐Pietri, D., & Vecchio, D. D. (2015) · Automatica · doi:10.1016/j.automatica.2015.06.009 · Cited by 11
“In particular, computationally efficient algorithms have been proposed for systems with two or more agents by leveraging the order preserving dynamics [1,5,8,13,16,18,40], which is important for transportation applications.”
BackgroundMethodInfluentialGenerating Visibility-Aware Trajectories for Cooperative and Proactive Motion Planning
Buckman, N., Pierson, A. N., Karaman, S., & Rus, D. L. (2020) · Proceedings - IEEE International Conference on Robotics and Automation/Proceedings · doi:10.1109/icra40945.2020.9196809 · Cited by 10
“In an effort to increase safety, prior work considers how to design controllers that can interact with human pedestrians and traffic [6], [7], [8] as well as methods for interacting cooperatively with other robots [9], [10], [11], [12], [13].”
Backgroundde Campos, G. R., Rossa, F. D., & Colombo, A. (2017) · IEEE Transactions on Human-Machine Systems · doi:10.1109/thms.2017.2776205 · Cited by 10
“in [13] and [18], which exploit a similar equivalence to the one presented in Section V-A.”
BackgroundMethodSelf-citationCo-operative Driving at Intersections using Vehicular Networks and Vehicle-Resident Sensing
Azimi, R. (2015) · KiltHub Repository · doi:10.1184/r1/6715379 · Cited by 10
Design of Safety Petri Net Controllers for Deadlock Prevention at a Class of Road Intersections
Wei, Y., Ning, H., An, Y., Wu, N., & Zhao, X. (2023) · IEEE Transactions on Intelligent Transportation Systems · doi:10.1109/tits.2023.3294283 · Cited by 9
“Recent studies mainly focus on the design of safety controllers [5], Yaxin Wei, Haijing Ning, Yisheng An, and Xiangmo Zhao are with the School of Information Engineering, Chang’an University, Xi’an 710064, China (e-mail: yxwei106@gmail.com; hjning@chd.edu.cn; aysm@chd.edu.cn; xmzhao@chd.edu.cn).”
BackgroundKojchev, S., Hult, R., Fredriksson, J., & Kneissl, M. (2023) · IEEE Transactions on Intelligent Transportation Systems · doi:10.1109/tits.2023.3320168 · Cited by 9
“In general, the coordination problem is difficult to solve and is formally shown to be NP-hard in [4].”
BackgroundDistributed Consensus to Enable Merging and Spacing of UAS in an Urban Environment
Balachandran, S., Munoz, C. A., & Consiglio, M. (2018) · International Conference on Unmanned Aircraft Systems (ICUAS) · doi:10.1109/icuas.2018.8453460 · Cited by 9
“Algorithm 1 Scheduling algorithm (From [10]) Require: r = {r1, .”
MethodInfluentialA Decentralized Framework to Support UAS Merging and Spacing Operations in Urban Canyons
Balachandran, S., Manderino, C., Munoz, C. A., & Consiglio, M. (2020) · International Conference on Unmanned Aircraft Systems (ICUAS) · doi:10.1109/icuas48674.2020.9213973 · Cited by 9
“Colombo et al. [11] use a schedule to construct a maximal control invariant set that will guarantee safe transit through an intersection.”
BackgroundMethodAbstraction-Based Safety Verification and Control of Cooperative Vehicles at Road Intersections
Ahn, H., & Colombo, A. (2019) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2019.2953213 · Cited by 9
“results [10]–[16] in that it now handles more complicated intersection scenarios including multiple conflict areas, road junctions, and merging lanes.”
BackgroundMethodInfluentialSelf-citationModeling concurrency and reconfiguration in vehicular systems: A π-calculus approach
Campbell, J., Tuncali, C. E., Liu, P., Pavlic, T. P., Özgüner, Ü., & Fainekos, G. (2016) · IEEE International Conference on Automation Science and Engineering (CASE) · doi:10.1109/coase.2016.7743450 · Cited by 8
Scheduling in Real-Time Mobile Systems
Chen, C., Hong, Z., & Jiang, J. (2022) · ACM Transactions on Embedded Computing Systems · doi:10.1145/3517747 · Cited by 8
“Colombo and Del Vecchio [15, 16] provide a semi-autonomous framework with the scheduling approach by proving the equivalence between the verification problem and the job-shop scheduling problem, and de-sign a least restrictive supervisor for collision avoidance at a special intersection scenario…”
BackgroundMethodLane-Free Crossing of CAVs through Intersections as a Minimum-Time Optimal Control Problem
Amouzadi, M., Orisatoki, M. O., & Dizqah, A. M. (2022) · IFAC-PapersOnLine · doi:10.1016/j.ifacol.2022.07.578 · Cited by 8
Kojchev, S., Hult, R., & Fredriksson, J. (2022) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc51059.2022.9992529 · Cited by 8
“The problem has been formally shown to be NP-hard [3], and such problems are in general difficult to solve.”
BackgroundCooperative Intersection Collision Avoidance in a Constrained Communication Environment
Colombo, A., & Wymeersch, H. (2015) · IEEE International Conference on Intelligent Transportation Systems (ITSC) · doi:10.1109/itsc.2015.70 · Cited by 8
“III, exact and efficient approximate algorithms to determine if a state (x, ẋ) belongs to the MCIS are found in [15], [19].”
BackgroundSelf-citationSafe and stabilizing distributed multi-path cellular flows
Johnson, T. T., & Mitra, S. (2015) · Theoretical Computer Science · doi:10.1016/j.tcs.2015.01.023 · Cited by 8
“Efficient distributed intersection control algorithms are developed in [49].”
Optimal motion planning for automated vehicles with scheduled arrivals at intersections
Müller, E. R., Wahlberg, B., & Carlson, R. C. (2018) · European Control Conference (ECC) · doi:10.23919/ecc.2018.8550329 · Cited by 8
“The latter case, although more general, typically leads to nonconvex formulations and NP-hard problems [11].”
BackgroundNor, M. H. M., & Namerikawa, T. (2019) · SICE Journal of Control Measurement and System Integration · doi:10.9746/jcmsi.12.215 · Cited by 8
“Several research efforts in this direction have been obtained for example considering the optimal time interval that each vehicle needs to spend in an intersection [8],[9], considering the optimal time for each vehicle to arrive at an intersection [10],[11], and jobshop scheduling based formulation [12].”
BackgroundDistributed controllers for provably safe, live and fair autonomous car manoeuvres in urban traffic
Schwammberger, M. (2020) · Carl von Ossiezky University of Oldenburg · Cited by 8
Ensuring Safety at Intelligent Intersections: Temporal Logic Meets Reachability Analysis
Arfvidsson, K. M., Jiang, F. J., Johansson, K. H., & Mårtensson, J. (2024) · IEEE Intelligent Vehicles Symposium · doi:10.1109/iv55156.2024.10588818 · Cited by 7
“One of the core challenges is the difficulty in computing the maximal controlled invariant sets for intersections in a general, computationally-tractable way, since finding the exact solution is an NP-complete problem [4].”
BackgroundColombo, A., & Rossa, F. D. (2018) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2018.2804860 · Cited by 7
“avoidance have been discussed in [12], [13] and further expanded in [14]–[19].”
BackgroundMethodSelf-citation
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.