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.
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.
Pruning and Search
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).
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