TRG-Planner: Traversal Risk Graph-Based Path Planning in Unstructured Environments for Safe and Efficient Navigation

Dongkyu Lee, I Made Aswin Nahrendra, Minho Oh, Byeongho Yu, Hyun Myung

Introduction

Navigating unstructured environments—such as disaster zones, dense forests, or steep mountains—remains a significant challenge for mobile robotics. Legged robots, like quadrupeds, are theoretically well-suited for these terrains, but their success depends heavily on the quality of path planning. Traditional navigation systems often rely on binary traversability maps, which classify a region as either "obstacle" or "free space." While 2.5D elevation maps provide more detail, they typically only evaluate whether a robot can safely stand at a specific point, ignoring the critical factor of how the robot arrives at or moves through that point.

This paper introduces the TRG-planner, a novel path-planning algorithm that utilizes a Traversal Risk Graph (TRG). By accounting for both terrain stability and the directional risk of movement, the TRG-planner enables robots to navigate complex, unstructured environments with high safety and efficiency.

The Challenge of Directional Risk

A primary limitation of existing planners is the neglect of "entry direction." For a legged robot, a 15-degree slope is easily manageable if approached head-on (longitudinally). However, attempting to traverse that same slope sideways (latitudinally) significantly increases the risk of tipping over. Standard global planners often generate paths that are distance-optimal but physically hazardous because they treat traversability as an absolute property of the terrain rather than a relative property of the robot's heading.

Methodology: The Traversal Risk Graph

The TRG-planner addresses these challenges through a multi-layered approach to graph construction and path search.

1. Nodes: Stability and Reachability

Instead of a dense grid, the TRG samples nodes representing areas where the robot can maintain stability. Crucially, the algorithm incorporates reachability analysis, ensuring that nodes are only added if they are physically accessible from the robot's current position.

2. Edges: Modeling Directional Risk

The core innovation of the TRG-planner lies in its edge-weighting strategy. The algorithm approximates the local terrain between two nodes as an ellipse using Principal Component Analysis (PCA). By analyzing the major and minor axes of this ellipse, the planner calculates a "traversal risk penalty." Walking along the steep, latitudinal axis of a slope incurs a significantly higher cost than walking along the longitudinal axis. This encourages the planner to favor paths that align with the terrain's natural gradients.

3. Wavefront Construction

To maintain real-time performance, the TRG-planner employs a wavefront construction method. Rather than sampling the entire environment, the graph expands outward from the robot's current location. This hierarchical approach manages a local graph—updated continuously with real-time sensor data—and a global graph, minimizing unnecessary computation in unreachable areas.

4. Risk-Aware Optimization

The final path is determined using an A* search algorithm with a custom cost function. This function includes a tunable safety factor ($\Gamma$), allowing operators to balance the trade-off between the shortest path and the safest path.

Experimental Evaluation

The authors validated the TRG-planner through extensive simulation and real-world deployment using a Unitree Go1 quadruped robot.

Simulation Results

In a 50m × 50m simulated mountainous environment, the TRG-planner was compared against standard algorithms like A, PRM, and T-Hybrid. The TRG-planner demonstrated remarkable computational efficiency, planning a 30m path in just 3.00 ms, compared to 482.28 ms for T-Hybrid and nearly 3 seconds for standard A*. Furthermore, the TRG-planner achieved the highest success rates in actual travel, proving that its risk-aware paths were more executable than those of its competitors.

Real-World Performance

The system was deployed in several challenging scenarios:

  • Mountainous Terrain: The robot successfully navigated a continuous 245m path across irregular slopes without a single fall.
  • Directional Slope Testing: On custom dirt mounds, the planner correctly identified and avoided dangerous lateral traversals.
  • ICRA 2023 Quadruped Robot Challenge (QRC): The TRG-planner served as the global navigation backbone for the DreamSTEP team. The robot successfully navigated a complex arena featuring ramps, steps, and K-rails, ultimately winning the competition.

Key Insights and Conclusion

The success of the TRG-planner underscores a vital principle in field robotics: traversability is relative. By acknowledging that the safety of a path depends on the robot's approach angle, the TRG-planner bridges the gap between high-level global planning and low-level physical stability.

While the current implementation is optimized for the stability profiles of legged robots, the underlying framework of directional risk and wavefront sampling provides a robust foundation for future work. The authors intend to extend this model to wheeled and tracked platforms, which face their own unique kinematic and stability constraints in unstructured terrain. The TRG-planner represents a significant step forward in making autonomous navigation in the wild both fast and reliable.

Summary updated

BibTeX
@article{lee2025trg,
  author = {Dongkyu Lee and I Made Aswin Nahrendra and Minho Oh and Byeongho Yu and Hyun Myung},
  title = {{TRG-Planner: Traversal Risk Graph-Based Path Planning in Unstructured Environments for Safe and Efficient Navigation}},
  journal = {IEEE Robotics Autom. Lett.},
  year = {2025},
  doi = {10.1109/lra.2024.3524912},
}

Loading related content...

Figure