Motion Planning in Dynamic Environments with the Rapidly Exploring Random Tree Method

Abstract

The Rapidly Exploring Random Tree (RRT) algorithm is a probabilistic motion planning method. It builds a graph in the configuration space of a robot such that its motion equation is taken into account. The basic RRT algorithm is able to plan a path which avoids the collision with static obstacles. This paper discusses the required modifications if the environment of the robot contains moving obstacles as well. Two different methods are presented. The first one can only be used if the graph is a single tree. The main modification w.r.t. the original RRT algorithm is that the graph is built in an extended space and a special distance-like pseudo-metric is applied. The second algorithm may work with several trees as well and it is based on the time-scaling of the reference path.