多无人机飞行路径自动规划算法研究

马传焱

(中国人民解放军63961部队，北京100012)

0 引言

随着无人机技术的发展，作战任务应用领域不断扩大，无人机作战样式也由单机工作，朝着一站多机、多站多机的网络式协同作战方式发展。任务的增加、多机协同战术应用的变化，迫切需要对无人机任务实行有效组织与科学管理。基于此，面向多无人机作战的任务规划重要性凸显，其能力要求也越来越高。

美国是世界上最先发展任务规划技术的国家，典型的联合任务规划系统(Joint Mission Planning System，JMPS)主要用来制定飞行威胁分析、飞机航路和攻击协调等航空任务计划;使用灵活的集成模型，允许用户根据需要进行系统配置和开发。我国的任务规划研究才刚刚开始，许多技术尚处于探索阶段。在无人机自动任务规划方面，主要针对单机的路径规划，对多机协同、任务分配、载荷使用和战术运用等方面较少涉及，尚不具备执行复杂战术任务规划的能力。

简单说来，无人机路径规划的目的是寻找最佳飞行航线，确定该航线上对载荷设备的控制策略，使无人机在确保飞行安全的前提下，发挥载荷设备的作用，完成各项任务。从多无人机路径规划问题抽象出的数学物理模型，实质上属于协调控制问题。随着战场环境、武器系统、作战样式复杂度的增加以及对无人机性能和多任务要求的提高，无人机控制难度和效果之间的矛盾更加突出，这些实战要求用传统的人员智力无法完成，需要借助现代智能计算的优势，从作战任务、指挥决策、环境影响、飞行控制和无人机能力等方面，优化出多种满足不同作战目的的解决方案。

常用的路径规划算法有遗传算法［1-5］、Dijkstra求最短路径法［6，7］、Voronoi图搜索法［8］(以下简称“V 图”)、A* 算法［9，10］、启发式搜索法［11］和神经网络［12］等多种方法。

本文给出了基于V图的多无人机飞行路径自动规划算法，对传统V图进行了改进，并对应用中的威胁源建模、估价函数的组织及航路优化等技术进行了说明，为多无人机协同航路自动生成过程提供参考。

1 威胁建模

威胁建模(Threat Modeling)是指对地面和空中各种不同类型的固定障碍物或具有辐射覆盖特征的威胁源进行形式化描述，以便于无人机在飞行过程中进行威胁规避。主要包括探测性威胁和杀伤性威胁。

1．1 探测性威胁建模

探测性威胁主要是探测雷达对无人机产生的威胁，其威胁区域投影在垂直面上为一个扇形区域，最大威胁半径为Rmax，张角为α，雷达水平最大威胁距离Rm=Rmaxsinα，无人机与雷达之间的水平距离为R，威胁系数为k，雷达的探测概率为:

1．2 杀伤性威胁建模

杀伤性威胁主要来源为各种地空导弹和高炮等，常用的一种模型认为威胁源作用范围内的无人机所受威胁程度与其到威胁源的距离成泊松分布关系，即无人机距离威胁源越远，所受威胁度越小，反之亦然。具体计算方法如下:

2 算法描述

2．1 V图的建立

从数学上理解，平面N个点中两邻点直线的垂直平分线连接组成连续多边形，多个多边形拼接组成V图。赋予其物理意义时，取威胁源为中心点并视作生长目标，按威胁度将垂直平分线向四周扩张直到相遇，构造出威胁分布的V图具有这一性质:相邻2个威胁源生长目标的公共Voronoi边是其间威胁度最小的位置。根据式(1)和式(2)威胁度计算模型来看，简单依据欧式、大圆或等角距离所构建的普通V图不足以具备这一性质，需根据各威胁源的威胁度等价关系，确定其在距离意义上的相对扩展速度来建立扩展V图。当威胁源同类型时，仅存在战技指标(威胁强度)上的差别，根据无人机与威胁源的距离—威胁度—相对扩张速度的方式即可计算。当存在探测性和杀伤性2种不同类型的威胁源时，因威胁度性质不同，无法直接比较大小。将威胁度转换为距离来确定相对扩张速度的方式已不可行，需依据专家知识确定威胁等价系数，建立威胁之间的等价关系程度，然后在V图中求解。

如图 1所示，图 1(a)为数学意义上的 V图，图1(b)为考虑威胁类型和强度差别建立等价关系，确定威胁源生长目标的相对扩张速度所建立V图。其中，威胁源1是威胁源2、3、4和5扩张速度的1.5倍。比较图1(a)和图1(b)可以看出，由于威胁源1的扩张速度快，V图的边明显远离威胁源1而靠近威胁源2和3。当以扩展V图的边作为无人机路径段时，其威胁度是对各类威胁源作用的综合度量，可更真实反应战场中威胁源对无人机任务的影响。

图1 2类V图的比较

2．2 基于V图的多无人机路径表示

