多无人机协同监视任务规划：从区域覆盖到路径优化的实战建模

1. 项目概述：从一道经典赛题看无人机协同监视的实战建模

十年前，当无人机（UAVs）对大多数人来说还是个新鲜概念时，2014年亚太地区大学生数学建模竞赛（APMCM）的A题《Routine Scheme for UAVs Surveillance》就已经将目光投向了这个领域。这道题的核心，是要求参赛者为多架无人机设计一套在特定区域内进行周期性监视的“例行方案”。说白了，就是给定一片区域、几架无人机，每架飞机有固定的巡航速度和续航时间，目标是规划它们的飞行路径，确保整个区域被定期、高效地“扫视”到，同时还要考虑一些现实约束，比如无人机需要返回基地充电或维护。

今天回头看这道题，它简直是一个预言。如今，无人机在边境巡逻、基础设施巡检、农业监测、城市安防等场景的应用已遍地开花，其核心任务规划逻辑与这道赛题一脉相承。这道题之所以经典，在于它剥离了复杂的硬件细节，直指多智能体协同任务规划中的几个核心数学问题：区域覆盖、路径规划、周期调度和资源约束优化。对于当时的学生而言，这是一个极具挑战性的综合建模训练；对于今天的从业者，复盘这道题，能帮助我们系统地理解监视任务背后的数学模型构建思路、算法选择逻辑以及方案评估方法，其价值远超竞赛本身。

接下来，我将以一名多次参与类似工业级项目规划的技术人员的视角，深度拆解这道赛题。我不会复述获奖论文的每一个公式，而是重点分享：面对这样一个开放性问题，我们该如何一步步构建模型、选择算法、处理细节，并最终得到一个稳健、可实施的方案。无论你是正在备战数模竞赛的学生，还是对无人机路径规划感兴趣的工程师，相信这些从实战中沉淀下来的思路和“避坑指南”，都能给你带来直接的启发。

2. 问题拆解与核心挑战分析

拿到题目，第一步不是急于建立方程，而是要把模糊的“例行监视方案”翻译成清晰的、可量化的数学问题。这需要我们对任务进行逐层拆解。

2.1 核心需求与约束条件明晰化

题目描述通常是概括性的，我们需要从中提取出所有硬性约束和优化目标。

1. 区域与监视要求：

• 区域：通常是一个多边形区域（可能是矩形、不规则形状）。监视意味着区域内的每一点都需要被无人机的传感器（如摄像头）周期性“看到”。
• 覆盖质量：这不是简单的“飞过即覆盖”。需要考虑传感器的视场角（FOV）和有效探测距离。因此，无人机的可覆盖范围是一个以其为圆心、以探测距离为半径的圆形（或扇形），而非一个点。这直接将问题从“线覆盖”提升到了“面覆盖”的复杂度。
• 周期性：“Routine”意味着这不是一次性的全覆盖，而是要求在一个周期T内，区域内任一点至少被覆盖一次。这引入了时间维度，是区别于旅行商问题（TSP）的关键。

2. 无人机平台约束：

• 数量与性能：有N架无人机，每架最大巡航速度V_max，最大续航时间（或航程）C_max。这是最核心的资源限制。
• 基地约束：无人机需要从基地出发，执行完任务后必须返回同一基地（或指定基地）。这决定了每条路径必须是闭合回路（Hamiltonian cycle）。
• 协同要求：多架无人机同时工作，它们之间的路径需要协调，避免重复覆盖浪费资源，同时又要确保没有监视盲区。

3. 优化目标： 题目可能明确或隐含了多个优化目标，通常需要权衡：

• 最大化覆盖效率：在给定周期T内，使被覆盖的区域面积比例最大。
• 最小化最大重访时间：对于区域内任一点，其连续两次被监视的时间间隔的最大值最小化。这能保证最差情况下的监视频率。
• 最小化总能耗或总飞行距离：在满足覆盖要求的前提下，让所有无人机飞行的总距离最短，以节省能源或延长整体任务时间。
• 均衡负载：让各架无人机的飞行时间或航程尽可能均衡，避免个别无人机过度消耗。

注意：在实际建模中，我们很少能同时优化所有目标。标准的做法是确定一个首要目标（如“在续航约束下，最小化最大重访时间”），将其他目标转化为约束条件（如“总飞行距离不超过某个阈值”）或进行多目标优化分析（如帕累托前沿）。

