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

Gongxing Wu, Atilla Incecik, Tahsin Tezdogan, Momchil Terziev, LingChao Wang

Research output: Contribution to journalArticlepeer-review

42 Citations (Scopus)
89 Downloads (Pure)


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.
Original languageEnglish
Article number108242
Number of pages15
JournalOcean Engineering
Early online date27 Nov 2020
Publication statusPublished - 1 Jan 2021


  • ship route planning
  • multi-scale map
  • visibility graph
  • autonomous ship


Dive into the research topics of 'Long-voyage route planning method based on multi-scale Visibility Graph for autonomous ships'. Together they form a unique fingerprint.

Cite this