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

Urban Robotics Lab.
School of Electrical Engineering, KAIST

TRG-planner finds a safe and efficient path for ground-based robots in unstructured environments.

Abstract

Unstructured environments such as mountains, caves, construction sites, or disaster areas are challenging for autonomous navigation because of terrain irregularities. In particular, it is crucial to plan a path to avoid risky terrain and reach the goal quickly and safely. In this paper, we propose a method for safe and distance-efficient path planning, leveraging Traversal Risk Graph (TRG), a novel graph representation that takes into account geometric traversability of the terrain. TRG nodes represent stability and reachability of the terrain, while edges represent relative traversal risk-weighted path candidates. Additionally, TRG is constructed in a wavefront propagation manner and managed hierarchically, enabling real-time planning even in large-scale environments. Lastly, we formulate a graph optimization problem on TRG that leads the robot to navigate by prioritizing both safe and short paths. Our approach demonstrated superior safety, distance efficiency, and fast processing time compared to the conventional methods. It was also validated in several real-world experiments using a quadrupedal robot. Notably, TRG-planner contributed as the global path planner of an autonomous navigation framework for the DreamSTEP team, which won the Quadruped Robot Challenge at ICRA 2023.

Real world experiments

Autonomous mapless navigation

Safe-aware global path planning

Simulation experiments

Graph initialization

Graph expansion & update

🎉Highlights🎉

Team DreamSTEP of KAIST won1st place in the ICRA 2023 Autonomous Quadrupedal Robot Challenge! TRG-planner was used as the global path planner for Team DreamSTEP's robot and could navigate a safe path through challenging terrains in the competition!

Related Research of Team DreamSTEP

DreamWaQ: Learning Robust Quadrupedal Locomotion With Implicit Terrain Imagination via Deep Reinforcement Learning
IEEE International Conference on Robotics and Automation (ICRA) 2023

Robust Recovery Motion Control for Quadrupedal Robots via Learned Terrain Imagination
Experiment-oriented Locomotion and Manipulation Research Workshop @ Robotics: Science and Systems (RSS) 2023

BibTeX


      @article{lee2025trg,
        title     = {{TRG-planner: Traversal risk graph-based path planning in unstructured environments for safe and efficient navigation}},
        author    = {Lee, Dongkyu and Nahrendra, I Made Aswin and Oh, Minho and Yu, Byeongho and Myung, Hyun},
        journal   = {IEEE Robotics and Automation Letters},
        volume    = {10},
        number    = {2},
        pages     = {1736--1743},
        year      = {2025},
        publisher = {IEEE}
      }