Robot motion planning: A game-theoretic foundation

Research output: Contribution to journalArticlepeer-review


Analysis techniques and algorithms for basic path planning have become quite valuable in a variety of applications such as robotics, virtual prototyping, computer graphics, and computational biology. Yet, basic path planning represents a very restricted version of general motion planning problems often encountered in robotics. Many problems can involve complications such as sensing and model uncertainties, nonholonomy, dynamics, multiple robots and goals, optimality criteria, unpredictability, and nonstationarity, in addition to standard geometric workspace constraints. This paper proposes a unified, game-theoretic mathematical foundation upon which analysis and algorithms can be developed for this broader class of problems, and is inspired by the similar benefits that were obtained by using unified configuration-space concepts for basic path planning. By taking this approach, a general algorithm has been obtained for computing approximate optimal solutions to a broad class of motion planning problems, including those involving uncertainty in sensing and control, environment uncertainties, and the coordination of multiple robots.

Original languageEnglish (US)
Pages (from-to)430-465
Number of pages36
JournalAlgorithmica (New York)
Issue number3-4
StatePublished - 2000
Externally publishedYes


  • Dynamic programming
  • Game theory
  • Geometric reasoning
  • Motion planning
  • Path planning
  • Robotics

ASJC Scopus subject areas

  • General Computer Science
  • Computer Science Applications
  • Applied Mathematics


Dive into the research topics of 'Robot motion planning: A game-theoretic foundation'. Together they form a unique fingerprint.

Cite this