Long-voyage route planning method based on multi-scale visibility graph for autonomous ships
Published in Ocean Engineering, 2021
Recommended citation: Wu, G., Atilla, I., Tahsin, T., Terziev, M. and Wang, L., 2021. Long-voyage route planning method based on multi-scale visibility graph for autonomous ships. Ocean Engineering, 219, p.108242. https://doi.org/10.1016/j.oceaneng.2021.108583
Abstract
With the increasing demand for the autonomous ship, a fast planning method for long-distance ship routes is needed. In this paper, a multi-scale Visibility Graph (VG) method is proposed for long-voyage route planning, as a solution to the problems of the slow planning and poor route accuracy. First, polygon data of obstacles are extracted from an electronic chart. In order to reduce the number of Visibility Points (VPs), the VPs are expanded from the convex points of these polygons. The small-scale, medium-scale, and large-scale VG models are established respectively. Second, this paper proposes the Local Planning Window (LPW) method, which greatly reduces the complexity of the VG models. The great circle route method is used to decompose the longer route, which further shorten the search time of the VG. The route planning process is designed for the multi-scale VG method. Finally, a long-voyage route planning example is carried out, in which, the utilization rate of the number of obstacle polygons and the number of VPs are analyzed. The data results show that: the complexity of VG models can be reduced greatly, and the search time of the VG will be shortened, by using the multi-scale VG method.
Highlights
- In order to reduce the number of Visibility Points, this paper proposes to use only the convex points of the obstacle polygon to build the Visibility Graph model. So the number of Visibility Points can be reduced nearly a half, and it will reduce the search time of Visibility Graph.
- The proposed Moving Planning Window method is that only those Visibility Points near the route are selected for the Visibility Graph, which will reduce a large number of Visibility Points, thereby saving planning time.
- Then a new multi-scale Visibility Graph method is proposed for long-voyage route planning. This approach can be a solution to the problems of the slow planning and poor route accuracy.