A Dynamic Programming Approach to Collision Avoidance of Autonomous Ships

The advancement of autonomous capabilities in maritime navigation has gained significant attention, with a trajectory moving from decision support systems to full autonomy. This push towards autonomy has led to extensive research focusing on collision avoidance, a critical aspect of safe navigation. Among the various possible approaches, Dynamic Programming is a promising tool for optimizing collision avoidance maneuvers. This paper presents a DP formulation for collision avoidance of autonomous vessels. We set up the problem framework, formulate it as a multi-stage decision process, define cost functions and constraints focusing on the actual requirements a marine maneuver must comply with, and propose a solution algorithm leveraging parallel computing. Additionally, we present a greedy approximation to reduce algorithm complexity. Through case studies, we demonstrate the effectiveness of the proposed approach in navigating complex scenarios, contributing to the future of autonomous maritime navigation. Through case studies, we show the efficacy of our approach in navigating complex scenarios.