协调多个运载器工作分配的任务重新安排

摘要

呈现了用于任务重新安排的系统和方法。实时监控运载器，并且从运载器中检测执行未完成工作的失能运载器。确定包括各运载器的剩余覆盖面积的剩余覆盖集合。计算从各运载器的工作完成位置至失能运载器停止点的行驶距离，以提供行驶集合。基于行驶集合和剩余覆盖集合确定多余覆盖集合，并且计算未完成工作的未完成覆盖面积。将多余覆盖集合与未完成覆盖面积以及剩余覆盖面积进行比较，以提供适应度列表，并且基于适应度列表从运载器中选择指定的运载器。

说明书

发明领域

本公开的实施方式总体上涉及机器人运载器的区域搜索。更具体地，本公开 的实施方式涉及用于协调多个运载器操作的实时任务重新安排。

发明背景

UAV的多种应用环境如搜索和营救、动物调查、边境安全、森林防火监控及 其他应用，是富有挑战的“容易失能（incapacitation-prone）”的环境。当前的搜索 模式方法由于运载器非最佳操作和操作环境变化而不考虑实时重新安排。

发明概述

显示了任务重新安排（mission re-planning）的系统和方法。实时监控运载器， 并且从运载器中检测执行未完成工作的失能运载器。确定各运载器的包括剩余覆 盖区域的剩余覆盖集合。计算从各运载器工作完成位置至失能运载器停止点的行 驶距离，以提供行驶集合。基于行驶集合和剩余覆盖集合确定多余覆盖集合，并 且计算未完成工作的未完成覆盖区域。多余覆盖集合与未完成覆盖区域和剩余覆 盖区域进行比较，以提供适应度（sufficiency）列表，并且基于适应度列表从运载 器中选择指定的运载器。

实施方式提供引导一个或多个无人航空运载器的未完成工作在非最佳情况下 完成的启发式（heuristic based）实时重新安排系统和方法，使得未完成工作可由 剩余运载器覆盖。实施方式能够按比例扩大规模，用于大规模情况，包括，例如， 多于400架无人航空运载器和其中的大量竞争性约束，而没有带来显著的计算负 担。

在实施方式中，任务重新安排系统包括状态模块、所需能力模块、适应度能 力计算模块和选择器模块。状态模块实时监控多个运载器，并从运载器中检测至 少一个执行未完成工作的失能运载器。所需能力模块计算未完成工作（incomplete  task）的未完成覆盖面积（incomplete coverage area）。适应度能力计算模块确定包 括各运载器的剩余（remaining）覆盖面积的剩余覆盖集合。适应度能力计算模块 进一步计算从各运载器的工作完成位置至至少一个失能运载器的停止点的行驶距 离，以提供行驶集合。适应度能力计算模块进一步基于行驶集合和剩余覆盖集合 确定多余覆盖集合，并且将多余覆盖集合与未完成覆盖面积以及剩余覆盖面积进 行比较，以提供适应度列表。选择器模块基于适应度列表从运载器中指定选择的 运载器。

在另一实施方式中，任务重新安排方法实时监控运载器，并从运载器中检测 执行未完成工作的失能运载器。方法进一步确定包括各运载器的剩余覆盖面积的 剩余覆盖集合。方法进一步计算从各运载器的工作完成位置至至少一个失能运载 器的停止点的行驶距离，以提供行驶集合。方法进一步基于行驶集合和剩余覆盖 集合确定多余覆盖集合，并且计算未完成工作的未完成覆盖面积。方法进一步将 多余覆盖集合与未完成覆盖面积以及剩余覆盖面积进行比较，以提供适应度列表， 并且基于适应度列表从运载器中指定选择的运载器。

在进一步的实施方式中，非临时性计算机可读存储介质包括用于任务重新安 排的计算机可执行指令。通过计算机可执行指令执行的方法实时监控运载器并从 运载器中检测至少一个执行未完成工作的失能运载器。通过计算机可执行指令执 行的方法进一步确定包括各运载器的剩余覆盖面积的剩余覆盖集合。通过计算机 可执行指令执行的方法进一步计算从各运载器的工作完成位置到至少一个失能运 载器的停止点的行驶距离，以提供行驶集合。

通过计算机可执行指令执行的方法进一步基于行驶集合和剩余覆盖集合确定 多余覆盖集合，并且计算未完成工作的未完成覆盖面积。通过计算机可执行指令 执行的方法进一步将多余覆盖集合与未完成覆盖面积以及剩余覆盖面积进行比较 以提供适应度列表，并且基于适应度列表从运载器中指定选择的运载器。

根据本公开方面，提供任务重新安排系统。系统包括状态模块，其可操作以 实时监控多个运载器并从运载器中检测至少一个执行未完成工作的失能运载器。 系统进一步包括所需能力模块，其可操作以计算未完成工作的未完成覆盖面积； 和适应度能力计算模块，其可操作以确定各运载器的包括剩余覆盖面积的剩余覆 盖集合，计算从各运载器的工作完成位置到至少一个失能运载器的停止点的行驶 距离以提供行驶集合，基于行驶集合和剩余覆盖集合确定多余覆盖集合，和将多 余覆盖集合与未完成覆盖面积以及剩余覆盖面积进行比较以提供适应度列表。系 统进一步包括选择器模块，其可操作以基于适应度列表从运载器中指定选择的运 载器。

