ComOpT: Combination and Optimization for Testing Autonomous Driving Systems

ComOpT is an open-source research tool for coverage-driven testing of autonomous driving systems, focusing on planning and control. Starting with (i) a meta-model characterizing discrete conditions to be considered and (ii) constraints specifying the impossibility of certain combinations, ComOpT first generates constraint-feasible abstract scenarios while maximally increasing the coverage of k-way combinatorial testing. Each abstract scenario can be viewed as a conceptual equivalence class, which is then instantiated into multiple concrete scenarios by (1) randomly picking one local map that fulfills the specified geographical condition, and (2) assigning all actors accordingly with parameters within the range. Finally, ComOpT evaluates each concrete scenario against a set of KPIs and performs local scenario variation via spawning a new agent that might lead to a collision at designated points. We use ComOpT to test the Apollo~6 autonomous driving software stack. ComOpT can generate highly diversified scenarios with limited test budgets while uncovering problematic situations such as inabilities to make simple right turns, uncomfortable accelerations, and dangerous driving patterns. ComOpT participated in the 2021 IEEE AI Autonomous Vehicle Testing Challenge and won first place among more than 110 contending teams.


I. INTRODUCTION
The development of autonomous driving (AD) technologies has reached the stage where the safety of such systems is a dominating factor for defining success. For verification and validation of autonomous vehicles in a fixed operational design domain (ODD), simulation-based testing is one of the highly recommended methods for modular testing of planning and control systems. The simulation environment can provide object labels such as bounding boxes (as a replacement of the perception module), allowing the prediction and planning modules to be tested in isolation. Nevertheless, the critical challenge remains to be designing the test case generation and management module. Within a limited test budget, the test case generation module should outsmart the AD system under test by creating scenarios that lead to undesired behavior (e.g., collision). Simultaneously, to demonstrate sufficient coverage over the ODD, the generation of test cases should be coverage-driven while ensuring diversity.
Towards the aforementioned challenges, we present Co-mOpT, an open-source research tool (under the AGPL v3 license) for coverage-driven testing of autonomous driving systems. As of September 2021, ComOpT interfaces to the open-source simulator LGSVL [1] and the Baidu Apollo autonomous driving software stack [2]. Internally, ComOpT integrates an axiomatic approach to generate abstract scenarios from a pre-defined list of categories. Every element in a category has its physical interpretation reflected in the simulation environment. One combination forms an abstract scenario, which can be instantiated in the simulation environment by (a) assigning a local map as well as (b) concretizing every element by picking a value in its associated parameter range. Although the axiomatic approach of abstract scenario generation sounds intuitive at first glance, it suffers from three crucial limitations in terms of realization: 1) Combinatorial explosion: Given N categories with each category having only 2 elements, there exist 2 N possible abstract scenarios in the worst case. 2) Feasibility considerations: Certain combinations are semantically unclear (e.g., making a left-turn in a straight-line road segment) or simply nonexistent in the ODD under consideration (e.g., no roundabout with pedestrian crossings in the map). 3) Semantically enriched map: Concretizing an abstract scenario requires searching for high-level concepts such as intersection types; these concepts are nonexistent in standard map formats.
For the first two issues, ComOpT utilizes the technique of constraint-based k-way combinatorial testing [3], [4]. Combinatorial testing [5] provides a coverage metric by requiring test cases to cover all element tuples for any k categories. The constraint-based variation allows integrating feasibility constraints, while implementing it using optimization solvers (e.g., mixed-integer linear programming) allows suggesting new test cases that maximally increase coverage. For the third issue, ComOpT implements a special module that allows querying high-level semantic information. In particular, it allows searching for local maps that can satisfy a specific combination of conditions (e.g., find all T-way junctions having pedestrian-crossings).
Finally, given a concrete scenario tested against a set of KPIs, ComOpT includes methods that can perform local perturbation over the scenario based on an innovation called agent spawning. Concretely, ComOpT introduces new agents (e.g., vehicles) to challenge the AD system. How these agents are introduced depends on the high-level behavioral pattern of the ego vehicle extracted from the simulated trace.
ComOpT participated in the 2021 IEEE AI Autonomous Vehicle Testing challenge. Apart from convincing scenario coverage and diversity metrics, ComOpT discovered numerous undesired scenarios for the Apollo Autonomous Driving SW stack, including situations to hit crossing pedestrians or inabilities to make trivial right turns. Ultimately, ComOpT won first place in the competition (within more than 110 contending teams), serving as objective evidence of the system performance.

