多无人机协同任务规划方法研究综述

无人机作为智能无人系统中的“集大成者”, 具有生存能力高、适应性强、使用灵活等特点, 被广泛应用在多种任务场景[1-3]。当前, 大型全能型无人机(如“死神”无人机、“全球鹰”无人机等)系统集成度高且功能强大, 但面对日益复杂的任务需求, 仍存在任务效费比低、系统容错性差、升级周期长等缺陷。多无人机系统旨在将大型平台的功能分散到空间分布的大量无人机, 利用网络连接将这些功能相对单一的低成本单元, 通过合理调度, 实现不同单元的动态组合和密切协作, 能够在兼具经济性的基础上达到甚至超过大型平台的能力水平。

多无人机系统具有单元配置灵活、部署形式多样、任务能力全面、系统冗余度高、经济成本低等优势, 可以极大提升未来战场的不对称优势, 因此各国均积极部署大量研究项目, 将多无人机系统的应用扩展至多种任务领域[1]。各国发展了以“女武神”“神经元”“小精灵”“郊狼”和“灰山鹑”等项目为代表的无人机项目, 部署了以系统集成技术和试验项目、拒止环境中协同作战项目、分布式作战管理、蜂群无人机应用等为代表的体系协同项目[2-3]。这些项目从集群协同模式、分布式指挥架构、核心关键技术和集群应用演示等方面进行大量探索, 推动多无人机系统与现有装备体系的有效融合, 探索多样化的应用模式[4]。

未来多无人机系统将继续朝向集群化、自主化和智能化的方向发展[4], 其应用面临多样化的挑战: 应用环境更为复杂, 存在不确定且强对抗性因素的干扰; 任务需求更为多样, 机间协同压力更大; 单元类型更加丰富, 资源配置与调度难度更大。因此, 需要发展多无人机协同任务规划技术, 高效调度各单元并融合其任务能力, 合理考虑多类因素干扰以保证任务执行效果, 自主调整任务指派及协同关系以应对环境变化。任务方案不合理将无法体现出多无人机的协同优势, 甚至出现冲突碰撞危险。

任务规划是多无人机系统应用的顶层设计, 是在场景先验信息支撑下, 在应用环境、任务需求和单元能力约束下, 充分考虑执行过程中的不确定因素, 量化当前条件下的可行资源配置与完成概率的关系, 建立包含无人机配置、任务映射关系、执行时间表和任务路径等在内的详尽任务执行方案, 并能够根据任务执行的过程变化及时对任务方案进行调整, 在正常情况下高效完成各项任务, 并在强对抗情况下最大限度地执行任务。

多无人机任务规划属于任务指派和资源分配范畴, 是一个带约束的组合优化问题[5-6], 可分为模型构建和模型求解两部分。从建模角度考虑, 任务规划首先需要将多样化的场景需求表征为任务组合, 在旅行商问题、车辆路径问题、广义指派问题、混合整数线性规划等模型[7-9]的基础上, 结合问题特有的约束条件和不确定因素进一步细化模型, 在优化目标牵引下引导模型求解, 获得满足需求的任务方案。从求解角度考虑, 根据机间信息交互策略的不同, 求解算法可分为集中式和分布式两类[10-11], 需要结合场景需求进行选择并改进, 以适应不同场景下的任务规划求解需求[12-13]。效能评估是根据多方面指标对多无人机系统进行的综合评价, 可以发现系统的薄弱点并进行针对性改进。

本文从问题表征建模和方案求解评估两个角度对当前研究进行梳理分析。问题表征建模分为场景分析、任务分配和航迹规划3部分, 其中场景表征部分分析任务、无人机和环境3类要素; 任务分配部分归纳与构建任务映射关系相关的约束条件、不确定因素和优化目标; 航迹规划分析单机航迹计算和多机协同策略。从方案求解评估角度, 列举了常用的集中式和分布式算法及其改进要点, 然后归纳了多无人机协同应用的效能评估流程。最后, 结合前序分析给出未来研究中应当关注的部分方向。

全面、合理的模型构建是任务规划问题求解的基础。多无人机协同任务规划的内涵十分丰富, 包含但不局限于复杂任务分解、平台载荷配置、任务目标分配、航迹协同规划、多机编队协同、单元自主控制等[14-15]。其中, 复杂任务分解与平台载荷配置主要体现人在回路中的指挥控制, 多机编队协同与单元自主控制主要体现为平台底层控制逻辑。任务目标分配和航迹协同规划承上启下, 是体现协同优势的核心部分, 从技术上保障了多样化任务能力的构成。

如图 1所示，本文从场景分析、任务分配和航迹规划3个层级分析任务规划问题。场景分析将抽象化的目标需求表征为任务组合, 任务分配建立任务与无人机的映射关系, 航迹规划设计无人机的任务路径。3个层级相互关联, 高一层级对下一层级进行引导, 下一层级在其范围内灵活调整并向上反馈, 在保证精度的前提下降低问题求解难度。

图1   任务规划过程示意图

