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.

VL - 23 ER - TY - CONF T1 - Decentralized and scalable conflict resolution strategy for multi-agents systems T2 - Int. Symp. on Mathematical Theory of Networks and Systems Y1 - 2006 A1 - L. Pallottino A1 - V. G. Scordio A1 - E. Frazzoli A1 - A. Bicchi KW - Embedded Control KW - Robotics AB -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.

JF - Int. Symp. on Mathematical Theory of Networks and Systems ER - TY - CONF T1 - Probabilistic verification of a decentralized policy for conflict resolution in multi-agent systems T2 - Proc. IEEE Int. Conf. on Robotics and Automation Y1 - 2006 A1 - L. Pallottino A1 - V. G. Scordio A1 - E. Frazzoli A1 - A. Bicchi KW - Embedded Control KW - Robotics AB -In this paper, we consider a decentralized cooperative control policy proposed recently for steering multiple non-holonomic vehicles between assigned start and goal configurations while avoiding collisions. The policy is known to ensure safety (i.e., collision avoidance) for an arbitrarily large number of vehicles, if initial configurations satisfy certain conditions. 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. In this paper, we introduce a condition on the final vehicle configurations, which we conjecture to be sufficient for guaranteeing liveness. Because of the overwhelming complexity of proving the sufficiency of such condition, we assess the correctness of the conjecture in probability through the analysis of the results of a large number of randomized experiments.

JF - Proc. IEEE Int. Conf. on Robotics and Automation N1 -Correct version

ER - TY - CONF T1 - Decentralized Cooperative Conflict Resolution for Multiple Nonholonomic Vehicles T2 - Proc. AIAA COnf. on Guidance, Navigation and Control Y1 - 2005 A1 - L. Pallottino A1 - V. G. Scordio A1 - E. Frazzoli A1 - A. Bicchi KW - Embedded Control KW - Robotics AB -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.

JF - Proc. AIAA COnf. on Guidance, Navigation and Control ER - TY - CONF T1 - Decentralized Cooperative Conflict Resolution Among Multiple Autonomous Mobile Agents T2 - cdc Y1 - 2004 A1 - L. Pallottino A1 - V. G. Scordio A1 - A. Bicchi KW - Embedded Control KW - Robotics AB -In this paper we consider policies for cooperative, decentralized traffic management among a number of autonomous mobile agents. The conflict resolution problem is addressed considering realistic restrictions on possible maneuvers. We formulate this problem as one in Mixed Integer Linear Programming (MILP). The method, which proves successful in a centralized implementation with a large number of cooperating agents, is also extended to a decentralized setting. Conditions for the existence of conflict avoidance maneuvers for a system of 5 autonomous agents with a transitive information structure are provided, along with the explicit policy to be applied by each agent.

JF - cdc ER - TY - CHAP T1 - On The Problem of Simultaneous Localization, Map Building, and Servoing of Autonomous Vehicles T2 - Advances in Control of Articulated and Mobile Robots Y1 - 2004 A1 - A. Bicchi A1 - F. Lorussi A1 - P. Murrieri A1 - V. G. Scordio ED - B. Siciliano ED - A. De Luca ED - C. Melchiorri ED - G. Casalino KW - Embedded Control KW - Robotics AB -In this chapter, we consider three of the main problems that arise in the navigation of autonomous vehicles in partially or totally unknown environments, i.e. building a map of the environment, self-localizing, and servoing the robot so as to achieve given goals based on sensorial information. As compared to most part of the existing literature on SLAM, we privilege here a system-theoretic view to the problem, which allows the localization and mapping problems to be cast in a unified framework with the control problem. The chapter is an overview of existing results in this vein, and of some interesting directions for research in the field. All chapters of this volume were revised and published online March 2005. The volume number was corrected from 4010 to 10.

JF - Advances in Control of Articulated and Mobile Robots T3 - STAR - Springer Tracts in Advanced Robotics PB - Springer Verlag ER - TY - CONF T1 - Cooperative Simultaneous Localization and Map Building for Servoing T2 - Proceedings of Multiagent Robotic Systems Trends and Industrial Application - Robocup 2003 Conference Y1 - 2003 A1 - A. Danesi A1 - D. Fontanelli A1 - P. Murrieri A1 - V. G. Scordio A1 - A. Bicchi KW - Embedded Control KW - Robotics JF - Proceedings of Multiagent Robotic Systems Trends and Industrial Application - Robocup 2003 Conference CY - Padova ER -