Path Planning — (Prediction)

Michele Cavaioni
Jul 25, 2017 · 5 min read

Prediction is a multi-modal problem. The module calculates how probable each mode is.

Generally, we initialize each mode’s probability with the prior knowledge of a similar situation already seen in the past.

Then, we update each belief based on the new evidence we gather at the present moment.

The inputs to the prediction module are represented by the map and the sensor fusion data, while the output is a list of predictions of future states of all the vehicles and moving objects in the vicinity. The output is represented by a set of possible trajectories and associated probability.

Prediction is done using two approaches:

  • Model-Based approach: it uses mathematical models of motion to predict trajectories.
  • Data-Driven approach: it relies on Machine Learning and therefore on examples to learn from.

MODEL-BASED Approach:

A model-based approach includes the knowledge of physics and constraints imposed by the road, behavior of drivers and vehicle dynamics.

After taking those into consideration, it creates process models and related trajectories and it uses multi-modal estimation algorithms to compare the observed trajectories to the ones expected from each model. Based on that observation, it assigns probability to each of the predicted trajectories.

So, in summary, a model-based approach computes the following for each dynamic object that we observe nearby our vehicle:

  • Identifies the common behaviors (for example: changing lanes, going straight, etc).
  • Defines a process model for each behavior. A process model is a mathematical description of the motion of an object and it incorporates uncertainty.
  • Uses the process model to compute probability of each behavior. Therefore update the beliefs by comparing the observation with the output of the process model.
  • Generates a trajectory for each behavior.- Identifies the common behaviors (for example: changing lanes, going straight, etc).
  • Defines a process model for each behavior. A process model is a mathematical description of the motion of an object and it incorporates uncertainty.
  • Uses the process model to compute probability of each behavior. Therefore update the beliefs by comparing the observation with the output of the process model.
  • Generates a trajectory for each behavior.

To understand what a process model is we can consider the example of a car merging onto a highway.

In this situation we would consider all the possible behaviors that the car running on the right lane of the highway would take, such as:

- ignore us and move on

- speed up

- slow down to allow us to merge

- change lane

The process models associated to each behavior, respectively, could be the following:

- Follow the current lane with constant velocity

- Follow the current lane with positive acceleration

- Follow the current lane with negative acceleration

- Follow the adjacent lane with constant velocity

As we can see, these process models can be represented by a mathematical expression.

The multi-modal estimation algorithms allow us to maintain the beliefs on which behavior the driver tends to perform.

One approach is the Autonomous Multiple Model Estimation (AMM).

It considers some set of M process models/behaviors and the probability μ for each of them.

To define this probability, let’s consider an example of a vehicle at an intersection, observing an oncoming vehicle (the blue car in the image below).

The 2 process models for the blue car are:

- go straight

- turn right

Each process model is represented by a Gaussian uncertainty.

At a different time step (time K) we observe the state of the vehicle and compute the new probabilities.

Looking at the vehicle’s “s” coordinate, (ref. Frenet coordinates) the distribution of probability for the 2 expected states (turn right, go straight) will be as follows:

The probability of each behavior is a function of these likelihoods (L_k) and the probabilities computed in the previous time-step. (Therefore it is a product of the likelihoods by the previous probabilities).


DATA-BASED Approach:

The data-driven approach uses Machine Learning in order to predict the vehicle’s behavior.

The algorithm is trained on a lot of training data of observed behaviors and it predicts what will happen next.

In better details, these are the steps for training and prediction.

Training:

  • Collect a lot of trajectories (for example using images from cameras at several intersections).
  • Clean the data, keeping the most relevant ones.
  • Define a measure of trajectory similarity (different vehicles can approach the same trajectory following slight different paths, so we have to define a way to compare trajectories).
  • Perform unsupervised clustering (in an intersection we would have three clusters: go-straight, turn-left, turn-right).
  • Define prototype trajectories for each cluster.
Prototype trajectories for each cluster (go-straight, turn-left, turn-right)

Prediction:

Once we have defined the prototype trajectories for each cluster, we perform the following:

  • Observe the vehicle’s partial trajectory (at different time steps).
  • Compare the current trajectory to the prototype trajectories for each cluster (using the same similarity measure used to perform the clusters).
  • Compute predicted trajectory for each cluster with associated probabilities.

This article has been inspired by the Udacity Self-Driving Car Nanodegree lectures (https//www.udacity.com)

Self-driving car bites

Projects and lectures on Autonomous Vehicle technology

Michele Cavaioni

Written by

Passionate about AI, ML, DL, and Autonomous Vehicle tech. CEO of CritiqueMatch.com, a platform that helps writers and bloggers to connect and exchange feedback.

Self-driving car bites

Projects and lectures on Autonomous Vehicle technology

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade