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.

%B IEEE Trans. on Robotics %V 23 %P 1170-1183 %G eng %0 Conference Paper %B American Control Conference (ACC) %D 2007 %T Probabilistic verification of decentralized multi-agent control strategies: a case study in conflict avoidance %A L. Pallottino %A A. Bicchi %A E. Frazzoli %K Embedded Control %K Robotics %XMany challenging verification problems arise from complex hybrid automata that model decentralized control systems. As an example, we will consider decentralized policies that steer multiple vehicles in a shared environment: properties of safety and liveness, such as collision avoidance and ultimate convergence of all vehicles to their goals, must be verified. To formally verify the behavior of proposed policies, it is desired to identify the broadest class of start and goal configurations, such that safety and liveness would be guaranteed. Simple conditions are proposed to identify such a class: ideally, a formal proof that such conditions are necessary and sufficient for safety and liveness is requested. Unfortunately, in decentralized control frameworks classical approaches are difficult to apply. Hence, probabilistic verification method can be applied to quantify the accuracy and the confidence of the veridicity of the desired predicate. The probabilistic verification method is applied to a recently proposed cooperative and completely decentralized collision avoidance policy for non-holonomic vehicles.

%B American Control Conference (ACC) %P 170-175 %G eng %0 Journal Article %J Robotics and Automation Magazine %D 2007 %T Symbolic Planning and Control of Robot Motion: Finding the Missing Pieces of Current Methods and Ideas %A C. Belta %A A. Bicchi %A M. Egerstedt %A E. Frazzoli %A E. Klavins %A G. J. Pappas %K Embedded Control %K Robotics %XApproaches to robot motion planning and control that involve tools such as automata, languages, temporal logics, and grammars, have been recently termed "symbolic." In this article, we review some existing results, discuss their relevance and applicability, and outline some of the main open questions and challenges in the area.

%B Robotics and Automation Magazine %V 14 %P 61-70 %G eng %0 Conference Paper %B Int. Symp. on Mathematical Theory of Networks and Systems %D 2006 %T Decentralized and scalable conflict resolution strategy for multi-agents systems %A L. Pallottino %A V. G. Scordio %A E. Frazzoli %A A. Bicchi %K Embedded Control %K Robotics %XA 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.

%B Int. Symp. on Mathematical Theory of Networks and Systems %G eng %0 Conference Paper %B Proc. IEEE Int. Conf. on Robotics and Automation %D 2006 %T Probabilistic verification of a decentralized policy for conflict resolution in multi-agent systems %A L. Pallottino %A V. G. Scordio %A E. Frazzoli %A A. Bicchi %K Embedded Control %K Robotics %XIn 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.

%B Proc. IEEE Int. Conf. on Robotics and Automation %P 2448-2453 %G eng %0 Conference Paper %B Proc. AIAA COnf. on Guidance, Navigation and Control %D 2005 %T Decentralized Cooperative Conflict Resolution for Multiple Nonholonomic Vehicles %A L. Pallottino %A V. G. Scordio %A E. Frazzoli %A A. Bicchi %K Embedded Control %K Robotics %XIn 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.

%B Proc. AIAA COnf. on Guidance, Navigation and Control %G eng