日本ソフトウェア科学会第 37 回大会 (2020 年度) 講演論文集

Simultaneously Searching and Solving Multiple
Avoidable Collisions for Testing AutonomousDriving Systems – Extended abstract
Alessandro Calò, Paolo Arcaini, Shaukat Ali, Florian Hauer, Fuyuki Ishikawa
The oracle problem is a key issue in testing Autonomous Driving Systems (ADS): when a collision is found,
it is not always clear whether the ADS is responsible for it. Our recent search-based testing approachoﬀers a solution to this problem by defining a collision as avoidable if a diﬀerently configured ADS would
have avoided it. This approach searches for both collision scenarios and the ADS configurations capableof avoiding them. However, its main problem is that the ADS configurations generated for avoiding somecollisions are not suitable for preventing other ones. Therefore, it does not provide any guidance to automotive engineers for improving the safety of the ADS. To this end, we propose a new search-based approachto generate configurations of the ADS that can avoid as many diﬀerent types of collisions as possible. We
present two versions of the approach, which diﬀer in the way of searching for collisions and alternative configurations. The approaches have been experimented on the path planner component of an ADS provided
by our industry partner. This is the extended abstract of [8].

This is the extended abstract of paper [8].

sion [4] [5] [6] [2] [13] [9].
Irrespective of the type of testing approach, test-1 Introduction

ing of an ADS faces the oracle problem [1] [3]. For

An Autonomous Driving System (ADS) in anexample, if testing reveals a system execution in

integral part of autonomous cars, responsible forwhich the ego car (i.e., the car running the ADS)

planning and executing a safe and comfortable pathcollides, it is not always apparent whether theto a destination. Naturally, ensuring that an ADS

ego car should be held responsible for it, and,always plans and executes a safe path avoiding aeven if not, whether it could have behaved dif-collision is critical.

ferently in order to avoid it.

Search-based testing (SBT)

Although someis a popular approach to test an ADS under di-guidelines [12] [10] [11] have been proposed to defineverse environmental conditions, to ensure that dur-whether or not the ego car is responsible for a col-ing autonomous driving the ADS will not gener-lision, they cannot be used to assess whether theate and execute paths that will lead to a colli-

ego car could avoid the collision with a diﬀerent
behaviour.

Alessandro Calò, Technical University of Munich,Germany.
Paolo Arcaini, National Institute of Informatics,
Japan.
Shaukat Ali, Simula Research Laboratory, Norway.
Florian Hauer, Technical University of Munich,Germany.
Fuyuki Ishikawa, National Institute of Informatics,
Japan.

We recently proposed a more practical approachin [7]. It exploits the fact that ADSs are usuallyconfigurable and diﬀerent ADS configurations leadto slightly diﬀerent behaviours. In [7], a collision isdefined to be avoidable if the ADS configured in adiﬀerent way does not collide in the exact same scenario. The alternative configuration is said to solvethe collision, and it is referred to as its solution.

tionale is that the current system configuration isIn [7], we also proposed a search-based approachalready very well-thought-out by the experts, and(called the combined approach) in order to detectso it should not be changed too much, in order toavoidable collisions.

avoid to obtain weird behaviors of the car.

The main problem of the combined approach is

At the same time, the approach searches for col-that the solution (i.e., the alternative configura-lisions over n diﬀerent search spaces.

tion) found for a particular collision may be too

search space S, we define an objective function thatspecific, i.e., it may not solve other collisions thatassesses whether an avoidable collision has been

have been proven to be avoidable with diﬀerent con-found in S, or how close we are from finding it.

figurations. In this paper, in order to assess this, weWe identify two ways to consider these diﬀerent

have performed an experiment using the results weobjective functions:For eachobtained in [7]: we run the path planner over all the1. SSAMO : they are kept separate, each one

found collisions using all the found alternative con-constituting an objective of the multi-objective

figurations. We discovered that the solutions foundproblem (so, SSAMO is an (n+1)-objective

for one kind of collision can solve from 46.07% toproblem);

68.00% of other types of collisions. Therefore, the2. SSAAO : we define an objective function thatsolutions found by the combined approach tend toaggregates the objectives for all the diﬀerent

overfit a particular collision type and are not too

search spaces (so, SSAAO is a 2-objective prob-

useful for re-engineering the path planner.

lem). We propose two ways to define this function:

