基于动态规划的无人机协同侦察路线规划  

Multi-UAV Route Optimization Based on Dynamic Programming

作　　者：童玮[1] 李业军[2] 沈焕生[1] 郑翔[1] 蒋海霞[1] TONG Wei LI Ye-jun SHEN Huan-sheng ZHENG Xiang JIANG Hai-xia(College of Communications Engineering, PLAUST, Nanjing 210007, China Xi＇an Communication Institute, Xi＇an 710106, China)

机构地区：[1]解放军理工大学通信工程学院,江苏南京210007 [2]西安通信学院,陕西西安710106

出　　处：《军事通信技术》2016年第3期11-14,共4页Journal of Military Communications Technology

基　　金：江苏省自然科学基金资助项目(BK20140065)

摘　　要：多无人机协同侦察路线规划要求多架无人机协作对目标地点进行遍历侦察,并且需同时满足不同目标的侦察要求。这一问题在简化意义下可以归约为以下两种组合优化里的经典问题:多旅行商问题与多配送中心车辆调度问题,因而该问题属于NP难问题。文章在相关假设情形下建立了带时间约束的整数线性规划模型。由于经典算法(例如分支定界法)难以直接求解该类复杂的组合优化问题,故采用动态规划的思想,分阶段利用启发式算法,最后求得问题的较优解。Multi-unmanned aerial vehicle cooperative reconnaissance mission planning requires multi-UAV cooperative reconnaissance of the target location,and needs to meet the requirements of different target reconnaissance.In a simplified sense,this problem can be reduced to two classic combinatorial optimization problems：multiple traveling salesman problem and multiple depots vehicle routing problem.Thus the problem is NP-hard problem.In this paper,based on some relevant assumptions,the problem was reformulated as an integer linear programming model with the time constraints.Since the classical algorithms（such as branch and bound method）were almost unable to directly solve such a complex combinatorial optimization problem,the ideal of dynamic programming was used to heuristically slove it in stages and a suboptimal solution was obtained finally.

关 键 词：无人机 协同任务分配 动态规划 

分 类 号：O221.6[理学—运筹学与控制论]