What do we mean by Localization? Should be the first question coming to us. Localization is the process of locating an object in a particular place or environment. Having said this, now the process of locating the vehicle on the road is “localization” in autonomous vehicles. For the autonomous vehicle to navigate its way through the destination, the vehicle has to localize itself on the road at every timestamp.
Therefore, the next question is “Why is it so hard to localize?” Let us start with “human driver” first. For any driver to reach the destination, the driver has to know where the source is and where the driver is currently. This is the basic concept of localization. For humans, the localization works differently based on the experience their perceptive of looking at the environment. However, in autonomous vehicles, there has to be a certain common criteria defined as the standard operating procedure across all the vehicles.
Programming the autonomous vehicle is similar to teaching a newborn to walk and navigate. The only difference is with autonomous vehicles, we are looking at two different worlds at the same time namely, static and dynamic. When a newborn is walking around, the dynamic world is at standstill giving way to the newborn, but with the autonomous vehicles, the vehicle has to find its way carefully through the dynamic world.
Static world are the objects in the environment that does not move or change as the vehicle is passing through. Like the roads, lane markings, signboards and other objects along the road. Dynamic world comprises of the pedestrians, cyclists, motorists and other vehicles. These keep moving along our vehicle and may or may not cross our intended path towards the destination.
How does the autonomous vehicle move? For any autonomous vehicle, the basic information is the HD map from the server. The HD map will have all the static information about the road. Similar to what a human driver sees in front of him and behind him through the rear view mirrors. Similarly based in the GPS coordinates, the vehicle will download the part of the road from the server. Now the road map is available and the vehicle can determine the geometry and other parameters of the road. On top of this, merge the dynamic map and obtain a fused map around the vehicle. Before the vehicle can move forward or backward, the Localize the vehicle with reference to the static objects. Why is the localization of the vehicles based on static map and not dynamic map? Dynamic map has objects that are moving constantly and not confined to any particular location (GPS coordinate). Hence, it is not advisable to localize the vehicle with respect to the dynamic map.
How does the vehicle get dynamic map? The dynamic map comprises of the all other dynamic objects around the vehicle like the pedestrians to other vehicles. The autonomous vehicle is equipped with camera and sensors, which will determine the moving and stationary objects around the car. The quality of sensors have gone up high in the recent past that they can give the dimension of each object around the vehicle. With the help of machine learning algorithms, the vehicle predicts the trajectory of the moving objects around it.
The fused map is now available with the vehicle. Next step for the vehicle is to plan the route to the destination. Similar to the navigational route provided by some of the map providers, google maps used commonly by everyone. The autonomous vehicle will have a route calculated to the destination similarly and in addition, the vehicle has to plan the route for every timestamp. Meaning, the vehicle has to consider the dynamic objects around it, the static objects for reference and navigate through them carefully without any mishaps. In case of a road construction or diversion that a traffic regulator signals standing on the road, the vehicle has to sense the same and plan to change lanes or take an exit. The autonomous vehicle must also read the dynamic road signs on the road to detect lane closure, accident and other dynamic events along the route. The autonomous vehicle should abide by the local traffic rules at all times, in terms of maintaining speed limit, driving on the proper lane, giving way to emergency vehicles, reading the traffic lights and everything that a human driver does. At every juncture or timestamp, the autonomous vehicle has to plan the path for the next position on the road. For the autonomous vehicle to plan the path efficiently, it should know the exact location of the vehicle on road at a given time.
Localization provides the exact position of the vehicle on the road with reference to some of the static objects. Only after knowing the exact position of the vehicle, the machine can decide its movement along the road. Say for example, if the vehicle is on the right corner of the road, the vehicle has to come onto the driving lane to move forward. With just the free space alone, the vehicle cannot decide and move forward. Localization helps to determine all the factors like the lane closure, non-drivable, or restricted to drive at regular speeds. The calculation of the lane information is mathematical and several filters like particle filter, kalman filter, etc are considered. Noise reduction and detection also plays an important role here. The filters reduce the noise and give an exact estimate for the calculations. What is Kalman Filter? Kalman filtering provides estimates of unknown variables given the measurements observed over time. Using linear models with Gaussian noises, Kalman filter provides optimal estimates. In case of autonomous vehicles, we will be dealing with landmark based maps i.e., the static map consists of objects like a traffic pole, road sign, mile marker or overhead signs on the road which are considered as landmarks. So Kalman filter is widely used over the particle filter, which is useful for feature-based maps.
The other difficulty for the localization is the coordinate system. The GPS signals of the static map are global coordinates and the vehicle can see the objects with respect to the vehicle or in other words, the vehicle coordinate system. Before we can associate any object on the map, we have to transform the position of the objects to a common or global coordinate system. The most common mathematical model used for the transformation is the “Transformation Vector” which is a 3-D representation of the Euclidean space in Cartesian coordinates.
The GPS coordinates determine the vehicle’s initial position on the map. This is not the localized position of the vehicle. On top of this, the localization algorithm helps to determine the exact position of the vehicle with reference to an object on the map. As the vehicle progresses on the road, the wheel odometry sensors determine the distance travelled by the vehicle with respect to the origin. The further positions are calculated in the Cartesian or global coordinate system surpassing the need to do the transformation for every time stamp.
Summarizing the points, “Localization” is to find the position of the vehicle at time (n) which is the best estimation based on the previous measurements, the sensor observations and the past trajectory of the vehicle. The sensor variations (noise) can be approximated using Gaussian distributions. The Kalman filtering is for the linear models and approximation of non-linear motions. For any autonomous vehicle, Localization is the foundation stone without which the navigation and path planning will not work. In short, without localization there is no autonomous vehicles.
About the Author:
Subramanya Prakash, Senior Engineer, Automated Cars, Mercedes Benz R&D India
With a Bachelor degree in Engineering and over 10+ years’ experience in the embedded SW development, I currently work for Mercedes Benz Cars in developing algorithms for the L2 and L3 Automated Cars.