Francesco Grothe, Valentin N. Hartmann, Andreas Orthey, Marc Toussaint

Machine Learning & Robotics Lab, University of Stuttgart, Germany
Learning and Intelligent Systems Group, TU Berlin, Germany

Brief: We extend and modify RRT-Connect to a combination of space and time. This allows us to plan paths for agents in environments that have moving obstacles with known trajectories. ST-RRT* is complete and asymptotically optimal.

We used an early version of ST-RRT* in the multi-agent-tamp solver.

Abstract:

We present a motion planner for planning through space-time with dynamic obstacles, velocity constraints, and unknown arrival time. Our algorithm, Space-Time RRT* (STRRT*), is a probabilistically complete, bidirectional motion planning algorithm, which is asymptotically optimal with respect to the shortest arrival time. We experimentally evaluate ST-RRT* in both abstract (2D disk, 8D disk in cluttered spaces, and on a narrow passage problem), and simulated robotic path planning problems (sequential planning of 8DoF mobile robots, and 7DoF robotic arms). The proposed planner outperforms RRT-Connect and RRT* on both initial solution time, and attained final solution cost. The code for ST-RRT* is available in the Open Motion Planning Library (OMPL).

Paper

Latest version: arXiv

Code

Code is available on Github.

Demo

The red disk needs to find a path through the moving obstacles (blue) to the goal (black).


We sequentially plan the movement of a mobile robot from a random start to a random goal state.

Bibtex

1
2
3
4
5
6
7
8
9
10

@inproceedings{22-grothe-ICRA,
  title     = {ST-RRT*: Asymptotically-Optimal Bidirectional Motion Planning 
               through Space-Time},
  author    = {Grothe, Francesco and Hartmann, Valentin N. and Orthey, Andreas and
               Toussaint, Marc},
  booktitle = {Proc{.} of the IEEE Int{.} Conf{.} on Robotics and
  		       Automation (ICRA)},
  year      = {2022},
  arxiv_pdf = {2203.02176}
}

Funding

The research has been supported by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) under Germany’s Excellence Strategy – EXC 2120/1 – 390831618 “IntCDC”