A Visibility Graph approach for path planning and real-time collision avoidance on maritime unmanned systems

In high navigation traffic areas, path planning and collision avoidance is a crucial element of safe navigation, mostly in view of possible future applications in hybrid scenarios where both manned and Autonomous Surface Vehicles (ASV) share the environment.This paper deals with a novel procedure to generate optimal paths in presence of static and moving obstacles. The proposed path planning approach deals with an optimization problem based on the so-called Essential Visibility Graph (EVG) [1], an extension of the standard Visibility Graph (VG) [2], in order to find the minimum cost piecewise linear path between two points in a scenario with several obstacles. Such approach can be used also in presence of multiple ASV or movable obstacles, by using a re-planning procedure to update the EVG over a selected prediction time interval. To make the solution compliant with the current regulation and make ASV behaviour predictable by human pilots on manned vehicles, EVG was extended by implementing a cut procedure based on Collision Regulations (COLREGS) [3]. Finally, the use of Dubins curves provides smooth paths, compliant with physics constraints such as the minimum turn radius.A campaign of numerical simulations was carried out to test the effectiveness of the proposed technique in different operational scenarios. Results show that the algorithm is always able to identify COLREGS-compliant trajectories, in order to avoid collisions and assure minimum safety distance as well. Furthermore, the low computational burden suggests that the proposed procedure can be considered a promising approach for real-time applications.