摘 要

为充分实现无人机和无人艇在海事监管领域中的优势互补，提高海事巡航的协调性和高效性，对无人机-艇协同任务规划展开研究，设计合理可行的任务规划方案。设计任务规划方案的具体内容包括：结合海事业务特点分析无人机-艇海空协同作业的模式，将巡航区域转换为巡航点考虑，通过类比多旅行商问题模型，建立了无人机-艇协同任务规划模型；根据模型对遗传算法适应度进行调整，并运用其对巡航点进行分配和路径优化；最后利用Matlab进行仿真实验，实验证明模型和算法是可行的，能够有效对无人机和无人艇进行任务规划并使得巡航路径之和最短。

关键词：无人机；无人艇；协同任务规划；遗传算法

Abstract

In order to fully realize the complementary advantages of Unmanned Air Vehicles (UAV) and Unmanned Surface Vessels (USV) in the field of maritime supervision and improve the coordination and efficiency of maritime cruise, UAV-USV cooperative mission planning is studied and a reasonable and feasible mission planning scheme is designed. The specific contents of the design task planning plan include: analyzing the mode of UAV-USV sea and air cooperative operation combined with the characteristics of maritime affairs, transforming cruise area into cruise point, and establishing UAV-USV cooperative mission planning model by analogy of multi-traveling salesman problem (MTSP) model, adjusting the fitness of genetic algorithm according to the model, and using it to allocate and route cruise points. Finally, the simulation experiment using MATLAB proves that the model and algorithm are feasible, and can effectively plan the mission of UAV and UAV and make the cruise path sum shorter.

Key Words: UAV；USV；Cooperative Mission planning；Genetic Algorithm

目 录

第1章 绪论 1

1.1 引言 1

1.2 研究意义 1

1.3 国内外无人机艇任务规划研究现状 2

1.3.1 国外无人机艇任务规划研究现状 2

1.3.2 国内无人机艇任务规划研究现状 3

1.4 论文组织结构 4

第2章 无人机-艇海空协同任务规划模型建立 5

2.1 无人机-艇协同任务规划问题 5

2.2 无人机-艇海空协同作业模式 6

2.3 多旅行商问题 7

2.4 无人机-艇海空协同任务规划模型 9

2.4.1 巡航对象选取 9

2.4.2 问题描述及假设 10

2.4.3 无人机-艇海空协同任务规划模型 10

2.5 本章小结 12

第3章 无人机-艇海空协同任务规划模型求解算法 13

3.1 任务规划算法 13

3.2 改进适应度遗传算法 13

3.2.1 遗传算法简介 13

3.2.2 适应度调整 15

3.2.3 无人机-艇协同任务规划模型求解思路 15

第4章 仿真实验分析 19

4.1 实例分析 19

4.1.1 仿真平台及相关参数 19

4.1.2 仿真结果及分析 19

4.2 本章小结 21

第5章 总结与展望 22

参考文献 23

致 谢 25

第1章 绪论

1.1 引言

随着航运经济的持续发展，海上活动日益繁忙，船舶数量与总运力与日俱增。据统计，我国2018年全年新增干散货船运力211艘、869.98万载重吨，新增集装箱新增运力62艘、12.34万TEU，新增液货危险品船运力71艘、39.98万载重吨^[1]。同时，在通讯技术迅猛发展、大数据和人工智能等技术持续进步的背景之下，船舶不断朝着大型、智能的方向发展。面对复杂多变的交通形势，巡逻艇和有人直升机等在日常调度、监管效率和安全性能等方面呈现出不足，传统的海事监管方式已无法满足高频次和高密度的巡航要求。近年来，无人机技术发展突飞猛进，我国在无人机技术及其功能实现和产品开发等方面都有了很大的进步。鉴于其飞行速度快、受天气影响较小、视野广等优势，我国常州市、徐州市、连云港市等众多海事部门都开始利用无人机巡航。将其作为重点水域、航段巡航的辅助方式，并对此制定了定期的空中巡航计划，逐步形成了以传统水上巡航和电子巡航为主，无人机空中巡航为辅的海空立体巡航监管体系。除此之外，海事无人艇也随之得到广泛应用。自2013年我国首艘无人测量艇在南海巡航成功后，无人艇逐步在海上巡航、海事搜救、水文监测等海事领域试用。无人艇和无人机凭借其各自的优点在海事监管领域具有很大的发展潜力，无论从技术手段和监管需求来看，利用无人机和无人艇进行海空立体巡航都是未来海事监管的必然发展趋势。

