Multi-extensibility and flexibility of unmanned surface vehicles (USVs) allow them perform many different tasks, further path planning technology is crucial to the safety, autonomy, and intelligent navigation of USVs. Firstly, this paper analyzes the impact of ocean currents and risk constraints on USV based on the electronic chart. Then take the optimal sailing time as the objective function and design a path planning algorithm based on an improved probabilistic roadmap (PRM) algorithm, in which a Gaussian space sampling algorithm based on edge detection is introduced. After building the network topology environment through improved PRM, then a Dijkstra algorithm based on great circle distance is used to solve the optimal path. Finally, the simulation experiment is designed through the MATLAB platform. By comparing the average and the three quartile lengths of the planned paths under three environments, the values of the designed Edge-Gaussion (E-G) PRM algorithm are smaller than Lazy PRM and Gaussian PRM algorithm, which shows that the improved PRM algorithm has better performance. When planning the USV path under the influence of current, compared with traditional length optimal path planning, although the navigation length planned by the designed algorithm is shorter by 972 m, sailing time is improved by 110 s, which efficiency shows the better application on the sea.
Manley JE. Unmanned surface vehicles, 15 years of development. In: OCEANS 2008, 2008, pp.1–4. New York, NY: IEEE.
2.
ZhuangJWangLLiaoY, et al. Global path planning of unmanned surface vehicle based on electronic chart. SRX Comput Sci2011; 38(9): 211–214.
3.
LyuHYinY.Path planning of autonomous ship based on electronic chart vector data modeling. J Transp Inf Saf2019; 37(5): 94–106.
4.
FanYZhaoYShiL, et al. Global path planning for unmanned surface vehicle based on grid model of electronic chart. Navig China2017; 40(1): 47–52.
5.
TsouMC.Multi-target collision avoidance route planning under an ECDIS framework. Ocean Eng2016; 121: 268–278.
6.
ChenCTangJ.Path planning and design of surface unmanned vehicle based on viewable method. Shipbuild China2013; 54(1): 129–135.
7.
TakahashiOSchillingRJ.Motion planning in a plane using generalized voronoi diagrams. IEEE Trans Robot Autom1989; 5(2): 143–150.
8.
NiuHLuYSavvarisA, et al. Efficient path planning algorithms for unmanned surface vehicle. IFAC-PapersOnLine2016; 49(23): 121–126.
9.
LuXLiYHeH.A walking planning method for virtual humans based on the C-space method. Comput Sci Eng2005; 27(8): 60–61.
10.
SánchezMiralles ÁSanz BobiMÁ. Global path planning in gaussian probabilistic maps. J Intell Robot Syst2004; 40(1): 89–102.
11.
ZhangZWuDGuJ, et al. A path-planning strategy for unmanned surface vehicles based on an adaptive hybrid dynamic stepsize and target attractive force-rrt algorithm. J Mar Sci Eng2019; 7(5): 132.
12.
NohGParkJHanD, et al. Selective goal aiming rapidly exploring random tree path planning for UAVs. Int J Aeronaut Space Sci2021; 22: 1397–1412.
13.
AriaM; Departemen Teknik Elektro, Universitas Komputer Indonesia, Indonesia. Optimal path planning using informed Probabilistic Road Map algorithm. J Eng Res2021; 1–15.
14.
ChenGLuoNLiuD, et al. Path planning for manipulators based on an improved probabilistic roadmap method. Robot Comput Integr Manuf2021; 72: 102196.
15.
JangKBaekJParkS, et al. Motion planning for closed-chain constraints based on probabilistic roadmap with improved connectivity. IEEE/ASME Trans Mechatron2022; 27(4): 2035–2043.
16.
YamaneYKobayashiK.A new fast weighted all-pairs shortest path search algorithm based on pruning by Shortest Path Trees. arXiv preprint arXiv: 1908.06798, 2019.
17.
DudejaCKumarP.An improved weighted sum-fuzzy Dijkstra’s algorithm for shortest path problem (iWSFDA). Soft Comput2022; 26: 3217–3226.
18.
ErgunSGokSAydoganT, et al. Performance analysis of a cooperative flow game algorithm in ad hoc networks and a comparison to Dijkstra’s algorithm. J Ind Manag Optim2019; 15(3): 1085–1100.
19.
ChenGWuTZhouZ.Research on ship meteorological route based on A-star algorithm. Math Probl Eng2021; 2021: 1–8.
20.
GuSZhouCWenY, et al. A motion planning method for unmanned surface vehicle in restricted waters. Proc IMechE, Part M: J Engineering for the Maritime Environment2020; 234(2): 332–345.
21.
HanXZhangX.Multi-scale theta* algorithm for the path planning of unmanned surface vehicle. Proc IMechE, Part M: J Engineering for the Maritime Environment2022; 236(2): 427–435.
22.
SulaimanSSudheerAP.Modeling of a wheeled humanoid robot and hybrid algorithm-based path planning of wheel base for the dynamic obstacles avoidance. Ind Rob2022; 49(6): 1058–1076.
23.
LyuDChenZCaiZ, et al. Robot path planning by leveraging the graph-encoded Floyd algorithm. Future Gener Comput Syst2021; 122(7): 204–208.
24.
ChenZMaoYSongL, et al. Path planning algorithm for unmanned vehicle based on evolutionary potential field model. J Wuhan Univ Technol2019; 43(1): 113–117.
25.
HollandJH.Genetic algorithms and the optimal allocation of trials. SIAM J Comput1973; 2(2): 88–105.
26.
LiKHuQLiuJ.Path planning of mobile robot based on improved multiobjective genetic algorithm. Wirel Commun Mob Comput2021; 2021: 1–12.
27.
FengHLiuMXuH.Multi-target path planning for unmanned surface vessel based on adaptive hybrid particle swarm optimization. J Huazhong Univ Sci Technol2018; 46(6): 59–64.
MaYNGongYJXiaoCF, et al. Path planning for autonomous underwater vehicles: an ant colony algorithm incorporating alarm pheromone. IEEE Trans Vehicular Technol2019; 68: 141–154.
30.
CheGLiuLYuZ.An improved ant colony optimization algorithm based on particle swarm optimization algorithm for path planning of autonomous underwater vehicle. J Ambient Intell Humaniz Comput2020; 11(8): 3349–3354.
31.
PatleBKBabuL GPandeyA, et al. A review: on path planning strategies for navigation of mobile robot. Def Technol2019; 15(4): 582–606.
32.
LowESOngPCheahKC.Solving the optimal path planning of a mobile robot using improved Q-learning. Robot Auton Syst2019; 115: 143–161.
33.
SunFWangXZhangR.Improved Q-learning algorithm based on approximate state matching in agricultural plant protection environment. Entropy2021; 23(6): 737. DOI: 10.3390/e23060737
34.
GuoSZhangXDuY, et al. Path planning of coastal ships based on optimized dqn reward function. J Mar Sci Eng2021; 9(2): 210.
35.
YangYJuntaoLLinglingP.Multi-robot path planning based on a deep reinforcement learning DQN algorithm. CAAI Trans Intell Technol2020; 5(3): 177–183.
36.
ZhuZHuCZhuC, et al. An improved dueling deep double-q network based on prioritized experience replay for path planning of unmanned surface vehicles. J Mar Sci Eng2021; 9: 1267.
37.
YangXShiYLiuW, et al. Global path planning algorithm based on double DQN for multi-tasks amphibious unmanned surface vehicle. Ocean Eng2021; 266: 112809.
38.
PenickaRFaiglJSaskaM.Physical orienteering problem for unmanned aerial vehicle data collection planning in environments with obstacles. IEEE Robot Autom Lett2019; 4: 3005–3012.
39.
GangCNingLDanL, et al. Path planning for manipulators based on an improved probabilistic roadmap method. Robot Comput Integr Manuf2021; 72: 1–17.
40.
DijkstraEW.A note on two problems in connexion with graphs. Numer Math2021; 1: 269–271.
41.
BohlinRKavrakiLE.Path planning using lazy PRM. In: IEEE international on robotics and automation, 2000, pp.521–528. New York, NY: IEEE.
42.
BoorVOvermarsMHStappenA. The gaussian sampling strategy for Probabilistic Roadmap planners. In: Proceedings 1999 IEEE international conference on robotics and automation, 1999; pp.1018–1023. New York, NY: IEEE.
43.
WilliamsJHillRRPignatielloJJ, et al. Wavelet analysis of variance box plot. J Appl Stat2022; 49(14): 3536–3563.
