基于蚁群算法的舰载机甲板路径规划*

孙茂伟，范加利，高富东，王云翔

（海军航空大学（青岛校区）舰面航空保障与场站管理系，山东 青岛 266041）

0 引言

航母舰载机起飞前或着舰后在航母甲板上的移动是舰载机出动与回收作业中的一个重要环节。航母舰载机的出动与回收效率是决定航母作战能力的核心因素［1］，因此，提高舰载机在航母甲板上的移动效率是提高航母作战能力的有效途径。航母甲板空间狭小，存在如舰载机、舰面保障设施等经常发生位置变动的障碍物，为了使舰载机能够在甲板上安全、迅速地完成移动作业，通常从移动路径避障和移动路径距离优化两个方面进行舰载机甲板路径规划。

传统的人工路径规划方法效率低、精度差［2］，在一定程度上影响了舰载机的出动与回收效率。随着计算机技术与人工智能技术的发展，基于粒子群算法［3-4］、遗传算法［5-6］、蚁群算法［7-9］等智能算法的路径寻优成为了移动机器人路径规划的一个重要研究方向［10］。舰载机甲板路径规划即可视为平面移动机器人的路径规划问题［11］。韩维等采用粒子群算法实现舰载机舰面路径规划［12］；王云翔等采用离散粒子群算法对多机移动条件下的舰载机进行甲板路径规划［13］。本文采用具有正反馈、并行机制且鲁棒性强的蚁群算法作为舰载机甲板路径寻优算法，通过Dijkstra 算法［14］建立蚁群算法的路径寻优空间，在寻优过程中，对寻优路径进行包围盒区域扩展，完成碰撞检测，实现了安全避障前提下的舰载机甲板最短路径规划。

1 舰载机仿真模型与碰撞检测算法

舰载机位于甲板时有展翼、折翼两种状态，常见的舰载机形状如图1（a）、图1（b）所示。为简化计算并在尽量减小空间损失的前提下提高模型通用性，将舰载机仿真模型统一成如图1（c）所示的凸五边形。

图1 舰载机仿真模型示意图Fig.1 Schematic diagram of carrier-based aircraft simulation model

设舰载机仿真模型机身长度为l（l=l1+l2），宽度为d，在甲板平面坐标系中的位置如图2 所示。其中，O 为舰载机仿真模型的中心点；F1～F5为凸五边形的5 个端点；α 为舰载机姿态角，则舰载机仿真模型可表示为F（O，l1，l2，d，α）。

图2 甲板平面坐标系中的舰载机仿真模型示意图Fig.2 Schematic diagram of carrier-based aircraft simulation model in deck plane coordinate system

舰载机甲板路径规划方法通常是先将舰载机视为一个质点，通过路径规划算法，在舰载机起始位置和目标位置之间求解一条满足约束条件且指标最优的可行路径。实际舰载机在甲板上移动的过程中，必须避免与甲板障碍物之间产生摩擦、碰撞，因此，应当确保舰载机仿真模型沿着路径规划算法计算出的路径移动时，与障碍物模型无重叠部分。

如图3 所示，本文将以O 为圆心、r 为半径的圆形区域定义为舰载机F（O，l1，l2，d，α）的安全区域。

图3 舰载机安全区域示意图Fig.3 Schematic diagram of safety area for carrier-based aircraft

其中，区域半径r 为舰载机中心点O 到舰载机模型轮廓的最大距离（通常为l1）外加一定的安全缓冲距离δ。当甲板上的所有障碍物均在此安全区域之外时，视为舰载机F（O，l1，l2，d，α）未与障碍物发生碰撞。

如下页图4 所示，设一段舰载机甲板规划路径为起点S 到终点T 的直线段ST，舰载机F（O，l1，l2，d，α）移动时，中心点O 保持在线段ST 上，且α 为恒定值，使舰载机中轴线也始终保持在线段ST 上，则舰载机F（O，l1，l2，d，α）在路径ST 上的碰撞检测转化为判断以线段ST 为中心，向两边分别扩充距离r后构成的矩形包围盒与障碍物模型之间位置关系。将甲板上的非舰载机障碍物均简化为适当的凸多边形，则当路径ST 的矩形包围盒与甲板上的所有障碍物凸多边形无交集时，路径ST 通过碰撞检测。

图4 基于路径包围盒的碰撞检测示意图Fig.4 Schematic diagram of the collision detection method based on path bounding box

判断路径ST 矩形包围盒与障碍物多边形位置关系的步骤：

Step 1 采用向量法［15］判断路径ST 矩形包围盒的各条边与障碍物多边形各条边之间是否存在相交的情况，若存在，则路径ST 矩形包围盒与障碍物多边形有重叠部分；

Step 2 若不存在相交边，则继续判断路径ST矩形包围盒与障碍物多边形是否为包含关系。采用面积法［16］，从两个多边形上各选一点，分别判断该点是否包含于另一个多边形内，若有包含情况，则路径ST 矩形包围盒与障碍物多边形为包含关系，否则为不重叠关系。

