Search papers, labs, and topics across Lattice.
This paper introduces fibration trees, a novel framework that integrates state space projections and decompositions to address the challenges of high-dimensional multi-robot motion planning. By modeling projections as fibrations, the authors unify various planning strategies, leading to the development of the Fibration-RRT planner, which is proven to be probabilistically complete. Experimental results across 32 scenarios demonstrate that Fibration-RRT effectively manages complex motion planning tasks with multi-robot teams, showcasing the framework's efficiency and versatility.
Fibration-RRT can tackle high-dimensional multi-robot motion planning by seamlessly integrating projection and decomposition strategies, proving to be both efficient and robust.
State space projections and decompositions have emerged as powerful tools to tackle the curse of dimensionality in high-dimensional, multi-robot motion planning problems. However, existing methods lack a unified framework which seamlessly handles combinations of projections (prioritization or task-space) and decompositions (parallel or decoupled subspaces). To fill this gap, we introduce fibration trees, which are trees consisting of state spaces as nodes and fibrations as edges, whereby a fibration models a projection from a higher-dimensional space to a lower-dimensional (or simplified) space. By modeling projections as fibrations, we unify sequential prioritization, parallel decomposition, and task-space projections under a single, coherent formalism. Building on this, we develop the rapidly-exploring random fibration trees (Fibration-RRT) planner, a sampling-based motion planner that generalizes strategies from quotient-space RRT (for sequential prioritizations) and discrete RRT (for parallel decompositions), while allowing the inclusion of task-space projections. Fibration-RRT operates on user-defined fibration trees and is proven to be probabilistically complete. To test the generality and efficiency of Fibration-RRT, we provide an open-source implementation and conduct experiments on 32 scenarios using multi robot teams with up to 96 degrees of freedom. Our results indicate that Fibration-RRT efficiently solves high-dimensional problems by exploiting user-defined fibration trees, thereby establishing fibration trees as a powerful, unified framework for multi-robot motion planning.