无人机集群巡检道路的航线规划与分布式机场选址方法

叶深文，张 钢，罗志勇

（1.广东工业大学 自动化学院, 广东 广州 510006；2.广州市优飞信息科技有限公司, 广东 广州 510630）

道路的路面状况对于交通安全性具有至关重要的影响。为了保障路面质量、提高安全性，道路管理部门需要经常性进行巡检和维护[1]。目前主要通过人工巡检的方式来监测道路状况，但是这种监测方式极其耗时耗力[2]。多旋翼无人机具有重量轻、机动性强和成本低等特点，采用无人机巡检道路成为道路巡检的主要趋势之一[3]。然而，当前无人机集群巡检道路普遍存在无航线规划或规划困难、无人机利用率不均衡、分布式机场选址困难等问题。由此可见，无人机巡检道路的航线规划与分布式机场选址是实现无人机集群全自主巡检道路的关键与难点之一。

无人机的航线规划主要包括2种情况：无人机实时航线规划和无人机离线航线规划。无人机实时航线规划是指在无人机移动时规划并更新航线。在无人机实时航线规划方面，在国外，Duhayyim等[4]采用6 G无人机通信路由规划技术，使6 G的无人机网络高效地收集数据和规划航线。Lee等[5]研究边缘计算系统，让无人机在应对不断变化的环境条件时具有更大的灵活性。在国内，Wang等[6]引入了一个具有时变效益的团队定向运动弧形路线概念，研究了一种考虑监控需求时空变化的路线规划方法。Zhou等[7]提出了一种三维空间仿生路径规划算法，解决了环境地图未知的情况下无人机的动态避障路径规划问题。无人机离线航线规划是指无人机在移动前就已规划好完整的航线。在国外，Cho等[8]提出了一种在多个异构无人机情况下，在最短时间内生成覆盖所有生成节点搜索路径的方法。Phalapanyakoon等[9]以确定要部署的无人机数量和飞行路径为目标，研究了在任务时间和电池容量有限的约束下，每轮无人机有多次行程的路径规划问题。在国内， Xie等[10]针对多个区域的覆盖路径规划问题，并考虑具有能量约束的多无人机，提出了分支定界的遗传算法。Zhang等[11]提出了一种混合差分进化算法，为复杂三维环境中的固定翼无人机生成高质量、可行的航路。这些研究主要以获得无人机最短航线为规划目标，而忽略无人机的均衡使用等其他目标，且没有融合机场选址问题。

机场选址是一个涉及多方面因素的优化决策问题。当前关于机场选址的研究主要集中在民用机场选址方面。在国外，Alves等[12]提出了一种选址方法，完善选址标准的框架并提供更客观的决策过程。Erkan等[13]利用地理信息系统确定合适的机场选址，考虑了23个标准，采用层次分析法和秩次质心法选择最佳机场地址。Aydin等[14]为一家低成本航空公司制定了一个指导框架，供其在土耳其境内寻找一个枢纽机场位置，以满足需求并吸引新乘客。在国内，Zhao等[15]根据大连市候鸟的详细调查数据，评估了不同选址方案对鸟类生态的影响。Han等[16]基于GeoSOT-3D全球细分网格模型，提出了一个应急机场选址方法，证明了离散全球网格系统作为选址空间数据结构具有良好的适用性。Liao等[17]引入模糊决策理论评估不同的机场选址方案，并通过2个三角模糊数的差来定义方案之间的优势度。由于民用机场严重受制于周围环境，因此这些研究在机场选址时主要考虑噪声、生态、电磁辐射等多方面的因素。相对而言，无人机的分布式机场在选址方面对环境的要求较为宽松，更注重机场集群的利用率、巡检周期等。目前，关于无人机分布式机场选址的研究甚为罕见。

为此，本文提出了无人机巡检道路的航线规划与分布式机场选址方法。首先，构建了巡检地图，去除巡检目标区域外的多余信息。其次，构建多目标优化函数，将航线规划问题和机场选址问题放在统一的框架下解决。再次，基于粒子群优化方法的思想，重新设计粒子的编码方法、更新规则和解码方法，并用于解决无人机道路巡检的航线规划和机场选址问题。

1 研究架构

本文的研究架构如图1所示。

图1 总体架构设计Fig.1 Overall architecture design

