This paper proposes a new method for the shortest path planning of UAV coverage searching in irregular regions. First, the mission area was dispersed with rasterisation by using the detection range of airborne sensor, and the path planning problem of area coverage searching was translated into a travelling salesman problem that can be solved. Then, the genetic algorithm was improved by using the multi-group parallel algorithm frame and elitist strategy, and the fitness function of the algorithm was redesigned. The parallel elitist genetic algorithm was put forward to solve the TSP problem. Experimental results show that the proposed method is applicable to the path planning problem of UAV area coverage searching. The proposed PEGA algorithm had a high convergence speed and the optimal solution had satisfactory quality. Improving the fitness function reduced the case of long distance between two points connected, apparently optimizing the path planning results.
ZHAO Chenhao
,
LIU Yonglan
,
ZHAO Jie
. Path Planning Method of UAV Area Coverage Searching Based on PEGA[J]. Science & Technology Review, 2014
, 32(28/29)
: 85
-90
.
DOI: 10.3981/j.issn.1000-7857.2014.28/29.012
[1] 曾维彪, 蔡子兴. 一种改进的全区域覆盖算法[J]. 计算机工程, 2008,34(21): 193-198.Zeng Weibiao, Cai Zixing. Improved complete coverage algorithm[J].Computer Engineering, 2008, 34(21): 193-198.
[2] Hutchison M G. A method for estimating range requirements of tacticalreconnaissance UAVs[C]. AIAA's 1st Technical Conference andWorkshop on Unmanned Aerospace Vehicles, Portsmouth, Virginia:AIAA, 2002.
[3] Koenig S, Szymanskj B, Liu Y. Efficient and inefficient ant coveragemethods[J]. Annals of Mathematics and Artificial Intelligence, 2001, 3(1-4): 41-76.
[4] Payton D, Daily M, Estkowski R, et al. Pheromone robotics[J]. AutonomousRobots, 2001, 11(3): 319-324.
[5] 彭辉, 沈林成, 霍霄华. 多UAV协同区域覆盖搜索研究[J]. 系统仿真学报, 2007, 19(11): 2472-2476.Peng Hui, Shen Lincheng, Huo Xiaohua. Research on multiple UAVcooperative area coverage searching[J]. Journal of System Simulation,2007, 19(11): 2472-2476.
[6] 龙国庆, 祝小平, 董世友. 多UAV协同区域覆盖侦察方法[J]. 火力与指挥控制, 2011, 36(10): 49-52.Long Guoqing, Zhu Xiaoping, Dong Shiyou. A study on the method ofcooperative area coverage reconnaissance of multi-UAV[J]. Fire Control& Command Control, 2011, 36(10): 49-52.
[7] Huang W H. Optimal line-sweep-based decompositions for coveragealgorithms [C]. IEEE International Conference on Robotics andAutomation, Seoul, Korea, May 21-26, 2001.
[8] 吕鹏举, 原杰, 吕菁华. 基于模拟退火算法的全国最优旅行方案[J]. 现代电子技术, 2011, 34(2): 32-34.Lü Pengjü, Yuan Jie, Lü Jinghua. Optimal nationwide traveling schemebased on simulated annealing algorithm[J]. Modern ElectronicsTechnique, 2011, 34(2): 32-34.
[9] 吴华锋, 陈信强, 毛奇凰, 等. 基于自然选择策略的蚁群算法求解TSP问题[J]. 通信学报, 2013, 34(4): 165-169.Wu Huafeng, Chen Xinqiang, Mao Qihuang, et al. Improved ant colonyalgorithm based on natural selection strategy for solving TSP problem[J]. Journal on Communications, 2013, 34(4): 165-169.
[10] 梅觅, 薛惠锋, 谷雨. 旅行商问题的改进差分进化方法[J]. 信息技术,2011(2): 20-23.Mei Mi, Xue Huifeng, Gu Yu. An improved differential evolutionalgorithm for TSP[J]. Information Technology, 2011(2): 20-23.
[11] 刘朝华, 张英杰, 吴建辉. 一种求解TSP问题的改进克隆选择算法[J]. 系统仿真学报, 2010, 22(7): 1627-1631.Liu Zhaohua, Zhang Yingjie, Wu Jianhui. Novel immune clonalselection for TSP solution[J]. Journal of System Simulation, 2010, 22(7): 1627-1631.
[12] 刘雁兵, 刘付显. 基于遗传算法的TSP问题求解与仿真[J]. 电光与控制, 2007, 14(4): 154-158.Liu Yanbing, Liu Fuxian. Solution and simulation of TSP problembased on genetic algorithm[J]. Electronic Optice & Control, 2007, 14(4): 154-158.
[13] 韩凤娇. 一种基于遗传算法的求解TSP问题的优化算法[J]. 网络安全技术与应用, 2012(7): 36-39.Han Fengjiao. A optimization method based on genetic algorithm forsolving TSP[J]. Network Security Technology & Application, 2012(7):36-39.
[14] 刘青凤, 李敏. 基于遗传算法的TSP问题优化求解[J]. 计算机与现代化, 2008(2): 43-56.Liu Qingfeng, Li Min. Optimizing solution for solving TSP problembased on genetic algorithm[J]. Computer & Modernization, 2008(2): 43-56.
[15] 邓长春, 朱儒明, 李泳霞, 等. 一种求解TSP问题的多种群并行遗传算法[J]. 计算机仿真, 2008, 25(9): 187-190.Deng Changchun, Zhu Ruming, Li Yongxia, et al. A multi-groupparallel genetic algorithm for TSP[J]. Computer Simulation, 2008, 25(9): 187-190.
[16] De Jong K A. An analysis of the behavior of a class of geneticadaptive systems[D]. Ann Arbor: University of Michigan, 1975.
[17] 史峰, 王辉, 郁磊, 等. MATLAB智能算法30个案例分析[M]. 北京:北京航空航天大学出版社, 2011.Shi Feng, Wang Hui, Yu Lei, et al. 30 case analyse of MATLABintelligent algorithm[M]. Beijing: Beihang University Press, 2011.
[18] 储理才. 基于MATLAB的遗传算法程序设计及TSP问题求解[J]. 集美大学学报: 自然科学版, 2001, 6(1): 14-19.Chu Licai. Genetic algorithm programming based on MATLAB andTSP solving[J]. Journal of Jimei University: Natural Science Edition,2001, 6(1): 14-19.
