@article {PSFB06-TRO, title = {Decentralized cooperative policy for conflict resolution in multi-vehicle systems}, journal = {IEEE Trans. on Robotics}, volume = {23}, number = {6}, year = {2007}, pages = {1170-1183}, abstract = {

In this paper we propose a novel policy for steering multiple vehicles between assigned independent start and goal configurations and ensuring collision avoidance. The policy rests on the assumption that agents are all cooperating by implementing the same traffic rules. However, the policy is completely decentralized, as each agent decides its own motion by applying those rules only on locally available information, and totally scalable, in the sense that the amount of information processed by each agent and the computational complexity of the algorithms are not increasing with the number of agents in the scenario. The proposed policy applies to systems in which new vehicle may enter the scene and start interacting with existing ones at any time, while others may leave. Under mild conditions on the initial configurations, the policy is shown to be safe, i.e. to guarantee collision avoidance throughout the system evolution. In the paper, conditions are discussed on the desired configurations of agents under which the ultimate convergence of all vehicles to their goals can also be guaranteed. To show that such conditions are actually necessary and sufficient, which turns out to be a challenging liveness verification problem for a complex hybrid automaton, we employ a probabilistic verification method. The paper finally reports on simulations for systems of several tens of vehicles, and with some experimental implementation showing the practicality of the approach.

}, keywords = {Embedded Control, Robotics}, author = {L. Pallottino and V. G. Scordio and E. Frazzoli and A. Bicchi} } @conference {PSFB-MTNS06, title = {Decentralized and scalable conflict resolution strategy for multi-agents systems}, booktitle = {Int. Symp. on Mathematical Theory of Networks and Systems}, year = {2006}, abstract = {

A decentralized cooperative collision avoidance control policy for planar vehicle recently proposed is herein considered. Given some simple conditions on initial configurations of agents, the policy is known to ensure safety (i.e., collision avoidance) for an arbitrarily large number of vehicles. The method is highly scalable, and effective solutions can be obtained for several tens of autonomous agents. On the other hand, the liveness property of the policy, i.e. the capability of negotiating a solution in finite time, is not yet completely understood. First a 3D workspace extension is proposed. Furthermore, based on a condition on target configuration previously proposed, some general results on the liveness property are reported. Finally, qualitative evaluations on the strategy and on the proposed target sparsity condition are pointed out.

}, keywords = {Embedded Control, Robotics}, author = {L. Pallottino and V. G. Scordio and E. Frazzoli and A. Bicchi} } @conference {PSFB05, title = {Decentralized Cooperative Conflict Resolution for Multiple Nonholonomic Vehicles}, booktitle = {Proc. AIAA COnf. on Guidance, Navigation and Control}, year = {2005}, abstract = {

In this paper, we consider the problem of collision-free motion planning for multiple nonholonomic planar vehicles. Each vehicle is capable of moving at constant speed along paths with bounded curvature, and is aware of the position and heading of other vehicles within a certain sensing radius. No other information exchange is required between vehicles. We propose a spatially decentralized, cooperative hybrid control policy that ensures safety for arbitrary numbers of vehicles. Furthermore, we show that under certain conditions, the policy avoids dead- and livelock, and eventually all vehicles reach their intended targets. Simulations and experimental results are presented and discussed.

}, keywords = {Embedded Control, Robotics}, author = {L. Pallottino and V. G. Scordio and E. Frazzoli and A. Bicchi} }