《AI Agent 技术原理与架构·决策、记忆与学习》4.1 任务分解:DAG、偏序与依赖

把任务拆成子任务不难,难的是把“谁依赖谁”说清楚。本节用有向无环图建模任务分解:依赖必须构成 DAG,才能做拓扑排序与关键路径计算;有环说明计划自相矛盾。实验给出七节点修复计划的拓扑序、最早开始/完成时间与关键路径,并解释为什么“检测到环”比“猜一个顺序”更安全。

以下数字为教学示例,不构成对任何真实系统或供应商的承诺。

任务分解(task decomposition)是 Agent 规划的第一步,也是最常被低估的一步。让模型"把大任务拆成小任务"很容易,结果却往往是"拆出了一个列表",而不是"拆出了一张图"。列表只回答"有哪些事",图才能回答"哪件先做、哪件等谁、哪条路决定总工期"。

这一节把任务分解建模成有向无环图(DAG):节点是子任务,边是依赖关系。建模之后,拓扑排序、关键路径这些成熟算法就可以直接给出可验证的计划;反过来,依赖声明里的错误(重复、未知依赖、环)也会在规划阶段就被抓住,而不是执行到一半才发现。

为什么必须是 DAG

依赖关系必须是无环的。环意味着计划自相矛盾:A 依赖 B,B 又依赖 A,没有一个可以开始的节点。

环有两种来源,值得区分:

  1. 声明错误:模型分解时把依赖写成了环,这是可修复的规划错误;
  2. 真实循环:任务在业务上确实需要来回,这通常说明分解错了——真正依赖的应该是更细粒度的子任务,或者需要重设计。

无论哪种,正确的处理都是在规划阶段拒绝并报告,而不是给它随便排一个顺序。实验里用"检测到环"而不是"排序成功"来收尾,正是这个意图:有环时唯一安全的行为是停止并让计划者重写。

拓扑排序与最早时间

有了 DAG,就可以做两件对 Agent 有意义的事:

  1. 拓扑排序:给出一个满足所有依赖的执行顺序。同一层可并行的节点按声明顺序固定,保证输出确定、可回归。
  2. 最早调度:对每个任务算"最早开始时间"和"最早完成时间"。最早开始等于其所有依赖的最晚完成,这决定了每个子任务能等多久、最迟何时必须开始。

最早时间不只是调度工具,它还是延误检测的基准:实际运行里某个子任务超过了最早完成时间,你就可以量化"这次延误推迟了总工期多久",而不是模糊地说"变慢了"。

关键路径:哪条路决定总工期

总工期不是所有任务工时之和,而是关键路径的长度:那条最长的依赖链。非关键路径上的任务有空闲时间,拖几天可能不影响总工期;关键路径上的任务晚一天,总工期就晚一天。

关键路径对 Agent 有三个直接用途:

  1. 资源优先:慢的模型、多的重试,优先投在关键路径上;
  2. 风险排序:关键路径上的任务失败影响最大,需要更强的验证器;
  3. 预算分配:非关键路径可以压缩或降级,不影响整体进度。

最小实验:七节点修复计划

下面的实验给出一个七节点的支付回调修复计划,打印它的拓扑序(最早调度)、关键路径与总工期,最后用两节点环演示拒绝行为。

# file: agp_lab/task_dag.py | write
# tier: 3
# verify: python3 -m unittest tests.test_task_dag
"""任务分解为 DAG:偏序、拓扑排序与关键路径。

把任务拆成子任务不难,难的是把“谁依赖谁”说清楚。依赖关系必须
构成有向无环图:有环说明计划自相矛盾,拓扑排序会失败;无环时才
能计算每个子任务的最早开始时间,以及决定总工期的关键路径。

实验给出一个七节点的修复计划,打印它的拓扑序、最早开始/完成时间
和关键路径,再用一个两节点环说明为什么“检测到环”比“排序随便给
一个顺序”更安全。
"""
from __future__ import annotations

from dataclasses import dataclass


class PlanError(ValueError):
    """依赖声明本身不合法。"""


class CycleError(PlanError):
    """依赖图存在环;remaining 是未能排序的节点。"""

    def __init__(self, remaining: tuple[str, ...]) -> None:
        super().__init__("依赖图存在环: " + ", ".join(remaining))
        self.remaining = remaining


@dataclass(frozen=True)
class Task:
    ident: str
    duration: int
    deps: tuple[str, ...] = ()


@dataclass(frozen=True)
class Slot:
    ident: str
    deps: tuple[str, ...]
    duration: int
    start: int
    finish: int


