Optimal obstacle avoidance based on the Hamilton-Jacobi-Bellman equation

This paper solves the on-line obstacle avoidance problem using the Hamilton-Jacobi-Bellman (HJB) theory. Formulating the shortest path problem as a time optimal control problem, the shortest paths are generated by following the negative gradient of the return function, which is the solution of the HJB equation. To account for multiple obstacles, we avoid obstacles optimally one at a time. This is equivalent to following the pseudoreturn function, which is an approximation of the true return function for the multi-obstacle problem. Paths generated by this method are near-optimal and guaranteed to reach the goal, at which the pseudoreturn function is shown to have a unique minimum. The proposed method is computationally very efficient, and applicable for on-line applications. Examples for circular obstacles demonstrate the advantages of the proposed approach over traditional path planning methods.