2 Proposed approaches
Starting from the needs of our industry partner,
we understood that it would be desirable to find a(a) SSAAO max : the fitness value is givenby the worst objective value across all thesearch spaces;

single configuration that solves multiple collisions(b) SSAAO sum : the fitness value is given

to better help the developers to improve the sys-by the sum of all objective values of alltem. Following this research direction, we propose

the search spaces.

two approaches that aim at finding configurations
which avoid as many collisions as possible. Both

2. 2 Two-stage approach

approaches continue to be based on evolutionary

The search space of SSA is very large, being thisalgorithms, as was done for the combined approachgiven by the combination of the n search spaces forin [7].

the diﬀerent scenarios and of the alternative configuration; therefore, SSA may suﬀer from scalability

2. 1 Single-stage approachissues. We then propose another approach, named

The first approach, named single-stage approach

two-stage approach (TSA), which aims at achieving(SSA), is the natural generalization of the combined

more scalability by decomposing the task in two

approach and aims at finding, at the same time, dif-stages. In the first stage, n combined searches (i.e.,

ferent collisions that can be avoided by the same al-applications of the combined approach from [7]) are

ternative configuration. The first objective of SSA

conducted for n search spaces in order to find naims at finding alternative configurations that areavoidable collisions. In the second stage, a single

not too diﬀerent from the original one. The ra-search is performed to find a configuration that si-表 1 Number of runs (out of 30) which avoid

objective values of all search spaces (SSAAO sum ).

j = 1, . . . , 7 types of collisionThis way, the search is given more information

collision types (j)Approach

The second method consists in aggregating allabout improvements in all 7 search spaces. This
1234567

worked better in the short term, because it defined

SSAAO max

0000000

a more “greedy” behavior, which was capable ofSSAAO sum

8400000

finding solutions for 2 scenarios in 4 cases.

SSAMO

920 10000T SAmin

000513 843. 2 SSAMO

T SAmax

000512 94The second strategy consisted in assigning eachsearch space to an individual search objective

multaneously solves all of them.

(SSAMO ). This proved to be better, being able
to find the solution for at least one collision of a3 Experimental results

search space in all 30 executions.

We run the two proposed approaches over theHowever, these results are still not acceptable forcombination of 7 diﬀerent search spaces (identify-

our aim of solving multiple collisions with a single

ing 7 types of scenarios). Experimental results arealternative configuration: there should be at least

reported in Table 1.

It shows in how many runsa few cases solving the majority of them. Looking(out of 30) each proposed approach solved j col-ahead at the results of the TSA, we see that this islisions (j = 1, . . . , 7) of diﬀerent types (i.e., frompossible.

diﬀerent search spaces), with the same alternative
configuration; note that each column represents an

3. 3 TSA

amount of collision types. The last column rep-

Being composed of two separate stages, the TSA

resents the best case, in which all seven avoidable

requires the selection of results from the first stage,collisions are solved. For example, SSAMO solves

which will be given as input to the second one.

two collisions (of two diﬀerent scenarios) in 20 runs.

At the first stage, the selection chooses a single
solution from the Pareto front, out of potentially

3. 1 SSAAO

many. Two straightforward selection criteria were

Regarding the SSA, the first strategy consisted

employed: taking the solution which minimizes thein aggregating the danger diﬀerences across all theconfiguration diﬀerence and the one which maxi-

scenarios, and two methods were investigated. Themizes it. The first one represents the collision which

first was to consider only the worst objective acrossis avoidable with the configuration closest to theall the search spaces (SSAAO max ). This method

original one, therefore being potentially the easiest

was not eﬀective at generating any favorable solu-one to solve. It will be denoted as T SAmin . The

tions within the allocated time budget. It is likely

second one represents the collision that requires thethat such a conservative approach is simply notbiggest change in weights to be avoided, therefore

suitable to handle such a complex problem in abeing potentially the most diﬃcult one to solve. It

timely manner. Indeed, since the fitness focuses

will be denoted as T SAmax . From the results in

exclusively on the worst objective value, the search

Table 1, we observe that the TSA is much moredoes not improve any other ones.

eﬀective than the SSA, as it is always able to solve

at least 4 collisions. From these results, it seems
that there is no significant diﬀerence between thetwo selection criteria.

