Rapid global path planning algorithm for unmanned surface vehicles in large-scale and multi-island marine environments

Dong Wang; Jie Zhang; Jiucai Jin; Deqing Liu; Xingpeng Mao

doi:10.7717/peerj-cs.612

Rapid global path planning algorithm for unmanned surface vehicles in large-scale and multi-island marine environments

PeerJ Comput Sci. 2021 Jun 29:7:e612. doi: 10.7717/peerj-cs.612. eCollection 2021.

Authors

Dong Wang^{1

2}, Jie Zhang^{1

2}, Jiucai Jin², Deqing Liu², Xingpeng Mao¹

Affiliations

¹ School of Electronics and Information Engineering, Harbin Institute of Technology, Harbin, Heilongjiang, China.
² First Institute of Oceanography, Ministry of Natural Resources, Qingdao, Shandong, China.

Abstract

A global path planning algorithm for unmanned surface vehicles (USVs) with short time requirements in large-scale and complex multi-island marine environments is proposed. The fast marching method-based path planning for USVs is performed on grid maps, resulting in a decrease in computer efficiency for larger maps. This can be mitigated by improving the algorithm process. In the proposed algorithm, path planning is performed twice in maps with different spatial resolution (SR) grids. The first path planning is performed in a low SR grid map to determine effective regions, and the second is executed in a high SR grid map to rapidly acquire the final high precision global path. In each path planning process, a modified inshore-distance-constraint fast marching square (IDC-FM²) method is applied. Based on this method, the path portions around an obstacle can be constrained within a region determined by two inshore-distance parameters. The path planning results show that the proposed algorithm can generate smooth and safe global paths wherein the portions that bypass obstacles can be flexibly modified. Compared with the path planning based on the IDC-FM² method applied to a single grid map, this algorithm can significantly improve the calculation efficiency while maintaining the precision of the planned path.

Keywords: Fast marching method; Fast marching square; Global path planning; Time optimal; Unmanned surface vehicle.

Grants and funding

This work was supported by the National Key R&D Program of China (No. 2017YFC14052**). The funders had no role in study design, data collection and analysis, decision to publish, or preparation of the manuscript.