海上无人机多机协同巡检航迹规划方法

李 果，秦筱楲，郝贵斌，蔡 超，李鹏展

（1.航天科工海鹰集团有限公司，北京 100070；2.华中科技大学人工智能与自动化学院，武汉 430030）

0 引言

随着无人机（unmanned aerial vehicle，UAV）技术的不断进步，无人机已被广泛应用于海洋资源管理、海上安全、环境监测、目标详查等领域[1]。海上无人机的主要作业任务是对在指定海域上空抵近需要详查的目标点进行巡检。在无人机巡检过程中，航迹规划是无人机海上巡检的重要组成部分，需要根据无人机的性能参数设定起飞后的巡航路线，确保无人机在可控状态下能够完成指定海域的巡检作业[2]。考虑到海面环境复杂，当存在多个待详查目标时，无人机要根据已知的或由本身载荷得到的各目标位置，考虑能耗、载荷有效范围等条件约束，确定至少需要配备的无人机数量，并给出较优的无人机调度策略，规划出每一架无人机的航线，确保以最优的代价协同作业完成巡检任务[3-5]。

本文通过对海上无人机协同规划整体流程进行研究分析，针对静态、动态2 种不同的场景，通过构建静态问题和动态问题模型，分别进行多无人机航迹协同规划，并给出多无人机航迹协同规划的最优方案和仿真结果。

1 海上无人机协同规划流程

海上无人机协同航迹规划问题本质上是具有约束条件的最优化求解，旨在解决多架无人机在目标区域内从起始点出发，以尽可能小的代价规划出尽可能优的航迹组的问题[6-8]。采用基于图的建模方法是无人机对目标区域进行搜索活动是否合理有效的前提[9]：首先，根据指定作业海域栅格图，采用基于图的建模方法对海域地图进行分区，并对每个分区采用栅格化的网络图进行表达，对不确定的目标区域环境信息进行合理的描述，有利于规划不同类型无人机的作业轨迹；其次，假设在进行搜索行动时，无人机具有自主避障的功能，而且可以及时获取其他无人机的实时信息，针对每个分区，根据无人机的类型、其他无人机信息及无人机机场分布情况，求解出最佳的巡航方案。

海上无人机巡检协同规划分为静态场景规划和动态场景规划，其整体规划流程如图1 所示。从图1可以看出：静态场景下，无人机巡航轨迹规划的目标是为每架无人机划分作业区域、生成作业路径，使得整个巡检作业的航迹长度代价与作业时间代价最小；而动态场景下，无人机巡航轨迹规划需针对不同的突发状况建立对应的场景模型和求解算法，评估不同突发场景下最佳的动态调整方案。动态问题求解后，会将求解的方案重新返回到静态问题模型中，无人机按照新的静态航线飞行，再次遇到动态问题则重复上述步骤，实现动态调整，保证无人机的正常作业。

图1 海上无人机巡检协同规划整体流程图Fig.1 Overall flowchart for collaborative planning and inspection of UAVs

2 基于分支定界法的静态场景无人机巡检航迹规划

海上无人机静态场景规划是指在不考虑海面上的突发状况情况下，按照指定的作业海域，根据无人机的最大单位巡检范围和机场位置等信息，规划出不同海域的无人机巡检路径，需在无人机起飞前规划出巡检航迹[10]。

考虑到无人机能耗的关系，每个海域往往不能由1 架无人机完成所有巡检，此时需要不同的无人机在不同的子区合力协同完成该海域的巡检任务。每一架无人机在各自巡检子区内按照S型飞行路径进行作业巡检，在给定的海域栅格图上需要确定的是每一架无人机的起始巡航位置、转弯机动位置及最后的返航位置（图2）。

图2 静态场景航轨规划示意图Fig.2 Schematic diagram of path planning in static condition

针对静态场景规划建立静态问题模型，通过输入无人机数量、属性（飞行速度、能耗、最大飞行里程、最大起飞质量、巡检半径）、机场位置（坐标）、机场各类型无人机数量、机场容量、海域栅格图、海域最低覆盖率、巡检时间窗要求（有效巡检时间）等参数，为每架无人机划分作业区域，然后生成作业路径，使得整个巡检作业的航迹长度代价与作业时间代价最小，即最小化M。

静态场景航路规划方案的目标函数为：

其中，约束条件如下：