1.2 研究意义

船舶交通流量和危险品运输量的增加对海事监管手段的技术程度提出新要求，在社会信息化程度的提高以及“智慧海事”建设的形势之下，无人机和无人艇已在逐步投入到海事监管领域之中。海事监管业务除了对重点海域和航段的交通流及水域环境状况进行监视等日常巡航之外，还包括了及时发现并处理船舶违章、航标异常等情况，以及发生水上交通事故后的应急反应行动。

无人机是可自主执行任务的智能航行器，支持自主动力驱动，且可携带多种任务载荷。因其机动性高、体积小、灵活轻便等特点而具有快速反应的能力，但其在续航能力及通信距离上存在局限，飞行高度高使其具有更为宽阔的视野，但也在一定程度上限制了其对海面目标的信息获取精度；无人艇是一种智能水面平台，支持遥控或自主航行，技术程度高，结构小巧，可以精确观测定位海面目标，还可完成巡航任务。但相比无人机，无人艇视野范围和机动灵活度有限，且受海浪影响较大。

单靠单体无人机或无人艇可能完成某个区域的巡航或搜索，但要完成更大范围的搜索或者更有效率地完成任务则需要多个无人机和无人艇配合。除了上述的速度、机动性、飞行高度、观测精度等方面，无人机和无人艇在通讯距离以及载荷能力等其他方面都可以进行优势互补，两者协同可以很大程度上增强环境感知能力。例如，无人机可能无法满足任务所需的续航能力或有效载荷，则可通过无人艇搭载无人机和相关设备进行作业。此外，在恶劣海况下，无人机和无人艇之间若没有任务的协调机制，导致作业群体规模的增加，降低作业效率，甚至会造成各自作业范围的交叉重叠，增加作业的复杂度，对有序高效地完成任务带来不利影响。

由于实际应用的需要，因此产生了无人机-艇协同作业的概念，即在无人机和无人艇单独作业的基础之上，通过协调多个无人机和无人艇来共同完成一些复杂的海事任务。无人机艇协同研究涉及到控制、人工智能、通讯等多方面的内容，是一个综合性的问题。对无人机-艇协同任务规划展开研究的意义可以体现在如下几方面：

（1）无人机和无人艇协同可以在监管半径、巡视角度等方面弥补单独作业的局限性，扩大巡航范围；

（2）海事监管任务构成要素是多样的，对执行任务的能力要求一般不是单一的，达成任务需要具备不同能力优势的无人机和无人艇协同完成；

（3）无论是并行作业还是次序作业，通过有效的任务协同规划，无人机和无人艇在时间和空间上密切协作，可以提高作业效率；

（4）无人机和无人艇均属于自动控制和人工智能领域的研究热点，其具有很高实际应用价值。

从以上几个角度来看，无人机-艇协同任务规划研究对实现无人机和无人艇协同完成复杂的海事监管任务具有重要意义。无人机-艇协同任务规划是无人机和无人艇协调与合作的重要技术之一，任务的规划结果直接影响整个协同作业系统的效率，这也是无人机和无人艇领域的一个重要课题，受到了国内外学者的极大关注^[2]。

1.3 国内外无人机艇任务规划研究现状

无论是多无人机还是多无人艇的任务规划研究，其重点都是如何在复杂的环境中使得无人机和无人艇在协同完成多项任务时付出的整体代价最小化，而收益最大化。国内外学者对任务规划研究常用的问题模型有旅行商问题模型(TSP)、车辆路径模型(MDVRP)、混合整数线性规划模型(MILP)、网络流模型(NFM)等，常用于求解此类问题的算法主要包括启发式算法、元启发式算法和精确算法三类^[3]。其中，元启发式算法基本思路是将自然界随机现象抽象为算法运用到求解问题中，通常能够快速且准确求解问题，在实际应用中使用较为广泛，具体包括粒子群优化算法^[4]、蚁群算法^[5][6]、遗传算法^[7]等。

