BoxRRT* -A Reliable Motion Planner

Adina M. Panchea, Alexandre Chapoutot, David FilliatHAL 2017

TL;DR

This paper introduces BoxRRT, a novel motion planner that guarantees safe and asymptotically optimal paths for mobile robots operating in uncertain environments. By combining stochastic sampling with robust interval-based numerical integration, BoxRRT addresses the critical challenge of ensuring reliability in robot navigation.

What Problem Does This Paper Address?

Navigating a mobile robot in the real world is fraught with uncertainty. The robot's exact starting position might be unknown, and its environment can contain obstacles that are difficult to model precisely. Traditional motion planners often struggle with these uncertainties, potentially leading to unsafe paths or outright failures. The authors tackle the problem of designing a motion planner that can reliably find a safe path from an uncertain initial state to a goal region, even when dealing with imprecise system dynamics and environmental information. This is crucial for applications where safety is paramount, such as autonomous driving or hazardous environment exploration.

Methods

The core of BoxRRT lies in its hybrid approach, blending established techniques with novel enhancements. It builds upon the Rapidly-exploring Random Tree (RRT) family of algorithms, which are known for their ability to efficiently explore complex configuration spaces and guarantee asymptotic optimality. Specifically, BoxRRT incorporates ideas from optimal RRT (RRT*) to ensure that the found path is not just feasible but also near-optimal in terms of cost.

The key innovation is the integration of modern tools for guaranteed numerical integration, specifically referencing work on DynIBEX (mentioned in the references). This allows the planner to handle uncertainties in the robot's state and dynamics more robustly. Instead of relying on point estimates, BoxRRT uses interval arithmetic to represent uncertain states and predict future states. This means that when the planner considers a potential path segment, it doesn't just check if a single trajectory is safe; it verifies that all possible trajectories* within the given uncertainty bounds remain safe. The algorithm iteratively refines the search tree, exploring new states and updating parent-child relationships to improve path quality and reduce cost over time, even after an initial solution is found.

Datasets

Not discussed in the paper. The paper focuses on a simulation-based application using a simple car model.

Key Insights and Ideas

  • Robustness through Interval Arithmetic: The most significant insight is the successful application of interval arithmetic to motion planning. This allows the planner to reason about and guarantee safety under uncertainty, a critical step beyond traditional planners that often assume perfect knowledge.
  • Guaranteed Safety in Uncertain Environments: BoxRRT* moves beyond probabilistic guarantees of safety to provide a more deterministic assurance, especially when combined with robust integration methods.
  • Asymptotic Optimality with Reliability: The paper demonstrates that it's possible to achieve both asymptotic optimality (finding the best possible path given enough time) and reliable safety, even in the presence of significant uncertainties.
  • Iterative Improvement: The algorithm's ability to continue refining the path even after finding an initial solution is a powerful feature, allowing for better performance over longer planning horizons or with more computational resources.

Key Results

The paper presents an application of BoxRRT to a simple car model with nonholonomic constraints*. For a planning task with 20,000 iterations (K=20000), the planner achieved the following:

  • CPU Time: 745 seconds.
  • Number of Vertices: 96.
  • Planned Path Length: 105 cm.
  • Total Number of Vertices in Tree: 13,655.

The accompanying Figure 1 visually depicts a BoxRRT* solution, showing the initial state (blue box), goal state (green box), and obstacles (red). This demonstrates the planner's ability to navigate around obstacles and reach the goal.

Limitations and Future Work

Limitations:

  • The computational cost for achieving high levels of reliability and optimality can be significant, as indicated by the 745-second runtime for the example.
  • The paper focuses on a specific type of uncertainty (interval-based state and dynamics) and a simplified car model.

Future Work:

The authors suggest that this work lays the foundation for more advanced reliable motion planning. Future directions could include:

  • Extending the approach to handle more complex and dynamic environments.
  • Investigating different types of uncertainty beyond interval arithmetic.
  • Optimizing the computational efficiency of the algorithm for real-time applications.
  • Applying BoxRRT* to more complex robotic systems with higher degrees of freedom.

Summary updated

Abstract

International audience
BibTeX
@inproceedings{panchea2017boxrrt,
  author = {Adina M. Panchea and Alexandre Chapoutot and David Filliat},
  title = {{BoxRRT* -A Reliable Motion Planner}},
  booktitle = {HAL},
  year = {2017},
}
Figure