在本节中, 场景分析从目标与任务、无人机与载荷和任务环境3方面分析影响任务执行的要素。任务分配从建立合理映射关系出发, 分析约束条件、不确定因素和优化目标的处理策略; 航迹规划从精确评估路径成本出发, 分析单机路径生成和多机航迹协同的相关研究。

实际存在的物体或区域, 根据形状可分为点目标、条带目标、规则面目标[16-17]和不规则面目标[18-19]; 根据运动状态可分为静态目标、规则移动目标和不规则移动目标[17,20-21]。

由单架无人机在一定时间内对目标实施的一系列行为, 不同场景可以视为不同类型和数量的任务组合。常见的任务类型如下。

• (1) 覆盖搜索: 对大面积未知区域进行持续性监视, 确定其内部目标信息, 包含行为式覆盖(Z型、回型)和非行为式覆盖[8,16,19]。

• (2) 定点侦察: 采用不同类型的任务载荷(光学、红外或雷达等)对位置概略已知的目标进行多层次的信息收集[17,22-23]。

• (3) 目标追踪: 对区域内移动目标进行持续监视, 为后续任务提供信息支撑[24]。

• (4) 火力打击: 使用多类型武器对信息已知的目标进行毁伤[22,25-26], 同时多向打击可以有效提升打击成功率[27]。

• (5) 效果评估: 对完成打击任务的目标进行评估, 判断是否达到毁伤要求[20,28]。

• (6) 通信中继: 为通信能力有限的无人机提供通信连接, 扩展无人机任务范围[29]。

• (7) 物资运输: 将充足数量和指定类型的物资运输到目标点[25]。

• (8) 电子干扰: 实施电子压制、降低对方探测和打击能力[30]。

可以根据任务需求和无人机能力调整任务设置。文献[31] 区分防御高和防御低的目标, 针对防御高的目标增加打击任务数量, 以确保毁伤效果。文献[32]针对无人机潜在断联风险, 派遣中继无人机执行通信中继任务, 使得无人机可在基站通信范围外执行观测任务。文献[33]针对应急区域覆盖搜索, 根据目标位置、区域大小和无人机续航能力调整任务设置, 能够兼顾任务效果与无人机负载。

多无人机系统单元间的差异主要体现在动力学性能和载荷功能两方面。

动力学性能影响任务路径设置和到达时间计算, 在任务规划计算时主要考虑速度范围、转弯半径、最大爬升角、最大下滑角等限制[34-36], 部分研究进一步简化为二维空间的速度与转弯半径限制[20,27]。

载荷功能影响任务指派和效果评估, 此处针对常用的侦察、打击和通信载荷进行分析。

(1) 侦察载荷: 从目标发现角度可简化为搜索半径[18], 或通过视场角与飞行高度计算扫描范围[17,37]。针对目标识别问题, 单传感器侦察需考虑置信概率, 多传感器协同侦察需要考虑信息融合问题。

(2) 打击载荷: 从目标毁伤角度, 一般简化为打击范围和毁伤概率指标[30,38]。

(3) 通信载荷: 一般简化为通信半径, 即该范围内单元相互连接[39-40], 进一步考虑通信拓扑结构[6,41]、通信跳数[41]、路径损耗[10,42]、接入单元数量[42]等限制。

多无人机系统可以通过平台与载荷的灵活配置, 形成多样化的任务能力。合理的配置方案可以提升机间协同效率, 在满足任务需求的同时避免资源浪费[43], 还可提升应对不确定因素干扰的能力。

文献[38]在协同对地打击场景下, 对比不同数量、不同隐身能力和飞行速度无人机的体系贡献率, 显示无人机数量存在饱和、隐身能力中等且速度高的无人机组合效果更好。文献[44]在速度和需求不确定的场景中, 相较确定问题增加少量执行单元, 有效提升任务方案的鲁棒性。文献[30]和文献[45]利用聚类方法将空间分布的多个任务划分成簇, 根据簇群数量确定无人机数量并进行任务分配, 提升大规模问题的求解效率。文献[13]分析无人机配置与任务分配的关联关系, 设置基于进化算法的双层求解方法, 结合任务分配计算情况调整无人机数量, 可以获得精确的无人机配置方案。文献[46]针对无人机武器载荷配置问题, 利用邻域搜索算法优化武器载荷搭载, 在满足毁伤需求的同时缩短了任务执行时间。

任务环境中影响任务执行的因素可分为地形障碍类、战场干扰类和气候条件类。

(1) 地形障碍类: 任务区域的障碍会延长任务路径, 影响到达时间的计算。计算时可以直接导入地形数据, 或建模为三维半球、圆台、圆柱等[34-35,47], 或二维圆形、方形等[26,48-49], 并可根据安全裕度适当扩大障碍范围[50]。

(2) 战场干扰类: 对抗环境中的地面火力和探测雷达会影响任务路径设置和任务风险评估[50-51], 可将其视为地形障碍以确保无人机不通过该区域[52], 也可建模为发现概率[50]和打击概率[47]的分布模型, 综合考虑任务路径长度和任务风险进行计算。

(3) 气候条件类: 气象因素对飞行的影响是全局性的, 且存在较多不确定性, 影响路径设置和飞行速度[36,53]。如小型无人机抗风能力弱, 需要根据风场方向调整任务路径设置[19]。

