DocumentCode :
2701212
Title :
Decentralized path planning for multi-agent teams in complex environments using rapidly-exploring random trees
Author :
Desaraju, Vishnu R. ; How, Jonathan P.
Author_Institution :
Dept. of Aeronaut. & Astronaut., MIT, Cambridge, MA, USA
fYear :
2011
fDate :
9-13 May 2011
Firstpage :
4956
Lastpage :
4961
Abstract :
This paper presents a novel approach to address the challenge of planning paths for multi-agent systems operating in complex environments. The algorithm developed, Decentralized Multi-Agent Rapidly-exploring Random Tree (DMA-RRT), is an extension of the Closed-loop RRT (CL-RRT) algorithm to the multi-agent case, retaining its ability to plan quickly even with complex constraints. Moreover, a merit-based token passing coordination strategy is developed to dynamically update the planning order based on a measure of each agent´s incentive to replan, derived from the CL-RRT. Agents with a greater incentive plan sooner, yielding a greater reduction of the global cost and greater improvement in the team´s overall performance. An extended version of the algorithm, Cooperative DMA-RRT, allows agents to modify others´ plans in order to select paths that reduce their combined cost and thus further improve global performance. The paths generated by both algorithms are proven to satisfy inter-agent constraints, such as collision avoidance, and a set of simulation and experimental results verify performance.
Keywords :
collision avoidance; mobile robots; multi-agent systems; multi-robot systems; trees (mathematics); closed-loop RRT algorithm; collision avoidance; complex environments; cooperative DMA-RRT; decentralized multiagent rapidly-exploring random tree; decentralized path planning; interagent constraints; merit-based token passing coordination strategy; planning order update; team overall performance; Collision avoidance; Computational modeling; Delay; Heuristic algorithms; Planning; Trajectory;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Robotics and Automation (ICRA), 2011 IEEE International Conference on
Conference_Location :
Shanghai
ISSN :
1050-4729
Print_ISBN :
978-1-61284-386-5
Type :
conf
DOI :
10.1109/ICRA.2011.5980392
Filename :
5980392
Link To Document :
بازگشت