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_{i1} - 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不是随便定的它源于传感器性能。假设使用可见光摄像头进行监视确定地面采样距离GSD这是关键参数指图像上一个像素点对应的地面实际尺寸。公式为GSD (飞行高度 * 传感器像元尺寸) / 焦距。例如无人机在100米高飞行相机像元尺寸3μm焦距24mm则GSD ≈ (100 * 0.003) / 24 0.0125米 1.25厘米。这意味着每个像素代表地面1.25厘米见方。定义有效覆盖分辨率如果识别目标需要至少10个像素那么可识别的目标最小尺寸就是10 * GSD 12.5厘米。计算覆盖半径R这取决于相机的视场角FOV。水平FOV为θ则在地面高度的覆盖半宽为飞行高度 * tan(θ/2)。但通常我们会取一个保守的、保证图像质量如边缘畸变小、分辨率足够的有效半径它可能小于理论最大半宽。设定网格大小网格单元应小于或等于有效覆盖直径2R。一个常见的经验法则是将网格边长设为R / √2这样可以保证当无人机路径穿过一个网格时其覆盖圆盘有很大概率能覆盖该网格中心点。如果R50米网格边长可设为35米左右。注意事项网格不是越小越好。一个1000m*1000m的区域用10米网格会产生1万个点用50米网格只有400个点。后者的计算量是前者的1/625。在竞赛有限时间内必须在精度和可求解性之间做权衡。通常先采用较粗的网格进行算法开发和验证最终方案可用更细的网格进行验证性计算。4.2 续航约束与路径长度估算续航约束总飞行距离 C_max * V_max是硬约束。在规划时我们需要实时估算路径长度。精确计算对于一条确定的路径序列{p0, p1, ..., pn}总长度L Σ distance(p_i, p_{i1})。快速预估用于分区阶段在还不知道具体路径时如何预估一个点集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无法直接从路径规划中得到必须通过仿真来评估。路径离散化将每架无人机的闭合路径按时间步长Δt例如1秒进行离散采样得到一系列时间-位置对(t, pos)。覆盖判断对于每个网格点g遍历所有无人机的所有时间采样点。如果存在某个采样点满足distance(pos(t), g) R则在时间t记录g被覆盖。生成覆盖时间序列对每个网格点g将其所有被覆盖的时刻按时间排序得到一个序列T_g [t1, t2, t3, ...]。计算重访时间对于周期性任务我们需要模拟多个周期。假设仿真总时长为K * TK为周期数。对于每个点g计算其序列中所有连续时间间隔t_{i1} - t_i找出其中的最大值即为该点在仿真时长内的最大重访时间I_g。全局统计所有网格点I_g的最大值就是该路径方案下观测到的I_max。同时可以统计I_g的平均值、中位数、方差等全面评估覆盖均匀性。实操心得仿真步长Δt的选择很重要。步长太大可能会错过一些覆盖事件无人机在两个采样点之间飞过了某个点的覆盖范围导致I_g被高估。步长太小计算量巨大。一个安全的选择是Δt (网格边长) / (2 * V_max)这样可以保证无人机在任一网格上空飞过时至少有一个采样点落入该网格。仿真周期数K也要足够多如10-20个周期以消除初始位置带来的随机性获得稳定的统计值。5. 方案评估、优化与常见问题排查得到一个初步方案后如何评价它好不好如何让它变得更好在实际操作中我们总会遇到各种问题。5.1 多维度方案评估体系不能只看一个I_max指标。一个全面的评估体系应包含评估维度具体指标说明与期望覆盖完备性覆盖率在周期T内至少被覆盖一次的网格点比例。必须达到100%或无限接近。覆盖及时性最大重访时间I_max核心指标越小越好。直接反映“最坏情况”下的监视间隔。平均重访时间I_avg反映整体平均监视频率。重访时间标准差I_std反映覆盖均匀性。越小说明各点监视频率越一致。资源效率总飞行距离/时间总和越小能耗越低系统效率越高。各无人机飞行距离/时间查看最大值、最小值和方差。方差越小负载越均衡。续航利用率单机飞行时间 / C_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赛题其价值在于它精准地捕捉了多无人机协同监视任务的核心数学模型。从区域离散化、任务分配到路径规划再到周期覆盖评估每一步都对应着实际工程中的关键环节。解决这类问题没有唯一的“标准答案”比拼的是对问题本质的理解深度、建模的巧思以及算法实现的稳健性。今天虽然我们有了更强大的计算工具和更成熟的算法库但这条从问题分析到模型构建再到求解与评估的系统化思维路径依然是应对复杂系统规划类问题的利器。在实际项目中我们往往还需要考虑更多因素如通信链路、避障、动态威胁等但所有这些高级功能都是建立在本文所探讨的这份最基础的“例行方案”骨架之上的。