MR. POP: Multi-Robot Parallel Optimizing Planner for Almost-Surely Asymptotically Optimal Planning
Authors: Chih H. Huang, Roy Xing, Brian Plancher, Zachary Kingston
Organizations: Columbia College, Columbia University · Department of Computer Science, Dartmouth College · Department of Computer Science, Purdue University
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.
Figures & tables
Figure 2: Overview of mr. pop . (a) The gpu grid is divided evenly between the number of robots for roadmap construction. (b) mr. pop builds search trees over the tensor product of each individual robot’s roadmap, and every gpu block carries out its own d rrt or ao -x + d rrt iteration. (c) For the primitive collision checking operations, 4 threads are assigned to each discretized motion for collision checking against the robot’s coarse spherization. For fine-grained collision checking, the threads are reassigned between the discretized motions based on the coarse results and the estimated workload.
Figure 3: Benchmark results for the 28 d o f four Franka bin packing problems. (a) The bin packing scene provides 50 manipulation problems. (b) Initial solution time and solve rate. Only mr. pop and p rrtc achieved a 100% solve rate, and among all planners with a solve rate over 60%, mr. pop averages a 2.5x speedup over p rrtc , a 1.9x speedup against vamp - mr cbs , and a 4.3x speedup against vamp - mr rrt . (c) Optimization time vs median path cost and interquartile range. mr. pop converges to solutions of lower cost faster than ao-d rrt while having a lower interquartile range, indicating a more consistent performance.
Figure 4: Benchmark results for the 35 d o f five Franka shelf reaching problems. (a) The shelf reaching scene provides 50 manipulation problems. (b) Initial solution time and solve rate. Only mr. pop achieved a 100% solve rate, and among all planners with a solve rate of at least 60%, mr. pop averages a 3.1x speedup over p rrtc and a 5.1x speedup against vamp - mr cbs and vamp - mr rrt . (c) Optimization time vs median path cost and interquartile range. mr. pop converges to solutions of lower cost faster than ao-d rrt while having a lower interquartile range, indicating a more consistent performance.
Figure 5: mr. pop seeding iteration vs. cuRoboV2 optimizer outcome tested on the 28 d o f four Franka arm problems. As mr. pop ’s iteration increased, the cuRoboV2 optimizer succeeds more often while producing paths of lower cost, duration, and dimensionless jerk.
Figure 6: Benchmark problems and results for the 8 d o f Fetch on the MotionBenchMaker dataset [ 2 ] . (a) The MotionBenchMaker scenes provide diverse manipulation problems for the 8 d o f Fetch, including counter-top manipulation, accessing shelves, and constrained reaching; Fetch has 7 scenes with 100 problems each. Green and red denote the start and goal configurations per sample problem, respectively. (b) Among all planners, only mr. pop , p rrtc , and aorrtc achieved a 100% solve rate. (c) mr. pop converges to low-cost solutions orders of magnitude faster compared to other a.s.a.o. planners, while also having a smaller interquartile range which demonstrates more consistent performance.
Figure 7: mr. pop replanning for a 14 d o f dual arm amid moving obstacles.
We present AO-ARC, an anytime multi-robot motion planning (MRMP) method that achieves initial solution times on par with state-of-the-art MRMP feasibility solvers while converging faster and more reliably than existing anytime MRMP methods as the number of robots increases. AO-ARC adapts the AO-x meta-algorithm for converting feasibility solvers into anytime algorithms by iteratively calling the original ARC method on bounded MRMP instances under a makespan cost metric. This exploits the adaptive (de)coupling of ARC while maintaining the consistent cost bound across robot (de)compositions needed for AO-x. We provide theoretical analysis proving the asymptotic optimality properties of AO- ARC and conduct empirical evaluation on a set of 2D scenarios with different levels of coordination complexity and a 3D manipulator scenario representative of real-world applications.
James D. Motes, Marco Morales, Nancy M. Amato
Parasol Lab, School of Computing and Data Science, University of Illinois at Urbana Champaign, Champaign, IL, 61820 USA · Department of Computer Science at Instituto Tecnológico Autónomo de México (ITAM), Mexico City, México
Multi-robot task and motion planning (MR-TAMP) requires jointly reasoning about discrete task decisions and continuous collision-free motions of multiple interacting robots. Although asymptotically optimal algorithms have been developed for task and motion planning, extending these guarantees to the multi-robot setting introduces an important challenge: different task transitions may involve different subsets of robots and therefore impose constraints of different dimensions on the composite configuration space. Consequently, an asymptotically optimal planner must not only optimize motion within each task mode, but also ensure sufficient exploration of the different types of transitions connecting them. We characterize this transition structure and establish sufficient conditions for global asymptotic optimality in MR-TAMP, requiring persistent coverage of relevant transitions and asymptotically improving motion planning within connected feasible regions. Based on these conditions, we develop an efficient asymptotically optimal MR-TAMP algorithm that combines evolving individual-robot roadmaps with implicit tensor-product search, avoiding explicit construction of the composite roadmap. The planner further employs conditional transition sampling, lazy collision checking, and mode- and solution-level guidance to improve finite-time planning efficiency while retaining persistent exploration. The resulting framework provides asymptotic optimality guarantees for multi-robot manipulation while efficiently exploiting the structure of individual-robot motion planning.
Sampling-based motion planners have been shown to be effective for systems with complex kinodynamic constraints and high dimensionality. However, these algorithms struggle to achieve real-time performance, leading to recent efforts to parallelize planning. While GPU-accelerated planners have achieved significant speedups, existing approaches require specialized CUDA programming that limits accessibility and portability. We present Parallel Asymptotically Optimal Kinodynamic RRT (PAKR), a massively parallel kinodynamic planner leveraging JAX and the XLA compiler to achieve GPU acceleration through standard Python tooling. By combining our parallel planner with the AO-x meta-algorithm, we achieve asymptotic optimality through fast iterative replanning. We provide a theoretical analysis of probabilistic completeness, analyze the effects of batch size and branching factor on convergence, and demonstrate scalability to complex dynamics using the MuJoCo-XLA simulator. Experiments show competitive runtimes with state-of-the-art GPU planners and superior solution quality.