2.2 从实际问题到数学模型的关键跃迁

理解需求后，我们需要用数学语言来描述它。这里有几个关键的建模决策点：

1. 连续空间 vs. 离散网格： 连续区域上的优化极其困难。通用做法是离散化。将监视区域用正方形网格进行划分，每个网格单元（Cell）的大小取决于无人机传感器的分辨率。假设只要无人机覆盖了某个网格的中心点，即认为该网格被覆盖。这样，区域覆盖问题就转化为了对有限个网格点的访问问题。网格粒度是精度与计算复杂度的权衡：网格越小，模型越精确，但计算量呈平方增长。

2. 路径的表示： 无人机的路径不再是连续的曲线，而是一系列网格中心点构成的序列P = {Base, p1, p2, ..., pk, Base}。无人机在两个点之间以直线飞行（假设空域开阔）。飞行距离就是这些点之间的欧几里得距离之和。续航约束转化为：总飞行距离 / V_max <= C_max。

3. “覆盖”的数学定义： 这是核心。设无人机在t时刻位于点pos(t)，其覆盖范围是以该点为圆心、R为半径的圆盘。那么，对于网格点g，在t时刻被覆盖的条件是：distance(pos(t), g) <= R。 对于周期性覆盖，我们需要为每个网格点g定义一个时间序列{t1, t2, ...}，表示其被覆盖的时刻。那么，该点的最大重访时间I_g = max(t_{i+1} - t_i)。整个区域的最大重访时间I_max = max(I_g over all g)。我们的目标就是最小化I_max。

通过以上拆解，一个看似抽象的“监视方案”问题，被清晰地转化为了：在带权图（网格点构成顶点，距离为边权）上，为多个旅行商（无人机）规划一组起点和终点均为基地的回路，使得所有顶点（网格点）被周期性访问，且满足每个旅行商的路径长度约束，同时优化关于访问时间间隔的全局目标函数。这是一个复杂的组合优化问题，是车辆路径问题（VRP）和覆盖路径问题（CPP）的混合体。

3. 核心模型构建与算法选型策略

明确了问题本质，就可以着手构建模型。2014年的优秀论文大多采用了分层或分阶段的建模策略，这是处理复杂问题的有效手段。

3.1 主流建模框架：两阶段法

直接求解全局最优解几乎不可能（NP-Hard问题）。因此，一个务实且高效的策略是将其分解为两个相对独立、依次解决的子问题。

第一阶段：区域划分与任务分配目标：将整个监视区域合理地分配给N架无人机，让每架无人机负责一块“责任区”（Region）。这样就把多机协同问题先简化为N个单机问题。

• 方法：这可以看作一个聚类问题。每个网格点是一个数据点，我们需要将其聚成N类。聚类的依据不仅仅是空间位置接近，还要考虑负载均衡。即，每个聚类所包含的网格点，其构成的单机覆盖路径长度应大致相当，且都不超过无人机的航程限制。
• 常用算法：
  • K-Means/K-Medoids聚类：以距离为基础，简单快速，但可能无法直接满足航程约束。
  • 基于Voronoi图的分区：以各无人机基地（或初始位置）为种子点生成Voronoi图，天然地将空间划分为每个种子点最近区域。然后需要通过迭代调整种子点位置来平衡各分区的工作量。
  • 启发式调整算法：先初步分区，然后计算各分区所需航程，将超限分区的一些边界点“转让”给相邻分区，反复迭代直至满足所有约束。这个过程很像“捏橡皮泥”，直到各块大小重量差不多。

第二阶段：单机覆盖路径规划目标：针对分配给一架无人机的那个“责任区”，规划一条从基地出发、覆盖区内所有网格点、最后返回基地的最优（或次优）路径。

