# An LLM-enhanced Multi-objective Evolutionary Search for Autonomous Driving
Test Scenario Generation

Haoxiang Tian  Institute of Software Chinese Academy of Sciences, University
of Chinese Academy of SciencesChina<EMAIL_ADDRESS>,
Xingshuo Han  Nanyang Technological UniversitySingapore
<EMAIL_ADDRESS>,  Guoquan Wu  Institute of Software Chinese Academy
of SciencesChina<EMAIL_ADDRESS>,  Yuan Zhou  Nanyang Technological
UniversitySingapore<EMAIL_ADDRESS>,  Shuo Li  ,  Jun Wei  ,  Dan Ye  ,
Wei Wang  Institute of Software Chinese Academy of SciencesChina lishuo19, wj,
yedan<EMAIL_ADDRESS>and  Tianwei Zhang  Nanyang Technological
UniversitySingapore<EMAIL_ADDRESS>
###### Abstract.

The safety of Autonomous Driving Systems (ADSs) is significantly important for
the implementation of autonomous vehicles (AVs). Therefore, ADSs must be
evaluated thoroughly before their release and deployment to the public. How to
generate diverse safety-critical test scenarios is a key task for ADS testing.
This paper proposes LEADE, an LLM-enhanced scenario generation approach for
ADS testing, which adopts the LLM-enhanced adaptive evolutionary search to
generate safety-critical and diverse test scenarios. LEADE leverages LLM’s
ability in program understanding to better comprehend the scenario generation
task, which generates high-quality scenarios of the first generation. LEADE
adopts an adaptive multi-objective genetic algorithm to search for diverse
safety-critical scenarios. To guide the search away from the local optima,
LEADE formulates the evolutionary search into a question & answering task,
which leverages LLM’s ability in quantitative reasoning to generate
differential seed scenarios to break out of the local optimal solutions. We
implement and evaluate LEADE on industrial-grade full-stack ADS platform,
Baidu Apollo. Experimental results show that LEADE can effectively and
efficiently generate safety-critical scenarios and expose 10 diverse safety
violations of Apollo. It outperforms two state-of-the-art search-based ADS
testing techniques by identifying 4 new types of safety-critical scenarios on
the same roads.

Autonomous Driving System, Simulation Test, Scenario Generation

††ccs: Software Testing, Validation and Verification, Reliability and Safety

##  1\. Introduction

The safety and reliability of Autonomous Driving Systems (ADSs) are
significantly important for the development and implementation of autonomous
vehicles (AVs) (bertoncello2015ten, ). It is essential to perform thorough
testing on ADSs before deploying them in the real world (barr2014oracle, ).
This process requires large amounts of diverse and comprehensive traffic
scenarios. However, testing AVs on public roads takes huge costs and can
increase the risk of accidents. Alternatively, simulation testing can create
large amounts of test scenarios with extremely low costs, which has been
widely used in ADS testing. Currently, about 90% of ADS testing is completed
through simulation platforms, 9% is completed at the test sites, while only 1%
is completed through actual road testing (zofka2015data, ).

Due to the complexity of real traffic, the ”long-tail” problem stands as the
primary restriction to the practical implementation of autonomous driving
(singh2021autonomous, ): despite existing technologies have achieved
autonomous driving capabilities for over 90% of scenarios, their realization
in public roads remains unattainable without addressing the remaining 10% of
long-tail scenarios (chen2023end, ). Therefore, how to generate diverse
safety-critical test scenarios to solve the long-tail problem is a key task
for AV testing.

The conventional scenario generation strategy is to simulate naturalistic
driving environments (nhtsa_pre_crash, ; feng2021intelligent, ). However, due
to the rareness of safety-critical events under naturalistic conditions, it is
difficult to thoroughly find safety violations of ADSs from the test scenarios
generated by simulating the public traffic driving environments. To address
this issue, researchers have proposed new approaches to generate safety-
critical test scenarios for ADSs, which can be broadly classified into two
categories. The first kind of approach is traffic accident-based scenario
generation, which reproduces traffic accidents from crash databases to test
the ADSs (10.1145/3338906.3338942, ; bashetty2020deepcrashtest, ;
althoff2018automatic, ; zhang2023building, ). However, these test scenarios
are simple and fixed. The tested ADSs may perform well in these tests, but
their performance under broader conditions may not be adequately assessed.

The second kind of approaches, which is more promising, is the search-based
scenario generation (harman2007automated, ; harman2012search, ;
mcminn2004search, ; thibeault2021psy, ). The key idea is to extensively search
for safety-critical scenarios in the simulation space (koren2018adaptive, ;
guo2024semantic, ; ben2016testing, ; tian2022generating, ; onieva2015multi, ;
kluck2019genetic, ; li2020av, ; tian2022mosat, ). Many of these approaches
adopt the genetic algorithm to generate critical scenarios. Generally, the
search process is divided into three steps: 1) randomly initialization to
create scenarios of the first generation; 2) evaluating each generated
scenario with a defined fitness function; 3) selecting high-quality scenarios
to conduct variation operators to generate new scenarios. This strategy has
demonstrated high capability in discovering new safety-critical scenarios for
ADS testing.

However, search-based scenario generation also exposes two challenges, which
are not well addressed in prior studies. C1: The random initialization of
first generation scenarios highly affects the efficiency of the evolutionary
search for critical scenarios. The quality of first generation scenarios has a
greater impact on the following search process. However, in traditional
genetic algorithms, the first generation individuals are crafted by randomly
initialized scenarios, which are highly contingent and uncertain. C2: The
evolutionary search process is prone to fall into local optima. In existing
genetic algorithms, the scenarios of each generation are generated by the
high-fitness individuals retained from previous generations, which tend to
cause convergence prematurely and result in a large number of iterations that
can only find a small number of safety-critical scenarios.

The goal of this paper is to introduce a new search-based scenario generation
method, which can overcome the above challenges. Our key idea is to leverage
the great capability of Large Language Models (LLMs) to generate high-quality
first generation scenarios and guide the generation away from the local
optima. LLMs, represented by ChatGPT-4 from OpenAI (roumeliotis2023chatgpt, ),
have emerged as a powerful tool for language understanding and question
answering (romera2024mathematical, ; zhang2022opt, ). They can interact with
humans as a knowledgeable expert. In addition to the chatbot services, LLMs
have also been used in software testing for different domains, e.g., unit test
generation (schafer2023empirical, ), input generation for mobile GUI testing
(liu2023fill, ). However, it is infeasible to directly apply LLMs to generate
safety-critical scenarios for ADS testing. This is because traffic scenarios
normally have high dimensionality and complexity, making it difficult for LLMs
to fully and accurately understand the search space. Additionally, since LLMs
have no specific domain knowledge about the traffic scenarios, they will make
up unreasonable scenarios, or arbitrarily modify existing scenarios, rendering
them less effective.

To address the above issues, we propose a novel methodology to adapt LLM’s
capability to traffic scenario generation. The key insight of our solution is
to leverage LLM’s program understanding and reasoning capabilities to generate
high-quality first generation scenarios and differential seed scenarios,
facilitating the evolutionary search for more diverse and safety-critical test
scenarios. With this strategy, we can use LLM’s ability in program
understanding to better comprehend the scenario generation task, which
generates high-quality scenarios of first generation considering scenario
generation requirements instead of random initialization, thus addressing C1.
We can also leverage LLM’s ability in quantitative reasoning to generate
differential seed scenarios to break out of local optimal solutions, thus
addressing C2.

Built upon this insight, we introduce LEADE, a LLM-enhanced scEnario
generation approach for ADS tEsting, which adopts an LLM-enhanced evolutionary
search technique for safety-critical and diverse scenarios. LEADE consists of
two modules: ❶ Scenario Program Generation. The input to this module is a
vehicle recording video, the most common scenario resource in real traffic.
LEADE first designs and implements a lightweight method to generate easy-to-
understand scenario programs from vehicle recording video for the LLM. Based
on the scenario programs, LEADE enables LLM to understand the test
requirements of scenario generation task. ❷ LLM-enhanced Scenario Adaptive
Evolutionary Search. This module is to search for diverse safety-critical
scenarios to test ADS. Firstly, LEADE makes LLM generate first generation
scenario programs considering test requirements. Secondly, LEADE formulates
scenario evolutionary search into a question & answering task, using an LLM-
enhanced adaptive multi-objective genetic algorithm to guide scenarios towards
diverse and safety-critical ones.

We implement and evaluate LEADE on Baidu Apollo (apolloauto, ), an industrial-
grade full-stack ADS platform that is widely used to control AVs on public
roads. Experimental results show that LEADE can effectively and efficiently
generate safety-critical scenarios and find diverse safety violations of
Apollo. LEADE exposes 10 distinct types of safety violations of Apollo in 14
hours, and outperforms two state-of-the-art search-based ADS testing
techniques by identifying 4 new types of safety-critical scenarios.

The contributions of this paper are as follows:

  * •

Insight: For the first time, we propose to formulate the ADS test scenario
generation and evolution as a question & answering task. We leverage LLM’s
powerful capabilities in program understanding and reasoning to generate high-
quality first population and differential seed scenarios to search for more
diverse and safety-critical scenarios.

  * •

Technique: We design a lightweight method to generate ADS test scenarios from
vehicle camera videos using the LLM, and a federate fuzz engine that combines
LLM’s reasoning-based differential seed scenario generation with adaptive
evolutionary search considering failure-inducing, diversity and coverage.

  * •

Evaluation: We perform effectiveness and efficiency evaluation on an
industrial level-4 grade ADS, and present a comprehensive analysis of LEADE
and the discovered safety violations of ADSs.

##  2\. Background and Related Work

###  2.1. Autonomous Driving System Selection

We target the industry-grade ADS to ensure the high practicality of LEADE. In
particular, we select the open-source full-stack ADS, Baidu Apollo
(apolloauto, ), due to their representativeness, practicality and
advancedness. (1) Representativeness. Apollo ranks among the top 4 leading
industrial ADS developers (rank, ) (the other three ADSs, Waymo, Ford, and
Cruise, are not released publicly). (2) Practicality. Apollo can be readily
installed on vehicles for driving on public roads (launch, ) (it has provided
self-driving services for real vehicles (selfhighway, ; baidutaxi, )). (3)
Advancedness. Apollo is actively and rapidly updated (the releases of Apollo
update on a weekly basis).

Figure 1. Overall framework of LEADE

###  2.2. ADS Test Scenario Program

In ADS simulation testing, the scenarios are described by scenario programs
that can be executed in the simulator. Scenario programs specified using
simulator APIs have loads of codes and cumbersome syntax, which is not
conducive to LLM’s comprehensive and accurate understanding and reasoning of
scenario programs. To tackle this issue, we investigate existing ADS test DSLs
(domain-specific language) that can describe scenarios in Apollo
(jullien2009openscenario, ; fremont2019scenic, ; zhou2023specification, ), and
select AVUnit (avunit, ) as the base platform considering the following
aspects: 1) AVUnit features rich DSLs for specifying environment conditions
and dynamic participants (NPC vehicles and pedestrians) with concise and
intuitive syntax (an example of the scenario program described by AVUnit is
shown as Figure 2); 2) AVUnit ensures deterministic scenario execution, which
means that participants move following the defined trajectories. In the AVUnit
scenario program, the position can be defined by ”lane_id -¿ dist” (here the
dist is: the distance from the position to the starting point of the lane
where it’s located. We call it lane distance).

Figure 2. An example of scenario program

###  2.3. ADS Test Scenario Generation

Generating diverse safety-critical scenarios is crucial for testing ADS, as
they undergo frequent updates and extensive testing before being deployed on
public roads. Due to the huge input space and functional complexity of ADSs
(shin2018test, ; nejati2019testing, ; arrieta2017search, ), it brings great
challenges to traditional software testing approaches when capturing various
rare events from complex driving situations. (guo2024semantic, ). How to
generate diverse safety-critical scenarios to fully test ADSs has received
significant attention in recent years(10.1145/2884781.2884880, ;
hekmatnejad2020search, ; cao2021work, ). ADS test scenario generation
approaches are divided into two primary strategies: traffic accident-based
approaches and search-based approaches.