由图1可知，无人机航线规划与分布式机场选址的方法总体架构包括巡检地图的构建、道路巡检航线模型的构建、粒子编码/解码的方法和实验及对比分析4部分。

在构建巡检地图部分，本文在收集巡检目标区域的地图后，通过分离目标区域的图层，去除巡检目标区域外的多余信息。然后通过设置机场候选点、拟合巡检道路和划分巡检道路与节点，简化目标区域错综复杂的道路，提供机场的候选地址。

在构建航线规划与机场选址的数学模型部分，根据道路巡检的实际需求，构建目标函数和约束条件，获得特定无人机数量下的巡检优化模型。

在算法部分，本文改进了粒子编码和粒子更新规则，并设计了粒子解码方式，使单个粒子包含航线规划方案和机场选址方案，探索特定无人机数量下最优的航线方案和机场选址方案。

在实验与分析部分，本文设计了2个指标以评价航线规划的效果。

2 构建巡检地图

本文以番禺区为实例展示如何解决航线规划及机场选址问题。

2.1 目标区域图层的分离

本文构建的番禺区道路巡检地图，如图2所示。收集的番禺区地图如图2(a) 所示，经过手工处理结果如图2(b) 所示。

图2 巡检地图的构建Fig.2 Inspection map construction

2.2 机场候选点的设置

由于省道和县道的网络复杂程度远高于高速公路网络，因此本文将省道和县道作为主要研究对象。

首先，本文在抠取的番禺区地图上沿着各个道路每隔3 km布点，得到机场候选点，如图2(c) 所示。候选点间距为3 km的原因在于，这个间距既可避免机场候选点间隔过大而使拟合的道路与实际的道路差异过大，也防止机场候选点间隔距离过小而增加算法计算时间。然后，收集各个机场候选点的坐标并对其编号。接着标记各个候选点对应的编号，如图2(d)所示。其中，横纵轴上的数字代表横纵坐标，坐标轴上的单位1表示2.22 km，以图的左下角为原点，各个候选点的位置由对应的横纵坐标表示。

2.3 巡检道路的拟合

在机场候选点的设置图上，本文沿着道路连接各个候选点画出折线段，以此拟合巡检道路，如图2(e)所示。其中，番禺区需要巡检的道路总长为888.19 km。

2.4 巡检道路与节点的划分

为了简化模型，本文将道路分岔口和道路的终点作为一个节点，并将节点画黑，则各个巡检道路都由折线段及其两端的节点构成，由此划分巡检道路与节点，得到无人机的必经路径，如图2(f) 所示。

3 构建优化模型

3.1 目标函数

本文将航线总里程最小和无人机的平均利用率最高作为目标函数。

3.1.1目标函数1：航线总里程最少

全域巡检周期内的航线总里程如式(1) 所示。

式中：L为无人机飞行的总里程，di为第i架无人机在完成全域巡检的1个周期内飞行总里程，n为无人机的总数量。di可由式(2) 求出。

式中：xj、yj和xj+1、yj+1分别为第i架无人机航线里相邻候选点的横纵坐标；Ms为将地图上的距离换算成实际里程，由于坐标轴上的1个单位表示2.22 km，因此Ms可由式(3) 求出。

3.1.2目标函数2：无人机的平均利用率最均衡

本文采用各个无人机飞行总里程的方差来表示无人机的平均利用率。飞行总里程的方差越小，说明在1个周期内各个无人机飞行总里程的差异越小，即无人机使用越均衡。无人机飞行总里程的方差σ2可由式(4) 得出。

式中：d为di的平均值，可由式(5) 得出。

3.2 约束条件

3.2.1约束1：各个航线里相邻机场间的距离

本文使用广州优飞信息科技有限公司的U880无人机进行道路巡检。该无人机平均飞行速度可达50 km/h，巡航时长为55 min。为此，本文设定无人机的飞行速度为50 km/h，每次飞行40 min，即无人机每个架次飞行30 km左右。考虑到顺风与逆风等因素，无人机实际飞行里程可能不足30 km。鉴于各个机场候选点的间隔距离为3 km，为减小求解空间，本文将各个航线里相邻机场之间的最大距离约束为30 km，最小距离约束为27 km，即约束条件为

式中：Lab为各个航线里相邻机场a和机场b之间的航线距离，可由式(7) 求出。

式中：xk、yk和xk+1、yk+1分别为机场a和机场b间航线里的相邻候选点的横纵坐标。

