Motion Planning for Continuous Time Stochastic Processes: A Dynamic Programming Approach
Provides a theoretical framework for motion planning under uncertainty, relevant to control theory and robotics, but the results are theoretical and incremental.
The paper develops a dynamic programming principle for stochastic motion planning problems with controlled processes having possibly discontinuous sample paths, enabling characterization of initial states that achieve desired maneuvers with a given probability. The approach is demonstrated on biological switches.
We study stochastic motion planning problems which involve a controlled process, with possibly discontinuous sample paths, visiting certain subsets of the state-space while avoiding others in a sequential fashion. For this purpose, we first introduce two basic notions of motion planning, and then establish a connection to a class of stochastic optimal control problems concerned with sequential stopping times. A weak dynamic programming principle (DPP) is then proposed, which characterizes the set of initial states that admit a control enabling the process to execute the desired maneuver with probability no less than some pre-specified value. The proposed DPP comprises auxiliary value functions defined in terms of discontinuous payoff functions. A concrete instance of the use of this novel DPP in the case of diffusion processes is also presented. In this case, we establish that the aforementioned set of initial states can be characterized as the level set of a discontinuous viscosity solution to a sequence of partial differential equations, for which the first one has a known boundary condition, while the boundary conditions of the subsequent ones are determined by the solutions to the preceding steps. Finally, the generality and flexibility of the theoretical results are illustrated on an example involving biological switches.