Traffic accident-based approaches. These approaches generally reproduce
traffic accidents from crash databases to test the ADS
(10.1145/3338906.3338942, ; bashetty2020deepcrashtest, ; althoff2018automatic,
; zhang2023building, ). Gambi et al. (10.1145/3338906.3338942, ) propose an
approach to generate test scenarios from police reports. Zhang X et al.
(zhang2023building, ) train a panoptic segmentation model to extract effective
information from the accident record and recover traffic participants in the
simulator. However, these approaches require lots of time to train and
optimize the information extraction model, and the generated test scenarios
are simple and fixed, which can not fully test industrial ADSs. Different from
these methods, LEADE designs and implements a lightweight method to generate
scenarios from traffic records, and searches for real-world various safety-
critical scenarios based on them, which can reduce the time cost and test the
ADS comprehensively.

Search-based approaches. Search-based techniques (harman2007automated, ;
harman2012search, ; mcminn2004search, ; thibeault2021psy, ) are widely used in
ADS testing (koren2018adaptive, ; guo2024semantic, ; dreossi2019compositional,
; ben2016testing, ; tuncali2018simulation, ; tian2022generating, ;
onieva2015multi, ; kluck2019genetic, ; li2020av, ; tian2022mosat, ) to guide
the generated test scenarios towards more critical cases. Abdessalem et al.
(ben2016testing, ; abdessalem2018testing2, ) generate critical scenarios for
ADSs by combining multi-objective search with surrogate models. AV-Fuzzer
(li2020av, ) and MOSAT (tian2022mosat, ) perturb the driving maneuvers of
participants in an evolving traffic environment, which generates test
scenarios towards safety-violation scenarios through high-level variation
operations. In these approaches, there are two challenges: 1) the scenarios of
the first generation are generated by random initialization, which is prone to
create low-quality seed scenarios, affecting the efficiency of searching for
safety-critical cases; 2) during the iterative search process, it is easy to
fall into local optimality and tend to find the safety-violations similar to
discovered ones. Compared with these approaches, LEADE can generate high-
quality scenarios of first generation by leveraging the LLM’s capability in
quantitative reasoning and formulating the evolutionary search into Q&A task
to generate differential seed scenarios for addressing the local optimal.

##  3\. Approach

Figure 1 shows the framework of LEADE. It consists of two modules: scenario
program generation, LLM-enhanced adaptive evolutionary search. (1) Scenario
program generation. The generation process comprises three phases: scenario
element extraction, abstract scenario construction and concrete scenario
program generation. For the input vehicle recording videos, this module first
extracts key elements from them, and then parses them into structured contexts
to construct abstract scenarios. Based on constructed abstract scenarios, this
module generates concrete scenario programs. (2) LLM-enhanced adaptive
evolutionary search. This module enables the LLM to understand the generated
scenario programs and the requirements of scenario generation task. Then it
makes LLM generate first generation scenarios considering the test
requirements. This module uses an adaptive multi-objective evolutionary method
to search for diverse and safety-critical scenarios. When the evolution
process gets stuck. LEADE generates feedback prompts to feed the individual
characteristics of previous generations into the LLM, letting the LLM generate
differential seed scenarios for the next generation. For the scenarios where
the ego vehicle causes the safety violation, LEADE records them and can replay
them to reproduce the safety violation of ADS.

###  3.1. Scenario Program Generation

####  3.1.1. Scenario element extraction.

To ensure the safety of ADSs, simulation testing requires a large number of
scenarios in real traffic. One of the most common scenario records in real
traffic is vehicle camera videos. Therefore, LEADE first extracts key elements
(e.g., road, vehicle and pedestrian motions, weather) of scenarios from
vehicle camera videos. Considering that LLMs have demonstrated strong
capabilities in accurate recognition and comprehension of these elements,
LEADE utilizes LLM to extract scenario key elements from the vehicle camera
videos. Specifically, we use Honda Scenes dataset (narayanan2019dynamic, ),
which contains 80 hours of diverse high-quality driving video clips collected
in San Francisco. The dataset includes roads, weather, vehicles, and
pedestrians.

Although LLMs perform well on image understanding and analysis, their
performance can be significantly influenced by the quality of the input
prompts. First, LEADE splits each scenario video clip into a sequence of
images. For the sequence of scenario images, we design linguistic patterns to
generate input prompts for the LLM, to guide it to understand the given
scenario and extract key elements, including weather, road type and surface
conditions, traffic lights and signs, types and motions of traffic
participants (vehicles and pedestrians) within the camera sight.

To design the prompt patterns, we select 20 different scenario video clips
that include various types of roads, weather, and traffic participants. Five
authors with experience in ADS testing independently write the prompt
sentences, and submit them to the LLM to extract the key elements from each of
the selected scenarios. Each author performs the self-check and cross-check on
the extraction results of the ten scenarios. For the extraction results that
have inaccuracy or missing key information, the corresponding prompt is
modified until the prompt can guide LLM to accurately and comprehensively
extract the key elements of all the selected scenarios. Finally, the five
authors vote for the five prompts based on their versatility, ease of
understanding, and simplicity. The prompt is shown as Figure 3.

Figure 3. The prompt for scenario element extraction

####  3.1.2. Abstract Scenario Construction

The abstract scenarios are constructed by parsing the extracted elements into
structured description contents. First, for each scenario, LEADE uses
StandfordNLP to perform part-of-speech tagging and dependency analysis on the
corresponding extracted element contents. Then each object in the scenario is
parsed into a tuple. Taking the scenario elements in Figure 4 as an example,
its abstract scenario is shown as Table 1, which is composed of elements in
five categories: environment, road condition, ego vehicle driving task, NPC
vehicles, and pedestrians.

Figure 4. An example of recorded scenario Table 1. An example of abstract scenario Element | Description
---|---
Environment |  | time=”daytime”, weather=”sunny”
---
Road |  | type=”crossroad”, signal=”traffic light”
---
EV task |  | turn right
---
| NPC
---
Vehicle
| [type=”truck”,motion=[”drive forward”],
---
position=”left front”,direction=”opposite”]
[type=”SUV”,motion=[”cross”],
position=”left vertical”,direction=”right verticcal”]
[type=”car”,motion=[”stop”,”cross”],
position=”opposite front”,direction=”opposite”]
Pedestrian |  | [motion=”cross”,position=”right front”,
---
direction=”left front”,number=1]

(1) Environment: this category contains scenario time (e.g., night) and
weather (e.g., rainy) to describe the driving environment of the test
scenarios.

(2) Road condition: this category contains road type (e.g., crossroad) and
traffic signal (e.g., traffic light) to describe the road condition in the
scenario.

(3) Ego vehicle (EV) task: ego vehicle is the video recording vehicle of the
scenario. The driving task of ego vehicle contains its driving motion in the
scenario (e.g., turn at intersection) and the driving direction (e.g., to the
right). In the generated test scenario, the ego vehicle will connect to ADS
and be tested by other extracted elements of the scenario.

(4) NPC vehicles: this category describes the NPC vehicles in the scenario,
including vehicle type (e.g., SUV, truck), vehicle motion (e.g., change lane),
vehicle position and direction relative to the ego vehicle (e.g., left front).

(5) Pedestrians: this category describes the pedestrians in the scenario,
including number of pedestrians, pedestrian motion (e.g., cross the
intersection), pedestrian position and direction relative to the ego vehicle
(e.g., from the left to the right).

####  3.1.3. Concrete Scenario Program Generation

According to each abstract scenario, LEADE generates the concrete scenario
program. To do this, three tasks are required to solve: 1) defining the
starting position and target position of the ego vehicle (the vehicle connects
into the ADS); 2) defining the trajectories for NPC vehicles and pedestrians;
3) defining the parameters of time and weather.

(1) Determining ego vehicle’s starting position and destination. LEADE first
selects one road $R$ in the map according to the extracted road type. Then it
parses the selected road to obtain all its lane information, including lane
ID, lane direction, lane length. The starting position and destination of ego
vehicle are marked as $S$ and $D$ respectively, which are determined by the
ego vehicle’s driving task. To do this, LEADE decomposes the road into a group
of districts based on the lane structure, ego vehicle’s starting position and
the relative positions to ego vehicle, as shown in Table 2.

Table 2. Road districts Road districts | Definition
---|---
$A(S,f)$ |  In front of $S$ and before the junction
$A(S,lf)$ |  Left front of $S$ and before the junction
$A(S,rf)$ |  Right front of $S$ and before the junction
$A(S,lv)$ |  Left lanes vertical to the lane of ego vehicle) of $S$
$A(S,rv)$ |  Right lanes vertical to the lane of ego vehicle) of $S$
$A(S,o)$ | The other side lanes of the junction

LEADE defines a series of rules for determination of starting position and
destination of ego vehicle, shown as Table 3. $L_{i}$ represents the lane with
ID $i$, $LD_{i}$ represents the direction of $L_{i}$, $LE_{i}$ represents the
length of $L_{i}$, $LT_{S}$ represents the lane distance of position $S$.

Table 3. Rules for defining ego vehicle Ego task | Rules
---|---
| Drive along
---
the lane
|  $S\in L_{i},LT_{S}<LE_{i}$;
---
$D\in L_{i},LT_{S}<LT_{D}\leq LE_{i}$
| Change to
---
left lane
|  $S\in L_{i},LT_{S}<LE_{i}$;
---
$D\in A(S,lf),LT_{D}>LT_{S}$
| Change to
---
right lane
|  $S\in L_{i},LT_{S}<LE_{i}$;
---
$D\in A(S,rf),LT_{D}>LT_{S}$
Cross |  |  $S\in L_{i},LT_{S}<LE_{i}$;
---
$D\in L_{j},L_{j}\in A(S,o),LD_{j}=LD_{i}$
Turn right |  |  $S\in L_{i},LT_{S}<LE_{i}$;
---
$D\in L_{j},L_{j}\in A(S,rv),sin(LD_{i},LD_{j})=1$
Turn left |  |  $S\in L_{i},LT_{S}<LE_{i}$;
---
$D\in L_{j},L_{j}\in A(S,lv),sin(LD_{i},LD_{j})=-1$

(2) Modeling motions of participants (including NPC vehicles and pedestrians)
to generate trajectories for them. Based on the road districts above, LEADE
models the motions of NPC vehicles and pedestrians. We conclude the types of
vehicle motions from (nhtsa_files, ) and the types of pedestrian motions from
(rasouli2017they, ). As page limitation, we take a NPC vehicle motion, ”turn
around” as an example to illustrate the motion modeling, shown as Table 4 and
others are available at motion modeling folder in
https://github.com/ADStesting-test/Leade. $W_{0}$ represents the initial
waypoint and $W_{f}$ represents the ending waypoint of the NPC vehicle or
pedestrian. $i$ is the ID of the lane of ego vehicle’s starting position. POS
is the position and DIR is the direction.

