Efficient algorithms for collision avoidance at intersections
Open Access
- 17 April 2012
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 145-154
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 problemKeywords
This publication has 13 references indexed in Scilit:
- Supervisory control of differentially flat systems based on abstraction2011
- Computational Tools for the Safety Control of a Class of Piecewise Continuous Systems with Imperfect Information on a Partial OrderSIAM Journal on Control and Optimization, 2011
- Monotone control systemsIEEE Transactions on Automatic Control, 2003
- Computational techniques for the verification of hybrid systemsProceedings of the IEEE, 2003
- Introduction to Lattices and Order2002
- Controllers for reachability specifications for hybrid systemsAutomatica, 1999
- Differential Equations with Discontinuous Righthand Sides1988
- Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey1979
- Two-Processor Scheduling with Start-Times and DeadlinesSIAM Journal on Computing, 1977
- Complexity of Machine Scheduling Problems1977