Paper Info
Title
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.
Year
DOI
Venue
2017
10.1145/3019612.3019708
SAC
Field
DocType
Citations 
Motion planning,Asynchronous communication,Mathematical optimization,Computer science,Constraint (mathematics),Collision,Robot,Distributed constraint optimization,Scalability,Distributed computing,Computational complexity theory
Conference
2
PageRank 
References 
Authors
0.38
19
3
Name
Order
Citations
PageRank
Alberto Viseras Ruiz120.38
Valentina Karolj220.72
Luis Merino332526.09