Table 4. The modeling for ”turn around” POS | DIR | Trajectory rules
---|---|---
far left | right |  | $W_{0}\in L_{m},L_{m}\in A(S,lv),sin(LD_{i},LD_{m})=-1$
---
$W_{f}\in L_{n},L_{n}\in A(S,lf),cos(LD_{i},LD_{n})=-1$
left |  | $W_{0}\in L_{m},L_{m}\in A(S,lv),sin(LD_{i},LD_{m})=-1$
---
$W_{f}\in L_{n},L_{n}\in A(S,o),LD_{n}=LD_{i}$
far right | right |  | $W_{0}\in L_{m},L_{m}\in A(S,rv),sin(LD_{i},LD_{m})=-1$
---
$W_{f}\in L_{n},L_{n}\in A(S,o),LD_{n}=LD_{i}$
left |  | $W_{0}\in L_{m},L_{m}\in A(S,rv),sin(LD_{i},LD_{m})=-1$
---
$W_{f}\in L_{n},L_{n}\in A(S,lf),cos(LD_{i},LD_{n})=-1$
opposite side | right |  | $W_{0}\in L_{m},L_{m}\in A(S,o),cos(LD_{i},LD_{m})=-1$
---
$W_{f}\in L_{n},L_{n}\in A(S,rv),sin(LD_{i},LD_{n})=1$
left |  | $W_{0}\in L_{m},L_{m}\in A(S,o),cos(LD_{i},LD_{m})=-1$
---
$W_{f}\in L_{n},L_{n}\in A(S,lv),sin(LD_{i},LD_{n})=-1$
front | right |  | $W_{0}\in L_{i},LT_{W_{0}}>LT_{S}$
---
$W_{f}\in L_{n},L_{n}\in A(S,rv),sin(LD_{i},LD_{n})=1$
left |  | $W_{0}\in L_{i},LT_{W_{0}}>LT_{S}$
---
$W_{f}\in L_{n},L_{n}\in A(S,lv),sin(LD_{i},LD_{n})=-1$
left front | right |  | $W_{0}\in L_{m},L_{m}\in A(S,lf),LD_{m}=LD_{i},LT_{W_{0}}>LT_{S}$
---
$W_{f}\in L_{n},L_{n}\in A(S,rv),sin(LD_{i},LD_{n})=1$
left |  | $W_{0}\in L_{m},L_{m}\in A(S,lf),LD_{m}=LD_{i},LT_{W_{0}}>LT_{S}$
---
$W_{f}\in L_{n},L_{n}\in A(S,lv),sin(LD_{i},LD_{n})=-1$
right front | right |  | $W_{0}\in L_{m},L_{m}\in A(S,rf),LT_{W_{0}}>LT_{S}$
---
$W_{f}\in L_{n},L_{n}\in A(S,rv),sin(LD_{i},LD_{n})=1$
left |  | $W_{0}\in L_{m},L_{m}\in A(S,rf),LT_{W_{0}}>LT_{S}$
---
$W_{f}\in L_{n},L_{n}\in A(S,lv),sin(LD_{i},LD_{n})=-1$

There are some general constraints when generating the trajectory
$(W_{0},W_{1},...,W_{f})$. 1) the constraint prohibiting NPC vehicles from
driving opposite to the lane direction: for the NPC vehicle’s two waypoints
$W_{p},W_{p+1}$, $W_{p}\in L_{m},W_{p+1}\in L_{n}$, if $L_{m}=L_{n}$,
$LT_{W_{p+1}}\geq LT_{W_{p}}$; 2) the constraint for vehicle heading: the
heading should be the same as the lane direction; 3) the constraint for
vehicle speed: the speeds of vehicles should not be more than maximum speed
limitation of the road; 4) the constraint for pedestrian speed: the speeds of
pedestrian should not be more than 3m/s.

(3) Defining the parameters of time and weather. The category of time of day
is discrete, and the category of weather is a dictionary variable whose keys
and values are the types of weather and quantification of the weather type
(which will be transferred to a real value in [0,1]). Therefore LEADE encodes
the time of day as a discrete vector, and encodes the weather as a vector [0,
1]—wk—, where —wk— is the number of weather kinds defined in a simulator.

###  3.2. LLM-enhanced Adaptive Evolutionary Search

Based on the generated scenario program, LEADE uses LLM-enhanced adaptive
genetic algorithm to search for more safety-critical and diverse test
scenarios. The algorithm is shown as Algorithm 1. When starting an
evolutionary search (line 1), instead of randomly initializing scenario
programs as the first generation, LEADE makes the LLM create the first-
generation scenario programs considering the ADS test requirements.

Algorithm 1 LLM-enhanced adaptive evolutionary search

1:Safety-critical scenario set SCR

2:A scenario program example AE, crossover probability interval PC, crossover
threshold $threshold_{c}$, mutation probability interval PM, mutation
threshold $threshold_{m}$, starting and scenario program understanding prompt
$pt$

3:first-generation P = LLM_generate(AE, $pt$)

4:while

5: doC $\leftarrow\emptyset$, M $\leftarrow\emptyset$, TS
$\leftarrow\emptyset$

6: if NOT (—TS—¿3 and TS[-1]=TS[-2]=TS[-3]) then

7: for $p_{i}\in$ P do

8: execute $p_{i}$

9: if $\exists$ ego safety violation in $p_{i}$ then

10: SCR $\leftarrow$ SCR $\bigcup p_{i}$

11: end if

12: end for

13: calculate fitness S

14: TS $\leftarrow$ TS $\bigcup$ S

15: P = Adaptive_variation(P, S, PC, PM, $threshold_{c}$, $threshold_{m}$)

16: end if

17: prompt = $pt$ \+ generate_feedback(P, S)

18: P = LLM_generate(prompt)

19:end while

20:break

21:return SCR

22:procedure Adaptive_variation(P, S, PC, PM, $threshold_{c}$,
$threshold_{m}$)

23: for $p_{i}\in$ P do

24: select fitness $s_{i}\in$ S

25: generate crossover probability $c_{i}\backsim U$(PC)

26: if $c_{i}$ ¿ $threshold_{c}$ then

27: $C\leftarrow C\bigcup p_{i}$

28: end if

29: generate mutation probability $m_{i}$ U(PM)

30: if $m_{i}$ ¿ $threshold_{m}$ then

31: $M\leftarrow M\bigcup p_{i}$

32: end if

33: end for

34: for each two individuals $p_{i},p_{j}\in C$ do

35: $p_{i}^{\prime},p_{j}^{\prime}\leftarrow uniformCrossover(p_{i},p_{j})$

36: $PN\leftarrow PN\bigcup p_{i}^{\prime},p_{j}^{\prime}$

37: end for

38: for $p_{i}\in M$ do

39: $p_{i}^{\prime}\leftarrow geneMutation(p_{i})$

40: $PN\leftarrow PN\bigcup p_{i}^{\prime}$

41: end for

42: return PN

43:end procedure

Then LEADE searches for diverse and safety-critical scenarios by a multi-
objective evolutionary search technique (line 19-38), which can improve the
heritability of high-quality scenarios and increase the mutation of low-
quality scenarios. To guide the search away from local optima, LEADE
formulates the evolution process into a question & answering task. When the
evolutionary search gets stuck, LEADE lets the LLM generate differential seed
scenarios for the next generation (line 11-16). LEADE executes generated
scenarios to test the ADS, and records the safety-violation scenarios of ego
vehicle (line 4-8), which can be automatically reproduced to re-test the ADS.

####  3.2.1. LLM-guided creation of first-generation scenarios

For the scenario program generated from traffic videos, we design the prompt
patterns to facilitate LLM to correctly understand the scenario program and
create the first-generation scenario programs for the evolutionary search of
scenarios. Five authors are asked to write the prompts respectively and
perform small-scale experiments to question the LLM for creating the first-
generation scenario programs. Then considering how well the scenario programs
generated by the LLM match user intent, they were selected the prompts with
the best results. Based on them, they performed card sorting [56] and
concluded prompt patterns. This process comes out two kinds of prompts,
scenario understanding prompt and starting prompt, shown in Table 5.

Table 5. Prompt patterns for first generation scenarios

Prompt type | Sample of prompt patterns
---|---
| Scenario
---
understanding
prompt
| A scenario to test ADS is shown as follows.
---
<A scenario program example>.
<The introduction of keywords of parameters of ego vehicle>.
<The introduction of keywords and parameters of NPC vehicle>.
<The introduction of keywords and parameters of pedestrians>.
<The introduction of keywords and parameters of environment>.
| Starting
---
prompt
| You are an expert of ADS testing.
---
We want you to generate ¡count¿ new different scenarios to challenge
ADS. The lane_id should be in <set of lane_id>. The lane distance
should be in [0,<lane length>]. The speed of npc vehicles should be
in [0,speed_limit], and the speed of pedestrian should be in [0,3].

Scenario understanding prompt is the prompt to tell LLM about the contextual
semantics of scenario programs. Figure 2 is an example of A scenario program
example. As page limitation, we take the introduction of keywords and
parameters of NPC vehicle as an example, which is: ”npc represents the
vehicles not controlled by the AV, specified using the keyword Vehicle,
followed by four parameters: the initial state (npc_init_state), the waypoints
that it should follow (npc_waypoint), the target state
(npc_destination_state), the type of the vehicle (npc_type). The state
contains: its position, its heading, and its current speed. When specifying
the state, the position must always be specified, but the heading and speed
are optional. The waypoint is a list of states and specified using the keyword
Waypoint. The position is described by a lane point. An example of lane point
is ”lane_39”-¿20, which specifies a point on the lane with ID 39 and the point
is 20 meters from the start of the lane.”

Starting prompt is the prompt to inform the LLM of the current task that
generates first population scenario programs. The set of lane_id, lane_length,
speed_limit are from the lane information obtained in Section 2.2.2 (1). LEADE
sends the scenario program to LLM along with the input prompts, to obtain the
first generation scenario programs. Note that, for the scenario programs
generated from the LLM, LEADE checks the feasibility of participants’
trajectories by the general constraints mentioned in 2.2.2 (2). For the
scenario program with infeasible trajectories, LEADE feeds them back to the
LLM to generate a feasible scenario program.

####  3.2.2. Adaptive Evolutionary Search

Based on the first-generation scenario programs, LEADE adopts an adaptive
genetic algorithm to build successfully-improved Pareto-optimal solutions
considering the following three objectives: failure-inducing to ego vehicle,
scenario diversity, road coverage.

For the same-generation scenario programs generated by adaptive evolutionary
search, when all of them have been executed, they are further manipulated by
adaptive crossover and adaptive mutation to generate new scenarios. Among
these new scenario programs and their parents, LEADE selects the top k ones as
the new generation by using Pareto optimality. When the saved scenario
programs in three consecutive generations keep the same, LEADE will generate
differential seed scenarios for the next generation.

(1) Fitness Function. To search for more safety-critical and diverse
scenarios, a fitness function that contains the objectives above is designed
to calculate the fitness score of each generated test scenario. The fitness
function consists of the following metrics: 1) the minimum distance between
ego vehicle and participants during ego vehicle’s driving; 2) the average
difference between participants’ trajectories and discovered safety-violation
scenarios; 3) the newly covered waypoint range by participants’ trajectories.

