Fast grid based collision avoidance for vessels using A∗ search algorithm

Abstract

In this work a real-time grid based collision avoidance algorithm for vessels in maritime environments is presented. Most grid based collision avoidance approaches use Lee's algorithm to find an optimal collision-free path. The drawback of this algorithm is the long runtime for large grids. To reduce this runtime, in this work the A* search is used instead of Lee's algorithm. The algorithm additionally regards the physical constrains of the vessel and pays attention to the COLREGs. The runtime and the resulting path of Lee's algorithm and the A* search are compared in computational experiments. Furthermore, the performance of the collision avoidance on a real vessel on the Lake Constance is presented.