对运动船舶的多无人机协同查证路径规划方法

赵兴刚， 赵翌僮， 康元基， 陈子匀， 杨双玲

(中国人民解放军66136部队， 北京 100041)

随着经济全球化不断发展，船舶艘次和吨位不断增加，港口吞吐量日益增大，船只事故与非法冲闯行为时有发生，对舰船海事监管提出了更高要求。当前我国海事监管平台设备主要有海巡船、海事直升机、船舶交管中心、自动查证系统和视频监控等，然而上述平台设备存在受海况影响大、信息不直观、对未安装或故意关闭识别设备船舶存在监控盲区等缺陷[1-2]。近年来，无人机(unmanned aerial vehicle，UAV)在感知、定位、导航和通信等技术方面取得突破性进展，可对船只进行调查取证，尽早发现事故或非法船只，作为传统海事监管设备重要补充，为海上监管部门提供先进技术支持[3]。

近年来，不少学者在海事监管领域采用启发式算法开展无人机路径规划应用探索，分析无人机应用于海上立体监管的可行性[4-5]。文献[6]通过聚类处理获取重点区域巡航范围，并基于巡航范围的形状确定无人机最佳巡航方向，设计混合整数线性优化算法探究无人机在各重点巡航区域间巡航的耗时最短路径。文献[7]基于多旅行商问题，设计了一种均衡单个旅行商路径长度的集中式搜索策略，实现了无人机集群对搜索地图的快速全面覆盖和每架无人机的搜索路径均衡。但是文献[6-7]采用区域覆盖的方式，利用无人机对关注区域进行监控，没有给出针对具体目标的搜索方法。文献[8]提出了一种聚类算法和遗传算法进行分布组合的优化算法，提高了对大规模多无人机协同搜索多目标问题的计算效率并改善了规划结果。文献[9]考虑多无人机的任务执行能力、资源和所受威胁等约束，采用多旅行商问题建立了无人机协同任务规划问题的组合优化模型，并采用模拟退火算法对模型进行修正求解。文献[10]建立飞行高度时变的传感器模型和海域环境概率图模型，并设计新的搜索图更新方案，提出了改进的多蜂群算法，实现了多无人机在未知海域中对目标的自适应搜索路径规划。文献[11]提出了基于K-means++聚类与改进型粒子群优化(particle swarm optimization，PSO)的求解算法完成多无人机多目标路径规划，能够使无人机避开障碍物并根据自身的速度规划出合理的飞行路径。

现有研究通过将启发式算法引入无人机协同侦察任务中，实现了对多固定目标的定点侦查[8-11]，然而，在实际运用中，对于入港船舶监管，仍存在两个问题：①进港船舶时刻处于运动过程中，对其跟踪识别具有高度时间敏感性，基于区域覆盖监管与固定目标位置的方法难以给出对运动船舶的具体查证路线；②港口吞吐量较大，无人机资源相对紧张且对运算实时性要求高，导致无人机对进港船舶监管中的实际运用效果较差。

为此，针对大量移动目标，设计一种基于改进模拟退火算法的多无人机协作跟踪查证的路径规划方法，对入港船舶的运动、无人机对船舶的查证和无人机在船舶间的运动过程进行建模描述；然后，改进模拟退火算法，使其适应于无人机数量未定与运动目标位置随时变化的情况，通过迭代递推的方式，得到所需最少无人机数量和对应的运动船舶查证路径规划方案；最后利用仿真实验验证了算法的可行性和有效性。

1 无人机查证问题描述

无人机可利用自身携带的电视摄像机、前视红外仪和合成孔径雷达等设备对入港船舶进行盘旋查证，操作员根据回传图像可确定入港船只国籍、舷号、船型和物资类型等信息，并实时与船舶交管中心掌握的船舶登记信息比对，判断船名与外观是否一致，有无涂改、伪造船名、不良记录或运载非法物资等情况，对问题船只进行初步筛选，为海事执法部门下步处置提供情报支撑。

在实际查证过程中，需保证无人机续航时间大于查证时间，不考虑返港补给情况，单架无人机升空后可担负多艘船只的查证任务。在查证任务开始时，无人机通常按照情报提供位置信息，位首艘船只计划查证位置盘旋等待，发现船只后降低高度，对其绕飞数周进行多角度摄像取证，完成查证后飞离前往下一艘查证船只，直至所有船只查证完毕结束。但由于各船只保持运动状态且速度不一，则任意时刻，两艘船间的位置是动态变化的，导致无人机在两艘船舶间飞行时间受查证顺序影响，当涉及多架无人机协同查证时，船只查证任务的分配也将影响查证总时间。

(1)

2 基于改进模拟退火的无人机查证路 径生成算法

2.1 无人机查证位置计算

由于船只处于运动状态，需求解两项查证任务之间的时间间隔，再根据船只速度确定无人机与待查证船舶相遇位置。具体求解过程可分为以下步骤。

步骤1假设t0时刻商船s1和s2的位置分别为(xs1,ys1)和(xs2,ys2)，一架无人机计划先后对s1和s2进行查证。在t0时刻无人机首先开始查证商船s1，持续tl分钟，在此期间随商船s1原航向绕飞查证。

步骤2t0+tl时刻无人机结束对商船s1查证，开始飞向下一待查证商船s2，无人机及商船位置如图1(a)所示。在t0+tl时刻，假设商船s1和s2的位置分别为(x′s1,y′s1)和(x′s2,y′s2)。由于商船起始位置已知，航向、航速一定，那么可以计算得方程组为

