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).
摘要
本文提出一种在随机局部路径成本下使自主水下航行器在作业海域选择性地完成部分预定任务的路径规划器。该问题被表述为定向越野问题的变体。本文在遗传算法(GA)的基础上,提出一种基于贪心策略的遗传算法(GGA)。该算法包含一种新颖的通过在进化过程中将不可行个体映射到可行解空间来提高优化效率的重生算子,并以差分进化规划器计算确定性局部路径成本。局部路径成本的不确定性来自不可预测的障碍物、测量误差和轨迹跟踪误差。为了提高规划器在不确定环境下的鲁棒性,设计了一种用于路径评估的采样策略,通过对局部路径的概率密度函数多次采样,得到对路径实际成本的估计。通过蒙特卡罗仿真实验验证所提规划器的优越性和有效性。仿真结果表明,所提出的GGA在总收益方面优于同类算法4.7%–¬¬24.6%,而基于抽样的GGA路径规划器(S-GGARP)相较于普通的GGA路径规划器(GGARP)提高了5.5%的平均收益。
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
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. https://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. https://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. https://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. https://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. https://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. https://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. https://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. https://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. https://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. https://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. https://doi.org/10.1016/j.im.2021.103557
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. https://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. https://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. https://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. https://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. https://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. https://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. https://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. https://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. https://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. https://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. https://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. https://doi.org/10.1007/s11432-018-9723-5
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. https://doi.org/10.1109/ICAIBD51990.2021.9458959
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. https://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. https://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. https://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. https://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. https://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. https://doi.org/10.1016/j.oceaneng.2016.09.040
Author information
Authors and Affiliations
Contributions
Jiaxin ZHANG designed the research. Jiaxin ZHANG and Meiqin LIU processed the data. Jiaxin ZHANG drafted the paper. Senlin ZHANG helped organize the paper. Ronghao ZHENG revised and finalized the paper.
Corresponding author
Additional information
Compliance with ethics guidelines
Jiaxin ZHANG, Meiqin LIU, Senlin ZHANG, and Ronghao ZHENG declare that they have no conflict of interest.
Project supported by the National Natural Science Foundation of China and Zhejiang Joint Fund for the Integration of Industrialization and Informatization (Nos. U1809212 and U1909206), the Fundamental Research Funds for the Zhejiang Provincial Universities (No. 2021XZZX014), and the National Natural Science Foundation of China (No. 62088102)
Rights and permissions
About this article
Cite this article
Zhang, J., Liu, M., Zhang, S. et al. Robust global route planning for an autonomous underwater vehicle in a stochastic environment. Front Inform Technol Electron Eng 23, 1658–1672 (2022). https://doi.org/10.1631/FITEE.2200026
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1631/FITEE.2200026