Article
Path Planning and Collision Avoidance in Unknown
Environments for USVs Based on an Improved D* Lite
Xiaohui Zhu
1
, Bin Yan
2
and Yong Yue
1,
*
Citation: Zhu, X.; Yan, B.; Yue, Y.
Path Planning and Collision
Avoidance in Unknown
Environments for USVs Based on an
Improved D* Lite. Appl. Sci. 2021, 11,
7863. https://doi.org/10.3390/
app11177863
Academic Editor: Giovanni Boschetti
Received: 29 July 2021
Accepted: 25 August 2021
Published: 26 August 2021
Publisher’s Note: MDPI stays neutral
with regard to jurisdictional claims in
published maps and institutional affil-
iations.
Copyright: © 2021 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/).
1
Department of Computing, Xi’an Jiaotong-Liverpool University, Suzhou 215123, China;
xiaohui.zhu@xjtlu.edu.cn
2
Jiangnan Rural Commercial Bank, Jintan District, Changzhou 213200, China; bin_bryant0316@163.com
* Correspondence: yong.yue@xjtlu.edu.cn
Abstract:
Path planning and collision avoidance during autonomous navigation in unknown environ-
ments is a crucial issue for unmanned surface vehicles (USVs). This paper improves the traditional D*
Lite algorithm and achieves multi-goal path planning and collision avoidance for USVs in unknown
and complex environments. By expanding the adjacent search range and setting a safe distance
for USVs, we solve the issue of limited steering maneuverability in USVs with fewer DOF during
autonomous navigation. We propose an approach to optimize the planned path during navigation
by comparing the estimated distance with the actual distance between the current waypoint and
the goal waypoint. A minimum binary heap is used to optimize the priority queue of the D* Lite
and significantly reduce the path search time. Simulation results show that the improved D * Lite
can significantly reduce the path planning time, optimize the planned path and solve the issue of
limited steering maneuverability in USVs. We apply the algorithm to a real USV for further tests.
Experimental results show that the USV can plan an optimized path while avoiding both static and
dynamic obstacles in complex environments with a safe distance during autonomous navigation.
Keywords:
path planning; improved D* Lite; unmanned surface vehicle; safe distance; autonomous
navigation; obstacle avoidance; minimum binary heap
1. Introduction
Due to the gradual deterioration in water quality [
1
], water quality monitoring is crucial
for the protection of river systems. Unmanned surface vehicles (USVs) are widely used
for water quality monitoring because of their advantages of low cost, high mobility and
suitability for conducting dangerous tasks [
2
]. Path planning is a critical issue for autonomous
navigation and collision avoidance in USVs. However, compared to other robots, such as
UAVs, and due to the limited steering maneuverability and the fewer degrees of freedom
(DOF) of USVs and the interference caused by wind and water flow, path planning is a more
critical issue for autonomous navigation and collision avoidance in USVs.
Scholars have carried out much research on path planning [
3
–
5
]. The graph search
algorithm of Dijkstra [
6
] is a classic path planning algorithm based on the breadth-first
search strategy. However, the path search efficiency of the Dijkstra algorithm is very low
due to its global path search strategy. The RRT* algorithm based on node sampling has
been used to provide asymptotically optimal, computationally tractable and feasible paths
in continuous radioactive space, and it gives a better navigation path than the Dijkstra
algorithm [
7
]. However, the convergence rate of RRT* is slow. Hart and Nilsson proposed
the A* algorithm [
8
]. It uses a heuristic function to estimate the path length from any node
to the goal node. As a result, A* searches less space and is thus more efficient. It has been
widely used in path planning and optimization [
9
]. However, it has to completely replan
the path when the environment is changed, which makes it very inefficient in dynamic
environments [10].
Appl. Sci. 2021, 11, 7863. https://doi.org/10.3390/app11177863 https://www.mdpi.com/journal/applsci
