PATACON: GPU-Parallel Tangent-Bundle RRT-Connect for Constrained Motion Planning
Authors: Gahyun Oh, Junho An, Suhyun Jeon, Suhan Park
Organizations: Department of Robotics, Kwangwoon University, Seoul, Republic of Korea. · Department of Intelligence and Information, Graduate School of Convergence Science and Technology, Seoul National University, Republic of Korea.
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.
Figures & tables
Fig. 1: Overview of PATACON, a GPU-parallel bidirectional constrained planner. Task-specific constraints define a constraint manifold, and CUDA blocks select local tangent spaces from shared tree-specific banks to explore different regions of the manifold concurrently. Candidate motion segments generated in each tangent space are projected and validated on the manifold before insertion into the trees.
Fig. 2: GPU mapping of PATACON. CUDA blocks concurrently explore local tangent-space regions, while candidate edges generated by each EXTEND are distributed across cooperative thread groups for parallel validation.
Fig. 3: Tangent-Space EXTEND and CONNECT. EXTEND generates multiple candidates along a common tangent direction, while CONNECT repeatedly applies EXTEND toward a fixed target in the opposite tree.
Fig. 4: Experimental setups used for constrained motion-planning benchmarks. Start and goal configurations are shown for the Franka Panda, dual Franka, fixed- and mobile-base FFW-SG2, and Unitree G1.
Robot
Constraint
Planner
Time (ms)
Succ.
Franka
OR(2D)
TB-RRT
570.58 ± 446.23
98
McVAMP
5.20 ± 3.37
100
cpRRTC
0.52 ± 0.06
100
PATACON
1.65 ± 0.10
100
Dual
BK(6D)
McVAMP
44.60 ± 23.69
100
cpRRTC
3.94 ± 0.39
100
TABLE I: Planning performance over 100 trials. Time: mean ± std. over successful trials.
Fig. 5: Cumulative planning success across constrained planning benchmarks. Each curve shows the percentage of 100 randomly sampled start–goal problems solved within the corresponding planning time. Planning time is shown on a logarithmic scale.
Variant
Time (ms) ↓
Success (%) ↑
cpRRTC
242.48 ± 19.47
100
+TGS
339.78 ± 117.54
100
+TGMP
288.43 ± 123.17
100
PATACON
152.95 ± 44.29
100
TABLE II: Cumulative ablation on the G1 whole-body benchmark.
Fig. 6: Anytime optimization behavior of AO-PATACON on the G1 whole-body benchmark over 10 independent runs. The upper plot shows the success rate over computation time, and the lower plot shows the median best-so-far path cost during continued optimization.
Many robot planning tasks require satisfaction of one or more constraints throughout the entire trajectory. For geometric constraints, manifold-constrained motion planning algorithms are capable of planning collision-free path between start and goal configurations on the constraint submanifolds specified by task. Current state-of-the-art methods can take tens of seconds to solve these tasks for complex systems such as humanoid robots, making real-world use impractical, especially in dynamic settings. Inspired by recent advances in hardware accelerated motion planning, we present a CPU SIMD-accelerated manifold-constrained motion planner that revisits projection-based constraint satisfaction through the lens of parallelization. By transforming relevant components into parallelizable structures, we use SIMD parallelism to plan constraint satisfying solutions. Our approach achieves up to 100-1000x speed-ups over the state-of-the-art, making real-time constrained motion planning feasible for the first time. We demonstrate our planner on a real humanoid robot and show real-time whole-body quasi-static plan generation. Our work is available at https://commalab.org/papers/mcvamp/.
Shrutheesh R Iyer, I-Chia Chang, Andrew Z. Liu +2
Department of Computer Science, Purdue University · School of Mechanical Engineering, Purdue University
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.
Jiayun Li, Georgia Chalvatzaki
PEARL Lab, Department of Computer Science, TU Darmstadt, Darmstadt, Germany · Hessian.AI, Darmstadt, Germany · Robotics Institute Germany (RIG), Germany
We present GASP, a GPU-Accelerated Safe Planner for real-time, collision-aware joint-space motion generation in known environments. GASP combines a clamped B-spline trajectory parameterization with a convolutional residual neural network that predicts the free interior control points, while analytically inserted boundary control points enforce initial and final derivative constraints for collision-aware planning under non-stationary conditions. A conditional variational autoencoder samples multiple trajectory candidates, which are decoded and validated in parallel on the GPU, yielding a batched planner for collision-aware coupled joint-space motion with near-millisecond inference. We validate GASP as an online motion-generation module, where it achieves analytical-level success rates with high collision-aware feasibility and substantially reduces inference time relative to GPU-based trajectory optimization. We further deploy GASP as a reinforcement-learning reset planner in competitive robotic table tennis, matching the baseline return rate while roughly halving training-time collisions.