3.2.2约束2：巡检航线的重复度

巡检航线重复度表示在1架无人机的巡检航线内，重复巡检道路的里程在该巡检航线总里程所占的比重。ρi表示第i架无人机的巡检航线重复度，可由式(8) 表示。

为使巡检航线重复度尽量低，本文做出如下约束：

式中：xu、yu和xu+1、yu+1分别为第i架无人机航线里重复巡检道路的相邻候选点的横、纵坐标。

3.3 航线规划模型的建立

综合上述的目标函数与约束条件，可得完整的数学模型，如式(11)所示。

4 粒子编码、更新和解码方法

粒子群算法是模拟鸟群觅食行为的优化算法，其通过个体间的信息交流与协作寻找全局最优解[18]。根据粒子群算法具有收敛速度快、容易实现、依赖参数少和对初值不敏感等特点[19]，本文采用粒子群算法解决该优化问题。为使1个粒子代表1个可行解，本文提出了适合于航线规划和机场选址的粒子编码、更新和解码方法。

4.1 编码方法

本文的粒子编码示意图如图3所示。

图3 粒子编码Fig.3 Particle encoding

本文将各个航线用无人机经过的候选点序列来表示，如： 3 →5 →4 →···。对于有n架无人机的航线方案，能得到n条候选点序列。将n条候选点序列合并成1条序列，以此得到粒子的编码。其中，bp为断点，用于分隔无人机集群的航线。

4.2 更新方法

为使各个粒子能随机规划航线和选择机场地址，本文提出如下粒子更新方法，使粒子能不断被更新筛选。

(1) 位置相减⊕ ：位置相减等于速度，若两位置分别为x、y，则

(2) 速度相加⊕：速度相加等于新的速度，若两速度分别为v=a→b，w=x→y，则

(3) 位置与速度相加⊕：位置与速度相加等于新的位置，假设位置为a，速度为v=x→y，则

式中：γ为一个随机的位置。

(4) 速度乘系数 ⊗：系数与速度相乘等于新的速度，其中，系数c∈[0,1]，d为(0,1) 之间的随机数。若速度为v=x→y，则

定义粒子的速度和位置更新公式为式(16)和(17)。

式中：xk+1为更新后的粒子位置，为粒子的历史最优解，为种群最优解，R为[0,1]之间的随机数。

4.3 解码方法

4.3.1直接解码直接解码用于提取粒子编码中的航线规划方案。由于粒子编码为无人机集群的航线的集合，因此可以直接解码，并根据断点拆分粒子编码，得到无人机集群的航线规划方案，如图4所示。

图4 直接解码Fig.4 Direct particle decoding

4.3.2间接解码间接解码用于提取粒子编码中的机场选址方案。该解码方式对得到的航线规划方案，先在各航线起飞点设置1个机场，然后根据各航线相邻机场的距离约束，逐步提取出符合约束的机场候选点并将其作为机场选址，以此得到机场选址方案，如图5所示。其中，Di为符合约束的距离，红框标出的数字为被选作机场地址的机场候选点序号。

图5 间接解码Fig.5 Indirect particle decoding

5 实验及对比分析

5.1 实验环境

实验环境的硬件配置为Intel(R) Core(TM) i5-7300HQ CPU @2.50GHz，8 GB RAM，软件环境配置为Windows 10企业版，采用Python 3.9编程实现算法。

4）从剖面上看，边坡支护以后形成的位移变形影响范围主要是集中在边坡的中上部，其影响深度主要分布在表部范围，其变形量值的大小为毫米级，体现了加固以后的效果。

5.2 评价指标

5.2.1无人机利用均衡率

无人机利用均衡率β定义为：在一次全域巡检的周期中，无人机巡检的最短里程与最长里程的比值。

若β接近于1，说明各个航线里程差异不大，无人机利用均衡率较高。若β远小于1，说明最短的航线里程远小于最长的航线里程，无人机利用率较低。

5.2.2无人机航线总里程优化率

无人机航线总里程优化率ηL定义为：在完成一次全域巡检的周期内，需要巡检路径的总里程与该周期内的无人机飞行总里程的比值。

式中：l为需要巡检路径的总里程。以番禺区为案例，全域需要巡检的道路总长为888.19 km。

若ηL越接近于1，说明在一个巡检周期内无人机的飞行总里程越短，航线总里程优化率越高。

