Planning optimal paths for multiple robots on graphs

Jingjin Yu; Steven M. Lavalle

doi:10.1109/ICRA.2013.6631084

Planning optimal paths for multiple robots on graphs

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

In this paper, we study the problem of optimal multi-robot path planning (MPP) on graphs. We propose two multiflow based integer linear programming (ILP) models that compute minimum last arrival time and minimum total distance solutions for our MPP formulation, respectively. The resulting algorithms from these ILP models are complete and guaranteed to yield true optimal solutions. In addition, our flexible framework can easily accommodate other variants of the MPP problem. Focusing on the time optimal algorithm, we evaluate its performance, both as a stand alone algorithm and as a generic heuristic for quickly solving large problem instances. Computational results confirm the effectiveness of our method.

Original language	English (US)
Title of host publication	2013 IEEE International Conference on Robotics and Automation, ICRA 2013
Pages	3612-3617
Number of pages	6
DOIs	https://doi.org/10.1109/ICRA.2013.6631084
State	Published - Nov 14 2013
Event	2013 IEEE International Conference on Robotics and Automation, ICRA 2013 - Karlsruhe, Germany Duration: May 6 2013 → May 10 2013

Publication series

Name	Proceedings - IEEE International Conference on Robotics and Automation
ISSN (Print)	1050-4729

Other

Other	2013 IEEE International Conference on Robotics and Automation, ICRA 2013
Country	Germany
City	Karlsruhe
Period	5/6/13 → 5/10/13

Fingerprint

ASJC Scopus subject areas

Software
Control and Systems Engineering
Artificial Intelligence
Electrical and Electronic Engineering

Cite this

Yu, J., & Lavalle, S. M. (2013). Planning optimal paths for multiple robots on graphs. In 2013 IEEE International Conference on Robotics and Automation, ICRA 2013 (pp. 3612-3617). [6631084] (Proceedings - IEEE International Conference on Robotics and Automation). https://doi.org/10.1109/ICRA.2013.6631084

Yu, J & Lavalle, SM 2013, Planning optimal paths for multiple robots on graphs. in 2013 IEEE International Conference on Robotics and Automation, ICRA 2013., 6631084, Proceedings - IEEE International Conference on Robotics and Automation, pp. 3612-3617, 2013 IEEE International Conference on Robotics and Automation, ICRA 2013, Karlsruhe, Germany, 5/6/13. https://doi.org/10.1109/ICRA.2013.6631084

@inproceedings{710e51f91a1a43cd9d951c1c620580a1,

title = "Planning optimal paths for multiple robots on graphs",

abstract = "In this paper, we study the problem of optimal multi-robot path planning (MPP) on graphs. We propose two multiflow based integer linear programming (ILP) models that compute minimum last arrival time and minimum total distance solutions for our MPP formulation, respectively. The resulting algorithms from these ILP models are complete and guaranteed to yield true optimal solutions. In addition, our flexible framework can easily accommodate other variants of the MPP problem. Focusing on the time optimal algorithm, we evaluate its performance, both as a stand alone algorithm and as a generic heuristic for quickly solving large problem instances. Computational results confirm the effectiveness of our method.",

author = "Jingjin Yu and Lavalle, {Steven M.}",

year = "2013",

month = nov

day = "14",

doi = "10.1109/ICRA.2013.6631084",

language = "English (US)",

isbn = "9781467356411",

series = "Proceedings - IEEE International Conference on Robotics and Automation",

pages = "3612--3617",

booktitle = "2013 IEEE International Conference on Robotics and Automation, ICRA 2013",

note = "2013 IEEE International Conference on Robotics and Automation, ICRA 2013 ; Conference date: 06-05-2013 Through 10-05-2013",

}

TY - GEN

T1 - Planning optimal paths for multiple robots on graphs

AU - Yu, Jingjin

AU - Lavalle, Steven M.

PY - 2013/11/14

Y1 - 2013/11/14

N2 - In this paper, we study the problem of optimal multi-robot path planning (MPP) on graphs. We propose two multiflow based integer linear programming (ILP) models that compute minimum last arrival time and minimum total distance solutions for our MPP formulation, respectively. The resulting algorithms from these ILP models are complete and guaranteed to yield true optimal solutions. In addition, our flexible framework can easily accommodate other variants of the MPP problem. Focusing on the time optimal algorithm, we evaluate its performance, both as a stand alone algorithm and as a generic heuristic for quickly solving large problem instances. Computational results confirm the effectiveness of our method.

AB - In this paper, we study the problem of optimal multi-robot path planning (MPP) on graphs. We propose two multiflow based integer linear programming (ILP) models that compute minimum last arrival time and minimum total distance solutions for our MPP formulation, respectively. The resulting algorithms from these ILP models are complete and guaranteed to yield true optimal solutions. In addition, our flexible framework can easily accommodate other variants of the MPP problem. Focusing on the time optimal algorithm, we evaluate its performance, both as a stand alone algorithm and as a generic heuristic for quickly solving large problem instances. Computational results confirm the effectiveness of our method.

UR - http://www.scopus.com/inward/record.url?scp=84887269402&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84887269402&partnerID=8YFLogxK

U2 - 10.1109/ICRA.2013.6631084

DO - 10.1109/ICRA.2013.6631084

M3 - Conference contribution

AN - SCOPUS:84887269402

SN - 9781467356411

T3 - Proceedings - IEEE International Conference on Robotics and Automation

SP - 3612

EP - 3617

BT - 2013 IEEE International Conference on Robotics and Automation, ICRA 2013

T2 - 2013 IEEE International Conference on Robotics and Automation, ICRA 2013

Y2 - 6 May 2013 through 10 May 2013

ER -

Access to Document

10.1109/ICRA.2013.6631084