有利地，选择器模块进一步可操作以基于最小化完成未完成覆盖面积的时间 指定选择的运载器。

有利地，选择器模块进一步可操作以基于最小化完成未完成覆盖面积和剩余 覆盖集合的时间指定选择的运载器。

有利地，选择器模块进一步可操作以基于最小化完成未完成覆盖面积的燃料 消耗指定选择的运载器。

有利地，本公开进一步包括适应度列表数据库模块，其可操作以在适应度列 表数据库模块中存储适应度列表。

有利地，运载器包括航空运载器和地面运载器。

有利地，状态模块进一步可操作以通过解码从通信模块接收的相应数据包确 定各运载器的状态。

根据本公开进一步方面，提供任务重新安排的方法。方法通过处理器的作用 执行，并且包括实时监控多个运载器，从运载器中检测至少一个执行未完成工作 的失能运载器，确定各运载器的包括剩余覆盖面积的剩余覆盖集合，计算从各运 载器的工作完成位置到至少一个失能运载器的停止点的行驶距离以提供行驶集 合，基于行驶集合和剩余覆盖集合确定多余覆盖集合，计算未完成工作的未完成 覆盖面积，将多余覆盖集合与未完成覆盖面积以及剩余覆盖面积进行比较以提供 适应度列表，和基于适应度列表从运载器中指定选择的运载器。

有利地，本公开进一步包括基于最小化完成未完成覆盖面积的时间指定选择 的运载器。

有利地，本公开进一步包括基于最小化完成未完成覆盖面积和剩余覆盖集合 的时间指定选择的运载器。

有利地，本公开进一步包括基于最小化完成未完成覆盖面积的燃料消耗指定 选择的运载器。

有利地，本公开进一步包括将适应度列表存储在存储器模块中包括的适应度 列表数据库模块中。

有利地，本公开进一步包括由选择的运载器执行未完成工作。

有利地，本公开进一步包括，如果适应度列表空白，将未完成工作划分为子 工作。优选地，本公开进一步包括将子工作分配于运载器中至少两个选择的运载 器。优选地，本公开进一步包括由至少两个选择的运载器执行子工作。

根据本公开再进一步方面，提供非临时性计算机可读存储介质，其包括用于 任务重新安排的计算机可执行指令。通过计算机可执行指令执行的方法包括实时 监控多个运载器，从运载器中检测至少一个执行未完成工作的失能运载器，确定 各运载器的包括剩余覆盖面积的剩余覆盖集合，计算从各运载器的工作完成位置 至至少一个失能运载器的停止点的行驶距离以提供行驶集合，基于行驶集合和剩 余覆盖集合确定多余覆盖集合，计算未完成工作的未完成覆盖面积，将多余覆盖 集合与未完成覆盖面积以及剩余覆盖面积进行比较以提供适应度列表，和基于适 应度列表从运载器中指定选择的运载器。

有利地，本公开进一步包括用于基于最小化燃料消耗和时间中的一种指定选 择的运载器完成未完成覆盖面积和剩余覆盖集合的计算机可执行指令。

有利地，本公开进一步包括如果适应度列表空白将未完成工作划分为子工作 的计算机可执行指令。

有利地，本公开进一步包括由选择的运载器执行未完成工作的计算机可执行 指令。

本概述的提供是为了以简化形式介绍思路的选择，该思路的选择在下文详细 描述中进一步描述。本概述不意图确定保护主题的关键特征或必要特征，也不意 图用作协助确定保护主题的范围。

附图简述

通过参考详细描述和权利要求同时结合附图考虑可得到对本公开实施方式更 完全的理解，其中贯穿附图同样的参考编号指代相似的元件。附图的提供是为有 助于对本公开的理解，而不是限制本公开的宽度、范围、规模或适用性。附图不 一定按比例制作。

图1是示例性搜索区域的示例，显示根据本公开的实施方式、具有不同的搜 索由凸多边形表示的搜索区域的能力的多个运载器。

图2是根据本公开的实施方式、实时重新安排运载器任务的系统的示例性功 能框图的示例。

图3是显示根据本公开的实施方式、实时重新安排运载器任务的方法的流程 图的示例。

图4是显示根据本公开的实施方式、重新安排运载器任务的方法的流程图的 示例。

详细描述

下文详细描述实质上是示例性的，并非意图限制本公开或本公开实施方式的 应用和用途。具体装置、技术和应用的描述仅作为实例提供。对本文所述实例的 改动对于本领域技术人员而言将是明显的并且本文限定的一般原理可应用于其他 实例和应用，而没有脱离本公开的精神和范围。此外，不意图被前文领域、背景、 概述或下文详细描述中存在的任何明确或暗示的理论束缚。本公开的范围应遵循 权利要求，而不限于本文描述和显示的实例。

本公开的实施方式可在本文中在功能和/或逻辑块组件以及各种处理步骤方面 进行描述。应当理解，这种块组件可通过任何数量的被配置以执行特定功能的硬 件、软件和/或固件组件实现。为简化起见，涉及飞行控制系统、数学建模、数据 通信、搜索和营救技术、飞行器操作及系统其他功能方面的常规技术和组件（以 及系统各个操作组件）可不在本文中详细描述。此外，本领域技术人员将理解， 本公开的实施方式可结合多种不同的飞行器、控制系统、搜索区域和搜索模式实 践，以及本文所述系统仅是本公开的一个实例实施方式。

