适用于海军平台的自动路径规划算法

沈燕霞

【摘要】本文介绍了一种适用于海军平台的自动路径规划算法，自动路径规划算法从电子海图提取地理数据，然后根据这些数据产生从开始点到目标点的航路点序列，该算法能应用于任意海军平台的路径规划。这种算法可适用于海军的各种领域，如鱼雷发射航路的计算，水面舰艇和潜艇的导航等。

【关键词】海军平台;自动路径;规划算法

1.引言

开发适用于海军平台的自动路径规划算法的目的是寻找通过给定区域并能避开所有障碍物的一条最佳路径。路径中的航路点序列来自之前扫描发现的点集。目前算法是针对二维航路点规划设计的，同时也考虑了海区的深度。

算法的边界条件定义如下：在开始计算时先获取自身和所有已知目标的真实位置，假定计算过程中这些目标的位置保持不变。因为整过计算过程仅几秒钟，这样做是可行的。在这短短的计算时间内，位置的变化量可以忽略。本文研究的算法的一个约束是最大计算时间不能超过20 s。其目的是为了适应多种水下作战系统。

2.算法实现

算法分为两大重要部分，它们是程序内独立的两个模块，这样保证了程序的可重用性和可维护性。

第一个模块为海军平台生成一个图，该图含有平台周围区域的地理数据和区域内障碍物的数据。这地理数据是从国际标准电子海图（ECDIS图型）提取的，并处理成数字地形模型。该过程是由剖面评算用电子海图分析器ESCAPE完成的。该程序从海图中获取给定区域的深度数据后生成光栅格式的地形图，如图1所示。光栅中的每一点表示一个深度值，因此整个区域都由深度值来描述。

图1 海图区域（左）转换为地形模型后的效果图（右）

这样的地形模型是生成图的基础。这些光栅点表示图的节点和边。节点为图的接合点，一条边连接两个接合点。边可以赋予权重以表示从起始节点到目标节点之间的距离，如图2所示。

节点               边             权重边

图2 描述节点和边的符号

图3 用图表说明地形模型

图4 对角线边

当地形模型转为图后，一个光栅点就对应一个节点，光栅点的深度值就表示从该点到相应节点的边的加权值，如图3所示。

图3上除了按沿直角运动外，还可以沿对角线运动。依照不同的角度（由两节点之间x和y的差值来决定），路径长度不同，因此边的权重也不同。当角度为45度时，目标节点的深1度值需要乘上，如图4所示。

为了寻找一条能避开岛屿等障碍物的路径，程序必须能确定是否达到了某一最小深度值。因此图上所有深度值都与最小深度比较。如果某一节点的深度比最小深度还深，该深度值将被定义为一个给定的值，比如1000，否则设置为1。这种区别对于路径规划算法来说是必要的。

除了（船或飞机）残骸等地理障碍物以外，石油平台和其他船只也需要一起考虑。因此在每个障碍物的周围定义一个危险区域。危险区域内的节点深度值都设置为1000。如果程序用于计算鱼雷射击诸元，目标船的探测范围也必须认为是障碍物。这种区域的深度值是可变的以便将探测距离定义为“可穿越”的障碍物。

图生成后就可以开始寻找从起点到目标点的最优路径，这个功能由第二个程序模块完成。根据给定的地理起始节点和目标节点位置以及地形模型的地理坐标，就可以用A*算法[2]计算最优路径。该算法来源于导航和机器人领域，在图格式中应用得很好。

算法原理如下：

算法首先建立“Open_List”和“Close_List”两张空列表。Open_List存储所有进入考虑视野但尚未处理的节点，一开始它只存储了起始节点。两个列表中的节点有三个数据域，其中d表示当前节点与起始点的距离，g表示与目标节点的估算距离，k表示其前驱节点的序号。对于起始节点s，定义d[s]=0和g[s]=0;对于其他节点，d和g的初始值为无穷大。所有节点的前驱节点为空。Close_List初始化为空列表。