1.3.1 国外无人机艇任务规划研究现状

在国外，已有诸多学者对无人机任务规划问题进行了深入的研究。P. B. Sujit^[8]等使用团队理论的概念设计了一种分布式任务分配算法，解决多无人机在相互之间不通信且传感器范围有限制的情况下的任务分配问题。Rodney Teo^[9]等关注城市环境中无人机任务分配问题，提出了基于有限状态自动机(finite state automaton, FSA)模型的控制逻辑设计和一种高效的分布式多无人机目标搜索算法。Cristian Ramirez-Atencia1^[10]等重新设计了一种多目标遗传算法，引入一种混合适应度函数用以检验解是否有效，将该算法用于解决无人机团队内的复杂任务规划问题。

1.3.2 国内无人机艇任务规划研究现状

国内对无人机和无人艇任务规划有关问题的研究虽然起步较晚，但也取得了丰硕的成果。多无人机协同任务规划研究方面，赵明^[11]等按无人机和目标数目的大小关系将目标分配模型分为三类，并针对其建立统一的扩展指派模型，建立仿真战场环境，利用三维切面估计航程代价，采用DE进化算法求解。杜继永^[12]等辨析了多无人作战飞机（UCAV）作战任务与载荷限制之间的协调性，建立多UCAV任务分配数学模型，在连续粒子群算法中引入买卖合同进行优化，避免了求解时在粒子位置解码后出现不符合UCAV载荷约束条件的解的现象。张耀中^[13]等面向执行侦察任务的异构型无人机的任务规划问题展开研究，用矩阵表征资源与需求的关系，构建了无人机飞行航程和续航时间指标，基于此建立模型，并提出一种分布式的扩展一致性束算法进行模型求解。陈星^[14]等以求解利静态任务分配模型为切入点，重点针对动态任务分配问题设计了新的启发式任务分配算法，该算法中将路径重合度作为评判是否分配目标任务的标准，并进行求解验证。

多无人艇任务规划研究方面，张博^[15]等结合无人艇作业环境的外部因素和无人艇自身的内部因素等多重约束，充分考虑任务之间的关联，建立了任务规划模型，利用代价函数将任务规划问题转变成函数最小值问题进行求解。李杰^[4]等研究执行攻击任务的多无人舰艇任务规划问题，在粒子群算法中引入分布式拍卖机制，将粒子的初始状态进行优化以适应问题模型，运用新的粒子群算法进行模型求解。

综合国内外研究现状来看，目前已有很多学者对多无人机协同任务规划或多无人艇协同任务规划进行了研究，也有部分学者将无人机和无人艇两者结合，对两平台间的协同任务规划问题进行研讨。但总体来说大多数学者的研究面向的是作战无人机或无人艇的任务规划问题，而不是海事监管这一领域的无人机或无人艇的任务规划问题。在对后者进行研究时可以借鉴前者的一些常用方法及约束条件，但此外还需要考虑无人机和无人艇在海事监管领域的应用方式及特点。

1.4 论文组织结构

本文结合海事监管的需求和发展，研究海事背景下的无人机-艇海空协同任务规划问题，各章节内容安排如下：

第1章：简要介绍无人机-艇任务规划研究相关内容，具体包括研究背景、研究目的及意义、国内外无人机艇任务规划研究现状和章节安排。

第2章：简介无人机-艇海空协同任务规划问题，分析三种不同的无人机-艇协同作业模式。阐释无人机-艇海空协同任务规划问题与多旅行商问题的异同，类比多旅行商问题，基于巡航点构建无人机-艇海空协同任务规划模型，具体过程包括问题描述和假设、约束条件分析、模型建立。

第3章：简介任务规划常用算法，介绍基本遗传算法实现步骤。根据模型目标函数，对遗传算法中适应度进行调整，设计了适宜本问题的适应度评价标准，运用改进的遗传算法求解无人机-艇协同任务规划模型。

