Robot motion planning: A game-theoretic foundation

Research output: Contribution to journalArticle

Abstract

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)
Volume26
Issue number3-4
DOIs
StatePublished - Jan 1 2000
Externally publishedYes

Keywords

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

ASJC Scopus subject areas

  • Computer Science(all)
  • Computer Science Applications
  • Applied Mathematics

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

  • Cite this