M.Sc Thesis

M.Sc StudentSharon Yasovitch
SubjectRapidly Exploring Random Trees for Guidance of Autonomous
DepartmentDepartment of Aerospace Engineering
Supervisor Professor Shima Tal


A recently developed tool known as rapidly-exploring random tree (RRT) is designed for robotic applications. This tool is used to solve motion planning problems of a vehicle moving amidst obstacles by preforming a random sampling search while generating feasible paths. RRT based algorithms are easily adjusted to many research fields and so are relevant to different uses. This thesis is aimed at solving complex problems in interception and guidance that deal with: obstacle avoidance, path-planning according to system dynamics, constraints that change over time and demands for time-based optimality, through the use of RRT-based algorithms.

A simple RRT algorithm can quickly achieve solutions to the defined problem; however, the solutions are far from optimal. Optimal solutions are usually achieved by a variation of the algorithm known as RRT*, that demands large computational effort. The algorithm presented in this work is based on a simple RRT method and allows for near-optimal solution to be achieved (without using an RRT* method) by using the desired cost function as part of the search space.

The new RRT variant is proposed for dealing with time-dependent motion planning problems. This is made by two innovations: extension of the search space with an additional time domain and path assignment methods that allow for better convergence rates in the new extended domain. Time progression of goal target and constraints are considered by the algorithm resulting in a convergence to minimal time solutions in a complex environment. An additional adjustment to the RRT algorithm is for the steering method of the algorithm according to the new search space.

In an attempt to explore the abilities of the new RRT method, we use a simple dynamics model known as Dubins dynamics. This dynamic model demonstrates how to adjust the new algorithm to various dynamic systems.

When extending the search space with time, the new RRT method demands construction of paths that are compliant with a time frame demand. For the Dubins model this is made by a changing turn radius solution method that is designed in this work. This novel path-planning method allows for Dubins path extension for a predefined fixed length by calculating an appropriate turn radius.

The thesis includes analytical analysis to assure the completeness property of the new RRT algorithm. The analysis defines a set of required conditions that while adhering to these conditions the new algorithm maintains convergence of the results to near-optimal solutions. The work is also confirmed by simulations of a Euclidean two dimensional plane with a time extension, a classic Dubins vehicle simulation and a Dubins vehicle motion with time extension.

The results of the simulations depict near-optimal solutions for different Dubins and relaxed Dubins problems, stationary and moving obstacles avoidance and solutions for a one-sided interception of a target moving in a known trajectory. These results illustrate the ability of the new algorithm to near-optimally solve complex interception problems within a highly constrained environment.