第4章：运用Matlab进行实例分析，验证改进遗传算法的有效性。

本文各章节详细安排如图1.1所示：

图1.1 本文组织结构

第2章 无人机-艇海空协同任务规划模型建立

2.1 无人机-艇协同任务规划问题

协同任务规划是在当前作业环境条件下，根据既定的约束条件，针对多任务需求确定出作业群体以最小的代价获得最大收益的任务分配方案。任务规划并不是简单的对任务进行分配和组合，而需要考虑作业群体的性能、作业环境的变化、目标任务的动态。进行任务规划时需要重点考虑三个方面：作业个体对应目标任务与其性能相匹配；个体完成任务的时间相互协调；任务分配结果为该条件下的最佳方案。

无人机-艇协同任务规划有别于多无人机或多无人艇任务规划，前者是两个不同平台之间的任务规划，而后者是单一平台内的任务规划。部分学者针对不同的平台之间的任务规划开展了研究。例如无人机与货车协同送货研究^[16]、无人机与卫星协同观测研究^[17]、无人机与舰机协同作战研究^[18]、无人机与无人地面车辆协同跟踪研究^[19]等。但是，无人机-艇协同任务规划与多无人机或多无人艇协同任务规划问题也存在相似之处：首先，两者都属于任务规划问题，其本质是组合优化问题；其次，两者的问题复杂度都随着作业个体及目标任务的数量的增加而增加。无人机-艇协同作业是从无人机或无人艇单独作业的方式衍生而来，与无人机或无人艇单独作业的本质区别在于两者在时间上的协调和空间上的协同，因此，对无人机艇进行任务规划时除了其单独作业时需要考虑的要素之外还需要重点考虑两者之间的协同关系。

无人机-艇协同任务规划研究基于多无人机和多无人艇任务规划研究，但又与其存在不同，具体可以概括为以下两点：

（1）无人机-艇协同任务规划问题中，无人机和无人艇承担任务的侧重点不同。无人机由于其灵活性、响应快、体积小等特点多用作远距离的监视和第一时间应急响应，充当“眼睛”的作用；无人艇由于其载重及续航优势可以用作无人机的载荷及续航补充，增加作业群体的载荷能力及续航能力。单一平台内的任务规划，各作业个体承担的任务性质较为均匀。

（2）无人机-艇协同任务规划问题中，无人机和无人艇两个协同对象之间性能差异较大。

无论在使用成本还是巡航速度和续航能力方面，无人机和无人艇都存在一定的差异。一般情况下，无人机巡航速度大于无人艇，而无人艇续航能力则强于无人机，单位路径使用成本也高于无人机。

2.2 无人机-艇海空协同作业模式

本文将利用无人机和无人艇进行海事监管分为以下三种模式：

（1）无人机和无人艇独立作业。即根据无人机和无人艇的续航能力、载荷能力、控制半径、通信半径等的差异分配与其各自性能相适应的巡航任务，如图2.1所示。

图2.1 无人机和无人艇独立作业示意图

（2）一艘无人艇搭载一架无人机协同作业。由无人艇搭载无人机到相应的起飞点派出无人机进行远距离的巡航，由于载荷限制而致使无人机无法完成的巡航任务则由无人艇执行，无人机执行完第一区域的巡航任务后降落至无人艇上，行至下一区域执行任务。如图2.2所示。这种模式可以在第一种模式的基础之上有效延长无人机-艇整体的巡航半径和巡航里程。

图2.2 一艘无人艇搭载一架无人机协同作业示意图

（3）一艘无人艇搭载多架无人机共同作业。无人艇搭载无人机至不同的起飞点可以分次派出无人机完成不同的巡航业务。多架无人机分开执行一定数目的巡航任务，既考虑到其续航和载重限制，又可提高作业效率。作业模式如图2.3所示。

图2.3 一艘无人艇搭载多架无人机协同作业

实际的海事监管应用中无人机和无人艇协同作业模式可能不单单只是其中一种，而是多种模式的结合。本文基于确定的巡航点对第三种模式下的无人机-艇海空协同任务规划问题展开研究。

2.3 多旅行商问题