News Release

Automated Technique to Efficiently Discover Severe Problems in Automated Driving Systems:
-- Investigating Potential Problems and Efficiently Searching for Likely Problems --

 The research team led by ISHIKAWA Fuyuki at the National Institute of Informatics (NII, Japan) developed an automated technique to efficiently search for simulation configurations that lead to severe situations in automated driving systems. This research was conducted under the ERATO-MMSD project (*1) funded by the Japan Science and Technology Agency (JST, Japan). The proposed technique excludes unlikely problems in each specific scenario, such as overtaking and right turn, during iterations of searching for severe problems. The technique can thus efficiently discover situations in which severe problems occur, such as simultaneous occurrence of high acceleration and high amounts of steering operation. The outcome of this research was presented at ASE 2021(*2), a flagship conference on automation in software engineering (November 16 2021).


 Automated driving systems (ADS) and advanced driver assistant systems are increasingly attracting attention. New car models with driving automation Level 3, which does not require human drivers to supervise the driving operation under certain conditions, are emerging. However, the ADS functionality being put into practical use is limited to specific situations such as traffic jams on highways or fixed routes. Increases in safety and reliability are required for the use of ADS in environments with complex situations, such as urban areas. In the JST ERATO-MMSD project, we have been investigating techniques for discovering simulation scenarios that lead to crashes(*3), techniques that explain the causes of crashes (*4), techniques that fix the behaviors to avoid the detected crashes(*5), and techniques that detect situations that lead to specific driving behavior such as high acceleration even without any danger(*6).

 One of the key functions in ADS is path planning, which continuously updates the direction and speed by examining the surrounding environment (including other cars and pedestrians). The path-planning functionality needs to handle not only safety but also multiple other aspects such as the extent of acceleration/deceleration, steering operation, and lane conformance.

 Simulation-based testing is commonly used for ADS but it requires the enumeration of countless possible scenarios in a comprehensive way. An example is "the ego-car is going to take a right turn, but another car is approaching from the opposite direction." However, the ADS behavior can differ in the same right-turn scenario: for example, it might take a turn without the need for braking, or it might decelerate and wait a long time before taking the turn. It is essential to check that different behaviors of the ADS do not lead to serious problems. Problems here refer to not only crashes but also uncomfortable situations with high acceleration or high amounts of steering operation, as well as traffic disturbance caused by driving too slowly.

 However, there is an enormous number of possible simulation configurations that must be dealt with, such as the positions of other cars even in one scenario of right turn. It is often impossible to detect simulation configurations that lead to problems by manually manipulating the configurations or automatically generating random configurations. Specifically, it is very difficult to discover simulation configurations in which serious problems occur due to combinations of multiple problems such as high acceleration and high amounts of steering operation. Moreover, some situations never occur in a certain scenario. For example, too much lateral acceleration is unlikely to occur in an overtaking scenario. This point suggests it is meaningless to simply increase the number of simulations to comprehensively search for all potential problems in each scenario by making all the possible queries such as "How strong is the lateral acceleration in the overtaking scenario?" and "Is there too much speed in the right-turn scenario?".

Methods and Results

 In this research, we proposed a technique to search for simulation configurations that lead to severe problems such as too high acceleration, crash or near-crash, and even their combinations while identifying specific types of problems that are unlikely to occur with any configurations. We could thus increase both the significance and the efficiency of the test search on top of our existing research.

As the baseline approach, we use an optimization technique called evolutionary computation(*7) that iterates simulation trials while adjusting the simulation configurations to trigger the target problem under search. The core idea of this research is to automatically review and update the search target--continuously, during the iterations of search--by analyzing the search history for efficient discovery of more serious, composite problems.

The proposed technique starts with searching for simulation configurations that cause the most severe problems in the target system. The common setting is to consider crashes as the most severe, especially if combined with too high speed or too high amounts of steering operation. The search target, i.e., which problems to search for, is then reviewed and updated by analyzing the search history after a certain amount of searching is done. Specifically, the priority is decreased if problems have been set as the search target and had reasonable search effort, but no configuration was found to cause the problem. In contrast, the priority is increased for problems that have not been considered intensively as the search target, or problems that are more severe and close to situations discovered so far. The proposed technique can capture the characteristics of the scenario under analysis, such as overtaking or right turn, by iterating this update procedure of the search target. As a result, we can avoid spending too much time in searching for simulation configurations to cause problems that cannot occur in the scenario under analysis. The technique can therefore efficiently discover simulation configurations that cause more serious problems, often composed of multiple problems such as too high speed or too high amounts of steering operation.


Fig 1: Overview of proposed technique


We applied the test generation technique to a path-planning program offered by Mazda for evaluation(*8). Results showed that the proposed technique could discover simulation configurations that led to severe problems, including composite ones, more efficiently.

