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

 ORCID:

Libin Hong

https://orcid.org/0000-0003-2579-0523

Yujun Zheng

https://orcid.org/0000-0002-6095-6325

-   Go to

Article info.
Open peer comments

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

http://doi.org/10.1631/FITEE.2000632


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",
volume="22",
number="11",
pages="1477-1491",
year="2021",
publisher="Zhejiang University Press & Springer",
doi="10.1631/FITEE.2000632"
}

%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

TY - JOUR
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


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,王玥2,杜怡辰2,陈鑫1,郑宇军1
1杭州师范大学信息科学与技术学院,中国杭州市,311121
2浙江工业大学计算机科学与技术学院,中国杭州市,310023
摘要:无人机在搜救任务中的应用日益广泛,然而由于响应时间有限、搜索区域广、搜索模式多样,无人机搜索规划也更加复杂。本文提出一类无人机搜索规划问题,其搜索区域被划分为一组子区域,且每个子区域中目标存在的先验概率已知。解决该问题需要确定这些子区域的搜索顺序以及每个子区域的搜索模式,使得最终搜索成功的概率最大化。提出一种自适应文化基因算法,它结合了遗传算法和一组邻域搜索策略,基于问题求解过程中的适应度提升和多样性提升指标,动态选择邻域搜索策略。在多个问题实例上的计算实验表明,与先进的全局搜索启发式算法以及非自适应文化基因算法相比,所提算法展现了出色性能。

关键词:文化基因算法;自适应;无人机;搜救

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

Reference

[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

<1>

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