Source-linked AI summary
ST-pRRTC: Parallel Space-Time RRT-C with Adaptive Goal-Time Forests
Duo Zhang, Jintong Li, Junshan Huang, Jingjin Yu
TL;DR
For known moving-obstacle trajectories, planning routes and timing across candidate arrival times divides finite search resources among backward trees. ST-pRRTC combines a shared forward tree with adaptive goal-time trees, and experiments report improved planning-time and arrival-time outcomes over ST-RRT* and SI-RRT on commonly solved problems.
Problem
With known obstacle trajectories, a configuration may be free at one time and blocked at another, so planning must reason jointly over routes and timing.
Source: §I · p. 1Method
ST-pRRTC uses a shared forward tree and adaptive backward goal-time forest, with continuous interval-root sampling or practical root recycling.
Source: §I · p. 1Results
Both ST-pRRTC 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.
Source: §I · p. 1Takeaways & Limitations
Root recycling shows empirical benefit over broad arrival-time ranges with limited tree capacity, while UR5e demonstrations show execution among moving Crazyflies.
Source: §I · p. 1Interval-root guarantees apply under stated assumptions in a bounded arrival-time domain; practical root recycling has no such guarantees.
Source: §I · p. 1
Abstract
from arXiv · showhide
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.
I. INTRODUCTION
With known moving-obstacle trajectories, motion planning must coordinate routes and timing, while searching many arrival times divides finite resources among backward trees. ST-pRRTC addresses this tradeoff with a shared forward tree and adaptive goal-time forest, including continuous interval-root sampling and practical root recycling.
I. INTRODUCTION
- Known obstacle trajectories still require joint reasoning over routes and timing because a configuration may be free at one time and blocked at another.Delays can postpone subsequent tasks, making short execution times essential.Source: §I · p. 1
II. RELATED WORK
I. INTRODUCTION
- ST-pRRTC couples a shared forward tree with a backward goal-time forest, exploring routes and timing through batched expansion and dynamic collision checking.It is proposed for minimizing arrival time with known obstacle trajectories.Source: §I · p. 1
- Interval root samples arrival times continuously within persistent backward-tree groups and has probabilistic-completeness and asymptotic arrival-time-optimality guarantees under stated assumptions in a bounded domain.The practical root-recycling policy reuses a fixed number of backward-tree slots, replacing roots later than the best known arrival while retaining useful search progress; it has no such guarantees.Source: §I · p. 1
- Across Disc2D, Panda-spheres, and tabletop rearrangement, both ST-pRRTC variants achieve lower mean first-solution times and earlier mean final arrivals than ST-RRT* and SI-RRT on commonly solved problems.Root recycling also shows empirical benefit over broad arrival-time ranges with limited tree capacity.Source: §I · p. 1
III. PROBLEM FORMULATION
The problem is to find a collision-free trajectory through ordered goals in a bounded horizon despite time-varying obstacles, while minimizing arrival time.
III. PROBLEM FORMULATION
- The robot must reach each goal at a time when it is collision-free, although moving obstacles may repeatedly block and clear that goal.The configuration space is combined with the planning horizon to define the space–time search domain.Source: §III · p. 2
- A feasible trajectory reaches each goal in order, may wait, and remains within the bounded planning horizon while minimizing its final arrival time.The model assumes known, deterministic obstacle trajectories and open-loop planning.Source: §III · p. 2
- For multiple goals, the paper analyzes successive single-goal queries, resetting local time and shifting obstacle trajectories to the query’s absolute start time.The theoretical guarantees concern each single-goal query.Source: §III · p. 2
A. GPU-Parallel Space–Time Forest
ST-pRRTC searches space and time with a shared forward tree and backward goal-time trees, allocating backward search through persistent groups or recycled slots.
A. GPU-Parallel Space–Time Forest
- The planner concurrently expands a shared forward tree and a backward forest, publishing improved solutions ranked first by arrival time and then by path length.The forward tree starts at the robot’s initial state; backward trees start at candidate goal-time states.Source: A. GPU-Parallel Space–Time Forest · p. 3
- The variants use N backward-search groups differently: interval root samples continuously within assigned intervals, while root recycling reuses concrete slots whose root times exceed the incumbent arrival.Both adjust allocation when the incumbent arrival time decreases.Source: A. GPU-Parallel Space–Time Forest · p. 3
B. Interval Root
- Interval root partitions times before the incumbent into uniform intervals and guided windows; the uniform sampling component preserves proposal support across the interval.Guided windows come from collision-free grid-time checks and guide sampling, but each sampled root is collision-checked independently.Source: B. Interval Root · p. 3
- A collision-free sampled goal-time state can act as a virtual root, becoming a concrete backward tree on its first successful extension; workers may instead expand existing active trees.A worker selects a group uniformly and uses a virtual root when the group has no active tree or with probability pnew.Source: B. Interval Root · p. 3
- Directed nearest-neighbor search rejects time-reversed or speed-infeasible extensions, while steering and bridge checks enforce time direction, speed limits, and collision freedom.Valid bridge candidates are ranked by arrival time and then space–time distance.Source: B. Interval Root · pp. 3–4
C. Theoretical Properties
Under stated sampling, storage, scheduling, and collision-validation assumptions, interval root is probabilistically complete and asymptotically arrival-time optimal for robust trajectories within the bounded horizon.
C. Theoretical Properties
- With unlimited sampling and storage, fair worker scheduling, and sound collision validation, interval root is probabilistically complete for robust trajectories arriving before H.The validation assumption requires acceptance of sufficiently short collision-free edges.Source: C. Theoretical Properties · p. 4
- The proof sketch covers a robust reference trajectory with a finite sequence of neighborhoods, using the uniform root component and conditional state sampling to give each neighborhood positive sampling probability.A retained forward vertex provides a reachable nearest-neighbor candidate whose sufficiently small extension stays in the free tube.Source: C. Theoretical Properties · p. 4
- Fresh roots before a target arrival have positive probability of extending into its terminal free tube and forming a valid bridge; consequently the incumbent converges to the optimal arrival time.The argument takes b=H for completeness and a countable sequence b approaching T* for almost-sure arrival-time optimality; path length is only a tie-breaker.Source: C. Theoretical Properties · p. 4
V. PRACTICAL ROOT RECYCLING
Root recycling limits each query to a fixed number of backward-tree slots, reusing later-rooted slots as the incumbent arrival improves. Unlike interval roots, it has no general completeness or arrival-time optimality guarantee.
V. PRACTICAL ROOT RECYCLING
- Root recycling bounds each single-goal query to N concrete-tree slots, concentrating expansions on retained trees and reusing slots rooted later than the incumbent.The forward tree and backward roots below the incumbent retain their nodes and timestamps.Source: §V · p. 4
- When the incumbent improves, roots at or after its arrival are deactivated; later-rooted slots may receive collision-free replacement roots before that arrival.The old tree is discarded, while the forward tree and roots earlier than the incumbent keep their search progress; a slot stays inactive if no valid replacement is found.Source: §V · p. 4
- Root recycling uses configuration-distance nearest neighbors and maximum-speed edges; bridges can use available time slack while respecting speed limits and time direction.Edges and bridges are collision-checked at absolute times.Source: §V · p. 4
- Root recycling has no general completeness or arrival-time optimality guarantee because initial roots can miss reachable arrival times and recycling requires an incumbent improvement.Under the first-order model, alternating maximum-speed motions can approximate slower movement or waiting within the clearance of a robust reference trajectory.Source: §V · pp. 4–5
A. Simulation Protocol
The simulation study compares ST-pRRTC variants with ST-RRT* and SI-RRT across Disc2D, Panda-spheres, and tabletop rearrangement benchmarks. It specifies the benchmark sets, planning budgets, and timing protocol.
A. Simulation Protocol
- The main study compares Root recycling, Interval root, ST-RRT*, and SI-RRT, with No recycling as the allocation ablation.SI-RRT preserves its safe-interval construction, bidirectional scheduling, and first-solution behavior; ST-RRT* uses its OMPL implementation.Source: A. Simulation Protocol · p. 5
- The study uses 300 procedurally generated Disc2D scenes, 300 Panda scenes with moving spheres, and all 962 tabletop transitions.For tabletop, one UR5e is replanned against the prescribed motion of the other arm; the planning horizon is twice the transition duration.Source: A. Simulation Protocol · p. 5
- The full-dataset comparison uses 0.5, 1, 3, and 5 s planning budgets, with ST-pRRTC requesting 64 backward roots or groups and batching 1024 new configurations.Root recycling and No recycling retain the original local extension rule; Interval root uses the space-time core with pnew = 0.05 and pguided = 0.95.Source: A. Simulation Protocol · p. 5
- ST-pRRTC GPU-kernel time is measured in repeated queries after scene setup is amortized, whereas CPU baselines are timed within planning calls after scene construction.Trials ran sequentially on an NVIDIA RTX 4090 and Intel Core i9-14900KF; CPU baselines were single-threaded.Source: A. Simulation Protocol · p. 5
B. Main Comparison
Across all three benchmarks and tested budgets, both ST-pRRTC variants have lower mean first-solution compute times and earlier mean final arrivals than ST-RRT* and SI-RRT on common-success sets. The figures distinguish all-scene first-solution success from arrival-time comparisons on those common-success sets.
B. Main Comparison
- Fig. 5 shows cumulative first-solution success across all scenes, with lines averaging four planning budgets and shading spanning their minimum and maximum.Fig. 6 compares first and final arrival means and 95% bootstrap intervals on common-success sets recomputed for each budget.Source: B. Main Comparison · p. 5, Figure 5 · p. 6, Figure 6 · p. 6
- Across all three benchmarks and tested budgets, both ST-pRRTC variants achieve lower mean first-solution compute times and earlier mean final arrivals than ST-RRT* and SI-RRT on common-success sets.Root recycling also achieves the highest tabletop success at every budget while remaining competitive on Disc2D and Panda-spheres.Source: B. Main Comparison · p. 6
- The comparison supports Root recycling as an effective finite-budget planner, though its comparison with Interval root reflects both allocation and expansion rules.Source: B. Main Comparison · p. 6
C. Seed Sensitivity
Across three seeds, both ST-pRRTC variants retain lower mean first-solution compute times and earlier mean final arrivals than the CPU baselines at 5 s. In broad goal-time ranges, root recycling preserves early arrivals with sparse roots, while sufficiently dense coverage can yield similar arrival-time performance without recycling.
C. Seed Sensitivity
- Across three seeds at 5 s, both ST-pRRTC variants have lower mean first-solution compute times and earlier mean final arrivals than both CPU baselines, with stable success rates.Seed sensitivity uses 100 independently selected problems per suite and common successes across all four methods and three seeds for quality metrics.Source: C. Seed Sensitivity · p. 6
D. Goal-Time Range and Capacity Ablations
- At 3 s, widening the 16-root range from 25 to 100 s raises no-recycling mean arrival from 2.47 to 7.13 s, while recycling stays between 1.10 and 1.11 s.With eight roots over 100 s, both methods solve all 300 cases, but mean arrival is 13.98 s without recycling versus 1.10 s with recycling.Source: D. Goal-Time Range and Capacity… · p. 7
- The reported arrival-time result is 1.10 s; 1024 and 2048 provide no measurable additional improvement, underscoring root recycling’s importance when limited roots must cover a broad planning horizon.With sufficiently dense root coverage, planning without recycling can achieve similar arrival-time performance.Source: D. Goal-Time Range and Capacity… · p. 7
E. Real-Robot Demonstrations
Root-recycling ST-pRRTC was physically demonstrated on a UR5e planning among moving Crazyflies. The demonstrations execute preplanned motions to consecutive goals, while the conclusion places these trials alongside the planner’s benchmark results and guarantees distinction.
E. Real-Robot Demonstrations
- The UR5e with Robotiq gripper planned motions to consecutive goals among two, three, or five OptiTrack-localized Crazyflies using prescribed trajectories and conservative spherical collision proxies.A synchronized trigger executed the preplanned arm and drone trajectories after drone prepositioning; no online replanning occurred.Source: E. Real-Robot Demonstrations · p. 7
- Physical demonstrations included three-Crazyflie reaching and five-Crazyflie portal-poking, and the figures document execution of all four exported plans.Fig. 9 pairs temporal overlays with selected side-camera snapshots.Source: E. Real-Robot Demonstrations · pp. 7–8, Figure 9 · p. 8
VII. CONCLUSION
- The conclusion reports that both variants outperform ST-RRT* and SI-RRT on common-success sets, while only interval root has stated completeness and arrival-time optimality guarantees.Root recycling is reported to maintain early arrivals with sparse roots over broad horizons and is demonstrated on the UR5e among moving Crazyflies.Source: §VII · p. 8