以下数字为教学示例,不构成对任何真实系统或供应商的承诺。
任务分解(task decomposition)是 Agent 规划的第一步,也是最常被低估的一步。让模型"把大任务拆成小任务"很容易,结果却往往是"拆出了一个列表",而不是"拆出了一张图"。列表只回答"有哪些事",图才能回答"哪件先做、哪件等谁、哪条路决定总工期"。
这一节把任务分解建模成有向无环图(DAG):节点是子任务,边是依赖关系。建模之后,拓扑排序、关键路径这些成熟算法就可以直接给出可验证的计划;反过来,依赖声明里的错误(重复、未知依赖、环)也会在规划阶段就被抓住,而不是执行到一半才发现。
为什么必须是 DAG
依赖关系必须是无环的。环意味着计划自相矛盾:A 依赖 B,B 又依赖 A,没有一个可以开始的节点。
环有两种来源,值得区分:
- 声明错误:模型分解时把依赖写成了环,这是可修复的规划错误;
- 真实循环:任务在业务上确实需要来回,这通常说明分解错了——真正依赖的应该是更细粒度的子任务,或者需要重设计。
无论哪种,正确的处理都是在规划阶段拒绝并报告,而不是给它随便排一个顺序。实验里用"检测到环"而不是"排序成功"来收尾,正是这个意图:有环时唯一安全的行为是停止并让计划者重写。
拓扑排序与最早时间
有了 DAG,就可以做两件对 Agent 有意义的事:
- 拓扑排序:给出一个满足所有依赖的执行顺序。同一层可并行的节点按声明顺序固定,保证输出确定、可回归。
- 最早调度:对每个任务算"最早开始时间"和"最早完成时间"。最早开始等于其所有依赖的最晚完成,这决定了每个子任务能等多久、最迟何时必须开始。
最早时间不只是调度工具,它还是延误检测的基准:实际运行里某个子任务超过了最早完成时间,你就可以量化"这次延误推迟了总工期多久",而不是模糊地说"变慢了"。
关键路径:哪条路决定总工期
总工期不是所有任务工时之和,而是关键路径的长度:那条最长的依赖链。非关键路径上的任务有空闲时间,拖几天可能不影响总工期;关键路径上的任务晚一天,总工期就晚一天。
关键路径对 Agent 有三个直接用途:
- 资源优先:慢的模型、多的重试,优先投在关键路径上;
- 风险排序:关键路径上的任务失败影响最大,需要更强的验证器;
- 预算分配:非关键路径可以压缩或降级,不影响整体进度。
最小实验:七节点修复计划
下面的实验给出一个七节点的支付回调修复计划,打印它的拓扑序(最早调度)、关键路径与总工期,最后用两节点环演示拒绝行为。
# 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 条决定了后两条。如果分解结果只是 Markdown 列表,验证器无从检查依赖,关键路径无从计算;模型的"计划"就停留在提示词层面,无法被系统保证。
与三条工作负载的关系
- W2 代码修复天然适合 DAG:repro → locate → fix → test → deploy → verify 是一条典型的修复链,data 这类并行任务可独立追踪。
- W3 运维处置依赖顺序更关键:先确认状态、再执行变更、最后验证恢复;跳步通常意味着不可逆风险。
- W1 检索问答依赖浅,但也需要"先检索再引用再总结"的偏序,防止先总结后补引用。
分解粒度要匹配任务规模:W1 拆两三步就够,W2 拆到几十个子任务,W3 宁可少拆不可错拆——不可逆动作的依赖写错,代价比漏拆更大。
小结
- 任务分解的输出应该是一张 DAG:节点是子任务,边是依赖关系。
- 依赖声明要校验:重复编号、未知依赖、自依赖、环都必须被拒绝。
- 拓扑排序给出合法执行顺序;最早调度给出每个子任务的等待与时限。
- 关键路径决定总工期;资源、风险与预算都应该向关键路径倾斜。
- 非关键路径上的任务有缓冲,延误不总影响总工期。
- 有环时唯一安全的行为是停止并重新分解,而不是猜一个顺序。
阅读导航:上一节:3.3 推理轨迹的失败分类 · 下一节:4.2 HTN/PDDL:计划表示与可验证性 。
常见错误与边界
- 分解成列表不是图。 没有依赖边,就没有验证、没有关键路径、没有可归因的延误。
- 有环时猜顺序。 静默排一个错序会让执行半路失败;应该报告环并重新分解。
- 不校验输入。 重复编号、未知依赖会在执行期才炸,审计成本高得多。
- 把总工期当工时和。 关键路径是工期来源;非关键任务拖期不一定影响交付。
- 执行顺序不稳定。 同层任务顺序漂移,回归与重放无法建立。
- 粒度一刀切。 三类负载的分解粒度不同;W3 不可逆动作宁可少拆不可错拆。
继续阅读
探索更多技术文章
浏览归档,发现更多关于系统设计、工具链和工程实践的内容。