TY - GEN
T1 - Planning optimal paths for multiple robots on graphs
AU - Yu, Jingjin
AU - Lavalle, Steven M.
PY - 2013
Y1 - 2013
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 -