II. RELATED WORK
Testing autonomous driving systems has been an active research field, and many autonomous driving safety standards such as ISO PAS 21448 SOTIF (Safety of Intended Functionality) [6] or UL 4600 [7] consider simulation-based testing to be instrumental. There are recent programmatic methods such as Scenic [8] or Paracosm [9] that allow specifying and generating scenarios for AD testing. The abstraction that ComOpT takes is one layer higher, supported by an automatic translation from the map of the ODD to a list of sub-maps matching the specification. This implies that given a specific ODD (e.g., Munich city), methods suggested by Scenic or Paracosm cannot easily provide coverage claims over the ODD. These methods are more applicable to re-specify a small number of scenarios, such as known crash scenarios. The Scenic tool, together with the CPS falsification tool VerifAI [10], also participated as an integrated testing framework in the 2021 IEEE AI testing competition [11] but failed to compete against ComOpT. 1 Within the scope of autonomous driving, prior work on combinatorial testing focuses on testing deep neural networks [3], [12], [4]. However, the black-box feature also makes it also highly applicable to be used in testing prediction and planning modules, as demonstrated by this work. With the semantic enrichment of maps, we can use combinatorial testing to argue the completeness of abstract scenarios against the ODD, thereby further differentiating ComOpT from other works. Apart from an axiomatic approach demonstrated by ComOpT, other commonly seen approaches include replaying existing crash scenarios (e.g., NHTSA accident database [13]) or scenario databases created by physical driving or by collective efforts (e.g., Pegasus [14] or SafetyPool [15]). One can run these scenarios (from standard formats ASAM OpenScenario [16]) and subsequently, perform scenario variations via various CPS falsification techniques [17], [18], [19], [10], [20], [21]. While we surely understand the benefit of scenario replay, ComOpT aims more -scenario replay and variation are incapable of arguing diversity and completeness. Finally, the previously mentioned CPS falsification techniques [17], [18], [19], [10], [20], [21] largely take low-level information traces such as vehicle position and velocity profiles and perform the search. In contrast, our scenario variation method (agent spawning) also integrates high-level semantic information such as behavioral patterns of the ego-vehicle and positions related to lanes to avoid performing a search in unnecessarily high parameter dimensions. Some of the low-level scenario variation methods also integrate constraint-free combinatorial testing in dealing with discrete variables [17], [9]. However, ComOpT uses a constraint-based version on the abstract (high-level) scenario generation; constraints are introduced due to considerations on encoding scenario infeasibility.

III. INSIDE COMOPT
In this section, we detail the underlying techniques integrated inside ComOpT. To ease understanding, Figure 1 provides a summary of the workflow and associates each function with the corresponding subsection in this paper.

