Route Planning for Autonomous Vehicles

A Thesis Proposal

ABSTRACT

This thesis addresses the path planning problem which is one of the most crucial parts of autonomous driving by utilizing the Rapidly-Exploring Random Tree star (RRT*) search algorithm. Two focus points, i.e., the start and the goal, are used to create an ellipse which is used to focus sampling and search tree towards the goal instead of the whole graph to reduce the pathfinding time. To find the nearest node towards the goal 2D-Tree binary search technique is used. This algorithm should respond to various speed levels and also avoid the moving object in the path without reducing its speed. Matlab is used to acquire the numerical results of the modified RRT* that will also be considered regarding Field Programmable Gate Array (FPGA) implementation with parallel programming for the faster processing.

The proposed research will investigate different aspects of the RRT* algorithm such as different methods of sampling, binary search algorithms, and parallel programming to reduce the time and find the shortest obstacle-free path for the autonomous vehicles. 

TABLE OF CONTENTS

Page

ABSTRACT………………………………………………………………………………………iii

TABLE OF CONTENTS ..………………………………………………………………………iv

LIST OF FIGURES ………………..……………………………………………………………..v

LIST OF ACRONYMS ..…………………………………………………………………………vi

CHAPTER 1. INTRODUCTION ..……………………………………………………………….1

1.1  Background ……………………………………………………………………………………1

1.2  Technical Approaches …………………………………………………………………………2

CHAPTER 2. METHODOLOGY ..………………………………………………………………..5

2.1 RRT* Algorithm ………………………………………………………………………………5

2.2 Implementation ………………………………………………………………………………..6

REFERENCES ……………………………………………………………………………………10

APPENDIX I …………………………………………………………………………………….13

LIST OF FIGURES

Figure 1.1 Tree Expansion .………………………………………………………………………..3

Figure 1.2 RRT* vs. Informed RRT* ……………………………………………………………..4

Figure 2.1 Algorithm for RRT* .…………………………………………………………………..5

Figure 2.2 Plane subdivision and the corresponding tree schematics .……………………………6

Figure 2.3 The graph with 200 iterations …………………………………………………………7

Figure 2.4 The graph with 1500 iterations ..………………………………………………………7

Figure 2.5 The graph and path after RRT* Implementation ………………………………………8

Figure 2.6 The graph and path after simple modification in RRT* ……………………………….9

LIST OF ACRONYMS

RRT – Rapidly Exploring Random Tree

PRM – Probabilistic RoadMap

FPGA – Field Programmable Gate Array

INTRODUCTION

1.1 Background

The autonomous vehicle would be the future of transportation. Millions of people lost their lives due to road accidents, and a significant cause of road accidents are mistakes made by drivers. According to the World Health Organization (WHO), approximately 1.24 million people die due to road accidents [1]. The Autonomous car developed by many companies and universities to reduce road accidents and make roads safer. For example, Google has tested its driverless car for 3 million miles [2]. Even universities such as Stanford and Carnegie Mellon develop their Autonomous car and test it in Grand and Urban DARPA challenges [3].

Path planning is the critical issue in the autonomous vehicle. There are different objectives of the path planning, as listed below [4].

• Global planning
• Behavioral planning
• Local planning

Global planning takes care of mission planning or route planning using different techniques such as D*, A*, Probabilistic Road Map (PRM), RRT* to find shortest and obstacle-free path [4]. Behavioral planning focused on event and maneuver management such as when to overtake. Local planning executes the decision taken by the behavioral planning in the manner that dynamic and kinematic model of the car taken consideration to make the ride more comfortable [4].

1.2 Technical Approaches

 A* is a graph based search algorithm, which was implemented widely in different autonomous vehicles. i.e., hybrid A* was implemented by a junior in DARPA challenge [5]. A* Algorithm is used in a static environment where the algorithm is continuously searching for the nearest node that approaches the destination [6].  A heuristic method is used to find the optimal path. Algorithm introduces three different variables which are H (Heuristic) value of the node, G value a movement cost of node and F value is an addition of H and G value. Open list and closed list of the nodes have been maintaining all the time. A* Algorithm has guarantee solution if its possible in the graph. The disadvantage of the algorithm is the cost of the solution is very high in long and practical situations [7][8].

 Ant Colony Optimization (ACO) is also one of the widely used technique for small robots. ACO is a probabilistic search technique which can work in a static environment where algorithm mocks the real ants [9]. Ants produce a pheromone that can be used for pheromone trail to indicate the optimal path. The system requires the previously known environment to perform [10].

 Clothoid curve [11], Polynomial curves [12], Bézier curves [13] and Functional optimization [14] are the different techniques, but this technique more focused on vehicle dynamics and kinematic model which is more useful in motion planning instead of path planning [4].

 Various algorithms have been developed as mentioned above but to find the most appropriate route in a dynamic environment; sampling-based algorithms are widely used. RRT is a sampling based algorithm. RRT is introduced by, i.e., S. M. LaValle and J. J. Kuffner in [15]. There is a graph of the randomly generated sampling points with the start and the goal point. The tree is developed with the use of samples to connect the start and the goal points. RRT algorithms do not need entirely modeled obstacles to avoid them and create an obstacle-free path.

Fig. 1.1 Tree expansion [14].

RRT* is an improved version of the RRT which creates nodes alongside with the random sampling points [16][17]. New node works as a parent node and starts to find nearest node or sample point for tree expansion. Using this kind of heuristic method RRT* can be used with the moving objects. The disadvantage of this sort of system is tree expansion. Tree expansion is not focused towards the goal which caused more time in execution [16]. Fig. 1.1 shows the update in Xinitial to Xparent node.

Cloud RRT* is a novel approach for biased sampling method [19]. During this technique, the objective is to get more sampling density in promising regions for faster and more appropriate route planning. Cloud RRT* is one of the ways to focus the tree expansion towards a goal instead of expanding in the whole graph [19]. To achieve that generalized Voronoi diagram is used to define objects in C-space. In the set of obstacle-free space spherical cloud of the samples has been created.

Fig. 1.2 RRT* vs. Informed RRT* [20]

Anytime RRTs introduce by, i.e., D. Ferguson, A. Stentz, they added cost function in traditional RRT* [20]. First, the path was found with the use of RRT* after that cost function Cs is introduced now they start to see the path again, but they only consider the nodes which have less Cs value and create a new path which is more cost efficient, but the computational price has to pay.

  Informed RRT* uses the ellipsoidal space to focus the search and the tree expansion [21]. This is a simple but effective modification in RRT* algorithm which helps to reduce the computational time.  As it can be seen in Fig. 1.2, tree expansion is more focused in informed RRT* compared to RRT*, which result to reduce CPU time.

 Algorithms such as RRT computational time is a significant issue. The maximum time has been consumed in the process of tree expansion. So far the work has been done in that manner to focus that and find the best optimal path.

METHODOLOGY

2.1 RRT* ALGORITHM

This section introduces the basic RRT algorithm structure, which is introduced by, i.e., S. M. LaValle and J. J. Kuffner in [11]. Configuration space defined as Ⅽ and the obstacle region is