Supervisory control for collision avoidance in vehicular networks using discrete event abstractions

摘要

We consider the problem of controlling a set of vehicles at an intersection, in the presence of uncontrolled vehicles and a bounded disturbance. We begin by discretizing the system in space and time to construct a suitable discrete event system (DES) abstraction, and formally define the problem to be solved as that of constructing a supervisor over the discrete state space that is safe (i.e., collision-free), non-deadlocking (i.e., the vehicles all cross the intersection eventually), and maximally permissive with respect to the chosen discretization. We show how to model the uncontrolled vehicles and the disturbance through uncontrollable events of the DES abstraction. We define two types of relations between systems and their abstraction: state reduction and exact state reduction. We prove that, when the abstraction is a state reduction of a continuous system, then we can obtain a safe, non-deadlocking, and maximally permissive memoryless supervisor. This is obtained by translating safety and non-deadlocking specifications to the abstract domain, synthesizing the supervisor in this domain, and finally translating the supervisor back to the concrete domain. We show that, when the abstraction is an exact state reduction, the resulting supervisor will be maximally permissive among the class of all supervisors, not merely memoryless ones. Finally, we provide a customized algorithm and demonstrate its scalability through simulation.