Introduction

Autonomous vehicles promise safer and more efficient transport. There are different levels of autonomy: the lowest is driver assistance, the highest is fully automated driving. In level 1, the driver is assisted, for example by anti-lock braking system (ABS) and cruise control. In level 2, the vehicle is equipped with lane correction and parking assistance. With level 3, the vehicle is capable of being autonomous in certain situations, such as overtaking on highways. For levels 4 and 5, the vehicle is capable of driving without human intervention. Autonomous vehicles must guarantee the safety of passengers and other road users in complex and unpredictable environments.

One of the most important aspects of autonomous car safety is the implementation of high-performance collision avoidance algorithms. On the road, events are unpredictable and the vehicle must be able to react to all situations.

This article explores the implementation of collision avoidance algorithms, how they work and how they are regulated. It will also detail the constraints associated with implementing these algorithms in real-time systems, as well as safety standards specific to autonomous vehicles.

Algorithmic strategies for collision avoidance

Collision avoidance is a major challenge for autonomous vehicles. Several algorithms are available to manage these critical situations.

Basic obstacle avoidance

The simplest way to avoid an obstacle is to go around it. There is a simple algorithm for getting around an obstacle: the bug algorithm.

The bug algorithm can be decomposed into three steps:

  1. Advance towards the target: The vehicle moves in a straight line towards the target.
  2. Avoiding the obstacle: As soon as the obstacle is detected in the vehicle’s path, the vehicle passes along the obstacle.
  3. Finding the shortest path: While driving along the obstacle, the vehicle calculates the distance separating it from the target. When the path to the target has a minimum distance, the vehicle leaves the bypass path and returns to the path to the target.

To illustrate this algorithm, we will take the example of a robot vacuum cleaner using the bug algorithm. It is trying to move towards the kitchen when it encounters a sofa. The robot follows the sofa so that it can go towards the kitchen.

Illustration of the bug algorithm for a robot vacuum cleaner avoiding a sofa

The bug algorithm is very simple to use and does not require a lot of computing power, but it is not the most optimized and does not follow the shortest path. There are more efficient algorithms, such as the algorithm based on elastic band theory.

Collision avoidance algorithm based on elastic band theory

The collision avoidance algorithm based on elastic band theory is based on a physical analogy, it modifies a previously defined trajectory (the elastic band) by taking into account of internal and external forces to avoid obstacles.

General concept :

We have a direct initial path between the start point Ps and the end point Pa. This path is represented by a deformable band.

Internal forces act like spring forces, to keep the trajectory close to the original one. They ensure that the vehicle follows the smoothest, most efficient trajectory possible.

This force is represented by a spring law:

$$ \begin{aligned} F_{int, i} = k_s(u_{i+1}-u_i) \end{aligned} $$

where

  • $F_{int, i}$ is the internal force acting on the $i^{th}$ point
  • $u_i$ is the position of the $i^{th}$ point
  • $u_{i+1}$ is the position of the $(i+1)^{th}$ point
  • $k_s$ is the spring constant

This force pulls each point towards its neighbour to keep the strip as short and straight as possible.

External forces distort the trajectory to move it away from detected obstacles, acting as repulsive forces. The closer an obstacle is, the stronger the repulsive force becomes.

This force is represented by:

If $||r_i|| < r_o$

$$ \begin{aligned} F_{ext, i} = -k_e(||r_i||-r_o)\frac{r_i}{||r_i||} \end{aligned} $$

Otherwise

$$ \begin{aligned} F_{ext, i} = 0 \end{aligned} $$

where

  • $r_i$ is the position vector between the obstacle and the $i^{th}$ point
  • $r_o$ is the threshold distance
  • $k_e$ is the external force constant

The algorithm continuously adjusts the shape of this band according to the forces applied, so that the trajectory remains safe and drivable.

Illustration of the elastic band

The figure above is only an illustration of the elastic band, the proportions of the forces are not respected.

The algorithm follows these steps:

  1. Obstacle detection: The vehicle’s sensors detect obstacles in the environment and estimate their position, speed and trajectory.
  2. Calculation of external forces: Based on the sensor data, the algorithm calculates the repulsive force applied by each obstacle to the elastic band.
  3. Deformation of the elastic band: Under the combined effect of the internal and external forces, the elastic band deforms, generating a new trajectory that bypasses the obstacles while remaining as close as possible to the initial trajectory.
  4. Validating the trajectory: Before applying the new trajectory, the algorithm checks that it is safe and possible. In the case of an autonomous car, the lane must not go off the road, cross prohibited zones or come into conflict with other cars. If the trajectory is validated, the vehicle adopts it to avoid obstacles. If no safe trajectory is found, the vehicle can initiate emergency braking.

Example :

A car brakes suddenly in front of the vehicle. The algorithm detects this car as an obstacle, and the elastic band deforms to avoid collision by searching for a free lane to the side. If the space to the side is insufficient, the algorithm triggers emergency braking, otherwise it slows the vehicle down and moves it safely to the side.

Using machine learning for collision avoidance

Machine learning is increasingly being used in collision avoidance.