本文在实际非限制性应用的背景下描述本公开的实施方式，即，利用无人航 空运载器（UAV）搜索区域。但是，本公开的实施方式不限于这种利用UAV的搜 索操作，并且本文所述技术还可用于其他应用和其他运载器，如：无人地面运载 器（UGV），如汽车；无人流体运载器（UFV），如：船、艇和潜水艇；卫星； 遥控运载器；自动遥控运载器；或其他运载器。例如，实施方式可适用于监视、 灭火、跟踪、对抗及其他应用。

在阅读本说明书后对于本领域技术人员而言明显的是，下文是实例，本公开 的实施方式不限于按照这些实例进行操作。可应用其他实施方式，并且可进行结 构改变，而没有脱离本公开示例性实施方式的范围。

UAV的许多应用环境如搜索和营救、动物调查、边界安全、森林防火监控及 其他应用是富有挑战的“容易失能”的环境。本公开的实施方式提供用于在一个或多 个UAV在其任务期间失能的情况下重新安排UAV或UAV组的系统和方法。

实施方式提供启发式重新安排系统和方法，其可处理多个UAV及其间的多种 竞争性约束。例如，重新安排算法基于并且作为如下因素的函数计算较高动力储 备：如邻近度、异类度、能力及其他约束，如下文更详细地说明的。

因此，当一个UAV失能时，重新安排算法在全部可用UAV中运行竞赛选择， 以找到和选择最接近的、最可用的和具有较高动力储备，并且将失能UAV的未完 成工作指定给选择的UAV。因此，重新安排算法实时重新安排和重新分配给定工 作，使得搜索可利用可用资源（或参与搜索的其余运载器）执行和完成。本公开 的实施方式对于大规模情况（即，多于400架运载器）明显易于扩大规模，而没 有导致显著的计算成本。

在一个实施方式中，方法包括模因算法（memetic algorithm），其用于响应执 行搜索的遥控运载器如UAV的非最佳条件期间。在模因计算的背景下，模因算法 （MA）是用于解决优化问题的技术。模因算法是利用局部搜索程序或方法提炼群 体中的个体的演化算法（EA）。本文所用模因方法的目的是通过多边形分解作为 UAV之间和每个子多边形的工作分割形式最小化扫描时间，如下文更详细说明的。

术语“重新安排”是指对预先建立的UAV预期采取的途径或飞行路径进行调节 的方法。重新安排需求的产生是因为至少一个UAV在任务执行期间的意外失能。 至少一个UAV的失能可由如下引起：非最佳操作条件、操作人员停用至少一个 UAV或其他现象。目标可以是最小化扫描失能UAV留下的剩余多边形分区所需 的时间。修改后安排的计算通常应在明显窄的时间窗内完成。

术语实时是指连续发送和接收而极少或没有时间延迟的信号。术语近实时指 基本上无明显时间延迟的实时信号。时间延迟可以是由如下引起的延迟：例如但 不限于，事件发生之间的自动数据处理或网络传输或其他计算和传输延迟。在本 文中，术语实时既指实时又指近实时。

无人航空运载器（UAV）是灵活的，并且可用于监视、搜索和营救工作或甚 至用于跟踪和对抗。配备良好图像传感器的UAV可向地面控制操作人员提供精确 且实时的图像，然后地面控制操作人员将传送该信息以有助于作出决策。另外， 与直升机平均飞行时间恰好超过两小时相比，一些新型UAV，如用于近期阿富汗 和伊拉克战争的Predator^TM，可飞行多于30小时，而无需补充燃料。

UAV长期徘徊的能力相对于载人飞行器具有重要的操作优势。UAV较长的飞 行时间意味着其可用于处理艰难的工作，如在公海搜索和营救人员，这一般需要 长期运行。UAV可配备热检测传感器，以检测藏匿在树下或房下的人，进一步扩 展UAV部署用于不同的应用情况。

图1是示例性搜索区域的示例图，其显示不同能力的多个运载器搜索由凸多 边形102表示的搜索区域。UAV可操作以由一个或多个固定基地位置发射和操作。 S1-S3表示固定基地位置，UAV在部署于任务中之前是驻守在此。

各基地S1-S3可包括多个UAV，并且每个UAV可包括多个能力。各UAV可 包括不同的速度、图像传感器分辨率（足迹（footprint））和飞行续航力。UAV的 能力度量可限定为UAV可扫描的总面积，并可基于UAV速度、飞行续航力和足 迹计算，如下文更详细地说明。

分配程序的第一步包括将凸多边形102划分为多个部分，使得指定给每一个 基地S1-S3的子面积与基地S1-S3每一个的总能力成比例。在图1所示的实施方式 中，几种UAV应用于工作。基地S1-S3每一个的总能力是分别位于基地S1-S3每 一个的全部UAV能力的总和。例如，基地S1的总能力是两架UAV110-112的能 力总和，基地S2的总能力是两架UAV114-116的能力总和，基地S3的总能力是 三架UAV118-122的能力总和。在指定各基地S1-S3的各子面积后，利用模因方 法找到最佳UAV组合以执行扫描。

模因方法基于驻守在相应基地（S1-S3）的各个UAV110-122的能力进一步分 割指定给各基地S1-S3（Si，i=1,2,3）的子面积，使得各UAV在最短搜索时间内 执行特有的搜索。模因方法被述及在共有的美国专利申请号12/960,440中，在此 其全部内容被引入本文作为参考。