式（1）～（6）中：M为无人机的整体航路长度代价和协同巡检的有效时间的加权和；L为n架无人机的整体航路长度代价；te为n架无人机协同巡检的有效时间；s为每架无人机巡检区域的面积；vi,max为无人机的最大巡航速度；pi为每架无人机的巡检覆盖率；Ri为无人机的最大航程；wi为每架无人机载荷传感器的探测范围；ti为第i架无人机的传感器有效工作时间；k1、k2分别为航路长度代价和时间代价的加权系数，且满足k1+k2=1的条件。

静态场景下的无人机巡航路径规划隶属全局路径规划，既需考虑约束条件（如飞机性能限制、任务约束等），又需考虑性能指标（如按照规定时间到达、飞行时间最短、任务效能最高等）。本文采用分支定界算法（branch and bound method）框架[11]（图3），通过将静态场下的全覆盖问题进行混合整数规划模型建模，并使用cplex、gurobi等求解器最小化目标函数（式1），从而进行规划问题的最优求解。

图3 分支定界算法流程图Fig.3 Flowchart of branch and bound method

运用上述方法进行海上无人机巡检系统仿真，设定静态场景下设计规划的无人机规模为50架次，海域的最低覆盖率为90%，整体模型的求解时间不超过30 s，则可以在20 s 内给出可行的多无人机协调巡检航迹规划方案。

3 基于启发式算法的动态场景无人机巡检航迹规划

海上无人机动态场景规划是指无人机在巡检过程中，遇到海面上的突发状况，例如：由于海面上空的天气因素影响，使得设定的飞行路径的部分轨迹和极端天气发生区域重合，为减少风险，此时需要根据现场情况局部动态调整原有飞行路径，避免无人机直接穿越该区域；在海面巡检过程中，发现目标并需要对目标进行连续跟监，或者遇到其他海上环境变化时，同样需要动态调整无人机的局部路径，决策无人机飞行路径，并满足指定海域的巡检要求[12-13]。因此，面向动态场景的航迹重规划问题需着重考虑2 个方面：一是根据实时环境信息进行避障规划，避障结束后能返回预设航迹继续飞行；二是出现突发障碍物时，无人机能够综合当前位置和环境信息，重新规划航迹以规避障碍物[14]。

动态场景无人机的路径规划主要是对时效性要求比较高，要求算法模型能够快速给出1 个可行方案。在动态场景下，无人机先按照静态场景下事先规划好的路径进行巡检，遇到突发情况，则会根据突发事件的场景触发不同的动态问题模型。每个模型都需设计独有的目标函数，用于评估不同场景下最佳的动态调整方案。

对动态场景无人机巡航轨迹规划建立动态问题模型，主要针对气象变化、连续跟踪、海域变化等突发场景。

3.1 气象变化场景

气象变化场景是指无人机在按照静态场景规划的航线巡检过程中，突发遇到极端恶劣天气情况。此时无人机会自动获取极端天气的区域及此时所有无人机的飞行位置，及时调整事先规划好的静态航迹，既要避开极端天气区域，又要完成巡检作业。

不考虑气象变化的静态场景规划的航线巡检方案如图4所示。此时，假定在静态场景下，该海域最佳的无人机数量为2架，使用蓝色和绿色无人机各1架，每架无人机分别从2 个机场起飞后，各自按照设定好的S型轨迹完成巡检，最后返回各自的机场。

图4 气象变化场景下动态调整前的无人机航线图Fig.4 Planning path of UAVs before dynamic adjustments under changing meteorological conditions

当无人机飞行过程中遇到雷暴等极端天气时，触发整体流程图（图1）中动态场景里的气象变化场景模型。该场景根据当前无人机的航线任务和各自的位置信息，通过引入发生极端天气海域栅格图、静态规划下的所有参数、所有无人机位置信息（包含机场内的无人机和正在执行任务的无人机）、无人机的电量信息、无人机的任务信息等约束条件，建立气象变化场景问题模型进行动态调整，重新调整局部航迹。

为节约能耗，无人机的巡检总时间越短越好。同时在天气恶劣的情况下，考虑无人机的安全性，要求在外执行无人机的数量越少越好，所以气象变化场景下的航路规划的目标函数应设计为使得无人机在完成任务的基础上巡检时间最小且执行任务的无人机数量最少，即最小化Q：

式（7）中：Q为无人机的巡检时间和执行任务的无人机数量的加权和；n为无人机数量；k1、k2分别为无人机数量和时间代价的加权系数，同样需满足k1+k2=1的条件。

