刍议基于优化Dijkstra算法的仿真实体路径规划

张贺勇 甄磊 孙娟 麻丽俊

北方自动控制技术研究所 山西 太原 030006

1 仿真实体路径问题

在仿真过程中，无论是目标打击任务，还是实体机动巡逻任务，模型实体机动的路径是否符合我们预想的目标一直都是我们关心的问题。尤其是在军事推演方面，实体机动的路径也算是推演过程中的一部分。手动添加设置机动点不需要我们考虑实体机动路径是否合理，实体模型只需按照预设的机动点逐点机动即可。但是在仿真平台自行推演实体机动的过程中，就需要我们通过算法来实现合理的实体机动路径。

以侦察打击目标来说，在侦察实体发现多个固定目标如空军基地、雷达站、指挥所等时，混伤爆破实体接收打击目标位置坐标，并向目标位置机动，在打击范围内摧毁目标实体。在上面的侦察打击目标任务中，混伤爆破实体出发位置就可以理解为推演实体路径原点，固定目标实体位置对应于轨迹路径所要经过的点。与传统的多个点所构成的图的遍历所形成的一条路径不同，这里我们还要考虑限制条件混伤爆破实体的打击范围，即加了限制条件一定范围内无向图中各点的遍历路径问题[1]。

2 DlS算法

2.1 算法思路

针对上面仿真推演过程中实体轨迹路径所转化成的无向图中各点之间的遍历问题，无论是哪种遍历方法，最终遍历结束之后都会形成一条轨迹，这条轨迹就是实体在推演过程中的机动路径。对于少量节点的实体模型来说，逐点遍历形成一个路径轨迹即可，对于多个节点的实体路径来讲，就要依靠算法来实现一条高效的轨迹路径，这里我们给出利用Dijkstra算法（简称为DIS算法）来实现实体路径的规划。

2.2 算法比较

对于最短路径算法，目前被应用最广的有：Dijkstra、Floyd、Bellman-ford三种算法。三种算法各有优缺点，Dijkstra算法复杂度低且比较容易实现，但不适用于多源点存在负权值图的路径遍历。Floyd算法可用于遍历多源点带负权边的图，缺点是算法复杂度高且双邻接矩阵的算法实现繁杂难懂。Bellman-ford算法适用于权值有负值的图且能够检测负圈，但对于稠密图的路径遍历来说算法复杂度过高，关系密切的顶点来说亦是如此。

虽然Dijkstra算法比较于Floyd和Bellman-ford算法来说不能遍历带负权的图，但Floyd算法复杂度高对于稠密图的最短路径遍历来说耗费的内存和时间过大。Bellman-ford算法虽然复杂度低，但其只适用于稀疏图，在现实问题中我们往往面对的都是稠密图最短路径的遍历。所以以算法的复杂度和适用范围来说，这里我们以Dijkstra算法为基础来进行实体路径规划。

Dijkstra算法采用了数组的思想，随着计算层数的增加，能够较快地适应条件变量的更新，达到快速求解的目的。在相同条件下，Dijkstra算法与基础神经网络算法相比，其计算耗时低且准确率高。

3 优化算法应用实体路径规划

3.1 算法优化

（1）源点确定。与Dijkstra算法中自行确定源点位置的情况不同，算法在仿真平台应用时，在对想定中实体进行推演仿真的过程中，我们所要确定的源点对象是具有机动能力的实体。像战斗机、装甲车、突击班等这些具有机动打击行为的实体都可以作为我们在初始化算法时的源点位置。

（2）节点与边的确定。同样的对于Dijkstra算法中遍历节点与边的确定，将仿真平台想定编辑中的固定目标实体作为确定的节点位置，像军事基地、指挥所、雷达、机场等。Dijkstra算法图中节点之间的边都是给出的，对于在仿真场景中源点和遍历节点存在确定边的情况，我们默认为源点到每个节点都存在一条可直接到达的边。当然对于超出一定距离阈值的情况我们就认为其需要借助其他点来到达。

（3）针对移动目标的实现方案。Dijkstra算法不能实现对移动实体目标在仿真过程的路径遍历，针对移动的实体目标，这里我们给出一种在我们的约束条件下的优先路径遍历方案。在移动目标进入阈值范围且进入源点实体限制因素射程范围内时，优先在仿真周期对移动实体目标进行路径遍历。

3.2 优化算法规划实体路径实现

针对约束条件下和移动实体目标路径基于Dijkstra算法的遍历，在XSIM平台中仿真模型以红方雷达探测范围作为限制条件下的Dijkstra算法遍历阈值范围，蓝色方的歼击机作为移动的目标实体，蓝色虚线混伤区域代表射程范围，红色方的源点战斗机停靠在机场且射程范围与蓝色方歼击机相同。指挥所在蓝方歼击机进入雷达探测区域时，对红方战斗机下发交火任务指令摧毁蓝方歼击机。

利用上方建立的实体模型，相同条件下利用Dijkstra算法与原有算法比较得到仿真结果。根据仿真结果可知，在相同的条件下，都实现了在蓝色方歼击机进入侦察区域红方战斗机开始对目标进行打击，并在射程范围内摧毁蓝方歼击机，黑色标记为蓝方歼击机被击落点。但平台本身算法仿真结果显示战斗机往返路径基本相同，运用Dijkstra算法仿真推演得到的实体路径轨迹更加符合我们所要求的标准。

4 结束语

在互联网技术高速发展的今天，对于军事仿真的效果越来越高。对于优化的Dijkstra算法来说，其不仅仅是应用在仿真推演过程中的实体路径轨迹规划的问题上。在XSIM平台中应用Dijkstra算法解决的路径轨迹推演的问题，在技术互通的今天，其他平台的仿真实体路径问题亦可运用上面的思想来解决同一类的路径问题。像三维场景中的蓝军智能行为牵扯到的巡逻、机动、上下车等问题，都可以利用Dijkstra算法思想来解决。