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

Libin HONG; Yue WANG; Yichen DU; Xin CHEN; Yujun ZHENG

doi:10.1631/FITEE.2000632

Your Location：

Home >

Browse articles >

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

Regular Papers | Updated：2022-01-05

- UAV search-and-rescue planning using an adaptive memetic algorithm
- 基于自适应文化基因算法的无人机搜救规划
- Frontiers of Information Technology & Electronic Engineering Vol. 22, Issue 11, Pages: 1477-1491(2021)
- Affiliations：
  
  School of Information Science and Technology, Hangzhou Normal University, Hangzhou 311121, China
  College of Computer Science and Technology, Zhejiang University of Technology, Hangzhou 310023, China
- Author bio：
  
  Yujun ZHENG, E-mail: yujun.zheng@computer.org
- Funds：
- DOI：10.1631/FITEE.2000632
  CLC： TP399
- Received：13 November 2020，
  
  Revised：2021-;9-;1，
  
  Accepted：16 May 2021，
  
  Published：2021-11
- Accepted：
Scan QR Code
Libin HONG, Yue WANG, Yichen DU, et al. UAV search-and-rescue planning using an adaptive memetic algorithm[J]. Frontiers of Information Technology & Electronic Engineering, 2021, 22(11): 1477-1491.
DOI：

Libin HONG, Yue WANG, Yichen DU, et al. UAV search-and-rescue planning using an adaptive memetic algorithm[J]. Frontiers of Information Technology & Electronic Engineering, 2021, 22(11): 1477-1491. 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.

关键词

Keywords

references

H Al-Helal , , , J Sprinkle . . UAV search: maximizing target acquisition . . Proc 17 th IEEE Int Conf and Workshops on Engineering of Computer Based Systems , , 2010 . . p.9 - - 18 . . DOI: 10.1109/ECBS.2010.9 http://doi.org/10.1109/ECBS.2010.9 . .

Y Altshuler , , , V Yanovsky , , , IA Wagner , , , 等 . . Efficient cooperative search of smart targets using UAV swarms . . Robotica , , 2008 . . 26 ( ( 4 ): ): 551 - - 557 . . DOI: 10.1017/S0263574708004141 http://doi.org/10.1017/S0263574708004141 . .

LF Bertuccelli , , , JP How . . UAV search for dynamic targets with uncertain motion models . . Proc 45 th IEEE Conf on Decision and Control , , 2006 . . p. 5941 - - 5946 . . DOI: 10.1109/CDC.2006.377010 http://doi.org/10.1109/CDC.2006.377010 . .

F Bourgault , , , T Furukawa , , , HF Durrant-Whyte . . 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 , , 2006 . . p. 209 - - 222 . . DOI: 10.1007/10991459_21 http://doi.org/10.1007/10991459_21 . .

F Burcin Ozsoydan , , , M Saǧir . . 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 , , 2021 . . 125 105044 DOI: 10.1016/j.cor.2020.105044 http://doi.org/10.1016/j.cor.2020.105044 . .

F Cabassi , , , M Locatelli . . Computational investigation of simple memetic approaches for continuous global optimization . . Comput Oper Res , , 2016 . . 72 50 - - 70 . . DOI: 10.1016/j.cor.2016.01.015 http://doi.org/10.1016/j.cor.2016.01.015 . .

CK Chak , , , G Feng . . Accelerated genetic algorithms: combined with local search techniques for fast and accurate global search . . Proc IEEE Int Conf on Evolutionary Computation , , 1995 . . p. 378 - - 383 . . DOI: 10.1109/ICEC.1995.489177 http://doi.org/10.1109/ICEC.1995.489177 . .

P Chandler , , , S Rasmussen , , , M Pachter . . UAV cooperative path planning . . Proc AIAA Guidance, Navigation, and Control Conf and Exhibit , , 2000 . . p. 1 - - 11 . . DOI: 10.2514/6.2000-4370 http://doi.org/10.2514/6.2000-4370 . .

ZN Dong , , , ZJ Chen , , , R Zhou , , , 等 . . 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 , , 2011 . . p. 1140 - - 1145 . . DOI: 10.1109/ICIEA.2011.5975758 http://doi.org/10.1109/ICIEA.2011.5975758 . .

