Decentralized path planning for multi-agent teams with complex constraints
This paper presents a novel approach to address the challenge of planning paths for multi-agent systems subject to complex constraints. The technique, called the Decentralized Multi-Agent Rapidly-exploring Random Tree (DMA-RRT) algorithm, extends the Closed-loop RRT (CL-RRT) algorithm to handle multiple agents while retaining its ability to plan quickly. Acore component of the DMA-RRT algorithm is a merit-based token passing coordination strategy that makes use of the tree of feasible trajectories grown in the CL-RRT algorithm to dynamically update the order in which agents replan. The reordering is based on a measure of each agents incentive to change the plan and allows agents with a greater potential improvement to replan sooner, which is demonstrated to improve the teams overall performance compared to a traditional, scripted replan order. The main contribution of the work is a version of the algorithm, called Cooperative DMA-RRT, which introduces a cooperation strategy that allows an agent to modify its teammates plans in order to select paths that reduce their combined cost. This modification further improves team performance and avoids certain common deadlock scenarios. The paths generated by both algorithms are proven to satisfy inter-agent constraints, such as collision avoidance, and numerous simulation and experimental results are presented to demonstrate their performance.
rrt collision avoidance cooperative planning