A. Abstract scenario generation via combinatorial testing
In this stage, the input of ComOpT is a list of discrete categories serving as the basis for abstract scenario generation. To ease understanding, throughout this paper, we consider the following overly simplified three categories.
• weather ∈ {sunny, rainy, cloudy}, • road ∈ {straight, T-shaped}, and • ego-action ∈ {drive-straight, left-turn, u-turn}. Apart from categories, ComOpT also takes explicitly stored constraints stating that certain combinations are impossible 2 . For example, if the road is straight, it is impossible for the autonomous vehicle to take a left turn. Utilizing the defined categories, the statement can be written as a logical formula "road.straight → ¬ego-action.left-turn".
ComOpT uses k-way combinatorial testing as a coverage criterion, whose goal is to ensure that the set of tested scenarios can cover all combinations for arbitrary k categories. To increase k-way coverage while avoiding certain scenario combinations, the abstract scenario generation problem is reduced to a mixed-integer linear programming (MILP) problem, with the objective being maximally increasing the coverage. The encoding is borrowed from our earlier work for testing ML-based systems [3]. A simple illustration of the 2-way combinatorial testing can be found in Figure 2. First, ComOpT builds tables for three categories mentioned earlier, i.e., C 1 = weather, C 2 = road, and C 3 = ego-action. A table is associated with every pair of categories; therefore a total of three 3 2 categories. With a particular combination being impossible (in this simple example, it is stated that it is impossible to do a left turn when the road is straight), the total number of empty cells to be filled equals 20 (C 1 , C 2 : 9; C 2 , C 3 : 5; C 1 , C 3 : 6). Given that there exists the first abstract scenario sunny, drive-straight, straight , the MILP will propose the second scenario rainy, u-turn, T-shaped that can maximally increase the metric by filling 3 cells. When all cells are filled, we have achieved a relative form of completeness where every category pair is covered. Observe that two abstract scenarios in Figure 2 have very different characteristics. By proceeding with such methods, the testing is truly driven by coverage, and we can guarantee that every abstract scenario is different from previously generated ones at least in one category, thereby guaranteeing diversity.
Finally, readers may raise concerns about generating complex routes via an axiomatic approach. Nevertheless, for any complex route within the ODD, one can always view it as a concatenation of multiple simple sub-journeys with each subjourney to cross a junction or drive along a lane segment (without intersection). Therefore, when ComOpT performs systematic testing, it just considers driving scenarios with various initial configurations under a single junction (e.g., Tshaped, roundabout) or a lane segment without intersection.

B. Concrete scenario generation
From a synthesized abstract scenario, ComOpT generates a concrete scenario by querying the map and the simulator. Detailed actions include finding a sub-map that satisfies all geographical conditions, locating the ego vehicle (here referring to the vehicle being controlled by the autonomous driving software stack), configuring Non-Player Character (NPC) vehicles and pedestrians, and setting up simulation parameters such as weather.
1) Sub-map finding based on semantic information: For a specific road structure matching the semantic information, such as T-shaped junction, ComOpT needs to search for the corresponding sub-map in the map and assign all agents accordingly. Due to space limits, we only highlight how a T-shaped junction is discovered using the junction example in Figure 3. We refer readers to the ComOpT documentation (in the source tree: scripts/comopt/map parse/README.md) for details on identifying other road structures.
First, for a given junction, ComOpT considers the number of related roads. Road structures with the same number of related roads are allocated into the same group. In Figure 3, three roads connect to junction J 5. Then ComOpT computes the angles between related roads. The angle sequence of adjacent roads is used to match the unique angle range sequences of each road structure class. In Figure 3, roads with identifiers road 115, road 116, and road 117 form angles of 181.7, 90.1, and 88.2 degrees. The computed degrees match the specification of a T-shaped junction, where for an ideal T-shaped junction, the incoming roads should form angles of 180, 90, and 90 degrees. Junction J 5 will not be categorized as a Y-shaped junction; as for a Y-shaped junction, incoming roads should form angles around 120, 120, and 120 degrees.
2) Concrete scenario generation outline: To demonstrate how ComOpT generates concrete scenarios with map data, we consider the example in Figure 4 which is a detailed visualization for the junction J 5. The detailed process is as follows: • Step 1 -assigning the initial road for the ego vehicle: We first decide the initial road segment for the ego vehicle, such that the specified ego behavior in an abstract scenario is legal and feasible (without collision

3) Non-road related parameter instantiation:
For other parameters, the instantiation from an abstract scenario to a concrete scenario requires a mapping process to the simulated world. As an example, in the parameter mapping file, it is specified that the weather "cloudy" stated in the abstract scenario is mapped to the LGSVL simulator with the following parameter range: Therefore, when instantiating concrete scenarios, one can either select the medium value or assign a random value within the range. ComOpT predominantly uses random assignment, but for parameters to be perturbed in later scenario variation (e.g., number-of-vehicles), ComOpT carefully selects the value to avoid being on the boundary.