YC Du , , , MX Zhang , , , HF Ling , , , 等 . . Evolutionary planning of multi-UAV search for missing tourists . . IEEE Access , , 2019 . . 7 73480 - - 73492 . . DOI: 10.1109/ACCESS.2019.2920623 http://doi.org/10.1109/ACCESS.2019.2920623 . .

HB Duan , , , P Li . . Bio-inspired Computation in Unmanned Aerial Vehicles , , : : Berlin, Heidelberg Springer , , 2014 . . DOI: 10.1007/978-3-642-41196-0 http://doi.org/10.1007/978-3-642-41196-0 . .

AE Eiben , , , SK Smit . . Parameter tuning for configuring and analyzing evolutionary algorithms . . Swarm Evol Comput , , 2011 . . 1 ( ( 1 ): ): 19 - - 31 . . DOI: 10.1016/j.swevo.2011.02.001 http://doi.org/10.1016/j.swevo.2011.02.001 . .

MA Goodrich , , , BS Morse , , , D Gerhardt , , , 等 . . Supporting wilderness search and rescue using a camera-equipped mini UAV . . J Field Robot , , 2008 . . 25 ( ( 1-2 ): ): 89 - - 110 . . DOI: 10.1002/rob.20226 http://doi.org/10.1002/rob.20226 . .

SR Hansen , , , TW McLain , , , MA Goodrich . . Probabilistic searching using a small unmanned aerial vehicle . . Proc AIAA Infotech@Aerospace Conf and Exhibit , , 2007 . . p. 1 - - 16 . . DOI: 10.2514/6.2007-2740 http://doi.org/10.2514/6.2007-2740 . .

CH Hu , , , Y Xia , , , JG Zhang . . Adaptive operator quantum-behaved pigeon-inspired optimization algorithm with application to UAV path planning . . Algorithms , , 2019 . . 12 ( ( 1 ): ): 3 DOI: 10.3390/a12010003 http://doi.org/10.3390/a12010003 . .

F Hutter , , , HH Hoos , , , K Leyton-Brown , , , 等 . . ParamILS: an automatic algorithm configuration framework . . J Artif Intell Res , , 2009 . . 36 267 - - 306 . . DOI: 10.1613/jair.2861 http://doi.org/10.1613/jair.2861 . .

Y Jin , , , Y Liao , , , AA Minai , , , 等 . . Balancing search and target response in cooperative unmanned aerial vehicle (UAV) teams . . IEEE Trans Syst Man Cybern Part B Cybern , , 2006 . . 36 ( ( 3 ): ): 571 - - 587 . . DOI: 10.1109/TSMCB.2005.861881 http://doi.org/10.1109/TSMCB.2005.861881 . .

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

N Krasnogor , , , J Smith . . A tutorial for competent memetic algorithms: model, taxonomy, and design issues . . IEEE Trans Evol Comput , , 2005 . . 9 ( ( 5 ): ): 474 - - 488 . . DOI: 10.1109/TEVC.2005.850260 http://doi.org/10.1109/TEVC.2005.850260 . .

XJ Lai , , , JK Hao . . A tabu search based memetic algorithm for the max-mean dispersion problem . . Comput Oper Res , , 2016 . . 72 118 - - 127 . . DOI: 10.1016/j.cor.2016.02.016 http://doi.org/10.1016/j.cor.2016.02.016 . .

W Li , , , BW Yang , , , GH Song , , , 等 . . Dynamic value iteration networks for the planning of rapidly changing UAV swarms . . Front Inform Technol Electron Eng , , 2021 . . 22 ( ( 5 ): ): 687 - - 696 . . DOI: 10.1631/FITEE.1900712 http://doi.org/10.1631/FITEE.1900712 . .

J Lin . . Backtracking search based hyper-heuristic for the flexible job-shop scheduling problem with fuzzy processing time . . Eng Appl Artif Intell , , 2019 . . 77 186 - - 196 . . DOI: 10.1016/j.engappai.2018.10.008 http://doi.org/10.1016/j.engappai.2018.10.008 . .

L Lin , , , MA Goodrich . . UAV intelligent path planning for wilderness search and rescue . . Proc IEEE/RSJ Int Conf on Intelligent Robots and Systems , , 2009 . . p. 709 - - 714 . . DOI: 10.1109/IROS.2009.5354455 http://doi.org/10.1109/IROS.2009.5354455 . .

