Proceedings of the Thirty-second (2022) International Ocean and Polar Engineering Conference
Shanghai, China, June 5–10, 2022
Copyright © 2022 by the International Society of Offshore and Polar Engineers (ISOPE)
ISBN 978-1-880653-81-4; ISSN 1098-6189

www.isope.org

Global Dynamic Path Planning Algorithm for USV Based on Improved Bidirectional RRT
Wenxuan Guo1, Guoyuan Tang1*, Fan Zhao1, Quanbin Wang2
1.School of Naval Architecture and Ocean Engineering, Huazhong University of Science & Technology, Wuhan, China
2.China Ship Development and Design Center, Wuhan, China

and optimize the initial solution, but in a dynamic environment, thealgorithm cannot cope with sudden obstacles and needs to be furtherimproved. Zhong (2019), combining the improved genetic algorithmwith the Morphin algorithm, enables the robot to effectively avoidobstacles in real time.

ABSTRACTPath planning is the key technique of autonomous navigation of
unmanned surface vehicle (USV). In this paper, an improved
bidirectional RRT global dynamic path planning algorithm for USV isproposed, which is combined with the Dijkstra algorithm and quadratic
Bezier curve to trim the path and improve smoothness. To avoid
emergent obstacles in the global path in real-time, the Morphin searchtree algorithm is introduced to dynamically plan the global path. The
simulation results show that this algorithm can improve theperformance and efficiency of path planning, and is more suitable forcomplex water surface environments.

Based on the above, A holistic approach is utilized, integrating
Improved Bidirectional RRT and Morphin algorithm to establish
Global Dynamic Path Planning Algorithm for USV Based on Improved
Bidirectional RRT in this paper. The algorithm mainly uses theimproved bidirectional RRT algorithm for global path planning. Whenthe USV encounters unexpected obstacles in the process of walking
along the global path, the Morphin algorithm is used to carry out thelocal path planning. The hybrid algorithm improves the searchefficiency by introduces the obstacle deviation, and target attraction tooptimize the expansion strategy of the bidirectional RRT algorithm.
And the Morphin search tree algorithm is used to dynamically plan theglobal path to avoid emergent obstacles in real-time. Combined withthe Dijkstra algorithm (Dijkstra, 1959) and the quadratic Bezier curve,
the obtained path is not only short in length but has good pathsmoothness, and the efficiency of path search is also improved.

KEY WORDS: Unmanned surface vehicle; Bidirectional RRT
algorithm; Morphin algorithm; Global Path Planning; Dynamicenvironment.
INTRODUCTION
In recent years, the application of unmanned surface vehicle in militaryand civil fields increases rapidly. At the same time, the development ofartificial intelligence technology predicts ship performance index moreconveniently (Yang, Tu, Song, Chen, Xie, and Sun, 2021). Aiming tocontrol the motion of the mobile robot in the ocean environment, thepath planning method has a pivotal role in USV research (Xu, 2019;Song, 2019). At present, the main algorithms of path planning include
artificial potential field generation, visual graph method, ant colonyalgorithm, particle swarm optimization algorithm, and artificial neuralalgorithm. Of particular concern is each method has its own advantages
and disadvantages.

ESTABLISHMENT OF ENVIRONMENTAL MODEL
Environmental modeling is abstract modeling of the actual environment
to obtain map pieces of information. Generally speaking, theestablishment of an environmental model is the basic condition torealize the path planning. Accurate and effective map environment
modeling is beneficial to the path search and affects the path planning
results. Therefore, map environment modeling is the primary task to besolved in the path planning of USV. At present, the common map
environment modeling methods mainly include visual graph method,link graph method, grid map method and so on．

Sampling-based algorithms have been used to solve complex
programming problems with high computational efficiency. LaValle(1998) proposes a classical sampling-based RRT algorithm, whichperforms uniform random sampling on the entire environment space,which has probabilistic completeness, but this algorithm only explores
the space through a random tree, which consumes a lot of time incomplex environments. Kuffner and LaValle (2002) point out the ideaof bidirectional search to generate two random trees simultaneously at
the starting point and the target point. Liu, Zhang, Wen, Wang, andChen (2019) proposed a GB-RRT algorithm that combines target bias
and curves smoothing to reduce search time, but the planned path has
many turning points and long path distances. Ryu and Park (2019)
proposed an improved Informed RRT* algorithm to effectively obtain

The grid graph method can construct a raster map. And raster map has
the characteristics of simple structure and accurate environment
description (Moravec and Elfes, 1985). Many mature path planningalgorithms can be used in raster maps for path search, such as theDijkstra algorithm, A* algorithm, genetic algorithm, ant colonyalgorithm, and so on. Accurate grid map modeling can ensure the speed
and accuracy of the planning process. In this paper, the grid method isused to model the working environment of USV. In a two-dimensional
environment in which a USV works, there are a limited number ofobstacles of different sizes, including static or dynamic obstacles. In3666