CS Paper Radar

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

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

cs.RO ·submitted 2026-09-25 00:33 UTC · v1

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.

Closest papers

Nearest neighbours by meaning across the whole index.

PrismPlan: A Shared GPU Substrate for Motion Planning Across Paradigms

cs.RO ·2026-09-26 ·Hong Wu, ChaoXuan Liu, ShuJie Wang
code/data similarity 0.77
Abstract · 20 pages, 6 figures

GPU acceleration has made motion planning one to two orders of magnitude faster, but it has not made the three paradigms---sampling, search, and optimization---comparable to one another: every GPU-accelerated planner is built around a single paradigm, so comparing across libraries also compares their collision checkers. All three, however, bottleneck on the same GPU primitive: batched collision detection and the batched forward kinematics beneath it. PrismPlan builds that primitive once, as a shared substrate of per-sphere collision--kinematics device code that every planner consumes. Because they all execute the same device code, the backend is held fixed by construction and the paradigms can be compared head-to-head. We run six planners over 1800 MotionBenchMaker problems on three robots (7--14 DoF, one a dual-arm whole-body composite) at an equal 2s budget. On the 7-DoF Panda, sampling (pRRTC) is the most reliable paradigm at 98%, while parallel search (wPA*SE) follows within four points at a 3-4 times$ lower median latency, and the local optimizers trail well behind when made to solve from scratch. On the 14-DoF dual-arm composite, sampling still solves about 90% of feasible problems, while no search or optimization planner clears a third of them. Our open-source code is available at https://github.com/XiaoyubotMotionTeam/PrismPlan.

0.39

Contact-Rich Motion Planning via GPU-Parallel Mode Evaluation

cs.RO ·2026-09-18 ·Jiayun Li, Georgia Chalvatzaki
similarity 0.72
Abstract

Contact-rich motion planning (CRMP) is essential for robotic manipulation and locomotion, yet remains computationally challenging due to combinatorial contact decisions. Existing methods typically avoid broad evaluation of contact-mode sequences through search heuristics or optimization reformulations. We revisit broad evaluation in light of modern GPU hardware and introduce Contact-Mode Expansion with parallel Trajectory optimization (CoMET), which combines GPU-parallel trajectory evaluation with greedy contact-mode expansion. On planar pushing benchmarks, CoMET is competitive with optimization-based, sampling, and tree-search baselines in solution quality and planning time, matching the full-enumeration reference on nearly all instances with fewer evaluations and shorter planning times. Ablations suggest that much of the performance gain comes from the high-throughput trajectory evaluator. In bimanual nonprehensile manipulation, GPU-friendly local mode expansion achieves higher planning success than the tested adaptive tree search as the mode space grows. These results demonstrate that broad explicit mode evaluation provides a simple yet effective alternative for CRMP.

0.25

PATACON: GPU-Parallel Tangent-Bundle RRT-Connect for Constrained Motion Planning

cs.RO ·2026-10-09 ·Gahyun Oh, Junho An, Suhyun Jeon, Suhan Park
similarity 0.70
Abstract · 8 pages, 6 figures, 2 tables

Fast whole-body motion planning enables continuous replanning for humanoid robots in dynamic environments while satisfying collision avoidance and kinematic constraints. However, constrained motion planning incurs substantial computational cost due to repeated constraint projection in addition to collision checking and nearest-neighbor search. Recently, GPU-based massively parallel planners have been proposed to reduce computational cost. Nevertheless, these planners still steer in the ambient configuration space, so projecting candidates that deviate from the manifold remains a significant source of overhead, particularly in highly constrained, high-dimensional problems. In this work, we introduce PATACON, a GPU-parallel bidirectional planner that explores tangent space to exploit the local manifold geometry induced by known constraint functions. Experiments on dual-arm closed-chain and humanoid whole-body constrained planning tasks show that PATACON outperforms the prior work as configuration-space dimension and constraint codimension grow, achieving up to an 11.25 times speedup. These results suggest that GPU-parallel tangent-space exploration brings constrained whole-body motion planning closer to real-time performance.

0.28

Asymptotically Optimal Multi-Robot Task and Motion Planning

cs.RO ·2026-09-16 ·Thi Thuy Ngan Duong, Cheuk Tung Shadow Yiu, Rahul Shome, Yoonchang Sung
similarity 0.69
Abstract

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.

0.22

Arborist: Algorithm-Hardware Co-Design for Fast and Efficient Motion Planning

cs.AR ·2026-09-11 ·Yaotian Liu, Lingyi Huang, Zishen Wan, Bo Yuan, Cheng Tan +2 more
top venue similarity 0.69
Abstract · Accepted to the 59th IEEE/ACM International Symposium on Microarchitecture (MICRO 2026)

