This study proposes a decentralized many-to-many negotiation protocol for collaborative collision avoidance of Autonomous Surface Vehicles (ASVs). The protocol enables heterogeneous vehicles with different collision avoidance algorithms to negotiate in the same framework using asynchronous communication. To achieve fully decentralized decision-making, the problem is modeled as a Distributed Constraint Optimization Problem (DCOP) and solved using a Distributed Stochastic Search Algorithm (DSSA). Additionally, each vehicle adjusts its decision variables within the range of egocentric and altruistic behaviors using the Monotonic Concession Protocol and Fuzzy Logic. The proposed negotiation protocol is tested with two different reactive collision avoidance algorithms, considering some of the navigational rules (COLREG), and verified both with simulation and field experiments.

This study proposes a decentralized collision avoidance method for multiple ships and utilizes information exchange between vessels. The method is formulated with a hierarchical algorithm architecture and communicates with other ships using the route exchange concept to calculate collision-free trajectories. The hierarchical architecture consists of mid-level and reactive trajectory planners and considers navigational rules, e.g. the COLREG, and both static and dynamic obstacles. Dynamic obstacles represent the ships in the scenarios and the algorithm accounts for both cooperative and non-cooperative vessels. The mid-level planner is used for finding effective control actions by combining the A* algorithm with a proactive collision avoidance optimizer based on the MPC. The reactive planner uses the Informed SB-MPC algorithm and serves as a final barrier for finding solutions to problematic scenarios where the mid-level planner solutions are infeasible. The main motivations of the study include 1) to utilize ship-to-ship information exchange to convey intentions and to solve collision avoidance problems and 2) to prevent autonomous ships to initiate aggressive maneuvers in close-range encounters by calculating and applying proactive control actions in advance. The performance of the method is validated via simulations of 22 Imazu problem cases and a case scenario defined in the Trondheim Fjord. The results support that the algorithm can generate collision-free trajectories considering the COLREG rules 8, 13-18 and maintains a minimum safety distance. Finally, the hierarchical algorithm demonstrates computationally efficient run times to be used in real-time applications.