02132nas a2200181 4500008004100000245008600041210006900127300001400196490000700210520150000217653002101717653001301738100001901751700001701770700001601787700001501803856013201818 2007 eng d00aDecentralized cooperative policy for conflict resolution in multi-vehicle systems0 aDecentralized cooperative policy for conflict resolution in mult a1170-11830 v233 a
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.
10aEmbedded Control10aRobotics1 aPallottino, L.1 aScordio, V G1 aFrazzoli, E1 aBicchi, A. uhttps://www.centropiaggio.unipi.it/publications/decentralized-cooperative-policy-conflict-resolution-multi-vehicle-systems.html01751nas a2200157 4500008004100000245011500041210006900156300001200225520113700237653002101374653001301395100001901408700001501427700001601442856013501458 2007 eng d00aProbabilistic verification of decentralized multi-agent control strategies: a case study in conflict avoidance0 aProbabilistic verification of decentralized multiagent control s a170-1753 aMany 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.
10aEmbedded Control10aRobotics1 aPallottino, L.1 aBicchi, A.1 aFrazzoli, E uhttps://www.centropiaggio.unipi.it/publications/probabilistic-verification-decentralized-multi-agent-control-strategies-case-study01047nas a2200205 4500008004100000245010700041210006900148300001000217490000700227520034300234653002100577653001300598100001300611700001500624700001700639700001600656700001500672700001600687856013800703 2007 eng d00aSymbolic Planning and Control of Robot Motion: Finding the Missing Pieces of Current Methods and Ideas0 aSymbolic Planning and Control of Robot Motion Finding the Missin a61-700 v143 aApproaches 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.
10aEmbedded Control10aRobotics1 aBelta, C1 aBicchi, A.1 aEgerstedt, M1 aFrazzoli, E1 aKlavins, E1 aPappas, G J uhttps://www.centropiaggio.unipi.it/publications/symbolic-planning-and-control-robot-motion-finding-missing-pieces-current-methods-and01456nas a2200157 4500008004100000245008500041210006900126520086800195653002101063653001301084100001901097700001701116700001601133700001501149856013401164 2006 eng d00aDecentralized and scalable conflict resolution strategy for multi-agents systems0 aDecentralized and scalable conflict resolution strategy for mult3 aA 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.
10aEmbedded Control10aRobotics1 aPallottino, L.1 aScordio, V G1 aFrazzoli, E1 aBicchi, A. uhttps://www.centropiaggio.unipi.it/publications/decentralized-and-scalable-conflict-resolution-strategy-multi-agents-systems.html01651nas a2200169 4500008004100000245010400041210006900145300001400214520101200228653002101240653001301261100001901274700001701293700001601310700001501326856014001341 2006 eng d00aProbabilistic verification of a decentralized policy for conflict resolution in multi-agent systems0 aProbabilistic verification of a decentralized policy for conflic a2448-24533 aIn 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.
10aEmbedded Control10aRobotics1 aPallottino, L.1 aScordio, V G1 aFrazzoli, E1 aBicchi, A. uhttps://www.centropiaggio.unipi.it/publications/probabilistic-verification-decentralized-policy-conflict-resolution-multi-agent-systems01298nas a2200157 4500008004100000245008500041210006900126520071000195653002100905653001300926100001900939700001700958700001600975700001500991856013401006 2005 eng d00aDecentralized Cooperative Conflict Resolution for Multiple Nonholonomic Vehicles0 aDecentralized Cooperative Conflict Resolution for Multiple Nonho3 aIn 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.
10aEmbedded Control10aRobotics1 aPallottino, L.1 aScordio, V G1 aFrazzoli, E1 aBicchi, A. uhttps://www.centropiaggio.unipi.it/publications/decentralized-cooperative-conflict-resolution-multiple-nonholonomic-vehicles.html