Fast Path Planning in Uncertain Environments: Theory and Experiments
This dissertation addresses path planning for an autonomous vehicle navigating in a two dimensional environment for which an a priori map is inaccurate and for which the environment is sensed in real-time. For this class of application, planning decisions must be made in real-time. This work is motivated by the need for fast autonomous vehicles that require planning algorithms to operate as quickly as possible. In this dissertation, we first study the case in which there are only static obstacles in the environment. We propose a hybrid receding horizon control path planning algorithm that is based on level-set methods. The hybrid method uses global or local level sets in the formulation of the receding horizon control problem. The decision to select a new level set is made based on certain matching conditions that guarantee the optimality of the path. We rigorously prove sufficient conditions that guarantee that the vehicle will converge to the goal as long as a path to the goal exists. We then extend the proposed receding horizon formulation to the case when the environment possesses moving obstacles. Since all of the results in this dissertation are based on level-set methods, we rigorously investigate how level sets change in response to new information locally sensed by a vehicle. The result is a dynamic fast marching algorithm that usually requires significantly less computation that would otherwise be the case. We demonstrate the proposed dynamic fast marching method in a successful field trial for which an autonomous surface vehicle navigated four kilometers through a riverine environment.
- Doctoral Dissertations