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

Duo Zhang; Jintong Li; Junshan Huang; Jingjin Yu

cs.ROSep 24, 2026

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

Authors: Duo Zhang, Jintong Li, Junshan Huang, Jingjin Yu

Organizations: Department of Computer Science, Rutgers, the State University of New Jersey, Piscataway, NJ, USA

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.

Figures & tables

Panel of Figure 1 — Fig. 1: A physical UR5e executes a motion planned by ST-pRRTC among three moving Crazyflies in the slow demonstration. The large image overlays robot and drone poses over time; the yellow arrow indicates end-effector motion toward the goal. The right column shows selected side-camera snapshots.

Panel of Figure 2 — Fig. 2: Interval root with $N=3$ backward-tree groups for one goal. Outlined boxes divide the full arrival range equally; filled bands divide the total guided-window duration equally. Matching colors identify groups; guided portions need not align with a group’s uniform interval. The marked samples $T$ lie between grid checks. After a better incumbent $U$ , both sampling allocations update, while retained roots keep their original times and group colors; gray roots are inactive.

Panel of Figure 3 — Fig. 3: Root recycling redirects finite tree capacity toward earlier arrivals. A solution arriving at $U$ makes later roots unable to improve arrival time. Their slots are reused at earlier collision-free times; hollow circles are replacement roots with no inherited nodes. The shared forward tree and earlier backward trees are retained. All panels use the same schematic space–time coordinates; the root at $U$ remains stored but inactive.

Panel of Figure 4 — Algorithm 1 Extend ( $\mathcal{T},\overline{\mathcal{T}},\mathcal{V},\sigma,x_{r},(U,C)$ )

Panel of Figure 5 — Algorithm 2 IntervalRoot ( $q_{s},q_{g},N,H,B$ )

Panel of Figure 6 — Algorithm 3 ST-pRRTC-RootRecycle ( $q_{s},q_{g},N,H,B$ )

Panel of Figure 7 — Fig. 4: Representative benchmark scenes from root-recycling solutions. Blue denotes the planned robot and red the moving obstacles; translucent arms indicate goal configurations. Both tabletop arms are shown at their start (solid) and goal (translucent) configurations. Arrows in the other panels show selected obstacle motion directions. The orange Disc2D curve is the time-parameterized robot path. The table is visual context only.

Panel of Figure 8 — Fig. 5: Cumulative first-solution success. Lines average the four planning budgets; shading spans their minimum and maximum. All scenes are included.

Suite	DoF	Moving geometry	Horizon	$v_{\max}$	Cases
Disc2D	2	20 discs	8.0 s	1.2 m/s	300
Panda-spheres	7	5 spheres	6.0 s	3.14 rad/s	300
Tabletop	6	other arm	$2T$	$\pi/2$ rad/s	962

TABLE I: Benchmark suites.

	Budget (s)	Metric	Root recycling	Interval root	ST-RRT*	SI-RRT
Disc2D	0.5	$S$ (%)	95.7	96.0	95.0	96.7
		$\bar{t}$ (ms)	1.59	1.31	9.85	4.66
	1	$S$ (%)	96.0	96.0	95.3	96.7
		$\bar{t}$ (ms)	1.17	1.37	11.40	5.62
	3	$S$ (%)	96.3	96.0	95.7	96.7
		$\bar{t}$ (ms)	0.93	1.34	11.48	5.58

TABLE II: Success and first-solution time.

Panel of Figure 11 — Fig. 6: First-solution (top) and final (bottom) arrival times. Means and 95% bootstrap intervals use the common-success set at each budget; the two rows share a vertical scale within each benchmark.

Panel of Figure 12 — Fig. 7: Final path length on the common-success sets. Shading shows 95% bootstrap intervals; Disc2D uses metres and the manipulators use joint-space radians.

Panel of Figure 13 — Fig. 8: Sensitivity to the initial arrival-time range, root count, and batch size on 300 tabletop cases. Each column varies one parameter with the other settings fixed as shown. Top: success rate over all cases. Bottom: mean final arrival on cases solved by both methods at each setting and budget. Error bars are clustered 95% bootstrap intervals; point labels report 3 s-budget means. $H_{\rm scene}$ denotes the per-transition horizon.

Disc2D (95 common successes at 5 s)
	Solved problems (%)				5-s budget: seed means
Method	0.5 s	1 s	3 s	5 s	First-solution time (ms)	Final arrival (s)
Root recycling	97–98	97–98	96–98	97–98	1.10–1.92	3.538–3.555
Interval root	96–97	96–97	97	96–97	1.26–1.97	3.548–3.554
ST-RRT*	95	95	95	95–96	14.62–17.96	3.650–3.724
SI-RRT	95–96	96–97	96–97	97	3.53–7.43	5.414–5.704

