Safe and Efficient Navigation in Extreme Environments using Semantic Belief Graphs

Muhammad Fadhil Ginting, Sung-Kyun Kim, Oriana Peltzer, Joshua Ott, Sunggoo Jung, Mykel J. Kochenderfer, Ali-akbar Agha-mohammadi

Introduction

In extreme environments such as disaster zones, caves, or urban ruins, robots face significant challenges beyond simple obstacle avoidance. Navigating these terrains requires specialized locomotion controllers—for example, climbing stairs requires a different gait than walking on flat ground. The primary hurdle is perceptual uncertainty: semantic terrain recognition is often noisy or incorrect when viewed from a distance. Misidentifying a flight of stairs as flat ground can lead to catastrophic failure, while being overly cautious leads to inefficient, circuitous routes. This paper introduces the Semantic Belief Graph (SBG), a framework that bridges high-level semantic recognition and low-level geometric planning to enable safe and efficient autonomous navigation.

Methods: The Semantic Belief Graph

The authors extend the classic Probabilistic Roadmap (PRM) into the "belief space" to create the SBG.

The Semantic Belief Graph (SBG) structure, where nodes represent geo-semantic beliefs and edges represent locomotion controllers.

Key components of the SBG include:

  • SBG Nodes: Each node represents a "geo-semantic belief," combining a Gaussian distribution for physical position with a categorical distribution (represented as probability "pie charts") for terrain types like stairs, rubble, or flat ground.
  • SBG Edges: Edges are associated with specific locomotion policies (e.g., stairs, flat ground, rubble).
  • Information Gathering: A novel feature of the SBG is the inclusion of "self-loop" edges. These represent planned actions, such as tilting a camera or moving closer to a target, specifically designed to reduce semantic uncertainty.
  • Dynamic Programming for Planning: Optimal policies are solved via Value Iteration. The cost function is defined as expected traversal time, where using an incorrect controller for a given terrain type incurs a significant time penalty. This mathematical formulation naturally incentivizes the robot to balance speed, risk, and the need for more information.

Evaluation and Results

The framework was evaluated across three settings: a small-scale simulation, a large-scale urban simulation based on the DARPA SubT Challenge, and real-world field tests using a Boston Dynamics Spot quadruped.

Performance comparison of the SBG approach against conservative and optimistic policies in terms of traversal time and controller selection accuracy.

The results demonstrate that the SBG approach significantly outperforms standard heuristics:

  • Efficiency: In the SubT simulation, the SBG approach achieved a traversal time of 18 time steps, compared to 22 for a "Conservative" policy (which requires 95% confidence) and 23 for an "Optimistic" policy (which frequently used incorrect controllers).
  • Accuracy: The system selected the correct terrain-specific controller 93.9% of the time.
  • Real-world Validation: Field tests confirmed the system's ability to perform active perception. When faced with a potential shortcut via stairs, the Spot robot planned an information-gathering action—pitching its body to scan the terrain—before successfully climbing, rather than defaulting to a much longer ramp route.

Key Insights

  • Active Perception: SBG-equipped robots do not just react to sensors; they plan to see. By treating information gathering as a first-class action, the robot can strategically resolve ambiguity.
  • Tractability: While solving full Partially Observable Markov Decision Processes (POMDPs) is often computationally prohibitive, grounding the belief state in a sparse graph makes the problem tractable for real-time autonomous systems.

Limitations and Future Work

Current limitations include a reliance on prior maps for initial roadmap sampling and a deterministic model for geometric transitions (ignoring risks like slipping). Future research aims to incorporate geometric failure probabilities and improve the scalability of belief sampling for environments with numerous semantic classes.

Summary updated

BibTeX
@inproceedings{ginting2023safe,
  author = {Muhammad Fadhil Ginting and Sung-Kyun Kim and Oriana Peltzer and Joshua Ott and Sunggoo Jung and Mykel J. Kochenderfer and Ali-akbar Agha-mohammadi},
  title = {{Safe and Efficient Navigation in Extreme Environments using Semantic Belief Graphs}},
  booktitle = {IEEE International Conference on Robotics and Automation},
  year = {2023},
  doi = {10.1109/icra48891.2023.10161056},
}

Loading related content...

Figure