针对动态场景下无人机的路径规划问题，可以利用构造启发式/元启发式等算法[15]、遗传算法（Genetic Algorithm，GA）[16]、模拟退火算法（Simulated Annealing，SA）[17]、禁忌搜索算法（Tabu Search，TS）[18]、大领域搜索算法（Large Neighborhood Search，LNS）[19]等进行航迹规划，但这些算法在规划空间的离散化、规划效率、约束条件处理和鲁棒性等方面分别有不同的局限性。研究表明，快速扩展随机树（Rapidly-exploring Random Trees，RRT）算法是1 种比较有效的单次查询快速路径规划算法[20]，并被成功应用于各类路径规划研究中。

如图5 所示，基于RRT 的航迹规划算法主要包括3个步骤：选择采样点、搜索新节点及扩展节点。

图5 RRT算法当前节点扩展示意图[20]Fig.5 Schematic diagram of node extension approach of RRT algorithm

本文在RRT算法基本框架下，以一定概率选择目标点作为采样点，来提高航迹规划的速度和质量。同时，在节点扩展过程中，仿照SAS（Sparse A*Search）[21]算法节点的扩展方式，把约束条件和目标函数嵌入到搜索与求解过程中，规划出气象变化场景下满足多种约束条件的最优航迹。具体启发过程如下：沿着当前扩展点的方向，对称地选择最大转弯角，根据最小扩展步长和最大扩展步长约束，形成1 个扇形区域（图5），在这个扇形区域内选择新的扩展点；新节点的产生首先按照一定的约束条件，把扇形区域划分成许多网格，然后在所有格网中，若满足某个格网中心与采样点距离最近并且该格网中心与当前扩展点之间的航迹是可行的，则将该格网中心作为新的扩展点插入到搜索树中，为减少搜索树中节点数目，每次限定只产生1个新节点；最后直至扩展树到达目标点，形成完整航迹数据集，再综合考虑目标函数求解，最终获得最优的航迹规划结果。

假定巡检区内存在雷暴区域，通过模型约束来进行数据集的预处理，再根据当前无人机的航线任务和各自的位置信息，利用启发式算法进行问题求解，可将图4动态调整为图6的巡检航迹规划方案。

图6 气象变化场景下动态调整后的无人机航线图Fig.6 Planning path of dynamically adjusted UAVsunder changing meteorological condition

图6 显示：蓝色航线的无人机飞到雷暴边界后返回机场，终止巡航任务；绿色无人机飞到第5个航点后进入原本蓝色无人机的巡航轨迹进行巡航，到达雷暴边界后返回机场。下方机场需再安排1架无人机从机场出发，完成绿色无人机的剩余可巡航路径。

运用启发式算法进行海上无人机巡检系统仿真，设定规划的无人机规模为50架次，海域最低覆盖率为80%，整体模型求解时间不超过30 s，则可以在30 s内给出该场景下可行的无人机巡检航迹规划方案。

3.2 连续跟监场景

连续跟监场景是指无人机在静态巡检作业下，突然发现需要跟踪的舰船目标，利用机载设备获取舰船的航行速度和航行方向，并临机调整事先规划好的静态航迹，确保对舰船目标的连续跟监[22]。

无需连续跟监时，2 架无人机按照之前的静态规划方案的路径图，各自按照设定轨迹完成巡检（图5）。若蓝色无人机在某时刻发现需要跟踪的舰船目标，并获得了该目标的航行速度和航行方向（图7），此时触发整体流程图（图1）中动态场景里的连续跟监场景模型。该场景根据当前无人机的航线任务和各自的位置信息，通过引入连续跟监场景下的海域栅格图、目标位置信息（坐标）及数量、目标航线、航向、速度、所有无人机信息（坐标）、电量、跟踪时间和目标优先级等约束条件，建立持续跟监场景问题模型，对局部航迹进行动态调整。

图7 连续跟监场景下动态调整前无人机航线图Fig.7 Planning path of UAVs before dynamic adjustments under continuous tracking and monitoring condition

考虑到在无人机能耗及巡检覆盖率的约束下，最大化舰船目标的跟踪时长的情况下，为保证对舰船目标的持续跟监，该场景下的目标函数应设计为力求对舰船目标的跟踪时长最大化，即最大化W：

式（8）中：W为无人机的跟踪时长。

同理，该场景下仍以RRT 算法基本框架为基础，把约束条件和目标函数嵌入其搜索与求解过程，规划出连续跟监场景下满足多种约束条件的最优航迹。

