Full Text:   <343>

Summary:  <8>

CLC number: TP242.2

On-line Access: 2022-10-26

Received: 2022-01-20

Revision Accepted: 2022-10-26

Crosschecked: 2022-03-07

Cited: 0

Clicked: 400

Citations:  Bibtex RefMan EndNote GB/T7714


Meiqin LIU


Jiaxin ZHANG


-   Go to

Article info.
Open peer comments

Frontiers of Information Technology & Electronic Engineering  2022 Vol.23 No.11 P.1658-1672


Robust global route planning for an autonomous underwater vehicle in a stochastic environment

Author(s):  Jiaxin ZHANG, Meiqin LIU, Senlin ZHANG, Ronghao ZHENG

Affiliation(s):  State Key Laboratory of Industrial Control Technology, Zhejiang University, Hangzhou 310027, China; more

Corresponding email(s):   zhangjiaxin@zju.edu.cn, liumeiqin@zju.edu.cn, slzhang@zju.edu.cn, rzheng@zju.edu.cn

Key Words:  Autonomous underwater vehicle, Route planning, Genetic algorithm, Orienteering problem, Stochastic path cost

Jiaxin ZHANG, Meiqin LIU, Senlin ZHANG, Ronghao ZHENG. Robust global route planning for an autonomous underwater vehicle in a stochastic environment[J]. Frontiers of Information Technology & Electronic Engineering, 2022, 23(11): 1658-1672.