Real-time motion planning must execute under strict latency and energy constraints on resource-limited platforms. This paper presents Arborist, an algorithm-hardware co-design framework that accelerates Fast Marching Tree (FMT*) motion planning through synergistic algorithmic and architectural innovations. At the algorithm level, Arborist introduces safe multi-tree expansion with global competition management and cross-tree optimality checking to expose inter-tree parallelism while preserving path quality. At the architecture level, our proposed ArboristAccel integrates an Arborist Toolbox that provides hardware support for inter-tree parallelism; a KD-tree Subsystem for high-throughput near-neighbor search; a Parallel-Query Retrieval module that balances multi-bank memory accesses to alleviate system-level memory bandwidth bottlenecks; and a Look-ahead Planning Engine that exploits intra-tree parallelism while preserving path quality by in-order commit. Synthesized in 16 nm and operating at 500 MHz, ArboristAccel sustains more than 1000x speedup over CPU across all workloads, peaking at 2800x on 2D-Maze, and delivers geomean improvements of 8.8x speedup, 4.6x area efficiency, and 3.1x power efficiency over an FMT* ASIC baseline. The corresponding factors relative to a state-of-the-art RRT*-based MOPED accelerator are 8.6x, 1.0x, and 1.8x, at comparable path cost. To the best of our knowledge, ArboristAccel is the first dedicated hardware accelerator for FMT*-based motion planning.

0.48

RoboKit: Accelerating Parallel Differentiable Optimization for Robot Learning

cs.RO cs.AIcs.LG ·2026-11-15 ·Jianglong Ye, Xuanbin Peng, Conor Mc Gartoll, Changwei Jing, Lai Wei +3 more
publishedcode/data similarity 0.68
Abstract · Accepted to CoRL 2026. Project page: https://openrobokit.com/robokit

We present RoboKit, a high-performance, general-purpose toolkit for parallel differentiable optimization in robotics, built on three principles: (i) Performance and flexibility: GPU-parallel multi-seed solvers pair sampling with versatile optimizers, running 2-60$\times$ faster than task-specific baselines across seven tasks; (ii) Geometry, rendering and physics: hybrid and coarse-to-fine representations accelerate collision, differentiable rendering and simulation, optimizing 4096 grasps in 2.97 s; (iii) Integration with learning: costs are differentiable and simulation is parallel, so RoboKit both distills optimization into policies and trains RL; distilled policies run 9-240$\times$ faster at comparable accuracy, and RL reaches a GPU baseline's scores up to 2.1$\times$ sooner on the same simulator.

0.47

ST-pRRTC: Parallel Space-Time RRT-C with Adaptive Goal-Time Forests

cs.RO ·2026-09-24 ·Duo Zhang, Jintong Li, Junshan Huang, Jingjin Yu
similarity 0.68
Abstract

We propose ST-pRRTC, a GPU-parallel space- time RRT-Connect motion planner for problems with known obstacle trajectories and unspecified arrival time. Searching over many arrival times broadens temporal coverage but divides a finite planning budget among more backward trees. To address the challenge, ST-pRRTC builds a shared forward tree and an adaptive forest of backward goal-time trees. Its interval root formulation samples goal arrival times continuously and guarantees probabilistic completeness and asymptotic arrival- time optimality under the stated assumptions in a bounded time domain. The practical root recycling policy has no such guar- antees. It adapts a fixed number of backward trees, replacing later roots while retaining useful search progress. Experiments on three dynamic benchmarks show that both variants achieve lower mean first-solution times and earlier mean final arrivals than ST-RRT* and SI-RRT on problems solved by all compared methods. Further experiments demonstrate the benefit of recy- cling over broad arrival-time ranges. Real-robot demonstrations show root-recycling ST-pRRTC planning motions for a UR5e among moving Crazyflie quadrotors.

0.16

DynoFluxBench: Benchmarking Kinodynamic Space-Time Planners in Dynamic Environments

cs.RO ·2026-09-16 ·Franz Queißner, Andreas Orthey, Wolfgang Hönig
benchmark similarity 0.68
Abstract · 8 pages

Robots that leave structured, static environments must plan motions that are kinodynamically feasible and safe among moving obstacles. However, there are no dedicated benchmark frameworks that combine both aspects. To overcome this, we present DynoFluxBench, a framework to compare kinodynamic planners in known, dynamic environments with unbounded arrival time. To demonstrate its utility and establish strong baselines, we develop three dedicated planners, named ST-Db-RRT, ST-GBRRT, and KIST, that fuse kinodynamic and space-time methods, covering different kinodynamic search paradigms: ST-Db-RRT expands with randomly selected discontinuity-bounded motion primitives using trajectory optimization, whereas KIST and ST-GBRRT maintain a kinodynamically feasible tree with different heuristic guidance. We analyze the probabilistic completeness guarantees of those new planners in dynamic environments. Finally, we evaluate ST-Db-RRT, ST-GBRRT, and KIST using DynoFluxBench, showing that ST-Db-RRT reaches a first solution up to 32 times faster, while KIST and ST-GBRRT remain valuable where trajectory optimization is fragile. Videos and further analysis can be found at https://dynofluxbench.github.io/dynofluxbench/.

0.32