基于改进A*算法的无人机任务分配和航迹规划优化方法

郑 锴， 郑献民， 殷少锋， 林宏旭， 孟庆豪

(中国人民解放军32146部队，河南 焦作 454000)

1 概述

任务分配和航迹规划是无人机任务规划的关键技术问题，国内外学者对无人机任务分配和航迹规划开展了广泛的研究，已取得了较大进展。无人机任务分配优化算法主要包括数学规划法、启发式算法、智能优化算法等；无人机航迹规划优化算法主要包括数学规划法、基于图形学的方法、启发式搜索算法、智能优化算法等[1-2]。

任务分配和航迹规划并非简单的连续过程，而是具有紧密的相互作用关系。在已有的研究工作中，往往将无人机的任务分配和航迹规划作为两个相对独立的环节进行研究，无人机任务分配过程中通常应用直线欧氏距离近似表示航程，未充分考虑威胁区域等对航迹预估的影响，从而易造成任务分配不合理。在动态不确定、强对抗性的战场环境下，无人机任务规划面临着复杂的环境约束条件，迫切要求在任务分配中参考航迹规划的预估结果，在航迹规划中应用任务分配的结果[3-6]。

本文提出了一种基于改进A*算法的无人机任务分配和航迹规划优化方法。该方法以无人机执行多目标侦察任务为应用背景，基于改进A*算法预估航程代价，通过无人机区域设置、任务分配、航迹规划等全局预先任务规划阶段，以及局部动态任务规划阶段，实现无人机多时序目标任务规划。任务规划的原理框图如图1所示。

图1 任务规划原理框图

其主要流程如下。1) 区域设置。在地理信息系统(Geographic Information System,GIS)中，依次点击无人机阵地坐标和任务坐标，确定任务规划区域范围，采用不同几何形状标记威胁区域。2) 任务分配。改进传统A*算法，构建无人机、各任务点之间的A*预估航程矩阵；应用旅行商问题(Travelling Salesman Problem,TSP)模型和遗传算法，求解各阵地内单无人机的时序任务分配。3) 航迹规划。采用改进A*算法规划并绘制航迹，基于三次B样条曲线法进行航迹平滑。4) 局部动态任务规划。在全局预先任务规划的基础上，依据威胁区域、任务目标的变化，确定局部动态规划空间，执行局部任务动态分配和局部航迹动态规划。

2 规划区域设置

典型应用场景为：无人机执行多目标侦察任务，任务区域内有地形、探测和火力等多种飞行安全威胁，以无人机航程最短、消耗最小、安全性最好为优化目的，每个目标至少被侦察一次，无人机航迹规避每个威胁区域，求解无人机的最优任务分配和航迹规划方案。

2.1 区域规划

在地理信息系统中，点击选定并标注无人机和多任务的位置，确定任务规划的区域范围，规划区域见图2。

图2 规划空间示意图

设在无人机和任务位置点中，最大高斯坐标值分别为Xmax和Ymax，最小高斯坐标值分别为Xmin和Ymin，规划空间的扩展距离值为L，则可确定矩形规划区域的4个顶点分别为(Xmin-L,Ymin-L)，(Xmin-L,Ymax+L)，(Xmax+L,Ymax+L)和(Xmax+L,Ymin-L)。

将二维规划空间离散栅格化，(Xmin-L,Ymin-L)为原点，设h为网格边长，则规划空间中任意点(x,y)的网格坐标(xg,yg)为

(1)

2.2 威胁设置

在地理和气象条件恶劣、高强度对抗、空域资源紧张等特殊战场环境下，无人机执行任务将面临地形、雷达探测、电子对抗、防空火力、禁飞区等飞行威胁区域。根据不同威胁模型的特点，分别通过手绘或标注等形式，用圆形、矩形、多边形等不同形状标记威胁区域。按式(1)计算威胁区域边界的网格坐标(xgt,ygt)，构建威胁区域矩阵G[x][y]，令G[xgt][ygt]=1表示该网格为威胁网格，G[xgt][ygt]=0表示该网格不是威胁网格。

3 改进A*算法设计

A*算法是一种启发式搜索算法，通过在栅格化空间不断评估路径函数值来启发式搜索节点，构造最优航迹[7-9]。A*算法全局性好、运行较快、易于工程实现，在航迹规划领域获得了广泛的关注。结合具体应用背景，对传统A*算法进行了改进设计，通过约束扇形搜索区域减小搜索计算代价，通过航迹节点调整去优化锯齿型航迹。

3.1 确定代价函数

A*算法的代价函数为

f(n)=g(n)+h(n)

(2)

式中：n为当前节点;f(n)为起始点经节点n到目标点的代价函数;g(n)为从起始点到节点n的实际代价;h(n)为节点n到目标节点的估计代价。

g(n)表示为

g(n)=ω1ln+ω2Jn+ω3zn

(3)

式中：ln为航程代价;Jn为威胁代价;zn为高度代价;ω1,ω2和ω3表示对应的代价权值。在战场高对抗条件下，无人机安全飞行是首要指标，要求航迹能够规避所有威胁区域，将威胁代价设为无穷大，令ω2=∞；无人机通常优先采用固定高度巡航，为简化航迹优化问题、减少计算量，设定无人机以固定高度巡飞，将三维空间航迹搜索问题简化为二维问题，令ω1=1，ω3=0。

