Fibration Trees: A Unified Approach to Multi-Robot Motion Planning

The exploration of high-dimensional spaces remains a challenging problem, in particular in the presence of narrow passages and small clearances. We propose novel sampling-based path-planning methods for high-dimensional spaces combining Rapidly-exploring Random Trees (RRT) and Hit-and-Run (HAR) random walks by decoupling the point being extended from the direction of extension. We also show that RRT and HAR appear as special cases of a generic algorithm coupling the biases used for the point and direction extension, respectively. We further study a sparse-move strategy in which only a fraction p_r of the robots is moved at each step, helping both RRT and the proposed HAR algorithms handle cluttered instances. Tests are presented for two families of models: classical piano mover problems in 3D, and complex molecular systems involving tens of rigid domains moving relatively to one another -- the latter viewed as independent robots exploring the motion space SE(3)N . Within seconds on a standard laptop, our algorithms solve instances with up to 64 robots and 384 degrees of freedom. We conclude by suggesting one of our methods, HARF, as the method of choice for complex multi-robot planning problems, being up to two orders of magnitude faster than the classical RRT moving all robots at each step--when it succeeds at all, and still up to 2.4 fold faster on most instances when both use their best p_r.

A fundamental challenge in multi-robot motion planning is achieving sufficient coordination to avoid inter-robot conflicts without incurring the large computational expense of searching the joint configuration space of the robot group. In this work, we present a method for multiple mobile robot motion planning that achieves an improvement in planning time up to an order of magnitude by leveraging the insight that we can use discrete search over a workspace decomposition to provide coordination between robots during planning. While prior work uses workspace topology to inform when coordination between robots is needed and then composes robots into their joint configuration space, we take a step further by iteratively refining our workspace representation to allow our planner to search smaller, decoupled configuration spaces.

We propose a workspace-fibered decomposition framework for motion planning in nR planar redundant manipulators operating in cluttered environments. Rather than planning directly in the full n-dimensional configuration space, the method incrementally constructs obstacle-constrained reachable workspaces of lower-dimensional non-redundant sub-chains and recursively lifts them through redundant orientation fibers. This yields a sequence of reduced planning manifolds that preserve branch-consistent reachability structure while avoiding explicit construction of the full configuration-space obstacle geometry. We first establish that, for planar position-only manipulators, the obstacle-constrained reachable workspace induced by the minimal non-redundant sub-chain provides an exact characterization of feasibility with respect to the connected component of the start configuration, enabling early infeasibility detection prior to introducing redundant degrees of freedom (DOF). We then introduce an incremental fiber-lifting procedure that propagates reachable workspace structure through successive redundant links while enforcing local inverse-kinematic branch consistency using Jacobian determinant continuity constraints. The resulting representation admits efficient reduced-space planning directly on recursively-constructed workspace-fiber manifolds. Experimental results on redundant nR planar manipulators demonstrate that the proposed construction preserves collision-free connectivity structure across successive lifting stages while substantially reducing collision checking complexity relative to direct configuration space reasoning.