算法依次考虑Open_List列表中d+g为最小的点。在第一步，该最小点就是起始点本身。首先把起始节点从Open_List列表删除后添加到Close_List列表。然后把起始节点的所有相邻节点加入到Open_List列表，对每一个节点计算到距离d和对应边权重值之和，然后在不考虑边权重的情况下估算到目标点的距离g。新得出来的值与邻节点对应值相比较，如果新值小，那么将用新的d和g代替原来的对应值，并把当前节点存储为邻节点的前驱节点。

当目标节点被添加到Close_List列表，算法结束。这时最佳的路径就可以从目标节点根据前驱节点从目标节点回溯到起始节点。

当最佳路径决定后，需要将其简化为航路点列表，因此对于最佳路径上的每一个节点，如果节点改变了路径方向就将其加入到航路点序列，这样就将所有节点转换为实际的地理位置。

若想定復杂，计算最佳路径的时间可能超过20秒。计算机系统的性能也会影响计算时间。为了满足时间约束，A*算法能加速，不足的是会降低规划路径的质量。在距离估算项乘以一个常数因子，计算速度就会增加，因子越大，计算速度越快。

3.测试结果

开发的算法进行了一系列测试。针对不同的想定，在德国Bight平台上已经完成功能等测试。目的是规划出鱼雷从我方船只到目标船只（用深灰色的圆做标记）的航行轨迹。图5提供了其中两种想定。黑色区域代表深度值在最小深度之下，被定义为威胁区域。灰色区域表示深度在我船深度之下，需要鱼雷改变航行深度。白色区域表示水深合适。圆的深灰色地区表示目标船的探测范围，红色线是计算得出的路径。

图5 German Bight试验结果

除了几个一般功能测试外，也对一些极端情形进行了测试。图6显示了从迷宫左下角出发到迷宫中心的路径，在这个测试中没有考虑时间限制。

图6 极端情况下的试验结果

此外还分析了A*算法的加速效果，在评估中用了几个不同的因子，如图7和图8所示。从图中可以明显看出，随着因子的增大，路径质量不断下降。因子从1.0增加到30时计算时间从14.9s减少到0.4s。经过几个系列测试分析后，选择1.5作为算法的加速因子，这一因子在不明显影响计算路径的质量的前提下大大缩短了计算时间。若计算时间超过给定值，程序会自动增加因子的大小。

图7 因子从1.0到1.5的加速测试

图8 因子从2.0到3.0的加速测试

4.结束语

程序的实现和测试都取得成功，它能计算出两个地理位置之间的最佳路径并能避开所有障碍物。

在绝大多数的实际想定中，计算最佳路径和相应的航路点列表的时间小于3s。就是对于军事应用，这一时间也是很理想了，因为手工计算要慢得多。在一些特例中，最佳路径的质量有所差别。加速因子取值为1.5时，A*算法在计算的時间和路径质量方面达到较好的平衡。但是因子依赖不同想定和图，在有些想定和图中，算法会扩展很多不必要的节点。因子取值越大，路径的质量差别越明显，如图7和图8所示。

在所有测试中，给定的20s时间约束存在2%的误差，若不存在路径，就将20.2s作为最大计算时间。这是A*算法中止执行的标准，如果计算时间超过这个值就认为不存在路径。A*算法操作的时间限制为20s，过了这个值就可以中止执行算法操作了。依赖于计算机系统性能的时间认为与A*算法没有关系。

程序在应用于海军平台前，还需要做一些修改，如对程序进行扩展以改进与海图的接口。根据路径质量要求，可以增加相应的曲线平滑算法，以尽量减少确定的路径与最优路径的差异。

参考文献

[1]ESCAPE V4（2005）;Wolter，Nils;ATLAS ELEKTRONIK GmbH.

[2]Graphentheoretische Konzepte und Algorithmen（2005）;Krumke.S.O.，Noltemeier，H.;Teubner Verlag.