Rapidly Exploring Random Trees for Guidance of Autonomous Vehicles

The rapidly-exploring random tree (RRT) method was designed for guidance of a robotic vehicle by performing a random sampling search that generates feasible paths while taking into consideration constraints such as obstacles. The method generates fast solutions for a given problem and improves them by adding more and more samples to the tree; however, it tends to converge to solutions that are far from optimal. A variation of the RRT method, known as RRT*, was recently designed to generate solutions that almost surely converge to the optimal solution. However, it requires a substantially larger computation effort.
Current RRT based algorithms plan the motion of the vehicle while obstacles are presumed stationary and the goal target is at a fixed position. A new variant for RRT is proposed for dealing with time-dependent problems. Dynamic environments that include changes of goal target, constraints, and system dynamics over time can be considered by this variant. Results show convergence to minimal time solutions when based on a simple RRT method, without the need for complicated schemes like the RRT*.
We will begin the talk with a review on the field of motion planning and the principles of RRT based methods, followed by definitions for a Dubins car-like vehicle, which represents a crude description of the dynamics of an aerial vehicle. The main part of the talk will focus on motion planning with time varying constraints and objectives by using the new RRT variant. The ability of the algorithm, in generating near-optimal solutions for time varying constraints and objectives, will be presented.