Optimal Human Navigation in Steep Terrain: a Hamilton-Jacobi-Bellman\n Approach

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

TL;DR

This paper introduces a novel method for calculating optimal walking paths in steep, complex terrain by combining the level set method with an optimal control formulation. The approach dynamically accounts for terrain slope and walking direction, enabling more realistic path planning than previous methods, and is demonstrated on real-world elevation data from Yosemite National Park.

What Problem Does This Paper Address?

Navigating steep and varied terrain presents a significant challenge for path planning. Traditional methods often rely on simplified assumptions, like straight-line travel, which are impractical in mountainous regions. While algorithms like Dijkstra's exist for discrete environments, and some continuous methods have been proposed, they often struggle to dynamically account for both the terrain's slope and the optimal direction of travel at each point. This paper tackles the problem of finding truly optimal walking paths in continuous, high-dimensional terrain, where speed is not only dependent on slope but also on the chosen direction of movement, a crucial factor for applications like search and rescue or law enforcement patrols.

Methods

The core of the proposed method lies in a Hamilton-Jacobi-Bellman (HJB) equation formulated within the framework of the level set method. The walking direction is treated as a control variable, and the HJB equation is solved to find the optimal control, which in turn determines the optimal walking velocity.

Here's a breakdown of the key techniques:

  • Level Set Method: This is used to represent and evolve the "front" of reachable points over time. Initially, a small circle around the starting point is considered the zero level set. As this set evolves, it expands to cover all points reachable within a certain time.
  • Optimal Control Formulation: The walking direction ($\theta$) is treated as a control variable. The velocity of travel at any point is a function of the terrain slope and the chosen direction. This leads to a directional Hamiltonian ($H_\theta$).
  • Hamilton-Jacobi-Bellman (HJB) Equation: To find the optimal path, the method maximizes over all possible walking directions ($\theta$) to define an optimal path Hamiltonian ($H$). This Hamiltonian is then used in the HJB equation to model the evolution of the level sets, effectively finding the minimum time to reach any point.
  • Ordinary Differential Equations (ODEs) for Path Reconstruction: Once the optimal travel time is determined by solving the HJB equation, a system of ODEs is used to trace back the optimal path from the destination to the starting point by following the characteristics of the HJB equation.
  • Handling Uncertainty: The method can be adapted to account for uncertainty in the starting point by reversing the problem: evolving level sets outward from the destination until they cover the region of possible starting points. This allows for the computation of multiple optimal paths from a region with a single level set computation.
  • Numerical Implementation: The paper discusses numerical challenges, including discretizing the maximization over directions and using a Godunov Hamiltonian for the HJB equation. They employ second-order accurate schemes for spatial derivatives and time integration, along with techniques like re-distancing and re-initialization to maintain numerical stability and accuracy, especially on challenging terrain. A high-slope penalization is also introduced to prevent paths from traversing impossibly steep areas.

Datasets

  • Synthetic Elevation Data: Used for initial testing and validation of the model's behavior against intuitive expectations.
  • Yosemite National Park Elevation Data: Real-world elevation data, specifically from the vicinity of El Capitan and Half Dome, was used to demonstrate the method's effectiveness on complex, natural terrain. This data was obtained from the USGS National Map Viewer and processed using QGIS and TopoToolbox.

Key Insights and Ideas

  • Dynamic Directional Control is Crucial: The most significant insight is that optimal path planning in steep terrain cannot simply rely on speed-dependent velocity. The direction of travel is a critical control variable that, when optimized, can lead to significantly more efficient and feasible paths, especially around obstacles or steep inclines.
  • HJB as a Unified Framework: The paper elegantly unifies path planning, optimal control, and level set methods under the HJB equation. This provides a powerful mathematical framework for solving complex navigation problems.
  • Reversing the Problem for Uncertainty: The clever inversion of the problem (evolving from destination to start) to handle uncertainty in the starting location is a key algorithmic innovation, significantly improving computational efficiency.
  • Clustering Reveals Patrol Strategies: The observation that multiple optimal paths from a region often converge to a few dominant routes is highly relevant for practical applications like law enforcement. This clustering can inform resource allocation by identifying the most likely escape or patrol routes.
  • Numerical Stability is Key: The paper highlights the practical challenges of implementing such a method, emphasizing the need for robust numerical techniques (re-distancing, re-initialization, high-slope penalization) to handle the complexities of real-world terrain data and avoid numerical artifacts.

Key Results

  • The method successfully computed optimal walking paths that realistically navigate around steep cliffs and mountains in Yosemite National Park, aligning with physical intuition.
  • When accounting for uncertainty in the starting point (e.g., 100 random points on El Capitan or Half Dome), the computed optimal paths naturally clustered into a few dominant routes.
  • For El Capitan, the analysis showed that approximately 76% of optimal paths traveled down the eastern slope, suggesting a law enforcement agency might allocate roughly three times more resources to patrolling the eastern slope compared to the western slope.
  • The numerical implementation demonstrated the effectiveness of techniques like re-distancing and high-slope penalization in producing more accurate and physically plausible paths, especially in challenging scenarios like traversing near steep cliffs.

Limitations and Future Work

  • Computational Cost: While the method is efficient for handling uncertainty by computing multiple paths from a single level set evolution, the initial HJB computation can still be computationally intensive.
  • Discretization of Direction: The maximization over the walking direction is performed discretely, which introduces some approximation error. The paper notes that this error tends to zero as the number of discrete directions increases.
  • Velocity Function Simplification: The paper mentions that the exact form of the velocity function is not critical as long as it behaves reasonably (e.g., maximal velocity near zero slope, low velocity for large slopes). However, the specific choice of function can influence the results.
  • Future Work: The authors suggest that their method could be applied to a wide range of scenarios beyond law enforcement, including search and rescue, robotics, and general navigation. Further exploration of different velocity functions and more complex terrain models could also be valuable.

Summary updated

Abstract

We present a method for determining optimal walking paths in steep terrain\nusing the level set method and an optimal control formulation. By viewing the\nwalking direction as a control variable, we can determine the optimal control\nby solving a Hamilton-Jacobi-Bellman equation. We then calculate the optimal\nwalking path by solving an ordinary differential equation. We demonstrate the\neffectiveness of our method by computing optimal paths which travel throughout\nmountainous regions of Yosemite National Park. We include details regarding the\nnumerical implementation of our model and address a specific application of a\nlaw 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\textbackslash\{\}n Approach}},
  booktitle = {eScholarship},
  year = {2018},
}
Figure