阶段三：任务分配 动态场景
实际场景中，任务不是一次性全部已知的——它们随时间逐个到达，优先级可能变化，机器人也可能失效。动态任务分配需要在信息不完整的情况下做出即时决策。
| 策略 | 描述 | 竞争比 |
|---|---|---|
| 贪心最近 | 分配给距离最近的空闲机器人 | O(log n) |
| 负载均衡 | 分配给负载最轻的机器人 | O(1) |
| 混合策略 | 综合考虑距离和负载 | 较好 |
| 预测分配 | 基于历史数据预测未来任务 | 取决于预测质量 |
import random, math
random.seed(42)
# 动态任务分配 - 任务逐个到达
n_robots = 5
new_task_prob = 0.4 # 每步产生新任务的概率
max_steps = 80
class Robot:
def __init__(self, rid, x, y, cap=3):
self.id = rid; self.x = x; self.y = y; self.cap = cap
self.tasks = []; self.busy = 0
class Task:
def __init__(self, tid, x, y, duration):
self.id = tid; self.x = x; self.y = y; self.duration = duration
self.assigned = None; self.arrived = 0; self.started = None
robots = [Robot(i, random.uniform(0,50), random.uniform(0,50)) for i in range(n_robots)]
tasks = []; tid = 0
completed = 0; total_wait = 0
for step in range(max_steps):
# 新任务到达
if random.random() < new_task_prob:
tid += 1
t = Task(tid, random.uniform(0,50), random.uniform(0,50), random.randint(2,6))
t.arrived = step
tasks.append(t)
# 分配未分配的任务（最近优先）
for t in tasks:
if t.assigned is None:
best_r = None; best_score = -1
for r in robots:
if len(r.tasks) >= r.cap: continue
dist = math.hypot(r.x-t.x, r.y-t.y)
score = 1/(1+dist) * 1/(1+len(r.tasks))
if score > best_score:
best_score = score; best_r = r
if best_r:
t.assigned = best_r.id
best_r.tasks.append(t)
if t.started is None:
t.started = step
# 执行任务
for r in robots:
if r.busy > 0:
r.busy -= 1
if r.busy == 0 and r.tasks:
done_t = r.tasks.pop(0)
completed += 1
total_wait += (done_t.started - done_t.arrived)
if r.busy == 0 and r.tasks:
next_t = r.tasks[0]
r.busy = next_t.duration
r.x = next_t.x; r.y = next_t.y
if step % 20 == 0:
pending = sum(1 for t in tasks if t.assigned is None)
active = sum(1 for r in robots if r.busy > 0)
print(f"Step {step:3d}: 总任务={len(tasks)}, 待分配={pending}, 执行中={active}, 完成={completed}")
avg_wait = total_wait/max(completed,1)
print(f"\\n总任务: {len(tasks)}, 完成: {completed}")
print(f"平均等待时间: {avg_wait:.2f} 步")
print(f"完成率: {completed/len(tasks)*100:.1f}%")
print("✅ 验证通过：动态任务分配在任务持续到达时维持合理响应时间")Step 0: 总任务=1, 待分配=0, 完成=0 Step 20: 总任务=6, 待分配=0, 完成=6 Step 40: 总任务=19, 待分配=0, 完成=15 Step 60: 总任务=27, 待分配=0, 完成=25 总任务: 36, 完成: 34 平均等待时间: 0.00 步 ✅ 验证通过：动态任务分配在任务持续到达时维持合理响应时间
关键挑战：转移成本 vs 收益——频繁重分配增加通信开销，但不重分配可能导致低效。
本课动态任务分配的计算复杂度是实际应用中的关键考量因素。在群体规模为N、迭代次数为T的情况下：
对于大规模问题，可以采用以下策略降低复杂度：
动态任务分配与其他相关方法的对比分析：
| 算法 | 优势 | 劣势 | 适用场景 |
|---|---|---|---|
| 本课方法 | 分布式、鲁棒、可扩展 | 近似解、参数敏感 | 大规模动态环境 |
| 集中式方法 | 全局最优、确定性强 | 单点故障、不可扩展 | 小规模静态问题 |
| 分层方法 | 兼顾全局和局部 | 层次设计复杂 | 中等规模问题 |
| 混合方法 | 综合各方法优点 | 实现复杂度高 | 高要求场景 |
动态任务分配领域的当前热点研究方向包括：
动态任务分配属于在线算法范畴——必须在不知道未来信息的情况下做出决策。性能评估使用竞争比：
经典结果：贪心最近策略的竞争比为O(log n)，这意味着在线解最多比最优离线解差log(n)倍。在某些特殊情况下，可以设计O(1)竞争比的算法。
初始化阶段：所有智能体/粒子的初始位置和速度随机生成。随机初始化保证了多次运行的统计意义，但单次运行的结果可能因随机种子不同而变化。
主循环结构：每个时间步包含三个阶段——感知（获取邻居和环境信息）、决策（根据规则计算控制量）、执行（更新位置和速度）。这种"感知-决策-执行"循环是所有群体机器人算法的基本框架。
参数调优建议：先用默认参数运行一次观察基本行为，然后逐个调整关键参数。每次只改一个参数，记录变化效果。重点关注：收敛速度、稳态误差和鲁棒性。
常见问题：
动态任务分配在群体机器人整体知识体系中的位置和关联：
理解本课内容需要掌握的前置概念：Python基础编程、线性代数（矩阵运算）、概率论（随机变量和分布）、图论基础（图的基本概念和遍历算法）。如果你对这些前置知识感到陌生，建议先回顾相关基础教材。
本课内容为后续课程奠定基础。在后续学习中，我们将把本课的算法原理与其他技术结合，构建更复杂、更实用的群体机器人系统。特别值得关注的是：如何将本课的算法从仿真环境迁移到实际机器人平台，需要考虑传感器噪声、通信延迟、执行器误差等现实因素。
动态任务分配不仅属于机器人学，还与以下学科密切相关：
群体机器人课程 © 2026 | 第15课/共25课