一种用于航迹规划的网络图构造方法研究*

周志鹏，周成平，赵庆璐

(华中科技大学，武汉 430074)

0 引言

随着现代防空体系的越来越完善，越来越多的先进防空武器系统被应用到实战之中，单个导弹已经不能单独的完成摧毁敌方目标的任务，更多的时候需要不同的发射平台发射多枚导弹进行协同攻击，以提高导弹的突防概率，多任务的协同航迹规划是当今也将是未来比较热门的研究方向[2]。无人飞行器种类繁多，不同种类无人飞行器的航迹规划问题模型不同，规划难度也有显著差异。文中提出的方法主要针对巡航导弹这一类无人飞行器，该类无人飞行器的问题模型的一个重要特征是具有辅助制导约束，规划环境复杂。

对于巡航导弹多任务协同规划方法的研究已经存在很多，他们虽然使用的算法各异，但共同点是均基于栅格图规划环境，且各种协同规划方法均难以在短时间内规划出结果。通过对多任务协同规划系统的分析发现，单任务的可行航迹生成速度是影响整个多任务协同规划系统规划速度的一个十分重要的因素。如此，缩短多任务协同规划系统的规划时间的目的可以通过缩短单任务生成可行航迹过程的时间来实现。基于栅格图环境的单任务航迹规划方法研究已经十分的成熟，但是由于栅格图的特性所决定，绝大多数的算法在栅格图上的规划速度均难以有所突破。鉴于此，文中提高单任务规划速度的思路是将栅格图环境稀疏为航迹网络图环境，如此一来，单任务规划的搜索空间将大大减少，速度也必然得到提升。

1 巡航导弹图规划空间构造方法

1.1 多任务规划系统简介

多任务规划系统整体流程图见图1。

一般地，从战术的角度看，多任务规划系统可分为任务分配(或攻击计划)子系统、多航迹协同规划子系统、效能评估子系统3个部分(图1)。

文中的研究重点在于航迹规划技术领域。基于进化算法的多任务协同规划系统的流程一般为:为每个任务生成可行航迹，检查协同代价，若不满足要求则再次为某一个或全部任务生成新的可行航迹，重新协同，直到满足协同要求为止。可见单任务的航迹规划是多任务协同规划系统的关键技术之一，多任务协同规划系统中的航迹规划的部分与单任务航迹规划系统中的航迹规划部分相比，所使用的技术相同，但目标有差异，且运行次数也不相同。单任务系统一般只专注于代价最优或较优，对得到的可行航迹的数量或有要求，但不强制，协同规划系统中，航迹规划模块在保证航迹较优的情况下，必须具备生成多组可行解的能力，相应地，在协同代价的评价体系中，单任务的最优解不是该系统所主要关注。单任务规划系统中，每规划一个任务，航迹规划部分一般只需执行一次即可，而在协同航迹规划系统中，规划N个任务，每个任务需产生M个解，航迹规划部分则需执行N*M次。总体来说，协同规划的单任务规划方面由于需要多次重复调用，所以必须满足以下两个要求，第一，可给出一组互异可行解，第二，时间越短越好[4-8]。

当前对于存在辅助制导约束的巡航导弹的多任务协同规划技术研究仍主要基于栅格图规划环境，尽管他们使用的算法种类有很多，但是由栅格图规划环境的特性所决定，这些方法在规划时间上均难以达到令人满意的程度。相比之下，已经在无人机航迹规划中广泛应用的 Voronoi图方法[9-10]和航迹片段法[11]能够在很短的时间内规划出航迹，相同条件下，图规划环境较之栅格图规划环境的规划速度快的原因有二:一是图规划环境是解空间的稀疏化，搜索空间相应减少;二是在构建图规划环境的过程中，已经将构建航迹所必须的一些计算工作完成，在规划时只需进行少量工作就可以快速组建航迹。但是目前为止还没有一种可以适用于巡航导弹问题模型的图规划环境构建方法，文中在前人研究的基础上提出了一种解决该问题方案。

图1 多任务规划系统

1.2 有向航迹网络图

