Automated Generation of Functionally Complete Assurance Suites for COLREGS-Compliance of Autonomous Surface Vehicles

Problem

System-level tests for an autonomous vessel are run in realistic maritime simulators. The open question is which scenarios to run. Historical traffic and stochastic generators (search-based or sampling-based) both tend to miss rare, critical edge cases, so they cannot provide a semantic guarantee that every relevant type of encounter was tested. My ISSTA 2025 study showed this empirically.

Contributions

1. An approach and prototype that automatically derives functionally complete assurance suites for COLREGS compliance.
2. A constraint-satisfaction method based on enhanced rejection sampling for deriving relevant initial scenes.
3. An empirical evaluation of functional completeness, efficiency and scalability against direct stochastic concretisation.

How multi-step refinement (MSR) works

1. Enumerate. The Refinery graph solver lists every functional equivalence class (FEC) that conforms to the COLREGS metamodel for a given number of vessels. Each FEC is a graph shape: vessels as nodes, COLREGS situations as edges.
2. Map to a logical scenario. Each abstract relation becomes a set of numeric constraints. For a crossing from port situation, both vessels are at visibility distance (6 NM), on a collision course, the own ship is in the target ship's starboard sector, and the target ship is in the own ship's port sector.
3. Concretise. Find vessel positions, velocities and dimensions that satisfy the constraints. The enhanced rejection sampler intersects the regions implied by individual constraints, such as a speed disc and a velocity-obstacle cone that forces the courses to meet. It samples from that intersection with Scenic and rejects only the remaining violations.
4. Budget. A global timeout gives each FEC a practical average of four minutes, and unsolved classes are retried with whatever budget is left.

The baseline, direct concretisation, solves only the generic constraints (in visible range, on collision course) without FECs, using NSGA-II/III or plain rejection sampling under the same global timeout.

Results

• MSR reaches 100% scenario (FEC) coverage for 2 to 6 vessels, a range that covers the vast majority of open-sea encounters.
• MSR outperforms direct concretisation in FEC coverage over time. Coverage over time is the practically important metric because it tells you how long it takes to reach a given level of assurance.
• MSR with enhanced rejection sampling scales best among the configurations we compared.

Artifacts

The measurement data and the software artifact are archived on Zenodo, and the code lives on in SceneGEMS, which uses the same three-level pipeline (functional → logical → concrete).

At the conference

I presented the paper in a 15-minute talk at MODELS 2026 in Málaga. The same week I presented the SceneGEMS tool demo and my doctoral symposium paper.