任务分配主要构建无人机与任务的映射关系, 是任务规划的核心。本节分析任务和无人机相关约束条件和处理策略, 归纳影响任务执行的不确定因素和描述方法, 最后列举多种常用优化目标。

模型约束可分为任务相关类和无人机相关类, 具体如下。

(1) 任务时序耦合约束: 不限制任务的具体执行时间, 而是限制任务间的相对执行顺序, 可分为同时执行、前序执行、后序执行、任务间执行和任务互斥5类[54-55], 可以使用有向无环图进行精确描述[28]。忽视该类约束会出现“死锁”问题并产生大量无效解[56]。可以通过任务分层计算[54]、强连通量消除[28]、关联任务打包编码[20,31,56]等方法进行处理。

(2) 任务时间窗约束: 限制任务的具体执行时间(最早开始/最晚结束), 根据违约处理策略可分为硬时间窗和软时间窗两类。在时间窗限制下, 到达过早需要“等待”, 到达过晚会受到惩罚或错失任务[55], 其中的“等待”过程降低速度不确定性对任务执行的干扰[57-58]。

(3) 无人机数量约束: 参与任务执行的某一类型无人机数量不能超过数量限制, 主要出现在无人机配置可变的场景[13]中。

(4) 无人机航程约束: 无人机所携带的能源有限, 部分场景需要考虑返航需求。一般使用燃料消耗[13,59]、飞行距离[39]、飞行时间[11,60]、最大任务数量[61]等指标进行计算。

(5) 无人机能力约束: 无人机必须具有相应能力方可执行任务。载荷能力可以使用0~1变量进行简要判断[10], 或结合功能半径和执行概率等参数进行进一步建模[62-63]。

(6) 无人机资源约束: 无人机携带资源有限, 所担负任务的资源总量不能超出自身的资源类型和数量限制[23,25-26]。

约束数量随问题规模变大呈非线性增加, 大部分约束只涉及单架无人机或部分任务, 少量约束则涵盖全部任务与无人机, 约束之间耦合关系复杂。对此, 可以使用惩罚策略[56,64-65]、放松策略[55-56,66]、构造修补策略[31,65,67]等进行处理, 如下所示。

• (1) 惩罚策略: 根据违约情况调整模型优化目标值[65], 将原始约束问题转化为无约束问题进行求解, 在约束较少的情况下筛选可行解的效率高, 但在大规模约束情况下可能无约束解很少[56]。

• (2) 放松策略: 在可接受范围内先放松部分约束, 后续根据需求进一步增加限制。放松约束可能导致解的性能下降, 但可以有效提升求解效率, 增强解的多样性[66]。文献[56] 为避免调整“死锁”带来的巨大时间成本, 设计成本近似函数以替代调整过程, 虽然降低了结果性能, 但大大缩短了求解时间。文献[68]针对时序耦合场景, 构造包含少量约束的主问题, 然后动态增加对优化目标有改进的约束条件, 有效缩短了多约束问题的计算时间。

• (3) 构造修补策略: 根据约束关系设计多种类型的操作, 对违约解进行调整, 能够确保最终解的可行性, 但调整多类约束的操作复杂。文献[31]针对时序耦合、动力学和能力等约束, 调整编解码生成无“死锁”方案, 设计无人机选择算子以满足能力约束, 以Dubins曲线设计任务路径并协调到达时间, 通过多次调整生成可行解。

在任务执行过程中, 存在多种不确定因素的干扰, 可分为任务相关类和无人机相关类。

• (1) 目标与任务: 存在位置[37,67]、类型[69]、数量[56,69]、资源需求、任务执行时长[44,58]、时间窗[58,70-71]等不确定因素。

• (2) 无人机与载荷: 存在单元故障[72-73]、速度变化[65,74-75]、载荷置信度[57,65]等不确定因素。

随着无人机规模的增加和协同关系的日益复杂, 不确定因素对任务执行过程的冲击逐渐加大, 需要进行针对性处理。处理策略可分为预处理和重规划两类, 其中预处理策略是针对部分可预估的因素, 在建模时考虑其影响范围, 通过增加部分成本提升方案的鲁棒性。重规划策略是针对部分难以预估的因素, 在不确定因素出现后, 对现有方案进行快速调整, 降低对任务执行过程的干扰, 具体如下所示。

(1) 预处理策略: 根据对不确定因素的描述策略不同, 可分为随机规划、马尔可夫方法和鲁棒优化3类。

• 随机规划: 适用于已知概率分布的不确定因素, 使用期望值、最差值和机会约束预估不确定因素的影响范围。通过求解期望值可以将不确定问题转化为确定问题, 但会存在实际值与计算值偏差较大的情况; 最差值是预估不确定因素的最坏影响, 可确保最高的可靠性, 但会过于保守; 机会约束是确保风险阈值内的最差情况满足要求, 可以通过调整阈值设置平衡成本与鲁棒性。文献[65]考虑速度不确定性并最小化期望违约成本, 提升方案鲁棒性但仍存在违约情况; 文献[76]对比使用期望值和最差值两种策略的效果, 在高度不确定的情况下, 后者由于过于保守, 方案质量较差。文献[75]考虑多类不确定因素, 构建模糊机会约束规划模型, 可以根据风险偏好生成多种可行方案。

