改进型Voronoi图和动态权值A*算法的无人机航迹规划

张淘沙，鲁艺，张亮，吕跃

（空军工程大学航空航天工程学院，西安710038）

改进型Voronoi图和动态权值A*算法的无人机航迹规划

张淘沙，鲁艺，张亮，吕跃

（空军工程大学航空航天工程学院，西安710038）

针对实际作战环境中的不同威胁等级和不同威胁实体的威胁源，提出了改进型的Voronoi图，并建立了基于改进型Voronoi图的航迹规划空间；基于A*算法的估价函数在不同阶段对指标的敏感度不同，在传统的启发式A*搜索算法基础上提出了动态权值A*搜索算法，提高了航迹搜索的效率，实现了航迹搜索过程快速性和准确性的结合。最后通过Matlab仿真计算出由动态权值A*算法得到的最优航迹，并进行了航迹的平滑处理，仿真表明了该方法的可行性。

无人机，航迹规划，改进型Voronoi图，动态权值A*算法，航迹平滑

0　引言

Voronoi图（以下简称V图）作为一种基本的几何结构，以其十分接近于自然现象本质的优点，目前已经被广泛地应用于无人机航迹规划。然而现有的关于V图在无人机航迹规划中的研究应用大多是将不同实体和相同实体不同威胁等级的威胁当作相同实体、相同等级的威胁来处理。A*算法作为一种启发式搜索算法，能较好地满足航迹规划中的各种约束条件，在有限的可选状态中确定一个最优解，并在理论上保证收敛于全局最优解，也已经广泛地应用于无人机航迹规划的研究［1］。但无人机在执行作战任务的过程中，实际作战环境并非总是和实际想象的完全相符合，为实现无人机航迹规划快速性和准确性的结合，需要对传统的A*算法做以改进。本文通过分析传统V图方法生成规划空间的局限性，建立了基于不同威胁实体和威胁等级的规划空间，采用动态权值A*算法进行航迹寻优，得到全局最优航迹。

1　基于改进型V图的规划空间建模

V图生成规划空间的方法是依据已知的威胁分布，以威胁源为中心，利用矢量生成法生成规划空间，得到初始可行航迹点和航迹段。但这种传统的生成规划空间的方法在实际应用中存在较大的局限性，本文将指出该方法的不足，并对其进行改进，得到基于改进型的V图规划空间模型［2］。

1.1传统V图的局限性

实际的作战环境中，存在不同种类和不同实体的威胁源，其威胁等级大小不同，如图1所示。O1，O2，O3分别为威胁源中心，R1，R2，R3分别为威胁源O1，O2，O3在相同杀伤概率下的杀伤半径，R1=3R2=3R3，CP，BP，AP分别为威胁源中心连线O1O2，O2O3，O1O3的中垂线，相交于P点，按传统V图的生成方法，线段PM，PN，PQ为规划的初始航迹段。但该结果会使航迹段PM，PQ的一部分位于威胁源O1的杀伤半径内，增加了威胁源O1对无人机的杀伤概率。为此本文对V图的生成规划空间的方法做出改进。

图1　传统V图生成的规划空间

1.2改进型V图的规划空间建模

（1）如果威胁源的威胁等级相同，仍按传统V图方法生成规划空间。

（2）如果威胁源的威胁等级不同，将威胁源进行分组，任取3个为一组，如图2所示。

O1，O2，O3分别为威胁源的中心，R1，R2，R3分别其表示威胁等级，且有2R1=3R2=6R3，A、B、C分别为中心连线的比例等分点，具体位置依据威胁源威胁等级确定；点P为A，B，C构成三角形的内心，也是ΔABC的内接圆P的圆心。

图2　不同威胁等级生成的规划空间

这样，对于威胁源O1，O2，O3构成的威胁区域，A，B，C，P为其4个初始航迹点，线段AP，BP和CP为初始航迹段，再将其与相邻威胁源所构成的其他初始航迹段相连，便得到最后的航迹规划空间，称之为“改进型V图”规划空间［3］。

（3）如果威胁源为不同威胁实体，为了规划简便起见，将其看作相同类型威胁处理。如图3所示：威胁区域是由一个雷达威胁源和两个地形威胁源共同组成，杀伤范围仍用杀伤半径R1，R2，R3来表示，且满足2R1=3R2=3R3，图中标识符的含义与图2相同，采用基于改进型V图方法进行规划空间的生成，则线段AP，BP和CP即为初始可行航迹段。

