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

 ORCID:

Meiqin LIU

https://orcid.org/0000-0003-0693-6574

Jiaxin ZHANG

https://orcid.org/0000-0003-3358-2206

-   Go to

Article info.
Open peer comments

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

http://doi.org/10.1631/FITEE.2200026


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",
volume="23",
number="11",
pages="1658-1672",
year="2022",
publisher="Zhejiang University Press & Springer",
doi="10.1631/FITEE.2200026"
}

%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

TY - JOUR
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


Abstract: 
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).

随机环境中的自主水下航行器鲁棒全局路径规划

张佳欣1,2,刘妹琴1,2,3,张森林1,2,郑荣濠1,2
1浙江大学工业控制技术国家重点实验室,中国杭州市,310027
2浙江大学电气工程学院,中国杭州市,310027
3西安交通大学人工智能与机器人研究所,中国西安市,710049
摘要:本文提出一种在随机局部路径成本下使自主水下航行器在作业海域选择性地完成部分预定任务的路径规划器。该问题被表述为定向越野问题的变体。本文在遗传算法(GA)的基础上,提出一种基于贪心策略的遗传算法(GGA)。该算法包含一种新颖的通过在进化过程中将不可行个体映射到可行解空间来提高优化效率的重生算子,并以差分进化规划器计算确定性局部路径成本。局部路径成本的不确定性来自不可预测的障碍物、测量误差和轨迹跟踪误差。为了提高规划器在不确定环境下的鲁棒性,设计了一种用于路径评估的采样策略,通过对局部路径的概率密度函数多次采样,得到对路径实际成本的估计。通过蒙特卡罗仿真实验验证所提规划器的优越性和有效性。仿真结果表明,所提出的GGA在总收益方面优于同类算法4.7%-24.6%,而基于抽样的GGA路径规划器(S-GGARP)相较于普通的GGA路径规划器(GGARP)提高了5.5%的平均收益。

关键词:自主水下航行器;路径规划;遗传算法;定向越野问题;随机路径成本

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

Reference

[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

<1>

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