TABLE III: Seed sensitivity.

Panel of Figure 15 — Fig. 9: Physical executions of root-recycling ST-pRRTC. Each large image overlays the same UR5e and its moving drone obstacles at multiple times. Yellow arrows indicate end-effector motion between successive goals; the smaller images show selected side-camera snapshots. The slow three-Crazyflie demonstration is shown in Fig. 1 .

Motion Planning

Motion planning finds safe, feasible paths and trajectories for robots and vehicles amid geometric, dynamic, and task constraints.

See all 392 papers

RRT $^η$ : Sampling-based Motion Planning and Control from STL Specifications using Arithmetic-Geometric Mean Robustness
Feb 18, 2026Ahmad Ahmad, Shuo Liu, Roberto Tron +1STL Motion Planning Motion Planning
Division of Systems Engineering, Boston University, Boston, MA, USA. · Department of Mechanical Engineering, Boston University, Boston, MA, USA. · Department of Electrical and Computer Engineering and the Department of Computer Science at the University of Maryland, College Park, MD, USA.
FLASH-CBF-RRT: Fast Lipschitz-Adaptive Safe Horizon CBF Steering for Certified Motion Planning
Oct 16, 2026Mani Amani, Hesam Mojtahedi, Reza Akhavian +2Motion Planning Safe Motion Planning
Department of Civil, Construction, and Environmental Engineering, San Diego State University, San Diego, CA, USA · Department of Electrical and Computer Engineering, University of California San Diego, La Jolla, CA, USA
Greedy Heuristics for Sampling-Based Motion Planning in High-Dimensional State Spaces
May 6, 2024Phone Thiha Kyaw, Anh Vu Le, Rajesh Elara Mohan +1Sampling-Based Motion Planning Tree Search
Space & Terrestrial Autonomous Robotic Systems (STARS) Laboratory, University of Toronto Institute for Aerospace Studies, 4925 Dufferin Sreet, Toronto, M3H 5T6, Ontario, Canada. · Advanced Intelligent Technology Research Group, Faculty of Electrical and Electronics Engineering, Ton Duc Thang University, Ho Chi Minh City, 700000, Vietnam. · ROAR Lab, Engineering Product Development, Singapore University of Technology and Design, Singapore, 487372, Singapore.

Feb 18, 2026J/K move · Enter open · S save

RRT $^η$ : Sampling-based Motion Planning and Control from STL Specifications using Arithmetic-Geometric Mean Robustness

Ahmad Ahmad, Shuo Liu, Roberto Tron, Calin Belta

Division of Systems Engineering, Boston University, Boston, MA, USA. · Department of Mechanical Engineering, Boston University, Boston, MA, USA. · Department of Electrical and Computer Engineering and the Department of Computer Science at the University of Maryland, College Park, MD, USA.

STL Motion Planning Motion Planning Sampling-Based Motion Planning Constrained Motion Planning

Open paper AskPDF arXiv

Sampling-based motion planning has emerged as a powerful approach for robotics, enabling exploration of complex, high-dimensional configuration spaces. When combined with Signal Temporal Logic (STL), a temporal logic widely used for formalizing interpretable robotic tasks, these methods can address complex spatiotemporal constraints. However, traditional approaches rely on min-max robustness measures that focus only on critical time points and subformulae, creating non-smooth optimization landscapes with sharp decision boundaries that hinder efficient tree exploration. We propose RRT

^η

, a sampling-based planning framework that integrates the Arithmetic-Geometric Mean (AGM) robustness measure to evaluate satisfaction across all time points and subformulae. Our key contributions include: (1) AGM robustness interval semantics for reasoning about partial trajectories during tree construction, (2) an efficient incremental monitoring algorithm computing these intervals, and (3) enhanced Direction of Increasing Satisfaction vectors leveraging Fulfillment Priority Logic (FPL) for principled objective composition. Our framework synthesizes dynamically feasible control sequences satisfying STL specifications with high robustness while maintaining the probabilistic completeness and asymptotic optimality of RRT

^\ast

. We validate our approach on three robotic systems. A double integrator point robot, a unicycle mobile robot, and a 7-DOF robot arm, demonstrating superior performance over traditional STL robustness-based planners in multi-constraint scenarios with limited guidance signals.

Abstract

Motion Planning

Explore similar work

RRTη^ηη: Sampling-based Motion Planning and Control from STL Specifications using Arithmetic-Geometric Mean Robustness

FLASH-CBF-RRT: Fast Lipschitz-Adaptive Safe Horizon CBF Steering for Certified Motion Planning

Greedy Heuristics for Sampling-Based Motion Planning in High-Dimensional State Spaces

RRT $^η$ : Sampling-based Motion Planning and Control from STL Specifications using Arithmetic-Geometric Mean Robustness