• 问题本质：这变成了一个带返回基地约束的覆盖旅行商问题（Covering TSP）或乡村邮差问题（RPP）。不同于经典TSP要求访问每个“城市”（网格点），这里只要无人机传感器的覆盖圆盘扫过该点即可，因此路径不必精确经过每一点，这提供了优化空间。
• 常用算法：
  • 栅格法（Boustrophedon Coverage）：像耕地一样，规划一组平行的“之”字形路径。这是全覆盖路径规划（CPP）最经典的方法，能保证无遗漏，但路径可能不是最短。适用于规则形状的责任区。
  • 基于图论的方法：将责任区视为一个图。一种巧妙的方法是生成区域的中轴（Medial Axis）或最小生成树（MST），然后将其转化为一条可遍历的路径。沿着“骨架”飞行，能用较短的路径有效覆盖区域。
  • 启发式算法（如遗传算法、模拟退火）：直接以路径点序列为染色体或状态，以路径总长度和覆盖率为适应度函数或能量函数，进行搜索优化。这种方法灵活，能处理不规则区域，但计算量大，且可能陷入局部最优。

实操心得：在两阶段法中，第一阶段的划分质量直接决定了第二阶段的天花板。一个糟糕的划分会导致某个无人机的责任区形状极其不规则，使得第二阶段的路径规划变得低效甚至无法满足续航要求。因此，在划分时，除了空间距离，一定要加入对路径长度预估的反馈。例如，可以用分区内网格点的凸包周长或MST长度作为其工作量的粗略估计，并在聚类目标函数中最小化各分区工作量的方差。

3.2 集成优化模型与算法

两阶段法虽然直观，但可能存在“阶段割裂”的缺点，即第一阶段的局部最优未必导致全局最优。更高级的模型尝试进行集成优化。

1. 混合整数规划（MIP）模型： 这是最“正统”的数学规划方法。可以定义0-1决策变量x_{ij}^k，表示无人机k是否从点i飞往点j；定义连续变量t_i^k表示无人机k访问点i的时间。然后，将续航约束、覆盖约束、流量平衡约束（每个点进出一次）、子回路消除约束等全部用线性或非线性等式/不等式写出，最后设定目标函数（如最小化总时间或最大重访时间）。

• 优点：严谨，若能求解到最优，则是最优解。
• 缺点：对于大规模问题（网格点多），变量和约束数量爆炸，计算不可行，通常只能用于极小规模的问题验证思想。

2. 基于智能优化的多机协同算法： 将多架无人机的完整路径编码为一个整体解，用元启发式算法直接搜索。

• 编码方式：例如，用一个长序列表示所有网格点的访问顺序和无人机归属[UAV1: p1, p2, p3 | UAV2: p4, p5, ...]。
• 算法：遗传算法（GA）、粒子群优化（PSO）、蚁群算法（ACO）都非常适合这类路径规划问题。适应度函数需要复杂设计，要同时惩罚：未覆盖点、续航超标、重访时间过长。
• 优点：理论上能搜索全局最优解，阶段耦合性好。
• 缺点：计算复杂度极高，收敛速度慢，需要精心设计编码、交叉变异操作和适应度函数，参数调优困难。

在实际竞赛和工程中，“两阶段法+精细化启发式调整”是平衡效果与效率的黄金选择。先通过聚类得到一个不错的初始解，再使用局部搜索（如2-opt, 3-opt交换路径片段）或简单的元启发式算法对这个初始解进行微调优化，往往能以可接受的计算成本获得高质量的解。

4. 关键参数计算与模型实现细节

模型框架搭好了，里面的参数和细节才是决定方案是否“靠谱”的关键。这里分享几个容易忽略但至关重要的计算点。

4.1 传感器覆盖模型与网格精度设定

覆盖半径R不是随便定的，它源于传感器性能。假设使用可见光摄像头进行监视：

1. 确定地面采样距离（GSD）：这是关键参数，指图像上一个像素点对应的地面实际尺寸。公式为：GSD = (飞行高度 * 传感器像元尺寸) / 焦距。例如，无人机在100米高飞行，相机像元尺寸3μm，焦距24mm，则GSD ≈ (100 * 0.003) / 24 = 0.0125米 = 1.25厘米。这意味着每个像素代表地面1.25厘米见方。
2. 定义有效覆盖分辨率：如果识别目标需要至少10个像素，那么可识别的目标最小尺寸就是10 * GSD = 12.5厘米。
3. 计算覆盖半径R：这取决于相机的视场角（FOV）。水平FOV为θ，则在地面高度的覆盖半宽为飞行高度 * tan(θ/2)。但通常，我们会取一个保守的、保证图像质量（如边缘畸变小、分辨率足够）的有效半径，它可能小于理论最大半宽。
4. 设定网格大小：网格单元应小于或等于有效覆盖直径（2R）。一个常见的经验法则是，将网格边长设为R / √2，这样可以保证当无人机路径穿过一个网格时，其覆盖圆盘有很大概率能覆盖该网格中心点。如果R=50米，网格边长可设为35米左右。

