DocumentCode :
91897
Title :
Least Restrictive Supervisors for Intersection Collision Avoidance: A Scheduling Approach
Author :
Colombo, Alessandro ; Del Vecchio, Domitilla
Author_Institution :
Dipt. di Elettron., Inf. e Bioingegneria, Inf. e Bioingegneria, Milan, Italy
Volume :
60
Issue :
6
fYear :
2015
fDate :
Jun-15
Firstpage :
1515
Lastpage :
1527
Abstract :
We consider a cooperative conflict resolution problem that finds application, for example, in vehicle intersection crossing. We seek to determine minimally restrictive supervisors, which allow agents to choose all possible control actions that keep the system safe, that is, conflict free. This is achieved by determining the maximal controlled invariant set, and then by determining control actions that keep the system state inside this set. By exploiting the natural monotonicity of the agents dynamics along their paths, we translate this problem into an equivalent scheduling problem. This allows us to leverage existing results in the scheduling literature to obtain both exact and approximate solutions. The approximate algorithms have polynomial complexity and can handle large problems with guaranteed approximation bounds. We illustrate the application of the proposed algorithms through simulations in which vehicles crossing an intersection are overridden by the supervisor only when necessary to maintain safety.
Keywords :
approximation theory; collision avoidance; computational complexity; mobile robots; multi-agent systems; multi-robot systems; road traffic control; road vehicles; scheduling; agent dynamics monotonicity; approximate algorithm; cooperative conflict resolution; intersection collision avoidance; least restrictive supervisor; polynomial complexity; scheduling approach; vehicle intersection crossing; Approximation algorithms; Approximation methods; Complexity theory; Safety; Schedules; Vectors; Vehicles; Collision avoidance; Maximal controlled invariant set; collision avoidance; intersection; maximal controlled invariant set; multi-agent system; safety; scheduling; supervisory control; verification;
fLanguage :
English
Journal_Title :
Automatic Control, IEEE Transactions on
Publisher :
ieee
ISSN :
0018-9286
Type :
jour
DOI :
10.1109/TAC.2014.2381453
Filename :
6985592
Link To Document :
بازگشت