PaperlayerView exact revision on arXiv

Source-linked AI summary

Motion planning in high dimensional spaces hybridizing RRT and HAR via position-direction decoupling

Frederic Cazals, Nelson Feyeux

arXiv:2609.16810v1cs.RO

TL;DR

High-dimensional motion planning is difficult in narrow passages and low-clearance spaces, particularly for many interacting robots. The paper hybridizes RRT and Hit-and-Run by decoupling node selection from extension direction, and introduces sparse robot moves for cluttered instances. Its methods solve molecular multi-robot problems with up to 64 robots and 384 degrees of freedom within seconds, with HARF reported as substantially faster than classical RRT in supported settings.

  • Problem

    High-dimensional motion planning is challenging in narrow passages and small-clearance regions, especially when many rigid domains move collectively.

  • Method

    The paper decouples RRT’s point selection from HAR’s direction sampling, yielding HARG, HARL, and HARF and allowing only a fraction p_r of robots to move at each step.

  • Results

    The methods solve instances with up to 64 robots and 384 degrees of freedom within seconds on a standard laptop, while HARF can be up to two orders of magnitude faster than classical RRT when it succeeds.

  • Takeaways & Limitations

    HARF is suggested as a method of choice for complex multi-robot planning, with sparse moves helping both RRT and HAR handle cluttered instances.

  • Takeaways & Limitations

    No algorithm solved the Cradle-64 model in mass-start mode within the 10-minute wall-clock limit.

Abstract

from arXiv · show

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.

1 Introduction

The paper targets high-dimensional and multi-robot motion planning, especially molecular systems with many rigid domains. It hybridizes RRT and HAR by assigning point selection and extension direction separately, and applies the framework jointly in SE(3)^N.

  • 1.1 Previous work: High-dimensional planning is difficult because randomized methods must discover narrow passages and unexplored regions while avoiding inter-robot collisions.Existing multi-robot approaches include decoupled, centralized, and sampling-based techniques, often relying on products of individual roadmaps.
  • 1.1 Previous work: The work addresses collective motion planning for rigid protein domains, modeled as up to many independently moving six-degree-of-freedom robots.The molecular-cradle formulation treats domains as individual molecules and explores their relative motions jointly.
  • 1.2 Contributions: RRT and HAR are complementary: RRT selects which node to extend through Voronoi bias, whereas HAR randomizes the extension direction.The paper uses this distinction as the basis for combining the two methods.
  • 1.2 Contributions: The proposed HARG, HARL, and HARF planners use HAR-based extension within RRT, while a generic von Mises–Fisher formulation contains RRT and HAR as special cases.The variants differ in how the new point is sampled: globally, locally over length δ, or at a fixed distance δ.
  • 1.2 Contributions: The framework plans N robots jointly in SE(3)^N without constructing explicit products of individual roadmaps, solving instances with up to 64 robots and 384 degrees of freedom within seconds.The contribution includes mass-start and rolling-start modes for controlling how concurrently robots move.

2 Motion planning with Hit-and-Run sampling

The planning framework retains RRT’s node-selection mechanism while replacing its extension direction with HAR-based sampling. HARG, HARL, and HARF differ in how far they sample along random directions, improving exploration of low-clearance free space.

  • 2.1 General setup: The planner performs collision checks on curved configuration-space segments, with joint configurations formed as products of individual robot spaces.Path shortening subsequently uses random shortcutting and partial shortcutting to reduce path length while preserving validity.
  • 2.2 The RRT planning algorithm: RRT selects a nearest tree node for a random configuration and projects the sample onto a radius-δ sphere when it lies farther than δ.The resulting node and edge are added only when the curved segment is collision-free.
  • 2.3 Decoupling positions and directions in RRT with HAR: Position-direction decoupling helps in low-clearance regions because RRT’s far-away samples are often projected onto obstructed spheres, especially in high dimensions.HAR instead samples productive portions of random rays more readily, reducing unproductive steering steps near obstacles.
  • 2.3 Decoupling positions and directions in RRT with HAR: HAR-based variants preserve RRT’s tree-building template but differ only in how qnew is sampled during the extension step.After a valid new sample is drawn, it is stored in the tree using the same connection process as RRT.
  • 2.3 Decoupling positions and directions in RRT with HAR: HARG samples along a random ray until collision or the domain boundary, HARL samples randomly on a ray of length δ, and HARF takes a fixed-distance δ step.These strategies randomize direction while retaining distinct global, local, and fixed-distance positional choices.
  • 2.3 Decoupling positions and directions in RRT with HAR: The generic sampler can couple positional and directional biases through a von Mises–Fisher distribution whose concentration depends on the positional bias.This provides a continuum between the RRT and HAR sampling behaviors.

