A key issue in handling uncertainty is how to model it so that it can
be effectively accounted for at the motion planning stage. We propose
a stochastic representation which allows one to analyze the expected
behavior and determine motion planning strategies with provable
performance. We define a framework for representing uncertainty in a
time-varying, partially predictable environment. This includes
important classes of problems such as motion planning for an assembly
robot in a manufacturing plant where the flow of parts/subassemblies
can be modeled stochastically. For simple cases, we derive analytical
solutions to the underlying optimization problems. For the more
general cases, we define a computational scheme based on dynamic
programming for determining the optimal strategies on a discretized
state space of the robot using different criteria. The result is a
stochastic state-feedback controller for operating in a dynamic,
uncertain environment. We are currently investigating how this
framework can be expanded to include other fundamental sources of
uncertainty, and how the computation can be made more efficient, for
example, by parallelization.