Multilevel motion planning: A fiber bundle formulation

Andreas Orthey, Sohaib Akbar, Marc Toussaint

Abstract

Motion planning in high-dimensional state spaces is a fundamental challenge in robotics. This paper presents a rigorous mathematical framework using fiber bundles to formalize multilevel abstractions. By modeling state spaces as local product spaces consisting of a "base space" (abstraction) and a "fiber" (details), we derive novel bundle primitives—restrictions and sections. These primitives enable the development of two new algorithms, QRRT and QMP**, which are proven to be probabilistically complete and asymptotically optimal. Evaluated on benchmarks with up to 100 degrees of freedom (DoF), our approach demonstrates speedups of up to six orders of magnitude over state-of-the-art planners, effectively solving complex problems that remain intractable for standard methods.

Introduction

As robots become more complex, the dimensionality of their configuration spaces grows, leading to an exponential increase in the difficulty of finding collision-free paths. While hierarchical planning is a common strategy to mitigate this "curse of dimensionality," formalizing these abstractions has historically lacked a unified mathematical language. Many existing hierarchical planners rely on heuristics that sacrifice theoretical guarantees like probabilistic completeness or asymptotic optimality.

This work addresses these gaps by introducing a fiber bundle formulation for multilevel motion planning. This framework allows us to "lift" solutions from simplified, lower-dimensional abstractions back into the full, high-dimensional state space with mathematical precision.

The Fiber Bundle Framework

The core of our approach is the use of fiber bundles from differential topology to model multilevel abstractions. In this view, a high-dimensional state space (the "total space") is projected onto a simpler "base space." The information lost during this projection is captured by the "fiber."

The SAGE framework workflow for multilevel motion planning.

The framework, illustrated in the flowchart above, involves imposing a multilevel abstraction on the state space, modeling it as a sequence of fiber bundles, and then deriving specific primitives to guide the planning process.

Geometric Intuition

To visualize this, consider a 3D torus. It can be abstracted into a 1D circle. In this case, the "fiber" at any point on the base circle is another circle. By planning a path on the base circle first, we can restrict our search in the 3D torus to the region that projects onto that path.

Geometric intuition of fiber bundles: projecting a torus or Mobius strip onto a circle.

Bundle Primitives

We define two key operations to navigate these levels:

  1. Bundle Restrictions: This operation limits the search in the high-dimensional space to the "preimage" of a successful path found in the low-dimensional abstraction. This focuses the planner's efforts on regions most likely to contain a valid solution.
  2. Bundle Sections: This is a recursive method used to "lift" a path from the abstraction to the full space. It involves finding feasible configurations within the fibers along the base path.

Algorithms: QRRT and QMP

Building on these primitives, we introduce two novel algorithms:

  • QRRT* (Quotient-space Rapidly-exploring Random Trees): An extension of the RRT* algorithm that grows trees across a sequence of increasingly complex quotient spaces.
  • QMP* (Quotient-space Roadmap Planner): A multilevel version of the PRM* algorithm that builds roadmaps through successive abstractions.

Both algorithms are designed to be probabilistically complete and almost-surely asymptotically optimal, ensuring that they will eventually find the shortest possible path if one exists.

Experimental Evaluation

We evaluated our fiber bundle planners against the Open Motion Planning Library (OMPL) on 12 diverse benchmarks. These ranged from low-dimensional tasks (e.g., a 6D piano mover) to extremely high-dimensional scenarios, including:

  • 100-DoF Hypercube: A purely high-dimensional search problem.
  • 21-DoF Box Folding: A complex manipulation task.
  • 54-DoF Kraken Animation: A high-DoF character animation problem.

Key Results

The results highlight the dramatic efficiency gains of the fiber bundle approach:

  • Orders of Magnitude Speedup: In the 100-DoF Hypercube scenario, QRRT* was approximately six orders of magnitude faster than the best-performing standard planner (STRIDE).
  • Solving Intractable Problems: In several high-DoF environments, such as the 30-DoF airport scenario, standard planners failed to find any solution within a 60-second limit. In contrast, our bundle planners consistently found solutions in under a second.
  • Sampling Efficiency: The strategy of sampling within path restrictions and gradually decaying that bias proved highly effective at finding narrow passages in high-dimensional spaces.

Conclusion and Future Work

The fiber bundle formulation provides a powerful and mathematically rigorous foundation for multilevel motion planning. By exploiting the structure of state space projections, we can achieve unprecedented performance in high-dimensional robotics tasks.

Currently, the hierarchy of abstractions must be specified manually. Future research will focus on the automatic discovery of optimal fiber bundle sequences, potentially by analyzing robot kinematics and environment geometry to identify the most critical degrees of freedom for a given task. Additionally, exploring bidirectional search variants could further enhance performance in complex "ingress" problems.

Summary updated

Abstract

Motion planning problems involving high-dimensional state spaces can often be solved significantly faster by using multilevel abstractions. While there are various ways to formally capture multilevel abstractions, we formulate them in terms of fiber bundles, which allows us to concisely describe and derive novel algorithms in terms of bundle restrictions and bundle sections. Fiber bundles essentially describe lower-dimensional projections of the state space using local product spaces. Given such a structure and a corresponding admissible constraint function, we can develop highly efficient and optimal search-based motion planning methods for high-dimensional state spaces. Our contributions are the following: We first introduce the terminology of fiber bundles, in particular the notion of restrictions and sections. Second, we use the notion of restrictions and sections to develop novel multilevel motion planning algorithms, which we call QRRT* and QMP*. We show these algorithms to be probabilistically complete and almost-surely asymptotically optimal. Third, we develop a novel recursive path section method based on an L1 interpolation over path restrictions, which we use to quickly find feasible path sections. And fourth, we evaluate all novel algorithms against all available OMPL algorithms on benchmarks of eight challenging environments ranging from 21 to 100 degrees of freedom, including multiple robots and nonholonomic constraints. Our findings support the efficiency of our novel algorithms and the benefit of exploiting multilevel abstractions using the terminology of fiber bundles.
BibTeX
@article{orthey2020multilevel,
  author = {Andreas Orthey and Sohaib Akbar and Marc Toussaint},
  title = {{Multilevel motion planning: A fiber bundle formulation}},
  journal = {Int. J. Robotics Res.},
  year = {2020},
  url = {https://openreview.net/forum?id=zKTpXYqUhe},
}
Figure