面向机场飞行区异物探测的无人机巡检路径规划研究*

陈济达 汤新民 刘金安 丁文浩

（南京航空航天大学民航学院 南京 211106）

1 引言

机场异物是指出现在机场飞行区域且容易给飞机安全飞行带来威胁甚至造成损失的外来物质，包括动、植物，碎石块，人工物件等，国际上通常称为Foreign Object Debris，简称FOD；它还有另外一个含义，即Foreign Object Damage，指因为机场跑道异物入侵事件而导致的损失［1～2］。FOD 一直是影响通航机场正常安全运行的重要因素，每年都造成了难以计量的机场直接和间接损失。异物探测技术则是在这种背景下应运而生，主要通过各种技术手段对跑道进行检索，识别外来物质，反馈回终端统一处理。目前各个中小机场对于FOD 的防范大多是由工作人员完成，通常每天要对跑道进行4 次人工巡检［3］。但是人工巡检耗时耗力，效率低下并且很难保障异物完全被清除。近几年无人机发展十分迅猛，本文将无人机与FOD 探测系统相结合，提出一种面向机场飞行区异物探测的无人机巡检手段。无人机机场异物探测具有以下优势：能够动态巡逻跑道，及时发现FOD 并且发出报警；能够第一时间获得FOD 目标的精确定位；能够实时人工介入查看该地区的高分辨率的二维图像；比起人工巡检极大地提高了效率，比起其他FOD 系统，诸如激光雷达系统、热成像系统、视频摄像机，又极大地降低了采购，维修，保养成本。

与地面探测设备的情况相比，无人机的覆盖路径规划CPP（the coverage path planning）是较少研究的问题。一般无人机的CPP问题通常采用Zamboni或者螺旋搜索［4～6］，Maza 和 Ollero 只研究简化处理后的凸多边形的覆盖问题［7］，其他的如 Valente 和Franco等不管覆盖区域的形状是怎样，将覆盖区域用凸多边形的路径规划方法规划路径，接着规划剩余的凹多边形的剩余子区域［8～9］。Ji，Wang，Niu 和Shen 将凹多边形进行分解成为多个凸多边形［10］。在 Li，Chen 和 Wang 的研究中，人为规定了无人机规划路径的起始点，但是结束点是由算法计算得到，该方法的局限在于无人机停止的点是随机的，所以很可能停留在危险区域或者人无法靠近操作的区域。同时该论文提出无人机最小消耗功率的方法就是减少转弯次数，所以在覆盖路径规划时，主要确定最小转弯次数的巡检路径［11］。与此同时，万龙利用Velodyne VLP-16 三维激光和3D-NDT算法获得先验地图的基础上，运用改进的A*算法进行全局路径的寻优，结合对局部动态环境的感知与规划，实现飞行器基于先验环境固定高度自主飞行任务［12］；陈海等提出一种凸多边形区域的无人机覆盖航迹规划算法［13］。本文通过对飞行区边界进行建模，采用分块的思想，通过多种路径规划算法得出所需最短时间（最小代价）的路径，估算出无人机完成整个巡航过程所需的时间。最后以南京禄口机场为例，规划计算水平轨迹和速度剖面，计算航程及航程时间，并证明Z 字扫描算法在覆盖路径问题的优越性。

2 无人机巡检航线水平轨迹规划

2.1 机场巡检区域建模

机场主体部分一般分为跑道，滑行道，草坪，停机坪。跑道是供飞机起飞时加速和着陆时减速滑跑用的带状地面，一般民航机场的跑道宽45m 或60m（不包含道肩），滑行道是机场内供飞机滑行的规定通道，一般会连接各个性质不同的功能分区，其宽度在23m～30m 之间。综合考虑无人机巡检效率和FOD 威胁程度，选取跑道和连接滑行道部分作为无人机巡检的目标飞行区，而机坪滑行道以及停机坪部分则先不纳入考虑范围。本文以南京禄口机场为案例，图1是通过ARCGIS软件绘制的shp格式的南京禄口机场图［14］。shp格式文件是现在全世界通用的用来记录几何要素的空间信息的手段。

图1 南京禄口机场shp格式图

无人机在巡检过程中，假设无人机的云台摄像机拍摄的范围是一个半径为R 的圆形区域，本文取其中一个内接正方形，其中正方形的边长本文默认当无人机飞跃每一个方格的中心点时，能够完全覆盖这区域的所有的范围，因此路径规划问题表示成无人机飞过每一个方块中心的轨迹。

机场巡检属于检测环境已知，通过环境的栅格化，无人机和目标区域的位置可以用栅格的坐标来表示［15］。其中可行域用空白格表示，不可飞行区域用灰色格子，将目标区域用方格矩阵ln×m[aij]（可行域aij=0，不可行域aij=1）表示出来，对巡检区域进行分块处理。由于机场区域的特殊性，本文先判断跑道与主滑行道位置以及方向，然后对联络滑行道采用种子填充算法分别进行合并形成几个连通区域。基于目标区域的分块方法的流程如下。

