Combinatorial-Testing-Based Multi-Ship Encounter Scenario Generation for Collision Avoidance Algorithm Evaluation

Collision avoidance algorithms play a crucial role in ensuring the safety and effectiveness of autonomous ships, which require comprehensive testing in realistic multi-ship encounter scenarios. However, existing scenario generation methods often inadequately represent the spatiotemporal complexity and dynamic risk interactions of real-world encounters, leading to biased evaluations. To bridge this gap, this paper proposes a combinatorial-testing-based scenario generation framework integrated with spatiotemporal complexity optimisation. First, a full-process scenario representation model is developed by abstracting real-world navigation features into a discretised parameter space. Subsequently, a combinatorial-testing-based scenario generation method is adopted to cover the parameter space, generating a high-coverage scenario set. Finally, spatiotemporal complexity is introduced to filter out oversimplified scenarios and extremely dangerous scenarios. Experiments demonstrated that 13.7% of generated scenarios were eliminated as unrealistic or trivial, while high-risk encounter scenarios and multi-ship interaction scenarios were amplified by 7.96 times and 5.84 times, respectively. Compared to conventional methods, the optimised scenario set exhibited superior alignment with real-world complexity, including dynamic risk escalation and multi-ship coordination challenges. The proposed framework not only advances scenario generation methodology through its integration of combinatorial testing and complexity-driven optimisation, but also provides a practical tool for rigorously validating autonomous ship safety systems.