Alexander Shum, Applied Math, University of Waterloo
In this work, the path planning problem is solved as an optimal control problem. The corresponding static Hamilton-Jacobi-Bellman (HJB) equation is used to determine the optimal path. The Ordered Upwind Method (OUM) has been previously used to numerically approximate the viscosity solution of the static HJB equation for direction-dependent weights.
The contributions of this work include an analytical bound on the convergence rate of the OUM for the boundary value problem to the viscosity solution of the HJB equation. The convergence result provided is to our knowledge the tightest existing bound on the convergence order of OUM solutions to the viscosity solution of the static HJB equation. Only convergence without any guarantee of rate has been previously shown.
Though finding the shortest path is often considered in optimal path planning, safe and energy-efficient paths are required for rover path planning. Reducing instability risk based on tip-over axes and maximizing solar exposure are important to achieve these goals. In particular, tip-over instability risk is a direction-dependent criteria, for which accurate approximate solutions to the static HJB equation cannot in general be found using the simpler Fast Marching Method. In addition to obstacle avoidance, soil risk and path length on terrain are also considered.
An extension of the OUM to include a bi-directional search (OUM-BD) for the source-point path planning problem is also presented. The solution of the static HJB is found on a smaller region of the environment, containing the optimal path.
A comparison is made in the path planning problem in both timing and performance between a genetic algorithm rover path planner, OUM and OUM-BD. The OUM boundary value problem is shown to converge numerically with at least the rate of the proven theoretical bound.