• 马尔可夫方法: 描述智能体与外界环境相互作用的模型, 用于求解不确定环境下的序列决策过程, 将不确定性以概率形式表示为转移矩阵, 调整决策最大化累积报酬。文献[74]针对动态对抗环境下的规划问题, 将不确定因素建模为系统的不可观测部分, 通过强化学习获得当前置信度下的最佳动作序列; 文献[77]针对移动目标追踪任务, 考虑载荷置信度和目标移动, 构建任务路径与观测结果的转移概率, 进而求解观测方案。

• 鲁棒优化: 通过不确定集描述不确定因素, 确保不确定集约束下方案的可行性[56,70],

不需要获取精确概率分布。常用不确定集包括区间集、预算集、因子式集、椭球集、离散集等[70]。不确定集越精细, 模型复杂度越高, 求解越困难; 不确定集越宽泛, 方案越保守, 经济性越差。文献[70]对比上述不确定集的计算时间, 其中椭球集、离散集和因子式集计算成本较高, 预算集和区间集计算成本较低。考虑执行时间和速度的不确定性, 文献[78]使用区间集求解, 设计区间支配占优关系, 方案鲁棒性强但十分保守; 文献[44]和文献[58]使用预算集求解, 使用动态规划方法表征了部分任务的延误影响, 通过增加少量成本有效提升了方案鲁棒性。

(2) 重规划策略: 根据对现有方案调整程度的不同, 分为完全重置和局部重置两类。

完全重置将重置全部任务映射关系, 可以实现最高水平的协调; 局部重置只调整部分方案, 可以快速形成可行方案。图 2所示为局部重叠示意图。文献[67]针对未知环境下的搜索场景, 通过完全重置调整任务方案, 平衡当前目标搜索收益和对新目标的覆盖能力。文献[10]在新目标连续出现的情况下, 对比完全重置和局部重置的计算效果, 在任务较多时完全重置计算时间过长, 使得整体系统始终处于不稳定状态。针对局部重置, 如图 2所示, 为降低对原有方案的干扰, 研究者提出多种调整策略: 如基于到达时间、载荷能力[64]和资源状况[79]选择无人机参与调整; 基于任务收益[40]和与新任务时间窗口重叠情况[80]调整任务映射关系。

图2   局部重置示意图

优化目标函数是引导任务规划求解的关键条件, 常见优化目标如下。

• (1) 任务完成时间: 通过计算任务最大完成时间评估任务执行效率[65,81]。

• (2) 任务平均开始时间: 通过计算任务开始时间评估任务执行效率, 常用于评估时间敏感任务[11,82]。

• (3) 任务总时间: 通过计算整体任务时间消耗评估任务时间成本[16,83]。

• (4) 任务路径长度: 通过计算无人机的路径总长度评估任务成本[18,50]。

• (5) 任务完成数量: 通过计算任务完成数量评估时间/资源有限场景内任务规划方法的求解效率[82,84]。

• (6) 任务成本: 通过计算任务路径长度、任务风险值[23]、平台损耗[76]、燃料消耗[59]等评估任务执行的经济成本。

• (7) 任务收益: 通过计算任务价值[7,80,85]、任务价值与完成时间的综合函数值[64,86]等评估任务执行效益。

• (8) 无人机数量: 通过计算参与任务的无人机数量, 评估无人机配置不定时规划方法的计算效率[13,87]。

• (9) 不确定成本: 通过预期违规成本[88]、路线变更成本[72]、未知区域覆盖指标[67]等计算不确定因素对任务执行过程的影响, 进而评估任务方案的鲁棒性。

任务规划可以使用多个优化目标筛选任务方案。针对多个优化目标, 可以使用权重策略、分层优化和多目标优化进行处理。

• (1) 权重策略: 为优化目标设置权重, 将其转化为单目标优化问题[16], 多应用于量纲相同或归一化的优化目标。该方法可以通过设置权重简化求解并区分不同优化目标, 但不合理的权重设置可能会掩盖部分优化目标。

• (2) 分层优化: 在某一优化目标结果的基础上求解其余优化目标, 多用于处理处于不同层级且相互影响的目标, 可以有效缩小问题搜索空间, 但弱化了优化目标之间的耦合关系。文献[89]针对速度的不确定性, 首先最小化任务路径长度, 在其结果上最小化不确定因素带来的预期损失。

• (3) 多目标优化: 使用Pareto占优策略筛选多个优化目标均占优的折中解, 多用于处理优化目标相互矛盾的情况。解集分布可以为问题分析提供参考[87], 但是需要对算法进行针对性改造, 且优化目标过多时算法选择压力下降, 非支配解数量激增, 需要调整筛选机制[23]。

