An Asynchronous Distributed Constraint Optimization Approach to Multi-Robot Path Planning with Complex Constraints

Alberto Viseras-Ruiz, Valentina Karolj, and Luis Merino. An Asynchronous Distributed Constraint Optimization Approach to Multi-Robot Path Planning with Complex Constraints. In Proceedings of the ACM Symposium on Applied Computing (SAC), Track on Intelligent Robotics and Multi-Agent Systems (IRMAS), pp. 268–275, 2017.

Download

[PDF] 

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 multi-robot path planning as a distributed constraint optimization problem. Specifically, in our approach the asynchronous distributed constraint optimization algorithm (Adopt) 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.

BibTeX Entry

@INPROCEEDINGS{sac17irmas,
  author = {Alberto Viseras-Ruiz and Valentina Karolj and Luis Merino},
  title = {An Asynchronous Distributed Constraint Optimization Approach to Multi-Robot Path Planning with Complex Constraints},
  booktitle = {Proceedings of the ACM Symposium on Applied Computing (SAC), Track on Intelligent Robotics and Multi-Agent Systems (IRMAS)},
  year = {2017},
  pages = {268-275},
  doi = {10.1145/3019612.3019708},
  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 multi-robot path planning as a distributed constraint optimization problem. Specifically, in our approach the asynchronous distributed constraint optimization algorithm (Adopt) 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. },
  }

Generated by bib2html.pl (written by Patrick Riley ) on Mon Jan 09, 2023 18:40:36