טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentTchuiev Vladimir
SubjectOptimal Pursuit with Rapidly Exploring Random Trees
DepartmentDepartment of Aerospace Engineering
Supervisor Professor Tal Shima


Abstract

The research addresses the problem of guiding a constant speed vehicle to a stationary target while enforcing a terminal heading constraint. A path that minimizes control effort and avoids obstacles scattered in the 2D environment is sought.


We utilize the Rapidly Exploring Random Trees (RRT) approach that uniformly samples vertices in the configuration space and connects them in a tree-like graph while avoiding obstacles. The RRT algorithm finds a feasible path if it exists, but almost surely does not converge to the optimal solution. Thus, we utilize an RRT variation, denoted RRT*, that retains the RRT properties and is guaranteed to asymptotically converge to the optimal solution.


We aim to create a minimum control effort path between vertices. The optimal solution of the non linear problem requires a significant computational effort, so we solve a linearized problem and acquire a controller with a closed form expression. The controller contains an expression for time-to-go that we approximate to achieve paths with close to optimal control effort. To expedite the convergence of the search to the optimal solution we also introduce two easy to calculate lower bounds for each new branch of the tree.


In our RRT{*} variation we sample vertices in the problem's configuration space and connect them in a spanning tree form around the obstacles. Each sampled vertex goes through three steps: Connecting to the best parent in the existing tree, pruning of high cost trajectories, and re-wiring connections with the sampled vertex as a parent while utilizing the lower bounds in all the steps.


The algorithm can also be used to solve a degenerated scenario without an intercept angle constraint - i.e. it provides a proportional navigation like solution for the nonlinear guidance problem with obstacles.


We demonstrate the algorithm's performance via simulations, showing that it can tackle various obstacle configurations, with and without terminal angle constraint. We investigate the algorithm's convergence rate towards the optimal solution. We also compared between the lower bounds and showcase a reduction of up to 60 percent in computational time when implemented.