GPU-parallel robot motion planner improves timing in dynamic spaces
ST-pRRTC: Parallel Space-Time RRT-C with Adaptive Goal-Time Forests
Robotics
Summary
Planning robot movements around moving obstacles can be tricky, especially when the exact time to reach the goal isn't fixed. The authors developed a method called ST-pRRTC that uses many quick computations on a graphics card to explore possible arrival times and routes. This method keeps track of multiple possible goal times adaptively, helping it find efficient routes faster than earlier approaches. They tested their method in simulations and real robots, showing it reaches goals sooner while avoiding moving obstacles.
What this means in practice
- •For industrial robot programmers: Generate faster collision-free arm trajectories around moving obstacles when exact arrival times are flexible.
- •For autonomous drone operators: Plan drone flight paths that avoid moving robots and change goal arrival times dynamically for improved safety.
Authors
Duo Zhang, Jintong Li, Junshan Huang, Jingjin Yu
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.