Efficient algorithms for collision avoidance at intersections

Colombo, Alessandro; Del Vecchio, Domitilla · 2012 · Crossref

DOI: 10.1145/2185632.2185656

archive: archived pipeline: cataloged verified

Get this paper ↗ (DOI — opens at the source; we link to it, we don't host it)

Summary

This paper addresses the challenge of synthesizing a least-restrictive controller for collision avoidance among multiple vehicles traversing an intersection. While previous research focused on longitudinal dynamics or rear-end collisions, this work tackles the computationally harder problem of preventing collisions caused by driver errors at intersection points. The authors define the safety problem as determining membership in the maximal controlled invariant set—the largest set of states from which a collision-avoiding control exists. They demonstrate that for a general model of vehicle dynamics, checking membership in this set is NP-hard, rendering exact solutions infeasible for real-time applications involving many vehicles. To address this complexity, the authors map the collision avoidance problem onto a scheduling problem from operations research. They prove that the safety problem is equivalent to a modified scheduling problem where vehicles are treated as jobs with specific release times, deadlines, and durations. By leveraging computational complexity theory, they show that this scheduling formulation is NP-complete. Consequently, they develop an approximate algorithm that solves the problem with polynomial complexity and provable error bounds. This approach allows for the design of a hybrid supervisor that periodically solves the scheduling problem to select safe inputs for agents with continuous dynamics. The proposed solution involves two main components: an exact algorithm for small-scale problems and an approximate algorithm for larger systems. The exact method enumerates all permutations of vehicle orderings, which is computationally expensive. The approximate method introduces constraints that simplify the problem, allowing it to be solved in polynomial time while guaranteeing that the solution remains within a bounded distance from the optimal safety set. The supervisor uses this approximate solution to enforce safety, ensuring that no collisions occur as long as agents adhere to the dynamic model. The significance of this work lies in providing a scalable, theoretically grounded framework for intersection safety. By bridging control theory and scheduling literature, the authors offer a method that balances computational efficiency with safety guarantees. This enables the deployment of collision avoidance systems in intelligent transportation networks with a larger number of vehicles than previously possible. The results imply that while exact safety verification is intractable for general cases, high-quality approximate solutions can be computed efficiently, facilitating real-time control of autonomous or assisted vehicles at complex intersections.

Provenance

The full processing record for this entry. Every stage of this paper's journey through the pipeline is logged — what ran, with which tool and model, how many attempts it took, and when it last completed.

Summary generated by qwen3.6-27b-prismaquant on 2026-06-26; verification: verified.

Topics

Ranked by relevance to this paper. Hover a topic for its definition.

• situational awareness