M López-Ibáñez , , , J Dubois-Lacoste , , , L Pérez Cáceres , , , 等 . . The irace package: iterated racing for automatic algorithm configuration . . Oper Res Persp , , 2016 . . 3 43 - - 58 . . DOI: 10.1016/j.orp.2016.09.002 http://doi.org/10.1016/j.orp.2016.09.002 . .

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

P Moscato , , , C Cotta . . A gentle introduction to memetic algorithms . . In: Glover F, Kochenberger GA (Eds. ), Handbook of Metaheuristics. Springer, Boston, USA , , 2003 . . p. 105 - - 144 . . DOI: 10.1007/0-306-48056-5_5 http://doi.org/10.1007/0-306-48056-5_5 . .

RR Murphy , , , S Tadokoro , , , D Nardi , , , 等 . . Search and rescue robotics . . In: Siciliano B, Khatib O (Eds. ), Springer Handbook of Robotics. Springer, Berlin, Heidelberg , , 2008 . . p. 1151 - - 1173 . . DOI: 10.1007/978-3-540-30301-5_51 http://doi.org/10.1007/978-3-540-30301-5_51 . .

IK Nikolos , , , ES Zografos , , , AN Brintaki . . UAV path planning using evolutionary algorithms . . In: Chahl JS, Jain LC, Mizutani A, et al. (Eds. ), Innovations in Intelligent Machines 1. Springer, Berlin, Heidelberg , , 2007 . . p. 77 - - 111 . . DOI: 10.1007/978-3-540-72696-8_4 http://doi.org/10.1007/978-3-540-72696-8_4 . .

YS Ong , , , MH Lim , , , N Zhu , , , 等 . . Classification of adaptive memetic algorithms: a comparative study . . IEEE Trans Syst Man Cybern Part B Cybern , , 2006 . . 36 ( ( 1 ): ): 141 - - 152 . . DOI: 10.1109/TSMCB.2005.856143 http://doi.org/10.1109/TSMCB.2005.856143 . .

E Özcan , , , JH Drake , , , C Altıntaş , , , 等 . . A self-adaptive Multimeme Memetic Algorithm co-evolving utility scores to control genetic operators and their parameter settings . . Appl Soft Comput , , 2016 . . 49 81 - - 93 . . DOI: 10.1016/j.asoc.2016.07.032 http://doi.org/10.1016/j.asoc.2016.07.032 . .

MD Phung , , , QP Ha . . Safety-enhanced UAV path planning with spherical vector-based particle swarm optimization . . Appl Soft Comput , , 2021 . . 107 107376 DOI: 10.1016/j.asoc.2021.107376 http://doi.org/10.1016/j.asoc.2021.107376 . .

YT Qi , , , ZT Hou , , , H Li , , , 等 . . A decomposition based memetic algorithm for multi-objective vehicle routing problem with time windows . . Comput Oper Res , , 2015 . . 62 61 - - 77 . . DOI: 10.1016/j.cor.2015.04.009 http://doi.org/10.1016/j.cor.2015.04.009 . .

AK Qin , , , VL Huang , , , PN Suganthan . . Differential evolution algorithm with strategy adaptation for global numerical optimization . . IEEE Trans Evol Comput , , 2009 . . 13 ( ( 2 ): ): 398 - - 417 . . DOI: 10.1109/TEVC.2008.927706 http://doi.org/10.1109/TEVC.2008.927706 . .

S Ragi , , , EKP Chong . . UAV path planning in a dynamic environment via partially observable Markov decision process . . IEEE Trans Aerosp Electron Syst , , 2013 . . 49 ( ( 4 ): ): 2397 - - 2412 . . DOI: 10.1109/TAES.2013.6621824 http://doi.org/10.1109/TAES.2013.6621824 . .

WY Ruan , , , HB Duan . . Multi-UAV obstacle avoidance control via multi-objective social learning pigeon-inspired optimization . . Front Inform Technol Electron Eng , , 2020 . . 21 ( ( 5 ): ): 740 - - 748 . . DOI: 10.1631/FITEE.2000066 http://doi.org/10.1631/FITEE.2000066 . .