文中所提出的方法主要是用于解决存在辅助制导约束的巡航导弹航迹规划问题。辅助制导约束是指航迹中每隔一定距离范围内必须设置一个辅助制导点，用于纠正由于惯导导航带来的飞行误差。辅助制导方式一般为地形匹配或景象匹配，这种辅助制导点的分布完全取决于规划环境，且实际情况下分布并不十分丰富，没有办法使用先规划航迹再添加辅助制导点的方法，必须在规划中对该约束条件进行处理。基于上述描述，如果要为该问题模型生成图规划环境，则辅助制导点必须作为图中的扩展结点。最直接的扩展方式是使用树的扩展，且规划时回溯路径不再需要任何规划算法。但是该方法的局限性在于，树的规模随扩展的深度的增加呈指数级增长，使用该方法所能解决的规划环境规模十分有限。文中采用图结构，图规模与规划环境的面积成线性关系，有很好的可扩展性。

生成图规划环境的第二个问题是通过结点方向问题。在任务未定的条件下，通过一个节点在任意方向是等可能的。两个相邻结点间的连接若均考虑全方向的情况下必然产生组合爆炸。对于该问题，文中提出的解决方案是将规划环境网格化，为每个网格选择一个辅助制导点作为该网格的代表点，该点即为网络图上的扩展节点。然后以一个网格作为扩展起点向外扩展，生成覆盖整个区域的网络。这样的一张网络覆盖了以起点网格为发射点的所有任务的解空间，而且合理的削减了结点角度的选择范围。如果以每一个网格为起点均生成这样的一张网络，则可覆盖整个规划环境的解空间。

生成图规划环境的第三个问题是通过同一结点的航迹段的方向问题，经过同一结点的两个航迹段，必须满足一个航迹段的进入该节点方向，与另一个航迹段离开该节点方向相同才可以成功拼接。所以经过每一个结点只能有一个角度，且航迹段必须分为进入段与离开段，即生成图上的边是有向的。航迹网络上的边必须有向的另外一个原因是巡航导弹实际飞行中的飞行管道问题，巡航导弹的飞行管道随着飞行距离的增加而增加，同样一段航迹以相对的方向飞行所覆盖的飞行管道是不同的，所以文中航迹网络的有向性不仅体现在经过一个节点的航迹段被分为进入段与离开段，而且进入段与离开段是固定的且不能相互转化。即这样的一张网络仅可以用来规划以该网络起点为发射点，以某一点为目标点的航迹，反之，若以该起点为目标点，则不能规划。

巡航导弹一般均为三维规划，即二维平面规划加高度规划，基于文中提出的航迹网络的结构，对于高度规划拟采用对整个规划环境生成一个最低飞行曲面的方法，在网络生成时只需保证航迹段的高度在该曲面以上即可，此种方法的弊端十分明显，规划出的航迹的平均高度会增高。但文中的目的主要在于验证将栅格图环境转化为图环境的方法的可行性，高度规划暂不是研究重点。

综上所述文中方法所构建出来的图规划环境是一种有向航迹网络图。

1.3 有向航迹网络图构建原则

图2 网络图结构

由于以每个网格为起点网络相互独立且结构相同，在此对一张网络的结构进行说明，网络图的简化示意图如图2所示。

图2所示为一个以网格P为起点的部分网络图。网络图的生成遵循以下4个原则:

图3 三个角度方向的连接

1)生成网格代表点，将栅格图规划环境按一定粒度划分为网格，为每一个网格寻找一个辅助匹配区点作为其代表点，该代表点尽量靠近网格中心为原则。实际上，地形辅助匹配点与景象辅助匹配点在很多情况下不能够在全角度上发挥作用，即一个匹配点只在一个角度范围内通过它时，才能起到辅助匹配的作用，在这个范围以外通过该点，那么这个点就无法作为一个辅助匹配点。鉴于此种情况，文中给出的一种解决策略是以靠近网格中心为原则寻找一组辅助匹配点可以覆盖360°全部范围，将这一组点作为网格代表点。在给定起点的条件下，选择n个角度作为通过该网格的角度通道(参见第4条，文中n=3)，在这一组网格代表点中，依次找出包含每一个角度的点，在这里，同一个点可以被选择多次，在第4条中有论述，虽然这样的一个点的空间位置相同，但是由于角度不同，在网络图的结构中它是作为不同的结点存在。

2)扩展标准，在实际应用中，一个节点扩展到它的子节点的扩展步长为辅助制导点间的距离约束条件。在图2中，为简化起见，以曼哈顿距离等于2作为标准进行扩展。