h(n)可理解为启发函数，引导节点(xn,yn)向目标点(xt,yt)的方向搜索扩展，可表示为

(4)

3.2 限定约束条件

考虑无人机最大航程、最小轨迹段长度、最大转弯角等性能约束，为优化搜索空间、提高搜索速度，在启发式航迹搜索过程中，设定以下约束条件。

1) 最大航程。

无人机受数据链作用距离、飞行动力等因素影响，最大航程受限。单架无人机航迹搜索的总航程f应小于无人机的最大航程Lmax，即f

2) 最小轨迹段长度。

受机动能力约束，改变飞行方向前，需要沿原方向直飞一段距离，即最短直飞距离为lmin。在A*算法中，网格边长h为搜索步长，搜索步长应大于最小航迹段长度，即h>lmin。

3) 最大转弯角。

在规划空间启发性搜索下一节点时，限定在扇形约束区域内搜索，而不是遍历每个相邻节点。图3为搜索区域示意图，阴影区域表示扇形搜索区域，最大转弯角θ对应于最小转弯半径Rmin，节点扩展角α在2θ范围内，从而可减小搜索空间、加快搜索速度。

图3 航迹节点的扇形搜索区域示意图

3.3 航迹节点调整

在栅格化节点扩展过程中，节点扩展主要局限在栅格线的交叉点上，会导致部分航迹呈锯齿状。为了避免锯齿形航迹，需要进行航迹节点调整，将部分锯齿形折线航迹优化为直线。图4所示为节点调整示意图，将虚线航迹优化为实线航迹。

图4 航迹节点调整示意图

设初始航迹节点序列为vw1[r]，节点序列数量为r，则节点的调整过程为：1) 初始令j=r；2) 循环检查(vw1[i],vw1[j])之间的连线是否通过威胁区，i∈{1,…,j-1}，若通过威胁区，令i=i+1,若不通过威胁区，令j=i，并将vw1[j]保存为调整后的航迹节点；3) 重复上述循环，直至j=1时停止循环，生成调整后的航迹序列vw2[l]，调整后的节点序列数量为l。

3.4 航迹搜索过程

在启发式搜索时，建立Open和Close两个表，Open表用于存储已经计算但没有扩展的节点，Close表用于存储已经扩展的节点。数据存储结构表示为{(xi,yi),fi,gi,hi,pi}，(xi,yi)为节点的网格坐标，fi,gi和hi为代价函数的变量值，pi代表当前节点的父节点。改进A*算法流程如图5所示。

图5 改进A*算法流程图

算法流程如下。

1) 初始化。设置步长和障碍区域，初始化Open和Close表，起点放入Open表中作为当前节点。

2) 节点扩展与存储。当前节点的相邻节点，若满足约束条件且不在当前Open和Close表中，则将该有效节点加入Open表；将Open表中代价最小的节点A移到Close表中；判断节点A是否为终点，若是终点则退出节点搜索，若不是终点则继续节点扩展。从Close表中提取初始航迹节点序列vw1[r]，将终点的代价函数值作为预估航程。

3) 航迹节点调整。初始设vw1[r]中的初始航迹起点为调整起点，初始航迹终点作为调整中继点；从调整起点开始，依次判断vw1[r]中各航迹点与调整中继点的连线是否经过障碍区；若调整起点与调整中继点的连线通过障碍，则将当前调整起点的下一点更新为调整起点，继续判断是否通过障碍；若调整起点与调整中继点的连线不通过障碍，将当前调整中继点保存为航迹调整后的一个航程点，并将当前调整起点更新为调整中继点，继续循环判断；直至当前调整中继点为起点，停止循环，综合各个调整中继点构建出调整后的航迹序列vw2[l]。

4 任务分配

TSP问题是经典的路径优化问题，传统的TSP模型求解时，通常将各点之间距离简化为直线欧氏距离[10]。在复杂高对抗的战场环境下，目标点间距离若不考虑规避威胁区域，将存在较大的误差，TSP求解将难以获取合理的结果。因此，改进TSP求解方法，任意两点的距离采用A*算法预估距离。

考虑规避威胁区域，采用A*算法估算出无人机起点、多个任务目标点之间的距离，构建出A*距离矩阵pw[k][k]，k为无人机的任务数量。图6所示为时序任务分配编码示意图，起点和终点为无人机阵地，1,2,…,k代表目标序号。

图6 时序任务分配编码示意图

目标函数R表示为

(5)

式中：hi j为无人机从目标i到目标j的A*距离;ci j∈{0,1},为决策变量。

若时序任务分配规模较小，优先采用深度遍历法，循环比较任何一种可能方案，准确获得最优解。若时序任务分配规模较大，精确算法求解计算量过大，可采用遗传算法求解[10-11]。

5 航迹规划

5.1 航迹寻优