1）比较矩阵X 和Y 方向上的方块数量，即判断n＞m 或是n＜m。跑道和主滑行道的方向和矩阵下标数值较小的方向一致。

2）沿着跑道方向，将该方向的每行或者每列所有元素累加求和，即

3）计算出所有求和等于零的项，并将相邻的行数或列数合并，查询到跑道与主滑行道的位置。

4）运用种子填充法搜寻各个联络滑行道的范围与位置。

（1）搜寻所有 i+1 或者 j+1 列的元素为 1 的值，在每一个间隔中随机选取一个元素为0 的坐标记为A（i+1，y）或者B（x，j+1）作为种子，并赋予其一个label，然后将该种子相邻的所有元素为0 的可行域方格都压入栈中；

（2）弹出栈顶元素，赋予其相同的label，然后再将与该栈顶元素相邻的所有元素为0 的方格都压入栈中；

（3）重复步骤（2），直到栈为空。

5）将跑道、主滑行道以及各个联络滑行道等各个连通区域进行编号。

3 无人机巡检航线路径规划

3.1 无人机飞行速度剖面

无人机在沿着规划路径巡航的时候，由于其自身飞行性能，在经过转折点时会有一个减速和加速的过程。为了简化无人机转弯问题，本文特作此假设：1）不考虑无人机的姿态操作，将无人机视为一个质点；2）在转弯过程中，其摄像装置的角度、姿态不受影响；3）忽略转弯过程中的高度变化。

通过将问题简化，本文讨论无人机转弯半径性能与实际扫描情况的关系。参考无人机的性能参数，将无人机转弯根据速度方向与航迹点连接的情况分为三种状态，第一种是当速度与航迹点连线夹角小于60°的时候，无人机在不减速的情况下正常过弯到下一个航迹点。第二种是当速度与航迹点连线夹角为60°～120°的时候，为了使无人机能够转过该航迹点指向下一个航迹点。此时，无人机的速度可以降到最小转弯半径所对应的速度，当速度方向指向下一个航迹点时再加速到巡航速度。当无人机的下一个目标点在速度方向的后方，即120°～180°在本文设定让无人机在到达该点后速度降为0，然后沿着下一个目标点方向在加速到匀速。

3.2 水平轨迹规划

通过查阅已有文献，可以采取两种方式进行路径规划，一是通过Zamboni 或者螺旋搜索按照规划路径的顺序将所有的航迹点全部遍历；第二是通过智能算法，为了避免陷入局部循序无解的情况，限制其求解范围，借鉴旅行商问题的思维，要求无人机在巡航时不允许重新走过遍历过的航迹点。

1）“Z”型扫描法

本论文研究的机场飞行区主要包括跑道，主滑行道，连通滑行道。通过第一步步骤将其栅格化后分块，扫描分块内部的航迹点再将不同分块连通起来。对于跑道和主滑行道这种规则矩形，根据平面二维坐标，计算x，y 方向上的距离，即xmax-xmin和ymax-ymin。

当xmax-xmin＞ymax-ymin时，就在跑道和主滑行道按照x方向进行Z字扫描；

当xmax-xmin＜ymax-ymin时，就在跑道和主滑行道按照y方向进行Z字扫描。

对于连通滑行道等不规则图形，为了保证能够对整个区域进行遍历，则直接按照上述步骤，以同样的方向对连通滑行道进行巡检。

根据无人机的速度剖面图，本文对其模型更进一步假设，无人机不减速过弯的情况下可以忽略弧线的长度，以直线做近似处理，无人机在速度降为νr和0 后，均能在ts时刻内转移到正确的方向。无人机在整个巡航过程中三种模式下转弯的次数分别为p1，p2，p3，其时间估算公式如下：

上述公式中，Δt2是无人机在模式2 转弯时的比正常巡航速度巡航多出来的时间，Δt3是无人机在模式3 转弯时的比正常巡航速度巡航多出来的时间。Pn是无人机要经过的航迹点，s是整个路径的长度。

2）基于遗传算法对飞行区目标区域的路径规划

为了保证无人机能够完全遍历所有的目标区域，以及寻找到优化后的巡检路径，本文参考旅行商问题用遗传算法对目标区域进行路径规划。作为整个优化目标，本文研究如何在无人机巡检效率最高的情况下，即飞行时间最短的数学模型如下所示：

