Model-Driven Scenario-Based Assurance for COLREGS Compliance

Why this problem

Autonomous surface vehicles are increasingly used for civilian and military missions, from oceanography to cargo transport. Before they can operate freely, someone has to show that they behave safely around other ships. The International Maritime Organization's MASS Code, in effect since 1 July 2026, explicitly asks for structured testing that includes detailed simulation and system-level tests. For collision avoidance the operational requirements are the COLREGS.

The COLREGS define who has the right of way when two vessels are in sight of one another and on a potential collision course. The basic situations are overtaking, crossing and head-on, and each assigns a role to each vessel: give-way or stand-on. Rule 8 then asks for a "safe distance" and "readily apparent" course changes (in practice more than 30°).

This is manageable for two ships. With three or more, one vessel can end up with contradicting roles, for example stand-on towards one ship and give-way towards another. These ambiguous scenarios are exactly where an autonomous controller is most likely to go wrong, and they are rare in real traffic. In the CommonOcean benchmark, 98% of the extracted encounters involve only two vessels.

The core idea: functional equivalence classes

We describe an encounter as a typed graph. Vessels are objects, COLREGS situations are edges (headOn, crossingFromPort, overtaking, …), and roles such as giveWay, standOn or ambiguous are inferred with graph patterns, following the COLREGS metamodel introduced by Kargén and Varró at MODELS ’24.

If you forget the identities of the vessels, the graph becomes a graph shape. Under a metamodel there are only finitely many shapes for a given number of vessels, and each shape is one semantically distinct edge case, which we call a functional equivalence class (FEC). An assurance suite that contains at least one scenario for every FEC is functionally complete. It gives a strong semantic guarantee that no type of encounter was skipped.

From abstract classes to simulation: multi-step refinement

The enhanced rejection sampler turns individual constraints into sampling regions, such as a speed disc and a velocity-obstacle cone that forces two courses to intersect. It samples directly from their intersection and rejects only the few samples that break the remaining constraints. This was the configuration that scaled best.

What we found so far

• Real-world data is not enough. Encounters extracted from AIS-based datasets are almost entirely two-vessel cases, and none of them were relevant multi-vessel COLREGS scenarios for three or more ships (ISSTA 2025).
• Automotive techniques do not transfer directly. Search-based and sampling-based scene generation, which work well for cars, are fast but lose diversity and completeness as the number of vessels grows (ISSTA 2025).
• Systematic refinement works. Multi-step refinement reaches 100% FEC coverage for 2–6 vessel encounters, which covers the vast majority of open-sea encounters, and it outperforms direct stochastic concretisation in coverage over time (MODELS 2026).
• The COLREGS have gaps. Some dangerous synthetic encounters cannot be classified under any COLREGS situation, which points to missing rules for multi-vessel cases.

Open directions

Covering each equivalence class once is not the end of the story. Two scenarios can look almost identical and still fall on different sides of a COLREGS boundary, so robustness (diverse coverage inside each class, especially near its boundaries) is the natural next question. Other directions are dynamic, reactive target-ship trajectories, richer vessel classes (sailing, restricted manoeuvrability), static obstacles, and execution at scale in higher-fidelity simulators.