Optimal motion planning for multiple robots having independent goals

Steven M. LaValle, Seth A. Hutchinson

Research output: Contribution to journalConference articlepeer-review


This work makes two contributions to geometric motion planning for multiple robots: i) motion plans can be determined that simultaneously optimize an independent performance criterion for each robot; ii) a general spectrum is defined between decoupled and centralized planning. By considering independent performance criteria, we introduce a form of optimality that is consistent with concepts from multi-objective optimization and game theory research. Previous multiple-robot motion planning approaches that consider optimality combine individual criteria into a single criterion. As a result, these methods can fail to find many potentially useful motion plans. We present implemented, multiple-robot motion planning algorithms that are derived from the principle of optimality, for three problem classes along the spectrum between centralized and decoupled planning: i) coordination along fixed, independent paths; ii) coordination along independent roadmaps; iii) general, unconstrained motion planning. Several computed examples are presented for all three problem classes that illustrate the concepts and algorithms.

Original languageEnglish (US)
Pages (from-to)2847-2852
Number of pages6
JournalProceedings - IEEE International Conference on Robotics and Automation
StatePublished - Jan 1 1996
EventProceedings of the 1996 13th IEEE International Conference on Robotics and Automation. Part 1 (of 4) - Minneapolis, MN, USA
Duration: Apr 22 1996Apr 28 1996

ASJC Scopus subject areas

  • Software
  • Control and Systems Engineering
  • Artificial Intelligence
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'Optimal motion planning for multiple robots having independent goals'. Together they form a unique fingerprint.

Cite this