航迹规划是在任务分配生成的任务映射的基础上生成可行路径, 是评估任务方案时间/路径成本的核心部分。多机航迹协同是在满足动力学约束和环境避障的基础上, 进一步考虑时序协同与机间避障需求。本节首先对比单机航迹规划的多种方法, 然后在此基础上分析多机时序协同与机间避撞的处理策略。

根据空间离散策略的不同, 单机航迹规划方法可分为图搜索类方法、概率类方法和人工势场法3类, 相关方法对比如表 1所示。

表1   多种航迹规划方法的对比

(1) 图搜索类方法: 将任务空间离散成连接目标和障碍的路径网络, 在此基础上搜索获得最/较优路径。常用空间离散方法包含可视图法[22]、Voronoi图法[90]、栅格法[17,59]等; 常用搜索方法包含Dijkstra算法[91]、A * 算法[26]、动态规划[8]算法、元启发算法[92]、强化学习[74]方法等。不同离散方法和搜索方法的组合可以适应不同任务需求: 文献[90]针对城市内未知移动目标搜索场景, 使用Voronoi图法设置待选航路点, 使用滚动时域预测方法优化路径, 可以兼顾飞行安全和搜索效率。文献[17]针对不确定区域内的搜索打击场景, 使用栅格法离散区域, 通过分布式蚁群算法优化路径, 可以有效引导无人机搜索目标存在概率高的区域。

(2) 概率方法: 在任务空间中设置大量采样点, 使用直/曲线连接起点、部分采样点与终点, 形成任务路径, 通过优化连接采样点提升路径质量, 根据采样点设置策略不同分为概率路标图法和快速随机树法。该类方法不需要对场景进行建模, 对动态或多障碍场景适应性很好, 能够快速得到可行路径, 但受采样点设置和搜索策略影响, 路径较为曲折。文献[93]利用快速随机树法处理未知障碍或突发威胁, 能够快速调整现有路径, 绕过障碍区域。

(3) 人工势场法: 在任务空间建立虚拟力场, 叠加目标产生的引力与障碍产生的斥力, 生成靠近目标且远离障碍的路径。该方法原理简单, 可以引入对方火力威胁、相邻无人机等多类因素, 有效提升任务路径的安全性。但是该方法在力场函数设置不合理时可能产生无法到达目标、违反避障约束和局部震荡等问题, 对此发展了多种改进策略, 如距离修正、局部扰动等[94-95]。

航迹规划计算过程中常使用曲线连接航路点, 通过调整曲率和长度生成多样化的任务路径。常用曲线包含Dubins曲线[22,96]、贝塞尔曲线[34]、B样条曲线[34-35]、毕达哥拉斯曲线[85,97]等, 多种航迹曲线的对比如表 2所示。

表2   多类航迹曲线对比

多机协同需要考虑任务时序耦合约束带来的时序协同要求和无人机密集部署带来的机间避撞需求。

机间时序协同体现在无人机的到达位置和到达时序, 需要根据协同需求设置航路点, 针对性调整路径长度和飞行速度。文献[22]考虑侦察、打击和评估任务的时序关系, 使用Dubins曲线设计任务路径, 增加盘旋段以调整到达时间, 满足多类任务的时序耦合约束。文献[85]考虑对目标同时多向打击的需求, 使用毕达哥拉斯曲线设计任务路径, 使用粒子群优化算法优化其路径长度和曲率参数, 并同步调整飞行速度, 满足同时到达要求, 避免了单纯控制路径长度所带来的大量迭代计算。文献[24]考虑无人机对地面移动目标的追踪, 考虑无人机与目标速度差异, 基于二者相对位置、速度比和转弯半径设计追踪路径, 保持无人机与目标的同步运动并最小化相对距离。

机间避撞需求可以通过生成空间无交叉或时空四维无交叉的路径进行处理。文献[91]使用路由网络对区域进行划分, 以避开障碍并防止路径交叉, 使用Dijkstra算法计算最短任务路径, 在此基础上插入航路点延长路径以满足时序协同需求; 文献[94]研究多无人机编队避障问题, 通过Voronoi图将场景分割为不重叠区域作为无人机的运动区域, 并通过人工势场法设计控制策略, 避免无人机相互碰撞。考虑时空调整, 文献[14]列举势场法和在线预测策略, 通过构造时空无冲突路径, 可以最大限度地降低冲突风险。文献[98]针对密集无人机集群协同规划问题, 设计分布式动态优先级解耦策略, 降低飞行时间短的无人机的优先级以挖掘其路径调整潜力, 低优先级无人机单向调整自身路径以避免与高优先级无人机发生碰撞, 从而获得整体无碰撞路径。

任务规划模型的高效求解是多无人机协同应用的现实需求。本节首先列举常用的集中式和分布式算法, 分析不同算法面向任务规划求解的改进策略, 然后归纳多无人机系统的效能评估流程。

集中式方法利用中心节点收集信息并指派任务, 可以充分协调各类资源, 能够获得最优方案, 但是其依赖于中心节点且扩展性差, 适用于在任务执行前综合已知信息进行调度[72]。分布式算法基于去中心化思想设计, 依赖于机间信息交互以实现任务协同, 避免了单点失效风险且扩展性较好, 但缺少中心节点的协调会造成单元间的任务竞争, 算法需要在解决单元冲突和提升协调效率之间寻找平衡, 适用于在任务执行过程中根据场景变化快速调整方案。

