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.
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