PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Gahyun Oh, Junho An, Suhyun Jeon, Suhan Park

arXiv:2610.13195v1cs.RO

TL;DR

Repeated projection and other search costs make constrained planning computationally demanding, while GPU planners still steer through ambient configuration space. PATACON uses GPU-parallel tangent-space exploration and multi-edge expansion; across benchmarks, its advantage grows with dimension and constraint restrictiveness, reaching 11.25× speedup with 100% success.

  • Problem

    Repeated projection adds substantial cost to constrained planning, and existing GPU planners still steer in ambient space rather than exploiting the constraint manifold.

    Source: §I · p. 1

  • Method

    PATACON combines tangent-space-guided GPU-parallel tree expansion with concurrent validation of multiple candidate edges.

    Source: §I · pp. 1–2

  • Results

    Across eight benchmarks, PATACON's advantages increase with configuration-space dimension and constraint restrictiveness, reaching 11.25× speedup with 100% success.

    Source: §I · p. 2

  • Takeaways & Limitations

    Experiments support combining local tangent-space guidance with massively parallel GPU execution for high-dimensional constrained motion planning.

    Source: §VI · p. 8

Abstract

from arXiv · show

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.

I. INTRODUCTION

Constrained planning for dual-arm and humanoid robots must satisfy kinematic relationships, joint limits, and collision avoidance, while repeated projection adds to planning cost. PATACON replaces ambient-space steering with GPU-parallel tangent-space exploration and batches candidate edges to amortize tangent-space overhead.

I. INTRODUCTION

  • Repeated constraint projection adds computational overhead to collision checking and nearest-neighbor search, making low planning latency important for repeated replanning as tasks or environments change.Dual-arm closed-chain and humanoid whole-body tasks must maintain kinematic relationships while respecting joint limits and avoiding collisions.Source: §I · p. 1
  • Unlike ambient-space GPU planners, PATACON explores tangent directions before projection and validates each candidate before insertion, so every inserted node is feasible.Ambient-space targets may make little progress along the manifold after projection, while tangent-space candidates are more likely to remain within constraint tolerance.Source: §I · p. 1

II. RELATED WORK

  • PATACON amortizes tangent-space preprocessing and bookkeeping by generating multiple candidate edges from one sample and nearest-neighbor query for concurrent validation.Existing GPU parallelism lowers projection cost, but ambient-space steering still produces off-manifold motions that must be projected.Source: §I · p. 2, §II · p. 2

I. INTRODUCTION

  • PATACON combines tangent-space-guided GPU extension, shared tangent-space banks, and speculative multi-edge expansion; across eight benchmarks, its advantage grows with dimension and constraint restrictiveness, reaching 11.25× speedup with 100% success.The planner generates consecutive candidate edges from one sample and nearest-neighbor query, validates them concurrently, and inserts the longest valid prefix.Source: §I · p. 2

II. RELATED WORK

  • Constrained-planning approaches include projection methods, local charts, and tangent spaces, while learning-based methods require offline data generation and training.The paper contrasts these methods with acceleration directly from the given constraint functions.Source: §II · p. 2

III. PROBLEM DEFINITION

The planning problem is to find a continuous path between feasible start and goal configurations while satisfying task-dependent kinematic constraints and collision-avoidance requirements.

III. PROBLEM DEFINITION

  • Task-dependent differentiable nonlinear equality constraints define a lower-dimensional manifold within the joint-feasible configuration space.At regular configurations, the Jacobian is assumed to have full row rank m, giving local manifold dimension d = n − m.Source: §III · p. 2
  • The planner uses an orthonormal basis of the constraint Jacobian's null space as a local representation of the manifold's tangent space.The basis N(q) satisfies Jh(q)N(q) = 0 and N(q)⊤N(q) = Id.Source: §III · p. 2
  • A valid path connects feasible start and goal configurations, and every configuration along it must satisfy kinematic constraints, joint limits, and collision avoidance.The collision-free set excludes both self-collision and environmental collision.Source: §III · p. 2

IV. GPU-PARALLEL TANGENT-BUNDLE RRT-CONNECT

PATACON combines tangent-guided sampling with multi-edge expansion to run bidirectional tree growth in parallel on the GPU. Tangent-space banks let CUDA blocks explore different local regions while candidate edges are projected and validated.

IV. GPU-PARALLEL TANGENT-BUNDLE RRT-CONNECT

  • The TGS–TGMP pipeline expands a selected tree, projects and validates candidate edges in parallel, and inserts only the longest consecutively valid prefix.After a successful extension, a target-directed CONNECT attempts to join the opposite tree.Source: §IV · p. 2

