Monte-Carlo树搜索在可扩展联盟形成中的应用研究

作者及机构
本研究由University of Science and Technology of China（中国科学技术大学）的Feng Wu与University of Southampton（南安普顿大学）的Sarvapali D. Ramchurn合作完成，发表于 *Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence (IJCAI-20)*。

研究背景

联盟形成（coalition formation）是多智能体系统（multi-agent systems, MAS）中的重要研究方向，其核心目标是通过智能体之间的协作优化群体社会福利。在联盟形成过程中，联盟结构生成（Coalition Structure Generation, CSG）是关键挑战之一，其任务是将一组智能体划分为互不重叠且完备的联盟（coalition），使得整体社会福利最大化。然而，CSG问题已被证明是NP完全问题，计算复杂度随智能体数量呈指数增长，传统精确算法（如动态规划）仅适用于小规模问题（如少于40个智能体），而近似方法（如GRASP、C-Link）虽能快速返回解，但无法保证解的质量。

为了平衡解的最优性和可扩展性，本研究提出了一种基于Monte-Carlo树搜索（Monte-Carlo Tree Search, MCTS）的新算法CSG-UCT。该算法通过采样联盟结构图（coalition structure graph）并逐步构建搜索树，结合探索-利用权衡策略，既可在大规模问题中高效运行，又能提供最优性保障。

研究方法

1. 算法框架

CSG-UCT算法的核心流程分为四个步骤：

(1) 选择（Selection）

从搜索树的根节点（初始为单智能体联盟结构，如{{a1}, {a2}, ..., {an}}）出发，基于UCB1启发式（Upper Confidence Bound 1）选择分支路径。UCB1的公式为：
[ \text{UCB1}(cs’) = \bar{v}(cs’) + c \sqrt{\frac{\log n(cs)}{n(cs’)}} ]
其中，(\bar{v}(cs’))为子树当前最优值，(n(cs))为节点访问次数，(c)为探索权重参数。该策略平衡了对高价值节点的利用（exploitation）和对低访问节点的探索（exploration）。

(2) 扩展（Expansion）

当选择的子节点未存在于搜索树时，将其加入树中。例如，从{{a1}, {a2}, {a3}, {a4}}扩展子节点{{a1, a2}, {a3}, {a4}}（通过合并{a1}和{a2}）。

(3) 模拟（Simulation）

对新节点进行rollout搜索：从该节点出发，贪心地合并联盟直至形成大联盟（grand coalition）。合并策略采用局部最优选择，每次合并使联盟结构值增量最大化的两个联盟。例如：
[ c_1, c2 = \arg\max{c’_1, c’_2 \in cs} [v(cs’) - v(cs)] ]

(4) 反向传播（Backpropagation）

将模拟得到的值从叶节点回溯更新至根节点，更新路径上各节点的最优值：
[ \bar{v}(cs_l) = \max {\bar{v}(csl), \bar{v}(cs{l+1})} ]

2. 理论分析

• 完备性：在足够时间下，CSG-UCT能遍历所有可能的联盟结构，确保找到最优解（定理1）。
  
• Anytime性质：算法可随时停止并返回当前最优解，且随迭代次数增加，解质量单调提升（定理2）。
  

3. 实验设计

实验对比CSG-UCT与主流近似方法（GRASP、C-Link），涵盖六类经典基准问题和实际灾难响应场景：
- 基准问题：包括均匀分布（uniform）、正态分布（normal）、NDCS等不同效用函数类型。
- 灾难响应案例：模拟放射性污染区域的应急团队协作，需快速组建包含医疗、消防等角色的联盟。

性能指标包括：
- 最优比率（optimal ratio）：当前解与最优解的比值（最优解通过CPLEX计算，限于≤20智能体）。
- 基线增益（baseline gain）：相较于单智能体联盟的改进幅度（用于大规模问题）。

研究结果

1. 算法性能

• 基准问题：在六类测试中，CSG-UCT（k=10^5次迭代）均优于GRASP和C-Link，最优比率接近1.0（图2a-f）。例如，在NDCS问题上，CSG-UCT仅需≤68次迭代即可找到12智能体的最优解（表1）。
  
• 灾难响应案例：CSG-UCT在100智能体规模下仍保持高效，基线增益显著高于对比方法（图2g）。
  

2. Anytime特性验证

通过控制迭代次数（k=10^2至10^3）证明：随着时间增加，解质量稳定提升，且运行时间线性增长（图2h），符合实际应用需求。

研究价值

1. 科学贡献

• 首次将MCTS应用于CSG问题，提出CSG-UCT算法，填补了大规模联盟形成领域的技术空白。
  
• 理论证明了算法的完备性和Anytime性质，为后续研究提供理论基础。
  

2. 应用价值

• 灾难响应：支持数百名应急人员快速组队，优化资源分配效率。
  
• 社交拼车等场景：可扩展至其他需动态协作的领域（如共享经济）。
  

研究亮点

1. 创新性方法：结合MCTS的采样能力和UCT的探索-利用平衡，解决了传统方法在规模与质量间的矛盾。
   
2. 实证优势：在多种效用分布和实际场景中均表现出优越性，验证了算法的普适性。
   
3. 开源实现：算法采用Java开发，便于后续扩展（如GPU加速）。
   

未来方向

作者计划进一步优化算法以支持超大规模问题（如>500智能体），并探索在实际应急系统中的应用验证。

注：本文涉及的术语首次出现时标注英文原名，如“联盟结构生成（Coalition Structure Generation, CSG）”。研究图表参见原论文图2及表1。