C. KPI for evaluating the quality of the scenario
Once when a concrete scenario is created, ComOpT runs the scenario and uses a set of metrics to evaluate if an undesired situation occurs. The set of undesired situations considered by ComOpT includes (a) collision or being very close, (b) uncomfortable brake or sudden acceleration, (c) lateral jerk, (d) route deviation, and finally (e) ignoring traffic signals. Note that for route deviation, it includes events such as driving out-of-road (e.g., onto the sidewalk) as well as inabilities to make simple right turns when the destination is simply placed at the right of the intersection.

D. Local scenario variation via agent spawning
When a concrete scenario does not demonstrate undesired behavior, ComOpT introduces a new scenario perturbation technique called agent spawning to find scenario variations that can make the resulting simulation demonstrating undesired behavior. Initially, the concrete scenario may have some agents (e.g., pedestrians or other road vehicles). The maximum number of additional agents that can be added is constrained by the equivalence class specified in the abstractto-concrete mapping information. E.g., for vehicle density being mild, in the concrete scenario, it is possible to have the number of vehicles within range [3,6]. Therefore, if the current concrete scenario has only 4 vehicles, it is still possible to spawn 2 additional vehicles while the scenario is still within the equivalence class defined by the abstract scenario.
The premise of applying agent spawning requires analyzing the timed trace over a concrete scenario. A timed trace represents the state of every agent (ego vehicle, NPC, traffic light, etc) under a predefined time granularity (e.g., 0.1 second) recorded in the simulation. The purpose of analyzing the timed trace contains two goals: (a) extract the high-level behavioral information of the ego vehicle, and based on the high-level behavioral information, (b) decide how to inject a new NPC in the existing scenario that may lead to a collision. In the following, we detail the underlying workflow. 2) Extracting the targeted collision points: Subsequently, ComOpT extracts the targeted collision points out of the behavioral sequence, where we expect the introduced NPC 3) Altering the scenario by adding one new NPC: Subsequently ComOpT decides, for each targeted collision point and its associated behavioral pattern, possible ways for introducing an NPC to induce a collision. We use again the scenario in Figure 5a to explain the concept. While for each pattern (e.g., lane-following) there is a fixed set of NPC control strategies (e.g., braking or being stationary), how to derive the concrete configuration remains to be solved. For simple control strategies such as setting the NPC to be stationary, deriving the configuration is trivial. For other cases, one needs to utilize physics to infer the possible configuration. For example, consider the scenario in Figure 5c where ComOpT plans to spawn an NPC to drive along the adjacent lane. Provided that the NPC shall be close to position C at time t, if the NPC drives under a fixed velocity v, then it should be placed initially at a position that is approximately vt meters away from point C. In the implementation, the distance to point C is relaxed by a set [vt − ∆, vt + ∆], with ∆ being a constant to allow considering nearby starting positions. 4) Scenario testing via optimization-based parameter search: Summarizing the process until now, given a concrete scenario, for each targeted collision point, ComOpT derives a parameterized scenario where the parameter is the initial distance between the newly spawned NPC and the targeted collision point. Finally, ComOpT performs a systematic search over the parameterized scenario. One can adopt multiple strategies such as randomization or uniform sampling to derive concrete parameters, in order to find scenarios with the ego vehicle demonstrating undesired behavior. However, testing a scenario is computationally expensive: it requires executing the autonomous driving stack in the simulation environment. Therefore, we have used an optimization-based approach to guide the finding of suitable parameters that lead to a collision.
The optimization target is to reach the situation where (1) the newly introduced NPC first reaches the targeted collision point, thereby generating possibilities for the ego vehicle to hit the NPC. Meanwhile, (2) the time when the introduced NPC reaches the targeted collision point should ideally be slightly earlier than the ego vehicle.
Therefore, if the time when the NPC drives through the targeted collision point is substantially earlier than the time when the ego vehicle reaches there, ComOpT increases the distance between the NPC's initial location and the targeted collision point. On the contrary, when the NPC arrives at the targeted collision point much later than the ego vehicle, ComOpT decreases the initial distance. Due to space limits, we refer readers to the source code for concrete configurations such as step size.

