Distributed Constraint Optimization Problems for autonomous maritime collaborative collision avoidance: A review and evaluation

Maritime transportation, responsible for a significant portion of global trade, is experiencing a shift towards automation and digital transformation. With the advancement of Autonomous Surface Vessels (ASVs) and Maritime Autonomous Surface Ships (MASS), there is a growing need for sophisticated navigation systems that can ensure safety and prevent collisions in increasingly congested waterways. This paper comprehensively reviews Distributed Constraint Optimization Problems (DCOPs) as a framework for collaborative collision avoidance among autonomous vessels. DCOPs enable decentralized decision-making, allowing vessels to optimize their trajectories collaboratively without reliance on centralized systems. We explore key DCOP algorithms such as Distributed Stochastic Search Algorithm (DSSA), Dynamic Programming Optimization Protocol (DPOP), SynchBB, and Max-Sum, examining their strengths, limitations, and applicability to multi-ship collision avoidance. Furthermore, we conduct simulations to evaluate these algorithms’ effectiveness, comparing their computational efficiency and communication costs. Our findings underscore the potential of DCOP-based approaches in enhancing navigational safety and operational efficiency for MASS. The paper concludes with a discussion of open challenges and future research directions.