PaperlayerView exact revision on arXiv

Source-linked AI summary

MR. POP: Multi-Robot Parallel Optimizing Planner for Almost-Surely Asymptotically Optimal Planning

Chih H. Huang, Roy Xing, Brian Plancher, Zachary Kingston

arXiv:2609.30644v1cs.RO

TL;DR

Multi-robot planners still struggle to scale while preserving probabilistic convergence guarantees and computational performance. MR. POP combines GPU SIMT parallelism with dRRT and AO-x; it reports a 100% solve rate and faster convergence than state-of-the-art a.s.a.o. planners up to 35-DOF, alongside higher downstream optimizer success.

  • Problem

    Multi-robot planners struggle to scale while achieving both probabilistic convergence guarantees and strong computational performance.

    Source: §I · p. 1, §VI · p. 7

  • Method

    MR. POP combines dRRT and AO-x with GPU SIMT parallelism to run hundreds of roadmap-construction and tree-search iterations alongside parallel nearest-neighbor search and collision checking.

    Source: §I · p. 1, §VI · p. 8

  • Results

    MR. POP was the only planner achieving a 100% solve rate while running faster than state-of-the-art a.s.a.o. planners in multi-robot systems up to 35-DOF.

    Source: §VI · p. 8

  • Takeaways & Limitations

    MR. POP’s high-quality, diverse seeds helped downstream motion optimizers avoid local minima, raising success from 4% to 72%.

    Source: §VI · p. 8

Abstract

from arXiv · show

Finding globally optimal paths remains a fundamental challenge in multi-robot motion planning. Despite acceleration of almost-surely asymptotically optimal (a.s.a.o.) planners via CPU-based parallelism, achieving both probabilistic convergence guarantees and strong computational performance, these algorithms still struggle to scale to multi-robot settings. As such, we introduce MR. POP, a GPU-based a.s.a.o. multi-robot planner based on dRRT and the AO-x meta-algorithm. MR. POP uses large-scale GPU-based SIMT-parallelism to simultaneously run hundreds of roadmap construction and tree search iterations with underlying parallel nearest neighbor search and collision checking operations. We show that this enables MR. POP to become the only planner achieving a 100% solve rate while being faster than state-of-the-art a.s.a.o. planners in multi-robot systems up to 35-DOF. MR. POP also raises the success rate of downstream motion optimizers (e.g., from 4% to 72%), by creating high-quality, diverse seeds that help avoid local minima.

I. INTRODUCTION

MR. POP addresses the difficulty of scaling multi-robot planning while retaining a.s.a.o. guarantees, using GPU parallelism with dRRT and AO-x. The paper reports strong solve and convergence results, and places the approach among earlier CPU- and GPU-parallel planning methods.

I. INTRODUCTION

  • Motion planning separates finding an initial collision-free path from optimizing it, while a.s.a.o. planners continually improve path quality toward the global optimum.The cited examples include RRT* and BIT* [6, 7].Source: §I · p. 1
  • Existing multi-robot planners avoid composite-space planning by decoupling robots, yet dRRT still struggles to scale and a.s.a.o. overhead remains a real-time barrier.The decoupling first finds individual collision-free paths, then resolves inter-robot collisions.Source: §I · p. 1
  • MR. POP combines dRRT and the AO-x meta-algorithm with GPU SIMT parallelism for multi-robot a.s.a.o. planning.It runs hundreds of roadmap-construction and tree-search iterations simultaneously, with parallel nearest-neighbor search and collision checking.Source: §I · p. 1
  • MR. POP was the only planner to achieve a 100% solve rate for initial solutions in multi-manipulator settings, and it showed faster convergence to optimal solutions.It also raised cuRoboV2’s success rate on multi-robot tasks from 4% to 72%.Source: §I · p. 1
  • The introduction reports real-world validation on a 14-DOF dual-arm setup and release of MR. POP as open source.The passage provides the project repository URL.Source: §I · p. 2

II. BACKGROUND AND RELATED WORK

  • AO-x adds a cost-to-come dimension and increasingly lower cost bounds to feasible planners, including AORRTC’s combination of AO-x and RRT-Connect.AORRTC has shown orders-of-magnitude speedups in finding paths of lower sub-optimality factor.Source: §II · p. 2