注意事项：网格不是越小越好。一个1000m*1000m的区域，用10米网格会产生1万个点，用50米网格只有400个点。后者的计算量是前者的1/625。在竞赛有限时间内，必须在精度和可求解性之间做权衡。通常先采用较粗的网格进行算法开发和验证，最终方案可用更细的网格进行验证性计算。

4.2 续航约束与路径长度估算

续航约束总飞行距离 <= C_max * V_max是硬约束。在规划时，我们需要实时估算路径长度。

• 精确计算：对于一条确定的路径序列{p0, p1, ..., pn}，总长度L = Σ distance(p_i, p_{i+1})。
• 快速预估（用于分区阶段）：在还不知道具体路径时，如何预估一个点集S所需的飞行距离？常用方法有：
  • 凸包周长法：计算点集S的凸包（Convex Hull）周长。这给出了覆盖这些点所需路径长度的下界。
  • 最小生成树（MST）长度倍增法：计算点集S的MST总长度L_mst。一条遍历所有点的最短回路（TSP解）长度L_tsp满足：L_mst <= L_tsp <= 2 * L_mst。我们可以用2 * L_mst作为一个保守的估计上界。
  • 基于密度的经验公式：如果点集大致均匀分布在一个面积为A的区域，那么遍历它的最优路径长度经验上正比于√(n*A)，其中n是点数。可以结合历史数据或简单模拟得到一个比例系数。

在分区调整时，使用这些快速预估方法来判断一个分区是否“过载”，比每次调用完整的路径规划算法要高效得多。

4.3 周期T与重访时间I_max的仿真计算

目标函数是最小化最大重访时间I_max。但I_max无法直接从路径规划中得到，必须通过仿真来评估。

1. 路径离散化：将每架无人机的闭合路径，按时间步长Δt（例如1秒）进行离散采样，得到一系列时间-位置对(t, pos)。
2. 覆盖判断：对于每个网格点g，遍历所有无人机的所有时间采样点。如果存在某个采样点满足distance(pos(t), g) <= R，则在时间t记录g被覆盖。
3. 生成覆盖时间序列：对每个网格点g，将其所有被覆盖的时刻按时间排序，得到一个序列T_g = [t1, t2, t3, ...]。
4. 计算重访时间：对于周期性任务，我们需要模拟多个周期。假设仿真总时长为K * T（K为周期数）。对于每个点g，计算其序列中所有连续时间间隔t_{i+1} - t_i，找出其中的最大值，即为该点在仿真时长内的最大重访时间I_g。
5. 全局统计：所有网格点I_g的最大值，就是该路径方案下观测到的I_max。同时，可以统计I_g的平均值、中位数、方差等，全面评估覆盖均匀性。

实操心得：仿真步长Δt的选择很重要。步长太大，可能会错过一些覆盖事件（无人机在两个采样点之间飞过了某个点的覆盖范围），导致I_g被高估。步长太小，计算量巨大。一个安全的选择是Δt < (网格边长) / (2 * V_max)，这样可以保证无人机在任一网格上空飞过时，至少有一个采样点落入该网格。仿真周期数K也要足够多（如10-20个周期），以消除初始位置带来的随机性，获得稳定的统计值。

5. 方案评估、优化与常见问题排查

得到一个初步方案后，如何评价它好不好？如何让它变得更好？在实际操作中，我们总会遇到各种问题。

5.1 多维度方案评估体系

不能只看一个I_max指标。一个全面的评估体系应包含：

5.2 经典优化技巧与策略

基于评估结果，如果方案不理想，可以从以下几个层面进行优化：

1. 分区优化：

• 交换边界点：在两个相邻分区的边界附近，尝试交换一些网格点，计算交换后两分区预估路径长度的变化，如果能使负载更均衡或总距离下降，则接受交换。
• 调整基地位置：如果基地位置可变，可以将其作为变量进行优化。将基地设在所有责任区的“中心”附近，能有效减少往返基地的无效飞行距离。

2. 路径优化：

