先说个之前真实踩过的坑：调试一套多机器人搬运系统时，我们用的 HTN 规划器明明给两辆小车规划出了互不依赖的任务，输出却是先让第一辆跑完全程、第二辆才开始走的线性计划。现场看就是两台设备干等着，执行时间长了将近一倍。问题不在规划器，而在我们直接把规划器输出的总序计划丢给执行器了。后来把去序化（deordering）这步补上，保留了规划结果里的层次结构（hierarchy），只把不必要的前后顺序约束拿掉，整个系统的吞吐才正常起来。
这篇东西不是概念科普，我会把“对 HTN 计划做 deordering”这件事从约束来源、算法设计、层次保留到工程落地一次讲透，适合正在做机器人任务执行、多智能体调度或任何需要把规划结果真正用起来的工程师看。
1. 顺序计划被执行系统“卡脖子”：去序化要解决的真实问题
很多入门资料喜欢把 HTN 规划的结果描述成“一个动作序列”，这个说法误导性很强。真实 HTN 规划器在求解时维护的是任务网络，包括任务节点的分解关系、变量绑定、以及节点之间的顺序约束。但在最终输出阶段，为了兼容经典执行器，绝大多数规划器会做一件事：把偏序的任务网络线性化成总序动作列表。这一步的代价是，原本可以被自由调度的动作被强行排成一条线，执行系统只能挨个执行。
我见过不少项目在规划验证阶段一切正常，一到实际现场就跑不动，瓶颈往往就在这。规划器用几毫秒生成一条 30 步的序列，执行器按顺序跑，其中三步要等机器人缓慢移动 5 分钟，但实际上这三个移动动作分属两台不同机器人，完全可以并行。线性计划把这种并行潜力完全压没了。
去序化做的工作，就是把“线性计划”还原成“偏序计划”：保留那些真正必要的先后依赖，去掉那些只是规划器搜索过程临时强加的顺序。说直白点，它相当于给规划结果做了一次约束最小化，让执行系统只受因果、资源和领域保护条件的限制，其余动作可以自由调序、并行执行。
这里要先分清两个概念：去序化不是重新规划，不改变动作集合，不改变目标状态，也不修改变量绑定和分解树；它只改变动作之间的关系。另一个容易混淆的概念是并行化——并行化往往要引入额外资源或拆分动作，而去序化只是揭示本来存在的并行度。换句话说，规划器本身可能已经找到了一个可行的并行分解，只是输出格式把它拍扁了，去序化是在做还原。
从这个角度看，去序化是规划与执行中间层的标准组件，尤其是机器人领域。ROSPlan 这类任务规划框架下游往往挂一个执行管理器，执行管理器接收的如果是一串全序动作，很多执行窗口就被堵死了。做了去序化之后，计划变成一个有向无环图，执行管理器可以根据传感器反馈动态决定哪些分支先做、哪些分支等待，现场韧性会强很多。
2. 拆解 HTN 计划里的顺序约束：哪些顺序是真的，哪些是规划器硬加的
要做去序化，首先得知道手里这份 HTN 计划里的顺序约束到底是怎么来的。我习惯把这四类约束分开看，因为它们对应的处理逻辑完全不同。
2.1 方法体里写的显式顺序
HTN 域定义中，复合任务的方法体常常直接写出子任务的执行顺序，比如“先检查电池电量，再前往目标点，最后执行装载”。这是领域工程师明确声明的语义顺序，去序化时原则上要尊重，不能因为两个子任务表面不冲突就强行拆掉。但这里有个细节容易被忽略：方法体内的顺序声明，并不代表所有兄弟子任务都必须保持严格先后。有的方法作者习惯把所有子任务写成一串列表，但实际上其中只有少数几对存在真实的前置关系。
我曾经见过一个巡逻任务的方法定义，开发者把“开舱门、开启摄像头、起飞、设置航点”四个步骤按清单顺序写在一起，而实际上开舱门和设置航点完全无关。这种顺序属于“作者方便”，不属于“领域必需”，去序化时如果能通过状态分析证明无依赖，完全可以放开。
2.2 因果前提条件带来的必然顺序
这是最核心的一类约束。一个动作的某个前提条件必须由之前某个动作产生，且中间没有被删除，那么这两个动作之间就形成因果依赖。去序化大多数情况下就是围绕因果链接展开的。
用个老土的例子：搬箱子任务的线性计划是“装载包裹 → 机器人移动到目的地 → 卸载包裹”，卸载动作要求包裹在机器人上，这个条件由装载动作产生，所以装载必须先于卸载。这不是规划器随意排的，是领域因果关系的必然结果。去序化时会为这类依赖建立一条从装载到卸载的有向边。
2.3 资源互斥与状态保护带来的隐性顺序
很多自动规划域模型是纯逻辑模型，只有谓词增删，没有显式资源。但真实系统跑起来时，两台机器人不能同时停在同一工位，充电桩一次只能给一台设备供电，机械臂和移动底盘不能并行占用。这些约束如果不在规划域里建模，规划器生成的线性计划可能根本没有输出任何顺序，结果就是去序化之后动作被调度到同一时刻，物理上直接冲突。
这种问题通常要靠一个独立于逻辑模型的资源层来补：给每个动作标注它占用的资源集合，然后在去序化算法里检测资源竞争。如果是容量为 1 的互斥资源，两个动作在同一阶段使用，就必须给它们加一条顺序边，否则并行执行会出事故。
另一种隐蔽的顺序来自保护条件。比如一个任务要求在“门保持打开”的前提下完成多次搬运，期间任何动作都不能关闭门。经典 STRIPS 风格的效果模型会把“门开着”表示成一个谓词，但如果中间某个动作删除该谓词，去序化只看前提和效果，没有专门标记保护区间，就可能允许这个删除动作插入到搬运动作之间，逻辑上又变成非法计划。
2.4 变量绑定带来的隐藏依赖
HTN 分解过程会做大量变量绑定，同一个对象可能在不同任务中作为参数出现。两个动作在谓词组面上看起来没有文本重合，但如果它们绑定到同一个物理对象，就有潜在竞争。比如两个导航动作一个把 robot1 从 A 导航到 B，另一个把 robot1 从 B 导航到 C，它们的前提完全可以通过状态分析解决，但如果资源模型不把 robot1 视为互斥资源，去序化就可能把两个导航动作并发释放，最终机器人只有一个，根本做不到。
所以完整去序化必须同时跑两套分析：逻辑因果分析和资源/绑定分析。前者负责计划正确性，后者负责物理可实现性。
3. 三个让去序化变复杂的隐藏难点
如果你只是想把一个普通顺序计划稍微松绑一下，那因果链接提取就够用了。但 HTN 计划去序化真正难的地方，在于它要同时处理层次结构、保护条件和约束规模这几个问题。我自己做实现时在下面三个坑里反复绕过，拿出来单独说说。
3.1 “能并行”和“安全并行”之间差着一整个状态更新
最简单的想法是：如果两个动作之间没有直接的因果链接，就认为它们可以互换。这在纯逻辑层面基本成立，但不安全。我举一个实际例子：动作 A 是move(robot, A, B)，效果包括删除at(robot, A)；动作 B 是scan(area, 2)，前提是robot.energy > 10。两者从谓词看完全不相关，没有因果链接，但它俩绑定了同一个机器人实体，而且 move 会消耗大量能量，可能在执行过程中把能量降到 10 以下，导致 scan 前提在真正开始执行时被破坏。
这种情况下，规划器只会把“现状”中成立的前提当作可满足的，去序化如果不追踪状态在计划执行路径上的变迁，就会错误地认为 scan 和 move 可以任意并行。正确做法是，在做因果分析时不仅看“某个条件由哪个动作产生”，还要看条件在整个执行窗口内是否稳定。也就是说，要维护一个连续的状态推进器，对每个候选并行对做一次局部 simulate，确认交换执行不会破坏任何前提。
3.2 保护条件不像普通前提那么好检测
普通前提只在动作开始瞬间检查，保护条件却要求某个表达式在一段区间内持续成立。经典计划的因果链接无法完整表达这一点，因为因果边是“后一个动作的前提由前一个动作产生”，它没有显式建模“此条件必须保持到某个里程碑”这种语义。
HTN 的方法体里这种模式非常常见：先初始化某个状态，然后连续执行多个动作都依赖它，最后再清除。如果在去序化时把保护区间拆成一堆普通的因果链接，你会得到庞大且脆弱的约束网络。更好的是把保护区间当成一个独立节点，连接到区间内所有使用该条件的动作，同时再连接所有可能删除该条件的动作，让约束结构保持清晰。这是我后来在无人机任务里被坑了几次才总结出来的经验。
3.3 约束网络膨胀：冗余边会吃掉并行度
线性计划长度为 n 时，朴素地给所有存在“潜在依赖”的动作对加边，边数最多会到 O(n^2)。HTN 计划不像经典块状计划那么规整，一个复杂分解树可能有几百个叶子动作，高度嵌套，不少局部约束在全局视野下根本是冗余的。
举个例子：动作 a 产生资源 rid，动作 b 使用它，动作 c 也使用它，并且 a → b → c 已经形成传递闭包。如果你在构建因果链时既加了 a → b、b → c，又额外加了 a → c，那么 a → c 就是冗余边，它不会破坏正确性，却会让调度器误以为 a 和 c 存在直接依赖，某些本可以并发执行的窗口会被压缩。传递闭包裁剪因此必须是去序化流程的最后一步，而且是强制步骤。
4. 核心算法：从线性序列到最小偏序约束图
讲完难点，给出一套我实际在用的去序化流程。这个流程不绑定特定 HTN 规划器，输入只需要三样东西：原始线性计划动作列表、初始状态、分解树（至少要知道每个叶子动作归属于哪个复合任务）。输出是一个带层次标注的偏序约束图。
4.1 第一步：因果链接提取
对计划中每个动作，检查它的每个前提条件，回溯到最近一个在“当前执行状态”中还保持该条件为真的动作（即“最新生产者”），如果存在，则建立一条有向边。伪代码大致这样：
def extract_causal_links(plan, initial_state): state = set(initial_state) producer = {} edges = [] for i, act in enumerate(plan): for p in act.preconditions: if p in state and p in producer: edges.append((producer[p], i)) for d in act.delete_effects: if d in producer: del producer[d] state.discard(d) for a in act.add_effects: producer[a] = i state.add(a) return edges这段代码重点在“前提检查 → 删除效果 → 添加效果”的顺序：先判断前提是否来自当前状态和最新生产者，再更新状态，避免动作自己给自己生产前提。注意它假设计划本身是合法的，即每个前提在每一步都成立，否则逻辑上就有 bug 了。
4.2 第二步：叠加资源互斥和副作用
规划域里没有资源的场景，需要单独定义每个动作的资源占用表。我通常用一个简单集合表示：move(robot1, A, B)占用{robot1}，charging(robot1, station1)占用{robot1, station1}。然后在已构建的因果约束图上，对每一对动作检查：如果它们占用了同一个容量为 1 的资源，并且当前没有其他约束天然让它们顺序化，就给它们加一条有序边，方向可以按启发式来，比如先发生动作的生产者优先，或者按原始计划顺序，只要最终形成一个无环约束图即可。
资源互斥加边有一个容易被忽视的点：方向不能随意倒着加，否则可能制造环。比如动作 a 与 b 共用资源，a 与 c 又一前一后，如果前面已经根据因果设置了 a → c，你又把 c → b 的资源边倒着加进去，可能形成一个 a → c → b 再连回 a 的环。解决方法是把所有资源边先存成候选集，最后统一做一次图判环校验，冲突时按原始计划顺序作为最终仲裁。
4.3 第三步：叠加保护条件区间
对每个保护条件区间(start_idx, end_idx, condition)，做两件事：一是找到区间内所有依赖该条件的动作，把区间开始动作与它们依次连边；二是找到区间内所有可能删除该条件的动作，把它与区间结束动作连边，确保删除不会提前。这个模型很像在约束图里插入一个“保护段”虚拟节点，但不是真节点，而是一簇边。
这一步务必在资源约束之后做，因为保护条件常常与资源占用耦合。例如无人机任务中“保持通信链路稳定”这个保护区间，区间内任何需要通信的动作都会消耗通信资源，而对这些动作做资源互斥时，必须已经知道谁落在保护区间内。
4.4 第四步：传递闭包裁剪
约束图构建完毕后，先做一次传递闭包计算，得到所有“可到达”的顺序关系，然后保留一个最小无环图，使得任意两个动作之间原有传递闭包关系不丢失，但不断开因果语义。具体实践中我不会完全删除因果边，而是以因果边为骨干，把冗余的传递边去掉。因为因果边代表“这个条件必须有生产者”，它是语义的根，而资源边和保护边属于执行安全层，可以在最小化过程中被传递关系吸收掉。
复杂度上，动作数量 n 在几百这个级别时，Floyd-Warshall 的 O(n^3) 虽然慢但可以接受；如果计划上万步，就要用拓扑序 + 分段剪枝，或者基于可达矩阵位运算优化。大多数机器人应用场景里 n 不超过一两千，直接实现起来没什么压力。
4.5 输出格式
最终约束图节点是原始动作，边是序关系，每个节点额外携带一个task_id字段，指向它所属的复合任务。有了这个字段，后面做层次视图就方便了。以下这个结构在工程里非常好用：
{ "actions": [ {"id": 0, "name": "load(r1,pkg1,A)", "htn_task": "deliver(pkg1,A,B)"}, {"id": 1, "name": "move(r1,A,B)", "htn_task": "deliver(pkg1,A,B)"}, {"id": 2, "name": "unload(r1,pkg1,B)", "htn_task": "deliver(pkg1,A,B)"}, {"id": 3, "name": "load(r2,pkg2,C)", "htn_task": "deliver(pkg2,C,D)"} ], "order_edges": [[0,1], [1,2], [3,null]], "task_hierarchy": { "deliver(pkg1,A,B)": [0,1,2], "deliver(pkg2,C,D)": [3,4,5] } }5. 层次不能丢：去序化后的分解树标注与层级视图
很多去序化实现只关注动作层的偏序图，拿到手就是一张拍平的 DAG，看起来能并行，用起来却让执行系统痛苦不堪。因为执行系统不仅要知道“哪个动作依赖哪个动作”，还要知道“这组动作共同完成的是哪个子目标”。HTN 规划结果最大的资产就是分解树，它记录了每个复合任务如何被细化成子动作，这层信息不能丢。
5.1 为什么要保留层次而不是只输出 DAG
动作级 DAG 在几十个动作时还能看，一旦上了几百个节点，人没法从中读懂计划意图。而带层级的偏序计划可以折叠：顶层看到的是“任务 A 与任务 B 可并行”，展开任务 A 才看到它内部的具体动作链。调试时先看哪个复合任务卡住，再下钻到叶子动作，比在巨型 DAG 里找原因高效得多。
执行层面更有价值：复合任务往往是执行管理器的基本恢复单位。一个搬运动作失败，通常要重新执行整个“搬运包裹”复合任务，而不是单独重试其中一个动作。没有层次标注，执行器只能盲目重放失败点附近的一串动作，很容易丢失上下文。
5.2 复合任务级并行度：把动作层偏序提升到任务层
层次视图不是简单地把叶子动作按父节点分组就完事，还需要计算复合任务之间的序关系。规则其实很简单：两个复合任务 T1 和 T2，如果 T1 的任意叶子动作与 T2 的任意叶子动作之间存在一条序边，那么在任务层上 T1 与 T2 就有对应顺序；如果没有任何边关联，它们就可以并行。
这个投影规则我用在一次无人机侦察任务里非常有效。顶层有三个复合任务“起飞”“执行区域扫描”“返航降落”，去序化后动作层显示“执行区域扫描”内部的某些图像采集动作竟然与“返航”的盘旋动作没有因果边，理论上可以重叠，但从任务语义上没人会这样调度。保留层次并投影后，任务层仍然显示三个复合任务串行，不会诱导调度器做危险优化。
所以层次视图的真正作用是“防止过度并行”。动作层允许的并行窗口是理论上限，任务层给出的并行窗口才是更接近语义安全边界的执行建议。
5.3 两层结构同时输出，并让人能看懂
我最后落地的方案是输出两份图：一份是“任务执行图”，节点是复合任务或原始动作，边代表复合任务之间的序依赖；另一份是“叶子动作依赖图”，供底层调度器做精细的并行窗口分析。执行引擎先按任务执行图安排大的阶段，再在每个阶段内用叶子动作图做微观调度。这样兼顾语义安全和执行效率。
关键编码点在于每个叶子动作上保留一个parent_task指针，更新时同样递归更新上层任务的序边。这相当于维护一个从叶子到根的蕴含关系，实现不复杂但必须做对。如果某个复合任务内部出现了环，说明去序化过程引入了不一致，规划器输出的原始计划可能被破坏，这时应直接抛错而不是继续下游执行。
6. 实测案例：一个典型物流 HTN 计划的完整去序化过程
理论讲再多，不如跑一遍实际例子。我用一个简化版多机器人物流域来说明，这个例子足够小又能体现前面所有约束类型。
6.1 域定义与初始计划
这里有辆机器人：robot1 在 A 点，robot2 在 C 点；包裹 pkg1 在 A 点，pkg2 在 C 点。HTN 域定义了deliver(p, from, to)复合任务，方法体固定为“装载 → 移动到目标 → 卸载”。初始状态与目标要求两个包裹分别被送到 B 和 D。
HTN 规划器一种常见的输出是这个线性计划：
| 序号 | 动作 | 所属任务 |
|---|---|---|
| 0 | load(r1, pkg1, A) | deliver(pkg1, A, B) |
| 1 | move(r1, A, B) | deliver(pkg1, A, B) |
| 2 | unload(r1, pkg1, B) | deliver(pkg1, A, B) |
| 3 | load(r2, pkg2, C) | deliver(pkg2, C, D) |
| 4 | move(r2, C, D) | deliver(pkg2, C, D) |
| 5 | unload(r2, pkg2, D) | deliver(pkg2, C, D) |
这个顺序完全合法，但它把两条本可并行的任务链硬排成了串行。
6.2 约束图构建全过程
第一步提取因果链接，会得到三组内在约束：
- load(r1, pkg1, A) → move(r1, A, B)，因为 move 前提
at(r1, A)由 load 产生； - move(r1, A, B) → unload(r1, pkg1, B)，因为 unload 前提
at(r1, B)和in(pkg1, r1)都需要前序动作支撑； - load(r2, pkg2, C) → move(r2, C, D) → unload(r2, pkg2, D)，同理。
接下来做资源互斥扫描：每个动作占用各自的机器人，robot1 相关动作和 robot2 相关动作之间没有共享资源，所以不会增加跨链约束。到这里，约束图已经清楚地分成两条独立链，任意一动一静两组动作之间都可以换序。
保护条件在本例中没有额外约束，因此可以跳过。最后做传递闭包裁剪，每条链内部的三节点边已经是极简形式，无需继续削减。
6.3 结果对比与执行收益
去序化后的偏序计划可以直观写成两列：
deliver(pkg1, A, B) deliver(pkg2, C, D) load(r1, pkg1, A) load(r2, pkg2, C) move(r1, A, B) move(r2, C, D) unload(r1, pkg1, B) unload(r2, pkg2, D)两列之间没有任何依赖边，执行系统可以让 robot1 和 robot2 同时开始。如果移动作业耗时 240 秒，装载卸载各 30 秒，线性执行总耗时是 (30+240+30)×2 = 600 秒，并行执行只要 300 秒。这就是去序化最直接的收益。
但我必须提醒一个反向场景：如果两个deliver任务共用同一台机器人，去序化后资源互斥检查会给所有涉及 robot1 的动作按原始计划顺序加边，约束图依然会形成一条长链。此时去序化不会把计划变成并行的，因为物理上它根本不能并行。这类场景要提前做好预期管理，别把去序化当成“能把所有计划都变快”的魔法。
7. 落地时容易踩的五个坑
最后分享几个我在工程里反复撞过的坑，这些细节很少写在论文里，但直接影响系统能不能真正跑起来。
7.1 因果链接里漏掉“隐式前提”
不少动作模型只声明了显式前提，但执行时还会依赖一些环境条件，比如机器人导航依赖地图已经加载、机械臂动作依赖安全门已关闭。如果你只对显式前提做因果分析，这些条件一旦被并行动作破坏，执行就会很随机地出问题。我的习惯是给每个动作加一个可选的implicit_preconditions集合，去序化时同样参与因果匹配。
7.2 资源互斥建模过粗导致“并行死锁”
只把机器人建模成资源远远不够。机器人的导航模块、机械臂、电池、通信信道都应视为独立资源。交互上有个经典 bug：动作 A 占用机械臂，动作 B 占用导航模块，机械臂和导航模块互不冲突，但实际上两者操作的是同一个机器人主体，根本不能物理并行。建模粒度要贴合物理本体，否则去序化算出来的并行窗口执行器坚决反对，两边就对不上。
7.3 裁剪冗余边时把保护区间语义削掉了
传闭包裁剪优化很容易引入这类问题：a → b 是资源边，b → c 是保护边，理论上传递闭包保留 a → c，然后删掉 a → b。但如果你删的是资源边，系统重新做一次并发调度时，a 和 b 可能被分配在同一时间窗口，尽管整体顺序仍然满足 a 在 c 之前，资源冲突还是会爆发。所以在裁剪时必须把边分成“语义骨干”和“传递冗余”两类，只删后者。
7.4 复合任务层的并行判定没有考虑“同步点”
有些复合任务内部要求子任务全部结束后才能通知上一层，这种同步点在层次视图里表现为一个虚拟的 join 节点。做任务层投影时如果忽略 join，两个复合任务的叶子动作也许没有直接边，但它们在执行时必须等到对方某个子任务完成，这时任务层应该建立隐藏互斥关系。否则调度器会在两个复合任务之间安排重叠执行，到了同步点又只能等，白白浪费调度机会。
7.5 只输出偏序图不输出“为什么”
偏序图里的每条边都应该能追溯到来源：是因果链接、资源约束、保护区间还是方法体显式顺序。工程调试时，执行器报告“动作 4 不能与动作 7 并行”只是一个表面现象，你必须能追问下去，找到是哪个条件的生产者链出了问题，才能快速定位模型 bug 或者重新调整资源分配。我最终会在导出的 JSON 里把order_edges扩展成带reason_type和description的对象数组，虽然占用了一些存储，但调试效率高到难以衡量。
如果让我给一个执行顺序建议，我会说：先把因果链接和层次投影跑通，保证计划逻辑正确；再补资源互斥，保证物理可执行；最后才考虑传递闭包裁剪。这个顺序也是我经过几轮重构后沉淀下来的，每一步单独验收，出了错也容易定位。做去序化的本质不是把顺序删光，而是把“不得不保持的顺序”和“后加的临时顺序”严格区分开，然后把后者的锁全部松开。
