On motion planning in changing, partially predictable environments

Steven M. LaValle, Rajeev Sharma

Research output: Contribution to journalArticlepeer-review


We present a framework for analyzing and computing motion plans for a robot that operates in an environment that both varies over time and is not completely predictable. We first classify sources of motion-planning uncertainty into four categories, and argue that the problems addressed in this article belong to a fundamental category that has received little attention. We treat the changing environment in a flexible manner by combining traditional configuration-space concepts with a Markov process that models the environment. For this context, we then propose the use of a motion strategy, which provides a motion command for the robot for each contingency that it might confront. We allow the specification of a desired performance criterion, such as time or distance, and determine a motion strategy that is optimal with respect to that criterion. We demonstrate the breadth of our framework by applying it to a variety of motion-planning problems. Examples are computed for problems that involve a changing configuration space, hazardous regions and shelters, and processing of random service requests. To achieve this, we have exploited the powerful principle of optimality, which leads to a dynamic programming-based algorithm for determining optimal strategies. In addition, we present several extensions to the basic framework that incorporate additional concerns, such as sensing issues or changes in the geometry of the robot.

Original languageEnglish (US)
Pages (from-to)775-805
Number of pages31
JournalInternational Journal of Robotics Research
Issue number6
StatePublished - 1997
Externally publishedYes

ASJC Scopus subject areas

  • Software
  • Modeling and Simulation
  • Mechanical Engineering
  • Artificial Intelligence
  • Electrical and Electronic Engineering
  • Applied Mathematics

Fingerprint Dive into the research topics of 'On motion planning in changing, partially predictable environments'. Together they form a unique fingerprint.

Cite this