阶段三：任务分配 分配基础
任务分配（Task Allocation）是群体机器人中的核心问题：给定一组机器人和一组任务，如何将任务分配给机器人，使得某个全局目标（如总代价最小、总收益最大）最优化？
匈牙利算法（Kuhn-Munkres算法）是求解指派问题的经典多项式时间算法，时间复杂度 O(n³)。
import random, math
from itertools import permutations
random.seed(42)
# 任务分配问题 - 匈牙利算法
n = 5
costs = [[random.randint(1, 20) for _ in range(n)] for _ in range(n)]
print("代价矩阵:")
for row in costs:
print(" " + " ".join(f"{x:3d}" for x in row))
# 匈牙利算法实现
def hungarian(cost):
n = len(cost)
u = [0]*(n+1); v = [0]*(n+1); p = [0]*(n+1); way = [0]*(n+1)
for i in range(1, n+1):
p[0] = i; j0 = 0
minv = [float('inf')]*(n+1); used = [False]*(n+1)
while True:
used[j0] = True; i0 = p[j0]; delta = float('inf'); j1 = 0
for j in range(1, n+1):
if not used[j]:
cur = cost[i0-1][j-1] - u[i0] - v[j]
if cur < minv[j]: minv[j] = cur; way[j] = j0
if minv[j] < delta: delta = minv[j]; j1 = j
for j in range(n+1):
if used[j]: u[p[j]] += delta; v[j] -= delta
else: minv[j] -= delta
j0 = j1
if p[j0] == 0: break
while j0:
p[j0] = p[way[j0]]; j0 = way[j0]
assignment = [0]*n
for j in range(1, n+1):
if p[j] > 0: assignment[p[j]-1] = j-1
total = sum(cost[i][assignment[i]] for i in range(n))
return assignment, total
assignment, total = hungarian(costs)
print(f"\\n最优分配: " + ", ".join(f"机器人{i}→任务{assignment[i]}" for i in range(n)))
print(f"总代价: {total}")
# 暴力验证（小规模）
brute_min = float('inf')
for perm in permutations(range(n)):
c = sum(costs[i][perm[i]] for i in range(n))
if c < brute_min: brute_min = c
print(f"暴力搜索最优: {brute_min}")
print(f"验证: {'正确' if total == brute_min else '错误'}")
print("✅ 验证通过：匈牙利算法找到全局最优任务分配")代价矩阵:
4 1 9 8 8
5 4 18 3 19
14 2 1 3 7
8 17 20 1 18
7 18 14 8 15
最优分配: 机器人0→任务4, 机器人1→任务1, 机器人2→任务2, 机器人3→任务3, 机器人4→任务0
总代价: 21
暴力搜索最优: 21
验证: 正确
✅ 验证通过：匈牙利算法找到全局最优任务分配
贪心策略（每次选最小代价的分配）复杂度 O(n²) 但不保证最优；匈牙利算法 O(n³) 保证最优。在 n 较小时差异不大，但 n>10 时贪心解可能比最优解差 20-50%。
本课任务分配问题的计算复杂度是实际应用中的关键考量因素。在群体规模为N、迭代次数为T的情况下：
对于大规模问题，可以采用以下策略降低复杂度：
任务分配问题与其他相关方法的对比分析：
| 算法 | 优势 | 劣势 | 适用场景 |
|---|---|---|---|
| 本课方法 | 分布式、鲁棒、可扩展 | 近似解、参数敏感 | 大规模动态环境 |
| 集中式方法 | 全局最优、确定性强 | 单点故障、不可扩展 | 小规模静态问题 |
| 分层方法 | 兼顾全局和局部 | 层次设计复杂 | 中等规模问题 |
| 混合方法 | 综合各方法优点 | 实现复杂度高 | 高要求场景 |
任务分配问题领域的当前热点研究方向包括：
匈牙利算法的行/列减法操作有清晰的几何含义：在代价矩阵的"地形"上，减去行最小值相当于将该行的"海平面"降低到最低点为零，减去列最小值类似。零元素的位置就是"免费"的分配机会。
用最少的线覆盖所有零元素时：
每次调整至少增加一个可分配的零元素，因此算法在O(n)次调整内终止。
初始化阶段：所有智能体/粒子的初始位置和速度随机生成。随机初始化保证了多次运行的统计意义，但单次运行的结果可能因随机种子不同而变化。
主循环结构：每个时间步包含三个阶段——感知（获取邻居和环境信息）、决策（根据规则计算控制量）、执行（更新位置和速度）。这种"感知-决策-执行"循环是所有群体机器人算法的基本框架。
参数调优建议：先用默认参数运行一次观察基本行为，然后逐个调整关键参数。每次只改一个参数，记录变化效果。重点关注：收敛速度、稳态误差和鲁棒性。
常见问题：
任务分配问题在群体机器人整体知识体系中的位置和关联：
理解本课内容需要掌握的前置概念：Python基础编程、线性代数（矩阵运算）、概率论（随机变量和分布）、图论基础（图的基本概念和遍历算法）。如果你对这些前置知识感到陌生，建议先回顾相关基础教材。
本课内容为后续课程奠定基础。在后续学习中，我们将把本课的算法原理与其他技术结合，构建更复杂、更实用的群体机器人系统。特别值得关注的是：如何将本课的算法从仿真环境迁移到实际机器人平台，需要考虑传感器噪声、通信延迟、执行器误差等现实因素。
任务分配问题不仅属于机器人学，还与以下学科密切相关：
群体机器人课程 © 2026 | 第11课/共25课