集中式方法可分为精确方法和近似方法: 精确方法是以较高的时间成本获得最优解, 近似方法是在有限时间内获得满意解。图 3展示了集中式方法下的精确方法和近似方法的各类具体算法。

图3   集中式方法的分类

(1) 精确方法

精确方法可以为任务规划问题分析提供准确参考[58], 包含动态规划和分支方法。

动态规划是一种求解多步优化问题的全局优化方法, 任务规划问题需要优化无人机对多个任务的执行顺序, 适用于动态规划方法[8,99]。文献[8]针对多区域覆盖侦察问题, 使用动态规划方法递归求解以获得多个区域的最佳访问顺序及进出位置。部分研究使用多步前瞻策略简化动态规划方法: 文献[99]针对对抗环境中多无人机协同场景, 使用两步前瞻策略求解无人机的行动方案, 能够以较少时间获取与最优解相近的结果。文献[100]针对Dubins旅行商问题, 每次只考虑部分目标间的最短路径, 通过多步求解获得整体路径, 并可动态调整前瞻程度以平衡求解效率与方案效果。

分支方法是树搜索策略的一种, 主要包含分支定界法、分支定价法和分支切割法等。分支定界法在混合整数线性规划模型的求解过程中修剪次优解分支, 避免大量无用搜索。文献[68]使用分支定价法求解时序耦合问题, 利用约束分布稀疏的特点, 通过列生成策略将问题分解为多个小问题进行求解并逐步逼近最优解, 有效缩减了计算时间。文献[70]考虑最坏情况建立鲁棒异构车辆路径问题线性规划模型, 使用分支切割法动态引入约束条件以逼近最优解, 能够获得问题的精确下界, 可作为多种启发式算法的对比基准。分支方法拥有大量改进策略, 如状态空间松弛、启发式分支修剪、启发式标签策略等[101-102]。

(2) 近似方法

近似方法不追求获得问题的最优解, 而是利用启发式信息引导搜索以期在多项式时间内获得满意解, 可分为构造启发式算法和元启发式算法两类。

构造启发式算法根据问题特点设计搜索规则指导求解过程, 如最邻近法、最小成本增加插入法[103]、时间增加最少插入法[81,103]等。该类方法形式简单, 没有复杂的控制参数, 能够以较少计算资源生成可行解, 但无法确保解的质量, 因此多用于初始种群构造。

元启发式算法基于对自然界的学习, 为问题求解提供了一种普遍适用框架, 不依赖于对问题的精确数学分析, 求解鲁棒性强, 可分为基于个体信息的搜索方法和基于群体信息的搜索方法。

个体信息搜索对单个解进行逐步改进以获得满意解, 代表算法包含模拟退火[7]、迭代局部搜索[70,104]、自适应变邻域搜索算法[44,103]等。文献[104]使用变邻域搜索算法求解车辆车队路径问题, 使用了7种路径间邻域结构和5种路径内邻域结构, 如shift(m, n)移动、k-opts交换等。文献[44] 设置基于任务路径、任务负载和时间窗的多种邻域, 根据计算状态评估不同邻域的效果, 并动态调整重点搜索方向。个体搜索方法没有通用架构, 需要根据问题特点针对性设置更新操作。

群体信息搜索依赖于当前大量解的状态引导搜索: 如粒子群优化算法[11]、蚁群算法[17,92]、遗传算法[20,87]、狼群算法[56]、鸽子群算法[35]等。文献[20]和文献[31]基于改进遗传算法求解任务规划, 使用多层目标束编码建立无人机与任务的映射关系, 改进交叉和变异操作以增强搜索能力。文献[56]利用狼群算法求解, 使用两段式编码缩小搜索空间, 引入新的换位和扩展操作以增强搜索能力。该类方法需要将问题空间合理映射至算法空间, 动态调整控制参数以平衡全局搜索与精细调整[44,92], 恰当处理多类约束以平衡求解效率与可行性[66], 融合不同更新操作以增强搜索能力[7,87]。

分布式算法可分为市场协商方法、分布式约束优化方法和多智能体方法3类: 市场协商方法通过竞拍将任务分配给“收益”最高的单元; 分布式约束优化方法将任务列表在单元间传递, 任务满足“选择阈值”则进行分配; 多智能体方法赋予各单元信息收集与分析能力, 以集群涌现的形式实现任务协同。图 4展示了分布式方法下的市场协商方法、分布式约束优化方法和多智能体方法的各类具体算法。

图4   分布式方法的分类

(1) 市场协商方法

市场协商方法根据“拍卖-竞标-中标”竞拍机制为单个任务[12]或多个任务[105]选择合适的执行单元。该类方法原理简单, 计算效率高, 但由于协商需求带来大量通信交互, 在大规模或通信资源密集场景下效果较差[10]。其代表性算法包括拍卖算法[56]、合同网算法[85]、一致性众包算法[61,105]、性能评估算法[60,106]等。