For the first metric, LEADE records the trajectory of ego vehicle (represented
as $(e_{1},e_{2},...,e_{n}$) and each participant (represented as
$(p_{1},p_{2},...,p_{n}$) every 1 second during ego vehicle’s driving, and
computes the distance between participant’s trajectory and ego vehicle’s
trajectory. The calculation is shown as below.

(1) $\min_{t\in[1,n]}\sqrt{(p_{t}.x-e_{t}.x)^{2}+(p_{t}.y-e_{t}.y)^{2}}$

For the second metric, LEADE uses the average Euclidean distance to compute
the differences between participants’ trajectories in different scenarios. For
two scenarios $i$ and $j$, the calculation of Euclidean distance of two NPC
vehicles $n$ and $m$ (vehicle $n$ is in scenario $i$, vehicle $m$ is in
scenario $j$) is shown as below, and that of pedestrians are calculated in the
same way.

(2)
$D_{in,jm}=\sum_{k=0}^{\mu}\sqrt{(x_{ink}-x_{jmk})^{2}+(y_{ink}-y_{jmk})^{2}}$

The calculation of average Euclidean distance for two scenarios are shown as
below (the number of NPC vehicles/pedestrians in scenario $i$ and $j$ are
represented as $l$ and $c$ respectively).

(3) $D_{i,j}=\frac{\sum_{n=0}^{l}\sum_{m=0}^{c}D_{in,jm}}{l*c}$

For the third metric, LEADE counts the waypoints that are covered by the
participants’ trajectories in each scenario. For each newly generated
scenario, LEADE calculates the newly covered waypoints. The calculation is
shown as below. $l$ is the number of participants. $Tr_{n}$ represents the
trajectory of participant $n$, and $w_{d}$ represents the $d$-th waypoint of
$Tr_{n}$.

(4) $\sum_{n=1}^{l}\sum_{d=0}^{f}(w_{d}\in Tr_{n}\cap w_{d}\notin E)$

The fitness score of each scenario is calculated at the end of execution. When
all scenarios of this generation have been executed, they will be diversified
by adaptive mutation and adaptive crossover. Among these individuals and their
parents, LEADE selects the top k ones as the next generation by using Pareto
optimality.

(2) Adaptive Variation. To increase the heritability of high-fitness scenarios
and the mutation of low-fitness scenarios, the adaptive-crossover and
adaptive-mutation probability are adopted during the evolution of population.

Adaptive Crossover: the scenario with greater fitness has a higher crossover
probability, and vice versa. Specifically, for the scenario program $i$ with
fitness $f_{i}$, LEADE first sets the crossover probability interval
$[PC_{min},PC_{max}]$ (here we set $PC_{min}=0.4,PC_{max}=1$, others can
change values according to actual needs), and then calculate the average
fitness $f_{avg}$ and maximum fitness $f_{max}$ of this generation. The
crossover probability $PC_{i}$ is computed as follows.

$PC_{i}=PC_{max}-(PC_{max}-PC_{min})\frac{f_{max}-f_{i}}{f_{max}-f_{min}}$

If $PC_{i}>threshold_{c}$, the scenario program will be added into the
crossover candidate set. For the scenarios with $PC\geq threshold_{c}$, LEADE
will conduct participant exchange or environment condition exchange across
each two scenarios.

Adaptive Mutation: the scenario with smaller fitness has a higher mutation
probability, and vice versa. Specifically, for the scenario program $i$ with
the fitness $f_{i}$, LEADE first sets the mutation probability interval
$[PM_{min},PM_{max}]$ (here we set $PM_{min}=0,PM_{max}=0.6$, others can
change their values according to actual needs). The crossover probability
$PM_{i}$ is computed as follows:

$PM_{i}=(PM_{max}-PM_{min})\frac{f_{max}-f_{i}}{f_{max}-f_{min}}$

If $PM_{i}>threshold_{m}$, LEADE will select the participant with the minimum
distance between ego vehicle during ego vehicle’s driving, and then conduct
value mutation on the participant’s waypoints or environment parameters. Note
that for each trajectory generated by mutation, LEADE checks its feasibility
by the general constraints mentioned in 2.2.2 (2). For the infeasible
trajectory, LEADE will re-generate it by mutation.

####  3.2.3. Feedback-guided LLM’s Differential Seed Scenario Generation

For the generated scenarios, LEADE executes them in the simulator to test the
ADS. During the adaptive evolutionary search, we find that as the iterations
increase, the evolutionary search is prone to falling into local optimality,
causing the newly generated safety-violation scenarios to be similar as those
generated in previous generations. To address the problem, when the
evolutionary search gets stuck, LEADE generates differential seed scenarios
for the next generation, which can facilitate to exploring finding more
diverse safety-critical scenarios.

Specifically, when the saved individuals in three consecutive generations keep
the same, LEADE selects the safety-violation scenarios generated by the
previous iterations (represented as $se$), and generates the feedback prompt
using the rule 1 in Table 6. The prompt generated by rule 1 is to promote LLM
learn from the characteristics of previously generated safety-violation
scenarios and create differential seed scenarios to explore more search space.
LEADE inputs the feedback prompt into the LLM, to utilize the reasoning
ability to generate differential seed scenarios.

However, the introduced differential seed scenarios may reduce evolutionary
search efficiency for safety-critical scenarios. To solve the potential
negative impacts of differential seed scenarios, during the search process,
when no safety-violation scenario occurs in three consecutive generations,
LEADE selects two representative individuals (the scenario with highest
fitness and lowest fitness in that generation) from each of the previous three
generations, and generates the feedback prompt using rule 2 in Table 6. $sf$
are the selected high-fitness scenarios and $sl$ are the selected low-fitness
scenarios. LEADE inputs the feedback prompt into the LLM, which facilitates it
modifying the scenarios most likely to lead to safety violation of ego
vehicle, to assisting find the safety-violation scenario faster.

Table 6. Rules for feedback prompt generation | Rule
---
1
|  The ego vehicle occurred safety violations in $se$. So they are what we
want.
---
Please substantially alter them to generate new scenarios different from $se$
| Rule
---
2
|  $sl$ create no challenge for ego vehicle. $sf$ create challenges for ego
vehicle,
---
but not leading to safety violation of it. Please add new npc vehicles or
pedestrians, or substantially alter values of parameters to generate
more challengeable scenarios

##  4\. Evaluation

To demonstrate the ability of LEADE, we apply it to test an industrial-grade
full-stack ADS, Apollo 7.0, which is widely used to control AVs on public
roads. To evaluate the efficiency and effectiveness of LEADE, we answer the
following research questions:

RQ1: How effective and efficient is LEADE in finding diverse safety violations
of Apollo?

RQ2: How beneficial is LEADE to creating high-quality first-generation
scenarios and addressing the local optimal?

###  4.1. Experiment Setup

We conducted the experiments on Ubuntu 20.04 with 500 GB memory, an Intel Core
i7 CPU, and an NVIDIA GTX2080 TI. SORA-SVL (an end-to-end AV simulation
platform which supports connection with Apollo) and San Francisco map are
selected to execute the generated scenarios. During the experiments, all
modules of Apollo are turned on, including perception module, localization
module, prediction module, routing module, planning module, and control
module. Apollo is equipped with a wide range of sensors, including two camera
sensors (one at the top and another in front of ego vehicle), one GPS, one
radar, one lidar.

The major safety requirements that LEADE concerns include: the ADS should
avoid collision with participants in scenarios, the ADS should reach the
destination. To monitor whether the ego vehicle satisfies the safety
requirements above, we define two specifications: the distances between ego
vehicle and participants during the execution of scenarios, and the distances
of ego vehicle and destinations at the ending of scenario execution. Note that
during the scenario execution, AVUnit can ensure NPC vehicles and pedestrians
move along the defined waypoints while following traffic regulations (e.g,
avoid colliding to other participants and ego vehicle, move within the maximum
speed of road, follow the lane direction). Thus the collisions between ego
vehicle and participant are caused by the safety violations of ego vehicle.

There are some parameters of LEADE that needs to be defined:
$threshold_{m},threshold_{c},k$. $threshold_{m}$ is the threshold for
individual mutation and $threshold_{c}$ is the threshold for individual
crossover. To determine them, we tested different values within the range of
thresholds that existing genetic algorithms recommends (haupt2000optimum, ),
and chose 0.3 for $threshold_{m}$ and 0.7 for $threshold_{c}$ respectively.
$k$ is the number of selected optimal individuals in each generation. To
balance the search effects and evolving costs, LEADE randomly generates
$k\in[4,8]$ for the adaptive evolutionary search process.

###  4.2. Experiment Design

For RQ1, we run LEADE to generate scenarios and execute them in the simulator
to test Apollo. For the found safety-violation scenarios, we design a set of
classification criteria to classify them, and analyze the potential
deficiencies and correct operations of modules in Apollo.

We evaluate LEADE in comparison to two state-of-art techniques that use
genetic algorithm to find safety-violation scenarios of Apollo: AV-Fuzzer and
MOSAT. AV-Fuzzer evolves participant behaviors to expose safety violations,
while MOSAT generates test scenarios using atomic maneuvers and motif
patterns. Both techniques employ genetic algorithms for scenario optimization.
We run LEADE, AV-Fuzzer and MOSAT for the same amount of time, and compare
their effectiveness and efficiency from the following aspects:

  * $\bullet$

How many types of Apollo safety violations can be found?

  * $\bullet$

How much time does it take to generate one scenario?

  * $\bullet$

How many scenarios are generated on average to find one safety-violation of
Apollo?

  * $\bullet$

How long does it take on average to expose the first safety violation and all
found types of safety violations of Apollo?

For RQ2, to evaluate the benefit of LEADE’s first-generation scenario creation
to efficiently finding safety violations of Apollo, and that of LEADE’s
addressing local optimal to effectively finding more diverse types of safety
violations of Apollo, we conduct the ablation experiments of LEADE. Two
variant versions $LEADE_{r}$ and $LEADE_{n}$ are implemented. $LEADE_{r}$
creates the first-generation individuals by random initialization of test
scenarios, and $LEADE_{n}$ evolves the test scenarios without differential
random seed scenarios. We run LEADE, $LEADE_{r}$ and $LEADE_{n}$ for the same
amount of time, and compare their effectiveness and efficiency.

To answer the research questions above, we run each experiment for 24 hours.
Note that to account for the randomness of search-based techniques, the
experiments were repeated 5 times, and the results were computed and compared
in the following.

###  4.3. Result Analysis: RQ1

For each run, on average, 3756 scenarios (min 3346 and max 4015) are generated
by LEADE and 313 (min 292 and max 355) out of them have safety violations of
ego vehicle. To better analyze the potential deficiencies of Apollo, for each
found safety-violation scenario, we identify the essential participants that
cause ego vehicle’s safety violation. For an example, a found safety-violation
scenario is shown as Figure 5(a), the corresponding safety-violation scenario
with only essential participants is shown as Figure 5(b), which means if any
participant in (b) is removed from the scenario, the safety violation of ego
vehicle will not occur. To identify essential participants of each safety-
violation scenario, LEADE first replays it by removing its participants one by
one, and checking whether the safety violation of ego vehicle can be
reproduced.

Figure 5. An example of safety-violation scenario Table 7. The found types of safety violations of Apollo Type |  Road type |  Driving task of EV | Participants | Driving Error of Apollo
---|---|---|---|---
type |  | initial position
---
relative to EV
behavior
1 | Intersection | Turn left | 2 NVs | left/right vertical lanes | cross |  Misidentifying the speed of NPC vehicles driving one after the other as the same, leanding to misjudgement of the speed of later vehicles
Turn right | 2 NVs | left vertical lanes | cross
2 |  | Multi-lanes
---
Straight road
| Change lane left/
---
Change lane right
2 NVs |  | ahead on left/right lane
---
behind on left/right lane
| drive along
---
accelerate
| Ignore acceleration of NPC vehicle behind on adjacent
---
lane, leading to not keeping the safe distance
3 | Intersection | Cross | 2 NVs | left vertical lanes |  | cross
---
turn left
| Mispredicting behaviors of vehicles driving side by side on vertical
---
lanes as the same, ignoring behavior changes of the one arriving later
4 | Intersection | Turn left/Cross | 1 NV | left vertical lanes | turn left |  | When turning at connection area of junction, there is a delay
---
in processing and responding to right of way of turning vehicle
5 |  | Multi-lanes
---
Straight road
Drive through | 2 NVs |  | ahead on the same lane
---
ahead on adjacent lane
| stop
---
decelerate
Disable to change lane again during driving
6 | Intersection | Turn right | 1 NV | left vertical lanes |  | stop at entrance
---
of EV’s turn-in lane
Disable to adjust route to another incoming lane during turning
7 | Intersection | Turn left | 2 NVs |  | the opposite side lanes
---
of the intersection
cross |  Inaccurate calculation of the distance and motion status of two consecutive NPC vehicles passing through an intersection
Cross | 2 NVs | left/right vertical lanes | cross
8 | Intersection | Cross |  | 1 NV
---
1 P
| ahead on left/right lane
---
left/right vertical lane
| follow lane
---
cross
| When participants in front perform abnormally actions (e.g.,emergen-
---
cy braking), EV is lack of prediction of potential dangers nearby
9 |  | Multi-lanes
---
Straight road
Drive through | 2 NVs | ahead on the same lane | drive slowly |  | Insufficient ability to cope with multiple slow-speed vehicles ahead,
---
leading to colliding with it when performing slow overtaking
10 | Intersection | Turn right | truck | left vertical lane | cross |  Lack of response to large vehicle dimensions when EV accelerates, leading to no adjustment for lateral spacing
Cross | truck | right vertical lane | turn right

To classify the found safety-violation scenarios into distinct categories, we
design a set of classification criteria considering the following aspects:
road type, driving task of ego vehicle, behaviors of participants, the driving
error of Apollo. Based on the criteria, the safety-violation scenarios with
only essential participants are categorized into 10 distinct types (shown as
Table 7), which are all revealed in the first 14 hours of each experiment. EV
represents the ego vehicle. NV represents NPC vehicles (2 NVs represents two
NPC vehicles), and P represents pedestrians. As the page limitation, we select
two types of safety-violation scenarios and explain them in the following (EV
represents the ego vehicle). The illustration for other types of safety
violations can be found in the safety violation folder of
https://github.com/ADStesting-test/Leade.

Examples of safety violation 7: As shown in Figure 6, in the first scenario,
EV is turning left. Vehicle $a$ is crossing the intersection from the opposite
side lanes, and vehicle $b$ is following $a$ to cross the intersection. Before
EV starts to turn at the entrance of junction, it identifies the right of way
of $a$ and stops to let $a$ pass. When $a$ pass the junction, EV accelerates
due to wrongly calculation of the distance and speed of $b$, causing collision
to $b$. The safety violation of the second scenario is caused by the same
error of EV.

Figure 6. Two examples of safety violation 7

Examples of safety violation 10: as shown in Figure 7, EV is turning right.
The truck $a$ on the left vertical lanes is crossing. When EV starts to turn,
$a$ is driving close to the adjacent lane of EV’s destination. EV decelerates
and turns right close to the right corner and keeps a safe distance with $a$.
However, when EV finishs the turning, it accelerates close to the lane
marking, not considering the big size of $a$ and leading to the collision.

Figure 7. An example of safety violation 10

To compare the effectiveness and efficiency of LEADE to existing state-of-art
techniques that uses genetic algorithm to find safety violations of Apollo, we
run MOSAT and AV-Fuzzer on the same road in San Francisco as LEADE. For the
sake of fairness, in each 24-hour running, the number of individuals in each
generation of the three approaches are the same (ranging from 4 to 8
respectively in the 5 times). Note that for each found safety-violation
scenario, we check whether the safety violation is caused by illegal actions
of participants in the scenario, and analyze the safety violations caused by
ego vehicle. Figure 8 shows a safety violation that was not caused by ego
vehicle. The NPC vehicle d changes to the lane of ego vehicle illegally and
collides to the ego vehicle. For the found safety violations caused by ego
vehicle, we use the same criteria to classify them. The experiment results are
shown as Table 8. SV is the abbreviation for ”safety violation”.

Figure 8. An example of safety violation not caused by EV Table 8. Comparison results of LEADE, MOSAT, AV-Fuzzer |  | LEADE | MOSAT | AV-Fuzzer
---|---|---|---|---
types of found SV | 10 | 6 | 3
time for a scenario (second) | min | 21.5 | 23.2 | 64.0
max | 25.8 | 26.9 | 49.8
avg | 23.0 | 24.4 | 55.0
number of scenarios to find one SV | min | 10.1 | 61.0 | 96.4
max | 13.7 | 65.9 | 192.6
avg | 12 | 62.1 | 131
time to find the first SV (min) | min | 6 | 22 | 89
max | 15 | 58 | 122
avg | 11 | 46 | 98
time to find all found types of SVs (hour) | min | 11.3 | 16.0 | 15.7
max | 13.6 | 18.9 | 20.4
avg | 12.9 | 18.1 | 19.2

In each 24-hour running, MOSAT can find 6 types of safety violations of
Apollo, and AV-Fuzzer can find 3 types of safety violations of Apollo. On
average, MOSAT generates 3541 test scenarios (min 3208 and max 3719), and 57
(min 49 and max 61) out of them occur safety violations of ego vehicle. AV-
Fuzzer generates 1572 test scenarios (min 1350 and max 1734), and 12 (min 9
and max 14) out of them occur occur safety violations of ego vehicle.

LEADE finds 10 distinct types of safety violations of Apollo and all of them
occur in the first 14 hours. MOSAT finds 6 types of safety violations and all
of them occur in the first 19 hours. AV-Fuzzer finds 3 types of safety
violations and all of them occur in the first 21 hours. Moreover, it takes
LEADE less time to find the first safety violation of Apollo than MOSAT and
AV-Fuzzer. Therefore, compared with MOSAT and AV-Fuzzer, LEADE can find more
types of safety violations of Apollo in a shorter time. On average, one safety
violation of Apollo occurs in 12 scenarios generated by LEADE. MOSAT generates
62 scenarios to find one safety violation of Apollo, and AV-Fuzzer generates
131 scenarios to find one safety violation of Apollo. The safety-violation
exposure frequency in LEADE is higher, which shows that LEADE can efficiently
generate more safety-critical scenarios. For the time cost of test scenario
generation, LEADE takes 23 seconds to generate and run a scenario to test
Apollo. The time cost for one test scenario of MOSAT is 24 seconds and that of
AV-Fuzzer is 55 seconds. LEADE generates and executes test scenarios with
almost the same time cost as MOSAT, which is less than AV-Fuzzer. The
comparison results show that LEADE can effectively generate more diverse
safety-violation scenarios.

###  4.4. Result Analysis: RQ2

We run LEADE, $LEADE_{r}$ and $LEADE_{n}$ for 24 hours using the same input
scenario programs. We compare the three approaches from the following aspects,
and the results are shown as Table 9.

  * •

How many types of safety violations of Apollo can be found?

  * •

How long does it take on average to find the first safety-violation scenario?

  * •

How long does it take on average to find all found types of safety-violation
scenarios?

Table 9. Comparison results of LEADE, $LEADE_{r}$ and $LEADE_{n}$ | LEADE | $LEADE_{r}$ | $LEADE_{n}$
---|---|---|---
| types of
---
found SV
10 | 10 | 6
| time to find
---
the first SV
11min | 39min | 17min
| generations to
---
find all SVs
14h | 15h | 22h

Table 9 shows that $LEADE_{r}$ takes the most time to generate the first
safety-violation scenario. It can be seen from Figure LABEL:running that in
early-generation scenarios, the number of safety violations exposed by
$LEADE_{r}$ is the least. We can conclude that LEADE’s first-generation
individual creation is helpful for generating high-quality first-generation
scenarios than random initialization.

For $LEADE_{n}$, the number of found safety violation types of ego vehicle is
fewer than LEADE and $LEADE_{r}$, and it takes more time to generate all found
types of ego vehicle’s safety violations. As the iterations of evolutionary
search increase, the growth of safety-violation scenarios generated by
$LEADE_{n}$ is slowest. We can conclude that the differential seed scenarios
of LEADE can help address the local optimal and find more diverse types of ego
vehicle’s safety violations.

(a) The growth in the found safety violation types over time

(b) The growth in the number of generated safety-violation scenarios over time

Figure 9. The running results of LEADE, $LEADE_{r},LEADE_{n}$

It’s worth noting that, during the iterations of LEADE and $LEADE_{r}$, after
a few types of safety violations have been found, the safety-violation
scenario generation grows faster. We analyze that it benefits from the
feedback-based differential seed scenario generation. As the amount and types
of discovered safety-violation scenarios increase, that of feedback scenarios
increase. LEADE can learn more experience from diverse safety-violation
scenarios, which can improve the quality of the generated differential seed
scenarios.

##  5\. Discussion

To leverage the LLM’s capability, LEADE inputs the prompt into GPT-4 by
sending API request, which brings extra time cost due to waiting for the
output of GPT. Generally, the time cost for each request is about 40 seconds,
which generates 6 scenarios on average. The extra time cost for a scenario
generated by GPT is 7 seconds. In the future, we plan to solve it by employing
the LLM locally, which can further improve the efficiency of LEADE.

In the execution of AVUnit scenario programs, NPC vehicles and pedestrians in
the scenarios must strictly obey the traffic laws. While this constraint may
lead to LEADE missing few safety-violation scenarios caused by anomalous
actions of participants. Considering that they lack practical significance,
currently, the goal of ADS testing is to find the safety violations caused by
AV.

##  6\. Conclusion

In this paper, we propose an approach, LEADE, an LLM-enhanced scenario
generation approach for ADS testing. It leverages LLM’s ability in program
understanding to better comprehend the scenario generation task and generate
high-quality scenarios of the first generation. Based on them, LEADE adopts an
adaptive multi-objective genetic algorithm to search for diverse safety-
critical scenarios. To guide the search away from the local optima, LEADE
leverages LLM’s ability in quantitative reasoning to generate differential
seed scenarios. The experimental results show that LEADE can effectively and
efficiently generate safety-critical scenarios than two state-of-the-art
search-based ADS testing techniques.

## References

  * (1) Autoware self-driving vehicle on a highway.
  * (2) Avunit’s documentation.
  * (3) Baidu launches public robotaxi trial operation.
  * (4) Baidu launches their open platform for autonomous cars–and we got to test it.
  * (5) Navigant research names waymo, ford autonomous vehicles, cruise, and baidu the leading developers of automated driving systems.
  * (6) An open autonomous driving platform, 2013.
  * (7) Nhtsa, 2022.
  * (8) Pre-crash scenarios in nhtsa, 2022.
  * (9) Raja Ben Abdessalem, Annibale Panichella, Shiva Nejati, Lionel C Briand, and Thomas Stifter.  Testing autonomous cars for feature interaction failures using many-objective search.  In 2018 33rd IEEE/ACM International Conference on Automated Software Engineering (ASE), pages 143–154. IEEE, 2018.  doi: 10.1145/3238147.3238192.
  * (10) Matthias Althoff and Sebastian Lutz.  Automatic generation of safety-critical test scenarios for collision avoidance of road vehicles.  In 2018 IEEE Intelligent Vehicles Symposium (IV), pages 1326–1333, 2018.  doi: 10.1109/IVS.2018.8500374.
  * (11) Aitor Arrieta, Shuai Wang, Urtzi Markiegi, Goiuria Sagardui, and Leire Etxeberria.  Search-based test case generation for cyber-physical systems.  In 2017 IEEE Congress on Evolutionary Computation (CEC), pages 688–697. IEEE, 2017.  doi: 10.1109/CEC.2017.7969377.
  * (12) Earl T Barr, Mark Harman, Phil McMinn, Muzammil Shahbaz, and Shin Yoo.  The oracle problem in software testing: A survey.  IEEE transactions on software engineering, pages 507–525, 2014.  doi: 10.1109/TSE.2014.2372785.
  * (13) Sai Krishna Bashetty, Heni Ben Amor, and Georgios Fainekos.  Deepcrashtest: Turning dashcam videos into virtual crash tests for automated driving systems.  In IEEE International Conference on Robotics and Automation (ICRA), 2020.
  * (14) Raja Ben Abdessalem, Shiva Nejati, Lionel C Briand, and Thomas Stifter.  Testing advanced driver assistance systems using multi-objective search and neural networks.  In Proceedings of the 31st IEEE/ACM International Conference on Automated Software Engineering, pages 63–74, 2016.  doi: 10.1145/2970276.2970311.
  * (15) Michele Bertoncello and Dominik Wee.  Ten ways autonomous driving could redefine the automotive world.  McKinsey & Company, 2015.
  * (16) Yumeng Cao, Quinn Thibeault, Aniruddh Chandratre, Georgios Fainekos, Giulia Pedrielli, and Mauricio Castillo-Effen.  Work-in-progress: towards assurance case evidence generation through search based testing.  In 2021 International Conference on Embedded Software (EMSOFT), pages 41–42. IEEE, 2021.
  * (17) Li Chen, Penghao Wu, Kashyap Chitta, Bernhard Jaeger, Andreas Geiger, and Hongyang Li.  End-to-end autonomous driving: Challenges and frontiers.  arXiv preprint arXiv:2306.16927, 2023.
  * (18) Tommaso Dreossi, Alexandre Donzé, and Sanjit A Seshia.  Compositional falsification of cyber-physical systems with machine learning components.  Journal of Automated Reasoning, 63(4):1031–1053, 2019.  doi: 10.1007/s10817-018-09509-5.
  * (19) Shuo Feng, Xintao Yan, Haowei Sun, Yiheng Feng, and Henry X Liu.  Intelligent driving intelligence test for autonomous vehicles with naturalistic and adversarial environment.  Nature communications, pages 1–14, 2021.  doi: 10.1038/s41467-021-21007-8.
  * (20) Daniel J Fremont, Tommaso Dreossi, Shromona Ghosh, Xiangyu Yue, Alberto L Sangiovanni-Vincentelli, and Sanjit A Seshia.  Scenic: a language for scenario specification and scene generation.  In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 63–78, 2019.
  * (21) Alessio Gambi, Tri Huynh, and Gordon Fraser.  Generating effective test cases for self-driving cars from police reports.  In Proceedings of the ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering, 2019.
  * (22) An Guo, Yang Feng, Yizhen Cheng, and Zhenyu Chen.  Semantic-guided fuzzing for virtual testing of autonomous driving systems.  Journal of Systems and Software, page 112017, 2024.
  * (23) Mark Harman.  Automated test data generation using search based software engineering.  In Second International Workshop on Automation of Software Test (AST’07), pages 2–2. IEEE, 2007.  doi: 10.1109/AST.2007.4.
  * (24) Mark Harman, S Afshin Mansouri, and Yuanyuan Zhang.  Search-based software engineering: Trends, techniques and applications.  ACM Computing Surveys (CSUR), 45(1):1–61, 2012.  doi: 10.1145/2379776.2379787.
  * (25) Randy L Haupt.  Optimum population size and mutation rate for a simple real genetic algorithm that optimizes array factors.  In IEEE Antennas and Propagation Society International Symposium. Transmitting Waves of Progress to the Next Millennium. 2000 Digest. Held in conjunction with: USNC/URSI National Radio Science Meeting (C), volume 2, pages 1034–1037. IEEE, 2000.  doi: 10.1109/APS.2000.875398.
  * (26) Mohammad Hekmatnejad, Bardh Hoxha, and Georgios Fainekos.  Search-based test-case generation by monitoring responsibility safety rules.  In IEEE International Conference on Intelligent Transportation Systems (ITSC), 2020.  doi: 10.1109/ITSC45102.2020.9294489.
  * (27) Jean-Michel Jullien, Christian Martel, Laurence Vignollet, and Maia Wentland.  Openscenario: a flexible integrated environment to develop educational activities based on pedagogical scenarios.  In 2009 Ninth IEEE International Conference on Advanced Learning Technologies, pages 509–513. IEEE, 2009.
  * (28) Florian Klück, Martin Zimmermann, Franz Wotawa, and Mihai Nica.  Genetic algorithm-based test parameter optimization for adas system testing.  In 2019 IEEE 19th International Conference on Software Quality, Reliability and Security (QRS), pages 418–425. IEEE, 2019.  doi: 10.1109/QRS.2019.00058.
  * (29) Mark Koren, Saud Alsaif, Ritchie Lee, and Mykel J Kochenderfer.  Adaptive stress testing for autonomous vehicles.  In 2018 IEEE Intelligent Vehicles Symposium (IV), pages 1–7. IEEE, 2018.  doi: 10.1109/IVS.2018.8500400.
  * (30) Guanpeng Li, Yiran Li, Saurabh Jha, Timothy Tsai, Michael Sullivan, Siva Kumar Sastry Hari, Zbigniew Kalbarczyk, and Ravishankar Iyer.  Av-fuzzer: Finding safety violations in autonomous driving systems.  In Proceedings of IEEE International Symposium on Software Reliability Engineering (ISSRE), pages 25–36, 2020.  doi: 10.1109/ISSRE5003.2020.00012.
  * (31) Zhe Liu, Chunyang Chen, Junjie Wang, Xing Che, Yuekai Huang, Jun Hu, and Qing Wang.  Fill in the blank: Context-aware automated text input generation for mobile gui testing.  In 2023 IEEE/ACM 45th International Conference on Software Engineering (ICSE), pages 1355–1367. IEEE, 2023.
  * (32) Phil McMinn.  Search-based software test data generation: a survey.  Software testing, Verification and reliability, 14(2):105–156, 2004.  doi: 10.1002/stvr.294.
  * (33) Athma Narayanan, Isht Dwivedi, and Behzad Dariush.  Dynamic traffic scene classification with space-time coherence.  arXiv preprint arXiv:1905.12708, 2019.
  * (34) Shiva Nejati.  Testing cyber-physical systems via evolutionary algorithms and machine learning.  In 2019 IEEE/ACM 12th International Workshop on Search-Based Software Testing (SBST), pages 1–1. IEEE, 2019.  doi: 10.1109/SBST.2019.00008.
  * (35) Enrique Onieva, Unai Hernández-Jayo, Eneko Osaba, Asier Perallos, and Xiao Zhang.  A multi-objective evolutionary algorithm for the tuning of fuzzy rule bases for uncoordinated intersections in autonomous driving.  Information Sciences, 321:14–30, 2015.  doi: 10.1016/j.ins.2015.05.036.
  * (36) Amir Rasouli, Iuliia Kotseruba, and John K Tsotsos.  Are they going to cross? a benchmark dataset and baseline for pedestrian crosswalk behavior.  In Proceedings of the IEEE International Conference on Computer Vision Workshops, pages 206–213, 2017.
  * (37) Bernardino Romera-Paredes, Mohammadamin Barekatain, Alexander Novikov, Matej Balog, M Pawan Kumar, Emilien Dupont, Francisco JR Ruiz, Jordan S Ellenberg, Pengming Wang, Omar Fawzi, et al.  Mathematical discoveries from program search with large language models.  Nature, 625(7995):468–475, 2024.
  * (38) Konstantinos I Roumeliotis and Nikolaos D Tselikas.  Chatgpt and open-ai models: A preliminary review.  Future Internet, 15(6):192, 2023.
  * (39) Max Schäfer, Sarah Nadi, Aryaz Eghbali, and Frank Tip.  An empirical evaluation of using large language models for automated unit test generation.  IEEE Transactions on Software Engineering, 2023.
  * (40) Seung Yeob Shin, Shiva Nejati, Mehrdad Sabetzadeh, Lionel C Briand, and Frank Zimmer.  Test case prioritization for acceptance testing of cyber physical systems: a multi-objective search-based approach.  In Proceedings of the acm sigsoft international symposium on software testing and analysis, pages 49–60, 2018.  doi: 10.1145/3213846.3213852.
  * (41) Sehajbir Singh and Baljit Singh Saini.  Autonomous cars: Recent developments, challenges, and possible solutions.  In IOP conference series: Materials science and engineering, volume 1022, page 012028. IOP Publishing, 2021.
  * (42) Quinn Thibeault, Jacob Anderson, Aniruddh Chandratre, Giulia Pedrielli, and Georgios Fainekos.  Psy-taliro: A python toolbox for search-based test generation for cyber-physical systems.  arXiv preprint arXiv:2106.02200, 2021.  doi: 10.1007/978-3-030-85248-1_15.
  * (43) Haoxiang Tian, Yan Jiang, Guoquan Wu, Jiren Yan, Jun Wei, Wei Chen, Shuo Li, and Dan Ye.  Mosat: finding safety violations of autonomous driving systems using multi-objective genetic algorithm.  In Proceedings of the 30th ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering, pages 94–106, 2022.
  * (44) Haoxiang Tian, Guoquan Wu, Jiren Yan, Yan Jiang, Jun Wei, Wei Chen, Shuo Li, and Dan Ye.  Generating critical test scenarios for autonomous driving systems via influential behavior patterns.  In Proceedings of the 37th IEEE/ACM International Conference on Automated Software Engineering, pages 1–12, 2022.
  * (45) Cumhur Erkan Tuncali, Georgios Fainekos, Hisahiro Ito, and James Kapinski.  Simulation-based adversarial test generation for autonomous vehicles with machine learning components.  In Proceedings of Intelligent Vehicles Symposium (IV), pages 1555–1562, 2018.  doi: 10.1109/IVS.2018.8500421.
  * (46) Shuai Wang, Shaukat Ali, Tao Yue, Yan Li, and Marius Liaaen.  A practical guide to select quality indicators for assessing pareto-based search algorithms in search-based software engineering.  In Proceedings of International Conference on Software Engineering (ICSE), pages 631–642, 2016.  doi: 10.1145/2884781.2884880.
  * (47) Susan Zhang, Stephen Roller, Naman Goyal, Mikel Artetxe, Moya Chen, Shuohui Chen, Christopher Dewan, Mona Diab, Xian Li, Xi Victoria Lin, et al.  Opt: Open pre-trained transformer language models.  arXiv preprint arXiv:2205.01068, 2022.
  * (48) Xudong Zhang and Yan Cai.  Building critical testing scenarios for autonomous driving from real accidents.  In Proceedings of the 32nd ACM SIGSOFT International Symposium on Software Testing and Analysis, pages 462–474, 2023.
  * (49) Yuan Zhou, Yang Sun, Yun Tang, Yuqi Chen, Jun Sun, Christopher M Poskitt, Yang Liu, and Zijiang Yang.  Specification-based autonomous driving system testing.  IEEE Transactions on Software Engineering, 2023.
  * (50) Marc René Zofka, Florian Kuhnt, Ralf Kohlhaas, Christoph Rist, Thomas Schamm, and J Marius Zöllner.  Data-driven simulation and parametrization of traffic scenarios for the development of advanced driver assistance systems.  In 2015 18th international conference on information fusion (FUSION), pages 1422–1428. IEEE, 2015.


# Breaking Cassie’s law for condensation in a nano-patterned slit

Martin Láska  Department of Physical Chemistry, University of Chemical
Technology Prague, Praha 6, 166 28, Czech Republic;
The Czech Academy of Sciences, Institute of Chemical Process Fundamentals,
Department of Molecular Modelling, 165 02 Prague, Czech Republic  Andrew O.
Parry  Department of Mathematics, Imperial College London, London SW7 2BZ, UK
Alexandr Malijevský  Department of Physical Chemistry, University of Chemical
Technology Prague, Praha 6, 166 28, Czech Republic; The Czech Academy of
Sciences, Institute of Chemical Process Fundamentals, Department of Molecular
Modelling, 165 02 Prague, Czech Republic

###### Abstract

We study the phase transitions of a fluid confined in a capillary slit made
from two adjacent walls each of which are a periodic composite of stripes of
two different materials. For wide slits the capillary condensation occurs at a
pressure which is described accurately by a combination of the Kelvin equation
and the Cassie law for an averaged contact angle. However, for narrow slits
the condensation occurs in two steps involving an intermediate bridging phase,
with the corresponding pressures described by two new Kelvin equations. These
are characterised by different contact angles due to interfacial pinning, with
one larger and one smaller than the Cassie angle. We determine the triple
point and predict two types of dispersion force induced Derjaguin-like
corrections due to mesoscopic volume reduction and the singular free-energy
contribution from nano-droplets and bubbles. We test these predictions using a
fully microscopic density functional model which confirms their validity even
for molecularly narrow slits. Analogous mesoscopic corrections are also
predicted for two dimensional systems arising from thermally induced
interfacial wandering.

Figure 1: Schematic illustration of a) gas-like, b) liquid bridge (blue) and
c) liquid-like configurations in a periodic slit. The edge contact angle
$\theta_{e}$ is highlighted, drawn here for $p>p_{\rm sat}$.