2 Dijkstra 算法

Dijkstra 算法适用于有起点的节点间最短路径问题求解。设平面空间中有起点S、终点T 以及其他节点P1～Pn，若两点间不能直线可达，则设两点间距离为无穷大。Dijkstra 算法求解S 到T 间最短路径具体步骤如下：

Step 1 首先设置两个初始为空的点集A、B，点集A 用于存放算法求解过程中已求得与起点S 间最短路径的点，点集B 用于存放还未求得与起点S间最短路径的点；

Step 2 将起点S 置于点集A 中，表示其与自身最短路径已知且距离为0，其余各点P1～Pn、T 均置于点集B 中；

Step 3 分别计算点集B 中各点到点S 的距离并记录，记其中与起点S 距离最近的点为Pmin，与点S 的距离为dmin。将该点从点集B 移至点集A 中；

Step 4 分别计算点Pmin到点集B 中剩余各点的距离Δi，i=1～nB，nB为点集B 中点的个数。若：

式中，di为点集B 中第i 个点与起点S 的当前记录距离，则令：

Step 5 重复上述步骤Step 3～Step 4 直至终点T从点集B 移至点集A。此时，计算得到的终点T 与起点S 间的距离即为最短距离，经过的节点集合构成了Dijkstra 算法最短路径。

3 基于蚁群算法的舰载机甲板路径规划方法

蚁群算法是一种模拟蚂蚁觅食行为的智能算法，其基本原理是觅食的蚂蚁在经过的路径上分泌信息素，后来的蚂蚁优先选择信息素浓度高的路径，并在经过该路径时更新路径的信息素，从而在蚁群觅食过程中形成路径选择正反馈机制，进而蚂蚁选择较短路径的概率越来越大，最终逐步接近并得到寻优结果。

本文将蚁群算法应用于舰载机甲板路径规划中，求解能够通过碰撞检测的舰载机最短移动路径。为提高路径规划效率，先利用Dijkstra 算法在全局路径空间中进行初步寻优，得到次优路径和由次优路径所确定的局部路径寻优空间。将Dijkstra 算法的寻优结果作为蚁群算法的输入，进一步完成最优路径寻优。同时，在蚁群算法寻优过程中，本文引入基于路径包围盒的碰撞检测方法，将碰撞检测结果融入信息素的更新过程，实现避障前提下的最短路径寻优。

设舰载机起始位置为S，目标位置为T。基于蚁群算法的舰载机甲板路径规划方法具体步骤如下：

Step 1 Dijkstra 算法路径寻优。根据甲板舰面保障设施、甲板舰载机及其他障碍物的轮廓特征构建甲板障碍物凸多边形，如图4 中黑色区域。通过MAKLINK 图法［17］，利用各障碍物凸多边形的端点，在甲板平面区域中建立直线状网格，各网格线的中点{p1，p2，…}依次连接，构成舰载机的可行路径空间，并进行Dijkstra 算法寻优，得次优路径为S→P1→P2→…→Pk→T，次优路径对应的局部路径寻优空间为节点P1～Pk所在的各条连接线{L1，L2，…，Lk}。

Step 2 设置蚁群算法的基本参数。包括蚁群蚂蚁数量m、信息素重要程度参数a、距离因素重要程度参数b、转移概率阈值q0、信息素衰减率ρ、信息素初始值0、信息素强度常数Q 以及算法迭代次数N等。

Step 3 m 只蚂蚁各自完成一次从起始位置S 到目标位置T 的觅食过程。将Step 1 中Dijkstra 算法得出的连接线{L1，L2，…，Lk}各自均匀切分为v 段，则切分点构成了蚂蚁觅食时下一个目的节点的备选点集D。设蚂蚁当前在节点i 上，选择下个节点j时，策略如下：

产生［0，1］之间的一个随机数q，若q≤q0，则选取备选节点中信息素浓度和距离因素乘积最大的节点作为下一个节点，即：

若q＞q0，则依次计算当前节点i 到下一节点的备选集D 中各点的选择概率Pi，z：

采用轮盘赌法从备选集D 中，根据选择概率选出下一个节点j。

对该段路径进行基于路径包围盒的碰撞检测，得检测结果记为C：

记录路径距离di，j：

其中，dE表示两点间的欧式距离，+∞表示该路径因未通过碰撞检测而被视为不可通行路径。

按上述策略，m 只蚂蚁各自完成从起始位置S到目标位置T 的一次觅食过程。

Step 4 最短完整路径信息素更新。所有蚂蚁完成一次从起始位置S 到目标位置T 的觅食过程后，根据记录的各段路径长度和，选择所有蚂蚁走过的m 条完整路径中最短的一条，按如下策略更新该完整路径上每段路径的信息素：

