基于A*算法的地空导弹部队机动路线选择模型研究*

陈宝印 申 铭 黄 横 张广品

(防空兵指挥学院研究生16队1) 郑州 450052)(75240部队2) 潮州 521041)(73136部队3) 厦门 361023)

1 引言

地空导弹部队主要担负的是地面部队和重点目标的对空安全等任务。由于担负任务的特殊性,其成为敌人打击的重点。兵力机动是提高地空导弹部队生存能力和再次抓住战机的有效途径。1999年南斯拉夫的地空导弹部队在抗击北约的空袭中就进一步说明地空导弹机动灵活作战是保护自己、消灭敌人的有效方法之一。然而,在机动的过程中机动路线可能有多条,如何快速、隐蔽、安全的到达指定地域,是指挥员在选择机动路线时必须面对的现实问题。同时在机动的过程中,影响的因素很多,从分析影响地空导弹部队机动因素出发,应用A*算法定量的给出选择地空导弹部队最佳机动路线的数学模型,为指挥员在战时的辅助决策支持提供了依据。

2 影响地空导弹部队机动的因素及量化

图1 影响因素

正确分析确定地空导弹部队机动路线的影响因素,是机动路线问题的前提。影响地空导弹部队机动路线的因素很多,为简便起见,主要考虑线路的路长、线路的路况、线路上的障碍(如壕沟、涵洞、桥梁和水深)、线路的隐蔽性、部队的自身防护能力和当时的气象条件等影响因素,如图1所示。设每一影响因素的量化值为Ekji,其中k、j表示节点编号,i表示第i个影响因素(k=1,2,3,…,n-1;j=2,3,4,…,n;i=1,2,3,…,6)。同时,这些因素又包含其子因素。各子因素量化值为Ekjir建立数学模型就要综合考虑衡量这六个因素,从而选择一条最佳的机动路线。

2.1 路长因素及量化

路长:地空导弹部队机动所经过路段的实际长度。在地空导弹部队机动的过程中,每条线路节点之间的距离都是不等的,而在战时,时间就是生命,所以线路路长是影响部队机动的因素之一。根据以上假设,路长因素量化值可设为Ekj2。

2.2 路况因素及量化

路况因素主要是指线路的道路等级、道路的交通情况和可维修性等等。如在水泥地面和在泥土路面及崎岖的山路上,即使是相同的距离,机动所需要的时间也是不相等的。而道路的等级、道路交通情况和可维修性可通过评判打分的方法得到其量化数据,故根据以上假设路况因素量化值可设为Ekj3,各子因子的量化值分别设为Ekj31和Ekj 32,则Ekj3=Ekj31+Ekj 32+Ekj33。(在个数值相加之前应对其进行无量化处理,可参考2.5)

式中:Ekj 31为道路的等级量化值,Ekj32为线路可维修性,Ekj33为道路的交通情况。对于某段路的评价可简化为(好,较好,差)三个等级,同样可通过专家评判获得量化数据。

2.3 障碍因素及量化

在障碍因素中,主要考虑机动中遇到的壕沟、涵洞、桥梁和水深等因素,这些影响因素主要限制地空导弹部队的通行,如壕沟太宽、涵洞太矮、桥梁承重太小、水深太深等都无法使部队通过。这些影响因素的量化值都是BOOL值,即0或1。能够通行即为1,不能通行即为0。根据假设,障碍因素的量化值可设为Ekj4,各子因素的量化值设为Ekj41,Ekj42,Ekj43,Ekj44,则 Ekj4=Ekj41◦Ekj42◦Ekj43◦Ekj44。

式中Ekj 41表示壕沟能否通行,Ekj 42表示涵洞能否穿越,Ekj43表示桥梁承重能否达到,Ekj44表示水深是否超过最大涉水深度。

2.4 隐蔽性因素及量化

地空导弹部队机动的目的就是快速机动,抓住战机,保护自己免遭攻击。所以选择隐蔽性好的线路,同样也可以达到快速机动的目的。在隐蔽性不好的线路上机动,容易暴露目标。随着高技术侦察装备的不断发展,特别是空中侦察装备,使部队在大多数情况下都必须很好地隐蔽自己免遭对方发现。这里主要考虑遭敌卫星和侦察飞机发现的概率。假设隐蔽性因素的量化值(等于不能被敌侦察发现的概率)为Ekj5。

其中,r为目标与背景光度,a为气象因子系数,u为目标形状修正因子,pt为卫星的分辨力,L为目标的几何尺寸,pw为武器被识别概率,v为飞机飞行速度,d为搜索宽度,s为机动区域,t为搜索时间,w为侦察卫星的数目,f为侦察飞机的数目。

故可得:Ekj5=1-P。

2.5 自身防护因素和气象因素及量化

自身防护能力是指地空导弹武器在执行战斗任务的过程中,采取自身保护和伪装措施而达到的自身防卫能力。防护能力越强,其生存能力就越强。

气象因素这里主要考虑天气情况和昼夜情况。天气情况如天气的恶劣程度,昼夜情况如是白天还是黑夜,主要影响能见度。

