Kidnapped Vehicle

In this project we utilize a particle filter approach to achieve a high accuracy for the localization module on a self driving car. This project involves the Term 2 Simulator which can be downloaded here.

The localization module is a critical one in a self driving vehicle. Localization can be defined as predicting the location of a vehicle with high accuracy in the range 3-10 cm, one way to localize a vehicle is by using data from the Global Positioning System (GPS), which makes use of triangulation to predict the position of an object detected by multiple satellites. But GPS doesn't always provide high accuracy data, e.g. In case of strong GPS signal, the accuracy in location is in the range of 1-3 m, whereas for a weak GPS signal, the accuracy drops to a range of 10-50 m. Hence the use of only GPS is not reliable and desirable.

To achieve an accuracy of 3-10 cm, sensor information from Laser (LIDAR) and/or Radial distance and angle sensor (RADAR) is used and fused together using a Particle Filter.

Dependencies

• cmake >= 3.5
  • All OSes: click here for installation instructions
• make >= 4.1 (Linux, Mac), 3.81 (Windows)
  • Linux: make is installed by default on most Linux distros
  • Mac: install Xcode command line tools to get make
  • Windows: Click here for installation instructions
• gcc/g++ >= 5.4
  • Linux: gcc / g++ is installed by default on most Linux distros
  • Mac: same deal as make - install Xcode command line tools
  • Windows: recommend using MinGW
• uWebSockets

Running the Code

Some scripts have been included to streamline this process, these can be leveraged by executing the following in the top directory of the project:

> ./clean.sh
> ./build.sh
> ./run.sh

Tips for setting up your environment can be found here.

The Map

map_data.txt includes the position of landmarks (in meters) on an arbitrary Cartesian coordinate system. Each row has three columns.

1. x position
2. y position
3. landmark id

Goal

In this project, a vehicle is kidnapped inside a closed environment and has no idea of its location. This environment is simulated in Udacity's self driving car simulator. The vehicle travels through the environment and takes roughly 2400 steps with change in orientation and position. The goal is to predict the location of vehicle using a Particle Filter approach implemented in C++. The error between ground truth location of robot and the predicted location should be minimal. Additionally, the program must be performant enough to run within 100 seconds while maintaining minimal error.

Implementation

The directory structure of this repository is as follows:

.
├── build.sh
├── clean.sh
├── CMakeLists.txt
├── README.md
├── run.sh
├── data
    ├── map_data.txt   
├── src
    ├──  helper_functions.h
    ├──  main.cpp
    ├──  map.h
    ├──  particle_filter.cpp
    ├──  particle_filter.h

The localization module was implemented as described below:

1. A noisy measurement from GPS sensor was received and used to initialize the position of vehicle. This measurement included the x coordinate, y coordinate (both in m) and the theta (orientation) of vehicle in radian. Noise is modelled by Gaussian distribution for all the previously described parameters. The number of particles chosen for this project was 30 and were initialized to locations taken from normal distribution with mean equal to the location received from GPS and standard deviation equal to the GPS measurement uncertainty.

2. Global map of environment is initialized. This map is represented by a list x and y coordinates of landmarks in the environment.

3. Once map and particles are initialized, the vehicle implements the Prediction step in which the location of each particle at next time step is predicted. This is done by using information of control inputs and time elapsed between time steps. The control inputs are nothing but magnitude of velocity (v) and yaw rate (θ). Location update is done with the help of the formulas given below:

4. After prediction step, the vehicle implements the Update step by using the information provided by the sensors (LIDAR and RADAR). However the coordinates of these measurements are relative to our vehicle and not the map, so a homogenous transformation is performed to map the vehicle coordinates to the global map ones in the following way.

Not all the particles can be in the vehicle's range at a given momment, so we retain only those that are in the range of the sensors from the particle position, and after this filtering process we map every sensor observation to a landmark using 1-NN (nearest neightbour algorithm). Finally the weight of the particle is updated using a Multivariate Gaussian Distribution for all observations associated to landmarks using the formula below (individual probabilities).

5. The last step is resampling the particles with replacement using their normalized weight as probabilities of appearance causing removal of the unlikely ones and more presence of the likely ones.