Structure and intractability of optimal multi-robot path planning on graphs

Jingjin Yu, Steven M Lavalle

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

In this paper, we study the structure and computational complexity of optimal multi-robot path planning problems on graphs. Our results encompass three formulations of the discrete multi-robot path planning problem, including a variant that allows synchronous rotations of robots along fully occupied, disjoint cycles on the graph. Allowing rotation of robots provides a more natural model for multi-robot path planning because robots can communicate. Our optimality objectives are to minimize the total arrival time, the makespan (last arrival time), and the total distance. On the structure side, we show that, in general, these objectives demonstrate a pairwise Pareto optimal structure and cannot be simultaneously optimized. On the computational complexity side, we extend previous work and show that, regardless of the underlying multi-robot path planning problem, these objectives are all intractable to compute. In particular, our NP-hardness proof for the time optimal versions, based on a minimal and direct reduction from the 3-satisfiability problem, shows that these problems remain NP-hard even when there are only two groups of robots (i.e. robots within each group are interchangeable).

Original languageEnglish (US)
Title of host publicationProceedings of the 27th AAAI Conference on Artificial Intelligence, AAAI 2013
Pages1443-1449
Number of pages7
StatePublished - Dec 1 2013
Event27th AAAI Conference on Artificial Intelligence, AAAI 2013 - Bellevue, WA, United States
Duration: Jul 14 2013Jul 18 2013

Publication series

NameProceedings of the 27th AAAI Conference on Artificial Intelligence, AAAI 2013

Other

Other27th AAAI Conference on Artificial Intelligence, AAAI 2013
CountryUnited States
CityBellevue, WA
Period7/14/137/18/13

ASJC Scopus subject areas

  • Artificial Intelligence

Fingerprint Dive into the research topics of 'Structure and intractability of optimal multi-robot path planning on graphs'. Together they form a unique fingerprint.

  • Cite this

    Yu, J., & Lavalle, S. M. (2013). Structure and intractability of optimal multi-robot path planning on graphs. In Proceedings of the 27th AAAI Conference on Artificial Intelligence, AAAI 2013 (pp. 1443-1449). (Proceedings of the 27th AAAI Conference on Artificial Intelligence, AAAI 2013).