A. Parallel Acceleration of Planning Algorithms

  • CPU parallel planning spans concurrent planner instances, parallel iterations, and parallel primitive operations, with examples including C-Forest, PRRT, and VAMP.C-Forest achieves superlinear speedup, while VAMP reports microsecond-scale planning.Source: A. Parallel Acceleration of Planning… · p. 2
  • Prior GPU planning work likewise covers high-, mid-, and low-level parallelism, with pRRTC combining mid- and low-level approaches for 5–10x speedups.Other examples include Quad-RRT, Kino-PAX, and cuRobo.Source: A. Parallel Acceleration of Planning… · p. 2

B. Multi-Robot Motion Planning

MR. POP uses per-robot roadmaps and searches their tensor product to plan in the composite free space. Its GPU implementation parallelizes roadmap construction and planning iterations across the grid.

B. Multi-Robot Motion Planning

  • dRRT builds a collision-free roadmap for each robot, then searches their tensor product to avoid inter-robot collisions; dRRT* repeats iterations toward a globally optimal solution in the limit.Prior acceleration attempts precompute inter-robot collisions and avoid costly rewiring [23].Source: B. Multi-Robot Motion Planning · p. 2

III. MR. POP ALGORITHM

  • MR. POP uses GPU-parallel bidirectional dRRT for initial solving and pairs bidirectional dRRT with AO-x for optimization, running independent iterations across blocks.Thread-level parallelism handles sampling, nearest-neighbor search, and collision checking.Source: §III · p. 2

A. Problem Setup

  • The composite roadmap is the tensor product of individual PRMs, with vertices mutually collision-free and edges representing collision-free robot moves or stay-put steps.Composite path cost is the sum of successive configuration distances; g(q) lower-bounds cost-to-come and cbest is the best path cost so far.Source: A. Problem Setup · p. 2

B. Roadmap Construction

  • Roadmap construction runs in parallel across the GPU grid: blocks are assigned to robots, sample configurations, find neighbors within radius δ, and collision-check candidate edges.After a grid-wide synchronization, the leader block checks roadmap connectivity by breadth-first search; Fig. 2 also shows the GPU grid divided among robots.Source: B. Roadmap Construction · pp. 2–3, Figure 2 · p. 3

C. Solve for Initial Solution

MR. POP runs independent bidirectional dRRT iterations across GPU blocks to seek an initial solution. Afterward, AO-x searches configuration-and-cost space for paths cheaper than the incumbent.

C. Solve for Initial Solution

  • During initial solving, each GPU block runs an independent bidirectional dRRT iteration, allowing hundreds of iterations to proceed in parallel.Each iteration expands the smaller tree, samples a composite configuration, queries dRRT’s oracle, and attempts a collision-free connection to the opposing tree.Source: C. Solve for Initial Solution · p. 3

D. Converge to Global Optimality

  • For optimization, AO-x represents tree vertices as configuration–cost-to-come pairs and samples as configuration–cost-budget pairs, making improvement below cbest a feasibility search.Every GPU block runs its own iteration.Source: D. Converge to Global Optimality · p. 3
  • AO-x samples configurations from the informed set and cost budgets from g(qrand) to cbest, then selects admissible tree extensions that stay within budget.The opposing-tree connection uses budget cbest − gnew; the random cost coordinate keeps every path cheaper than cbest reachable with positive probability.Source: D. Converge to Global Optimality · p. 3

E. Multi-Thread Reassignment for Collision Checking

MR. POP uses two-stage collision checking: coarse checks run in parallel over discretized motions, then fine-grained work is reassigned according to estimated workload.

E. Multi-Thread Reassignment for Collision Checking

  • MR. POP discretizes each edge into motions and checks each checkpoint against coarse and fine spherical approximations of the robot’s collision geometry.The robot’s URDF is used to generate both approximations.Source: E. Multi-Thread Reassignment for… · p. 4
  • In the coarse stage, four threads per discretized motion trace forward kinematics and check a conservative sphere representation in parallel.For each motion, the stage counts the fine-grained spheres requiring checks in the second stage.Source: E. Multi-Thread Reassignment for… · p. 4
  • In the fine stage, threads are reassigned among motions in proportion to their remaining sphere-check workload, dividing each motion’s checks evenly across its assigned threads.This allocation is described as preventing stalling and increasing throughput.Source: E. Multi-Thread Reassignment for… · p. 4