Future outlook

 The techniques investigated in the ERATO-MMSD project so far are generic and can be tailored to specific demands and operation environments for individual automotive companies. For example, it is possible to apply our techniques with the RSS framework (responsibility-sensitive safety)(*9). We envision tailoring our technique through customization for specific safety evaluation aspects and operation environments given emerging international standards and the unique demands of individual automotive companies.

Comment by ISHIKAWA Fuyuki

"As part of the ERATO-MMSD project, we have conducted many research studies on the prototype program of the path planner provided by Mazda. One of our key focus areas is testing and debugging techniques, and we have adapted techniques from traditional program coding to ADS. The obtained techniques provide effective and efficient ways to search for solutions that match the specific demands of tests or repair operations. We will disseminate and demonstrate the techniques according to different demands based on emerging standards and various domains of ADS. We will also expand the scope of our research to examine sensing (object detection) aspects in addition to path planning along with another ongoing project "eAI"(*10)."


 This research has been made possible thanks to the support of the Japan Science and Technology Agency's ERATO-MMSD (JPMJER1603). We used a program of path planning offered by Mazda.

Information on Paper

Title: Targeting Requirements Violations of Autonomous Driving Systems by Dynamic Evolutionary Search
Authors: Yixing Luo, Xiao-Yi Zhang, Paolo Arcaini, Zhi Jin, Haiyan Zhao, Fuyuki Ishikawa, Rongxin Wu, Tao Xie
Posted: The 36th IEEE/ACM International Conference on Automated Software Engineering (ASE 2021)
Announce date: 16th November 2021, Australian Time

Related Link

News Release: PDF

Automated Technique to Efficiently Discover Severe Problems in Automated Driving Systems:
-- Investigating Potential Problems and Efficiently Searching for Likely Problems --

  • (*1) ERATO Hasuo Metamathematics for Systems Design (ERATO-MMSD): a project funded by the Exploratory Research for Advanced Technology (ERATO) scheme of the Japan Science and Technology Agency (JST). The project conducts academic research for the quality assurance of cyber-physical systems that make up the core of Society 5.0. The project specifically focuses on automated driving systems and investigates reliability techniques for their modeling, formal verification, and testing, along with holistic and practical V&V techniques. This challenge requires the close collaboration of different academic areas such as software science and engineering, control theory and engineering, and artificial intelligence. Therefore, the project also focuses on (meta)mathematical theories.
  • (*2)ASE 2021: The 36th IEEE/ACM International Conference on Automated Software Engineering. This conference is given the highest rank “A*” in the CORE ranking for international conferences in the computer science area.
  • (*3)Alessandro Calò, Paolo Arcaini, Shaukat Ali, Florian Hauer, and Fuyuki Ishikawa, Generating Avoidable Collision Scenarios for Testing Autonomous Driving Systems, The 13th IEEE International Conference on Software Testing, Verification and Validation (ICST 2020 Industry Track), pp. 375–386, March 2020.
  • (*4)Xiao-Yi Zhang, Paolo Arcaini, Fuyuki Ishikawa, and Kun Liu, Investigating the Configurations of an Industrial Path Planner in Terms of Collision Avoidance, The 31st International Symposium on Software Reliability Engineering (ISSRE 2020, Research Track — Practical Experience Reports), pp. 301–312, October 2020.
  • (*5)Alessandro Calò, Paolo Arcaini, Shaukat Ali, Florian Hauer, and Fuyuki Ishikawa, Simultaneously Searching and Solving Multiple Avoidable Collisions for Testing Autonomous Driving Systems, The Genetic and Evolutionary Computation Conference (GECCO 2020), pp. 1055–1063, July 2020.
  • (*6)Paolo Arcaini, Xiao-Yi Zhang, and Fuyuki Ishikawa, Targeting Patterns of Driving Characteristics in Testing Autonomous Driving Systems, IEEE International Conference on Software Testing, Verification and Validation (ICST 2021 Industry Track), pp. 295–305, April 2021.
  • (*7)Evolutionary computation: It refers to techniques to obtain optimal solutions by iterative improvement, similar to the evolution process of natural life (e.g., mutation and crossover).
  • (*8)The model we examined is a prototype for research evaluation, and its quality does not have any relationship with the quality of the actual products.
  • (*9)Responsibility-Sensitive Safety: a scheme that defines the minimum rules that must be satisfied by ADS. Standardization activity is ongoing in the IEEE (Institute of Electrical and Electronics Engineers).
  • (*10)“eAI”: a research project supported by the JST-Mirai program "Super Smart Society (Society 5.0)" mission area. This project aims at developing engineering techniques for AIs, specifically with deep learning techniques, that can meet the fine-grained demands for safety and reliability of ADS. “Engineerable AI Techniques for Practical Applications of High-Quality Machine Learning-based Systems”.

※This is a joint news release by the National Institute of Informatics(NII) and the Japan Science and Technology Agency (JST).