一致性众包算法[105]将多个任务构造成任务包进行分配, 并通过冲突消解迭代寻找无矛盾解, 较拍卖算法效率更高。性能评估算法[60,106]在构建收益函数时考虑前后任务的正/负向耦合关系, 增加任务重要性指标、提升整体任务执行效率, 降低了算法为快速收敛采用的贪婪策略的“短视”影响。为在不影响算法性能的前提下降低信息交互的需求, 各类研究设计了大量策略: 如设计动态通信拓扑结构[107]、调整双向无源通信为单向有源通信[29]、调整同步通信为异步通信[107], 设计分组策略(预分组[86]、地理距离[82]和任务偏好[108])以非全连接形式降低通信需求。

(2) 分布式约束优化方法

分布式约束优化方法较市场协商方法更依赖于单元本地信息进行决策, 协调通信需求低, 通过合理设计求解过程可以获得误差许可内的近似解[109]。其代表性算法有: Swarm-Gap算法、令牌传递算法、Max-Sum算法等。

Swarm-Gap算法根据预设阈值选择任务, 阈值设计对方案性能影响很大, 因此多采用动态阈值策略。文献[110]设计分散遗忘的响应阈值动态调整策略, 提升动态场景的适应性。文献[111]针对动态蚁群分工模型设计响应阈值的调整策略, 能够有效处理异构无人机和时序耦合任务的相关约束, 并满足快速重规划需求。令牌传递算法传递包含任务信息的令牌, 单元在接收令牌后决定执行任务或将任务随机传递给其余单元。文献[84]针对分配环网、任务选择顺序和无人机任务选择进行改进, 提升任务完成数量并缩减了任务完成时间。文献[9]改进算法以避免令牌的重复创建与无效传递, 在搜索救援场景中较贪婪算法性能提升明显。文献[109]设计多层Max-Sum算法, 通过分层策略处理任务间时序约束, 通过时序网络处理任务时间窗约束, 通过构建多单元组合降低任务执行时间, 较拍卖算法提升了任务完成率并缩减了任务完成时间。

(3) 多智能体方法

多智能体方法为单元赋予信息收集、状态分析与自主决策的能力, 基于预设规则和局部交互, 各单元自下而上地形成整体有序的协同状态, 具有高度自组织性、灵活性和扩展性。其代表性算法为博弈论方法[49,53,112-113]和群体智能方法[9,17,111]。

文献[112]利用分布式博弈论框架求解动态任务分配问题, 基于贪婪策略设计协商过程, 考虑任务成本的变化, 能够确保单元与整体收益一致。部分研究借鉴博弈论中的隐式协调策略, 文献[113]在一致性众包算法中基于对其余智能体的预测进行出价, 在降低信息交互的同时提升了求解性能。

群体智能算法侧重对生物群体机制的学习, 如鱼群迁徙、狼群捕猎、蚁群搬运和蜂群觅食等。如图 5所示, 无人机作为集群个体搜集环境信息, 按照预定规则进行交互并更新自身行为, 在集群层面实现复杂任务协同[14]。文献[96]参考蚁群觅食机制, 处理搜索打击移动目标问题, 调整信息素更新机制引导搜索, 较传统覆盖搜索方式效率更高。文献[115]参考狼群高效分工协作和复杂环境的适应性, 提出了对抗环境下无人机群协同决策策略。文献[39]参考蝗虫的独居和群居状态, 在搜索与救援场景下, 提出兼顾区域覆盖搜索和关键区域联合救援需求的调度策略。当前群体智能算法多为生物行为的简单模仿, 多用于较为松散、简单的“触发式”任务场景。未来在复杂场景应用时需要进一步提炼生物群体的交互规则, 如狼群捕猎时的分布位置、层级结构、群组构型等, 针对性调整并丰富无人机内部的协同策略。

图5   基于自组织涌现的架构

效能评估是通过对任务能力、协同效率、成本代价、计算效率等方面的分析, 评估多无人机系统的综合能力。效能评估流程包含评估指标设计、指标计算和权重设置3个部分。

评估指标多采用多层体系设计, 即将整体指标划分为多个类别, 在每个类别下设置多种具体指标。考虑单机任务能力, 在对地打击场景下, 文献[116]从打击、突防、态势感知和能力范围等方面建立指标体系; 文献[117]使用ADC(availability, dependability, capability)法评估无人机效能, 在完善能力类指标基础上, 增加可靠度类和可用度类指标。考虑多机协同效率, 文献[118]针对观察－判断－决策－行动(observe orient decide act, OODA)决策链, 设置感知、通信、决策、打击、组队等全方面的协同作战指标体系; 本文考虑多机打击场景[119], 基于打击和协同情况设计效能影响因子, 描述不同载荷的影响关系。考虑综合成本代价, 文献[38]考虑代价类指标, 分析不同类型无人机在对抗情况下的生存率; 文献[51]考虑成本类指标, 分析无人机搭载不同类型光学载荷、执行侦察任务的经济成本; 文献[120] 在评估装备体系贡献率时考虑成本因素, 面向任务需求给出有限预算下的装备列表。考虑计算效率, 文献[121]设置规划计算时间、重规划响应时间等指标。