The equilibrium phases of confined fluids have been the subject of long-
standing interest. At the bulk critical point, fluctuations lead to the
thermal analogue of the Casimir force hertlein , while at lower temperatures
the liquid-gas phase boundary is shifted leading to the phenomenon of
capillary condensation fisher ; evans1 ; evans2 ; hend . By having walls which
preferentially adsorb different phases one can also radically alter the nature
of the phase equilibria due to interfacial effects parry_cwalls ; binder03 .
Indeed, it is now possible to observe experimentally the condensation in pores
of different geometries fabricated using electron beam nanolitography bruschi
. In the present paper we discuss the nature of capillary condensation in a
slit for which the walls are periodically patterned with two different types
of material. This is much richer than that occurring for chemically
homogeneous slits since the condensation from gas to liquid may either occur
directly or in two-steps via an intermediate bridge-like phase. The location
of these phase transitions are described by generalized Kelvin equations which
involve one of three possible contact angles each associated with meniscus
pinning. Only one of these angles is the Cassie angle cassie , which lies
between the other two, somewhat analogous to contact angle hysteresis degennes
; quere . By allowing for dispersion forces we predict Derjaguin-like
corrections to the Kelvin equations due to volume reduction and the singular
free-energy of droplets and bubbles adsorbed at the walls.

