FAST NUMERICAL ALGORITHMS FOR OPTIMAL ROBOT MOTION PLANNING

Optimization of high-level autonomous tasks requires solving the optimal motion planning problem for a mobile robot. For example, to reach the de-sired destination on time, a self-driving car must quickly navigate streets and avoid hazardous obstacles such as buildings or other cars, as well as provide safety for pedestrians. Our approach to solve the optimal planning problem is to use the optimal control formalism borrowed from the control theory. In this setting, safety constraints for either a robot or its surroundings are defined as obstacles, which are penalized using infinite cost to guarantee that tasks are performed safely. Unlike in control theory, the complexity of real-world tasks in addition with safety constraints prohibit finding an analytic solution to the optimal motion planning problem. Hence, the application of numerical algorithms is necessary. In this thesis, we demonstrate that solu-tions to a general motion planning problem are computable, which permits the use of numerical algorithms to solve this problem. Moreover, we propos