Intractability of optimal multirobot path planning on planar graphs

Research output: Contribution to journalArticlepeer-review

41 Scopus citations

Abstract

We study the computational complexity of optimally solving multirobot path planning problems on planar graphs. For four common time- and distance-based objectives, we show that the associated path optimization problems for multiple robots are all NP-complete, even when the underlying graph is planar. Establishing the computational intractability of optimal multirobot path planning problems on planar graphs has important practical implications. In particular, our result suggests the preferred approach toward solving such problems, when the number of robots is large, is to augment the planar environment to reduce the sharing of paths among robots traveling in opposite directions on those paths. Indeed, such efficiency boosting structures, such as highways and elevated intersections, are ubiquitous in robotics and transportation applications.

Original languageEnglish (US)
Article number7342901
Pages (from-to)33-40
Number of pages8
JournalIEEE Robotics and Automation Letters
Volume1
Issue number1
DOIs
StatePublished - Jan 2016

All Science Journal Classification (ASJC) codes

  • Control and Systems Engineering
  • Biomedical Engineering
  • Human-Computer Interaction
  • Mechanical Engineering
  • Computer Vision and Pattern Recognition
  • Computer Science Applications
  • Control and Optimization
  • Artificial Intelligence

Keywords

  • Boolean satisfiability problems
  • Multi-robot path planning
  • NP-hardness
  • Planar graphs
  • Transportation networks

Fingerprint

Dive into the research topics of 'Intractability of optimal multirobot path planning on planar graphs'. Together they form a unique fingerprint.

Cite this