先说个之前真实踩过的坑调试一套多机器人搬运系统时我们用的 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 规划器一种常见的输出是这个线性计划序号动作所属任务0load(r1, pkg1, A)deliver(pkg1, A, B)1move(r1, A, B)deliver(pkg1, A, B)2unload(r1, pkg1, B)deliver(pkg1, A, B)3load(r2, pkg2, C)deliver(pkg2, C, D)4move(r2, C, D)deliver(pkg2, C, D)5unload(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 秒线性执行总耗时是 (3024030)×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的对象数组虽然占用了一些存储但调试效率高到难以衡量。如果让我给一个执行顺序建议我会说先把因果链接和层次投影跑通保证计划逻辑正确再补资源互斥保证物理可执行最后才考虑传递闭包裁剪。这个顺序也是我经过几轮重构后沉淀下来的每一步单独验收出了错也容易定位。做去序化的本质不是把顺序删光而是把“不得不保持的顺序”和“后加的临时顺序”严格区分开然后把后者的锁全部松开。