Efficient algorithms for collision avoidance at intersections
By Alessandro Colombo, D. Vecchio. 2012
142 citations recorded by the source corpus.
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.
Subfields: Computational Theory and Mathematics, Control and Systems Engineering, Industrial and Manufacturing Engineering
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Control and Systems Engineering
- Kazuya Takeda
- Cristofer Englund
- Alexander Carballo
- Lei Chen
- Ekim Yurtsever
- Jacob Lambert
- Andreas A. Malikopoulos
- Jackeline Rios-Torres
Citations in the corpus
- A Survey of Autonomous Driving: Common Practices and Emerging Technologies (2019, background): “Level two is partial automation to which advanced assistance systems such as emergency braking or collision avoidance [33], [34]”
- Cooperative Collision Avoidance at Intersections: Algorithms and Experiments (2013, background): “More recently, work that employs job-scheduling techniques [8], [17] and optimal control [19] for ICA has appeared.”
- Cooperative Intersection Management: A Survey (2016, background): “The authors would like to thank the anonymous reviewers for their invaluable comments that help improve the quality of this paper significantly.”
- Explanations in Autonomous Driving: A Survey (2021, background): “assistance system components such as emergency braking or collision avoidance [130], [131].”