在本模型中,由于在相同时刻自身的防护能力和气象条件的量化值都是相同的,故在模型中其量化值将不予考虑。

2.6 影响因素量化值的无量纲化

3 A*算法的基本原理[2]

A*算法是建立在Dijkstra算法基础上的启发式搜索算法,在Dijkstra算法基础上引入了当前节点的估价函数 f(n)。其关键就是建立估价函数

式中,f(n)是从初始点通过节点n到达目标点的估价函数。g(n)为从初始点开始,沿着产生的路径,移动到节点n的移动耗费。h(n)为从节点n移动到目标点的预估移动耗费。

A*算法的实现步骤如下:

1)以起点为第1个路径节点,寻找与之相连的候选节点;2)对与之相连的每一个候选节点计算其估价函数值 f(n),选出 f(n)值最小的节点作为下一个路径节点;3)如果该节点是目标节点,则结束搜索,否则,进入步骤2),以新的路径节点为起点继续搜索,并记录搜索到的最短路径,直至目标节点。

4 适合防空兵机动路线选择的A*改进算法

4.1 改进思路

在地空导弹机部队机动过程中,由于各种影响因素的存在,同时各影响因素所占有的比重也是不同的,为分析问题的方便,我们引入机动能力影响因子的概念,即把机动过程中的相关影响因素转化成权重值。然后将g(n)的值乘以这个权重值,再利用A*算法进行求解。公式如下:

e为每段路的机动能力影响因子。

4.2 算法实现步骤

在算法的实现过程中,要构造两个链表。分别存储待扩展的节点和已扩展的节点,分别称为OPEN表和CLOSE表。算法实现步骤如下:

1)初始化设置。设置初始节点:ds=0,ps=Φ;其他点:ds=∞,ps=?(未知);将起始节点s标号,记k=s。并将起始点信息加载到OPEN表中,CLOSE表赋值为空。

2)机动能力因子计算。首先计算起始点s到其他直接连接的未标记的点j的机动能力因子ekj。

3)距离计算。计算从所有标记点的点到其他直接连接的未标记的点j的距离。即搜索距离当前节点最近的节点,求 f(j)的最小值,将节点j从OPEN表中删除并加载到CLOSE表中。判断节点 j是否为终结点,如果是,转向步骤5);否则转向步骤4)。

4)判断节点j的节点信息是否在确定的范围内,如果在范围内,则扩展节点j;否则加载节点j的节点信息并进行扩展。转向步骤3)。

5)从节点 j开始,利用回溯的方法输出起始节点到目标节点的最优路径,以及最短距离,算法终止。

4.3 机动能力因子计算

根据影响地空导弹部队机动的因素,在确定每一个影响因素的量化之后,可建立如下计算公式计算从所有标记的节点k到其他直接连接的未标记节点j的机动能力影响因子:

式中,Ekji为第i个影响因素的量化值;qi为第i个影响因素所占有的比重。

计算后,代入机动能力因素计算式即可。

5 实例分析

根据上述设计,现以一个实例来具体说明A*算法在地空导弹部队机动路线选择中的应用。如图2所示,为某地空导弹部队从S1～S8可能机动的路线节点及可能经过的路段。

图2 机动路线树

1)由图2可知,该地空导弹部队可能的机动路线一共有8条,即:

表1 可能路径表

2)设定每一个影响因素的权重 qi为(0.4,0.1,0.2,0.3),根据4.3节可算得每段路的机动能力因子ei。

3)对所有影响地空导弹部队机动的因素,利用前面给出的数学模型求取Ekji,如表2所示。

表2 各影响因素值

4)根据前面的数学模型,利用VC++6.0编写仿真程序,可得到地空导弹部队机动路线选择的结果,计算结果如表3所示。

表3 A*算法计算结果表

从表3可以得到地空导弹部队机动在图2的地图中各可能路线的评价值,因此很容易看出哪条路径最适合于机动。表3中路径3的评价值最小,即S1-S4-S6-S8为最佳的机动路线。

6 结语

利用A*算法计算地空导弹部队机动的最佳路径,方法简单,设置的数据少,选择的速度快,而且易于编程实现,是解决地空导弹部队机动路线选择问题的有效途径。在实际问题中,可根据地空导弹部队执行任务的特殊性,灵活的选择影响因素,具有一定的推广价值。

[1]张野鹏.作战模拟基础[M].北京:高等教育出版社,2004,7

[2]漆阳华,等.A*的改进路径规划算法[J].信息与电子工程,2009(4)

[3]张最良.军事运筹学[M].北京:高等教育出版社,2004

[4]康凤举.现代仿真技术与应用[M].北京:国防工业出版社,2001,9

[5]王永庆.人工智能原理与方法[M].西安:西安交通大学出版社,1998,5

[6]杜国红,等.坦克分队CGF实体智能机动行为仿真[J].系统仿真学报,2006(7)

[7]王洁,等.地空导弹火力单元最佳兵力机动线路的选择[J].系统工程与电子技术,2003(1)

[8]杨建军.科学研究方法概论[M].北京:国防工业出版社,2006,7