All Tom cruise fans would remember scenes from the movie minority report where a Self driving car chases him all around the city. At that point in time, it seemed futuristic and fiction for many people. Today it’s not futuristic and it is definitely not fiction anymore. A self-driving car, also known as a robot car or driverless car is a vehicle that is capable of sensing its environment and moving with little or no human input. Try closing your eyes and walking in a closed room by listening to instructions from your friend, extremely tough to stay on the right course isn’t it? The task to make a Self-driving car work is much more complex and involves a lot of precision.
Why go for Self-driving cars?
To be factual, the full-scale benefits and the costs associated with these Self-driving cars are largely hypothetical today. The impact of Self-driving cars on the environment, economy, safety, and public health cannot be directly established, a lot of information is needed to arrive at conclusions. But the projected benefits are the reason behind the pursuit of the idea.
Safety: Year on year the number of people who die in motor vehicle crashes is increasing rapidly. Hypothetically Self driving cars could bring these numbers down as algorithm driven software could be less prone to errors and more accurate in following the traffic rules.
Equity: Self-driving cars can mobilize those people who cannot drive by themselves such as elderly or disabled.
Shipping and delivery: The shipping and delivery industry is expected to benefit the most from these cars as human-centric concerns like hunger, fatigue of the drivers, etc. would reduce shipping and delivery times considerably.
Apart from the above-explained benefits there are many other expected benefits like energy conservation and Increase in productivity etc.
Self-driving cars and their complexity
Humans are built to process so much information and data very quickly and make a logical decision in a split second. Consider the case of walking or even driving a car where with a single plain sight human brain intuitively processes the distance between the obstacles, current position, the shortest route to the destination and follows it to the destination. In case of any sudden change in these parameters humans reprocess and reassess and adjust accordingly. All of this is done effortlessly and quite easily by most of the humans.
While it is so simple for humans, a self-driving car has to develop a sense of vision, understand the position and keep assessing this till the destination is reached. The entire cycle has to be really fast to be anywhere near the speed of a human being. This requires a lot of high sensitivity equipment, efficient algorithms, and quick data processing and thus arises the complexity.
How do self-driving cars work!
The three major processes involved here are
a) mapping and localization,
b) obstacle avoidance and
c) path planning.
Although different manufacturers can use different sensor suites and algorithms depending on their unique cost and operational constraints, the processes across vehicles are similar.
Mapping & Localization
Before making any navigation decisions, the vehicle needs to understand the map of the surrounding and precisely locate itself in the map. A laser range finder (LIDAR-Light detecting and ranging devices) is generally used to scan the environment. The mapping is done on the basis of time taken by the laser to reach the object and travel back. Why use a laser range finder when a video camera can do the job? The answer to the question is very simple. A video camera is simple to extract the scene and build a 2D environment but using laser range finders the depth of the scene is readily available to build a 3D map. The vehicle filters and discretizes data collected from each sensor and often aggregates the information to create a comprehensive map, which can then be used for path planning.
An example of a Google car’s internal map at an intersection tweeted by Idea lab founder Bill Gross. Gross claims that Google’s Self-Driving Car gathers almost 1 GB of data per second.
Laser beams diverge as they travel long distances and hence it gets very difficult to get accurate readings greater than 100m. For the vehicle to know its relative position it has to use its GPS. GPS estimates can be off by many meters due to undesirable atmospheric conditions, reflections from buildings and accumulated position error over a period of time.
Uber’s self-driving prototypes use sixty-four laser beams, along with other sensors, to construct their internal map; Google’s prototypes have, at various stages, used lasers, radar, high-powered cameras, and sonar. No single sensor is sufficient for the safe running of the car. The algorithm uses data from all the sensors and uses it along with pre-built road users and their behaviour patterns and commonly used traffic signals. For example, its speculated that Google’s self-driving cars can successfully identify the biker extend his arm to make a manoeuvre and successfully slow down enough for the biker to pass.
Obstacles are defined in the library with predefined shape and motion descriptors. The vehicle uses a probabilistic model to track the predicted future path of moving objects based on its shape and prior trajectory. For example, if a two-wheeled object is traveling at 40 mph, it is most likely a motorcycle and not a bicycle and will get categorized accordingly by the vehicle. The information like the previous, current and future locations of all the obstacles in vehicles vicinity help in taking the right course of action. This process shall help in smarter decision making especially in busy intersections.
Path planning as the name indicates uses the information processed in the above stages to plan a safe path avoiding the obstacles while following road rules to the destination. Different manufacturers can have different algorithm strategies based on the objectives, the kind of equipment used etc. The algorithm generally has a long-range plan and a short-range plan. The short-range plan keeps getting updated dynamically based on the obstacles and their movement. Based on the short-range plan the long-range plan gets updated. Once the path is defined based on the speed, safety and time requirements the instructions are passed to on-board processors and actuators. Altogether, this process takes on average 50ms, although it can be longer or shorter depending on the amount of collected data, available processing power, and the complexity of the path planning algorithm. The process of localization, mapping, obstacle detection, and path planning is repeated until the vehicle reaches its destination.
Control & Execution:
As the name suggests this step refers to the execution of the path plan made earlier. The path can be broken into position (x, y), an angle (yaw- a yaw is rotation is the movement around yaw axis of a rigid body) and a speed(v). The control algorithm generates instructions for the vehicle such as steering wheel angle or acceleration level while considering the constraints of the road, obstacles and wheel slip etc.
PID (proportional Integral derivative) algorithm helps execute the plan and exercise control over the vehicle. This is a very simple and preliminary algorithm that is used in the basic controller of a self-driving car. The PID controller calculates an error value. This error is the difference between actual and planned course of action. This value has 3 major components of error
a) P: Proportional component- This term applies to the correction proportional to the error. Depending on the frequency at which the algorithm calculates the error, the oscillation is more or less important. The coefficient indicates the degree of oscillation desired.
b) D: Derivative component – The PD component understands that the error decreases and slightly reduce the angle it adopts to approach a smooth path.
c) I: Integral component – This I component is the result of accumulated error over a time because of the mechanical error that causes to turn vehicle a little more or less and thus an integral component is added to the earlier components to adjust the error.
The PID controller algorithm is simplistic and used for standalone cases. It is difficult to add lateral and longitudinal controls. When humans drive, they drive adjusting naturally to the size, mass, and dynamics of the vehicle. To replicate these more complicated controllers (MPC- Model predictive control etc.) are being developed and used.
Role of Machine learning:
Machine learning algorithms are extensively used to find solutions to various challenges in the self-driving cars applications. The applications based on machine learning include speech and gesture recognition and language translation. Both supervised and unsupervised algorithms are used in the steps of mapping and localization, obstacle avoidance, path planning, and control and execution. The major areas where machine learning algorithms are used is rendering of surrounding environment and forecasting the changes that are possible to these surroundings. The machine learning algorithms broadly can be classified as decision matrix algorithms, cluster algorithms, and regression algorithms. One category of the machine learning algorithm can be utilized for multiple key areas. For example, the regression algorithms can be utilized for object localization as well as object detection or prediction of the movement.
Decision matrix algorithms: These algorithms identify the relationship between the sets of the data and then make a decision out of it. Whether a car needs to take a turn or decelerate to a level and continue for the turning is decided using these algorithms.
Regression algorithms: Adaptive boosting is a regression-based machine learning algorithm that is most commonly used in this area. It can be used for classification as well in certain applications. This an adaptive learning algorithm. To create a powerful learner adaptive boosting uses multiple iterations and thus the name adaptive. A new learner is added and the weights are adjusted so that it takes care of the example incorrectly classified in the previous rounds. The regression algorithms can be used for short path planning and long learning. Other regression algorithms that are used for self-driving cars are decision forest regression, neural network regression and Bayesian regression etc.
Hurdles in the path:
A fair number of scientists believe that these cars can generate as much as 1GB data per second. Theoretically speaking this would amount to Petabytes of data generated per year by a normal car. Although all the generated information is not important the question problem posed is still unanswered. Another concern area is the current testing is confined entirely to pre-mapped areas and it’s very unsafe to do the test in an unmapped area. While the data problem may be solved but the threat of these vehicles getting hacked is very high and raises serious security concerns. Public acceptance, personal data usage and the threat of data privacy are still the biggest hurdles for the evolution of these vehicles.
https://medium.com/udacity/how-self-driving-cars-work-f77c49dca47e https://www.nytimes.com/2018/03/19/technology/how-driverless-cars-work.html https://www.hyundai.news/eu/technology/how-do-self-driving-cars-work/ https://robohub.org/how-do-self-driving-cars-work/
by VVNS Anudeep
PG IB 2017-19