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

Jiaxin ZHANG; Meiqin LIU; Senlin ZHANG; Ronghao ZHENG

doi:10.1631/FITEE.2200026

Your Location：

Home >

Browse articles >

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

Regular Papers | Updated：2023-01-11

- Robust global route planning for an autonomous underwater vehicle in a stochastic environment
- 随机环境中的自主水下航行器鲁棒全局路径规划
- Frontiers of Information Technology & Electronic Engineering Vol. 23, Issue 11, Pages: 1658-1672(2022)
- Affiliations：
  
  1.State Key Laboratory of Industrial Control Technology, Zhejiang University, Hangzhou 310027, China
  2.College of Electrical Engineering, Zhejiang University, Hangzhou 310027, China
  3.Institute of Artificial Intelligence and Robotics, Xi’an Jiaotong University, Xi’an 710049, China
- Author bio：
  
  E-mail: zhangjiaxin@zju.edu.cn;
  ‡Corresponding author
  slzhang@zju.edu.cn;
  rzheng@zju.edu.cn
- Funds：
- DOI：10.1631/FITEE.2200026
  CLC： TP242.2
- Received：20 January 2022，
  
  Accepted：07 March 2022，
  
  Published Online：29 April 2022，
  
  Published：0 November 2022
- Accepted：
Scan QR Code
Jiaxin ZHANG, Meiqin LIU, Senlin ZHANG, et al. 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.
DOI：

Jiaxin ZHANG, Meiqin LIU, Senlin ZHANG, et al. 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. DOI： 10.1631/FITEE.2200026.

摘要

本文提出一种在随机局部路径成本下使自主水下航行器在作业海域选择性地完成部分预定任务的路径规划器。该问题被表述为定向越野问题的变体。本文在遗传算法（GA）的基础上，提出一种基于贪心策略的遗传算法（GGA）。该算法包含一种新颖的通过在进化过程中将不可行个体映射到可行解空间来提高优化效率的重生算子，并以差分进化规划器计算确定性局部路径成本。局部路径成本的不确定性来自不可预测的障碍物、测量误差和轨迹跟踪误差。为了提高规划器在不确定环境下的鲁棒性，设计了一种用于路径评估的采样策略，通过对局部路径的概率密度函数多次采样，得到对路径实际成本的估计。通过蒙特卡罗仿真实验验证所提规划器的优越性和有效性。仿真结果表明，所提出的GGA在总收益方面优于同类算法4.7%–24.6%，而基于抽样的GGA路径规划器（S-GGARP）相较于普通的GGA路径规划器（GGARP）提高了5.5%的平均收益。

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

关键词

Keywords

references

Abbasi A , Mahmoud Zadeh S , Yazdani A , 2020 . A cooperative dynamic task assignment framework for COTSBot AUVs . IEEE Trans Autom Sci Eng , early access . doi: 10.1109/TASE.2020.3044155 http://doi.org/10.1109/TASE.2020.3044155

Bagagiolo F , Festa A , Marzufero L , 2021 . The orienteering problem: a hybrid control formulation . IFAC-PapersOnLine , 54 ( 5 ): 175 - 180 . doi: 10.1016/j.ifacol.2021.08.494 http://doi.org/10.1016/j.ifacol.2021.08.494

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 . doi: 10.1631/FITEE.1900586 http://doi.org/10.1631/FITEE.1900586

Cheng CX , Sha QX , He B , et al. , 2021 . Path planning and obstacle avoidance for AUV: a review . Ocean Eng , 235 : 109355 . doi: 10.1016/J.OCEANENG.2021.109355 http://doi.org/10.1016/J.OCEANENG.2021.109355

Chou XC , Gambardella LM , Montemanni R , 2021 . A Tabu Search algorithm for the probabilistic orienteering problem . Comput Oper Res , 126 : 105107 . doi: 10.1016/j.cor.2020.105107 http://doi.org/10.1016/j.cor.2020.105107

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 . doi: 10.1109/TSMC.2016.2582745 http://doi.org/10.1109/TSMC.2016.2582745

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 . doi: 10.1016/j.proeng.2014.12.098 http://doi.org/10.1016/j.proeng.2014.12.098

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 . doi: 10.1016/j.cor.2013.09.011 http://doi.org/10.1016/j.cor.2013.09.011

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 . doi: 10.1007/978-3-319-00930-8_32 http://doi.org/10.1007/978-3-319-00930-8_32

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 . doi: 10.1109/TVT.2021.3097084 http://doi.org/10.1109/TVT.2021.3097084

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 . doi: 10.1016/j.im.2021.103557 http://doi.org/10.1016/j.im.2021.103557