One of the main advantages of machine learning is its ability to analyze and learn from a wide range of scenarios, both real and simulated. Unlike conventional avoidance algorithms, which follow predefined rules, machine learning based avoidance systems improve over time. Trained models can generalize from the data they have trained with to predict future events. On the other hand, if the model is not trained with a quantity of data that covers a wide variety of scenarios, it may underperform in unusual situations.

Uber ATG (Advanced Technologies Group) is using machine learning for their autonomous vehicles. You can check out their article on version management for their machine learning models on their blog. These models predict the movements of other vehicles, pedestrians and cyclists. They can also plan optimal routes for their own vehicles and identify potentially dangerous situations.

Machine learning brings with it a degree of non-transparency. Unlike traditional algorithms, where every decision can be traced and explained, machine learning based systems are opaque, making it difficult to understand the decisions taken by the algorithm to avoid a situation.

Implementing algorithms in real-time systems

Collision avoidance algorithms in autonomous vehicles require latency-free execution. The system must ensure a rapid response.

Real-time constraints

To ensure vehicle safety, collision avoidance systems are subject to strict time constraints. A few seconds of latency can be enough to miss the avoidance maneuver. A real-time system must be able to give a correct result within a limited timeframe, to ensure that there is no old and incorrect data. The time scale depends on the environment in which the system operates. In the case of autonomous vehicles, it is generally in the millisecond range. The various tasks are prioritized according to their criticality. Collision avoidance is a high-priority task, and must be able to run before checking the washer fluid level.

Data acquisition

Collision avoidance algorithms need a large amount of data on the environment and on the vehicle in order to determine the best solution.

Autonomous vehicles use different types of sensors to perceive the environment.

  • Lidar (laser detection): measures the distance between two objects to determine their location
  • Cameras: identify obstacles and road markings
  • GPS: provides both global and precise positioning
  • Radar: detects moving objects and determines their speed

Sensor on autonomous vehicle Image source : https://www.generationrobots.com/blog/fr/lidar-ouster-une-technologie-cle-pour-lavancement-des-vehicules-autonomes/

The various data are processed and grouped together. Sensors are not without fault so data processing algorithms take into consideration possible margins of error. It is also possible to have redundant sensors to compensate in the event of one sensor being obstructed.

Adapting collision avoidance algorithms to real-time systems for autonomous vehicles is an important task, and these algorithms need to be efficient, fast and accurate. Collision avoidance algorithms are one of the highest priority tasks, as they require fast execution to guarantee a quick response. In addition, using sensor data, the system builds a simplified model of the environment, which is easier to work with.

Standards and regulations for autonomous vehicle safety

Safety standards for autonomous vehicles

Collision avoidance requires obstacle detection. Obstacle detection for autonomous vehicles is regulated by UL 4600. The UL4600 technical standard is not available for free, but in the news section of the Underwriters Laboratories (UL) website we can find an overview.

The UL 4600 standard is specifically dedicated to autonomous systems without human supervision. This standard requires effective detection technology. In order to comply with this standard, the vehicle must demonstrate that analysis, simulation, controlled environment testing and public road testing have been completed, both for the initial version of the vehicle and for each software update.

UL 4600 is not the only standard for autonomous vehicles. There are also:

  • ISO 26262 guarantees that vehicle electronic systems achieve a certain level of functional safety.
  • ISO 21448 guarantees that systems operate safely in normal and unexpected conditions.
  • ISO 21434 focuses on vehicle cybersecurity.

Test methodology and validation

The validation of collision avoidance algorithms is very important for guaranteeing the safety of autonomous vehicles.

Hardware-in-the-loop (HIL) simulation

HIL simulation is a technique used to validate embedded systems. It consists of connecting real hardware components, such as the vehicle’s computers, to a simulation environment. This technique enables tests to be carried out in a controlled and reproducible environment, without the risks and costs of road tests.

HIL simulation makes it possible to test software and hardware at an early stage of development and to simulate dangerous scenarios that would be too dangerous to test on the road.

Test methodology

Collision avoidance algorithms are tested in 3 different ways:

  1. Simulation tests

Simulation tests allow testing the system on a large number of scenarios. A large number of different situations can be simulated in a short space of time. They can also be used to test scenarios with dangerous conditions, such as very high speeds.

  1. Closed road testing

Closed road tests allow testing the system in a more real world environment, such as a test track. These tests do not compromise the safety of the other users. They also allow us to test the data received from the sensors.

  1. Tests on open roads

The final validation phase consists in testing the system on open roads with real traffic conditions. Then we compare the autonomous system’s performance with that of a real, attentive, non-disabled human driver. This verifies that the system matches or exceeds the human ability to avoid collision.

Conclusion

Collision avoidance is a crucial factor in the safety of autonomous vehicles, which are confronted with complex and unpredictable environments. Algorithms based on elastic band theory and machine learning offer promising solutions for collision avoidance.

Implementing these algorithms in real time environments requires particular attention to speed of execution, reliability and safety. Since autonomous vehicles can potentially be dangerous to other road users, they must meet strict constraints and comply with safety standards such as UL4600.

To guarantee a high level of reliability, collision avoidance algorithms are tested in simulations, on closed roads and on open roads. The evolution of these technologies is increasing the safety of autonomous vehicles and other people.

Bibliography