Belief Roadmaps with Uncertain Landmark Evanescence

Erick Fuentes, Jared Strader, Ethan Fahnestock, Nicholas Roy

Introduction

Autonomous navigation typically relies on pre-existing maps to localize. However, real-world environments are dynamic; landmarks such as parked cars or temporary structures may disappear, a phenomenon termed landmark evanescence. Standard planning algorithms often assume a static world, leading to navigation failures when expected landmarks are missing and robot uncertainty grows unchecked. This paper presents BRULE (Belief Roadmap with Uncertain Landmark Evanescence), a framework designed to plan reliable paths in environments with transient landmarks.

Problem Formulation

The core challenge lies in the exponential growth of possible world configurations as the number of landmarks increases. Reasoning over every combination of present and absent landmarks—a hybrid discrete-continuous belief space—is computationally prohibitive for real-time applications. If a robot commits to a path dependent on a landmark that has since vanished, its positional uncertainty can exceed safe thresholds.

Comparison of state space navigation and the corresponding belief space evolution under landmark uncertainty.

The BRULE Framework

The authors extend the standard Belief Roadmap (BRM) by representing the robot's positional belief as a Gaussian Mixture Model (GMM). Each component in the mixture corresponds to the robot's belief under a specific hypothesis of landmark existence.

Efficient Belief Updates

BRULE utilizes a closed-form belief update mechanism, allowing it to predict uncertainty evolution along a path without exhaustive simulation. To maintain tractability, the algorithm bounds the number of mixture components using weighted sampling without replacement. This ensures that the most probable world states are tracked while keeping the computational load manageable.

To navigate the roadmap efficiently, BRULE employs a "probability mass" heuristic. This metric allows the planner to prune suboptimal paths that are unlikely to lead to successful localization at the goal, significantly speeding up the search process compared to naive sampling methods.

Experimental Evaluation

The framework was rigorously tested in both simulation and real-world settings:

  • Simulations: 66 environments with varying landmark distributions (diffuse vs. clustered) and correlation structures, including "mutex" (mutually exclusive) landmarks.
  • Real-World Deployment: A Boston Dynamics Spot robot was tasked with navigating MIT’s Killian Court. AprilTags served as landmarks with assigned "evanescence" probabilities to simulate a stale map.

Key Results

BRULE demonstrated significant improvements over "Optimistic BRM" (which assumes all landmarks exist) and a sampling-based baseline, BRULE-Expected (BRULE-E).

Quantitative performance comparison showing BRULE's advantage in regret reduction and planning efficiency.

Performance and Efficiency

In simulations, BRULE consistently achieved lower regret than optimistic planners. Notably, BRULE scaled far more effectively than BRULE-E; at 1,000 particles, BRULE was nearly ten times faster while maintaining comparable or superior performance.

Real-World Reliability

In the Spot robot trials, BRULE achieved a mean position error of only 55 cm (std dev: 8 cm). In contrast, BRULE-E exhibited a higher mean error (69 cm) and much higher variance (51 cm). This discrepancy highlights BRULE's superior ability to reason about landmark correlations, such as mutual exclusivity, ensuring the robot remains localized even when specific landmarks are missing.

Conclusion and Future Work

BRULE provides a robust and efficient solution for robot navigation in semi-static environments. By leveraging GMMs and intelligent pruning, it overcomes the exponential complexity of landmark evanescence. Future research will address current limitations, such as the assumption of perfect landmark detection and the static nature of the world during the execution phase, potentially incorporating landmark drift and more complex occlusion models.

Summary updated

BibTeX
@inproceedings{fuentes2025belief,
  author = {Erick Fuentes and Jared Strader and Ethan Fahnestock and Nicholas Roy},
  title = {{Belief Roadmaps with Uncertain Landmark Evanescence}},
  booktitle = {IEEE International Conference on Robotics and Automation},
  year = {2025},
  doi = {10.1109/icra55743.2025.11128352},
}
Figure