美国专利申请号12/960,440中更详细说明的算法将搜索多边形102划分，并 将各部分104、106和108分别指定给各基地S1-S3。

基地i包括表示为C_i的能力，其是基地i中全部UAV的能力总和，并且多边 形（图1中的102）上存在m个基地。工作空间被划分成m个部分（104、106 和108），并且每个部分104/106/108分别被指定给一个基地S1/S2/S3。如果满足 下列等式，则认为方案可行：

面积(P₁):面积(P₂):…:面积(P_m)=C₁:C₂：…:C_m

其中部分P_i的面积是面积(P_i），因此基于下列面积约束，所有部分P_i的总面 积应等于给定多边形102的面积：

本公开的实施方式提供在UAV118-122中的个体UAV在其任务期间失能的情 况下重新安排UAV118-122中的至少一个UAV的系统和方法，如下文更详细地说 明。

图2是根据本公开的实施方式、实时重新安排运载器任务的系统200的示例 性功能框图示例。关于系统200描述的不同示例性方框、模块、处理逻辑和电路 可通过如下实施或执行：通用处理器、内容可寻址存储器、数字信号处理器、特 定应用集成电路、现场可编程门阵列、任何适当的可编程逻辑装置、离散门或晶 体管逻辑、离散硬件组件或其任意组合，它们被设计以执行本文所述的实时重新 安排运载器任务。

系统200可以是与图1中的UAV232和236或UAV118-122连通的网络架构 的部分，或可以是独立的便携装置，如移动电话、个人数字助理（PDA）如 Blackberry^TM装置、Palm Treo^TM、MP3播放器、iPod^TM、iPad^TM或其他类似的便携 装置。在一些实施方式中，系统200可以是，例如但不限于，个人无线计算机， 如无线笔记本计算机、无线掌上型计算机,或其他移动计算机装置。系统200提供 多个自动运载器任务的实时重新安排。因此，系统200实时重新安排和重新分配 给定工作，以使剩余运载器参与搜索，从而完成失能UAV的未完成工作。

系统200可包括工作分配模块202、命令模块204、状态模块206、实时重新 安排模块208、处理器模块220、存储器模块222和通信模块224。

工作分配模块202被配置以将多个工作分别分配给UAV232和236（类似于 图1中的UAV110-122）。

命令模块204被配置以指挥分配给UAV232和236中每一个的工作。命令模 块204通过通信模块224指挥UAV232和236部署。以这种方式，通信模块224 可充当系统200和任务管理框架228之间的通信桥。例如但不限于，通信模块224 可利用无线数据通信链路230和网络插座（未显示）提供通信桥。然后通过任务 管理框架228处理任务系列点，以控制全部UAV232和236遵循任务系列点。任 务系列点可包括，例如但不限于，UAV232和236每一个将遵循以执行工作如区 域搜索的UAV232和236每一个的系列航点。

状态模块206被配置以实时监控UAV232和236和从UAV232和236中检测 至少一个执行未完成工作的失能UAV。各UAV232/236携载的健康管理逻辑（未 显示）监控UAV232/236的状态，并向通信模块224发送与状态相应的数据包。 通信模块224检验数据包的有效性（即，通过利用CheckSUM、循环冗余检验（CRC） 或其他错误校正方法），并将数据包传递至状态模块206。然后，状态模块206可 解码数据包，以检验UAV232/236中任一个是否失能。

实时重新安排模块208被配置以基于适应度列表从UAV232/236和UAV 110-122中指定至少一个活跃UAV以完成未完成工作。例如，实时重新安排模块 208可从232/236和UAV110-122中选择至少一个最接近的、最可用的并且具有较 高动力储备的活跃UAV来完成未完成工作。实时重新安排模块208可包括所需能 力计算模块210（所需能力模块210）、搜索模块212、适应度能力计算模块214、 适应度列表数据库模块216和选择器模块218。

如上所述，实时重新安排模块208被配置以处理多个UAV和其中的多种竞争 约束。例如，实时重新安排模块208基于并且作为诸如邻近度、异类度、能力和/ 或其他约束的因素的函数计算较高动力储备。

实时重新安排模块208考虑UAV232、236和110-122之间的邻近度，用于计 算较高能量服务者（server）。因此，当一个UAV失能时，实时重新安排模块208 运行全部可用UAV之间的竞赛选择，以找到最接近的、最可用的并且具有较高动 力储备，并将失能UAV的未完成工作指定给选择的UAV。实时重新安排模块208 然后相应地实时重新安排和重新分配给定工作，以使搜索可利用可用资源（或参 与搜索的其余运载器）执行和完成。

实时重新安排模块208考虑异类度，因为参与任务——即搜索——的UAV 232、236和110-122不一定是同类的，并且可包括，例如但不限于，飞机、直升 机或其他运载器。因此，在非同类情况下，邻近度可能不意味着较高能量储备。 因为，飞机可比邻近直升机更快并且利用更少能量到达停止点。

实时重新安排模块208考虑能力，因为UAV如UAV232/236和UAV110-122 携带的传感器组可具有不同的能力，例如，不同的传感器足迹。如果邻近UAV具 有的传感器足迹小于较远的UAV，则邻近UAV的搜索栅格将较精细，这表示邻 近UAV可以移动更多以覆盖搜索区域。

所需能力计算模块210被配置以计算未完成工作的未完成覆盖面积。能力度 量基于如下运载器资源计算：如但不限于，传感器足迹、速度、续航力、燃料及 其他资源。如上所述，各基地（图1中的S1-S3）包括多个UAV——来自具有不 同能力的UAV232、236和110-122。来自UAV232、236和110-122的各UAV可 具有不同速度、图像传感器分辨率（足迹/传感器足迹）和飞行续航力。UAV的能 力度量可被限定为UAV可扫描的总面积，并可通过速度、飞行续航力（最大飞行 时间）和足迹的乘积计算。例如，UAV能力可基于下列关系确定：

UAV能力=足迹*速度*续航力

因此，所需能力计算模块210可如下确定处理失能UAV的未完成工作所需的 能力（剩余面积）：

剩余面积（米²)=足迹（米）*速度（米/秒）*续航力（秒）。