@article{title="Robust global route planning for an autonomous underwater vehicle in a stochastic environment",
author="Jiaxin ZHANG, Meiqin LIU, Senlin ZHANG, Ronghao ZHENG",
journal="Frontiers of Information Technology & Electronic Engineering",
publisher="Zhejiang University Press & Springer",

%0 Journal Article
%T Robust global route planning for an autonomous underwater vehicle in a stochastic environment
%A Jiaxin ZHANG
%A Meiqin LIU
%A Senlin ZHANG
%A Ronghao ZHENG
%J Frontiers of Information Technology & Electronic Engineering
%V 23
%N 11
%P 1658-1672
%@ 2095-9184
%D 2022
%I Zhejiang University Press & Springer
%DOI 10.1631/FITEE.2200026

T1 - Robust global route planning for an autonomous underwater vehicle in a stochastic environment
A1 - Jiaxin ZHANG
A1 - Meiqin LIU
A1 - Senlin ZHANG
A1 - Ronghao ZHENG
J0 - Frontiers of Information Technology & Electronic Engineering
VL - 23
IS - 11
SP - 1658
EP - 1672
%@ 2095-9184
Y1 - 2022
PB - Zhejiang University Press & Springer
ER -
DOI - 10.1631/FITEE.2200026

This paper describes a route planner that enables an autonomous underwater vehicle to selectively complete part of the predetermined tasks in the operating ocean area when the local path cost is stochastic. The problem is formulated as a variant of the orienteering problem. Based on the genetic algorithm (GA), we propose the greedy strategy based GA (GGA) which includes a novel rebirth operator that maps infeasible individuals into the feasible solution space during evolution to improve the efficiency of the optimization, and use a differential evolution planner for providing the deterministic local path cost. The uncertainty of the local path cost comes from unpredictable obstacles, measurement error, and trajectory tracking error. To improve the robustness of the planner in an uncertain environment, a sampling strategy for path evaluation is designed, and the cost of a certain route is obtained by multiple sampling from the probability density functions of local paths. Monte Carlo simulations are used to verify the superiority and effectiveness of the planner. The promising simulation results show that the proposed GGA outperforms its counterparts by 4.7%–24.6% in terms of total profit, and the sampling-based GGA route planner (S-GGARP) improves the average profit by 5.5% compared to the GGA route planner (GGARP).




Darkslateblue:Affiliate; Royal Blue:Author; Turquoise:Article


[1]Abbasi A, Mahmoud Zadeh S, Yazdani A, 2020. A cooperative dynamic task assignment framework for COTSBot AUVs. IEEE Trans Autom Sci Eng, early access.

[2]Bagagiolo F, Festa A, Marzufero L, 2021. The orienteering problem: a hybrid control formulation. IFAC-PapersOnLine, 54(5):175-180.

[3]Cai CY, Yao XL, 2020. Trajectory optimization with constraints for alpine skiers based on multi-phase nonlinear optimal control. Front Inform Technol Electron Eng, 21(10):1521-1534.

[4]Cheng CX, Sha QX, He B, et al., 2021. Path planning and obstacle avoidance for AUV: a review. Ocean Eng, 235:109355.

[5]Chou XC, Gambardella LM, Montemanni R, 2021. A Tabu Search algorithm for the probabilistic orienteering problem. Comput Oper Res, 126:105107.

[6]Dorling K, Heinrichs J, Messier GG, et al., 2017. Vehicle routing problems for drone delivery. IEEE Trans Syst Man Cybern Syst, 47(1):70-85.

[7]Duchoň F, Babinec A, Kajan M, et al., 2014. Path planning with modified A star algorithm for a mobile robot. Procedia Eng, 96:59-69.

[8]Evers L, Glorie K, van der Ster S, et al., 2014. A two-stage approach to the orienteering problem with stochastic weights. Comput Oper Res, 43:248-260.

[9]Ferreira J, Quintas A, Oliveira JA, et al., 2014. Solving the team orienteering problem: developing a solution tool using a genetic algorithm approach. In: SnáŠel V, Krömer P, Köppen M, et al. (Eds.), Soft Computing in Industrial Applications. Springer, Cham, p.365-375.

[10]Han GJ, Gong AN, Wang H, et al., 2021. Multi-AUV collaborative data collection algorithm based on Q-learning in underwater acoustic sensor networks. IEEE Trans Veh Technol, 70(9):9294-9305.

[11]Ji HP, Zheng WM, Zhuang XY, et al., 2021. Explore for a day? Generating personalized itineraries that fit spatial heterogeneity of tourist attractions. Inform Manage, 58(8):103557.

[12]Kirsanov A, Anavatti SG, Ray T, 2013. Path planning for the autonomous underwater vehicle. Proc 4th Int Conf on Swarm, Evolutionary, and Memetic Computing, p.476-486.

[13]Lan ML, Lai SP, Lee TH, et al., 2021. A survey of motion and task planning techniques for unmanned multicopter systems. Unmanned Syst, 9(2):165-198.

[14]Mahmoud Zadeh S, Powers D, Sammut K, et al., 2015. Optimal route planning with prioritized task scheduling for AUV missions. Proc IEEE Int Symp on Robotics and Intelligent Sensors, p.7-14.

[15]Mahmoud Zadeh S, Powers DMW, Sammut K, et al., 2018. A novel versatile architecture for autonomous underwater vehicle’s motion planning and task assignment. Soft Comput, 22(5):1687-1710.

[16]Mahmoud Zadeh S, Powers DMW, Atyabi A, 2019. UUV’s hierarchical DE-based motion planning in a semi dynamic underwater wireless sensor network. IEEE Trans Cybern, 49(8):2992-3005.

[17]Marinakis Y, Politis M, Marinaki M, et al., 2015. A memetic-GRASP algorithm for the solution of the orienteering problem. In: Le HA, Dinh TP, Nguyen NT (Eds.), Modelling, Computation and Optimization in Information Systems and Management Sciences. Springer, Cham, p.105-116.

[18]Royset JO, Reber DN, 2009. Optimized routing of unmanned aerial systems for the interdiction of improvised explosive devices. Mil Oper Res, 14(4):5-19.

[19]Schilde M, Doerner KF, Hartl RF, et al., 2009. Metaheuristics for the bi-objective orienteering problem. Swarm Intell, 3(3):179-201.

[20]Sun SQ, Song BW, Wang P, et al., 2022. An adaptive bi-level task planning strategy for multi-USVs target visitation. Appl Soft Comput, 115:108086.

[21]Teng SY, Ong HL, Huang HC, 2004. An integer L-shaped algorithm for time-constrained traveling salesman problem with stochastic travel and service times. Asia-Pac J Oper Res, 21(2):241-257.

[22]Tsai CC, Huang HC, Chan CK, 2011. Parallel elite genetic algorithm and its application to global path planning for autonomous robot navigation. IEEE Trans Ind Electron, 58(10):4813-4821.

[23]Vansteenwegen P, van Oudheusden D, 2007. The mobile tourist guide: an OR opportunity. OR Insight, 20(3):21-27.

[24]Xue ZB, Liu JX, Wu ZX, et al., 2019. Development and path planning of a novel unmanned surface vehicle system and its application to exploitation of Qarhan Salt Lake. Sci China Inform Sci, 62(8):84202.

[25]Yan SK, 2021. Research on path planning of AUV based on improved ant colony algorithm. Proc 4th Int Conf on Artificial Intelligence and Big Data, p.121-124.

[26]Yu H, Wang YJ, 2014. Multi-objective AUV path planning in large complex battlefield environments. Proc 7th Int Symp on Computational Intelligence and Design, p.345-348.

[27]Zeng Z, Sammut K, Lammas A, et al., 2015. Efficient path re-planning for AUVs operating in spatiotemporal currents. J Intell Robot Syst, 79(1):135-153.

[28]Zeng Z, Zhou HX, Lian L, 2020. Exploiting ocean energy for improved AUV persistent presence: path planning based on spatiotemporal current forecasts. J Mar Sci Technol, 25(1):26-47.

[29]Zhang H, Xin B, Dou LH, et al., 2020. A review of cooperative path planning of an unmanned aerial vehicle group. Front Inform Technol Electron Eng, 21(12):1671-1694.

[30]Zhang JX, Liu MQ, Zhang SL, et al., 2022. AUV path planning based on differential evolution with environment prediction. J Intell Robot Syst, 104(2):23.

[31]Zhuang YF, Sharma S, Subudhi B, et al., 2016. Efficient collision-free path planning for autonomous underwater vehicles in dynamic environments with a hybrid optimization algorithm. Ocean Eng, 127:190-199.

Open peer comments: Debate/Discuss/Question/Opinion


Please provide your name, email address and a comment

Journal of Zhejiang University-SCIENCE, 38 Zheda Road, Hangzhou 310027, China
Tel: +86-571-87952783; E-mail: cjzhang@zju.edu.cn
Copyright © 2000 - 2022 Journal of Zhejiang University-SCIENCE