Decentralized path planning for multi-agent teams in complex environments using rapidly-exploring random trees

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.