Full Text:   <1887>

Summary:  <773>

CLC number: TP399

On-line Access: 2021-11-15

Received: 2020-11-13

Revision Accepted: 2021-05-16

Crosschecked: 2021-09-01

Cited: 0

Clicked: 3429

Citations:  Bibtex RefMan EndNote GB/T7714


Libin Hong


Yujun Zheng


-   Go to

Article info.
Open peer comments

Frontiers of Information Technology & Electronic Engineering  2021 Vol.22 No.11 P.1477-1491


UAV search-and-rescue planning using an adaptive memetic algorithm

Author(s):  Libin Hong, Yue Wang, Yichen Du, Xin Chen, Yujun Zheng

Affiliation(s):  School of Information Science and Technology, Hangzhou Normal University, Hangzhou 311121, China; more

Corresponding email(s):   yujun.zheng@computer.org

Key Words:  Memetic algorithm, Self-adaptive, Unmanned aerial vehicle (UAV), Search-and-rescue

Libin Hong, Yue Wang, Yichen Du, Xin Chen, Yujun Zheng. UAV search-and-rescue planning using an adaptive memetic algorithm[J]. Frontiers of Information Technology & Electronic Engineering, 2021, 22(11): 1477-1491.

@article{title="UAV search-and-rescue planning using an adaptive memetic algorithm",
author="Libin Hong, Yue Wang, Yichen Du, Xin Chen, Yujun Zheng",
journal="Frontiers of Information Technology & Electronic Engineering",
publisher="Zhejiang University Press & Springer",

%0 Journal Article
%T UAV search-and-rescue planning using an adaptive memetic algorithm
%A Libin Hong
%A Yue Wang
%A Yichen Du
%A Xin Chen
%A Yujun Zheng
%J Frontiers of Information Technology & Electronic Engineering
%V 22
%N 11
%P 1477-1491
%@ 2095-9184
%D 2021
%I Zhejiang University Press & Springer
%DOI 10.1631/FITEE.2000632

T1 - UAV search-and-rescue planning using an adaptive memetic algorithm
A1 - Libin Hong
A1 - Yue Wang
A1 - Yichen Du
A1 - Xin Chen
A1 - Yujun Zheng
J0 - Frontiers of Information Technology & Electronic Engineering
VL - 22
IS - 11
SP - 1477
EP - 1491
%@ 2095-9184
Y1 - 2021
PB - Zhejiang University Press & Springer
ER -
DOI - 10.1631/FITEE.2000632

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.




Darkslateblue:Affiliate; Royal Blue:Author; Turquoise:Article


[1]Al-Helal H, Sprinkle J, 2010. UAV search: maximizing target acquisition. Proc 17th 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 45th 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 6th 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 44th 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.

Open peer comments: Debate/Discuss/Question/Opinion


Please provide your name, email address and a comment

Journal of Zhejiang University-SCIENCE, 38 Zheda Road, Hangzhou 310027, China
Tel: +86-571-87952783; E-mail: cjzhang@zju.edu.cn
Copyright © 2000 - 2022 Journal of Zhejiang University-SCIENCE