假定在首次发现舰船目标后，根据当前无人机的航线任务和各自的位置信息，利用启发式算法进行解算，可将图7动态调整为图8的巡检航迹规划方案。

图8 连续跟监场景下动态调整后无人机航线图Fig.8 Planning path of dynamically adjusted UAVs under continuous tracking and monitoring condition

图8 显示，此时的巡检方案为蓝色无人机进行跟踪，到达绿色无人机航线后直接返回最近机场，由绿色无人机完成后面的跟踪任务。在蓝色无人机开始跟踪时，机场需要另外派出紫色无人机完成蓝色和绿色无人机的静态巡检航线，完成后返回最近机场。

运用启发式算法进行海上无人机巡检系统仿真，设定规划的无人机规模为50架次，海域的最低覆盖率为80%，舰船目标有效跟踪率不低于95%，整体模型的求解时间不超过30 s，则可以在30 s 内给出该场景下可行的无人机巡检航迹规划方案。

3.3 海域变化场景

海域变化场景是指无人机在静态巡检作业下，原本设定的航线区域部分被临时封锁，无法正常进入封锁海域，原本已规划好的巡检航线中涉及封锁海域的均不可通行，需重新动态调整巡检路线，完成指定的巡检任务。

无海域封锁时2架无人机按照之前的静态规划方案的路径图，各自按照设定轨迹完成巡检（图5）。若某时刻临时管控封锁局部海域，此时无人机不允许进入该海域（图9），触发整体流程图（图1）中动态场景里的海域变化场景模型。根据当前无人机的航线任务和各自的位置信息，通过引入海域变化场景下的海域栅格图、封锁海域位置信息（坐标）及数量、所有无人机信息（坐标）、电量等约束条件，建立海域变化场景模型，对巡检航迹进行局部化调整。

在考虑无人机能耗基础上，重点考虑巡检覆盖率的问题，在保证巡检覆盖率的前提之下，实现巡检时间最小，即最小化R：

式（9）中：R为无人机巡检覆盖率和无人机的有效巡检时间的加权和；p为无人机巡检覆盖率；te为无人机巡检有效时间；k1、k2分别为无人机巡检覆盖率和巡检有效时间的加权系数，满足k1+k2=1 的条件，同时要求巡检覆盖率的优先级高于巡检时间优先级。

同理，该场景下仍以RRT 算法基本框架为基础，把约束条件和目标函数嵌入其搜索与求解过程中，规划出连续跟监场景下满足多种约束条件的最优航迹。

假定航线区内临时封锁局部海域，根据当前无人机的航线任务和各自的位置信息，同样采用启发式算法进行快速求解，可将图9动态调整为图10的航迹巡检规划方案。

图10 海域变化场景下动态调整后无人机规划示意图Fig.10 Planning path of dynamically adjusted UAVs under changing sea surface area condition

从图10可以看出，此时蓝色无人机的返航点被封锁区域覆盖，蓝色无人机则在到达封锁边界时，直接返回机场，同时不需要额外安排其他无人机继续执行其原本航线，因为剩余航线均已被封锁；绿色无人机根据原本航线得到2 个与封锁边界相交的点，用这2点作为绿色无人机新的航点，重新构建航线，再依次完成巡航任务。

运用启发式算法进行海上无人机巡检系统仿真，设定规划的无人机规模为50架次，海域的最低覆盖率为80%，整体模型的求解时间不超过60 s，则可以在60 s 内给出该场景下可行的无人机巡检航迹规划方案。

4 结论

海上无人机协同巡检可以显著提高海洋巡检的作业效率和安全性，通过深入了解无人机海上巡检的航迹规划、目标函数设计、算法流程等技术细节，有助于提高任务的效率和性能。本文主要论述了海上无人机多机协同巡检航迹规划方法，区分静态和动态两大场景，分析了海上无人机协同规划整体流程，并分别介绍了多无人机航迹协同规划方法。其中：静态场景下主要采用分支定界法建立全覆盖问题的混合整数规划模型；动态场景下重点讨论了气象变化、连续跟监、海域变化3 种突发场景下的无人机巡航轨迹规划问题，针对不同情况设计不同的目标函数，采用启发式规划算法动态调整局部巡检航迹，确保完成整个巡检任务。未来，随着无人机在海洋保护、资源管理和安全维护等领域发挥越来越重要的作用，无人机技术也将日臻完善。