In a self-driving car car, GPS (Global Positioning Systems) use trilateration to locate our position.
In these measurements, there may be an error from 1 to 10 meters. This error is too important and can potentially be fatal for the passengers or the environment of the autonomous vehicle. We therefore include a step called localization.
Localization is the implementation of algorithms to estimate where is our vehicle with an error of less than 10 cm.
This article follows articles AI … And the vehicle went autonomous and Sensor Fusion.
Localization is a step implemented in the majority of robots and vehicles to locate with a really small margin of error. If we want to make decisions like overtaking a vehicle or simply defining a route, we need to know what’s around us (sensor fusion) and where we are (localization). Only with this information we can define a trajectory.
How to locate precisely?
There are many different techniques to help an autonomous vehicle locate itself.
- Odometry — This first technique, odometry, uses a starting position and a wheel displacement calculation to estimate a position at a time t. This technique is generally very inaccurate and leads to an accumulation of errors due to measurement inaccuracies, wheel slip, …
- Kalman filter — The previous article evoked this technique to estimate the state of the vehicles around us. We can also implement this to define the state of our own vehicle.
- Particle Filter — The Bayesian filters can also have a variant called particle filters. This technique compares the observations of our sensors with the environmental map. We then create particles around areas where the observations are similar to the map.
- SLAM — A very popular technique if we also want to estimate the map exists. It is called SLAM (Simultaneous Localization And Mapping). In this technique, we estimate our position but also the position of landmarks. A traffic light can be a landmark.
Sensors
- Inertial Measurement Unit (IMU)is a sensor capable of defining the movement of the vehicle along the yaw, pitch, roll axis. This sensor calculates acceleration along the X, Y, Z axes, orientation, inclination, and altitude.
- Global Positioning System (GPS) or NAVSTAR are the US system for positioning. In Europe, we talk about Galileo; in Russia, GLONASS. The term Global Navigation Satellite System (GNSS) is a very common satellite positioning system today that can use many of these subsystems to increase accuracy.
Vocabulary
We will introduce several words in this article :
- Observation — An observation can be a measurement, an image, an angle …
- Control — This is our movements including our speeds and yaw, pitch, roll values retrieved by the IMU.
- The position of the vehicle — This vector includes the (x, y) coordinates and the orientation θ.
- The map — This is our landmarks, roads … There are several types of maps; companies like Here Technologies produce HD Maps, accurate maps centimeter by centimeter. These cards are produced according to the environment where the autonomous car will be able to drive.
Kalman Filters
Explained in the previous article, a Kalman filter can estimate the state of a vehicle. As a reminder, this is the implementation of the Bayes Filter, with a prediction phase and an update phase.
Our first estimate is an equal distribution across the area.
We then have a measurement telling us that we are located next to a door.
Our distribution then changes to give a higher probability to areas located near doors.
We then perform a motion, our probabilities are shifted with greater uncertainties.
We take a new measurement, telling us that we are next to a door again.
The only possibility is to be located near the middle door.
In this example of a Kalman filter, we were able to locate ourselves using a few measurements and a comparison with the map. It is essential to know the map (including information only the 1st door has an adjacent door) to make deductions. This technique makes it possible not to use an initial position, which is preferable to the technique using odometry.
Particle Filters
A Particle Filter is another implementation of the Bayes Filter.
In a Particle Filter, we create particles throughout the area defined by the GPS and we assign a weight to each particle.
The weight of a particle represents the probability that our vehicle is at the location of the particle.
Unlike the Kalman filter, we have our probabilities are not continuous values but discrete values, we talk about weights.
Algorithm
The implementation of the algorithm is according to the following scheme. We distinguish four stages (Initialization, Prediction, Update, Sampling) realized with the help of several data (GPS, IMU, speeds, measurements of the landmarks).
- Initialization — We use an initial estimate from the GPS and add noise (due to sensor inaccuracy) to initialize a chosen number of particles. Each particle has a position (x, y) and an orientation θ.
This gives us a particle distribution throughout the GPS area with equal weights. - Prediction — Once our particles are initialized, we make a first prediction taking into account our speed and our rotations. In every prediction, our movements will be taken into account. We use equations describing x, y, θ (orientation) to describe the motion of a vehicle.
- Update — In our update phase, we first realize a match between our measurements n and the map m.
We use sensor fusion data to determine surrounding objects and then update our weights with the following equation :
In this equation, for each particle:
– σx and σy are our uncertainties
– x and y are the observations of the landmarks
– μx and μy are the ground truth coordinates of the landmarks coming from the map.
In the case where the error is strong, the exponential term is 0, the weight of our particle is 0 as well. In the case where it is very low, the weight of the particle is 1 standardized by the term 2π.σx.σy.
- Resampling — Finally, we have one last stage where we select the particles with the highest weights and destroy the least likely ones.
The higher the weight, the more likely the particle is to survive.
The cycle is then repeated with the most probable particles, we take into account our displacements since the last computation and realize a prediction then a correction according to our observations.
Particle filters are effective and can locate a vehicle very precisely. For each particle, we compare the measurements made by the particle with the measurements made by the vehicle and calculate a probability or weight. This calculation can makes the filter slow if we have a lot of particles. It also requires having the map of the environment where we drive permanently.
Results
My projects with Udacity taught me how to implement a Particle Filter in C ++. As in the algorithm described earlier, we implement localization by defining 100 particles and assigning a weight to each particle through measurements made by our sensors.
In the following video, we can see :
- A green laser representing the measurements from the vehicle.
- A blue laser representing the measurements from the nearest particle (blue circle).
- A particle locating the vehicle (blue circle).
- The black circles are our landmarks (traffic lights, signs, bushes, …) coming from the map.
SLAM (Simultaneous Localization And Mapping)
Another very popular method is called SLAM, this technique makes it possible to estimate the map (the coordinates of the landmarks) in addition to estimating the coordinates of our vehicle.
To work, we can with the Lidar find walls, sidewalks and thus build a map. SLAM’s algorithms need to know how to recognize landmarks, then position them and add elements to the map.
Conclusion
Localization is an essential topic for any robot or autonomous vehicle. If we can locate our vehicle very precisely, we can drive independently. This subject is constantly evolving, the sensors are becoming more and more accurate and the algorithms are more and more efficient.
SLAM techniques are very popular for outdoor and indoor navigation where GPS are not very effective. Cartography also has a very important role because without a map, we cannot know where we are.
Today, research is exploring localization using deep learning algorithms and cameras.
Now that we are localized and know our environment, we can discuss algorithms for creating trajectories and making decisions!
ACE IT SKILLS 