3 Instantiations: planning in SE(3) and SE(3)N

The paper instantiates motion planning for single rigid bodies in SE(3) and multiple independent robots in SE(3)^N, defining sampling, distances, paths, and HAR directions for these spaces.

  • SE(3): Single-object planning searches valid rigid SE(3) transformations from source to target while avoiding obstacles.
  • SE(3): The SE(3) configuration space is bounded by R, with configurations represented as rigid transformations combining translation and rotation.
  • SE(3): HAR directions combine a rotation vector with a translational vector, balancing rotation and displacement through the steering range δ.
  • SE(3): Local HAR samples along a direction up to δ, whereas global HAR extends the ray to a boundary or collision before sampling on the resulting curved segment.
  • SE(3)^N: For N robots, the configuration space is SE(3)^N; points, tangent-space directions, translations, distances, and interpolated paths are constructed componentwise across robots.

4 Experiments

The experiments compare RRT and HAR variants across path-finding and path-quality tasks, tuning steering ranges and direction bias under repeated, time-limited runs.

  • Setup: The study compares RRT-C, HARF, HARL, and HARG variants, using Connect methods for finding paths and Quick or Informed heuristics for path quality.
  • Setup: Each contender is run 50 times per model under a fixed time limit, with path shortening performed for 30 seconds.
  • Setup: The reported statistics include first-path time, final-path length, successful point creation per iteration, and run success rate.
  • Hyper-parameter tuning: The steering range δ is tuned separately for each Connect algorithm by retaining the value with the lowest mean first-path time over 50 runs.
  • Hyper-parameter tuning: HARF interpolates between HAR at κ = 0 and RRT at κ = ∞ through a von Mises-Fisher bias on extension directions.

4.4 Models

The evaluation spans single-object, multi-robot, and molecular-cradle models, revealing that HAR methods become increasingly advantageous as jointly moving systems grow more difficult.

  • Models: The models range from 6 degrees of freedom in Cubicles through 20-degree-of-freedom 2D systems to molecular cradles reaching 384 degrees of freedom.
  • Piano mover and Cubicles model: 0.85 s makes RRT-C fastest on the single-object Cubicles model, versus 3.5–7.7 s for HAR variants, while final path lengths remain comparable.
  • 2D disk models: 0.017 s versus 0.51 s on 2D-small-obstacle and 0.40 s versus 42.8 s on 2D-big-obstacle: HARF-C is about 30–100 times faster than RRT variants, with shorter paths.
  • 2D disk models: Increasing obstacle size causes running-time losses of 24-fold for HARF-C and 84-fold for RRT-C because of collisions in the steering procedures.
  • Molecular cradles: On molecular cradles, HARF-C reaches Cradle-9 in 0.037 s versus 0.049 s for RRT-C and Cradle-25-coarse in 0.4 s versus 1.13 s.
  • Molecular cradles: No algorithm solves Cradle-64 in mass-start mode within 10 minutes, motivating experiments with rolling starts.

4.6 RRT versus HAR in rolling start mode

Tuning the moving fraction p_r improves performance as clutter and dimensionality increase, with HARF-C generally providing the strongest multi-robot results and RRT-C remaining effective on easier or single-robot problems.

  • Performance improves with p_r < 1 as clutter increases, including 2D-big-obstacle, Cradle-25-tight, and Cradle-64.
  • On Cradle-25-tight, tuned p_r yields 3.4s for HARF-C and 5.2s for RRT-C, while HARL-C and HARG-C improve from roughly 1–2 minutes to 7–30 seconds.
  • For Cradle-64, HARF-C finds a path in 17.3s with p_r = 0.35, while RRT-C takes 41.6s with p_r = 0.1; HARL-C and HARG-C exceed five minutes.
  • HARF-C remains ahead of RRT-C on all multi-robot models except Cradle-25-coarse when both use tuned p_r, by factors of 1.2 to 2.4.The largest margin occurs on the largest instance, and the authors characterize the advantage as robustness rather than raw speed.
  • Single-robot problems favor RRT-C for rapid path finding, whereas multi-robot problems may require tuning p_r because mass concentration and forward steering hinder RRT-C at p_r = 1.
  • The Quick heuristic slows every algorithm but shortens final paths, with its main benefit appearing in obstacle-rich settings.
  • HARG has the most productive iterations, HARL is also efficient, and HARF and RRT generate fewer samples because they use approximately fixed-distance steps.

4.8 Comparison against recent contenders

The comparison with recent approaches shows that the proposed planners are competitive with fiber-bundle methods and faster than a recent diffusion-based approach, while RRT difficulties remain tied to steering in high-dimensional, low-clearance spaces.

  • For flying drones, the proposed RRT-C and HARF-C times are comparable to the fiber-bundle method in mass start mode and better in rolling start mode.The fiber-bundle method takes 0.14s, versus 0.17s for RRT-C and 0.21s for HARF-C in mass start; rolling-start times are 0.062s and 0.14s.
  • The fiber-bundle approach reduces dimensionality by stratifying the configuration space into multiple lower-dimensional levels, but requires designing the stratification and choosing the number of levels.
  • The proposed methods are one order of magnitude faster than the diffusion-based approach on comparable multi-robot systems.The diffusion approach reports systems up to 20 robots and 40 degrees of freedom with running times of tens of seconds.
  • RRT’s mass-start difficulty arises from steering and the choice of δ: large δ increases collisions at low clearance, whereas small δ produces insufficient rotational change.
  • Orthogonal ray sampling and rotational-weight tuning produced no significant performance improvement, and random rotation patches did not repair RRT’s small-δ behavior.
  • Resetting the HAR walk after every iteration, K_steps = 0, performed best compared with following HAR for multiple consecutive steps.

5 Outlook

The paper combines RRT’s exploration with HAR-based directional sampling for joint planning in high-dimensional multi-robot spaces, and recommends HARF with tuned p_r for large, cluttered instances.

  • The hybrid strategy decouples sampled positions from extension directions, combining RRT’s exploration of unseen regions with HAR’s ability to search in arbitrary directions.
  • Tests show RRT variants struggle as dimensionality grows, whereas HARL and HARG are more resilient to increased dimensionality.
  • Using a reduced moving fraction p_r provides a simpler way to tame the configuration space, and this strategy is complementary to configuration-space stratification.
  • RRT-C remains an excellent default for low-dimensional problems, while HAR-based samplers, especially HARF, become more effective as robot count and clutter increase.
  • Theoretical analysis of the hybrid algorithms and their hyperparameters remains an open direction, alongside applications to multi-robot motion in cluttered environments.

S1 RRT and HAR: illustrations

The supplementary illustration uses a cradle model to visualize RRT and HAR behavior in a configuration space where each molecule moves along a prescribed geodesic path.

  • The toy system contains N molecules, each represented by a parameterized geodesic path between its initial and final positions.
  • The associated configuration space is C = [0, 1]^N, corresponding to independent motion of N robots.
  • Planning starts at q0 = (0, . . . , 0)^T and targets q∞ = (1, . . . , 1)^T.
  • Figures S1 and S2 project nodes, edges, and solutions onto the motion space of the first two robots to illustrate algorithm behavior.Figure S1 shows six RRT algorithms after 1500 iterations with a steering value of 2%; Figure S2 gives the corresponding HAR illustration.

S2 Models

The section introduces random domains as connected regions of unit cubes, then replaces cubes with balls to form fictitious random molecules.

  • A random domain is modeled as a connected region of unit cubes, called a 3D polycube.
  • Replacing the cubes with balls converts the polycube representation into a fictitious random molecule or domain.
  • The construction provides a geometric model for random domains in three dimensions.

S3 Sampling coupled translations

This section derives the distribution and expected norm of one translation block when the joint translation vector is sampled uniformly on a high-dimensional sphere.

  • Joint translations are sampled on S3N−1, and Gaussian vectors normalized by their joint norm have the same distribution.
  • The squared norm of each translation block follows a Beta distribution obtained from independent chi-square components.
  • The expected norm of one translation block is then computed from the resulting Beta density and Gamma-function expression.
  • For N = 1, the expected block norm equals 1 because the single translation vector lies on the unit sphere.
  • For N = 2, substituting Gamma-function values yields the stated closed-form expectation for each block norm.

S4 Detailed results

The detailed-results section reports contender comparisons across classical and molecular models, using tables averaged over 50 runs and organized by algorithmic mode.

  • Classical models: The Cubicles benchmark uses a 405 × 200 × 200 box with start-goal distance 205 and one-minute runs.
  • The tables cover Cubicles, 2D-small-obstacle, 2D-big-obstacle, Cradle-9, Cradle-25-coarse, Cradle-25-tight, and Cradle-64.
  • Results are averaged over 50 runs and report both pr = 1 and an optimal pr when it differs from one.
  • Each table separates Connect and Quick-Connect blocks, sorts by time to the first path, and marks the best and second-best entries.
  • Molecular models: The Cradle-9 benchmark uses a 228 × 228 × 220 box, start-goal distance 30.0, and one-minute runs.
Loading 2609.16810v1…