搜索模块212被配置以从UAV232、236和110-122中搜索活跃UAV。搜索 模块212可基于从通信模块224接收的数据搜索活跃UAV，如下文所说明的。

适应度能力计算模块214可操作以提供适应度列表，该适应度列表包括来自 UAV232、236和110-122的具有完成失能UAV的未完成工作所需的能力的活跃 UAV的列表。所需能力的特征在于，未完成覆盖面积（剩余面积（remainArea））。 以这种方式，适应度能力计算模块214确定表征各UAV232、236和110-122的未 扫描区域的剩余覆盖集合（k.剩余面积（k.leftArea）），并计算各UAV232、236 和110-122从工作完成位置终点（k）至失能运载器停止点（点）的行驶距离（到 达邻近度（getAdjacency）（点，终点(k)）），从而提供行驶集合（邻近度（k）= 到达邻近度(点，终点(k)））。

然后适应度能力计算模块214基于行驶集合（通过足迹度量的邻近度（k））） 和剩余覆盖集合（k.剩余面积）利用下列关系确定多余覆盖集合（多余值（k））：

多余值（k)=邻近度（k）*足迹+k.剩余面积

具有面积单位的（邻近度（k）*足迹）和具有距离单位的邻近度（k）可互换 地用作行驶集合。

行驶集合（邻近度（k）*足迹）是各UAV到达终点（k）从而开始覆盖失能 UAV的未完成覆盖面积（剩余面积）需要行驶的面积。剩余覆盖集合（k.剩余面 积）是来自UAV232、236和110-122的各UAV的未扫描面积。因此，多余覆盖 集合（多余值（k））确定来自UAV232、236和110-122的各UAV可需要多少面 积覆盖或能力以完成扫描其自身的未扫描面积（k.剩余面积）加上到达终点（k） 的能力（邻近度（k）*足迹）。然后适应度能力计算模块214基于下列关系比较 各UAV232、236和110-122的多余覆盖集合多余值（k）与未完成覆盖面积（剩 余面积）以及剩余覆盖面积（k.动力），以提供适应度列表：

如果（（k.动力–剩余面积-多余值（k））>0），其中

剩余面积是未完成覆盖面积，其表征处理失能UAV的未完成工作所需的能力， k.动力是剩余覆盖面积，其表征各UAV的剩余能力，以及k是大于或等于1的整 数，表示特定UAV，多余值（k）表征各UAV完成扫描其自身指定区域所需的能 力加上到达终点（k）所需的能力。

如果k.动力超过剩余面积和多余值（k）的总和，则选择UAV（k）作为候选 可用活跃UAV，以完成失能UAV的未完成工作。

适应度列表数据库模块216包括适应度列表，适应度列表包括完成失能UAV 的未完成工作的可用活跃UAV。

选择器模块218被配置以基于各种约束从适应度列表中选择来自UAV 110-122的至少一个可用活跃UAV，以完成未完成工作。例如但不限于，选择器 模块218基于如下指定选择的UAV完成失能UAV的未完成工作：例如，最小化 完成未完成覆盖面积的时间、最小化完成未完成覆盖面积和剩余覆盖集合的时间、 最小化完成未完成覆盖面积的燃料消耗或其他约束。

处理器模块220包括处理逻辑，其被配置以实施系统200操作相关的功能、 技术和处理工作。具体地，处理逻辑被配置以支持本文所述系统200的搜索功能。 例如但不限于，处理器模块220可被适当地配置以执行模因算法，指挥状态模块 206实时监控UAV110-122和从UAV110-122中检测至少一个执行未完成工作的 失能UAV，并指挥所需能力计算模块210计算未完成工作的未完成覆盖面积。例 如但不限于，处理器模块220可被适当地配置以指挥适应度能力计算模块214提 供适应度列表，指挥选择器模块从适应度列表中选择至少一个可用活跃运载器， 指挥存储器模块222在其中的适应度列表数据库模块216中存储适应度列表，和 指挥和/或执行系统200的其他功能。

处理器模块220可通过如下实施或实现：通用处理器、内容可寻址存储器、 数字信号处理器、特定应用集成电路、现场可编程门阵列、任何适当的可编程逻 辑装置、离散门或晶体管逻辑、离散硬件组件或其任意组合，它们被设计以执行 本文所述功能。以这种方式，处理器可作为微处理器、控制器、微控制器、状态 机或类似物实现。处理器还可作为计算装置组合，例如，数字信号处理器和微处 理器的组合、多个微处理器、一个或多个微处理器结合数字信号处理器核、或任 何其他这种构造而实施。