在指标计算方面, 定量指标可以结合任务数据计算具体数值, 如任务完成数量、命中概率、计算时间等; 定性指标没有明确的表达式, 一般需要在专家系统的支撑下, 在预设范围内进行评分, 如抗干扰能力、协同感知能力等[38,51,119]。部分研究对指标值进行规范化: 文献[117]将指标实际值与预设期望值进行对比; 文献[120]设计能力满足函数进行归一化, 指标超出预定值则保持为1。

在权重设置方面, 由于各类型指标差异较大, 可以采用模糊层级归纳法[51-52]、层次分析法[117]、证据推理法[121]等方法将多种指标统一为综合效能值。但上述方法主观因素比较大, 且不适用于多变的任务环境。因此, 文献[122]提出基于静态贝叶斯网络的评估方法, 降低主观因素的干扰; 文献[123]提出基于自适应粒子群算法的反向传播神经网络方法, 具有良好的泛化能力, 适用于动态任务场景。

效能评估可以发现多无人机协同应用的薄弱环节, 为优化多无人机系统的规模配置提供参考[119], 指导后续无人机和任务载荷的改进设计。

任务规划技术的发展可以推动多无人机系统在多场景中的应用, 是无人机自主控制领域的关键问题。当前多无人机协同任务规划还存在较多挑战, 现梳理部分可行方向。

(1) 量化评估无人机配置与完成概率的关联

无人机的配置影响整体协同效率, 并与最终任务执行效果息息相关。需要在合理表征无人机任务能力、资源数量、飞行航程和任务耦合关系的基础上, 在任务分配和航迹规划计算方法支撑下, 量化评估当前条件下的可行资源配置与完成概率的关系, 建立无人机配置计算方法, 在避免遍历无人机配置组合的前提下, 根据任务需求调派合理数量的无人机, 并根据场景变化灵活调整无人机数量。

(2) 不确定因素影响下的任务规划建模

不确定因素会影响任务方案性能, 甚至造成方案失效, 需要在计算任务方案时考虑该类因素的影响。不确定因素的合理建模是平衡任务方案鲁棒性和方案成本增加的关键, 需要对比不同建模方法的差异, 寻找合理的建模方法和控制参数, 为模型构建提供合理参考; 同时考虑多种不确定因素同时出现时的建模策略, 分析多类型因素的关联性(如时间窗口的存在可以降低速度不确定性对任务方案的冲击), 以较小的成本获得鲁棒性强的任务方案。

(3) 适用于动态场景高效求解的分布式算法

分布式算法通过单元间的信息交互实现任务指派, 求解效率高, 能够适应动态任务场景需求。分布式算法需要针对信息交互机制、收益评估函数、冲突消解机制和集群协同规则等进行改进。调整信息交互机制, 减少冗余信息交互, 在不影响算法求解性能的同时降低通信压力; 丰富收益评估函数内容, 在单机收益基础上增加对多机协同情况的评估; 调整冲突消解机制, 兼顾算法探索性能与收敛速度; 设计协同规则, 实现多约束下的集群智能涌现系统的构建。

(4) 适用于任务规划求解的强化学习方法

强化学习算法通过与环境的交互进行学习, 能够有效获取训练过程中的信息, 突破“短视”限制获得整体占优的方案, 适用于任务规划这种多阶段决策问题, 在大规模多约束任务规划问题中应用前景广阔。但任务规划问题场景多样, 存在不同的任务、无人机配置和执行要求等, 需要考虑强化学习方法对环境的敏感问题, 在构建训练环境时考虑问题的复杂性, 提升算法的泛化能力。考虑到环境存在不确定因素干扰, 无人机采取动作后获得的收益不是确定值, 因此可以采用值分布强化学习算法处理不确定因素的问题, 通过训练获得收益的概率分布, 提高方法的鲁棒性。

(5) 多无人机系统任务规划效能评估方法

效能评估可以为无人机配置部署和设计升级提供针对性的参考。需要面向异构多无人机系统在复杂环境下的协同应用, 构建全面的指标体系, 考虑任务能力、协同效率和动态环境适应性等。在指标体系的基础上, 可以使用神经网络方法, 在较少主观因素的影响下, 建立任务规划效能评估方法。同时, 需要建立参数敏感性分析方法, 发现限制多无人机系统的薄弱点, 进而指导无人机配置与设计改进。

任务规划是多无人机协同应用的顶层设计。本文针对这一带约束的组合优化问题, 从表征建模和求解评估两个角度梳理现有研究。从场景分析、任务分配和航迹规划分析任务规划建模, 归纳要素表征、约束条件、不确定因素和航迹协同等方面的研究, 为未来不同场景下的任务规划建模提供参考; 总结任务规划求解中常用的集中式算法和分布式算法的特点及改进策略, 为后期优化方法的选择与改进提供支撑; 分析系统效能评估中指标设计、数值计算和权重设置的研究, 指导后期无人机单元配置与设计改进。最后, 总结未来无人机任务规划研究的若干发展方向。本文的研究对于全面了解多无人机任务规划研究现状具有良好的参考意义。