PREDICTION in Autonomous Vehicle - All You Need To Know

Think of a situation , you were driving a car on a two lane road, moving forward you want to take a right turn but there is a car in the 2nd lane coming in opposite direction , Now what will you do ?

Prediction in autonomous vehicle is all about how our autonomous vehicle is going to predict the trajectory or path of the other vehicle and take an action to avoid collision.

I am in the Term-3 of Udacity Self Driving Car Nanodegree Program and here I will be sharing my knowledge on Prediction, an important part of trajectory planning for autonomous vehicle.

How is it done?

The inputs for Prediction comes from Sensor fusion and Localization. Sensor fusion is all about combining data(using Kalman Filter) from multiple sensors(Like Radar, LIDAR,etc.) for our car to understand its environment while Localization is used by the car to know precisely where it is .

Once we have the inputs ,Predicting trajectory of the vehicle can be done by the following approaches:

1. Model based Approach

2. Data Driven Approach

These approaches can be used individually or hybrid of the two to make better prediction .

Let’s look at these approaches one at a time: -

1. Model Based Approach:

This approach identifies common behaviors of the vehicle(change lane, turn left, turn right, determining maximum turning speed, etc.) .

In this approach we create a model for each possible trajectory the vehicle can go and send it to a Multi modal Estimation Algorithm (Assume it to be a black box for now) along with the behavior of the car. This Algorithm will assign probabilities to trajectory model and finally the model with the highest probability will be selected.

Modal Based Approach

Before we dive much into Model Based Approach lets have a look at the Frenet Coordinate System.

Frenet Coordinate System

In FCS we use ‘s’ and ‘d’ notation to determine the position of the object, where ‘s’ is the distance on the road while d determine the distance from center of the lane unlike the Cartesian Coordinate system in which we use x, y coordinates to denote the position on the road . FCS is a better way of representing the position of object on the road because implementation of equation for curvy road using Cartesian Coordinate will be much harder.

Steps Used in Model Based Approach:

Steps used in Model Based Approach

Step 1: Identify the common behavior of the cars

Step 2: Create process model for each behavior that is identified

Step 3: Calculate the probabilities of each Process model

Let’s understand each step by taking a simple example:

Image Source: Udacity Nano Degree Program

Suppose that our Autonomous vehicle (Green car ) has to come on highway . for that it has to predict the behavior of the blue car .

Step1:

The behavior of the blue car can be as follow:

• It will ignore us
• It will decelerate and be a polite driver to let our car go ahead
• It will accelerate and will go ahead of our car
• It will change lane and continue with same velocity

etc..

We have to represent each of these behavior using mathematical description. For that we will move to step 2.

Step2:

Process Model provides a mathematical description for the identified behaviors .

These models can vary in complexity from a very simple to a very complex mathematical description

• Note that number of process model depend upon the number of behavior identified . It may vary with the number of the behavior.

General state form of the process model for predicted state x at time k is given as :

state vector

Step3:

In this step we are going to determine what action the driver in the car is going to perform by assigning probability to the process model we have created for each behavior. This is done by Multi modal Estimation Algorithms. The simplest approach to this algorithm is Autonomous multiple modal (AMM) algorithm.

Autonomous multiple modal (AMM) algorithm.

In AMM we first observe the state of the vehicle at time k-1 and at time k.

Then we compute our process model at time k-1 and get the expected states for time k.

Then will just compare the likelihood of the expected state with the observed state. And get the probability of the model at time k using the following formula:

Probability of the Model (i) at time k

where:

M: Number of different process model

U: Probability of the model.

L: Likelihood of the observation of the model

k: timestamp

Finally, the model with the highest probability is selected.

2. Data Driven Approach

In data driven approach we will take a black box and train it using lots of training data. One it gets trained we will fit the observed behaviour and get the prediction .

It is helpful in determining specific patterns of the vehicle which could havebe otherwise missed .

Data Driven Approach is done in two phases:

1. Offline Training (Training of model)
2. Online Prediction (Prediction of trajectory using model)

Data Based Approach

Offline Training

Steps Used in Data Driven Approach:

Step 1: Get Data of Lots of Trajectories

Step 2: Clear Data

Step 3: Select a measure to perform similarity

Step 4: Perform Unsupervised clustering of trajectories using machine learning algorithms like spectral clustering or agglomerative clustering

Step 5: Define a trajectory pattern for each cluster

By following these steps we will end up with patterns and clustureof trajectories

Online Prediction

Step 1: Observe the vehicle partial trajectory

Step 2: Compare it with prototype trajectories

Step 3: Predict a trajectory

Repeat the Online Prediction Steps till we find a maximum likelihood for one of the prototype trajectory to be similar to the vehicle trajectory.

So till now you must be having a good understanding of the two different approaches for predicting the trajectories.

Hybrid Approach

So now the question is which approach to use ..?

Well why not to use the advantage of both the approach . This is where Hybrid Approach Comes into picture . :)

Hybrid Approach

In order to implement the hybrid approach we will replace the multiple motion estimator of the motion based approach with machine learning. And in order to do so we need a classifier. So one such classifier is Naive Bayes Classifier

Naive Bayes Classifier:

A typical assumption while dealing with continuous data is that continuous value associated with each class are distributed according to a Gaussian distribution.

For example suppose the training data contains a continuous attribute x . We first segment this data by the class and then calculate the mean and standard deviation of each class. Suppose we have the k_th segment of the class i.e C_k of x and u_k is the mean and sigma_square_k is the standard deviation Then the probability distribution of v given a class C_k can be computed by plugging v into the equation

So that’s all what we need to know about how prediction is done by our autonomous vehicle in predicting the trajectory of the other vehicles. Remember in this blog we have covered prediction by taking one object at a time while in real world scenarios there can be number of objects whose prediction has to be at the same time,this make the process of prediction more complicated . Fortunately what we have learned till now can be a good way of predicting the trajectory of vehicles on highway.

You can learn more on Prediction by following this paper on multiple-model algorithms by Ryan R. Pitre Vesselin P. Jilkov X. Rong Li.

In case of any query reach out to me on LinkedIn or write down as a private note.