存储器模块222可以是具有适量存储器的任何适当的数据存储区，该存储器 被安排以支持系统200的操作。存储器模块222以下文所述方式被配置，以按支 持系统200功能性所需存储、保留和提供数据。在实际实施方式中，存储器模块 222可包括，例如但不限于，非挥发性存储装置（非挥发性半导体存储器、硬盘装 置、光盘装置及类似物）、随机存取存储装置（例如，SRAM、DRAM）或本领域 已知的任何其他形式的存储介质。存储器模块222可连接于处理器模块220，并被 配置以存储，例如但不限于，相应于搜索情况的输入参数值和输出参数值。

存储器模块222可存储，例如但不限于，运载器能力（例如，覆盖面积）、 运载器性能参数（例如，速度、转弯速率等）、扫描模式、扫描时间、运载器操 作成本（例如，燃料成本）、适应度列表数据库模块216及其他数据。另外，存 储器模块222可表现，例如但不限于，动态更新数据库——包括用于存储搜索模 式航线点、UAV能力或其他数据的表。存储器模块222还可存储，例如但不限于， 处理器模块220执行的计算机程序、操作系统、应用程序、用于执行程序处理的 试验数据或其他程序或数据。

存储器模块222可连接于处理器模块220，使得处理器模块220可从存储器模 块222读取信息和向存储器模块222写入信息。作为实例，处理器模块220和存 储器模块222可位于其各自的ASIC中。存储器模块222也可整合到处理器模块 220中。在实施方式中，存储器模块222可包括高速缓冲存储器，用于存储临时变 量或在将由处理器模块220执行的指令执行期间的其他中间信息。

通信模块224管理UAV232和236（类似于图1中的UAV110-122）之间的 通信网络。通信模块224分别通过无线数据通信链路234和238从UAV232和236 和向UAV232和236发送和接收数据。通信模块224可包括发送器模块（未显示） 和接收器模块（未显示），并可连接于可支持特定无线通信协议和调制方案的RF 天线布置226，从而与UAV232和236通信。

通信模块224被配置以将相应于各UAV232和236的数据包传递至状态模块 206。例如，如上所述，各UAV232和236携载的健康管理逻辑（未显示）监控各 UAV232和236的状态，并发送相应数据包至通信模块224。通信模块224检验数 据包的有效性（即，通过利用CheckSUM、CRC或其他错误校正方法），并将数 据包传递至状态模块206。然后，状态模块206可解码数据包，以检验UAV232 和236中的任一个是否失能。

通信模块224接收各UAV的剩余飞行能力，如但不限于，剩余燃料、飞行时 间、健康状况——如影响各UAV能力的退化和非最佳性能、状态（例如，失能状 态或操作状态）及其他数据。通信模块224通信地连接于任务管理框架228，并被 配置以通过无线数据通信链路230发送这种信息至任务管理框架228。任务管理框 架228被配置以执行由实时重新安排模块208提供的重新安排，从而实时解决不 明事件，因而保持搜索工作。

图3是流程图示例，显示根据本公开的实施方式、重新安排运载器任务的方 法300。关于方法300执行的各种工作可通过软件、硬件、固件、具有用于执行处 理方法的计算机可执行指令的计算机可读介质或其任意组合执行。方法300可记 录在计算机可读介质中，如半导体存储器、磁盘、光盘及类似物，并可被存取和 执行——例如，通过计算机CPU，如其中存储计算机可读介质的处理器模块220。

应当理解，方法300可包括任意数量的另外的或可选的工作，图3所示工作 无需以示例顺序执行，并且方法300可合并到具有本文未详细描述的其他功能的 更全面的程序或方法中。以示例为目的，下文对方法300的描述可涉及上文关于 图1-2述及的元件。

在实际实施方式中，方法300的部分可由系统200的不同元件执行，如：工 作分配模块202、命令模块204、状态模块206、实时重新安排模块208、处理器 模块220、存储器模块222、通信模块等。方法300可具有类似于图1-2所示实施 方式的功能、材料和结构。因此，共有的特征、功能和元件可不在此赘述。.

方法300可通过如下开始：工作分配模块如工作分配模块202向多个运载器 如UAV232和236分别分配多个分配工作（工作302）。

方法300可通过如下继续：由运载器执行分配工作（工作304）。

方法300可通过如下继续：状态模块如状态模块206监控运载器（工作306）。

方法300可通过如下继续：状态模块206确定运载器中的失能运载器是否执 行未完成工作（调查（inquiry）工作308）。如果未完成工作未被失能运载器执行 （调查工作308的“否”分支），则方法300可进行至工作306。否则（调查工作308 的“是”分支），方法300可通过如下继续：计算完成失能运载器的未完成工作所需 的能力（工作312）。

方法300可通过如下继续：搜索模块212如搜索模块212从运载器中搜索活 跃运载器（工作314）。

方法300可通过如下继续：适应度能力计算模块如适应度能力计算模块214 计算各活跃运载器完成未完成工作的可用能力（工作316）。可用能力在下文方法 400的工作408的背景中进行进一步说明。

