为解决不规则区域内UAV 最短覆盖搜索路径的规划问题,提出一种新的求解方法。首先,利用机载传感器探测范围对任务区域进行栅格化离散,将区域覆盖搜索路径规划问题转化为一个可求解的旅行商问题;然后,利用多种群并行算法框架及精英策略对遗传算法进行改进并重新设计算法的适应度函数,提出一种并行精英遗传算法用于问题的求解。实验仿真结果表明,提出的求解方法对于UAV 区域覆盖搜索路径规划问题具有较好的适用性;提出的PEGA 算法收敛速度快,得出的最优解质量较高;通过改进适应度函数能够有效减少远距离两点相连的情况,对于覆盖搜索路径规划结果产生了明显的优化效果。
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.
[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.
