Code for the paper "Automatic Generation of Test-cases of Increasing Complexity for Autonomous Vehicles at Intersections", Abolfazl Karimi and Parasara Sridhar Duggirala, ACM/IEEE International Conference on Cyber-Physical Systems (ICCPS), 2022.
"This test case is harder than that one" is usually an appeal to intuition: more vehicles, worse weather, faded lane markings. That makes complexity subjective and hard to search over.
This paper defines it objectively instead. A test case is a scenario in which the behavior of the ego vehicle is left unspecified, together with pass-fail criteria. Its complexity is characterized by its set of solutions — the set of ego behaviors that would pass it — and two test cases are compared by the subset relation on those sets. A test case is strictly more complex than another when the behaviors that pass it are a strict subset. The definition depends only on the pass-fail criteria, never on a judgment about which features look challenging.
That definition makes the generation problem tractable: given a test case, producing a more complex one becomes a constraint-satisfaction search. The search variables are the changes to the existing test case, and the constraints define what counts as a solution — steering geometry of the cars, lane geometry, car shapes, traffic rules, bounds on longitudinal acceleration, and so on.
The constraints do not all belong to one solver, so they are split into three categories and discharged by three different tools:
| Constraint category | Solved with |
|---|---|
| Physical realism, vehicle dynamics, road geometry | simulation |
| Traffic rules and right-of-way, which are non-monotonic and relational | answer set programming (clingo) |
| Timing and acceleration constraints over continuous trajectories | SMT solving (Z3, via PySMT) |
Splitting the problem this way is what makes it computationally feasible. The output is a new test case whose trajectories are provably consistent with the specification rather than merely plausible.
Implemented on top of the Scenic libraries and the CARLA simulator, generating test cases for several 3-way and 4-way intersections with different topologies. In the experiments, both CARLA's autopilot and autopilot-plus-RSS (Responsibility-Sensitive Safety) fail as generated complexity increases.
src/complexgen/
core/ test-case representation and the complexity search
predicates/ traffic-rule and right-of-way predicates for the ASP encoding
simulators/ CARLA and Scenic backends
scripts/ command-line entry points
tests/
examples/ worked intersections:
leftTurnFrom3wayY
leftTurnFrom4wayStop
leftTurnFromContinuingHighway
logic_program.txt the answer-set program for the rule constraints
Docker/ container definition; docker_container.sh to run it
Dependencies are in requirements.txt; docker_container.sh builds and runs the
container. The entry points live in src/complexgen/scripts/, each with -h:
| Script | What it does |
|---|---|
new.py |
create a new test-case scenario |
extend.py |
extend an existing test case into a more complex one |
replay.py |
replay an existing scenario |
autopilot.py |
replay a scenario with CARLA's autopilot driving the ego vehicle |
Note that these moved into src/complexgen/scripts/ in an earlier reorganization; older
notes referring to ./new.py at the repository root are out of date.
Tested against CARLA 0.9.14 and Scenic 3, with current Z3 and PySMT.
@inproceedings{Karimi.2022,
title={Automatic Generation of Test-cases of Increasing Complexity for Autonomous
Vehicles at Intersections},
author={Karimi, Abolfazl and Duggirala, Parasara Sridhar},
booktitle={2022 ACM/IEEE 13th International Conference on Cyber-Physical Systems (ICCPS)},
year={2022},
organization={IEEE}
}- ScenarioGeneration — replacing code coverage with requirement-derived predicate coverage to drive a fuzzer (ICCPS 2026).
- FormalizedTrafficRules — the traffic-rule monitor and its formalization (ICCPS 2020).