Similar articles

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]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 4^th 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 4^th 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 7^th 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.