Long-voyage route planning method based on multi-scale Visibility Graph for autonomous ships

Wu, Gongxing and Incecik, Atilla and Tezdogan, Tahsin and Terziev, Momchil and Wang, LingChao (2021) Long-voyage route planning method based on multi-scale Visibility Graph for autonomous ships. Ocean Engineering, 219. 108242. ISSN 0029-8018

[thumbnail of Wu-etal-OE-2021-Long-voyage-route-planning-method-based-on-multi-scale-Visibility-Graph-for-autonomous-ships] Text (Wu-etal-OE-2021-Long-voyage-route-planning-method-based-on-multi-scale-Visibility-Graph-for-autonomous-ships)
Accepted Author Manuscript
Restricted to Repository staff only until 27 November 2021.
License: Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 logo

Download (1MB) | Request a copy from the Strathclyde author


    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.

    ORCID iDs

    Wu, Gongxing, Incecik, Atilla, Tezdogan, Tahsin ORCID logoORCID: https://orcid.org/0000-0002-7032-3038, Terziev, Momchil ORCID logoORCID: https://orcid.org/0000-0002-1664-6186 and Wang, LingChao;