方法300可通过如下继续：适应度能力计算模块214生成具有完成未完成工 作所需能力的活跃运载器的适应度列表（工作318）。

方法300可通过如下继续：处理器模块如处理器模块220确定适应度列表是 否空白（调查工作320）。

如果适应度列表是非空白（调查工作320的“否”分支），则方法300可通过如 下继续：从活跃运载器中指定选择的运载器完成未完成工作（工作322）。

方法300可通过如下继续：由所选运载器完成未完成工作（工作324），并进 行至任务结束（工作310）。

如果适应度列表空白（调查工作320的”是”分支），则方法300可通过如下继 续：将未完成工作划分为子工作（工作326）。

方法300可通过如下继续：工作分配模块202向至少两个从运载器中选择的 运载器分配子工作（工作328）。

方法300可通过如下继续：由至少两个所选运载器执行子工作（工作330）， 并进行至任务结束（工作310）。

图4是流程图示例，显示根据本公开的实施方式、重新安排运载器任务的方 法400。关于方法400执行的不同工作可通过软件、硬件、固件、具有用于执行处 理方法的计算机可执行指令的计算机可读介质或其任意组合执行。方法400可记 录在计算机可读介质中，如半导体存储器、磁盘、光盘及其他非临时性介质，并 可被存取和执行——例如，通过计算机CPU，如其中存储计算机可读介质的处理 器模块220。

应当理解，方法400可包括任意数量的另外的或可选的工作，图4所示工作 无需以示例顺序执行，并且方法400可合并到具有本文未详细描述的其他功能的 更全面的程序或方法中。以示例为目的，下文对方法400的描述可涉及上述关于 图1-2述及的元件。

在实际实施方式中，方法400的部分可通过系统200的不同元件执行，如： 工作分配模块202、命令模块204、状态模块206、实时重新安排模块208、处理 器模块220、存储器模块222、通信模块等。方法400可具有类似于图1-2所示实 施方式的功能、材料和结构。因此，共同的特征、功能和元件可不在此赘述。

方法400可通过如下开始：状态模块如状态模块206实时监控多个运载器如 UAV232和236（工作402）。

方法400可通过如下继续：状态模块206从运载器中检测至少一个执行未完 成工作的失能运载器（工作404）。例如，实时重新安排模块208接收表示UAVk 已经失能而没有完成其扫描工作的事件。此时，实时重新安排模块208执行竞赛 选择程序，其中选择完成其工作和具有足够能力的UAVr以处理由于UAVk失能 而留下的剩余面积（剩余面积）。随后，改道（rerouting）程序指挥UAVr飞行至 失能UAVk的位置，并继续UAVk的未完成工作。在此，k和r均是大于或等于1 的整数，均表示不同的具体UAV。

方法400可通过如下继续：计算未完成工作的未完成覆盖面积（剩余面积） （工作406）。未完成覆盖面积（剩余面积）包括完成失能UAV的未完成工作所 需的能力。

方法400可通过如下继续：计算各运载器完成未完成工作的可用能力（工作 408），如下文工作410-416所述。实时重新安排模块208可处理大量UAV和它 们之间的多种竞争性约束。例如，重新安排算法考虑UAV之间的邻近度（邻近度 （k））。因此，当一架UAV失能时，实时重新安排模块208运行全部可用UAV 之间的竞赛选择，以找到最接近的、最可用的并且具有较高动力储备，并向选择 的UAV指定新工作。

方法400可通过如下继续：适应度能力计算模块如适应度能力计算模块214 计算从各运载器的工作完成位置到至少一个失能运载器的停止点的行驶距离，以 提供行驶集合（邻近度（k）*足迹））（工作410）。

方法400可通过如下继续：适应度能力计算模块214基于行驶集合和剩余覆 盖集合确定多余覆盖集合多余值（k）（多余值（k)=邻近度（k）*足迹+k.剩余 面积）（工作412）。

方法400可通过如下继续：适应度能力计算模块214确定各运载器的包括剩 余覆盖面积的剩余覆盖集合（k.剩余面积）（工作414）。

方法400可通过如下继续：适应度能力计算模块214比较多余覆盖面集合（多 余值（k））与未完成覆盖面积（剩余面积）以及剩余覆盖面积（k.动力），以提 供适应度列表（工作416）。

方法400可通过如下继续：适应度列表数据库模块如适应度列表数据库模块 216存储适应度列表（工作418）。

方法400可通过如下继续：基于适应度列表从运载器中指定选择的运载器（工 作420）。

方法400可通过如下继续：选择器模块218如选择器模块218基于最小化完 成该未完成覆盖面积（剩余面积）的时间指定选择的运载器（工作422）。时间可 例如通过选择邻近度（k）最小、速度最大和/或足迹大的UAV进行最小化。例如， 如果邻近UAV具有的传感器足迹小于较远的UAV，则邻近UAV的搜索栅格将更 精细，这表示其可行驶更多以覆盖区域。因此，为最小化时间，可选择较远UAV。

方法400可通过如下继续：基于最小化完成未完成覆盖面积（剩余面积）和 剩余覆盖集合（k.剩余面积）的时间指定选择的运载器（工作424）。

方法400可通过如下继续：选择器模块218基于最小化完成未完成覆盖面积 的燃料消耗指定选择的运载器（工作426）。燃料可例如通过选择燃料燃烧能力最 小的UAV进行最小化。

