Robot motion planning in a changing, partially predictable environment

In this paper we present a framework for analyzing and determining robot motion plans for situations in which the robot is affected by an environment that probabilistically changes over time. In general, motion planning under uncertainty has recently received substantial interest, and in particular a changing-environment has been recognized as an important aspect of motion planing under uncertainty. We model the environment as a finite-state Markov process, and the robot executes a motion strategy that is conditioned on its current position and the state of the environment. Optimality of a robot strategy is evaluated in terms of a performance functional that depends on the environment, robot actions, and a precise encoding of relevant preferences. By using a simple, yet powerful computation technique that is based on dynamic programming, we can numerically compute optimal robot strategies for a wide class of problems, surpassing previous results in this context that were obtained analytically. Several computed motion planning examples are presented.