基于构建的战场环境V图，无人机的飞行路径可以表示为:V图的顶点为路径中途点，边为路径段，从无人机起飞点到目标的V图边的组合构成多条路径。依该方法分别为各个无人机选择，可构成多无人机协同初始路径图，如图2所示，粗实线表示无人机的飞行路径。

图2 基于V图的多无人机路径示意

2．3 基于V图的多无人机路径规划算法

V图中第i条边的权值采用以下代价函数计算:

式中，Ji为第i条边的权值;Jt，i为第i条边的威胁代价;Jf，i为第i条边的油耗代价。综合考虑威胁及油耗对航路影响引入系数k，其值由航路制订者根据实践经验和按作战要求设定。

威胁代价与无人机的雷达可探测性指标和杀伤性威胁参数指标相关联。当无人机沿V图第i条边飞行时，所受威胁代价可以理解为该条边上所有点的威胁代价积分。近似地在每条边上平均采样若干点，计算所有威胁对各点的影响，积分求和后获得近似每条边的威胁代价。

式中，N为探测性威胁的数目;M为火力威胁的数目;d代表第i条边上的采样点到任意一个威胁点的距离。

3 仿真结果

仿真实例中，整个战场上分布24个作用范围不同的威胁，要求为UAV规划出当前点到目标点的初始路径。

设置规划参数K=0.5，算法仿真结果如图3(a)所示，从图3(a)中可以看出，路径完全避开了威胁区，并选择了代价最小的路径。且由于采用Dijkstra最小路径搜索方法获得的路径，因此获得的是确定的解。

下面验证不同的规划参数对于规划结果的影响。K越大越考虑燃油消耗对规划结果的影响，K越小则更倾向考虑威胁接近代价。调整参数K=0，初始路径规划结果如图3(b)所示。从规划结果可以看出，图3(b)为了尽量规避威胁，需要付出较多的燃油代价。

经过1次优化后，路径在避开威胁区的前提下被尽量拉直;经过2次优化后，消除了航路上的角度较小的转弯，规划出的路径更符合无人机的机动特性，如图4所示。

当无人机和目标数量均增加到16个，在已经进行了任务分配的基础之上，同时生成多架无人机的飞行路径，如图5所示。

图3 基于V图的路径规划

图4 路径规划的优化

图5 多无人机路径自动生成

4 结束语

上述的路径自动规划算法可以应用在2种典型的多无人机任务(协同攻击和协同侦察)。仿真结果表明，本文基于V图解决了多无人机航路规划问题中的威胁源建模、估价函数的建立以及航路优化算法等方面问题，给出的方法能够在保证算法有效性的基础上，减小了搜索空间，提高了规划的实时性。算法兼顾了生存能力、飞行距离和人为决策等多个约束条件，具有较好的鲁棒性。

［1］ 郑昌文，李 磊，徐帆江，等.基于进化计算的无人飞行器多航迹规划［J］.宇航学报，2005，26(2):224-227.

［2］ 罗亚中，唐国金，梁彦刚.基于分解策略的SSO发射轨道遗 传 全 局 优 化 设 计［J］.航 空 学 报，2004，25(5):443-446.

［3］ 张 旺，王黎莉，伍 洋.基于遗传算法的阵列天线综合及分析［J］.无线电通信技术，2011，37(4):28-30.

［4］ 梁晓辉，吴 威，赵沁平.大规模真实地形数据中的全局路径规划方法——基于遗传算法的研究［J］.计算机研究与发展，2003，39(3):301-306.

［5］ 吴晓涛，孙增圻.用遗传算法进行路径规划［J］.清华大学学报(自然科学版)，1995，35(5):14-19.

［6］ 胡晓磊，胡朝晖，江洋溢.基于Dijkstra算法的水平航迹规划［J］.火力与指挥控制，2004，29(4):86-92.

［7］ 马云红，周德云.飞行器低空突防威胁建模与航迹优化算法［J］.火力与指挥控制，2004，29(5):31-37.

［8］ 赵文婷，彭俊毅.基于VORONOI图的无人机航迹规划［J］.系统仿真学报，2006，18(增 2):159-162.

［9］ 周成平，陈前洋，秦 筱.基于稀疏A*算法的三维航迹并行规划算法［J］.华中科技大学学报(自然科学版)，2005，33(5):42-45.

［10］穆中林，鲁 艺，任 波，等.基于改进A*算法的无人机航路规划方法研究［J］.弹箭与制导学报，2007，27(1):297-300.

［11］ IKEDA T，HSU M Y，IMAI M.A Fast Algorithm for Finding Better Routes by AI Search Techniques［C］∥IEEEVehicleNavigation＆InformationSystems Conference Proceedings，1994:291-296.

［12］ ARAÚJO F，RIBEIRO B，RODRIGUES L.A Neural Network for Shortest Path Computation ［J］.IEEE Transactions on Neural Networks，2001，12(5):1 067-1 073.