中国指挥与控制学会会刊 
舰载机在航母甲板上的调度与转运是制约其出动能力的重要因素,更是甲板安全作业的隐患。目前,世界各国海军普遍采用人工转运,也就是由牵引车司机开车转运飞机。这种转运方式一方面占用大量航空部门人员的编制,另一方面对牵引车司机要求较高,要经过多年培养才能胜任。本研究致力于无人驾驶牵引模式,在该模式中,若甲板停机较多,如何确定舰载机在甲板的行进路径是问题的关键。
1 舰载机碰撞计算
1.1 障碍物描述
航母飞行甲板在飞行保障过程中会停放大量舰载机,包括临时停机、等待起飞等几种状态。舰载机在转运过程中的路径避碰,实际上就是计算与这些障碍飞机的间距,间距为零即为碰撞。在本研究中,各型舰载机实际存在高度差,但由于差值较小,加之船体晃动的原因,不会允许一架舰载机从另一架舰载机上方通过的情况,即甲板面的碰撞检测可以转化为平面碰撞检测问题。因此,本文采用多边形表示法描述平面内舰载机及障碍物。对于平面内的任意N边形P,可用式(1)表示[7] 图1 所示的多边形轮廓图表示,在数学上可用端点序列p表达如下
p={p1(x1,y1),…,pi(xi,yi),…,pn(xn,yn);i=1…n}
其中,P(x,y)是按逆(顺)时针方向排列的头尾相连的矢量端点的集合,且各矢量内部之间无交点。也就是说,对于甲板面停放的舰载机,其外形描述可用如
在实际计算中,由于甲板面舰载机型号较多,各型舰载机形状极不规则,多数需要采用凹多边形表示,这给计算带来极大复杂度。本文采用凸多边形包围盒的方法,降低碰撞计算复杂度。对于图1 所示的舰载机轮廓,可用图2 的凸多边形包围盒表示,其端点序列p'表达如式(3)所示。对于其他舰载机障碍物,也采用相同的描述方式。
1.2 碰撞检测法
1.2.1 边边检测法
采用多边形法表示舰载机后,其碰撞检测实际为组成多边形的各个边之间距离的检测。对于图3 所示的两型舰载机,五边形是舰载机战斗机,矩形是舰载机直升机,其分别用端点序列p={p1,p2,p3,p4,p5}和端点序列q={q1,q2,q3,q4}表示。
对于该两型舰载机的距离,可以用式(4)表示,也就是两多边形之间的距离取值为两多边形距离最近的边之间的距离。
Dmin= d(, )
当这一值小于安全距离时,舰载机发生碰撞。该碰撞检测计算可分为以下三步实现:
1)计算指定两边是否相交,若相交,两边距离为零;若不相交,距离为∞。
2)若不相交,计算两线段各个端点之间距离。
3)若不相交,计算每个端点到另一线段的垂足间距离,并判断垂足是否在另一线段上。
4)距离取为1)2)3)中的最小值。
以上三步计算是两多边形其中一对边的距离,要计算所有边相互间的距离后,可得出两多边形的距离,其碰撞检测计算复杂度为(p维度×q维度)。
1.2.2 边线检测法
本文采用一种边线检测法计算碰撞。其主要思想是通过计算路径中心线与障碍物的距离来得出碰撞结果,其关键点是多边形在移动过程中,位姿要保持恒定。对于舰载机在甲板面的移动,无论是自行滑动,还是牵引拖动,其运动姿态必然是机头向前,两翼最宽处的连线与中心线正交,如图4 所示。
五边形为移动中的舰载机,带实心箭头的虚线是其移动路径,沿该路径行驶时,五边形最宽处的宽度为2r,图中用带空心箭头的虚线表示。矩形为障碍舰载机,在边线碰撞检测法中,我们将矩形障碍物沿各个方向放大,放大数值为r,也就是五边形最宽处的一半,若设置安全距离δ,则放大数值为r+δ。然后,计算路径中心线与放大后的矩形是否相交,若相交,则发生碰撞,若不相交,则不碰撞。其计算步骤可用以下两步表示:
1)将障碍物按指定数值放大;
2)计算路径中心线与放大障碍物的各边是否相交。
多边形的放大方法,采用一般几何计算中向量平移计算即可。需要注意,这里是多边形各个边向外侧平移一定距离,不是多边形的顶点移动,顶点的移动距离数值要超过边移动的距离值。该碰撞检测方法迭代次数只与障碍物多边形的边数相关,其计算复杂度为(q维度)。
1.3 碰撞计算法
碰撞检测的核心是障碍物边与路径线的相交计算。本文采用求解非齐次线性方程组的方法,将两条直线方程联立,通过系数矩阵左除,得出直线交点。若不存在交点,则返回空。表达式如式(5)所示。
AX=B X=A\B
具体计算步骤分为三步实现:
1)求解非齐次线性方程组,得到直线交点,若无交点,返回空;
2)当障碍物边与路径线都不垂直于X轴时,判断交点横坐标是否落在两线段内部;
3)当障碍物边垂直于X轴时,判断交点纵坐标是否落在障碍物线段内部,判断交点横坐标是否落在路径线段内部;
4)当路径线垂直于X轴时,判断交点纵坐标是否落在路径线段内部,判断交点横坐标是否落在障碍物线段内部。
其中,2)3)4)中任何判断成立时,视为碰撞成立,应跳出迭代循环。
2 舰载机路径选择建模
根据上文的分析,舰载机在甲板面的移动可以视为多边形的甲板的移动和避碰问题,如图5 所示。P0是初始舰载机停机位,P1是目标舰载机停机位。舰载机从初始位置到目标位置的移动过程中,存在Q1、Q2和Q3三架障碍舰载机,矩形方框表示的是舰岛,始末停机位之间的实线。从初始位置到目标位置实际存在无穷条转运路线,本文的目标是要选择其中路径最短的一条。需要注意的是,两点之间线段最短,在实际计算过程中,必须将转运路径离散化,用多段直线路径的拼接来绘制整条路径。因此,舰载机路径选择问题实质上寻找使整条路径最短的多段直线转运路径,这些路径应满足一定的甲板约束条件。
综上,该模型的目标函数可以描述为:寻找长度代数和最小的转运路径线段序列。其约束条件应满足以下几方面:一是始末停机位应距离一个机位以上,当始末停机位间距过小时,实际行走路径为大弧度的曲线,相当于原地调整机位,这不属于本研究的范畴;二是始末停机位不在舰岛区域内部;三是各个路径线段不可交叉,按顺序排列,路径线段交叉不属于正常路径范围,应在迭代中直接排除;四是路径线段不与其他障碍飞机碰撞,不与舰岛发生碰撞。数学表达式如下:
目标函数: F=min
St: |A0-A1|>L
and
T(i)∩T(j)=∅ i,j∈n
and i∈n,k∈m
式中,T(i)表示舰载机路径线段序列,数量为n。A0表示初始停机位坐标,A1表示目标停机位坐标,L为舰载机长度。IL表示舰岛区域。PL(k)表示障碍飞机序列,数量为m。
3 舰载机路径选择计算
3.1 粒子群算法求解
对于上文中路径线段序列的计算,实际上是求各个线段的端点坐标。需要注意的是,线段序列的数量决定了舰载机的避障能力,但过多的路径线段会增加碰撞检测的计算量,本文根据航母飞行甲板实际情况,每条舰载机转运路径设置三个路径点,由四条路径线段构成。因此,该问题实际上是一种带有约束条件的组合优化问题,即:如何选取三个符合约束的中间点,使经过这三点的舰载机路径最短。
对于这种具有连续解的组合优化问题,采用粒子群算法较为合适[8]。该算法通过初期大量随机粒子,保证算法的全局性,通过中期各粒子不断向最优粒子靠近,保证算法的快速收敛性。同时,在解决组合优化问题时,该算法编码相对简单,尤其适合解空间为连续值的问题。
3.1.1 粒子编码
每个粒子实际就是一个舰载机转运路径中间点的组合,由于本文取三个路径中间点,每个点由(x,y)坐标构成,因此,每个粒子由3×2维矩阵[x1 y1;x2 y2;x3 y3]构成,其中,坐标的计算采用连续值计算,需要注意的是解空间问题。本文以俄式航母飞行甲板为参考,设置甲板最长处与最宽处为300 m×70 m,也就是图5 中的矩形边框区域。由于实际飞行甲板边界为图5 中深蓝色边框,即路径点应该在深蓝色边框内,因此,我们在数学模型中增加约束条件来限制解空间,表达式如下
A(i)∩BD(j)=∅ i∈ ,j∈
A(i)表示三个路径中间点坐标,BD(j)表示四块边界区域。在计算中同样采用碰撞检测的方式,计算路径是否与边界线发生碰撞,如发生碰撞,则路径中间点落在边界区域,跳出迭代循环。
3.1.2 算法流程
算法流程如下:
1)根据种群数量,初始化粒子位置、速度。采用随机散点方式,给50个3×2维矩阵赋值作为粒子位置,再给50个3×2维矩阵赋值作为速度,注意数值要在解空间内。同时,用目标函数计算粒子适应度值,初始化自身最优值与全局最优值。
2)采用式(12)计算每个粒子的速度,注意将速度限制在解空间范围内。
=w +c1×rand1×(- )+c2×rand2×(- )
式中,c1和c2是学习因子,c1代表向粒子自身最优值学习的权重,c2代表向所有粒子最优值学习的权重。
3)根据计算出的新速度,采用式(13)计算更新粒子的最新位置。
= +
4)根据每个粒子最新位置,利用目标函数计算适应度值,同时,更新个体历史最优值。
5)根据个体历史最优值,更新全局最优值,同时,保留最优值所对应的粒子。该粒子就是当前最优方案。
6)判断是否达到迭代次数,否则返回2)继续计算。
3.1.3 参数设置
种群数量不易太小,要防止搜索过程提前收敛,本文设置为50。迭代次数不易太多,否则会影响运算速度,先设置为200,后面根据收敛情况再进行调整。式(10)中的w表示惯性权重,其代表粒子要按原速度惯性飞一段后,再转为新速度,其值较大时,粒子全局搜索能力高,值较小时,局部搜索能力高。因此,本文采用线性递减的惯性权重值,前期值大,保证算法的全局性,后期值小,保证算法的收敛性,如式(14)所示[9]。
w=wmax-
本次设置为c1=1.7,c2=2,保证全局最优高于自身最优。
3.2 仿真结果
本文采用Matlab7.1编程,飞行甲板各舰载机初始位置按照图5 所示布置,舰载机描述采用多边形方法,其原始端点序列如式(15)所示。
p=
原始机位、目标机位、障碍机位采用机头坐标加机头角方式描述,信息如表1 所示。
表1 机位信息 |
| P0 | P1 | P2 | P3 | P4 | |
|---|---|---|---|---|---|
| x | 240 | 150 | 200 | 100 | 48 |
| y | 42 | 35 | 45 | 39 | 22 |
| θ | 180 | 230 | 180 | 180 | 230 |
结果如下:
1)连续优化计算10次,其结果如图6 所示。图中红色线为舰载机与障碍飞机轮廓,绿色线为障碍飞机按照边线检测法放大后的轮廓,黑色线为经过优化后的10条路径,可以清楚地看到,所有路径不与绿色轮廓线相交,表明本文碰撞检测方法符合实际路径需求。
2)连续优化50次,取其中最优路径如图7 所示,该路径为在此布列情况下的最短避碰路径,长度值为198.0 m,表明本文所采用的避碰算法及优化方法,能够用于飞行甲板转运辅助决策。
3)连续优化50次,将每次的最短路径显示如图8 所示,数值如表2 所示。50次平均路线距离为201.8 m,最大为207.6 m,最小为198.0 m,最优值浮动范围不超过9.6 m,变化范围较小。表明采用粒子群算法计算该碰撞问题偏差小,没有陷入局部收敛,算法全局性强。
表2 50次最短路径数值 |
| 序 号 | 距离 值 | 序 号 | 距离 值 | 序 号 | 距离 值 | 序 号 | 距离 值 | 序 号 | 距离 值 |
|---|---|---|---|---|---|---|---|---|---|
| 1 | 198.0 | 11 | 198.6 | 21 | 198.7 | 31 | 201.3 | 41 | 206.4 |
| 2 | 202.4 | 12 | 203.1 | 22 | 199.4 | 32 | 198.0 | 42 | 207.6 |
| 3 | 199.5 | 13 | 199.3 | 23 | 201.5 | 33 | 207.6 | 43 | 205.2 |
| 4 | 198.5 | 14 | 205.4 | 24 | 204.8 | 34 | 206.9 | 44 | 198.4 |
| 5 | 198.3 | 15 | 198.9 | 25 | 200.8 | 35 | 202.8 | 45 | 204.1 |
| 6 | 198.2 | 16 | 199.3 | 26 | 199.1 | 36 | 202.6 | 46 | 207.3 |
| 7 | 205.3 | 17 | 201.4 | 27 | 198.5 | 37 | 199.9 | 47 | 205.6 |
| 8 | 198.5 | 18 | 199.6 | 28 | 205.3 | 38 | 203.4 | 48 | 199.4 |
| 9 | 198.1 | 19 | 206.2 | 29 | 207.6 | 39 | 207.1 | 49 | 198.1 |
| 10 | 198.5 | 20 | 200.1 | 30 | 202.3 | 40 | 203.1 | 50 | 205.2 |
4)在种群取值50,迭代次数设置为200的情况下,连续优化10次,10次的收敛曲线如图9 所示。图中可以看出,10次的优化过程都在100到110代左右结束收敛,表明粒子群算法计算该碰撞问题收敛速度快,收敛一致性好,迭代次数设置合理。
4 结束语
本文针对舰载机在航母飞行甲板转运过程中,需要寻找一条最优行走路径的问题,采用平面多边形法描述舰载机,提出一种新的多边形碰撞检测方法,同时,将该方法运用于本文所建立舰载机飞行甲板转运数学模型,采用粒子群算法对模型进行优化计算,结果所得路径符合舰载机在飞行甲板的避碰要求及长度最短要求,表明本文所采用避碰算法及优化方法适用于航母飞行甲板辅助决策。