3)扩展方向，网络图中除起点 P向360°方向扩展，其他所有的点的扩展方向均采用背离起点的原则，此原则即为，过被扩展点做被扩展点与起点连线的垂线，该垂线将规划环境分成两部分，扩展时只考察与起点异侧部分的点，且不包含垂线上的点。上节所述采用以一个网格为起点扩展一张网络的方法可以有效的削减结点的角度选择。在发射点确定的情况下只对前方的结点进行扩展是合理的。

4)经过辅助制导点的角度，起点P无角度限制，其他点均采用固定角度。即上节所述的航迹段对接问题。结合第二步，每一个结点只通过一个角度扩展它前方180°范围的点显然会增加边界航迹的不合理性。在实际生成网络图中采用了3个角度通道。如图3所示，这样的改进其实是将一个网格结点变为3个位置相同但角度不同的3个扩展结点，所以仍然符合上节提出的经过每一个结点只能有一个角度，且航迹段是有向的原则。理论上，将角度通道增加到n个，则有扩展关系的两个网格之间至多会有n2条航迹段相连，在综合考虑生成时间储存空间及解空间稀疏程度的情况下，文中选择了3个角度通道来生成网络。

1.4 可行性分析

基于前两节的论述，按照此设计思想，将网格粒度缩小至以栅格图规划环境的像素为单位，然后不再使用较少的角度通道，而是对全角度进行扩展，那么在两辅助制导点间连接方法固定的情况下，这样生成的航迹网络即为该栅格图规划环境的解空间。

鉴于在现有技术条件下，网格划分到像素级别和以极小粒度的角度覆盖全方向在处理时间与储存空间上均难以实现，所以文中的设计思想是对理论上的完美网络进行简化，从而与现有的技术条件相吻合。通过前两节的描述，可以看出简化包含两个方面，降分辨率处理(以网格来替代像素)，简化角度(只选择若干个角度通道)。

首先讨论降分辨率简化，降分辨率本质上是把网格中的所有点用一个点来代表。这样做的一个后果就是使得网格中的非代表点的辅助制导点没有被考察。在边长为L的正方形内选取一点，正方形内其他点距该点的平均距离最小为:

平均距离最大为:

文中用来测试的模拟栅格图规划环境为10°*15°(经纬度)，约 1000km*1500km，分辨率 1″*1″，在处理时间及储存空间条件允许的情况下，可以将网格边长尺度缩小至在10km左右，由于代表点的选择以靠近网格中心为原则，未扩展点与代表点的平均距离可以控制在10km以内，即航迹网络上的一个航迹段代表的是它的两个端点为圆心，10km为半径的两个圆形区域之间的所有连接。即对一个航迹段的端点在几公里的范围内进行一个小扰动，根据实际经验，扰动后的航迹绝大多数情况下依然可以是可行的。降分辨率可能导致的另外一种情况是在某些本可以存在连接关系的网格对中，由于只选择两个代表点，使得两代表点间的连接超出或小于航迹距离要求而被废弃。这种边界情况的出现比例同样依赖于网格的大小，但在既定网格粒度下，可以使用进化算法来进行两匹配区点的连接，进化算法连接与几何连接相比优点在于，几何连接所得航迹长度固定而进化算法连接的航迹长度拥有弹性，这样对边界情况的处理更加合理。

对于角度的简化，文中对一个网格选择了3个角度通道方向来扩展该网格前方的180°区域。由于一张网络图只为以该网络图起点为发射点的任务提供解集，所以不考虑极端条件下，经过非起点的网格的航迹的角度均在指向网格前方180°范围内，在选择了3个角度通道来代表180°区间的情况下，不采用网络图方法经过该点所使用的角度与固定角度通道的差值最多有20°，根据以往航迹规划的经验，认为这个角度差异是不会严重影响连接成功率的。

2 实验结果

文中利用一套模拟的规划环境对上述方法进行了实验验证，初始规划环境为栅格图环境，大小为36000*54000，分辨率为经纬度 1″*1″。硬件环境为商用PC机，处理器Intel E7200，内存2G，硬盘250G。

选择了两种网格尺度，分别为1000*1000和500*500(像素)，根据分辨率可知网格的实际距离尺度大约为30km和15km。按上文所述，为每一个网格寻找一个匹配区结点作为该网格代表点，但存在一部分网格不包含匹配区点，鉴于巡航导弹的规划中存在这样一种情况，即优先考虑地形或景像匹配，将GPS辅助导航方式作为补充。所以在这些网格中选取一个GPS辅助导航点作为其代表点。