Acknowledgments
P. Arcaini and F. Ishikawa are supported by ERATO HASUO Metamathematics for Systems Design Project (No. JPMJER1603), JST. Funding
Reference number:

10.13039/501100009024 ER-ATO. We thank our industry partner Mazda forproviding the software used as the target in ourwork and discussing principles in testing and improving complex real-world automotive systems.
The provided software is a prototype constructed
for the purpose of evaluating new testing methods
and its quality has no relation with the quality ofMazda products. Shaukat Ali is supported by theCo-evolver project (No. 286898/F20) funded by theResearch Council of Norway under the FRIPRO
program.
参 考 文 献[ 1 ] Barr, E. T., Harman, M., McMinn, P., Shahbaz,M., and Yoo, S.: The Oracle Problem in Software
Testing: A Survey, IEEE Transactions on Software
Engineering, Vol. 41, No. 5(2015), pp. 507–525.
[ 2 ] Ben Abdessalem, R., Panichella, A., Nejati,S., Briand, L. C., and Stifter, T.: Testing Autonomous Cars for Feature Interaction Failures Using Many-objective Search, Proceedings of the 33rdACM/IEEE International Conference on Automated Software Engineering, ASE 2018, New York,NY, USA, ACM, 2018, pp. 143–154.
[ 3 ] Briand, L., Nejati, S., Sabetzadeh, M., and Bianculli, D.: Testing the Untestable: Model Testing ofComplex Software-Intensive Systems, Proceedingsof the 38th International Conference on Software
Engineering Companion, ICSE 16, New York, NY,USA, Association for Computing Machinery, 2016,
pp. 789–792.

[ 4 ] Bühler, O. and Wegener, J.: Evolutionary functional testing of an automated parking system, Proceedings of the International Conference on Computer, Communication and Control Technologies(CCCT) and the 9th. International Conferenceon Information Systems Analysis and Synthesis(ISAS), 2003.
[ 5 ] Bühler, O. and Wegener, J.: Evolutionary functional testing of a vehicle brake assistant system, 6th
Metaheuristics International Conference, Vienna,Austria, 2005.
[ 6 ] Bühler, O. and Wegener, J.: Evolutionary functional testing, Computers & Operations Research,
Vol. 35, No. 10(2008), pp. 3144–3160.
[ 7 ] Calò, A., Arcaini, P., Ali, S., Hauer, F., andIshikawa, F.: Generating Avoidable Collision Scenarios for Testing Autonomous Driving Systems,2020 IEEE 13th International Conference on Software Testing, Validation and Verification (ICST),2020, pp. 375–386.
[ 8 ] Calò, A., Arcaini, P., Ali, S., Hauer, F., andIshikawa, F.: Simultaneously Searching and Solving Multiple Avoidable Collisions for Testing Autonomous Driving Systems, Proceedings of the 2020
Genetic and Evolutionary Computation Conference, GECCO20, New York, NY, USA, Association for Computing Machinery, 2020, pp. 1055–1063.
[ 9 ] Hauer, F., Pretschner, A., and Holzmüller, B.:Fitness Functions for Testing Automated and Autonomous Driving Systems, International Conference on Computer Safety, Reliability, and Security,Springer, 2019, pp. 69–84.
[10] Nister, D., Lee, H.-L., Ng, J., and Wang, Y.:
The Safety Force Field.
[11] Rizaldi, A., Keinholz, J., Huber, M., Feldle, J.,
Immler, F., Althoﬀ, M., Hilgendorf, E., and Nipkow,T.: Formalising and Monitoring Traﬃc Rules forAutonomous Vehicles in Isabelle/HOL, Integrated
Formal Methods, Polikarpova, N. and Schneider,S.(eds.), Cham, Springer International Publishing,
2017, pp. 50–66.
[12] Shalev-Shwartz, S., Shammah, S., and Shashua,
A.: On a Formal Model of Safe and Scalable Selfdriving Cars, CoRR, Vol. abs/1708.06374(2017).
[13] Vos, T. E., Lindlar, F. F., Wilmes, B., Windisch,A., Baars, A. I., Kruse, P. M., Gross, H., and Wegener, J.: Evolutionary functional black-box testingin an industrial setting, Software Quality Journal,
Vol. 21, No. 2(2013), pp. 259–288.