基于多无人机任务分配和单机时序任务分配的分配方案，依据每架无人机的任务序列分别进行航迹规划，应用改进A*算法进行航迹寻优，A*算法按照第2章执行。

无人机起点、时序序列u[c]中的各任务点、无人机回收点构成航迹点序列，从起点开始，依次将航迹序列中的两个连续时序节点作为A*搜索的起止点，获得各连续节点之间的初始航迹序列v1[r]及调整后航迹序列v2[l]。任意两个时序连续节点间的v2[l]，组合在一起构成无人机的总航迹v3[q]，总航迹点数量为q。

将无人机的航迹点v3[q]进行地理坐标转换，绘制在地理信息系统上，可得到无人机航迹图。

5.2 航迹平滑

航迹寻优绘制的航迹为折线图，不符合实际航迹，需要将折线航迹转换为平滑曲线，得出满足飞行约束的航迹曲线。三次B样条曲线具有局部性、凸包性和C2连续性等特点，平滑效果好[12]。

航迹寻优获得的航迹控制点为Pi(i=0,1,…,n)，采用三次B样条曲线进行平滑处理，每段曲线由连续相邻的4个航迹控制点确定。改进A*算法的航迹点往往易于稀疏化，使航迹平滑曲线更接近初始航迹折线，可考虑在v3[q]的各个航迹点附近增加控制点，比如航迹点v3[i]与节点v1[j]相对应，可在v3[i]点后增加控制点v1[j+1]，再执行曲线平滑操作。

n次B样条曲线可表示为

(6)

式中：Pi为序列航迹点；基函数Bi,n(t)为

(7)

当n=3时，三次B样条曲线表示为

t∈[0,1]。

(8)

6 局部动态任务规划

在复杂多变的战场环境中，往往存在突发威胁、目标变化等情况，预先规划航迹将不能满足任务需求。根据战场态势变化，在预先全局规划的基础上，仅进行局部动态规划，从而可缩小规划空间、缩短规划时间。具体表述如下。

1) 局部区域设置。根据威胁区域分布、目标变化情况，在GIS中点击选定局部规划的起点、多个目标点、终止点的位置，标绘威胁区域，确定局部区域范围。起点和终止点通常在初始全局航迹上，选在更新后威胁区域的边界附近，中间点为无人机必须经过的一些目标点，包括预先已知目标点和动态变化的目标点。

2) 局部任务动态分配。依据改进A*算法，构建局部规划起点、多个目标点、终止点之间的A*预估航程矩阵；基于旅行商问题模型和遗传算法，求解各点的时序任务分配。

3) 局部航迹动态规划。采用改进A*算法规划并绘制航迹，基于三次B样条曲线法进行航迹平滑，规划出局部起点、各中间点、终止点之间的航迹，最终回到初始规划航迹。

7 实验验证

针对无人机任务规划的应用需求，应用Visual Studio 2015与QT5.8开发环境和C++语言，开发了无人机任务规划软件，包括无人机管理和监测、地理信息系统、任务分配、航迹规划、数据上报等功能模块，地理信息系统模块基于OSG/OSGEarth开源库二次开发。任务规划软件界面主要包括菜单栏、GIS显示区域、状态区域和任务规划子界面等。

图7(a)所示为确定无人机和7个目标的位置、标绘威胁区域后，点击任务分配按键，根据考虑障碍区域的预估A*距离，求出了时序任务分配结果，并在子窗口右下方显示出分配结果；点击航迹搜索按键，给出了A*搜索的初始航迹，可以看出航迹能够规避障碍，但是由于航迹搜索局限在栅格交叉点而导致部分航迹呈锯齿状。图7(b)所示为点击航迹调整后进行航迹节点调整，将部分锯齿形折线航迹优化为直线。图7(c)所示为点击航迹平滑按键后得出航迹曲线。测试结果表明，多个目标时序分配合理，无人机航迹规避了障碍区域，通过航迹调整和航迹平滑避免了航迹折线现象。测试过程无明显时延，全局任务规划结果合理。

图7 全局任务规划测试结果

图8(a)所示为分别在局部区域标志出局部起点、2个中间点、局部终点，标绘更新后的威胁区域，点击任务分配按键，根据预估A*距离，求出了时序任务分配结果，并在子窗口右下方显示出分配结果。图8(b)所示为点击航迹搜索、航迹调整、航迹平滑后，规划出局部动态航迹曲线。测试结果表明，局部动态任务规划的目标时序分配合理，航迹规避了障碍区域，动态任务规划结果合理。

图8 局部动态任务规划测试结果

8 结论

基于改进A*算法的无人机任务分配和航迹规划优化方法，主要包括规划区域设置、任务分配、航迹规划和动态任务规划等步骤。在地理信息系统中，点击选定无人机和各任务点的位置，标绘威胁区域，确定规划区域；结合应用背景改进A*算法，通过航迹调整优化航迹；应用预估A*航程矩阵，基于TSP模型和遗传算法求解任务时序分配结果；应用改进A*算法和B样条曲线法规划并绘制出无人机航迹；根据威胁区域和目标的变化进行局部区域动态规划，合理规划出局部航迹。实验证明该方法可靠性好、易于工程实现。