An asynchronous distributed constraint optimization approach to multi-robot path planning with complex constraints

Abstract

Multi-robot teams can play a crucial role in many applications such as exploration, or search and rescue operations. One of the most important problems within the multi-robot context is path planning. This has been shown to be particularly challenging, as the team of robots must deal with additional constraints, e.g. inter-robot collision avoidance, while searching in a much larger action space. Previous works have proposed solutions to this problem, but they present two major drawbacks: (i) algorithms suffer from a high computational complexity, or (ii) algorithms require a communication link between any two robots within the system. This paper presents a method to solve this problem, which is both computationally efficient and only requires local communication between neighboring agents. We formulate the multirobot path planning as a distributed constraint optimization problem. Specifically, in our approach the asynchronous distributed constraint optimization algorithm (Adopt) [15] is combined with sampling-based planners to obtain collision free paths, which allows us to take into account both kinematic and kinodynamic constraints of the individual robots. The paper analyzes the performance and scalability of the approach using simulations, and presents real experiments employing a team of several robots.