在上述公式中，本文对问题进行一定程度的简化。定无人机巡航的速度是νc，最小转弯半径时对应的速度为νr，加速度和减速度是ɑ。ts是无人机在减速转弯时转到正确角度花费的时间。f(Pt)是0～1变量，用来判断无人机转弯的飞行模式。Pt是t 时刻无人机所在的坐标。θ是t 时刻无人机从上一个目标点来与到下一个目标点去的轨迹构成的角度。Ct是无人机飞行的时间成本，本模型中小于60°的转弯无人机不减速直接从该点经过，大于60°小于120°转弯无人机减速到最小转弯半径的速度过弯，大于120°的先减速到零然后加速飞行。

4 仿真案例

南京禄口机场长3600m，宽230m，采用10m×10m 的栅格网络对其进行划分。经过栅格化处理后的禄口机场图如图2所示。

图2 栅格化后的南京禄口机场图

通过Matlab对程序进行图像预处理，灰度化后二值化，最后变成一个只用0 和1 表示的矩阵，其中，0是可行域，1是非可行域。

图3 0-1矩阵形式的禄口机场示意图

采用遗传算法的步骤如下所示：

1）初始种群的产生。对于一个既定的连通区域，将里面所有方格在大矩阵的位置作为坐标存为一个数组Z，然后将其每个点计作一个数字1，2，3，……N，本文采用实数编码的方法。在一段染色体中，将Z 中的点随机放置在各个基因位，其染色体如图4。

图4 染色体编码示意图

在新一代的群体构成方法中，出于对性能考虑，选择保留一个最好的父串的最佳保留群体构造方式，在初代的选择，每一代的选择交叉、变异都使用了精英保留的思想。

2）适应度的计算。对整个目标区域用10m*10m 的方格划分，按照上述优化模型计算适应度函数，同时设定无人机巡航的速度是5m/s，最小转弯半径对应的速度是3m/s，加速度是5m/s2，无人机在降速转弯时能在3s内转到合适的角度。

3）选择过程。用随机方法产生初始种群，适应度比例选择，（精英保留）产生新一代种群。为了使高适应度个体的基因有更高的概率遗传给下一代，采用赌盘选择算子作为本实验的选择函数。

4）交叉过程。交叉概率为0.5，首先保留精英个体，之后其他个体采用算术重组，每个父代的基因随机打乱顺序重组交叉。

5）变异过程。变异概率是0.05，首先保留精英个体中最优个体不发生变异，之后采用对换变异的策略，通过随机选择串中的两个位点进行变异，之后再对变异后的个体进行两次适应度评估，若小于变异前的适应度则再变异。

最后让种群迭代到设定的迭代数，结束遗传操作，得到一个近似最优值。通过遗传算法仿真得到的无人机巡检最少时间为392.15s。迭代次数设置五千次，整个迭代时间花费9min28s。得到的路径如图5所示。

采用Z型扫描的步骤如下。

1）从整个机场目标飞行区取出选中块内所有点的坐标，并优先按照行坐标的大小由小到大，再按照列坐标的大小从小到大依次排列。

2）任意选择奇数或者偶数行，将该行（列）的排列顺序重新通过冒泡排序法按照列（行）的从大到小排列。

图5 仿真得到5000次迭代的遗传算法规划路径

3）将所有的点按照顺序连接起来，参照上述遗传算法中规定的无人机飞行性能。

图6 “Z”型扫描规划路径

Z 字算法时间得到的无人机巡检时间为313.62s。整个路径规划过程共花费了3s，得到的路径图如图6所示。

表2 遗传算法和“Z”字扫描算法的性能对比

在本次仿真中，巡检时间的一个重要影响因素就是无人机转弯次数。遗传算法虽然以最短巡检时间作为优化目标，但是由于遗传算法的局限性，陷入局部优化的遗传算法在后期迭代中很难减少转弯次数，导致表征巡检时间的适应度函数下降速度越来越慢。而且遗传算法规划路径的原理类似用穷举的办法寻找更优化的路径，所以整个计算机计算过程十分缓慢。而“Z”型算法没有迭代过程，其路径是按照固定的规律寻找的，所以转弯次数是固定而且极少的，故此算法的路径规划速度快，无人机巡检时间也花费的比较少。

5 结语

本文开展了面向机场飞行区异物探测的无人机巡检路径规划研究，将需要巡检区域的坐标经过转化成二维直角坐标并记录下来。通过对目标区域的栅格化和矩阵化，将机场目标区域分块成为跑道，主滑行道和各段连通滑行道，随机调用一组数据作为仿真数据。

通过遗传算法和“Z”字扫描两种方法对取得的数据进行路径规划仿真，通过第四部分仿真结果来看，“Z”型扫描所需要的规划时间更短，无人机转弯次数更少，规划效果更好，无人机飞行时间短，所以建议选用“Z”字算法作为机场飞行区异物探测的无人机路径规划方法。