图3　不同实体威胁源生成的规划空间

1.3模拟仿真示意

选取飞行区域为500 km×500 km的高威胁空间，该空间内有两种类型的威胁：一是雷达威胁，威胁值的大小有两种等级，在对无人机80%探测概率下的杀伤半径为100 km和50 km。二是地形威胁，假设也有两种威胁等级，威胁半径分别为50 km和25 km。对于该规划威胁空间，利用基于改进型V图生成规划空间方法，采用Matlab进行分析，得到如图4所示仿真结果。

图4　改进型V图生成的规划空间

这样，就得到改进型的V图的规划空间，再将起始点和目标点与初始规划空间中几个最近的多边形顶点相连，得到了一个从起始点到目标点的有向图，然后便可找出若干条从起始点到达目标点的航迹。

2　航迹性能指标

无人机航迹规划是一个约束条件复杂的多目标规划问题，本文主要考虑无人机的威胁代价和燃油代价［4-5］。

2.1雷达威胁代价

假定无人机具有相同的RCS，则无人机沿着V图每条边的雷达威胁代价是该边的积分。如式（1）：

为了简化计算，将每条边均匀地分为6等分，取其中的3个点L/6，L/2，5L/6来代替整条边的代价，N为雷达的个数，这样第i条边的雷达威胁代价如式（2）［6］：

2.2地形威胁代价

对于地面的山脉、高大建筑物、禁飞区等威胁，将其简化为一系列圆形区域，无人机规避这些区域飞行。假定无人机速度恒定，第i边的地形威胁代价就是无人机飞过该边的燃油代价，燃油代价与路径长短成正比，记为Jfuel，i。

2.3航迹总代价

得到了无人机第i条边的威胁代价和燃油代价之后，便可得到第i条边的总代价，如式（3）：

式（3）中，k为安全系数，若要求无人机安全性最大，则k为0；若要求路径最短，则k为1。

完成航路代价计算后，V图每条边的权值也就是该边的航迹代价，称之为加权V图。在此基础之上，使用相关的航迹搜索算法便可求出无人机的初始航迹［7］。假设该航迹由N段有向加权边组成，则该航路总代价为：

2.4航迹目标隶属度函数

V图的每条边都被赋予威胁代价和燃油代价，但不能简单相加就作为其总代价。因为威胁和燃油代价属于不同的物理量，必须对其进行归一化［8］。对于燃油代价或威胁代价f（x），存在一个最高代价值M和一个最低代价值m，利用式（5）进行归一化，得到目标隶属度函数Af（x）。

则基于目标隶属度函数的航迹性能指标如式（6）所示：

式（6）中：k为安全系数，取值范围为［0，1］，当k取值越大时，表明无人机为减小燃油代价而不惜牺牲威胁代价。k取值越小时，意义相反。

2.5航迹平滑处理

在进行航迹规划时并没有充分考虑无人机的运动学和动力学性能，因此，必须要对最后的航迹规划结果进行平滑处理，以满足无人机的机动约束，形成无人机的可飞航迹。

本文主要考虑无人机的最大法向过载，为此将圆弧拟合思想引入无人机的航迹平滑，利用式（7）对规划的初始航迹进行平滑处理，详见文献［9］。

式（7）中，Vmin为无人机的最小飞行速度，nymax为无人机最大法向过载。

3　基于动态权值的A＊搜索算法

3.1A*搜索算法

A*算法估价函数的一般形式为：f（m）=g（m）+h（m），g（m）为初始节点到当前节点实际付出的代价；h（m）是当前节点m到目标节点的估计代价，体现启发式信息，其形式通常根据问题的特性而定，将h（m）称为启发函数［10-11］。

3.2动态权值A*搜索算法

实际作战环境中，为兼顾航迹搜索过程的快速性和准确性，本文提出动态权值的估价函数［12］，定义为估价函数式：

式（8）中λ是一个正数，其取值范围为［0，1］。

（1）λ=0，意味着搜索过程不依赖任何启发信息，此时算法蜕化成相同代价的搜索，适用于规划空间中待扩展节点规模不大时的情形。