To begin, we recall the macroscopic Kelvin equation and mesoscopic Derjaguin
correction for condensation in a chemically homogeneous slit, made from two
infinite planar walls separated by a distance $L$. The fluid is at pressure
$p$ (or equivalently chemical potential $\mu$), at a temperature $T$ below the
critical point. Confinement changes the liquid-gas phase boundary, that is the
pressure when gas condenses to liquid, away from the bulk saturation curve
$p_{\rm sat}(T)$. Macroscopically, the shift from $p_{\rm sat}$, at which
capillary condensation (cc) occurs is described by the Kelvin equation thomson

$\delta p_{cc}=\frac{2\gamma\cos\theta}{L}\,,$ (1)

where $\theta$ is the contact angle defined by Young’s equation
$\gamma_{wg}=\gamma_{wl}+\gamma\cos\theta$ for each semi-infinite wall. Here
$\gamma_{wg}$, $\gamma_{wl}$ and $\gamma$ are the tensions of the wall-gas,
wall-liquid and liquid-gas interfaces respectively. For partial wetting the
Kelvin equation is remarkably accurate for $L$ down to tens of molecular
length scales. However, for complete wetting ($\theta=0$), corrections are
apparent at the mesoscopic scale. In particular, for systems with dispersion
forces the Kelvin equation is modified to derj ; evans85

