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

Duo Zhang, Jintong Li, Junshan Huang, Jingjin Yu

Department of Computer Science, Rutgers University

arXiv preprint, 2026

arXiv PDF

Paper video

An overview of the method, benchmark results, and real-robot demonstrations.

Abstract

ST-pRRTC is a GPU-parallel space-time RRT-Connect planner for known obstacle trajectories and an unspecified arrival time. It grows a shared forward tree and a backward forest rooted at candidate goal-arrival times. Searching more arrival times broadens coverage but divides a finite planning budget among more trees. We study two ways to allocate that search effort: interval root samples goal times continuously, while root recycling reuses a bounded set of tree slots after finding an earlier solution. Interval root has probabilistic completeness and asymptotic arrival-time optimality for robust solutions in a bounded horizon. Root recycling is a practical policy without those general guarantees. Across three dynamic benchmarks, both variants achieve lower mean first-solution compute times and earlier mean final arrivals than ST-RRT* and SI-RRT on cases solved by all compared methods. A UR5e executing plans among moving Crazyflie drones demonstrates the approach on hardware.

ST-pRRTC: interval root and root recycling

A backward tree needs both a goal configuration and a goal-arrival time. GPU workers expand a shared forward tree and the backward forest in parallel, checking edges against moving obstacles at their corresponding times.

Interval root

Uniform sampling preserves coverage of candidate arrival times. Goal collision checks suggest guided sampling windows, and the planner collision-checks every sampled root. An earlier solution lowers the arrival bound while preserving useful search trees.

Interval-root sampling before and after a better arrival bound: uniform intervals and guided windows shrink while retained roots keep their times.
Uniform intervals provide coverage. Guided windows favor promising times. Earlier solutions reduce the active time range.

Guarantees: for a single goal in a bounded horizon, interval root is probabilistically complete for positive-clearance solutions and asymptotically optimal in arrival time when robust solutions approach the optimum. The analysis assumes unlimited sampling and storage, fair worker scheduling, and sound local collision validation that accepts sufficiently short collision-free motions.

Root recycling

Root recycling uses a fixed set of backward-tree slots. After an earlier solution, it replaces later roots with new, empty roots at earlier times and retains the shared forward tree and useful earlier backward trees. Recycled roots do not inherit the old tree's nodes. This policy focuses finite search effort on useful arrival times and does not inherit interval root's general completeness or optimality guarantees.

Root recycling: grow candidate goal-time trees, find an earlier solution, and reuse late slots for empty roots at earlier times.

Benchmarks

We compare root recycling and interval root with ST-RRT* and SI-RRT on Disc2D, a Panda arm among moving spheres, and UR5e tabletop transitions. In the tabletop benchmark, one arm plans against the prescribed motion of the other. Blue denotes the planned robot and red the moving obstacles. Translucent arms show goal configurations. The tabletop serves as visual context.

Top plots show cumulative first-solution success over all cases, averaged across planning budgets of 0.5, 1, 3, and 5 seconds. Their shading spans the minimum and maximum across budgets. Bottom plots show mean final arrival and 95% bootstrap intervals on cases solved by all four methods at each budget.

Compute time measures GPU-kernel execution for ST-pRRTC and CPU planning calls for the baselines, excluding scene construction and upload. Experiments use an RTX 4090 and an Intel Core i9-14900KF, with single-threaded CPU baselines.

  • Root recycling
  • Interval root
  • ST-RRT*
  • SI-RRT

Disc2D

300 cases

Representative Disc2D scene: the planned robot is blue and moving obstacles are red. Disc2D: percentage of solved problems versus first-solution compute time for root recycling, interval root, ST-RRT star, and SI-RRT. Disc2D: mean final arrival time versus planning budget, comparing the same four methods.

Panda-spheres

300 cases

Representative Panda-spheres scene: the planned robot is blue and moving obstacles are red. Panda-spheres: percentage of solved problems versus first-solution compute time for root recycling, interval root, ST-RRT star, and SI-RRT. Panda-spheres: mean final arrival time versus planning budget, comparing the same four methods.

Tabletop

962 cases

Representative Tabletop scene: the planned robot is blue and moving obstacles are red. Tabletop: percentage of solved problems versus first-solution compute time for root recycling, interval root, ST-RRT star, and SI-RRT. Tabletop: mean final arrival time versus planning budget, comparing the same four methods.

Benchmark motion examples

Example motions planned with root recycling. The robot is blue and the moving obstacles are red. Each clip plays at 1× speed and loops.

Disc2D

Example 1
Example 2
Example 3

Panda-spheres

Example 1
Example 2
Example 3

Tabletop (dual UR5e)

The blue UR5e plans its motion around the red UR5e’s prescribed trajectory.

Example 1
Example 2
Example 3

Real-robot demonstrations

A UR5e executes planned reaches among Crazyflie drones following known trajectories. A synchronized trigger starts the preplanned robot and drone motions. These demonstrations do not use online replanning.

Each clip pairs simulation with aligned front and side camera views at 2.5× playback speed.

Left/right reaching with three slow drones

The gripper alternates between targets on its left and right while three drones move through the workspace.

Left/right reaching with three fast drones

The same reaching task uses faster drone motion, requiring different timing to avoid collisions.

Top/center/bottom reaching with two drones

The gripper reaches the top, center, and bottom of a vertical opening while two drones circulate around it.

Citation

@article{zhang2026stprrtc,
  title   = {{ST-pRRTC}: Parallel Space-Time {RRT-C} with Adaptive Goal-Time Forests},
  author  = {Zhang, Duo and Li, Jintong and Huang, Junshan and Yu, Jingjin},
  journal = {arXiv preprint arXiv:2609.30533},
  year    = {2026},
  url     = {https://arxiv.org/abs/2609.30533}
}