📚 课程目录第4章协同任务分配问题建模

4. 协同任务分配问题建模

多无人系统协同任务分配的核心，是把“谁去做什么、什么时候做、以什么代价做”转化为一个可计算、可求解的数学问题。与单平台任务规划不同，协同分配必须同时考虑任务之间的时序依赖、平台能力差异、资源消耗、通信拓扑以及冲突消解。本节从建模五要素出发，给出可直接落地的形式化描述，并说明如何把工程语义映射为数学规划形式。

一、任务定义：从工程语义到可计算对象

任务不是一句自然语言指令，而是一个带属性的可计算对象。一个任务 t_i 通常定义为五元组：

t_i = (id, type, location, duration, dependency)
type ∈ {侦察, 打击, 通信中继, 运输, 评估}
location = (x, y, z) 或目标区域编号
duration = 执行该任务所需时间窗
dependency = 前置任务集合 Pred(t_i)

其中 dependency 是协同分配区别于单平台规划的关键。例如“打击”任务必须等待“侦察”任务完成并回传目标确认信息，因此 Pred(打击) = {侦察}。若忽略依赖关系，求解器可能给出物理上不可执行的分配方案。任务集合记为 T = {t₁, t₂, …, t_n}，每个任务可被一个或多个平台执行，也可要求多平台同时执行（如协同打击需要两架无人机同时到达）。

二、无人系统集合：能力与状态建模

无人系统集合 U = {u₁, u₂, …, u_m}，每个平台 u_j 需要描述其能力、位置、资源和状态：

u_j = (pos, speed, capability, energy, payload, comm_range)
capability ⊆ {侦察, 打击, 中继, 运输}
energy ∈ [0, 100]%  剩余能量
payload = 当前挂载类型与数量

能力集合决定了任务与平台之间的可行匹配关系。例如只有 capability 包含“打击”的平台才能被分配到打击任务。位置和速度用于计算航程时间与到达时间窗，能量和载荷用于约束可执行任务数量。实际建模中，常把平台能力写成 0-1 矩阵 A_ij：若平台 j 能执行任务 i，则 A_ij=1，否则为 0。该矩阵是后续约束和目标函数的基础。

三、约束条件：可行解必须满足的硬边界

协同任务分配的约束可分为四类，缺一不可：

能力约束：任务 i 只能分配给满足 A_ij=1 的平台 j。
时序约束：若任务 i 依赖任务 k，则 t_i^start ≥ t_k^end，且执行平台需满足转场时间。
资源约束：平台能量、载荷、通信带宽不能超过上限；例如总航程 d_j ≤ d_max，剩余能量 e_j ≥ e_min。
协同约束：某些任务要求多平台同时到达，即 |t_i^arrive(j) − t_i^arrive(k)| ≤ ε，ε 为允许时间偏差。

这些约束共同定义了可行解空间。工程上，约束越紧，可行解越少，求解难度越大。因此建模时需区分硬约束（必须满足）和软约束（尽量满足，可转化为惩罚项）。

四、目标函数：把“好方案”量化

目标函数决定优化方向。常见目标包括：总任务完成时间最短、总航程最小、总能耗最低、任务覆盖率最高、平台负载最均衡。多目标情况下，通常采用加权求和：

min J = w1·Σ travel_time + w2·Σ energy_cost
        + w3·max_load_imbalance − w4·coverage
s.t. 硬约束全部满足

权重 w₁…w₄ 需根据任务场景标定。例如侦察任务优先覆盖率和时间，打击任务优先到达时间和协同精度。目标函数中的每一项都必须可计算，且量纲统一或归一化，否则加权求和会失去物理意义。

五、数学规划形式：从语义到标准模型

最常用的形式是混合整数线性规划（MILP）。定义决策变量 x_ij ∈ {0,1}，表示任务 i 是否由平台 j 执行；t_i 为任务开始时间。则模型可写为：

min  Σ_i Σ_j c_ij · x_ij + Σ_i t_i
s.t. Σ_j x_ij = 1,        ∀i（每个任务至少执行一次）
     Σ_i x_ij ≤ L_j,      ∀j（平台任务数上限）
     t_i ≥ t_k + τ_ki,    ∀(k,i) ∈ 依赖关系
     x_ij = 0,            若 A_ij = 0
     x_ij ∈ {0,1}, t_i ≥ 0

该模型可直接交给求解器（如 Gurobi、CPLEX、OR-Tools）求解。对于大规模场景，可分解为“任务分组—平台分配—时序优化”三层，或采用拍卖算法、遗传算法等启发式方法快速获得近优解。

六、建模检查清单

完成建模后，建议逐项核对以下内容，避免模型不可解或解无意义：

检查项	判断标准	常见问题
任务依赖是否完整	每个依赖关系都有对应时序约束	遗漏前置任务导致时序冲突
能力矩阵是否准确	A_ij 与平台实际载荷一致	把侦察平台分配给打击任务
资源约束是否可满足	存在至少一个可行解	能量上限过紧导致无解
目标权重是否归一化	各项量纲统一或无量纲化	航时与能耗直接相加
协同时间偏差 ε 是否合理	与平台速度、通信延迟匹配	ε 过小导致无可行协同方案

建模提示：先保证可行解存在，再优化目标函数。若求解器返回不可行，优先检查能力矩阵和时序约束，而不是调整目标权重。

综上，协同任务分配建模的本质是把任务、平台、约束、目标四类信息统一到决策变量 x_ij 和 t_i 上，形成 MILP 或等价形式。模型一旦建立，后续的求解算法选择、分布式拍卖机制设计、在线重分配策略，都围绕该模型展开。建模质量直接决定协同分配结果是否可执行、是否高效。