Abstract: The use of unmanned aerial vehicles (UAVs) is becoming more commonplace in search-and-rescue tasks, but UAV search planning can be very complex due to limited response time, large search area, and multiple candidate search modes. In this paper, we present a UAV search planning problem where the search area is divided into a set of subareas and each subarea has a prior probability that the target is present in it. The problem aims to determine the search sequence of the subareas and the search mode for each subarea to maximize the probability of finding the target. We propose an adaptive memetic algorithm that combines a genetic algorithm with a set of local search procedures and dynamically determines which procedure to apply based on the past performance of the procedures measured in fitness improvement and diversity improvement during problem-solving. Computational experiments show that the proposed algorithm exhibits competitive performance compared to a set of state-of-the-art global search heuristics, non-adaptive memetic algorithms, and adaptive memetic algorithms on a wide set of problem instances.

基于自适应文化基因算法的无人机搜救规划

[1]Al-Helal H, Sprinkle J, 2010. UAV search: maximizing target acquisition. Proc 17^th IEEE Int Conf and Workshops on Engineering of Computer Based Systems, p.9-18.

[2]Altshuler Y, Yanovsky V, Wagner IA, et al., 2008. Efficient cooperative search of smart targets using UAV swarms. Robotica, 26(4):551-557.

[3]Bertuccelli LF, How JP, 2006. UAV search for dynamic targets with uncertain motion models. Proc 45^th IEEE Conf on Decision and Control, p.5941-5946.

[4]Bourgault F, Furukawa T, Durrant-Whyte HF, 2006. Optimal search for a lost target in a Bayesian world. In: Yuta S, Asama H, Prassler E, et al. (Eds.), Field and Service Robotics: Recent Advances in Research and Applications. Springer, Berlin, Heidelberg, p.209-222.

[5]Burcin Ozsoydan F, Savgir M, 2021. Iterated greedy algorithms enhanced by hyper-heuristic based learning for hybrid flexible flowshop scheduling problem with sequence dependent setup times: a case study at a manufacturing plant. Comput Oper Res, 125:105044.

[6]Cabassi F, Locatelli M, 2016. Computational investigation of simple memetic approaches for continuous global optimization. Comput Oper Res, 72:50-70.

[7]Chak CK, Feng G, 1995. Accelerated genetic algorithms: combined with local search techniques for fast and accurate global search. Proc IEEE Int Conf on Evolutionary Computation, p.378-383.

[8]Chandler P, Rasmussen S, Pachter M, 2000. UAV cooperative path planning. Proc AIAA Guidance, Navigation, and Control Conf and Exhibit, p.1-11.

[9]Dong ZN, Chen ZJ, Zhou R, et al., 2011. A hybrid approach of virtual force and A^∗ search algorithm for UAV path re-planning. Proc 6^th IEEE Conf on Industrial Electronics and Applications, p.1140-1145.

[10]Du YC, Zhang MX, Ling HF, et al., 2019. Evolutionary planning of multi-UAV search for missing tourists. IEEE Access, 7:73480-73492.

[11]Duan HB, Li P, 2014. Bio-inspired Computation in Unmanned Aerial Vehicles. Springer, Berlin, Heidelberg.

[12]Eiben AE, Smit SK, 2011. Parameter tuning for configuring and analyzing evolutionary algorithms. Swarm Evol Comput, 1(1):19-31.

[13]Goodrich MA, Morse BS, Gerhardt D, et al., 2008. Supporting wilderness search and rescue using a camera-equipped mini UAV. J Field Robot, 25(1-2):89-110.

[14]Hansen SR, McLain TW, Goodrich MA, 2007. Probabilistic searching using a small unmanned aerial vehicle. Proc AIAA Infotech@Aerospace Conf and Exhibit, p.1-16.

[15]Hu CH, Xia Y, Zhang JG, 2019. Adaptive operator quantum-behaved pigeon-inspired optimization algorithm with application to UAV path planning. Algorithms, 12(1):3.

