多 Agent 图拓扑与执行策略

多 Agent 图拓扑与执行策略

学习目标

• 理解 ChatDev 的拓扑分析流程：如何自动识别图结构并选择执行策略
• 掌握 Tarjan 强连通分量算法在环检测中的应用
• 了解三种执行策略的适用场景和切换机制
• 能够根据任务需求选择合适的图拓扑

前置知识

本章涉及多 Agent 编排的通用原理，建议先阅读：

• 子图组合模式

下文聚焦 ChatDev 的具体拓扑分析与策略选择实现。

---

项目实践

拓扑分析流程

ChatDev 的 TopologyBuilder 在图构建阶段自动分析拓扑并选择策略：

关键源码位于 workflow/runtime/execution_strategy.py，定义了三种策略类：

DAGExecutor         → 无环图的层间屏障执行
CycleExecutor       → 含环图的迭代控制
ParallelExecutor    → 多数投票模式的并行池

DAG 策略：拓扑分层

当图无环时，采用 Kahn 算法进行拓扑分层：

执行顺序：

1. 层 0：执行 START（无依赖，立即完成）
2. 层 1：Agent A 和 Agent B 并行执行（彼此无依赖）
3. 层 2：等待层 1 完成后，执行 Agent C

关键点：层内并行、层间串行。这保证了数据流的正确性。

Cycle 策略：Tarjan 环检测

当图包含环时，ChatDev 使用 Tarjan 的强连通分量（SCC）算法检测环：

workflow/cycle_manager.py

class CycleDetector:
    """使用 Tarjan 算法检测图中的所有环"""

    def detect_cycles(self, nodes: Dict[str, Node]) -> List[Set[str]]:
        # 对每个未访问节点执行 strong_connect
        for node_id in nodes:
            if node_id not in self.index:
                self._strong_connect(node_id, nodes)
        return self.cycles

每个检测到的环被封装为 CycleInfo：

CycleInfo:
  - cycle_id: 环的唯一标识
  - nodes: 环中包含的节点集合
  - exit_edges: 可以退出环的边（带条件判断）
  - iteration_count: 当前迭代次数
  - max_iterations: 安全上限（默认 100）

执行流程：

ChatDev 的环退出机制：

• 边的 condition 字段定义退出条件（如关键词匹配）
• 当条件满足时，CycleExecutor 选择退出边继续执行
• 当迭代次数达到 max_iterations 时强制退出

MajorityVote 策略：并行投票

当 is_majority_voting: true 时（此时图没有边定义）：

graph:
  id: majority_vote_example
  is_majority_voting: true
  nodes:
    - id: Agent_A
      type: agent
      config: { ... }
    - id: Agent_B
      type: agent
      config: { ... }
    - id: Agent_C
      type: agent
      config: { ... }

所有 Agent 并行接收相同的初始消息，结果通过 Counter.most_common(1) 聚合：

Agent A → "结果 X"
Agent B → "结果 X"
Agent C → "结果 Y"
         → Counter: X=2, Y=1
         → 多数结果: "结果 X"

问题与规避

问题	表现	规避策略
环无退出条件	迭代到 max_iterations 强制退出	确保至少一条边带有 condition
DAG 中存在隐式环	被误判为 Cycle 模式	用 make validate-yamls 检查
多数投票平票	most_common(1) 返回任意一个	设计 Agent 时避免确定性冲突
DAG 层内 Agent 失败	层间屏障阻止后续执行	配置节点 retry 策略

设计取舍

Tarjan vs Kahn 算法

维度	Tarjan (SCC)	Kahn (入度)
检测能力	所有强连通分量	仅判断是否为 DAG
复杂度	O(V + E)	O(V + E)
输出	具体的环集合	拓扑排序或检测到环
ChatDev 的选择	✅ 使用	❌ 仅用于 DAG 分层

ChatDev 使用 Tarjan 而非 Kahn 来检测环的原因：Tarjan 不仅能判断是否有环，还能输出具体的环成员和大小，为后续的 CycleExecutor 提供完整信息。

策略模式 vs 统一执行器

ChatDev 选择策略模式（三个独立的策略类）而非一个统一的执行器：

• 优势：每种策略的优化空间大，代码职责清晰
• 代价：增加 if-elif 分支判断

参考来源

• ChatDev 执行策略源码
• ChatDev 环检测器源码