（2）λ为非0的固定正值时，f（m）为常权函数。当λ取值较大时，估价函数过分强调启发式信息，突出搜索过程的深度优先性，减少节点的扩展量，算法的快速性提高，但准确性变差；当λ取值较小时，突出搜索过程的广度优先性，算法的准确性提高，但搜索过程的实时性变差，即λ在不同阶段对两项指标的敏感度不同。

（3）λ为动态值时，通过对搜索初期、后期赋予λ不同的权值，实现了搜索初期要求搜索的快速性，搜索后期要求准确性的目的。

在此，给出深度的定义Mm，是指将整条航迹上的节点按照先后顺序编码，当前节点在整条航迹上的位置就称为当前节点的深度。编码越小，深度越浅；编码越大，深度越深。

选择权值系数λ与当前节点的深度Mm成反比，即：λ=1/Mm。即在深度较浅时，λ值较大，搜索过程以深度优先，注重搜索过程的快速性；随着深度的增加，λ逐渐变小，搜索后期会逐渐以广度优先，提高搜索过程的准确性［12-13］。

4　仿真分析

参数设置：

（1）选取2.3所选取的威胁空间；

（2）假设单部雷达具有如下的性能：对于δ为10 dB·m2的目标，当虚警概率为1.0e-6时，探测概率为80%；

（3）杀伤概率为80%时，不同等级威胁的火力杀伤半径25 km和50 km。依据第2节所建立的性能指标和第3节动态权值A*算法，选取不同燃油系数k和启发式函数的组合。

4.1动态权值系数，分析生成航迹的变化情况

（1）k=0，λ=0，不考虑燃油代价，只考虑威胁代价，搜索过程不依赖任何启发信息，其生成的航迹R1如图5所示。

由图5知：为规避雷达威胁集中的区域，无人机选择最远路径R1，威胁代价最小，燃油代价最大。

图5　k=0，λ=0，时生成的航迹R1

（2）k=0.25，λ=0，考虑25%权重的燃油代价和75%权重的威胁代价，搜索过程不依赖任何启发信息，生成的航迹R2如图6所示。由图6知，此时生成航迹R2向威胁比较集中的区域靠近，生成的航迹R2比航迹R1的距离略短，但仍消耗了较大的燃油代价。

图6　k=0.25，λ=0，时生成的航迹R2

（3）k=0.5，λ=0，考虑50%权重的燃油代价和50%权重的威胁代价，搜索过程中不依赖于任何启发信息，生成的航迹R3如图7所示。由图7知，此时航迹R3由原来威胁稀疏的区域移动到地面威胁相对集中的区域，燃油代价明显减少，威胁代价明显的增加。

（4）k=1，λ=0，只考虑燃油代价，不考虑威胁代价。航迹搜索过程不依赖任何启发信息，生成的航迹R4如图8所示，由该图可知若只考虑燃油代价，不考虑威胁代价，使得生成航迹进一步移动到R4，此时燃油代价最小，但威胁代价达到最大。

图7　k=0.5，λ=0，时生成的航迹R3

图8　k=1，λ=0，时生成的航迹R4

以上生成的航迹R1，R2，R3和R4，显示了航迹从威胁稀疏区域向最集中的区域移动的过程，航迹规划的结果是合理的，显示了权值变化对航迹规划结果的影响。

4.2燃油系数k=0.5生成航迹的变化情况

（1）k=0.5，λ=0时，搜索过程中不依赖任何启发信息，此时生成的全局最优航迹为R3，见图7所示。

（2）k=0.5，λ=1，时，考虑50%权重的燃油代价和50%权重的威胁代价，此时的动态启发式估价函数变为：f（m）=g（m）+h（m），采用此估价函数进行航迹搜索，生成的航迹R5如下页图9所示。

图9　k=0.5，λ=0，时生成的航迹R5

（3）k=0.5，考虑50%权重的燃油代价和50%权重的威胁代价，λ为动态变化权值时；此时的动态启发式估价函数变为更为一般的通式：f（m）=g（m）+（1/Mm）·h（m），生成的航迹R6如图10所示。

图10　k=1，λ为动态权值时生成的航迹R6

由图10知，搜索初期，深度Mm比较小，动态权值系数λ=1/Mm较大，航迹搜索主要依赖于启发式信息，体现搜索过程的快速性。此时生成航迹更接近于k=0.5，λ=1时生成的航迹R5。

