OPTIMAL OBSTACLE AVOIDANCE BASED ON THE HAMILTON-JACOBI-BELLMAN EQUATION

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