def validate(tasks: list[Task]) -> None:
    """检查重复编号、未知依赖、自依赖与非法工期。"""
    if not tasks:
        raise PlanError("计划为空")
    known: dict[str, Task] = {}
    for task in tasks:
        if not task.ident:
            raise PlanError("任务编号不能为空")
        if task.ident in known:
            raise PlanError(f"重复任务编号: {task.ident}")
        if task.duration < 0:
            raise PlanError(f"{task.ident}: 工期不能为负")
        known[task.ident] = task
    for task in tasks:
        for dep in task.deps:
            if dep == task.ident:
                raise PlanError(f"{task.ident}: 不能依赖自己")
            if dep not in known:
                raise PlanError(f"{task.ident}: 未知依赖 {dep}")


def topological_order(tasks: list[Task]) -> list[str]:
    """Kahn 算法;同层顺序按声明顺序固定,保证输出确定。"""
    validate(tasks)
    order = [task.ident for task in tasks]
    indegree = {task.ident: 0 for task in tasks}
    children: dict[str, list[str]] = {task.ident: [] for task in tasks}
    for task in tasks:
        for dep in task.deps:
            indegree[task.ident] += 1
            children[dep].append(task.ident)
    ready = [ident for ident in order if indegree[ident] == 0]
    result: list[str] = []
    while ready:
        current = ready.pop(0)
        result.append(current)
        for child in children[current]:
            indegree[child] -= 1
            if indegree[child] == 0:
                ready.append(child)
    if len(result) != len(tasks):
        remaining = tuple(ident for ident in order if ident not in result)
        raise CycleError(remaining)
    return result


def earliest_schedule(tasks: list[Task]) -> list[Slot]:
    """按拓扑序计算每个任务的最早开始与最早完成时间。"""
    by_id = {task.ident: task for task in tasks}
    finish: dict[str, int] = {}
    slots: list[Slot] = []
    for ident in topological_order(tasks):
        task = by_id[ident]
        start = max((finish[dep] for dep in task.deps), default=0)
        stop = start + task.duration
        finish[ident] = stop
        slots.append(
            Slot(ident, task.deps, task.duration, start, stop)
        )
    return slots


def critical_path(tasks: list[Task]) -> tuple[int, tuple[str, ...]]:
    """返回总工期与一条关键路径;并列时取拓扑序更早的终点。"""
    by_id = {task.ident: task for task in tasks}
    order = topological_order(tasks)
    start: dict[str, int] = {}
    finish: dict[str, int] = {}
    parent: dict[str, str | None] = {}
    for ident in order:
        task = by_id[ident]
        best_dep: str | None = None
        best_finish = 0
        for dep in task.deps:
            if best_dep is None or finish[dep] > best_finish:
                best_finish = finish[dep]
                best_dep = dep
        start[ident] = best_finish
        finish[ident] = best_finish + task.duration
        parent[ident] = best_dep
    end = order[-1]
    for ident in order:
        if finish[ident] >= finish[end]:
            end = ident
    path: list[str] = []
    cursor: str | None = end
    while cursor is not None:
        path.append(cursor)
        cursor = parent[cursor]
    path.reverse()
    return finish[end], tuple(path)


def sample_plan() -> list[Task]:
    """一个七节点的支付回调修复计划。"""
    return [
        Task("repro", 2),
        Task("locate", 3, ("repro",)),
        Task("fix", 5, ("locate",)),
        Task("test", 4, ("fix",)),
        Task("data", 6, ("locate",)),
        Task("deploy", 2, ("test", "data")),
        Task("verify", 1, ("deploy",)),
    ]


def cyclic_plan() -> list[Task]:
    """一个两节点环,用于演示拒绝而不是猜测。"""
    return [
        Task("a", 1, ("b",)),
        Task("b", 1, ("a",)),
    ]


if __name__ == "__main__":
    tasks = sample_plan()
    print(f"{'序号':<4}{'任务':<8}{'依赖':<14}{'工期':>4}{'最早开始':>8}{'最早完成':>8}")
    for index, slot in enumerate(earliest_schedule(tasks), start=1):
        deps = ",".join(slot.deps) or "-"
        print(
            f"{index:<4}{slot.ident:<8}{deps:<14}{slot.duration:>4}"
            f"{slot.start:>8}{slot.finish:>8}"
        )
    length, path = critical_path(tasks)
    print()
    print("关键路径: " + " -> ".join(path))
    print(f"总工期: {length}")
    try:
        topological_order(cyclic_plan())
    except CycleError as exc:
        print("环检测: " + str(exc))

运行:

cd private/labs/agp-lab
python3 -m agp_lab.task_dag

输出:

序号  任务      依赖              工期    最早开始    最早完成
1   repro   -                2       0       2
2   locate  repro            3       2       5
3   fix     locate           5       5      10
4   data    locate           6       5      11
5   test    fix              4      10      14
6   deploy  test,data        2      14      16
7   verify  deploy           1      16      17