方法400可通过如下继续：由所选运载器执行未完成工作（428）。方法400 可通过如下继续：如果适应度列表空白，将未完成工作划分为子工作（430）。在 实时重新安排期间，可存在无UAV具有剩余能力以处理失能UAV的剩余面积的 情况。在这种情况下，具体剩余面积可在活跃UAV组之间划分，该活跃UAV应 协作扫描区域。换句话说，实时重新安排模块208不知道具体失能UAV留下的剩 余面积的形状；实时重新安排模块208知道剩余系列点。在这种情况下，实时重 新安排模块208将剩余系列点划分成两部分，并将每个部分分配于至少一个UAV。

方法400可通过如下继续：选择器模块218向运载器中至少两个所选运载器 分配子工作（工作432）。

方法400可通过如下继续：由至少两个运载器执行子工作（工作434）。

以这种方式，本公开的实施方式提供启发式重新安排算法，其利用实时重新 安排系统能使剩余运载器覆盖失能运载器的未完成工作。减少搜索时间的模因工 作分配算法可用于生成多个无人运载器覆盖的区域搜索方法——通过考虑其不同 的检测和范围能力以及基地位置。实施方式能够对于大规模情况——包括例如， 多于400架无人运载器——扩大规模，而不导致明显的计算负担。

当以软件或固件实施时，系统200的不同元件如本文所述工作分配模块202、 命令模块204、状态模块206、实时重新安排模块208和通信模块224本质上是执 行不同工作的代码段或指令。程序或代码段可存储在非临时性介质如处理器可读 介质中，或通过载波中包含的计算机数据信号在传输介质或通信路径上传输。

"处理器可读介质"或"机器可读介质"可包括任何可存储或传递信息的非临时 性介质。处理器可读介质的实例包括电子回路、半导体存储器装置、ROM、闪存、 可擦写ROM（EROM）、软盘、CD-ROM、光盘、硬盘、光纤介质、RF链路或其 他非临时性介质。

在本文中，术语“计算机程序产品”、“计算机可读介质”及类似物可一般用于指 如下介质：例如，存储器、存储装置、存储单元或其他非临时性介质。这些和其 他形式的计算机可读介质可涉及存储处理器模块220应用的一个或多个指令，以 使处理器模块220执行指定操作。这种指令，一般被称为“计算机程序代码”或"程 序代码"（其可以计算机程序形式分组或其他分组），在执行时，实现应用系统如 系统200的方法。

本领域技术人员将理解，关于实施方式如本文公开的系统200所描述的不同 示例性方框、模块、回路和处理逻辑可以硬件、计算机可读软件、固件或其任何 实际组合实施。为明确示例硬件、固件和软件的这种可交换性和相容性，一般对 不同示例性组件、方框、模块、回路和步骤在其功能性方面进行描述。这种功能 性是否以硬件、固件或软件实施取决于施加于整个系统的具体应用和设计约束。 了解本文所述思路的本领域技术人员可针对每个具体的应用以适当方式实施这种 功能性，但是这种实施决定不应被解释为导致脱离本发明的范围。

虽然至少一个实例实施方式已被展示在前文详细描述中，但应理解，多种改 动是存在的。还应理解，本文所述实例实施方式或实施方式并非意图以任何方式 限制主题的范围、应用性或构造。相反，前文详细描述将为本领域技术人员提供 便捷的路线图以实施所述实施方式或实施方式。应当理解，在元件功能和安排方 面可进行多种改变，而不脱离权利要求限定的范围，这包括在提交本专利申请时 已知的等同形式和可预期的等同形式。

上文描述涉及“连接”或“耦合”在一起的元件或节点或部件。如本文所用，除非 另外明确表述，“连接”意为一个元件/节点/部件直接接合（或直接连通）另一元件 /节点/部件，并且不一定以机械方式。同样，除非另外明确表述，“耦合”意为一个 元件/节点/部件直接或间接接合（或者，直接或间接连通）另一元件/节点/部件， 并且不一定以机械方式。因此，虽然图1-2显示元件的实例安排，但另外的插入元 件、装置、部件或组件可存在于本公开的实施方式中。

本文所用的术语和短语及其变型，除非另外明确表述，应被解释为是开放式 的，而非限制性的。作为前述实例：术语“包括”应被理解为表示“包括但不限于” 或类似意思；术语“实例”用于提供讨论项目的示例性例子，而非其穷尽或限制性的 列举；和形容词如“常规的”、“传统的”、“正常的”、“标准的”、“已知的”和类似含 义的术语不应被解释为将所述项目限定于给定时期或可用于给定时间的项目，相 反应被理解为包括现在或将来任何时间可用或已知的常规的、传统的、正常的或 标准的技术。

同样，除非另外明确描述，用连接词“和”连接的项目组不应被理解为要求这些 项目中的每一个均存在于分组中，相反应被理解为是“和/或”。类似地，除非另外 明确描述，用连接词“或”连接的项目组不应被理解为要求组内相互排他，相反也应 被理解为是“和/或”。另外，虽然可以单数形式描述或请求保护本公开的项目、元 件或组件，但考虑复数形式处于其范围内，除非明确表述限定为单数。一些实例 中扩展用词和短语如“一个或多个”、“至少”、“但不限于”或其他类似短语的存在不 应被理解为意指，在这种扩展短语可不存在时就意图或要求较窄的情况。