$\delta p_{cc}=\frac{2\gamma}{L-3\ell}\,,$ (2)

which includes the Derjaguin correction allowing for the thickness $\ell$ of
the liquid layer adsorbed at each wall in the gas-like phase. This is very
well approximated as $\ell=(2A/\delta p)^{-1/3}$ , where $A$ is the Hamaker
constant and $\delta p=p_{\rm sat}-p$, corresponding to the wetting layer
thickness at a single wall lipowsky85 ; dietrich .

We now turn to a heterogeneous slit where the walls are made of two materials
arranged into a periodic array of stripes of width $H_{1}$ and $H_{2}$ each
characterised by different contact angles $\theta_{1}$ and $\theta_{2}$. The
two walls are adjacent with translation invariance assumed along the stripes
(i.e. the stripes on the opposing walls are exactly aligned). We assume that
material 1 preferentially adsorbs liquid relative to material 2 so that
$\theta_{1}<\theta_{2}$. The condensation in this capillary may happen by two
mechanisms similar to that if there is a single stripe on each surface laska
or between geometrically structured walls chmiel ; rocken . For wide slits it
occurs via a single first-order phase transition from a gas-like to liquid-
like phase similar to that for a chemically homogeneous slit. However, if the
slit is sufficiently narrow, condensation happens in two steps via an
intermediate phase in which liquid bridges locally condense between the
stripes of the more wettable material 1 (see Fig. 1). We first derive the
generalised, macroscopic Kelvin equations which determine the phase boundaries
for each type of condensation:

One-step condensation. The pressure at which gas condenses to liquid is
determined by balancing the grand potential $\Omega$ per unit length (along
the stripe) and over a single period of the two phases. For the gas-like phase
$\Omega_{g}\approx-pHL+2\gamma_{wg}^{(1)}H_{1}+2\gamma_{wg}^{(2)}H_{2}$, where
$\gamma_{wg}^{(i)}$ are the wall-gas tensions for each material and
$H=H_{1}+H_{2}$. Similarly, for the liquid-like phase we have
$\Omega_{l}\approx-p^{\dagger}HL+2\gamma_{wl}^{(1)}H_{1}+2\gamma_{wl}^{(2)}H_{2}$
where $p^{\dagger}$ is the pressure of the metastable bulk liquid and
$\gamma_{wl}^{(i)}$ are two wall-liquid surface tensions. Balancing the grand
potentials determines that the value of $p-p^{\dagger}\approx\delta p_{cc}$ at
which (single step) capillary condensation occurs is given by

$\delta p_{cc}=\frac{2\gamma\cos\theta_{\rm cas}}{L}\,,$ (3)

which is unaltered if the stripes are not perfectly adjacent, i.e. if the
upper wall (say) in Fig. 1. is shifted or indeed, rotated so the stripes are
no longer parallel. This is the obvious generalization of the standard Kelvin
equation and identifies that the appropriate contact angle appearing in it is
the familiar Cassie angle cassie ,

$\cos\theta_{\rm cas}=f_{1}\cos\theta_{1}+f_{2}\cos\theta_{2}\,,$ (4)

where $f_{i}=H_{i}/H$ is fraction of the wall area occupied by each material.
Viewed in terms of phase separation, $\theta_{\rm cas}$ is the angle that a
circular meniscus of radius $R=\gamma/\delta p_{cc}$, which separates the
coexisting phases, meets both walls at one of the edges between the two
materials.

Two-step condensation. In this case, there are two phase boundaries
corresponding to a pressure shift $\delta p_{gb}$, where the gas phase locally
condenses to a bridge phase, and a second $\delta p_{lb}$ (at higher pressure)
when the bridge phase condenses to liquid. These are determined by matching
the grand potential of a bridge phase $\Omega_{b}$ with $\Omega_{g}$ and
$\Omega_{l}$. In each unit cell the liquid bridge is bounded by two circular
menisci of radius $R=\gamma/\delta p$ which are pinned at the edges between
the two materials (see Fig. 1). These meet the walls at an edge contact angle
$\theta_{e}$ which is related to the pressure by $\cos\theta_{e}=L/2R$. The
grand potential of the bridge phase is given by $\Omega_{b}\approx-
pA_{g}-p^{\dagger}A_{l}+2(H_{1}\gamma_{wl}^{(1)}+H_{2}\gamma_{wg}^{(2)})+2\gamma
l_{\rm men}$ where $A_{g}$ and $A_{l}$ are the areas occupied by the gas and
(metastable) liquid, respectively, and $l_{\rm men}$ is the length of each
meniscus. Equating this value with $\Omega_{g}$ and $\Omega_{l}$ determines
the pressure shifts as

$\delta p_{gb}=\frac{2\gamma\cos\theta_{gb}}{L}\,,\;\delta
p_{lb}=\frac{2\gamma\cos\theta_{lb}}{L}\,,$ (5)

where $\theta_{gb}$ are $\theta_{lb}$ are the values of the edge contact
angles at the respective phase transitions given by fin_slit

$\cos\theta_{1}=\cos\theta_{gb}+\frac{L}{2H_{1}}\left[\sin\theta_{gb}+\sec\theta_{gb}\left(\frac{\pi}{2}-\theta_{gb}\right)\right]$
(6)

and

$\cos\theta_{2}=\cos\theta_{lb}-\frac{L}{2H_{2}}\left[\sin\theta_{lb}+\sec\theta_{lb}\left(\frac{\pi}{2}-\theta_{lb}\right)\right]\,,$
(7)

which satisfy $\theta_{gb}<\theta_{\rm cas}<\theta_{lb}$. The phase transition
occurring at $\delta p_{lb}$ is equivalent to the local evaporation of liquid
between the less wettable stripes as $p$ is reduced.

Figure 2: Contact angles appearing in the macroscopic Kelvin equations for one
step and two step condensation [see equations (3) and (5)] in a maximum
contrast slit ($\theta_{1}=0$ and $\theta_{2}=\pi$) as a function of the
aspect ratio $a=L/H_{1}$. For equal area fractions, $f_{1}=f_{2}=\frac{1}{2}$,
the triple point occurs at $a_{T}=1$.

Condensation occurs via one step if $\theta_{gb}>\theta_{\rm cas}$ (wide
slits) or two steps if $\theta_{gb}<\theta_{\rm cas}$ (narrow slits). The
marginal case between these two different mechanisms occurs when
$\theta_{gb}=\theta_{lb}$ (equivalent to each being equal to $\theta_{\rm
cas}$) and identifies the triple point (T) where the gas-like, liquid-like and
bridging phases coexist. This happens when the aspect ratio $a\equiv L/H_{1}$
takes the value

$a_{T}=\frac{2f_{2}(\cos\theta_{1}-\cos\theta_{2})}{\sin\theta_{\rm
cas}+\sec\theta_{\rm cas}\left(\frac{\pi}{2}-\theta_{\rm cas}\right)}\,.$ (8)

In the limit $f_{1}=0$, Eq. (8) reduces to the result pertinent to a parallel
plate geometry in which there is just a single, adjacent stripe, of material 1
on each wall laska . If the aspect ratio is greater than this value the
condensation occurs via one step. We illustrate this in Fig. 2 where we plot
the three contact angles appearing in the generalised Kelvin equations for a
_maximum contrast_ slit ($\theta_{1}=0$ and $\theta_{2}=\pi$) as a function of
the aspect ratio $a$ for equal stripe widths $H_{1}=H_{2}$.

Figure 3: DFT results determining the triple point for the maximum contrast
slit with $H_{1}=H_{2}=40\,\sigma$ and slit width $L=48\,\sigma$. The graph
shows that the grand potential (per unit length, over one cell and in units,
$\varepsilon$, of the fluid-fluid potential strength SP ) as a function of the
undersaturation [$\delta\mu=(\mu_{\rm sat}-\mu)/\varepsilon$] for the gas-
like, liquid-like and bridge configurations all intersect at a value of the
chemical potential close to, but slightly away from bulk saturation. The
triple point aspect ratio $a_{T}=1.2$, below which Cassie’s law breaks down,
is slightly above the macroscopic prediction $a_{T}=1$ in accordance with Eq.
(11).

Figure 4: Equilibrium density profiles (over one period) for coexisting states
at the triple point for a maximum contrast slit with $H_{1}=H_{2}=40\,\sigma$
and $L=48\,\sigma$. Left and right correspond to gas-like and liquid-like
phases for which liquid droplet and gas bubbles are visible, while the centre
plot corresponds to the bridge state with a near flat meniscus. Figure 5: DFT
results of the triple point aspect ratio of a maximum contrast slit for
increasing slit width (in units of $\sigma$) showing the approach to the
macroscopic result $a_{T}=1$. The inset shows that the mesoscopic result (11)
is accurate down to molecularly narrow slits with $L\approx 15\,\sigma$.