A. Tangent-Guided Sampling for Concurrent Exploration

  • Tangent-Guided Sampling selects a local tangent region, samples within it, and performs nearest-neighbor search among nodes associated with that region.Tangent-space guidance favors directions consistent with local constraint geometry, while tangent-local nearest-neighbor search and tangent-space management add computation.Source: A. Tangent-Guided Sampling for… · p. 3
  • Separate start- and goal-tree tangent-space banks are shared across CUDA blocks, allowing blocks to select regions dynamically rather than being assigned fixed tangent spaces.A tangent space becomes selectable after its root node and associated data are initialized.Source: A. Tangent-Guided Sampling for… · p. 3
  • When sampling from a newly created tangent space, backtracking prevention reverses displacements that point toward previously explored regions, restricting samples to the forward half-space.The forward direction is obtained by projecting the displacement between the new and parent tangent-space roots onto the new tangent space.Source: A. Tangent-Guided Sampling for… · p. 3

B. Tangent-Guided Multi-Edge Projection

Tangent-Guided Multi-Edge Projection reuses one sampling and nearest-neighbor result to generate consecutive candidates along a shared tangent direction. The candidates are projected and validated before a valid prefix is added to the tree.

B. Tangent-Guided Multi-Edge Projection

  • TGMP reuses the selected tangent-space context and expansion direction to generate multiple consecutive candidate edges in one EXTEND call.This avoids repeating sampling and nearest-neighbor operations for each edge.Source: B. Tangent-Guided Multi-Edge Projection · p. 3
  • Candidates advance in ordered steps of size ξ along a common tangent-space direction, up to K candidates and the configured maximum Kmax.Candidate generation stops when the tangent residual exceeds its threshold, which signals that the local approximation should be renewed but does not itself establish feasibility.Source: B. Tangent-Guided Multi-Edge Projection · pp. 3–4
  • TGMP defines the multi-step expansion independently of whether candidate-edge validation runs sequentially or concurrently on the GPU.The +TGMP ablation processes generated edges sequentially, while full PATACON validates them concurrently.Source: B. Tangent-Guided Multi-Edge Projection · p. 4
  • Projection and collision checking determine the valid candidate prefix; EXTEND inserts that prefix and returns trapped when no candidate is valid.The full-batch case can trigger creation of a new tangent space when the final candidate exceeds the tangent-residual threshold.Source: B. Tangent-Guided Multi-Edge Projection · p. 4

C. GPU-Parallel Edge Projection and Validation

PATACON processes multiple candidate edges concurrently on the GPU, while projecting each edge’s waypoints sequentially. Tree insertion follows the original candidate order and accepts only the longest valid prefix.

C. GPU-Parallel Edge Projection and Validation

  • Multiple candidate edges are projected and validated concurrently on the GPU, but waypoint projections within each edge remain sequential.Waypoints proceed from the edge source, with each projection following the preceding projected waypoint.Source: C. GPU-Parallel Edge Projection and… · p. 4
  • An edge is valid only if its sequential waypoint projections converge within tolerance and satisfy joint-limit and collision constraints.CONNECT also applies a target-progress condition.Source: C. GPU-Parallel Edge Projection and… · p. 4
  • Candidate results are consumed in TGMP order, and only the longest consecutively valid prefix is inserted; an invalid first edge returns TRAPPED.Otherwise, EXTEND returns ADVANCED with the final inserted configuration.Source: C. GPU-Parallel Edge Projection and… · p. 4
  • A tangent space is renewed only after full-batch acceptance; a nonempty valid prefix is sufficient to trigger CONNECT.The boundary node becomes the new tangent-space root when renewal occurs.Source: C. GPU-Parallel Edge Projection and… · p. 5

D. Target-Directed Connection and Bridge Validation

After an exploratory extension, PATACON repeatedly extends toward a fixed configuration in the opposite tree. It validates a final bridge before declaring the trees connected.

D. Target-Directed Connection and Bridge Validation

  • CONNECT repeatedly extends the growing tree toward a fixed target selected from the opposite tree, which remains unexpanded during that attempt.The target search considers all configurations in the opposite tree.Source: D. Target-Directed Connection and… · p. 5
  • At each CONNECT step, the displacement toward the target is projected onto the tangent vector space and passed to the same TGMP-based EXTEND procedure.This generates a multi-step candidate sequence whose edges undergo GPU-parallel projection and validation.Source: D. Target-Directed Connection and… · p. 5
  • The trees connect only when the current configuration is within ϵ_con of the target and the final bridge passes validation.On success, PATACON traces the path through both trees and the bridge.Source: D. Target-Directed Connection and… · p. 5
  • Candidate edges must make at least the required progress toward the target; a failing edge ends valid-prefix insertion even if projection and collision checks pass.The minimum required reduction in target distance is ϵ_prog > 0.Source: D. Target-Directed Connection and… · p. 5

V. EXPERIMENTS

The experiments assess planning performance across constraint regimes, the cumulative effects of TGS and TGMP, and solution-quality improvement under a shared anytime optimization framework.

