Beam Search Algorithm for Ship Anti-Collision Trajectory Planning

The biggest challenges in the maritime environment are accidents and excessive fuel consumption. In order to improve the safety of navigation at sea and to reduce fuel consumption, the strategy of anti-collision, shortest trajectory planning is proposed. The strategy described in this paper is based on the beam search method. The beam search algorithm (BSA) takes into account many safe trajectories for the present ship and chooses the best in terms of length and other criteria. The risk of collision of present ship with any target ships is detected when the closest point of approach (CPA) of the present ship is violated by the target ship's planned trajectory. Only course alteration of the present ship is applied, and not speed alteration. The algorithm has been implemented in the decision support system NAVDEC and tested in a real navigation environment on the m/f Wolin, a Polish ferry. Almost all BSA trajectories calculated were shorter in comparison to the standard NAVDEC-calculated algorithm.