搜索后期，随着深度逐渐增大，启发式权值系数逐渐减少，节点的扩展以广度搜索优先，生成航迹R6逐渐向全局最优航迹R3靠近，体现了算法的准确性。

总之，通过对当k=0.5，λ为动态权值时生成航迹的仿真分析，实现了搜索过程中快速性和准确性的结合。

4.3航迹平滑处理

针对运用动态权值A*算法生成的航迹R6，采用上文中航迹平滑思想进行仿真得到平滑航迹，可得到满足无人机机动约束的可行航迹，图11即为平滑后的航迹结果与威胁空间的叠加显示，验证了航迹的可飞性。

5　结束语

本文提出利用基于改进型V图和动态权值A*算法求解无人机在实际作战环境中的航迹规划问题，既克服了传统的V图在规划空间建模时的局限性，又实现了在航迹搜索过程中快速性和准确性的结合，仿真表明该方法具有很好的可行性，同时动态权值法也为实际运用中可飞航迹的调整提供了好的思路。

图11　平滑之后的航迹与威胁空间叠加

［1］康乐.无人机三维航迹规划方法研究［J］.计算机工程与应用，2009，45（33）：236-239.

［2］肖秦琨，高晓光.基于空间改进型Voronoi图的无人机路径规划研究［J］.计算机工程与应用，2005，26（S）：204-206.

［3］Timothy W M，Randal W B.Trajectory Planning for Coordinated Rendezvous of Unmanned Air Vehicles［R］.AIAA-2000-4399-CP，2000.

［4］刘振，史建国，高晓光.Voronoi图在航迹规划中的应用［J］.系统仿真学报，2008，29（S）：15-17.

［5］赵文婷，彭俊毅.基于VORONOI图的无人机航迹规划［J］.系统仿真学报，2006，18（S2）：159-162.

［6］叶媛媛，闵春平，沈林成，等.基于VORONOI图的无人机空域任务规划方法研究［J］.系统仿真学报，2005，17（6）：1353-1355.

［7］杨遵，雷虎民，曾康斌.不同威胁源下无人机的攻击航路规划算法与仿真［J］.系统仿真学报，2010，22（8）：1938-1941.

［8］冯慧，屈香菊.基于多目标模糊优化方法的无人机航迹规划［J］.飞行力学，2007，25（2）：25-28.

［9］周炜，魏瑞轩，董志兴.基于层次分解策略无人机编队避障方法［J］.系统工程与电子技术，2009，31（5）：1152-1156.

［10］穆中林，鲁艺，任波.基于改进A*算法的无人机航路规划方法研究［J］.弹箭与制导学报，2007，28（1）：297-299.

［11］李季，孙秀霞.基于改进A*算法的无人机航迹规划算法研究［J］.兵工学报，2008，29（7）：778-780.

［12］李少华，魏海光，周成平，等.一种无人飞行器的快速航迹规划方法［J］.四川兵工学报，2011，32（12）：73-76.

［13］李锐.基于启发式算法的无人机三维航迹规划仿真研究［J］.电光与控制，2009，16（8）：28-29.

UAV Path Planning Based on Improved Voronoi Diagram and Dynamic Weights A*Algorithm

ZHANG Tao-sha，LU Yi，ZHANG Liang，Lü Yue
（Engineering College of Aeronautics and Astronautics，Air Force Engineering University，Xi’an，710038，China）

Aiming at different threat level and different kinds of threat in actual operational environment，the path planning space on the basis of improved Voronoi diagram is established.Because evaluation function of A*algorithm requires different sensitiveness to indicator at different stage，based on traditional heuristic A*algorithm，dynamic weights A*algorithm is proposed to improve efficiency of path searching and combine the rapidity and the veracity of path planning.By Matlab software，the optimal path is acquired and the path is smoothed.The simulation shows the feasibility of improved Voronoi diagram and dynamic weights A*algorithm.

UAV，path planning，improved Voronoi diagram，dynamic weights A*algorithm，path smooth

TJ012.4

A

1002-0640（2015）02-0156-05

2014-01-03

2014-02-03

张淘沙（1990-），男，江苏宿迁人，硕士研究生。研究方向：飞行器航迹规划，指挥控制与引导。