Technique to automatically discover simulation configurations for behaviors hard to test

The research team led by Fuyuki Ishikawa at the National Institute of Informatics (NII, Japan) developed a technique to search automatically for simulation configurations that test various behaviors of 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 iterates trials on simulations using an optimization method called evolutionary computation so that it discovers simulation configurations that lead to specific features of driving behaviors such as high acceleration, deceleration, and steering operation. The outcome of this research was presented in ICST 2021 (*2), a flagship conference on software testing held during April 12-16 2021.

Background

More attention is being focused on automated driving systems (ADS) or advanced driver assistant systems. New car models with Level 3 of autonomous driving are emerging, ones that do not require human drivers to supervise the driving operation under certain conditions. 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 use of ADS in environments with enormous situations such as urban areas.

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. A typical approach is that human testers enumerate scenarios. An example is “the ego-car is going to take a right turn, but a car is approaching from the opposite direction.” However, the ADS behavior can differ in the same right turn scenario, for example, either taking a turn without the need for braking or decelerating and waiting for a long time before taking the turn. It is essential to check different behaviors the ADS can take before utilizing it in society. However, specific behaviors such as long deceleration are unlikely to occur when we just run many simulations under configurations with different positions of other cars and so on. Moreover, the ADS has more possible specific behaviors, for example, simultaneous occurrences of strong acceleration and high amounts of steering operation. Configuring simulations to cause such specific behaviors intentionally is very difficult.

Research Method and Outcome

In this research, we proposed a technique for test generation that automatically searches for simulation configurations leading to specific features of driving behaviors such as high acceleration and deceleration and high amounts of steering operation. We use an optimization technique called evolutionary computation, which repeats simulation trials to adjust configurations so that specified driving behaviors last for a long period of time. In this way, the technique can discover simulation configurations, such as the positions of other cars, leading to the desired features of driving behaviors.

The proposed technique also avoids only generating simulation configurations that only lead to dangerous situations such as collisions. Therefore, it reveals features of driving behaviors not limited to emergency situations. In addition, it can search for and trigger combinations of behaviors such as simultaneous occurrences of high acceleration and high amounts of steering operation.

We applied and evaluated the test generation technique to a program of path planning offered by Mazda (*3). The technique could generate specific behaviors that were rarely caused in random simulations. For example, it generated strong acceleration together with high amounts of steering operation as well as high acceleration following high deceleration in a scenario for a right turn at an intersection. These cases occurred only with very specific timings of other cars entering the intersection. In this way, we showed the technique can intentionally trigger combinations of specific behaviors using simulation configurations that are very difficult for human engineers to design.

Future outlook

This research was conducted in the JST ERATO-MMSD project. In the project, we investigated other techniques for discovering simulation scenarios that lead to crashes (*4), techniques that explain the causes of crashes (*5), and techniques that fix the behaviors to avoid the detected crashes (*6). The research this time was to increase confidence in the system safety by checking “various situations,” in addition to the techniques for detecting and fixing problematic behaviors. Thus, we established a comprehensive approach for testing of ADS with both tests for detecting problems and tests for checking diverse cases, which have been done for conventional software programs.

Late 2020 featured a competition for test generation tools on advanced driver-assistance systems (ADAS) (in conjunction with the SBST Workshop (*7) to be held in May 2021). The ERATO-MMSD project submitted a tool called Frenetic (*8) to the competition. Frenetic made significant results in terms of the rates of generated failure cases and their diversity. This exactly came from the aforementioned research experience.

We provided comprehensive testing techniques for ADS. Although we used the program provided by Mazda in our evaluations, the techniques are generic and can be tailored for the specific demands of each automotive company. For example, we can adjust the techniques to the emerging framework called responsibility-sensitive safety proposed by Intel and Mobileye. We will endeavor to make our techniques available by tailoring them for emerging international standards as well as the demands from each automotive company.

Comment by Fuyuki Ishikawa

“We have conducted active research on the path-planning component through collaboration with Mazda. We have established a holistic set of testing and debugging techniques, including the aforementioned one, by adapting techniques for conventional program code. The key of these techniques is to search for solutions such as “desirable tests” and “desirable fix actions.” We will extend and empirically validate the techniques given emerging standards as well as different demands in each ADS application.”

###

About the National Institute of Informatics (NII)

NII is Japan’s only academic research institute dedicated to the new discipline of informatics. Its mission is to “create future value” in informatics. NII conducts both long-term basic research and practical research aimed at solving social problems in a wide range of informatics research fields, from fundamental theories to the latest topics, such as artificial intelligence, big data, the Internet of Things, and information security.

As an inter-university research institute, NII builds and operates academic information infrastructure essential for the research and educational activities of the entire academic community (including the Science Information Network) as well as developing services such as those that enable the provision of academic content and service platforms.

(*1) ERATO Hasuo Metamathematics for Systems Design Project (ERATO-MMSD): a project funded in the Exploratory Research for Advanced Technology (ERATO) scheme of the Japan Science and Technology Agency (JST). The project conducts academic research for quality assurance of cyber-physical systems as the core of Society 5.0. The project specifically focuses on automated driving systems and investigates reliability techniques for modeling, formal verification, testing, and holistic, practical V&V techniques including all of them. This challenge requires tight 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.

https:/

/

www.

jst.

go.

jp/

erato/

hasuo/

en/

(*2) ICST 2021: IEEE International Conference on Software Testing, Verification and Validation 2021. Given an “A” in the CORE ranking for international conferences in the computer science area.

(*3) The model we examined is a prototype for research evaluations, and its quality does not have any relationship with the quality of the actual products.

(*4) Alessandro Calò, Paolo Arcaini, Shaukat Ali, Florian Hauer, 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

(*5) Xiao-Yi Zhang, Paolo Arcaini, Fuyuki Ishikawa, 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

(*6) Alessandro Calò, Paolo Arcaini, Shaukat Ali, Florian Hauer, 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

(*7) The 14th International Workshop on Search-Based Software Testing:

https:/

/

sbst21.

github.

io/

(*8) Frenetic: a tool to generate diverse road structures as test scenarios for lane keeping functionality