Mr Pop speeds up multi-robot path planning with GPU parallelism
MR. POP: Multi-Robot Parallel Optimizing Planner for Almost-Surely Asymptotically Optimal Planning
Robotics
Summary
Planning paths for multiple robots to move without collisions is a tough challenge, especially when trying to find the best overall routes. The authors introduce MR. POP, a system that uses powerful graphics processors (GPUs) to run many calculations at once for planning these paths. This approach helps it solve planning problems faster and with higher success than previous methods, even as the complexity grows. Because of this, robots get better starting paths for further motion improvements, helping to avoid getting stuck on poor routes.
What this means in practice
- •For robotics engineers: Plan coordinated collision-free paths for teams of robots efficiently using GPU-accelerated computations.
- •For manufacturing automation teams: Generate reliable and diverse robot movement plans that improve downstream optimization and reduce production delays in factories.
Authors
Chih H. Huang, Roy Xing, Brian Plancher, Zachary Kingston
Abstract
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.