Planning with SiMBA: Motion Planning under Uncertainty for Temporal Goals using Simplified Belief Guides

Qi Heng Ho, Zachary N. Sunberg, Morteza Lahijanian

Abstract

This paper presents a new multi-layered algorithm for motion planning under motion and sensing uncertainties for Linear Temporal Logic (LTL) specifications. We propose a technique to guide a sampling-based search tree in the combined task and belief space using trajectories from a simplified model of the system, making the problem computationally tractable. Our method, Simplified Models with Belief Approximation (SiMBA), eliminates the need to construct fine and accurate finite abstractions. We prove correctness and probabilistic completeness of our algorithm and illustrate its benefits on several case studies. Results show that guidance with a simplified belief space model allows for significant speed-up in planning for complex specifications.

Introduction

Robots operating in real-world environments must navigate two primary challenges: complex task requirements and inherent uncertainty. Complex tasks, such as "Visit A, then B, but never enter C unless D has been visited," are formally expressed using Linear Temporal Logic (LTL). Simultaneously, robots contend with "noisy" motors (motion uncertainty) and sensors (measurement uncertainty). Instead of exact states, they maintain a belief—a probability distribution over possible states. Planning for LTL tasks in high-dimensional belief space is computationally expensive. Traditional abstraction-based methods often suffer from "state explosion," failing as problem complexity increases. SiMBA addresses this by finding valid paths through continuous belief space without relying on slow, fine-grained abstractions.

The SiMBA Framework

SiMBA utilizes a three-layer architecture to decompose the planning problem into manageable components:

  1. Task Planning Layer: The LTL formula is converted into a Finite State Automaton. To optimize search, the framework uses a geometric adjacency graph of the environment to prune physically impossible transitions from the task chart.
  2. SiMBA Guide Layer: This layer uses a Simplified Model of the robot's dynamics. While lower-dimensional or physically simpler, this model approximates how uncertainty grows and shrinks. It rapidly generates a "rough draft" trajectory that satisfies the temporal logic constraints.
  3. Belief Search Layer: A high-fidelity planner, such as Gaussian Belief Trees, uses the simplified trajectory as a guide. By biasing the search toward this guide, the algorithm drastically narrows the search space while ensuring the final plan respects the robot's true, complex dynamics.
The three-layer SiMBA architecture: Task Planning, SiMBA Layer, and Belief Search Layer.

Experimental Evaluation

The algorithm was evaluated on two simulated benchmarks:

  • Underwater Cave Inspection: A robot navigates a cave with varying sensor quality, where localization is only effective near the surface. Tasks ranged from simple reaching to complex nested sequences.
  • Urban Drone Delivery: A UAV must deliver packages in a city, receiving GPS signals only above specific building heights. The drone faces constraints on flight altitude while carrying cargo.
Visualization of the drone delivery task in 3D. The red ellipses represent the robot's belief (uncertainty) as it navigates around obstacles (grey blocks).

Key Results

SiMBA was compared against traditional abstraction-based approaches and a "SiMBA-free" baseline.

  • Scalability: Abstraction-based methods failed (0% success) due to the complexity of the belief space.
  • Performance: On the most complex underwater task, the SiMBA-free version achieved only a 4% success rate within 120 seconds. In contrast, the full SiMBA framework achieved a 54% success rate with significantly faster planning times.
  • Intelligent Behavior: In the drone scenario, the algorithm autonomously determined that the drone should fly higher to gain a GPS fix before attempting a precision landing, satisfying the LTL requirements through belief-aware planning.

Discussion and Conclusion

A central insight of this work is the effectiveness of "good enough" guides. A simplified model capturing the essence of uncertainty dynamics is sufficient to guide precise planners through complex spaces. Furthermore, geometric pruning prevents the exploration of logically valid but physically impossible solutions.

While SiMBA is probabilistically complete, its efficiency depends on the quality of the human-designed simplified model. Future work will explore the automatic generation and adaptive refinement of these models to further enhance planning performance in uncertain, high-dimensional environments.

Summary updated

Abstract

This paper presents a new multi-layered algorithm for motion planning under motion and sensing uncertainties for Linear Temporal Logic specifications. We propose a technique to guide a sampling-based search tree in the combined task and belief space using trajectories from a simplified model of the system, to make the problem computationally tractable. Our method eliminates the need to construct fine and accurate finite abstractions. We prove correctness and probabilistic completeness of our algorithm, and illustrate the benefits of our approach on several case studies. Our results show that guidance with a simplified belief space model allows for significant speed-up in planning for complex specifications.
BibTeX
@inproceedings{ho2023planning,
  author = {Qi Heng Ho and Zachary N. Sunberg and Morteza Lahijanian},
  title = {{Planning with SiMBA: Motion Planning under Uncertainty for Temporal Goals using Simplified Belief Guides}},
  booktitle = {IEEE International Conference on Robotics and Automation},
  year = {2023},
  url = {https://openreview.net/forum?id=VLXw7mduKs},
}
Figure