• 局部搜索：对单条路径使用2-opt、3-opt算法。随机选择路径上的2个或3个节点，断开连接并重新以更短的方式连接，如果总距离缩短则接受。这是优化TSP类路径最有效的方法之一。
• 节点插入/删除：对于覆盖路径，不一定需要访问所有网格点。可以尝试删除一些被过度覆盖区域（即被多条无人机路径或单条路径多次覆盖）的冗余访问点，或者在不增加太多距离的情况下，插入一些覆盖盲区的点。
• 平滑处理：生成的路径可能是折线。考虑到无人机的转弯性能，可以对路径进行平滑处理（如贝塞尔曲线、样条曲线），但平滑后会略微增加路径长度，需要权衡。

3. 协同策略优化：

• 动态责任区：在高级模型中，无人机的责任区不是固定的。可以设计规则，当一架无人机提前完成本区巡视后，可以“援助”相邻未完成区域。
• 异质无人机编队：如果无人机性能不同（速度、续航、传感器不同），模型会更复杂，但也能发挥更大效能。让长航时无人机负责外围远区，让高速无人机负责核心密集区。

5.3 常见问题与排查实录

在实现过程中，一定会踩坑。以下是一些典型问题及解决思路：

问题1：仿真覆盖率永远达不到100%，总有零星网格点未被覆盖。

• 排查：首先检查覆盖半径R和网格大小的比例是否合理。如果网格边长大于√2 * R，那么即使无人机路径穿过网格，其覆盖圆盘也可能够不到中心点。调小网格尺寸或增大有效覆盖半径。
• 检查路径离散化步长：仿真步长Δt太大，会导致“错过”覆盖事件。减小Δt重新仿真。
• 检查分区边界：未被覆盖的点往往出现在两个或多个责任区的交界处，成为“三不管”地带。在分区时，可以设置重叠带，即相邻分区有一定范围的重叠区域，确保边界被双重覆盖。或者在路径规划后，专门检查边界点，微调附近无人机的路径以覆盖它们。

问题2：某架无人机的路径长度远超续航限制。

• 排查：责任区面积过大或形状过于狭长。回顾分区算法，是否只考虑了空间距离聚类，而忽略了路径长度预估？在分区目标函数中显式加入路径长度约束或惩罚项。
• 解决方案：将该超载分区进行拆分，将其一部分网格点强制分配给负载较轻的相邻分区。或者，增加该区域的无人机数量（如果题目允许调整无人机部署）。

问题3：算法运行时间过长，无法在合理时间内得到解。

• 排查：网格粒度是否过细？智能优化算法的种群规模、迭代次数是否设置过高？
• 优化策略：
  • 降粒度：先用粗网格快速得到一个大致可行的方案。
  • 分治：将大区域先分成几个大块，分别规划，再考虑块间的衔接。
  • 改进启发式：用贪婪算法、最近邻法构造初始解，再用局部搜索优化，比完全随机的智能算法收敛快得多。
  • 设定终止条件：不要追求绝对最优，设定一个可接受的目标值或最大运行时间。

问题4：最大重访时间I_max集中在少数几个点，这些点往往是区域边缘或角落。

• 分析：这是覆盖问题的典型现象——中心区域容易被多次覆盖，边缘区域覆盖频率低。
• 优化：这提示你的路径规划过于“中心聚集”。可以特意为边缘和角落点分配更高的权重，在路径规划时，让无人机优先或更频繁地访问这些“关键点”。也可以在目标函数中，不是简单地最小化最大重访时间，而是最小化所有点重访时间的某种加权和，给边缘点更高的权重。

回顾2014年这道APMCM赛题，其价值在于它精准地捕捉了多无人机协同监视任务的核心数学模型。从区域离散化、任务分配到路径规划，再到周期覆盖评估，每一步都对应着实际工程中的关键环节。解决这类问题，没有唯一的“标准答案”，比拼的是对问题本质的理解深度、建模的巧思以及算法实现的稳健性。今天，虽然我们有了更强大的计算工具和更成熟的算法库，但这条从问题分析到模型构建，再到求解与评估的系统化思维路径，依然是应对复杂系统规划类问题的利器。在实际项目中，我们往往还需要考虑更多因素，如通信链路、避障、动态威胁等，但所有这些高级功能，都是建立在本文所探讨的这份最基础的“例行方案”骨架之上的。