Search

We address the problem of optimal path planning for a simple nonholonomicvehicle in the presence of obstacles. Most current approaches are either splithierarchically into global path planning and local collision avoidance, orneglect some of the ambient geometry by assuming the car is a point mass. Wepresent a Hamilton-Jacobi formulation of the problem that resolves time-optimalpaths and considers the geometry of the vehicle.

We present a method for optimal path planning of human walking paths inmountainous terrain, using a control theoretic formulation and aHamilton-Jacobi-Bellman equation. Previous models for human navigation wereentirely deterministic, assuming perfect knowledge of the ambient elevationdata and human walking velocity as a function of local slope of the terrain.Our model includes a stochastic component which can account for uncertainty inthe problem, and thus includes a Hamilton-Jacobi-Bellman equation withviscosity. We discuss the model in the presence and absence of stochasticeffects, and suggest numerical methods for simulating the model. We discuss twodifferent notions of an optimal path when there is uncertainty in the problem.Finally, we compare the optimal paths suggested by the model at differentlevels of uncertainty, and observe that as the size of the uncertainty tends tozero (and thus the viscosity in the equation tends to zero), the optimal pathtends toward the deterministic optimal path.