5)
Managing the ordering of scenarios to be tested, and termination: In previous subsections, we detail how to derive a new scenario to be tested, under a unique targeted collision point. However, as shown in Figure 5a, there are multiple targeted collision points (A, B, C, D) to be considered. To this end, one requires a meta-level search strategy to manage the ordering on the scenarios to be tested, as well as setting up proper termination criteria. We exemplify the underlying meta-level search strategy using Figure 5.
First, ComOpT maintains a priority queue over the targeted collision points, where the priority is based on the associated behavioral pattern of the point. For example, lanechange-right has higher priority over lane-following. Therefore, in Figure 5a, the targeted collision point C is explored first, leading to the parameterized scenario in Figure 5c. By varying the initial location of the NPC and running the simulation, one of the situations may occur: • The ego vehicle collides with other NPCs, as demonstrated in Figure 5f. Then the search terminates.  Figure 5d. This scenario will be further explored. Therefore, targeted collision points E, F, G, and H will be added to the existing priority queue containing A, B, and D. ComOpT then selects point G to be further explored, due to its associated pattern lane-change-left having higher priority. Finally, to ensure termination, ComOpT sets a fixed budget on the number of simulations to be executed whenever local scenario perturbation algorithm is triggered.

IV. EVALUATION ON BAIDU APOLLO AND LGSVL
This section details the result evaluated on the Baidu Apollo 6.0 AD stack (master branch taken on 2021.04.14) and the LGSVL simulator (version 2021.01). The configuration reported in this paper is based on the version that participated in the 2021 IEEE Autonomous Vehicle Testing Challenge. We refer readers to the following YouTube channel for a summary of results, including (1) a two-minute teaser video highlighting the techniques and some undesired scenarios, and (2) additional 40 problematic AD driving scenarios discovered by ComOpT.
https://www.youtube.com/playlist?list= PL6ii4xJXGd8L3bn9pWuchuKBPb0R5JgJ7 For the version used in the competition, ComOpT is set with a default configuration to generate the first 15 abstract scenarios (equivalence classes) that maximally increase coverage governed by 2-way combinatorial testing. We assume that the ODD is defined using the San Francisco map as supported by the LGSVL simulator. Therefore, the atomic map geometry only contains straight lanes, T-way junctions, and 4-way intersections. We need to explicitly specify constraints such as "no roundabouts" to prevent the abstract scenario generator from creating such candidates. Table I highlights the statistical summary of the generated scenarios. Every column lists the number of such scenarios. The scenario set base has 45 concrete scenarios, as each abstract scenario (15 in total) is instantiated 3 times to build concrete scenarios. The case of perturbed considers the generated scenarios by perturbing (detailed in Sec. III-D) the concrete scenarios in the base. The problems on too-close and collision are regarded as safety-critical. The others are undesirable but regarded as performance issues. A scenario may contain both safety-critical and performance issues. From Table I, we observe that our local scenario perturbation technique, at least within the experiment, is effective in uncovering safety-critical scenarios. We observe that there are only two types of collision accidents between vehicles collected from the simulation results: rear collision and lateral collision. The reason is that the San Francisco map of offered by LGSVL only covers a part of the city. Roads within this part of the city does not have dashed yellow lines, and overtaking by borrowing the lane in the opposite direction is not allowed in Apollo. In such a case, head-to-head collisions cannot happen unless agents are educated to intentionally violate the traffic law.
Studying the root cause of undesired behaviors, we realize that Apollo may (1) fail to make trivial right turns, as it does not perform a lane change first, (2) fail to keep a safe distance, (3) have frequent interleaving of acceleration and deceleration, even when no external traffic signal exists, (4) violate the traffic rules such as running over red lights when there is still sufficient space to stop, and finally (5) run into trouble when inconsistencies exist between the map in the LGSVL simulator and the map internally stored in Apollo.

V. SUMMARY
ComOpT is our initial step towards a vision where testing autonomous driving systems can be systematically approached with scientific rigor. Within ComOpT, we designed and implemented a coverage-driven, two-layered approach that guarantees to maintain abstract scenario diversity while capable of performing local scenario perturbation.
ComOpT still has many potentials to be improved and matured, such as integrating the methods in the literature for generating scenarios, or designing other traffic agents beyond using the NPC agents made available by the simulators, or providing proper interfaces to other autonomous driving SW stacks such as Autoware.Auto [22].