Complexity Analysis Using Graph Models for Conflict Resolution for Autonomous Ships in Complex Situations

Abstract Maritime autonomous surface ships (MASSs) will reshape the fast-evolving ecosystem for their attractive socio-economic benefits and potential to improve safety. However, their new systems and technology need thorough verifications to identify unintended components of risk. The interaction between MASS cyber-physical systems and the existing regulatory framework is currently unpredictable; artificial intelligence-powered intelligent situation awareness and autonomous navigation algorithms must safely and efficiently adhere to the regulations which are only designed for human interpretation without MASSs consideration. This paper contributes to algorithmic regulations and particularly algorithmic COLREGs in real-world MASS applications. It focuses on codifying COLREGs into a machine-executable system applicable to MASSs, then analyzing their performance in dynamic and mixed interactions between multiple vessels in complex scenarios. Based on fullest pairwise COLREGs criteria, this paper considers decision-making (DM) and complexity analysis in multi-collision-conflict scenarios. Complexity influential factors are an interplay between the characteristics of COLREGs, traffic scenarios, MASS interactions, and the environment. Participant vessels are the decision-makers forming a decentralized uncertain DM process, casted into a multi-participant multi-conflict multicriteria DM problem. This is tackled through the technique of graph models for conflict resolution, using risk graph models and fuzzy preferences over alternative collision-avoidance states. This paper conducts a comprehensive analysis of DM and navigational complexity; we develop novel complexity estimation scores, tools for complexity monitoring for human intervention, and spatial analysis of traffic complexity for geo-intelligent MASSs deployment and operation planning. The presented work is validated on a database of historical scenarios extracted from multiple data sources.