式中，Δij=Q/Dmin，Dmin为最短完整路径总长度。

Step 5 重复Step 3～Step 4，直至达到算法最大迭代次数N，得到最优路径。

基于蚁群算法的舰载机甲板路径规划方法流程如图5 所示。

图5 基于蚁群算法的舰载机甲板路径规划方法流程图Fig.5 Flow chart of the path planning for carrier-based aircraft deck based on ant colony algorithm

4 仿真实验分析

本文以一个舰载机甲板调度模拟训练场为原型，建立Matlab 仿真场景，验证基于蚁群算法的舰载机甲板路径规划方法的有效性。

仿真场景：训练场地长度110 m，宽度70 m，设置停机位A1～A9、20 m×20 m 正方形舰面保障固定作业区域B1。视作业区域B1、停放在停机位A2上的舰载机F1和临时停止移动的舰载机F2为障碍物，测试舰载机Ft可按指定训练科目在训练场中的不同停机位之间移动。

设舰载机F1（A2，10 m，5 m，10 m，90°）、舰载机F2（［60 50］，10 m，5 m，10 m，0°）以及作业区域B1为障碍物区域，测试舰载机Ft的起点S 为停机位A8，目标位置T 为停机位A6。采用本文提出的基于蚁群算法的舰载机甲板路径规划方法进行路径规划。设置算法参数：蚂蚁数量m=20、信息素重要程度参数a=1、距离因素重要程度参数b=2、转移概率阈值q0=0.8、信息素衰减率ρ=0.1、信息素初始值0=0.000 5、信息素强度常数Q=1、算法迭代次数N=800，舰载机圆形安全区域的安全缓冲距离δ=l1×5%。仿真结果如图6、表1 所示，迭代过程如图7 所示。

图6 基于蚁群算法的舰载机甲板路径规划方法的路径规划结果Fig.6 Result of the path planning for carrier-based aircraft on deck based ant colony algorithm

图7 基于蚁群算法的舰载机甲板路径规划方法的迭代过程Fig.7 Iterative process of the path planning method for carrier-based aircraft deck based on ant colony algorithm

为比较算法效果，采用基于障碍物包围盒的碰撞检测方法，即将障碍物区域边界外扩安全区域半径r 的距离，再采用Dijkstra 算法与蚁群算法进行路径寻优，结果如图8、表1 所示。

图8 对比算法（采用基于障碍物包围盒的碰撞检测方法）的路径规划结果Fig.8 Path planning results of the comparison algorithm（using the collision detection method based on obstacle bounding box）

设临时停止移动的舰载机发生了位置变动，即变为F2（［60 40］，10 m，5 m，10 m，0°），采用本文提出的基于蚁群算法的舰载机甲板路径规划方法进行路径规划，结果如图9 所示，规划路径长度为66.736 6 m。

图9 障碍舰载机发生了位置变动后的仿真结果Fig.9 Simulation results when the position of the obstacle carrier-based aircraft changes

由图6 的仿真结果可知，本文提出的基于蚁群算法的舰载机甲板路径规划方法先通过Dijkstra 算法计算，得到了测试舰载机Ft从起点停机位A8到目标停机位A6的次优路径（图6 中Dijkstra 路径），在该次优路径所确定的局部寻优路径空间中，采用引入了基于路径包围盒碰撞检测的蚁群算法进行最优路径寻优，得到的最终规划路径（图6 中本文方法路径）明显优于通过Dijkstra 算法计算得到的次优路径，并且各段路径的包围盒与障碍物无任何重叠，确保了规划路径的安全。如图9 所示，当临时停止移动的舰载机F2发生了位置变动，本文提出的舰载机甲板路径规划方法仍然能够实现避障条件下的最短路径寻优。

对比图6、图8 及表1 数据，采用基于障碍物包围盒碰撞检测的对比方法是将障碍物的计算区域固定地扩大了，直接导致可规划路径空间减少；本文提出的舰载机甲板路径规划方法，则采用了基于路径包围盒的碰撞检测方法进行避障，用蚁群算法对每段路径寻优时，同时判断备选路径的安全扩展区域是否与障碍物有重叠，路径空间利用更加灵活。因此，能够在防止发生碰撞的前提下，节省出更多的可行路径空间，从而得到更短的有效规划路径。

5 结论

本文提出了一种基于蚁群算法的舰载机甲板路径规划方法。该方法先采用Dijkstra 算法计算次优路径并缩小最优路径寻优范围，再采用融合了基于路径包围盒碰撞检测的蚁群算法，实现避障与最短路径寻优。通过舰载机甲板调度模拟训练场仿真场景下的实验表明，本文提出的基于蚁群算法的舰载机甲板路径规划方法，能够在甲板作业空间狭小、障碍物经常发生位置变动的环境下，为舰载机在航母甲板上的移动作业提供安全、有效的最短路径规划方案。