Optimal human navigation in steep terrain: a Hamilton–Jacobi–Bellman approach

Christian Parkinson, D. J. Arnold, Andrea L. Bertozzi, Yat Tin Chow, Stanley Osher

Abstract

We present a method for determining optimal walking paths in steep terrain using the level set method and an optimal control formulation. By viewing the walking direction as a control variable, we can determine the optimal control by solving a Hamilton-Jacobi-Bellman equation. We then calculate the optimal walking path by solving an ordinary differential equation. We demonstrate the effectiveness of our method by computing optimal paths which travel throughout mountainous regions of Yosemite National Park. We include details regarding the numerical implementation of our model and address a specific application of a law enforcement agency patrolling a nationally protected area.

Introduction

Finding the most efficient path through rugged terrain is a challenge familiar to any hiker. While "common sense" often dictates avoiding steep inclines, formalizing this into a predictive model requires moving beyond simple grid-based algorithms. This research, conducted by a team at UCLA, presents a continuous, physics-based framework for optimal navigation using Hamilton-Jacobi-Bellman (HJB) equations and the Level Set Method.

The Problem with Discrete Pathfinding

Traditional navigation algorithms like Dijkstra’s or A* typically treat the environment as a discrete graph of connected nodes. While highly effective for road networks, these methods struggle with the continuous nature of mountainous terrain. In such environments, the "best" direction can change with every step, and human walking speed is highly sensitive to local slope. Previous models often failed to dynamically account for how a traveler might choose to "zig-zag" or contour around a peak to maintain an optimal speed.

Methodology: Optimal Control and Level Sets

The authors frame navigation as an optimal control problem, where the walking direction is the dynamic control variable.

  1. The Level Set Method: Instead of calculating a single trajectory, the model evolves a "front" outward from the starting point. This front represents the boundary of the area reachable within a specific time interval.
  2. Hamilton-Jacobi-Bellman (HJB) Equation: The HJB equation serves as the core of the model, calculating the optimal walking direction at every point by maximizing a directional Hamiltonian. It determines which direction moves the front forward most efficiently given the local topography.
  3. Velocity Function: The model utilizes a modified Irmischer-Clarke function to map terrain slope to walking speed, accounting for the fact that humans move fastest on slight declines (~2%) and slowest on extreme gradients.
Figure 1: Evolution of a level set front from a starting point 'a' toward a destination 'b' over elevation contours.

Once the expanding front reaches the destination, the specific optimal path is extracted by solving a system of Ordinary Differential Equations (ODEs) backwards from the goal to the start. To handle the "jagged" nature of real-world elevation data, the researchers employ high-order numerical schemes and re-distancing techniques to maintain mathematical stability.

Handling Uncertainty and Strategic Planning

A significant contribution of this work is its application to scenarios involving spatial uncertainty. For instance, if a law enforcement agency knows a crime occurred within a general region but lacks a specific starting point, the model can be inverted. By evolving the level set backwards from a known destination, the system can calculate optimal paths from thousands of potential starting points simultaneously.

Figure 2: Level set front expansion from a region 'A' to address scenarios with spatial uncertainty.

Furthermore, the researchers observed path convergence. Even when starting from 100 different random points, optimal paths often "collapse" onto a few primary corridors. Using k-means clustering, these high-probability routes can be identified, allowing for data-driven resource allocation, such as prioritizing patrols on specific slopes.

Results in Yosemite National Park

The model was tested using high-resolution USGS elevation data for Yosemite National Park, specifically around El Capitan and Half Dome. The simulations successfully generated paths that avoided sheer cliffs, opting for gullies and gentler slopes.

In a strategic test case near El Capitan, the model demonstrated that 76% of optimal paths converged to the eastern slope. This insight provides a quantitative basis for patrolling: a ranger should monitor the eastern slope roughly three times as heavily as the western one to maximize the probability of intercepting a traveler.

Conclusion and Future Directions

While the HJB approach is computationally more intensive than graph-based methods, it offers high accuracy in continuous, rugged environments. Future work may incorporate additional human factors such as caloric expenditure, visibility for tactical movements, or the influence of existing trail networks. Currently, the model provides a robust tool for search-and-rescue operations and strategic land management in nationally protected areas.

Summary updated

Abstract

We present a method for determining optimal walking paths in steep terrain using the level set method and an optimal control formulation. By viewing the walking direction as a control variable, we can determine the optimal control by solving a Hamilton-Jacobi-Bellman equation. We then calculate the optimal walking path by solving an ordinary differential equation. We demonstrate the effectiveness of our method by computing optimal paths which travel throughout mountainous regions of Yosemite National Park. We include details regarding the numerical implementation of our model and address a specific application of a law enforcement agency patrolling a nationally protected area.
BibTeX
@inproceedings{parkinson2018optimal,
  author = {Christian Parkinson and D. J. Arnold and Andrea L. Bertozzi and Yat Tin Chow and Stanley Osher},
  title = {{Optimal human navigation in steep terrain: a Hamilton–Jacobi–Bellman approach}},
  booktitle = {eScholarship},
  year = {2018},
}
Figure