On motion planning in changing, partially predictable environments

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.