F. Seeding for Multi-Robot Jerk-Free Motion

MR. POP can seed jerk-free motion optimization with diverse paths generated during its optimization process. The authors integrate it into cuRoboV2’s seeding component, prioritizing lower-cost paths when selecting seeds.

F. Seeding for Multi-Robot Jerk-Free Motion

IV. THEORETICAL ANALYSIS

Under robust optimality, MR. POP’s incumbent converges almost surely to the optimal cost as roadmap size and iteration count grow. The analysis combines cost-bounded dRRT on an incrementally grown roadmap with probabilistic roadmap approximation guarantees.

Theorem 1

  • Under robust optimality, MR. POP is a.s.a.o.: its incumbent converges almost surely to C* as roadmap size and iteration count tend to infinity.The assumption requires paths of cost at most (1 + ε)C* with positive clearance for every ε > 0.Source: §IV · p. 4

Convergence argument

  • The AO-x analysis applies these subroutine properties across growing roadmaps and iteration counts to establish incumbent convergence.For each fixed roadmap, its finite set of path costs lets the incumbent reach that roadmap’s minimum after finitely many iterations.Source: §IV · pp. 4–5

Subroutine conditions

  • On a fixed roadmap, cost-bounded dRRT terminates almost surely when a path cheaper than the incumbent exists and has expected suboptimality contracting by a positive fraction.The contraction constant depends only on the fixed roadmap.Source: §IV · p. 5

Roadmap approximation

  • With the stated connection-radius condition, the roadmap contains a path of cost at most (1 + ε)C* with probability tending to one for every ε > 0.The radius is based on the PRM* radius applied per robot; roadmap growth and a constant radius δ do not affect the theorem when δ eventually exceeds r*(n).Source: §IV · p. 5

V. EXPERIMENTS

The experiments evaluate MR. POP on multi-robot planning and optimization, test its components through single-robot ablations, and validate it on dual-arm hardware.

Multi-robot experiments

  • Multi-robot experiments assess initial-solution finding and path optimization, including MR. POP’s combination with cuRoboV2 for globally optimal seeding.Source: §V · p. 5

Single-robot ablations

  • Single-robot tasks isolate the tree-search and AO-x components, testing bidirectional search for initial solutions and AO-x for path optimization.Source: §V · p. 5

Hardware validation

  • The evaluation also validates MR. POP on dual-arm hardware.Source: §V · p. 5

A. Methodology

The methodology covers 28- and 35-DOF multi-manipulator benchmarks, compares MR. POP with GPU and CPU planner baselines, and includes single-robot baselines and hardware details.

Multi-robot benchmarks

  • The benchmarks comprise 50 four-Franka bin-packing problems at 28 DOF and 50 five-Franka shelf-reaching problems at 35 DOF.Source: A. Methodology · p. 5

Planner baselines

  • Multi-robot baselines include cuRoboV2, pRRTC, VAMP-MR, and a GPU bidirectional ao-dRRT implementation; single-robot baselines include cuRoboV2, pRRTC, AORRTC, RRT*, BIT*, and FMT.Source: A. Methodology · pp. 5–6

Multi-robot benchmarks

  • In the 28-DOF bin-packing benchmark, only MR. POP and pRRTC achieve a 100% solve rate; MR. POP averages 2.5x speedup over pRRTC, 1.9x over VAMP-MR CBS, and 4.3x over VAMP-MR RRT among planners above 60% solve rate.Source: Figure 3 · p. 6
  • In the 35-DOF shelf-reaching benchmark, only MR. POP achieves a 100% solve rate; among planners with at least 60% solve rate, it averages 3.1x speedup over pRRTC and 5.1x over VAMP-MR CBS and VAMP-MR RRT.Source: Figure 4 · p. 6

