Decoupled Multi-agent Path Planning in Non-convex Domains

Project Description  (top)

Decoupled Multi-agent Path Planning by Steven Chen, Mark Cutler, and Jack Quindlen

This project aims to develop a multi-agent path planning algorithm that finds collision-free trajectories for a team of mobile robots. Further, we aim to reduce computational complexity by decoupling the multi-agent planning problem into a sequence of simpler single-agent planning problems.

Many applications of multi-agent systems require coordination of mobile agents that are navigating in complex environments. For instance, researchers have investigated using fleets of unmanned aerial and ground vehicles for forest fire monitoring, persistent surveillance, and warehouse inventory management. These scenarios require computing collision free trajectories connecting initial and final positions for every agent in the fleet.

We formulate the multi-agent path planning problem as an optimization problem, and develop an algorithm for solving this optimization problem based on sequential convex programming (SCP). Previous SCP-based methods [Augugliaro '12, Morgan '14] efficiently compute motion plans in convex spaces with no static obstacles. In many scenarios where the spaces are non-convex, previous SCP-based algorithms failed to find feasible solutions because the convex approximation of collision constraints leads to forming a sequence of infeasible optimization problems. We propose a method that addresses this problem by tightening collision constraints incrementally, thus forming a sequence of more relaxed, feasible intermediate optimization problems.

Further, we show that decoupling the multi-agent optimization problem to a number of single-agent optimization problems leads to significant improvement in computational tractability. We develop a decoupled implementation of the proposed algorithm and show that it runs faster and finds feasible solution more reliably than previous SCP-based algorithms. The proposed algorithm is real-time implementable and is validated through hardware experiment on a team of quadrotors.

Videos  (top)