第 4 章 市政分工：协作与协调

第 4 章 · 市政分工：协作与协调

章节摘要：会说话、会谈判、会守规之后，镇民要开始真正一起干活。本章进市政厅，处理协作的三大工程问题：任务怎么分（任务分配与调度，从中心化指派到市场化竞价）、心怎么齐（联合意图与共享计划，团队协作模型）、力怎么合（分布式问题求解与分布式约束优化 DCOP）。读完你将掌握分工机制的选型逻辑，并能写出贪心分配、联合承诺与分布式搜索的最小实现。

学习目标

阅读完本章，你应当能够：

1. 对比任务分配的四类机制（中心化指派、贪心分配、市场化竞价、组合拍卖），说出各自的通信与计算代价；
2. 解释联合意图理论为何要求"共同目标的承诺要互知"，说出Joint Intentions 与SharedPlans 两大流派的差异；
3. 描述团队协作中角色分配、 mutual belief 建立与任务重分配的典型流程；
4. 把一个调度问题写成分布式约束优化（DCOP）模型：变量、域、约束、成本；
5. 实现并比较同步分支定界与 DSA 这类局部搜索的求解质量与消息开销。

核心概念速览

一句金句：协作的三个台阶：分工解决"谁干"，联合意图解决"为啥一起干"，分布式求解解决"怎么一起干得好"。

子章节导航

4.1 派活的艺术：任务分配与调度

任务分配是多智能体系统的"人事处"。本节从中心化指派讲起，过贪心分配的贪心陷阱、市场化竞价的动态优势，到组合拍卖打包授标的精打细算；用代码对照匈牙利算法式的最优与贪心的近似，再跑一个负载敏感的市场化分配实验。

4.2 联合意图与团队协作模型

一群镇民各干各的不叫团队。本节讲联合意图理论：共同目标上的互知承诺（我知道你知道我们都答应过）、承诺的维持与终止条件；对照SharedPlans 的部分共享计划思想；落到团队协作模型的角色分配、相互信念与重组流程。代码实现一个会"打招呼再行动"的联合承诺状态机。

4.3 分布式问题求解与 DCOP

协作的收官是群策群力：分布式问题求解（DPS）的老三样——任务分解、子问题分配、结果共享，以及它的现代形态 DCOP（分布式约束优化）：变量各持一镇民，约束即利益牵连。本节用会议排期做例子建模 DCOP，实现同步分支定界与 DSA 局部搜索并对比。

子章节之间的逻辑关系

三节按"先分活、再同心、后合力"推进：4.1 是静态分工（假设任务独立），4.2 把有依赖的执行绑成团队（任务间有承诺耦合），4.3 处理最深度的耦合——任务本身不可分家，只能在约束网上分布式搜索。难度递增，通信开销也递增；工程上能停留在浅层就别下潜。

4.1 分工（任务独立） ──► 4.2 同心（承诺耦合） ──► 4.3 合力（约束耦合）
      │                      │                        │
      └─ 市场化竞价          └─ 互知与重分配          └─ DCOP 两代求解
​

本章可考核知识点清单

• 能写出任务分配问题的形式化（镇民集、任务集、代价矩阵、目标函数）并说出它与指派问题的关系；
• 能解释贪心分配的最坏情况与市场机制如何通过价格信号自发纠偏；
• 能默写联合意图的两条核心约束（共同承诺的互知、终止条件的通知义务）；
• 能说明相互信念"我们知道我们知道"与一阶知识的差别及建造成本；
• 能把给定的资源冲突场景翻译成 DCOP 四元组（变量、域、约束、成本）；
• 能比较完备算法与局部搜索在解质量、消息数、收敛性上的取舍。

前置知识与后续延伸

• 前置知识：第 3 章合同网（市场竞价的协议底座）；基本的图论词汇（节点、边、着色）。
• 后续延伸：本章的分配与调度是第 9 章交通信号与仓库机器人应用的算法心脏；DCOP 的约束网在第 5 章资源竞争里换个名字叫"冲突图"；团队协作的承诺问题在 第 7 章学堂里会以"信用分配"的新面目重现。