A memetic algorithm for path planning of curvature-constrained UAVs performing surveillance of multiple ground targets

作     者：Zhang Xing Chen Jie Xin Bin Peng Zhihong 

作者机构：School of Automation Beijing Institute of Technology State Key Laboratory of Intelligent Control and Decision of Complex Systems 

出 版 物：《Chinese Journal of Aeronautics》 (中国航空学报（英文版）)

年 卷 期：2014年第27卷第3期

页      面：622-633页

核心收录：

学科分类：08[工学] 082503[工学-航空宇航制造工程] 0802[工学-机械工程] 0825[工学-航空宇航科学与技术] 0801[工学-力学（可授工学、理学学位）] 

基　　金：co-supported by the Foundation for Innovative Research Groups of the National Natural Science Foundation of China (No. 61321002) the Projects of Major International (Regional) Joint Research Program NSFC (No. 61120106010) Beijing Education Committee Cooperation Building Foundation Project, the National Natural Science Foundation of China (No. 61304215) Beijing Outstanding Ph.D. Program Mentor (No. 20131000704) 

主　　题：Approximate gradient Dubins traveling salesmanproblem with neighborhood Local search Memetic algorithm Unmanned aerial vehicles 

摘      要：The problem of generating optimal paths for curvature-constrained unmanned aerial vehicles （UAVs） performing surveillance of multiple ground targets is addressed in this paper. UAVs are modeled as Dubins vehicles so that the constraints of UAVs＇ minimal turning radius can be taken into account. In view of the effective surveillance range of the sensors equipped on UAVs, the problem is formulated as a Dubins traveling salesman problem with neighborhood （DTSPN）. Considering its prohibitively high computational complexity, the Dubins paths in the sense of terminal heading relaxation are introduced to simplify the calculation of the Dubins distance, and a boundary-based encoding scheme is proposed to determine the visiting point of every target neighborhood. Then, an evolutionary algorithm is used to derive the optimal Dubins tour. To further enhance the quality of the solutions, a local search strategy based on approximate gradient is employed to improve the visiting points of target neighborhoods. Finally, by a minor modification to the individual encoding, the algorithm is easily extended to deal with other two more sophisticated DTSPN variants （multi-UAV scenario and multiple groups of targets scenario）. The performance of the algorithm is demonstrated through comparative experiments with other two state-of-the-art DTSPN algorithms identified in literature. Numerical simulations exhibit that the algorithm proposed in this paper can find high-quality solutions to the DTSPN with lower computational cost and produce significantly improved performance over the other algorithms.