V. EXPERIMENTS

  • The first experiment compares planner performance across increasingly restrictive constraints and higher-dimensional configuration spaces.This evaluates behavior across distinct planning regimes.Source: §V · p. 5
  • A cumulative ablation progressively adds Tangent-Guided Sampling (TGS) and Tangent-Guided Multi-Edge Projection (TGMP) to cpRRTC.Source: §V · p. 5
  • A final experiment evaluates solution-quality improvement under a common anytime optimization framework.Source: §V · p. 5

A. Experimental Environment

The benchmarks span several robot models and constraint regimes, with shared start–goal pairs and planning conditions across planners. PATACON’s latency advantage is most pronounced in higher-dimensional, more restrictive settings.

A. Experimental Environment

  • All planners share each regime’s robot model, environment, start–goal pairs, joint limits, constraint definitions, feasibility tolerances, and timeout; 100 feasible pairs are sampled per regime.Source: A. Experimental Environment · p. 6
  • Timing uses an RTX 5090 workstation and excludes one-time initialization while including computations required for each planning query.Unless otherwise specified, PATACON uses N_blk = 512, K_max = 4, ϵ_M = 0.1, and edge-discretization resolution G = 16.Source: A. Experimental Environment · p. 6
  • The benchmarks cover Franka Panda (7-DoF), dual Franka (14-DoF), fixed-base FFW-SG2 (15-DoF), mobile-base FFW-SG2 (18-DoF), and Unitree G1 (35-DoF).The setups show start and goal configurations for these robot models.Source: A. Experimental Environment · p. 6, Figure 4 · p. 6

B. Planning Performance across Constraint Regimes

  • TB-RRT is evaluated only on single-arm Franka, and McVAMP only on Franka and dual Franka, because of their substantially higher planning times on larger problems.The higher-dimensional comparisons therefore focus on cpRRTC and PATACON.Source: B. Planning Performance across… · p. 6
  • PATACON’s latency advantage is consistent on higher-dimensional FFW-SG2 and Unitree G1 benchmarks, and grows under more restrictive constraints.On fixed-base FFW-SG2 with bimanual-pose and axis constraints, equivalent throughput is approximately 38.5 solutions per second for PATACON versus 3.4 for cpRRTC.Source: B. Planning Performance across… · p. 6

C. Ablation Study

The ablation finds that tangent-guided multi-edge expansion works best when paired with concurrent GPU projection and validation and exploration that avoids backtracking. In the anytime evaluation, AO-PATACON reaches full success early on G1 and continues refining path quality within the remaining budget.

C. Ablation Study

  • PATACON projects and validates multiple candidate edges concurrently on the GPU, whereas +TGMP processes candidate edges sequentially within an EXTEND call.Both approaches use tangent-guided multi-edge expansion; PATACON also prevents backtracking toward previously explored tangent-space regions.Source: C. Ablation Study · p. 6
  • TGS alone increases planning time because tangent-space construction and maintenance add overhead, while TGMP amortizes that cost by reusing tangent-space context across consecutive expansions.TGS also provides geometry-aware exploration and a restricted nearest-neighbor search.Source: C. Ablation Study · p. 6
  • Combining tangent-guided multi-edge expansion with concurrent GPU edge processing and backtracking prevention reduces planning time and makes tangent-guided exploration most effective.Backtracking prevention steers expansion away from the parent tangent-space region toward unexplored manifold regions.Source: C. Ablation Study · p. 7

D. Anytime Planning Performance

  • AO-PATACON uses each feasible solution's cost as an upper bound, reinitializes the trees, and restarts the search when it finds a lower-cost solution.The repeated restart process runs throughout the 10-s optimization budget.Source: D. Anytime Planning Performance · p. 7
  • On G1, AO-PATACON reaches 100% success early and continues improving incumbent path quality with the remaining optimization budget.Best-so-far path cost falls stepwise, with the largest reductions shortly after first feasible solutions and smaller gains later.Source: D. Anytime Planning Performance · pp. 7–8

VI. CONCLUSION

PATACON combines tangent-space-guided exploration with GPU-parallel tree expansion and validation for constrained motion planning. Across dual-arm and whole-body tasks, it becomes increasingly advantageous as constraints grow more restrictive and planning becomes more challenging.

  • PATACON integrates tangent-space-guided exploration with GPU-parallel tree expansion and validation to explore constrained configuration spaces efficiently.Source: §VI · p. 8
  • Experiments across dual-arm and whole-body planning problems show PATACON becomes increasingly advantageous as constraints become more restrictive and planning grows more challenging.Source: §VI · p. 8
  • The results demonstrate the effectiveness of combining local tangent-space guidance with massively parallel GPU execution for high-dimensional constrained motion planning.Source: §VI · p. 8

APPENDIX CORRECTION OF BENCHMARK RESULTS

Re-evaluation without concurrent GPU workloads corrected cpRRTC planning times in two benchmarks and showed lower mean planning times than PATACON in both.

Loading 2610.13195v1…