Citation: Yu, J.; Liu, G.; Xu, J.; Zhao,
Z.; Chen, Z.; Yang, M.; Wang, X.; Bai,
Y. A Hybrid Multi-Target Path
Planning Algorithm for Unmanned
Cruise Ship in an Unknown Obstacle
Environment. Sensors 2022, 22, 2429.
https://doi.org/10.3390/s22072429
Academic Editors: Xiaochun Cheng
and Daming Shi
Received: 5 February 2022
Accepted: 17 March 2022
Published: 22 March 2022
Publisher’s Note: MDPI stays neutral
with regard to jurisdictional claims in
published maps and institutional affil-
iations.
Copyright: © 2022 by the authors.
Licensee MDPI, Basel, Switzerland.
This article is an open access article
distributed under the terms and
conditions of the Creative Commons
Attribution (CC BY) license (https://
creativecommons.org/licenses/by/
4.0/).
Article
A Hybrid Multi-Target Path Planning Algorithm for Unmanned
Cruise Ship in an Unknown Obstacle Environment
Jiabin Yu
1,2,3
, Guandong Liu
1,2,3
, Jiping Xu
1,2,3,
*, Zhiyao Zhao
1,2,3
, Zhihao Chen
1,2,3
, Meng Yang
1,2,3
,
Xiaoyi Wang
1,2,3
and Yuting Bai
1,2,3
1
School of Artificial Intelligence, Beijing Technology and Business University, Beijing 100048, China;
yujiabin@th.btbu.edu.cn (J.Y.); 1804010402@st.btbu.edu.cn (G.L.); zhaozy@btbu.edu.cn (Z.Z.);
2130062048@st.btbu.edu.cn (Z.C.); 2030602069@st.btbu.edu.cn (M.Y.); wangxy@btbu.edu.cn (X.W.);
baiyuting@btbu.edu.cn (Y.B.)
2
Beijing Laboratory for Intelligent Environmental Protection, Beijing Technology and Business University,
Beijing 100048, China
3
State Environmental Protection Key Laboratory of Food Chain Pollution Control,
Beijing Technology and Business University, Beijing 100048, China
* Correspondence: xujp@th.btbu.edu.cn
Abstract:
To solve the problem of traversal multi-target path planning for an unmanned cruise
ship in an unknown obstacle environment of lakes, this study proposed a hybrid multi-target path
planning algorithm. The proposed algorithm can be divided into two parts. First, the multi-target
path planning problem was transformed into a traveling salesman problem, and an improved
Grey Wolf Optimization (GWO) algorithm was used to calculate the multi-target cruise sequence.
The improved GWO algorithm optimized the convergence factor by introducing the Beta function,
which can improve the convergence speed of the traditional GWO algorithm. Second, based on
the planned target sequence, an improved D* Lite algorithm was used to implement the path
planning between every two target points in an unknown obstacle environment. The heuristic
function in the D* Lite algorithm was improved to reduce the number of expanded nodes, so the
search speed was improved, and the planning path was smoothed. The proposed algorithm was
verified by experiments and compared with the other four algorithms in both ordinary and complex
environments. The experimental results demonstrated the strong applicability and high effectiveness
of the proposed method.
Keywords:
unknown obstacle environment; improved D* Lite algorithm; improved grey wolf
optimization algorithm; unmanned cruise ship multi-target path planning
1. Introduction
In recent years, Unmanned Cruise Ships (UCSs) for water quality sampling have been
widely used in the field of water environment protection. Generally, a UCS needs to traverse
multiple target points for water sampling, but there are many unknown obstacles that can
move freely and dynamically change with the environment in the actual river or lake, so
the UCS is required to plan an optimization path traversing multiple sample points in a
short time and effectively avoid unknown obstacles to cruise safely. Therefore, multi-target
path planning of a UCS in an unknown obstacle environment is of great importance [1].
Since the 1970s, many studies on the path planning problem have been conducted. The
path planning methods can be roughly divided into several groups: the grid search meth-
ods, such as A* algorithm [
2
], Depth-First Search (DFS) [
3
], Breadth-first Search (BFS) [
4
],
and Dijkstra algorithm [
5
]; the sampling-based methods, such as Probabilistic Roadmap
(PRM) [
6
] and Rapidly Exploring Random Tree (RRT) [
7
]; heuristic or swarm intelligence
algorithms, such as Genetic Algorithm (GA) [
8
], Ant Colony Optimization (ACO) [
9
],
Particle Swarm Optimization (PSO) [
10
], and neural network-based algorithms [
11
]; the
Sensors 2022, 22, 2429. https://doi.org/10.3390/s22072429 https://www.mdpi.com/journal/sensors