(2)

步骤3假设无人机以巡航速度vuav沿最短路径，经过Δt时间后(Δt为时间间隔，其长度为无人机结束对s1商船查证时刻到开始对商船s2查证时刻的差)，在t0+tl+Δt时刻于(x″s2,y″s2)处与以速度v2航行的商船s2相遇并开始查证，无人机及商船位置如图1(b)所示。(x″s2,y″s2)在商船s2的航线上可得方程组为

(3)

求解方程组可得

(4)

(5)

图1 无人机在两艘船间运动过程Fig.1 Movement process of the UAV between two moving ships

2.2 无人机查证序列路径及耗时计算

表示无人机；S为无人机查证商船的序列； 为无人机i的商船查证序列中的第k艘商船图2 无人机识别运动商船序列Fig.2 UAV verification sequence for moving ships

(6)

(7)

(8)

2.3 基于模拟退火的无人机运动路径生成算法执行步骤

模拟退火算法在搜索过程中具有突跳的能力，可以有效避免搜索陷入局部最优解，基于此，利用模拟退火的思想生成并迭代优化无人机路径，以确定所需最少无人机数量并降低查证路线耗时，具体流程如下。

Step 1给定初始无人机数量n0，初始温度T0和终止温度Tf。

Step 2随机生成长度等于待查证船只数的序列，并根据无人机数量n0，随机选择序列位置，通过插入0值对序列进行切分，得到每架无人机查证商船序列Pi0。根据2.2给出方法，计算得到优化目标初始值maxτ(Pi0)，迭代指标k=0，Tk=T0。

Step 3等概率随机选用交换、位移和倒置算子生成新查证序列P′i，计算目标值增量Δf=maxτ(P′i)-maxτ(Pi0)。

Step 5若达到热平衡[内循环次数大于n(Tk)]转Step 6；否则转Step 3。

Step 6降低Tk，k=k+1，若Tk

根据上述计算步骤，算法流程图如图3所示。

图3 基于模拟退火的多无人机协同查证路径生成算法Fig.3 Multi-UAV collaborative path planning method for moving ships based on simulated annealing

3 仿真分析

使用MATLAB进行仿真实验以验证算法有效性，仿真场景如下：选取某日上午6：00拟进某港的船舶情况如图4所示，该港外航线位于以港口为圆心，方位在与正北方向顺时针夹角20°～70°的扇形区域，设港口为原点，监管处置线端点坐标分别为：C点坐标(170.99,62.23)，D点坐标(62.23，170.99)。

入港商船运动状态数据如表1所示，航向均指向港口，现利用算法确定需派遣进行查证的无人机最少数量及查证路径。

图4 初始仿真场景想定Fig.4 Initial simulation scenario

表1 入港商船运动状态数据

由于各船舶运动方向不变，根据船舶速度、方向和CD线位置，可以计算得到各船舶达到CD线的时间。计算结果表明首艘到达CD线的为1号船，所需时间为8.41 h，即无人机查证总时间最大值t*=8.41 h(约504 min)。

设无人机飞行速度为120 km/h，查证时飞行速度与待查证船舶航速一致，查证时间为10 min。

利用Intel(R) Core(TM) i5-10300H CPU，16.0 GB 内存的笔记本电脑使用MATLAB进行无人机查证路径优化，计算共耗时396.74 s，结果表明，当无人机数量为3时，无人机最大路径耗时计算结果达到收敛(图5)，此时的无人机最大路径耗时为470.1 min,小于t*=8.41 h=504.6 min，满足条件，因而确定所需要的最少无人机数量为3架。

图5 无人机最大路径耗时与迭代次数间关系Fig.5 The relationship between the maximum UAV verification time and the number of iterations

3架无人机的飞行路线和对应完成的识别任务如图6所示，标出了每一架无人机识别的商船序号，其中，红色线段表示在商船识别过程中无人机飞过的轨迹，蓝色线段表示无人机在识别完一艘商船后，到下一艘识别商船的飞行轨迹，所有的红色线段与蓝色线段相互连接，构成无人机在完成整个任务过程中的飞行路线。

表2～表4给出了3 架无人机具体完成的识别商船序列，以及识别序列中每一艘商船对应的识别开始位置、识别结束位置、识别开始时间和识别结束时间。这里的时间以某日6：00为时间起点，记为0 min。

4 结论

针对进港运动船舶如何合理分配无人机查证任务，对无人机路径进行优化进而提高船舶查证效率的问题，基于模拟退火思想提出了一种面向运动目标的路径规划算法来对无人机查证路线进行优化求解。算法首先根据港口位置和航道情况，设置监管处置线，并由运动船舶当前状态，预测其到达处置线时间；然后根据无人机对船舶跟踪查证时间和序列中相邻船舶之间的飞行间隔时间，可以得到各无人机查证序列所需时间；最后由小到大设置无人机数量，以最小化各无人机查证序列所需最大耗时为优化目标，利用模拟退火算法对查证序列进行迭代寻优，确定完成查证任务所需最少无人机数量及对应查证路线。仿真结果分析验证了算法的可行性和有效性。

图6 无人机对运动船舶的查证路径Fig.6 UAV verification path for moving ships

表2 无人机1识别序列对应的识别位置和识别时间

表3 无人机2识别序列对应的识别位置和识别时间

表4 无人机3识别序列对应的识别位置和识别时间