Kirsanov A , Anavatti SG , Ray T , 2013 . Path planning for the autonomous underwater vehicle . Proc 4 th Int Conf on Swarm, Evolutionary, and Memetic Computing , p. 476 - 486 . doi: 10.1007/978-3-319-03756-1_43 http://doi.org/10.1007/978-3-319-03756-1_43

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 . doi: 10.1142/S2301385021500151 http://doi.org/10.1142/S2301385021500151

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 . doi: 10.1109/IRIS.2015.7451578 http://doi.org/10.1109/IRIS.2015.7451578

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 . doi: 10.1007/s00500-016-2433-2 http://doi.org/10.1007/s00500-016-2433-2

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 . doi: 10.1109/TCYB.2018.2837134 http://doi.org/10.1109/TCYB.2018.2837134

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 . doi: 10.1007/978-3-319-18167-7_10 http://doi.org/10.1007/978-3-319-18167-7_10

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 .

Schilde M , Doerner KF , Hartl RF , et al. , 2009 . Metaheuristics for the bi-objective orienteering problem . Swarm Intell , 3 ( 3 ): 179 - 201 . doi: 10.1007/s11721-009-0029-5 http://doi.org/10.1007/s11721-009-0029-5

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 . doi: 10.1016/j.asoc.2021.108086 http://doi.org/10.1016/j.asoc.2021.108086

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 . doi: 10.1142/S0217595904000229 http://doi.org/10.1142/S0217595904000229

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 . doi: 10.1109/TIE.2011.2109332 http://doi.org/10.1109/TIE.2011.2109332

Vansteenwegen P , van Oudheusden D , 2007 . The mobile tourist guide: an OR opportunity . OR Insight , 20 ( 3 ): 21 - 27 . doi: 10.1057/ori.2007.17 http://doi.org/10.1057/ori.2007.17

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 . doi: 10.1007/s11432-018-9723-5 http://doi.org/10.1007/s11432-018-9723-5

Yan SK , 2021 . Research on path planning of AUV based on improved ant colony algorithm . Proc 4 th Int Conf on Artificial Intelligence and Big Data , p. 121 - 124 . doi: 10.1109/ICAIBD51990.2021.9458959 http://doi.org/10.1109/ICAIBD51990.2021.9458959

Yu H , Wang YJ , 2014 . Multi-objective AUV path planning in large complex battlefield environments . Proc 7 th Int Symp on Computational Intelligence and Design , p. 345 - 348 . doi: 10.1109/ISCID.2014.118 http://doi.org/10.1109/ISCID.2014.118

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 . doi: 10.1007/s10846-014-0104-z http://doi.org/10.1007/s10846-014-0104-z

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 . doi: 10.1007/s00773-019-00629-0 http://doi.org/10.1007/s00773-019-00629-0

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 . doi: 10.1631/FITEE.2000228 http://doi.org/10.1631/FITEE.2000228

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 . doi: 10.1007/s10846-021-01533-9 http://doi.org/10.1007/s10846-021-01533-9

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 . doi: 10.1016/j.oceaneng.2016.09.040 http://doi.org/10.1016/j.oceaneng.2016.09.040

Views

Downloads

CSCD

Alert me when the article has been cited

Submit

Tools

Publicity Resources

A novel forwarding and routing mechanism design in SDN-based NDN architecture

Discovering optimal features using static analysis and a genetic search based method for Android malware detection

A scheduling method based on a hybrid genetic particle swarm algorithm for multifunction phased array radar

Fuzzy cost-profit tradeoff model for locating a vehicle inspection station considering regional constraints

ECG quality assessment based on a kernel support vector machine and genetic algorithm with a feature matrix

Related Author

Jia LI

Ren-chao XIE

Tao HUANG

Li SUN

Nor Badrul ANUAR

Ahmad KARIM

Mohd Faizal Ab RAZAK

Ahmad FIRDAUS

Related Institution

State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications

Faculty of Computer System & Software Engineering, University Malaysia Pahang, Gambang

Department of Information Technology, Bahauddin Zakariya University

Department of Computer System and Technology, University of Malaya

Air and Missile Defense College, Air Force Engineering University

Chat

Address：Zhejiang University Press, 148 Tianmushan Road, Hangzhou, China Postal code：310028
Tel：+86-571-88273162 Email：fitee@zju.edu.cn
It is recommended to read the content of this site in Chrome&IE9+. Please switch to extreme mode in browser 360.
Cookies We use cookies to help provide and enhance our service and tailor content. By continuing, you agree to the use of cookies.

⁰