Path Planning in Coastal Navigation for Maritime Autonomous Surface Ships using the D* Algorithm

Abstract

Establishing the passage plan of a ship is an essential step before the ship starts to sail. Research related to the automatic generation of ship passage plans is garnering attention because of the development of maritime autonomous surface ships. The ocean, islands, and navigation rules should be considered in coastal navigation. Therefore, from the perspective of the path-planning algorithm, the passage planning of a ship is a global pathplanning problem. Because traditional global path-planning methods, such as Dijkstra and A*, are timeconsuming owing to processes such as environmental modeling, changing the passage plan of a ship during voyage is difficult. Therefore, the D* algorithm was used to address these problems. The start point was near Busan New Port, and the destination was Ulsan Port. The navigable area was designated based on the result of combining the ship trajectory data and grid in the target area. The initial path plan generated using the D* algorithm was analyzed with 33 waypoints and a total distance of 113.946 km. The final path plan, which was simplified using the Douglas–Peucker algorithm, was analyzed with a total distance of 110.156 km and 10 waypoints. This is approximately 3.05% less than the total distance of the initial passage plan of the ship. This study shows the possibility of automatically generating a path plan in coastal navigation for maritime autonomous surface ships using the D* algorithm. Using the shortest distance–based path planning algorithm, the fuel consumption and sailing time of the ship can be minimized.