An effective memetic algorithm for UAV routing and orientation under uncertain navigation environments
Tóm tắt
Navigation correction is usually frequently required by unmanned aerial vehicles (UAVs), especially under uncertain navigation environments. Although the UAV’s straight flights that connect navigation correction points can constitute a plan of navigation corrections, the underlying attitude orientations of the UAV when flying through the visited points are also required by appropriate steering motions. In this regard, a UAV routing and orientation problem (UAV-ROP) that minimizes the 3D flight distances of the UAV under navigational, steering and uncertain constraints, is introduced and proven NP-hard in this paper. To optimize the layered routing and orientations in the UAV-ROP simultaneously, an effective memetic algorithm is proposed in this paper. In the algorithm, the GA performs the outer loop for optimizing the route and the local search metaheuristic does the inner loop for optimizing the orientations. Also, a globally maintained knowledge base that records high-quality sub-routes is used to accelerate the inner optimization of the memetic algorithm. The highlight in addressing the UAV-ROP in this paper is a layered optimization idea in a memetic algorithm to fit the layered optimization requirements of the problem. Experiments on open-access datasets indicate that, the proposed memetic algorithm shows an excellent overall performance compared with other competitors, which is qualified to give an authenticated reliable route with orientations of the UAV despite uncertain navigation environments.
Tài liệu tham khảo
Almadhoun R, Taha T, Dias J, Seneviratne L, Zweiri Y (2019) Coverage path planning for complex structures inspection using unmanned aerial vehicle (uav). In: International conference on intelligent robotics and applications. Springer, pp 243–266
Atencia CR, Del Ser J, Camacho D (2019) Weighted strategies to guide a multi-objective evolutionary algorithm for multi-UAV mission planning. Swarm Evolut Comput 44:480–495
Chao IM, Golden BL, Wasil EA (1996) The team orienteering problem. Eur J Oper Res 88(3):464–474
Chen F, Wang H, Xie Y, Qi C (2016) An ACO-based online routing method for multiple order pickers with congestion consideration in warehouse. J Intell Manuf 27(2):389–408
Chen MC, Hsiao YH, Reddy RH, Tiwari MK (2016) The self-learning particle swarm optimization approach for routing pickup and delivery of multiple products with material handling in multiple cross-docks. Transp Res Part E Logist Transp Rev 91:208–226
Coelho BN, Coelho VN, Coelho IM, Ochi LS, Haghnazar R, Zuidema D, Lima MS, da Costa AR (2017) A multi-objective green UAV routing problem. Comput Oper Res 88:306–315
da Costa PRdO, Mauceri S, Carroll P, Pallonetto F (2018) A genetic algorithm for a green vehicle routing problem. Electron Notes Discrete Math 64:65–74
Dubins LE (1957) On curves of minimal length with a constraint on average curvature, and with prescribed initial and terminal positions and tangents. Am J Math 79(3):497–516
Eremeev AV, Kovalenko YV (2020) A memetic algorithm with optimal recombination for the asymmetric travelling salesman problem. Memet Comput 12(1):23–36
Golden BL, Levy L, Vohra R (1987) The orienteering problem. Naval Res Logist (NRL) 34(3):307–318
Gunawan A, Lau HC, Vansteenwegen P (2016) Orienteering problem: a survey of recent variants, solution approaches and applications. Eur J Oper Res 255(2):315–332
Guo K, Li X, Xie L (2020) Simultaneous cooperative relative localization and distributed formation control for multiple UAVs. Sci China Inf Sci 63(1):119201
Guzey HM, Dierks T, Jagannathan S, Acar L (2019) Modified consensus-based output feedback control of quadrotor UAV formations using neural networks. J Intell Robot Syst 94(1):283–300
Harikumar K, Senthilnath J, Sundaram S (2018) Multi-UAV oxyrrhis marina-inspired search and dynamic formation control for forest firefighting. IEEE Trans Autom Sci Eng 16(2):863–873
Huang Y, Chen J, Wang H, Su G (2019) A method of 3d path planning for solar-powered UAV with fixed target and solar tracking. Aerosp Sci Technol 92:831–838
Huo M, Duan H, Yang Q, Zhang D, Qiu H (2019) Live-fly experimentation for pigeon-inspired obstacle avoidance of quadrotor unmanned aerial vehicles. Sci China Inf Sci 62(5):52201
Kachitvichyanukul V, Sombuntham P, Kunnapapdeelert S (2015) Two solution representations for solving multi-depot vehicle routing problem with multiple pickup and delivery requests via PSO. Comput Ind Eng 89:125–136
Khosiawan Y, Khalfay A, Nielsen I (2018) Scheduling unmanned aerial vehicle and automated guided vehicle operations in an indoor manufacturing environment using differential evolution-fused particle swarm optimization. Int J Adv Rob Syst 15(1):17–29
Kim SJ, Jeong Y, Park S, Ryu K, Oh G (2018) A survey of drone use for entertainment and AVR (augmented and virtual reality). In: Augmented reality and virtual reality. Springer, pp 339–352
Li J, Deng G, Luo C, Lin Q, Yan Q, Ming Z (2016) A hybrid path planning method in unmanned air/ground vehicle (UAV/UGV) cooperative systems. IEEE Trans Veh Technol 65(12):9585–9596
Li J, Han Y (2016) Optimal resource allocation for packet delay minimization in multi-layer UAV networks. IEEE Commun Lett 21(3):580–583
Li Y, Soleimani H, Zohal M (2019) An improved ant colony optimization algorithm for the multi-depot green vehicle routing problem with multiple objectives. J Clean Prod 227:1161–1172
Lim A, Zhang X (2017) A two-stage heuristic with ejection pools and generalized ejection chains for the vehicle routing problem with time windows. Informs J Comput 19(3):443–457
Lin J, Zhou W, Wolfson O (2016) Electric vehicle routing problem. Transp Res Procedia 12:508–521
Liu X, Ansari N (2018) Resource allocation in UAV-assisted m2m communications for disaster rescue. IEEE Wirel Commun Lett 8(2):580–583
Ma L, Huang X, Chen J, Li J, Sun T (2020) A two-level memetic path planning algorithm for unmanned air/ground vehicle cooperative detection systems. In: 2020 5th international conference on advanced robotics and mechatronics (ICARM). IEEE, pp 25–30
Ma L, Li J, Lin Q, Gong M, Coello CAC, Ming Z (2019) Cost-aware robust control of signed networks by using a memetic algorithm. IEEE Trans Cybern 50(10):4430–4443
Manfreda S, McCabe MF, Miller PE, Lucas R, Pajuelo Madrigal V, Mallinis G, Ben Dor E, Helman D, Estes L, Ciraolo G et al (2018) On the use of unmanned aerial systems for environmental monitoring. Remote Sens 10(4):641
Nekkaa M, Boughaci D (2015) A memetic algorithm with support vector machine for feature selection and classification. Memet Comput 7(1):59–73
Peng B, Zhang Y, Lü Z, Cheng T, Glover F (2020) A learning-based memetic algorithm for the multiple vehicle pickup and delivery problem with lifo loading. Comput Ind Eng 142:106241
Reina D, Tawfik H, Toral S (2018) Multi-subpopulation evolutionary algorithms for coverage deployment of UAV-networks. Ad Hoc Netw 68:16–32
Roberge V, Tarbouchi M, Labonté G (2012) Comparison of parallel genetic algorithm and particle swarm optimization for real-time UAV path planning. IEEE Trans Ind Inf 9(1):132–141
Samma H, Lim CP, Saleh JM, Suandi SA (2016) A memetic-based fuzzy support vector machine model and its application to license plate recognition. Memet Comput 8(3):235–251
Sheng W, Chen S, Sheng M, Xiao G, Mao J, Zheng Y (2016) Adaptive multisubpopulation competition and multiniche crowding-based memetic algorithm for automatic data clustering. IEEE Trans Evol Comput 20(6):838–858
Song BD, Park K, Kim J (2018) Persistent UAV delivery logistics: MILP formulation and efficient heuristic. Comput Ind Eng 120:418–428
Vansteenwegen P, Souffriau W, Van Oudheusden D (2011) The orienteering problem: a survey. Eur J Oper Res 209(1):1–10
Wang T, Qin R, Chen Y, Snoussi H, Choi C (2019) A reinforcement learning approach for UAV target searching and tracking. Multim Tools Appl 78(4):4347–4364
Wu X, Che A (2019) A memetic differential evolution algorithm for energy-efficient parallel machine scheduling. Omega 82:155–165
Xia W, Wu Z (2005) An effective hybrid optimization approach for multi-objective flexible job-shop scheduling problems. Comput Ind Eng 48(2):409–425
Xing L, Rohlfshagen P, Chen Y, Yao X (2009) An evolutionary approach to the multidepot capacitated arc routing problem. IEEE Trans Evol Comput 14(3):356–374
Xue Y, Rui Z, Yu X, Sang X, Liu W (2019) Estimation of distribution evolution memetic algorithm for the unrelated parallel-machine green scheduling problem. Memet Comput 11(4):423–437
Yang H, Meng C, Wang C (2020) A probability first memetic algorithm for the dynamic multiple-fault diagnosis problem with non-ideal tests. Memet Comput 12:101–113
Yang X, Bostel N, Dejax P (2019) A MILP model and memetic algorithm for the hub location and routing problem with distinct collection and delivery tours. Comput Ind Eng 135:105–119
Zeng ZZ, Yu XG, Chen M, Liu YY (2018) A memetic algorithm to pack unequal circles into a square. Comput Oper Res 92:47–55
Zhu Z, Xiao J, Li JQ, Wang F, Zhang Q (2015) Global path planning of wheeled robots using multi-objective memetic algorithms. Integr Comput-Aided Eng 22(4):387–404