A Ryan , , , JK Hedrick . . A mode-switching path planner for UAV-assisted search and rescue . . Proc 44 th IEEE Conf on Decision and Control , , 2005 . . p. 1471 - - 1476 . . DOI: 10.1109/CDC.2005.1582366 http://doi.org/10.1109/CDC.2005.1582366 . .

WG Sheng , , , SY Chen , , , MM Sheng , , , 等 . . Adaptive multi-subpopulation competition and multiniche crowding-based memetic algorithm for automatic data clustering . . IEEE Trans Evol Comput , , 2016 . . 20 ( ( 6 ): ): 838 - - 858 . . DOI: 10.1109/TEVC.2016.2524555 http://doi.org/10.1109/TEVC.2016.2524555 . .

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

J Tisdale , , , Z Kim , , , JK Hedrick . . Autonomous UAV path planning and estimation . . IEEE Robot Autom Mag , , 2009 . . 16 ( ( 2 ): ): 35 - - 42 . . DOI: 10.1109/MRA.2009.932529 http://doi.org/10.1109/MRA.2009.932529 . .

JA Tomlin . . Technical note—an improved branch-and-bound method for integer programming . . Oper Res , , 1971 . . 19 ( ( 4 ): ): 1070 - - 1075 . . DOI: 10.1287/opre.19.4.1070 http://doi.org/10.1287/opre.19.4.1070 . .

A Turky , , , NR Sabar , , , S Dunstall , , , 等 . . Hyper-heuristic local search for combinatorial optimisation problems . . Knowl-Based Syst , , 2020 . . 205 106264 DOI: 10.1016/j.knosys.2020.106264 http://doi.org/10.1016/j.knosys.2020.106264 . .

WH van Willigen , , , MC Schut , , , AE Eiben , , , 等 . . Online adaptation of path formation in UAV search-and-identify missions . . Proc Int Conf on Adaptive and Natural Computing Algorithms , , 2011 . . p.186 - - 195 . . DOI: 10.1007/978-3-642-20267-4_20 http://doi.org/10.1007/978-3-642-20267-4_20 . .

T Volgenant , , , R Jonker . . A branch and bound algorithm for the symmetric traveling salesman problem based on the 1-tree relaxation . . Eur J Oper Res , , 1982 . . 9 ( ( 1 ): ): 83 - - 89 . . DOI: 10.1016/0377-2217(82)90015-7 http://doi.org/10.1016/0377-2217(82)90015-7 . .

S Waharte , , , N Trigoni . . Supporting search and rescue operations with UAVs . . Proc Int Conf on Emerging Security Technologies , , 2010 . . p.142 - - 147 . . DOI: 10.1109/EST.2010.31 http://doi.org/10.1109/EST.2010.31 . .

S Waharte , , , A Symington , , , N Trigoni . . Probabilistic search with agile UAVs . . Proc IEEE Int Conf on Robotics and Automation , , 2010 . . p.2840 - - 2845 . . DOI: 10.1109/ROBOT.2010.5509962 http://doi.org/10.1109/ROBOT.2010.5509962 . .

XP Wang , , , LX Tang . . A machine-learning based memetic algorithm for the multi-objective permutation flowshop scheduling problem . . Comput Oper Res , , 2017 . . 79 60 - - 77 . . DOI: 10.1016/j.cor.2016.10.003 http://doi.org/10.1016/j.cor.2016.10.003 . .

Y Wang , , , MX Zhang , , , YJ Zheng . . A hyper-heuristic method for UAV search planning . . Proc Int Conf on Swarm Intelligence , , 2017 . . p.454 - - 464 . . DOI: 10.1007/978-3-319-61833-3_48 http://doi.org/10.1007/978-3-319-61833-3_48 . .

XB Yu , , , CL Li , , , GG Yen . . A knee-guided differential evolution algorithm for unmanned aerial vehicle path planning in disaster management . . Appl Soft Comput , , 2021 . . 98 106857 DOI: 10.1016/j.asoc.2020.106857 http://doi.org/10.1016/j.asoc.2020.106857 . .

B Zhang , , , HB Duan . . Predator-prey pigeon-inspired optimization for UAV three-dimensional path planning . . Proc Int Conf on Swarm Intelligence , , 2014 . . p.96 - - 105 . . DOI: 10.1007/978-3-319-11897-0_12 http://doi.org/10.1007/978-3-319-11897-0_12 . .

