Assessing Scene Generation Techniques for Testing COLREGS-Compliance of Autonomous Surface Vehicles

Question

Scenario-based testing is the standard way to assure automated cars at system level, and there is a mature toolbox for generating test scenes. Can the same techniques test whether an autonomous vessel follows the COLREGS when several ships meet? The maritime setting differs: other dynamics, open-sea geometry without lanes, more diverse actors, and rules that turn ambiguous with more than two vessels.

What we did

We focused on the hardest part of a maritime test scenario, the initial scene: where each vessel is, and how fast and in which direction it moves, at the moment they come within visibility range.

1. Formalised and extended a COLREGS model to multi-vessel encounters. The functional constraints are: exactly one own ship (the ASV); every own-ship/target-ship pair is in a COLREGS situation; target ships are not in a situation with each other.
2. Adapted two automotive scene-generation methods:
   • Search-based (SB): a multi-objective problem over position, heading, speed and length, solved with NSGA-II after hyper-parameter tuning. The objectives are the geometric distance from satisfying each constraint.
   • Rejection sampling (RS): sampling regions in the style of the Scenic framework (visibility region, velocity space, velocity-obstacle cone), intersected per target ship, with rejection for the constraints between target ships that cannot be expressed as regions.
3. Extracted real-world scenes from the CommonOcean benchmark (AIS data from Florida, the Middle East coast and the US west coast).
4. Abstracted every scene to its functional equivalence class (a graph shape) using the Refinery graph solver. This allowed us to measure relevance, diversity and completeness at the semantic level.

Results

• RQ1: Relevance. Synthetic approaches produced 68.1–94.6% relevant scenes. The real-world dataset had 0% relevant scenes for three or more vessels: of 3,298 extracted encounters, 3,222 involved two vessels, 72 three, 4 four, and none five or six.
• RQ2: Diversity and completeness. Coverage of equivalence classes dropped for both SB and RS as the vessel count increased.
• RQ3: Scalability and speed. SB found scenes within seconds up to six vessels. RS did not scale beyond three.

We also hit encounters that are clearly dangerous but fit no COLREGS situation, for example a fast small vessel and a slow large one both in the port-side sector with nothing on the starboard side. This is evidence of gaps in the rules themselves.

Why it matters

The paper shows that neither historical data nor off-the-shelf stochastic generation can deliver completeness guarantees for multi-vessel COLREGS testing. That negative result motivated the systematic, refinement-based approach in my MODELS 2026 paper.

Behind the paper

The first submission went through a major revision. Based on the reviews we reframed it as an experience report, which made the contribution clearer. I presented it in Trondheim at ISSTA 2025, co-located with FSE 2025. It received an ACM SIGSOFT Distinguished Paper Award.