elib
DLR-Header
DLR-Logo -> http://www.dlr.de
DLR Portal Home | Imprint | Privacy Policy | Contact | Deutsch
Fontsize: [-] Text [+]

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

Viseras, Alberto and Karolj, Valentina and Merino, Luis (2017) An Asynchronous Distributed Constraint Optimization Approach to Multi-Robot Path Planning with Complex Constraints. In: IRMAS. The 32nd ACM Symposium on Applied Computing, Track on Intelligent Robotics and Multi-Agent Systems (IRMAS), 3-7 April 2017, Marrakesh, Morocco. DOI: 10.1145/3019612.3019708 ISBN 978-1-4503-4486-9/17/04

[img] PDF
2MB

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.

Item URL in elib:https://elib.dlr.de/112458/
Document Type:Conference or Workshop Item (Speech)
Title:An Asynchronous Distributed Constraint Optimization Approach to Multi-Robot Path Planning with Complex Constraints
Authors:
AuthorsInstitution or Email of AuthorsAuthors ORCID iD
Viseras, Albertoalberto.viserasruiz (at) dlr.deUNSPECIFIED
Karolj, Valentinavalentina.karolj (at) dlr.deUNSPECIFIED
Merino, Luislmercab (at) upo.esUNSPECIFIED
Date:2017
Journal or Publication Title:IRMAS
Refereed publication:Yes
Open Access:Yes
Gold Open Access:No
In SCOPUS:No
In ISI Web of Science:No
DOI :10.1145/3019612.3019708
ISBN:978-1-4503-4486-9/17/04
Status:Published
Keywords:multi-robot path planning, distributed constraint optimization, sampling-based planner
Event Title:The 32nd ACM Symposium on Applied Computing, Track on Intelligent Robotics and Multi-Agent Systems (IRMAS)
Event Location:Marrakesh, Morocco
Event Type:international Conference
Event Dates:3-7 April 2017
HGF - Research field:Aeronautics, Space and Transport
HGF - Program:Transport
HGF - Program Themes:Traffic Management (old)
DLR - Research area:Transport
DLR - Program:V VM - Verkehrsmanagement
DLR - Research theme (Project):V - Vabene++ (old)
Location: Oberpfaffenhofen
Institutes and Institutions:Institute of Communication and Navigation > Communications Systems
Deposited By: Viseras Ruiz, Alberto
Deposited On:02 Jun 2017 16:20
Last Modified:31 Jul 2019 20:09

Repository Staff Only: item control page

Browse
Search
Help & Contact
Information
electronic library is running on EPrints 3.3.12
Copyright © 2008-2017 German Aerospace Center (DLR). All rights reserved.