These macroscopic arguments do not allow for the direct influence of
dispersion forces. Recall that for a homogeneous slit, they may be safely
ignored for partial wetting but lead to the Derjaguin correction (2) for
complete wetting. The situation is somewhat richer for the patterned slit. If
both materials are partially wet, then, as for the homogeneous case, we
anticipate that the Kelvin equations for one and two step condensation remain
accurate down to molecularly narrow slits. However, if one of the materials is
wet (or dry) then the influence of the long-range forces become important at
the mesoscopic scale. This is most transparent when we consider the maximum
contrast slit described above where material 1 is completely wet and material
2 is completely dry. In the gas-like phase each stripe of material 1 is wet by
a drop of liquid and, in the liquid-like phase, each stripe of material 2 is
wet by a bubble of gas. The volumes of these, which would become macroscopic
as $H_{1}$, $H_{2}$ and $L$ increase need to be taken into account when we
consider, for example, the value of the pressure shift $\delta p_{T}$ at the
triple point. The shape of these drops and bubbles is determined by the
intermolecular forces and can be calculated using interfacial Hamiltonian
methods posp_stripe . The pressure shift at the triple point for the maximum
contrast slit is then modified from (3) to

$\delta p_{T}=\frac{2\gamma\cos\theta_{\rm
cas}}{L-\frac{\pi}{4}(f_{1}l_{D}+f_{2}l_{B})}\,,$ (9)

where $l_{D}=(A_{1}/2\gamma)^{1/4}\sqrt{H_{1}}$ is the maximum thickness of
the wetting drop and $l_{B}=(A_{2}/2\gamma)^{1/4}\sqrt{H_{2}}$ is the maximum
thickness of the drying bubble. Here $A_{1}$ and $A_{2}$ are the Hamaker
constants for each material. Since at the triple point $H_{1}$ and $H_{2}$ are
both of order $L$, the reduction in the effective slit width is _greater_ than
that occurring in a homogenous system (since at condensation $\ell\sim
L^{1/3}$). Note that as $H_{2}$ is reduced to a value $\propto\ln H_{1}$ the
drops coalesce to cover the whole surface corresponding to a first-order
wetting transition at which $\theta_{\rm cas}$ vanishes posp_bridge . For
smaller values of $H_{2}$ both walls are completely wet and the location of
the single step condensation is described by the usual Derjaguin correction
(2).

The location of the triple point for the maximum contrast slit is most subtle
when the area fractions are equal, $f_{1}=f_{2}=1/2$, since in that case the
wall is overall neutral, $\theta_{\rm cas}=\pi/2$. The Kelvin-Cassie equation
(3) predicts that single step condensation occurs at $p_{\rm sat}$, while Eq.
(8) predicts that the triple point occurs for $a_{T}=1$ (see Fig. 2). This
macroscopic prediction for $a_{T}$ is easy to understand. The menisci which
bound the liquid bridges are flat with a free-energy cost of $2\gamma L$ per
unit cell. For the gas-like (liquid-like) phase this must be compensated by
having a drop of liquid (bubble of gas) coat the wet (dry) stripes which
carries with it a macroscopic free-energy cost of $2\gamma H_{1}$ per unit
cell. Thus, purely macroscopically, the triple point must occur for $L=H_{1}$.
When we include dispersion forces however, the surface free-energy of a liquid
drop, and similarly for the gas bubble, contains a Casimir-like contribution
$\sqrt{2A_{1}/\gamma}\ln\left(H_{1}/\sigma\right)$ where $\sigma$ is a
molecular diameter. Taking these into account determines the higher-order
contribution to Eq. (9) when the walls are neutral

$\delta p_{T}=\sqrt{2\gamma}(\sqrt{A_{1}}-\sqrt{A_{2}})\frac{\ln
L/\sigma}{L^{2}}\,;\;\;\;\;\;{\rm for}\;\theta_{\rm cas}=\frac{\pi}{2}$ (10)

This small shift therefore owes its origin to the difference in the strengths
of the dispersion forces; we note that it is larger than the shift $\delta
p_{cc}=2A/L^{3}$ for a homogeneous slit when $\theta=\pi/2$. Similarly, for
the aspect ratio we find

$a_{T}=1+\frac{\sqrt{A_{1}}+\sqrt{A_{2}}}{\sqrt{2\gamma}}\frac{\ln
L/\sigma}{L}+\cdots\,,$ (11)

which approaches unity as the slit width increases.

We have tested the above prediction for the value of $a_{T}$ for the maximum
contrast slit using a microscopic density functional theory (DFT) which we use
to determine the equilibrium density profiles and free-energies of stable and
metastable phases evans79 . These are obtained by minimizing a grand potential
functional

$\Omega[\rho]={\cal F}[\rho]+\int{\rm d}{\mathbf{r}}\rho({\bf
r})[V({\mathbf{r}})-\mu]\,,$ (12)

where $V({\mathbf{r}})$ is the external potential modelling the long-ranged
interaction from the patterned walls and ${\cal F}[\rho]$ is the intrinsic
free-energy functional for which we use Rosenfeld’s Fundamental Measure Theory
ros  (see Supplemental Material SP ). We have determined the phase coexistence
for system sizes ranging from $L=10\,\sigma$ to $L=110\,\sigma$ and for
different stripe widths $H_{1}$ (=$H_{2}$). Fig. 3 shows the equilibrium grand
potential versus the undersaturation close to the triple point for
$H_{1}=H_{2}=40\,\sigma$ and $L=48\,\sigma$. The three coexisting density
profiles are shown in Fig. 4. Finally, in Fig. 5 we plot the triple point
aspect ratio as a function of slit width which shows that, as predicted, the
value tends to unity as $L$ increases. In the inset we show that the deviation
from unity is extremely well described by the $\ln L/L$ correction in
accordance with the prediction (11).

In 3D these results are not affected significantly by thermal fluctuations
where their only influence is to round the bridging transitions associated
with two-step condensation over a pressure range $\mathcal{O}({\rm e}^{-\gamma
LH/k_{B}T})$. Thermal fluctuations are much more important in 2D for systems
with short-ranged forces. Here, a simple realization of the neutral wall is an
Ising strip of width $L$ where the surface spins are fixed to be up and down
each over a distance $H_{1}$. Single step condensation between predominately
down spin (analogous to gas) and up spin (liquid) phases, occurs at zero bulk
field, $h=0$, rounded over a scale $\mathcal{O}({\rm e}^{-\gamma L/k_{B}T})$,
while bridging occurs away from $h=0$ (except at the triple point) and is
rounded over a scale $\mathcal{O}(1/LH_{1})$ privman . Interfacial wandering
in all three phases leads to similar mesoscopic corrections to those predicted
for dispersion forces. These can be determined using random walk arguments and
interfacial models fisher84 ; parry92 ; jak . For the gas phase, the entropic
repulsion of the interfaces that bound the liquid drops from the walls leads
to a partition function (per unit cell and at $h=0$) given by $Z_{g}\approx
e^{-2\gamma H_{1}/k_{B}T}/H_{1}^{3}$ and similarly for the liquid phase. For
the bridge, on the other hand $Z_{b}\approx{\rm e}^{-2\gamma L/k_{B}T}/L$
arising from the wandering of the two near flat menisci. Balancing the free-
energies determines that a pseudo triple point occurs at $h=0$ when the aspect
ratio is $a_{T}\approx 1+\frac{k_{B}T}{\gamma}\frac{\ln L}{L}$. This may be
checked numerically and may even be amenable to exact analysis binder ; zuba ;
abraham07 ; abraham .

In this paper, we have shown that the locations of one-step and two-step
capillary condensation in patterned slits are described by Kelvin equations
involving three possible contact angles, only one of which is the Cassie angle
$\theta_{\rm cas}$ for which we give an explicit geometrical interpretation.
However, for narrow slits Cassie’s law is broken and two-step condensation is
characterized by different angles which arise from meniscus pinning. The
pinning associated with these angles not only determines the phase equilibria
but will also have a strong influence on metastability relevant to
experimental studies and may well underpin the phenomena of contact angle
hysteresis. Mesoscopic Derjaguin-like corrections are significantly larger
than those for condensation in homogenous slits and are predicted in both 2D
and 3D.

This work was financially supported by the Czech Science Foundation, Project
No. 20-14547S, and the European Union s Horizon 2020 research and innovation
program (Project VIMMP: Virtual Materials Marketplace, No. 760907).

## References

  * (1) C. Hertlein, L. Helden, A. Gambassi, S, Dietrich, and C. Bechinger, Nature 451, 7175 (2008).
  * (2) M. E. Fisher and H. Nakanishi, J. Chem. Phys. 75, 5857 (1981).
  * (3) R. Evans, P. Tarazona and U. Marini Bettolo Marconi, J. Chem. Phys. 84, 2376 (1986).
  * (4) R. Evans, J. Phys.: Condens. Matter. 2, 8989 (1990).
  * (5) D. Henderson, Fundamentals of Inhomogeneous Fluids, (New York: Dekker, 1992).
  * (6) A. O. Parry and R. Evans, Phys. Rev. Lett. 64, 439 (1990).
  * (7) K. Binder, D. Landau, and M. Müller, J. Stat. Phys. 110, 1411 (2003).
  * (8) L. Bruschi, G. Mistura, L. Prasetyo, D. D. Do, M. Dipalo, and F. De Angelis, Langmuir 34, 106 (2018).
  * (9) A. B. D. Cassie, Discuss. Faraday Soc. 3, 11 (1948).
  * (10) P. de Gennes, F. Brochard-Wyart, and D. Quèrè, Capillarity and Wetting Phenomena: Drops, Bubbles, Pearls, Waves, Springer New York, (2013).
  * (11) D. Quèrè, Annu. Rev. Mater. Res. 38, 71 (2008).
  * (12) W. Thomson, Phil. Mag. 42, 448 (1871).
  * (13) B. V. Derjaguin, Acta Phys. Chem. 12, 181 (1940).
  * (14) R. Evans and U. Marini Bettolo Marconi, Chem. Phys. Lett. 114, 415 (1985).
  * (15) R. Lipowsky, Phys. Rev. B 32, 1731 (1985).
  * (16) S. Dietrich, in Phase Transitions and Critical Phenomena, edited by C. Domb and J. L. Lebowitz (Academic, New York, 1988), Vol. 12.
  * (17) M. Láska, A. O. Parry, and A. Malijevský, Phys. Rev. Lett. 124, 115701 (2020).
  * (18) G. Chmiel, K. Karykowski A. Patrykiejew, W. Rżysko and S. Sokołowski, Mol. Phys. 81, 691 (1994).
  * (19) P. Röcken, A. Somoza, P. Tarazona, and G. Findenegg, J. Chem. Phys. 108, 8689 (1998).
  * (20) A. Malijevský, A. O. Parry, and M. Pospíšil, Phys. Rev. E 96, 020801(R) (2017).
  * (21) A. Malijevský, A. O. Parry, and M. Pospíšil, Phys. Rev. E 96, 032801 (2017).
  * (22) A. Malijevský, A. O. Parry, and M. Pospíšil, Phys. Rev. E 99, 042804 (2019).
  * (23) R. Evans, Adv. Phys. 28, 143 (1979).
  * (24) Y. Rosenfeld, Phys. Rev. Lett. 63, 980 (1989).
  * (25) See Supplemental Material for details of the DFT model.
  * (26) V. Privman and M. E. Fisher, J. Stat. Phys. 33, 385 (1983).
  * (27) M. E. Fisher, J. Stat. Phys. 34, 667 (1984).
  * (28) A. O. Parry and R. Evans, J. Phys. A 25 275 (1992).
  * (29) P. Jakubczyk, M. Napiórkowski, and A. O. Parry, Phys. Rev. E 74, 031608 (2006).
  * (30) K. Binder, D. Landau, and M. Muller, J. Stat. Phys. 110, 1411 (2003).
  * (31) M. Zubaszewska, A. Gendiar and A. Drzewinski, Phys. Rev. E 86, 062104 (2012).
  * (32) D. B. Abraham, F. H. L. Essler, and A. Maciołek, Phys. Rev. Lett. 98, 170602 (2007).
  * (33) D. B. Abraham and A. Maciołek, Phys. Rv. Lett. 105, 055701 (2010).