A Methodology for Intelligent Path Planning

In this work we present a methodology for intelligent path planning in an uncertain environment. Examples would include a mobile robot exploring an unknown terrain or a UAV navigating enemy territory while avoiding radar detection. We show that the problem of path planning in an uncertain environment, under certain assumptions, can be posed as the adaptive optimal control of an uncertain Markov decision process. The strategy for path planning then reduces to computing the control policy based on the current estimate of the environment, also known as the "certainty equivalence" principle in the adaptive control literature. Further we show that the path planning problem, as formulated in this paper, possesses special structure which can be used to significantly reduce the dimensionality of the problem. Finally we apply this methodology to the problem of path planning of a mobile rover in an unknown, unstructured terrain