H Zhang , , , B Xin , , , LH Dou , , , 等 . . A review of cooperative path planning of an unmanned aerial vehicle group . . Front Inform Technol Electron Eng , , 2020 . . 21 ( ( 12 ): ): 1671 - - 1694 . . DOI: 10.1631/FITEE.2000228 http://doi.org/10.1631/FITEE.2000228 . .

YZ Zhang , , , Y Mei , , , K Tang , , , 等 . . Memetic algorithm with route decomposing for periodic capacitated arc routing problem . . Appl Soft Comput , , 2017 . . 52 1130 - - 1142 . . DOI: 10.1016/j.asoc.2016.09.017 http://doi.org/10.1016/j.asoc.2016.09.017 . .

YJ Zheng . . Water wave optimization: a new nature-inspired metaheuristic . . Comput Oper Res , , 2015 . . 55 1 - - 11 . . DOI: 10.1016/j.cor.2014.10.008 http://doi.org/10.1016/j.cor.2014.10.008 . .

YJ Zheng , , , HF Ling , , , JY Xue . . Ecogeography-based optimization: enhancing biogeography-based optimization with ecogeographic barriers and differentiations . . Comput Oper Res , , 2014 . . 50 115 - - 127 . . DOI: 10.1016/j.cor.2014.04.013 http://doi.org/10.1016/j.cor.2014.04.013 . .

YJ Zheng , , , MX Zhang , , , HF Ling , , , 等 . . Emergency railway transportation planning using a hyper-heuristic approach . . IEEE Trans Intell Transp Syst , , 2015 . . 16 ( ( 1 ): ): 321 - - 329 . . DOI: 10.1109/TITS.2014.2331239 http://doi.org/10.1109/TITS.2014.2331239 . .

YJ Zheng , , , YC Du , , , HF Ling , , , 等 . . Evolutionary collaborative human-UAV search for escaped criminals . . IEEE Trans Evol Comput , , 2020 . . 24 ( ( 2 ): ): 217 - - 231 . . DOI: 10.1109/TEVC.2019.2925175 http://doi.org/10.1109/TEVC.2019.2925175 . .

YJ Zheng , , , YC Du , , , ZL Su , , , 等 . . Evolutionary human-UAV cooperation for transmission network restoration . . IEEE Trans Ind Inform , , 2021 . . 17 ( ( 3 ): ): 1648 - - 1657 . . DOI: 10.1109/TⅡ.2020.3003903 http://doi.org/10.1109/TⅡ.2020.3003903 . .

R Zhou , , , Y Feng , , , B Di , , , 等 . . Multi-UAV cooperative target tracking with bounded noise for connectivity preservation . . Front Inform Technol Electron Eng , , 2020 . . 21 ( ( 10 ): ): 1494 - - 1503 . . DOI: 10.1631/FITEE.1900617 http://doi.org/10.1631/FITEE.1900617 . .

Views

173

Downloads

CSCD

Alert me when the article has been cited

Submit

Tools

Publicity Resources

A UAV-enabled mobile edge computing paradigm for dependent tasks based on a computing power pool

Distributed game strategy for unmanned aerial vehicle formation with external disturbances and obstacles

Motor speed estimation and failure detection of a small UAV using density of maxima

Multi-UAV obstacle avoidance control via multi-objective social learning pigeon-inspired optimization

Related Author

Xiaonan CUI

Wei LI

Hao YUAN

Ming HE

Yan GUO

Xuebin LAI

Yang YUAN

Haibin DUAN

Related Institution

School of Communications Engineering, Army Engineering University of PLA

School of Command and Control Engineering, Army Engineering University of PLA

State Key Laboratory of Virtual Reality Technology and Systems, School of Autonomous Science and Electrical Engineering, Beihang University

School of Mechanical Engineering & Automation, Beihang University

Peng Cheng Laboratory

Chat

Address：Zhejiang University Press, 148 Tianmushan Road, Hangzhou, China Postal code：310028
Tel：+86-571-88273162 Email：fitee@zju.edu.cn
It is recommended to read the content of this site in Chrome&IE9+. Please switch to extreme mode in browser 360.
Cookies We use cookies to help provide and enhance our service and tailor content. By continuing, you agree to the use of cookies.

⁰