5.3 实验方案设计

本文设计的实验方案如下。

(1) 可行性实验。

实验1：本文方法能够计算得出较为合理的航线规划方案和机场选址结果，则可以验证本文提出的方法具有可行性。

(2) 性能实验。

实验2：揭示无人机利用均衡程度与无人机数量的相关性。

实验3：揭示航线总里程优化率与无人机数量的相关性。

5.4 实验结果与分析

5.4.1实验1的结果与分析

实验步骤如下。

(1) 通过本文所提方法，分别探索了5，10，20架无人机情况下的优化问题，得到最优粒子。

(2) 通过解码最优粒子，得到无人机的航线规划方案和机场的选址方案。

实验结果如图6和图7所示。

图6 航线规划方案Fig.6 Route planning results

图7 机场选址方案Fig.7 Airport site selection results

其中，绿色的线表示需要巡检的道路，红色的线表示1次全域巡检周期内重复巡检的道路，蓝色的线表示经过算法规划得到的无人机航线。由图6可知，本文方法规划的无人机航线覆盖了全域所有的道路，验证了本文的方法能较合理地规划全域巡检的航线，具有航线规划的可行性。

在图7中，绿色的线代表需要巡检的道路。其中，蓝色的三角形代表在1次全域巡检周期内只被使用1次的机场，红色的圆形代表1次全域巡检周期内被使用多次的机场。由图7可知，机场的选址均在规划的航线附近，且不同无人机数量情况下的机场选址均有被重复利用的机场，减少了机场数量和建设成本，验证了本文提出的方法能较合理地选择机场地址，具有机场选址的可行性。

5.4.2实验2的结果与分析

实验步骤如下。

(1) 通过本文所提方法，分别探索了1～20架无人机情况下的优化问题，得到20个最优粒子。

(2) 解码20个最优粒子，得到不同无人机数量下的航线规划方案。

(3) 根据各个航线方案，计算并收集不同无人机数量下的无人机利用均衡率。

(4) 对比不同无人机数量下的无人机利用均衡率，分析不同无人机数量下，无人机利用的均衡程度。

实验结果如图8所示。

图8 不同无人机数量下，无人机利用均衡率折线图Fig.8 The line chart of the balanced utilization rate of UAVs under different number of UAVs

由图8可知，随着无人机数量的增加，无人机利用均衡率逐渐下降，最低为73.74%，并且最后在76%左右波动，趋于稳定。由此可见，通过本文所提出的方法，在不同无人机数量下得到的最优航线规划方案，无人机利用的均衡程度都处于较高水平。

5.4.3实验3的结果与分析

实验步骤如下。

(1) 根据实验2第(1) 、(2) 步得到的20个航线规划方案，计算并收集不同无人机数量下的航线总里程优化率。

(2) 对比在不同无人机数量下的航线总里程优化率，分析无人机航线的优化程度。

实验结果如图9所示。

图9 不同无人机数量下，无人机航线总里程优化率折线图Fig.9 The line chart of the optimization rate of the total mileage of the routes under different number of UAVs

由图9可知，随着无人机数量的增加，无人机的航线总里程优化率虽然略有降低，但降低的幅度不大。总体而言，航线总里程优化率在76%处上下波动。由此可见，无论无人机数量是多少，本文方法规划得到的航线方案都能具有一致良好的航线总里程优化效果。

6 结论

当前无人机巡检道路普遍存在无航线规划或规划困难、难以均衡使用各巡检无人机、 难以确定分布式机场地址等问题。为此，本文提出了一种无人机巡检道路的航线规划与分布式机场选址方法，并较为全面系统地评估了该方法的性能。

本文的主要贡献有：(1) 基于粒子群优化方法的思路，本文提出了融合航线优化与机场选址的粒子编码方法、更新规则和解码方法；(2) 实现了巡检航线总里程数尽量短、无人机使用率尽量均衡的多目标优化；(3) 提出了较为全面的评价指标，用于评价航线规划及机场选址的效果。

实验结果表明：(1) 采用本文的方法，优化后的巡检航线重复部分低于总里程的7%，无人机利用均衡率在75%以上。(2) 优化后,分布式机场的重复利用率得到显著提高。

本文对于无人机集群的全自主巡检具有重要意义。下一步将展开无人机巡检道路的排班方法研究。