Hardware

  • Experiments ran on a desktop with an Intel Core Ultra 9 285K 24-Core CPU and NVIDIA GeForce RTX 5090 GPU.Source: A. Methodology · p. 6

B. Multi-Robot Simulation Benchmarks

Across the multi-robot benchmarks, MR. POP combines high solve rates with faster path optimization, and its advantage increases on the 35-DOF problem. Using MR. POP seeds also improves cuRoboV2’s success and path outcomes.

B. Multi-Robot Simulation Benchmarks

  • On 28-DOF bin packing, only MR. POP and pRRTC achieved a 100% solve rate; MR. POP had a 2.5x speedup over pRRTC.For path optimization, MR. POP converged to lower-cost solutions faster than ao-dRRT, with a smaller interquartile range.Source: B. Multi-Robot Simulation Benchmarks · p. 6
  • At 35 DOF, MR. POP alone achieved a 100% solve rate and averaged 3.1x speedup over pRRTC and 5.1x over VAMP-MR CBS and VAMP-MR RRT.The reported advantage over the second-best solve rate increased from 0% at 28 DOF to 16% at 35 DOF.Source: B. Multi-Robot Simulation Benchmarks · p. 6
  • The default cuRobo seeder uses a PRM that plans directly in composite space, which often fails as that search space grows exponentially.Source: B. Multi-Robot Simulation Benchmarks · p. 7
  • MR. POP raises cuRoboV2’s success rate from 4% to 72%; higher seeding iterations yield paths of lower cost, duration, and dimensionless jerk.The evaluation uses the 28-DOF four-Franka problems.Source: B. Multi-Robot Simulation Benchmarks · p. 7, Figure 5 · p. 7

C. Single-Robot Simulation Benchmarks & Ablations

Single-robot benchmarks isolate MR. POP’s tree search and AO-x optimization without roadmap construction. On the Fetch tasks, it achieves fast, consistent cost convergence, while initial-solution performance varies with problem difficulty.

C. Single-Robot Simulation Benchmarks & Ablations

  • For single-robot benchmarks, MR. POP bypasses roadmap construction and plans directly in configuration space, isolating its bidirectional tree search and AO-x layer.Source: C. Single-Robot Simulation Benchmarks… · p. 7
  • With a 20-second limit per problem, only MR. POP, pRRTC, and AORRTC achieved a 100% solve rate; MR. POP lagged pRRTC in this single-robot scenario.Here MR. POP functions as GPU-based RRT-Connect with added AO-x overhead.Source: C. Single-Robot Simulation Benchmarks… · p. 7
  • MR. POP found initial solutions faster on harder problems but lagged AORRTC on easier ones because of GPU launch and I/O overheads.Source: C. Single-Robot Simulation Benchmarks… · p. 7
  • MR. POP converges to lower-cost paths orders of magnitude faster than the other anytime a.s.a.o. planners, with a smaller path-cost interquartile range than AORRTC.These single-robot results isolate the AO-x design because no roadmap layer is used.Source: C. Single-Robot Simulation Benchmarks… · p. 7

D. Hardware Deployment

MR. POP reports stronger multi-robot planning performance and demonstrates deployment on a 14-DOF dual-arm system. The deployment also shows replanning around moving obstacles in real time.

D. Hardware Deployment

  • On a 14-DOF dual-arm system, MR. POP’s path optimality and seeding effectiveness transferred to hardware, with optimized replanning around obstacles in real time.The system paired a 7-DOF Flexiv Rizon 4s with a 7-DOF Kinova Gen 3.Source: D. Hardware Deployment · p. 7, Figure 7 · p. 8

VI. CONCLUSION AND FUTURE WORK

  • MR. POP was the only planner to consistently achieve a 100% solve rate and was faster than state-of-the-art a.s.a.o. planners on multi-robot systems up to 35-DOF.The reported result covers finding initial solutions and faster convergence to optimal solutions.Source: §VI · p. 8
  • MR. POP raised downstream motion optimizers’ success rates from 4% to 72% by providing high-quality, diverse seeds that help avoid local minima.The authors attribute the seeds’ diversity to iteratively shrinking cost bounds in the AO-x process.Source: §VI · p. 8
Loading 2609.30644v1…