[16]Hutter F, Hoos HH, Leyton-Brown K, et al., 2009. ParamILS: an automatic algorithm configuration framework. J Artif Intell Res, 36:267-306.

[17]Jin Y, Liao Y, Minai AA, et al., 2006. Balancing search and target response in cooperative unmanned aerial vehicle (UAV) teams. IEEE Trans Syst Man Cybern Part B Cybern, 36(3):571-587.

[18]Kamrani F, Ayani R, 2009. UAV Path Planning in Search Operations. INTECH Open Access Publisher, Rijeka, Croatia.

[19]Krasnogor N, Smith J, 2005. A tutorial for competent memetic algorithms: model, taxonomy, and design issues. IEEE Trans Evol Comput, 9(5):474-488.

[20]Lai XJ, Hao JK, 2016. A tabu search based memetic algorithm for the max-mean dispersion problem. Comput Oper Res, 72:118-127.

[21]Li W, Yang BW, Song GH, et al., 2021. Dynamic value iteration networks for the planning of rapidly changing UAV swarms. Front Inform Technol Electron Eng, 22(5):687-696.

[22]Lin J, 2019. Backtracking search based hyper-heuristic for the flexible job-shop scheduling problem with fuzzy processing time. Eng Appl Artif Intell, 77:186-196.

[23]Lin L, Goodrich MA, 2009. UAV intelligent path planning for wilderness search and rescue. Proc IEEE/RSJ Int Conf on Intelligent Robots and Systems, p.709-714.

[24]López-Ibáñez M, Dubois-Lacoste J, Pérez Cáceres L, et al., 2016. The irace package: iterated racing for automatic algorithm configuration. Oper Res Persp, 3:43-58.

[25]López-Ortiz A, Maftuleac D, 2015. Optimal strategies for search and rescue operations with robot swarms. https://arxiv.org/abs/1410.1077v1

[26]Moscato P, Cotta C, 2003. A gentle introduction to memetic algorithms. In: Glover F, Kochenberger GA (Eds.), Handbook of Metaheuristics. Springer, Boston, USA, p.105-144.

[27]Murphy RR, Tadokoro S, Nardi D, et al., 2008. Search and rescue robotics. In: Siciliano B, Khatib O (Eds.), Springer Handbook of Robotics. Springer, Berlin, Heidelberg, p.1151-1173.

[28]Nikolos IK, Zografos ES, Brintaki AN, 2007. UAV path planning using evolutionary algorithms. In: Chahl JS, Jain LC, Mizutani A, et al. (Eds.), Innovations in Intelligent Machines 1. Springer, Berlin, Heidelberg, p.77-111.

[29]Ong YS, Lim MH, Zhu N, et al., 2006. Classification of adaptive memetic algorithms: a comparative study. IEEE Trans Syst Man Cybern Part B Cybern, 36(1):141-152.

[30]Özcan E, Drake JH, Altintacs C, et al., 2016. A self-adaptive Multimeme Memetic Algorithm co-evolving utility scores to control genetic operators and their parameter settings. Appl Soft Comput, 49:81-93.

[31]Phung MD, Ha QP, 2021. Safety-enhanced UAV path planning with spherical vector-based particle swarm optimization. Appl Soft Comput, 107:107376.

[32]Qi YT, Hou ZT, Li H, et al., 2015. A decomposition based memetic algorithm for multi-objective vehicle routing problem with time windows. Comput Oper Res, 62:61-77.

[33]Qin AK, Huang VL, Suganthan PN, 2009. Differential evolution algorithm with strategy adaptation for global numerical optimization. IEEE Trans Evol Comput, 13(2):398-417.

[34]Ragi S, Chong EKP, 2013. UAV path planning in a dynamic environment via partially observable Markov decision process. IEEE Trans Aerosp Electron Syst, 49(4):2397-2412.

[35]Ruan WY, Duan HB, 2020. Multi-UAV obstacle avoidance control via multi-objective social learning pigeon-inspired optimization. Front Inform Technol Electron Eng, 21(5):740-748.

