Path planning for road vehicles by dynamic programming

Abstract

This thesis presents a deterministic approach for path planning of road vehicles, operating in a known environment in the presence of static obstacles. The path planning problem is addressed using two different methods: Dynamic Programming and Search-based Planning. The first method, based on the numerical solution of the Hamilton-Jacobi-Bellman equation, allows finding an optimal solution at the expense of a high computational cost. Search-based Planning converts the path planning problem into a minimum path problem on a graph, and allows finding a solution to a planning task rather quickly, even for large and high-dimensional operating spaces. In this thesis, Dynamic Programming is first used to find an optimal solution for a small operating space. In particular, this approach is employed to perform a parking maneuver for a car-like vehicle. Then, Dynamic Programming and Search-based Planning are combined together in the algorithm FOCS (Fusion of Optimal Control and Search). This algorithm allows finding a path exploiting the advantages of both approaches while providing a bound on the sub-optimality of its solution. The thesis analyzes the algorithm FOCS and illustrates its effectiveness in finding a minimum-time path for a car-like vehicle in different environments.