Optimal motion planning for multiple robots having independent goals

Steven M. LaValle, Seth A. Hutchinson

Research output: Contribution to journalArticle

Abstract

This work makes two contributions to geometric motion planning for multiple robots: 1) motion plans are computed that simultaneously optimize an independent performance measure for each robot; 2) a general spectrum is defined between decoupled and centralized planning, in which we introduce coordination along independent roadmaps. By considering independent performance measures, we introduce a form of optimality that is consistent with concepts from multiobjective optimization and game theory literature. Previous multiple-robot motion planning approaches that consider optimality combine individual performance measures into a scalar 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: 1) coordination along fixed, independent paths; 2) coordination along independent roadmaps; 3) general, unconstrained motion planning. Computed examples are presented for all three problem classes that illustrate the concepts and algorithms.

Original languageEnglish (US)
Pages (from-to)912-925
Number of pages14
JournalIEEE Transactions on Robotics and Automation
Volume14
Issue number6
DOIs
StatePublished - Dec 1 1998

Keywords

  • Game-theory
  • Mobile robots
  • Motion planning
  • Multiobjective optimization
  • Multiple robots
  • Obstacle avoidance
  • Path planning
  • Scheduling

ASJC Scopus subject areas

  • Control and Systems Engineering
  • 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