[36]Ryan A, Hedrick JK, 2005. A mode-switching path planner for UAV-assisted search and rescue. Proc 44^th IEEE Conf on Decision and Control, p.1471-1476.

[37]Sheng WG, Chen SY, Sheng MM, et al., 2016. Adaptive multi-subpopulation competition and multiniche crowding-based memetic algorithm for automatic data clustering. IEEE Trans Evol Comput, 20(6):838-858.

[38]Syswerda G, 1991. Schedule optimization using genetic algorithms. In: Davis LD (Ed.), Handbook of Genetic Algorithms. van Nostrand Reinhold, New York, USA.

[39]Tisdale J, Kim Z, Hedrick JK, 2009. Autonomous UAV path planning and estimation. IEEE Robot Autom Mag, 16(2):35-42.

[40]Tomlin JA, 1971. Technical note—an improved branch-and-bound method for integer programming. Oper Res, 19(4):1070-1075.

[41]Turky A, Sabar NR, Dunstall S, et al., 2020. Hyper-heuristic local search for combinatorial optimisation problems. Knowl-Based Syst, 205:106264.

[42]van Willigen WH, Schut MC, Eiben AE, et al., 2011. Online adaptation of path formation in UAV search-and-identify missions. Proc Int Conf on Adaptive and Natural Computing Algorithms, p.186-195.

[43]Volgenant T, Jonker R, 1982. A branch and bound algorithm for the symmetric traveling salesman problem based on the 1-tree relaxation. Eur J Oper Res, 9(1):83-89.

[44]Waharte S, Trigoni N, 2010. Supporting search and rescue operations with UAVs. Proc Int Conf on Emerging Security Technologies, p.142-147.

[45]Waharte S, Symington A, Trigoni N, 2010. Probabilistic search with agile UAVs. Proc IEEE Int Conf on Robotics and Automation, p.2840-2845.

[46]Wang XP, Tang LX, 2017. A machine-learning based memetic algorithm for the multi-objective permutation flowshop scheduling problem. Comput Oper Res, 79:60-77.

[47]Wang Y, Zhang MX, Zheng YJ, 2017. A hyper-heuristic method for UAV search planning. Proc Int Conf on Swarm Intelligence, p.454-464

[48]Yu XB, Li CL, Yen GG, 2021. A knee-guided differential evolution algorithm for unmanned aerial vehicle path planning in disaster management. Appl Soft Comput, 98:106857.

[49]Zhang B, Duan HB, 2014. Predator-prey pigeon-inspired optimization for UAV three-dimensional path planning. Proc Int Conf on Swarm Intelligence, p.96-105.

[50]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.

[51]Zhang YZ, Mei Y, Tang K, et al., 2017. Memetic algorithm with route decomposing for periodic capacitated arc routing problem. Appl Soft Comput, 52:1130-1142.

[52]Zheng YJ, 2015. Water wave optimization: a new nature-inspired metaheuristic. Comput Oper Res, 55:1-11.

[53]Zheng YJ, Ling HF, Xue JY, 2014. Ecogeography-based optimization: enhancing biogeography-based optimization with ecogeographic barriers and differentiations. Comput Oper Res, 50:115-127.

[54]Zheng YJ, Zhang MX, Ling HF, et al., 2015. Emergency railway transportation planning using a hyper-heuristic approach. IEEE Trans Intell Transp Syst, 16(1):321-329.

[55]Zheng YJ, Du YC, Ling HF, et al., 2020. Evolutionary collaborative human-UAV search for escaped criminals. IEEE Trans Evol Comput, 24(2):217-231.

[56]Zheng YJ, Du YC, Su ZL, et al., 2021. Evolutionary human-UAV cooperation for transmission network restoration. IEEE Trans Ind Inform, 17(3):1648-1657.

[57]Zhou R, Feng Y, Di B, et al., 2020. Multi-UAV cooperative target tracking with bounded noise for connectivity preservation. Front Inform Technol Electron Eng, 21(10):1494-1503.