两种网格尺度下生成一张网络图的情况如下:

由此可见，生成的航迹数量非常多，图4仅显示部分网络的示意图

图4 航迹网络图

图4为1000*1000网格尺度下所生成的部分航迹网络，该尺度下规划环境被分为36*54个网格，如图截取的区域仅有12*7大小。如图4所示，P点为网络起点，在P点的众多子节点中只选择了A1显示，在A1的子节点中也只选择了 B1、B2、B3进行显示。网络图的效果与文中的预期完全一致。

为验证在该航迹网络上的规划效率，文中在该网络上实现了蚁群算法的单任务规划，蚁群算法属于进化算法，可以给出多个可行解，十分符合协同规划的需求。鉴于协同规划还需另行考虑其他许多因素，因此文中并未实现协同规划模块。本实验的目的是要证明在该航迹网络图上，单任务规划的时间得到极大提高，进而必然将降低协同规划的规划时间。

蚁群算法的参数选择对规划结果的影响十分明显，其中蚂蚁数目与进化代数的参数选择，分别采用蚂蚁数目与任务长度线性相关，进化代数固定为100代。

对不同任务的规划结果如下:

任务 任务长蚂蚁数量 可行航规划度/km 迹数量 用时/s任务1 468.18 103 101 3任务2 773.48 170 170 7任务3 1616.97 355 355 34

航迹规划结果截图如图5只为每一个任务显示了最优的10条航迹。

图5 规划结果

可以看出使用航迹网络的方法能够在短时间内得到大量可行解。但是因为其基于网络图的特点，不同的航迹会公用部分航迹段，而从图中总体来看，航迹的多样性还是十分饱满的。

3 总结

文中对存在辅助制导约束的巡航导弹航迹规划问题提出了一种将栅格图规划环境转化为图规划环境的方法。该方法的优势在于可以很快得出多组可行航迹，适合大批量的任务规划，尤其适用于多任务协同规划;该方法作为针对一类问题模型所提出的解决方法，可适用于多种武器系统，这在实际应用中有着重要的意义。该方法的不足之处在于若只进行少量的任务规划，使用该方法则费效比较高;生成数据量较大，需要对数据有高效的管理方法。

综上所述，在经过简化从而适应目前技术水平的情况下，还是可以看到此种方法可以得出令人满意的结果。可以在短时间内规划出大量的可行航迹，且航迹的多样性比较令人满意。而且可以预见，随着硬件技术的进步，该方法的性能也必将越来越高。

[1]丁明跃，郑昌文，周成平，等.无人飞行器航迹规划[M].北京:电子工业出版社，2009.

[2]黄赛超，刘顺利，姚弘毅.从四次局部战争看美军巡航导弹的使用及发展[J].飞航导弹，2007(7):19－21.

[3]任敏，吴昊，沈林成.巡航导弹的任务模式和规划需求[J].飞航导弹，2009(1):29－32.

[4]张志勇，毕义明，郑重.巡航导弹协同作战任务规划需求[J].飞航导弹，2012(6):32－36.

[5]郑昌文，丁明跃，周成平，等.多飞行器协调航迹规划方法[J].宇航学报，2003，24(2):115－120.

[6]史战伟，周成平，丁明跃，等.基于进化计算的多无人飞行器协同航迹规划[J].战术导弹技术，2007(5):49－53.

[7]刘宇坤，谢军.基于 K路径算法的多无人机协同航迹规划[J].微计算机信息，2008，24(8－3):208－209.

[8]叶媛媛，闵春平.多无人机协同航路规划的共同进化方法[J].计算机仿真，2007，24(5):37－39.

[9]Chandler P，Rasumussen S，Pachter M.UAV cooperative path planning[C]//Proceedings of AIAA Guidance，Navigation，and Control Conference，2000.

[10]McLain T W，Beard R W.Trajectory planning for coordinated rendezvous of unmanned air vehicles[C]//Proceedings of the AIAA Guidance，Navigation，and Control Conference，2000.

[11]Li Shidong，Ding Mingyue，Cai Chao.A novel path planning method based on path network[C]//Proceedings of the SPIE 6th International Symposium on Multipectral Image Processing and Pattern Recognition，2009.