Path planning for ship sailing: an overview

Ship routing algorithm has long been a common interest for the development of autonomous ship and intelligent ship operations. With the increase demand in transportation worldwide, no matter for long distance voyage or inland waterway shipping, it could always assist in avoid encountering extreme sailing condition, reducing fuel consumption, guarantee the sailing safety while considering accurate estimated time of arrival (ETA), etc.

Various voyage optimization methods were proposed and implemented in the market, to search for a ship’s potential sailing area and to plan optimal ship routing with multiple objectives. For inland waterborne traffic, it is a complex system in which many factors play important roles, such as waterway topography and high traffic density. For inland ship sailing, it is essential to investigate ship path planning and navigation risk to increase the safety and capacity of traffic. [1] In fact, routing algorithm for transport vessels has been widely investigated throughout the years. There are many well-established methodologies in the current maritime transportation community, such as sampling-based algorithms, graph-based planning method and more recently, artificial intelligence and machine learning algorithms.

The graph-based planning method is a common type of method based on an implicit traversal model, such as Dijkstra algorithm, A* algorithm and their more advanced variants. Other traditional applications could be found in sampling-based algorithms, like Probabilistic Roadmap Method (PRM) algorithms, Rapidly Random Tree (RRT) algorithms and methods developed based on them. These traditional algorithms could generally give an acceptable performance and good efficiency in computation, but they usually are only capable in providing low-resolution routes and are prone to local optima. Furthermore, for advanced trajectory planning, the sailing speed is an important factor to be included, but it instead could be hard for these traditional algorithms to deal with.

To better adapt complicated environmental and continuous changes in inland waterborne traffic, artificial intelligent methods therefore are applied widely. They with no doubt will possess greater capabilities in handling complex problems and achieve speed assignment in trajectory planning, however, a common drawback would be lack of computation efficiency for fast decision-making onboard ships, which is often a tricky problem for advanced optimization methods to be taken care of. There is always a trade-off between computation efficiency in practical operation and the effectiveness of optimization algorithms. Besides, they require certain amount of training data that usually are precious resources to share and obtain.

Figure 1: Global and local path planning for autonomous navigation [3].

For a typical route planning problem, the situational awareness module is the base that all the planning method is built on. After the identification and perception of environment, data will be transferred to support and assist the decision-making of the planning algorithm. This could be done both before and during the sailing, running in parallel to give a real-time update and correction for the operation. Besides the external environment, from a practical aspect, the maneuverability of autonomous vessels is also a significant factor to be considered as constraints, avoiding giving any reference path that unrealistic for the vessel to follow, especially from the speed following aspect.

An article by Yuhan Chen

References
[1] Gan L, Yan Z, Zhang L, et al. Ship path planning based on safety potential field in inland rivers[J]. Ocean Engineering, 2022, 260: 111928.
[2] Cao S, Fan P, Yan T, et al. Inland waterway ship path planning based on improved RRT algorithm[J]. Journal of Marine Science and Engineering, 2022, 10(10): 1460.
[3] Lu Y, Xue Z, Xia G S, et al. A survey on vision-based UAV navigation[J]. Geo-spatial information science, 2018, 21(1): 21-32.