关键路径: repro -> locate -> fix -> test -> deploy -> verify
总工期: 17
环检测: 依赖图存在环: a, b

这张表有三个要点。

关键路径不等于全部任务。 关键路径只有 6 个节点,data 不在上面。data 的工期虽然最长(6),但它与 fix 并行,只依赖 locate,最晚在 fix 完成前完成即可。如果 data 拖到 16 之后,deploy 才会被影响;只要在 16 前完成,总工期不受任何影响。这就是"有空闲的非关键任务"。

最早开始时间暴露等待。 deploy 最早开始于 14,因为它要等 test(14 完成)和 data(11 完成)都结束。data 明明 11 就完成了,却要等到 14——这 3 个单位的空闲就是并行带来的缓冲。看懂这张表,就能回答"为什么 deploy 这么晚才开始",而不是让模型"快点做"。

环必须被拒绝。 最后一行是 CycleError:两个互相依赖的节点无法排序,输出报告的是"存在环"和未排序的节点,而不是一个错误的顺序。对 Agent 来说,这个异常应该触发重新分解,而不是把环按某种启发式强行摊平。

分解要可验证,判据是什么

判据合格的样子不合格的样子
依赖显式每个子任务声明依赖列表只有任务清单,没有边
无环保证拓扑排序前做环检测有环时猜一个顺序
输入校验重复编号/未知依赖/自依赖被拒静默吞掉错误依赖
关键路径可算能算出总工期与瓶颈链只知道所有工时之和
调度确定同层顺序固定每次运行顺序不同

“调度确定"这条容易被忽略。同样的计划,两次运行的执行顺序必须一致,否则回归测试无法建立、重放会漂移。实现上用"声明顺序固定"的稳定排序,而不是集合的无序遍历。

架构含义

任务分解对架构有三个直接约束:

  1. 分解输出图,不只输出列表。 计划数据结构里必须有显式的依赖边。
  2. 计划要先验证再执行。 环、未知依赖、重复编号在规划阶段拒绝,不让执行器遇到。
  3. 总工期要有来源。 关键路径要可计算、可解释,让延误能被归因到具体子任务。

第 1 条决定了后两条。如果分解结果只是 Markdown 列表,验证器无从检查依赖,关键路径无从计算;模型的"计划"就停留在提示词层面,无法被系统保证。

与三条工作负载的关系

  • W2 代码修复天然适合 DAG:repro → locate → fix → test → deploy → verify 是一条典型的修复链,data 这类并行任务可独立追踪。
  • W3 运维处置依赖顺序更关键:先确认状态、再执行变更、最后验证恢复;跳步通常意味着不可逆风险。
  • W1 检索问答依赖浅,但也需要"先检索再引用再总结"的偏序,防止先总结后补引用。

分解粒度要匹配任务规模:W1 拆两三步就够,W2 拆到几十个子任务,W3 宁可少拆不可错拆——不可逆动作的依赖写错,代价比漏拆更大。

小结

  • 任务分解的输出应该是一张 DAG:节点是子任务,边是依赖关系。
  • 依赖声明要校验:重复编号、未知依赖、自依赖、环都必须被拒绝。
  • 拓扑排序给出合法执行顺序;最早调度给出每个子任务的等待与时限。
  • 关键路径决定总工期;资源、风险与预算都应该向关键路径倾斜。
  • 非关键路径上的任务有缓冲,延误不总影响总工期。
  • 有环时唯一安全的行为是停止并重新分解,而不是猜一个顺序。

阅读导航:上一节:3.3 推理轨迹的失败分类 · 下一节:4.2 HTN/PDDL:计划表示与可验证性 。

常见错误与边界

  1. 分解成列表不是图。 没有依赖边,就没有验证、没有关键路径、没有可归因的延误。
  2. 有环时猜顺序。 静默排一个错序会让执行半路失败;应该报告环并重新分解。
  3. 不校验输入。 重复编号、未知依赖会在执行期才炸,审计成本高得多。
  4. 把总工期当工时和。 关键路径是工期来源;非关键任务拖期不一定影响交付。
  5. 执行顺序不稳定。 同层任务顺序漂移,回归与重放无法建立。
  6. 粒度一刀切。 三类负载的分解粒度不同;W3 不可逆动作宁可少拆不可错拆。

继续阅读

探索更多技术文章

浏览归档,发现更多关于系统设计、工具链和工程实践的内容。

全部文章 返回首页

「books」更多文章

  1. 《大规模分布式计算深入解析》15.3 落地:从 Neo4j 到自研图引擎
  2. 《大规模分布式计算深入解析·图计算与图数据库内核》 · 目录与学习路径(45 篇)
  3. 《大规模分布式计算深入解析》15.2 十一卷主线:从切分到图