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.
de VosJHekkenbergRGBandaOAV. The impact of autonomous ships on safety at sea–a statistical analysis. Reliab Eng Syst Safe, Vol. 210, 2021, p. 107558.
3.
International Maritime Organization. Outcome of the regulatory scoping exercise for the use of Maritime Autonomous Surface Ships (MASS). London: IMO, 2021.
International Maritime Organization (IMO). MSC.1/Circ.1638—outcome of the regulatory scoping exercise for the use of Maritime Autonomous Surface Ships (MASS), https://www.imo.org (2021, accessed: 31 October 2024).
6.
PoratheT.Maritime Autonomous Surface Ships (MASS) and the COLREGS: Do we need quantified rules or is “the ordinary practice of seamen” specific enough?TransNav2019; 13.
7.
ChangC-HWijeratneIBKontovasC, et al. COLREG and MASS: analytical review to identify research trends and gaps in the Development of Autonomous Collision Avoidance. Ocean Eng2024; 302: 117652.
8.
KimJ-KParkD-J.Understanding of sailing rule based on COLREGs: comparison of navigator survey and automated collision-avoidance algorithm. Mar Policy2024; 159: 105894.
9.
RutledalDRellingTResnesT.It’s not all about the COLREGs: a case-based risk study for autonomous coastal ferries. In: IOP conference series: materials science and engineering, Vol. 929. IOP Publishing, 2020, p.012016.
10.
VagaleAByeRTOucheikhR, et al. Path planning and collision avoidance for autonomous surface vehicles II: a comparative study of algorithms. J Mar Sci Technol2021; 26(4): 1307–1323.
11.
ZhuQXiYWengJ, et al. Intelligent ship collision avoidance in maritime field: A bibliometric and systematic review. Expert Syst Appl 204; 252: 124148.
12.
LyuHHaoZLiJ, et al. Ship autonomous collision-avoidance strategies—a comprehensive review. J Mar Sci Eng2023; 11(4): 830.
13.
AkdağMSolnørPJohansenTA.Collaborative collision avoidance for maritime autonomous surface ships: a review. Ocean Eng2022; 250: 110920.
14.
ChenLFuYChenP, et al. Survey on cooperative collision avoidance research for ships. IEEE Trans Transp Electrif2022; 9(2): 3012–3025.
PoratheTde VriesLPrisonJ. Ship voyage plan coordination in the MONALISA project: user tests of a prototype ship traffic management system. In: De WaardDBrookhuisKWiczorekR, et al. (eds.) Proceedings of the Human Factors and Ergonomics Society Europe Chapter 2013 Annual Conference. 2014, pp.1–11.
17.
PoratheTBorupOJeongJS, et al. Ship traffic management route exchange: acceptance in Korea and Sweden, a cross cultural study. In: Proceedings of the International Symposium Information on Ships, ISIS 2014. 2014, pp.64–79.
18.
ŠorovićMKapidaniNLukšićZ, et al. Towards the introduction of the sea traffic management system in the Adriatic Sea. In: 2023 12th Mediterranean Conference on Embedded Computing (MECO). IEEE, 2023, pp.1–6.
19.
NesheimDARødsethØBernsmedK, et al. Secure, trustworthy and efficient information exchange-enabling added value through the maritime data space and public key infrastructure. In: 20th International Conference on Computer and IT Applications in the Maritime Industries. 2021.
20.
SemnaniSHBasirOA.Target to sensor allocation: a hierarchical dynamic Distributed Constraint Optimization approach. Comput Commun2013; 36(9): 1024–1038.
21.
FiorettoFPontelliEYeohW.Distributed constraint optimization problems and applications: a survey. J Artif Intell Res2018; 61: 623–698.
22.
LiSNegenbornRRLodewijksG.Distributed constraint optimization for addressing vessel rotation planning problems. Eng Appl Artif Intell2016; 48: 159–172.
23.
KimD-GHirayamaKParkG-K.Collision avoidance in multiple-ship situations by distributed local search. J Adv Comput Intell Intell Inform2014; 18(5): 839–848.
24.
KimDHirayamaKOkimotoM.Ship collision avoidance by distributed tabu search. TransNav2015; 9(1).
KimD.A study on intention exchange-based ship collision avoidance by changing the safety domain. J Korean Soc Mar Environ Saf2019; 25(3): 259–268.
27.
AkdağMTranHALauvåsN, et al. A decentralized negotiation protocol for collaborative collision avoidance of autonomous surface vehicles. Authorea Preprints.
28.
LiSLiuJCaoX, et al. A novel method for solving collision avoidance problem in multiple ships encounter situations. In: Computational Logistics: 9th International Conference, ICCL 2018, Vietri sul Mare, Italy, October 1–3, 2018, Proceedings 9. Springer, 2018, pp. 47–66.
29.
LiSLiuJNegenbornRR.Distributed coordination for collision avoidance of multiple ships considering ship maneuverability. Ocean Eng2019; 181: 212–226.
30.
HirayamaKMiyakeKShiotaT, et al. DSSA+: Distributed collision avoidance algorithm in an environment where both course and speed changes are allowed. TransNav2019; 13(1): 117–123.
31.
LiuKDingSYanL, et al. COLREGs-compliant autonomous collision avoidance and improved adaptive LOS-based motion control for USVs in complex waters. Ocean Eng2025; 318: 120127.
32.
LiangZYangYHuangZ, et al. USV path planning algorithm based on 20D-A* and IDWA algorithms under COLREGs. Ocean Eng2025; 331: 121389.
33.
HanZWuDZhangJ, et al. COLREGs-adaptive trajectory planning and decision-making in maritime autonomous surface ships. Ocean Eng2024; 312: 119308.
34.
DanielisPBrekenfelderWParzyjeglaH, et al. Integrated autonomous underwater vehicle path planning and collision avoidance algorithms. Trans Marit Sci2024; 13(1).
35.
ZhangHCaoYShanQ, et al. Collision avoidance for maritime autonomous surface ships based on model predictive control using intention data and quaternion ship domain. J Mar Sci Eng2025; 13(1): 124.
36.
WangZChenPChenL, et al. Collaborative collision avoidance approach for USVs based on multi-agent deep reinforcement learning. IEEE Trans Intell Transp Syst2025; 26: 4780–4794.
37.
XiaoZLuXNingJ, et al. Colregs-compliant unmanned surface vehicles collision avoidance based on improved differential evolution algorithm. Expert Syst Appl2024; 237:121499.
38.
HaoSGuanWCuiZLuJ.USV collision avoidance decision-making based on the improved PPO algorithm in restricted waters. J Mar Sci Eng2024; 12(8): 1428.
39.
ChenXYinSLiY, et al. Dynamic path planning for multi-USV in complex ocean environments with limited perception via proximal policy optimization. Ocean Eng2025; 326: 120907.
40.
CuiZGuanWZhangX.A collision avoidance decision-making method for multiple marine autonomous surface ships based on P3DL-PPO algorithm. J Mar Sci Technol2025; 30: 205–223.
41.
XiaoZHouBNingJ, et al. Collision avoidance for unmanned surface vehicles in multi-ship encounters based on analytic hierarchy process–adaptive differential evolution algorithm. J Mar Sci Eng2024; 12(12): 2123.
42.
LeeH-JParkD-J.Collision evasive action timing for MASS using CNN–LSTM-based ship trajectory prediction in restricted area. Ocean Eng2024; 294: 116766.
43.
JeongMChaddaALiAQ. Active Learning-augmented Intention-aware Obstacle Avoidance of Autonomous Surface Vehicles in High-traffic Waters. In: 2024 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). IEEE, 2024, pp. 10005–10012.
44.
XuXCaoYCaiP, et al. Research on real-time collision avoidance and path planning of USVs in multi-obstacle ships environment. Ocean Eng2024; 295: 116890.
45.
YokooMHirayamaK.Algorithms for distributed constraint satisfaction: a review. Auton Agents Multi-Agent Syst2000; 3: 185–207.
46.
HirayamaKYokooM.An approach to over-constrained distributed constraint satisfaction problems: Distributed hierarchical constraint satisfaction. In: Proceedings Fourth International Conference on MultiAgent Systems. IEEE, 2000, pp. 135–142.
HoangKDYeohWYokooM, et al. New algorithms for continuous distributed constraint optimization problems. In: Proceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems. 2020, pp.502–510.
50.
ZhangXWangCJiangL, et al. Collision-avoidance navigation systems for Maritime Autonomous Surface Ships: a state of the art survey. Ocean Eng2021; 235: 109380.
51.
WangCWangNXieG, et al. Survey on collision-avoidance navigation of maritime autonomous surface ships. In: Offshore Robotics: Volume I Issue 1, 2021. Springer, 2022, pp. 1–33.
52.
TranHAJohansenTANegenbornRR. Collision avoidance of autonomous ships in inland waterways–A survey and open research problems. In: Journal of Physics: Conference Series, Vol. 2618. IOP Publishing, 2023, p.012004.
PertzovskyAZivanRAgmonN.Collision avoiding Max-Sum for mobile sensor teams. J Artif Intell Res2024; 79: 1281–1311.
55.
CerquidesJPicardGRodríguez-AguilarJA. Designing a marketplace for the trading and distribution of energy in the smart grid. International Foundation for Autonomous Agents and Multiagent Systems, 2015.
56.
FiorettoFYeohWPontelliE, et al. A distributed constraint optimization (DCOP) approach to the economic dispatch with demand response. In: Proceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems. 2017, pp. 999–1007.
57.
AgrawalPKumarAVarakanthamP.Near-optimal decentralized power supply restoration in smart grids IFAAMAS, 2015.
58.
MonteiroTLPujolleGPellenzME, et al. A multi-agent approach to optimal channel assignment in WLANs. In: 2012 IEEE Wireless Communications and Networking Conference (WCNC). IEEE, 2012, pp. 2637–2642.
59.
ChliMWinsperM.Using the Max-Sum algorithm for supply chain emergence in dynamic multiunit environments. IEEE Transactions on Systems, Man, and Cybernetics: Systems2015; 45(3): 422–435.
60.
AmigoniFCastellettiAFGiulianiM, et al. Modeling the management of water resources systems using multi-objective DCOPs. In: AAMAS’15 Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems. International Foundation for Autonomous Agents and Multiagent Systems, 2015, pp. 821–829.
61.
KinoshitaKIizukaKIizukaY.Effective disaster evacuation by solving the distributed constraint optimization problem. In: 2013 Second IIAI International Conference on Advanced Applied Informatics. IEEE, 2013, pp.399–400.
62.
RamchurnSDFarinelliAMacarthurKS, et al. Decentralized coordination in robocup rescue. Comput J2010; 53(9): 1447–1461.
63.
QuigleyWCRahoutiMWeissGM. A Secure blockchain-assisted framework for real-time maritime environmental compliance monitoring. arXiv preprint arXiv:2503.08707.
64.
AbabioIBBieniekJRahoutiM, et al. A blockchain-assisted federated learning framework for secure and self-optimizing digital twins in industrial IoT. Future Internet2025; 17(1): 13.
