Hierarchical Task Network Planning with LLM-Generated Heuristics¶

会议: NeurIPS 2026
arXiv: 2605.07707
论文: https://arxiv.org/abs/2605.07707
代码: 待确认
领域: LLM Agent
关键词: 分层任务网络规划、启发式搜索、大语言模型代码生成、符号规划、Pytrich规划器

一句话总结¶

将大语言模型启发式生成范式从经典规划拓展至全序分层任务网络（HTN）规划，通过结合位运算状态编码与任务网络层次信息的生成-评估-选择管线，生成高效的 Python 启发式代码，在基准测试中使搜索扩展节点数在 83% 的共享问题上大幅低于 SOTA 规划器 Panda。

研究背景与动机¶

分层任务网络（Hierarchical Task Network, HTN）规划是机器人任务规划、复杂游戏 AI 与智能助手决策中的核心形式化方法。不同于仅在平坦状态转移空间中搜索动作序列的经典规划，HTN 规划通过方法库（Method Library）将高阶抽象复合任务逐步递归分解为可执行的基元动作序列，其搜索空间由世界状态（World State）与任务网络（Task Network）联合构成。这种分层分解机制将人类专家的程序性领域知识显式固化在方法结构中，直接约束了动作探索的顺序与组合，从而在本质上起到了显式启发式指导的作用。

然而，这也导致 HTN 领域的独立启发式函数研发长期滞后。现有的领域无关启发式（如任务分解图松弛 TDG、基于界标计数的 LMCount 以及 Panda 规划器中的可达性松弛族 \(\text{RC}^{\text{FF}}\) 和 \(\text{RC}^{\text{LMCut}}\)）不仅理论估计松弛较弱，且在大规模复合任务中面临严重的内存与计算瓶颈。2020 年国际规划竞赛（IPC 2020）HTN 赛道的冠军 HyperTensioN 甚至完全不依赖可采纳启发式，而是依靠递归搜索与高效剪枝取胜，这充分暴露出人工工程化设计普适、紧致的 HTN 启发式面临着极高壁垒。

近期研究表明，大语言模型（LLM）能够根据规划域描述自动编写 Python 启发式代码，并在经典状态空间规划中战胜传统基准。但在 HTN 规划中，启发式函数不能仅计算命题真值的距离，还必须深刻理解待处理任务网络、动作拓扑序约束以及复合任务的多重可选分解路径。本文的核心 idea 是：将 LLM 启发式代码生成扩展至全序 HTN 规划，通过设计暴露位运算状态与任务网络分解上下文的 Python 接口，配合领域提示词与反模式过滤引导模型生成 O(1) 紧致下界函数，在单个微型训练实例上筛选出最佳代码并无缝部署于全量基准。

方法详解¶

核心机制¶

HTN 规划问题由元组 \(\mathcal{P}_{\text{HTN}}=\langle s_0, \omega_I, F, A, C, \mathcal{M} \rangle\) 定义，其中 \(F\) 为基元命题（fluents），\(A\) 为动作算子，\(C\) 为复合任务，\(\mathcal{M}\) 为分解方法库，\(\omega_I\) 为初始任务网络，\(s_0 \subseteq F\) 为初始状态。全序 HTN 规划要求任务网络 \(\omega=\langle T, \prec, \alpha \rangle\) 中的任务具有严格的线性拓扑序。

启发式函数 \(h(s, \omega)\) 的核心机制在于同时度量两重剩余代价： 1. 任务网络剩余分解与执行代价：基于任务网络中残留的复合任务与基元任务，评估将其完全展开为可执行基元序列所需的最小动作成本； 2. 状态感知目标距离（State-Aware Pipeline Distance）：度量当前世界状态 \(s\) 距离满足任务前提或最终目标命题的不可避免的操作步数。

为了使生成代码能在数万次节点扩展中保持纳秒级响应，方法在底层将世界状态与算子条件全量编码为长整型位掩码（bitsets）。单次命题查询仅需一次右移与与操作 (state >> fact.global_id) & 1，将原本 \(O(|F|)\) 的字符串比对压缩至 \(O(1)\)，并强制所有全局不动点表与静态拓扑分析在搜索初始化阶段预计算完成。

整体框架与流程¶

整个方法由“提示词构建 \(\to\) 批量代码采样 \(\to\) 沙盒执行与单实例评估 \(\to\) 极小化节点选择 \(\to\) 全量基准求解”五个紧密衔接的阶段构成。

%%{init: {'theme': 'base', 'themeVariables': {'fontSize': '12px', 'lineColor': '#2B6CB0'}, 'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["输入：HDDL领域定义 + 极值示例 + 领域提示块"] --> B["阶段 1：领域提示词构建<br/>明确四步设计要求与反模式警示"]
    B --> C["阶段 2：LLM 批量代码生成<br/>采样 N=20 个候选 Heuristic 类"]
    C --> D["阶段 3：沙盒执行与单实例评估<br/>在最小训练问题上运行（60s 超时）"]
    D --> E["阶段 4：极小扩展节点筛选<br/>过滤崩溃/超时，选取展开节点最少者"]
    E --> F["阶段 5：Pytrich 求解器集成部署<br/>结合 A*/GBFS/WA* 在全部测试集展开搜索"]

在 Pytrich 规划器内部，入选的启发式实例贯穿搜索全生命周期：在根节点处调用一次 initialize 执行预处理，在搜索树每次弹出父节点并产生子节点时调用 __call__ 输出整数评价值，驱动优先队列排序。

关键设计（带序号的紧凑段落）¶

1. 预处理与单步求值分离的双阶段接口设计：消除扩展循环中的计算开销

传统 LLM 生成的代码容易在每次节点扩展时遍历全图，导致严重的搜索超时。针对此问题，系统设计了继承自 Pytrich Heuristic 的纯 Python 类接口，强制拆分为 initialize(self, model: Model, initial_node: HTNNode) 与 __call__(self, parent_node: HTNNode, node: HTNNode) -> int。所有复杂的图遍历、谓词全局索引建立、静态关系解析以及类似 TDG 的不动点下界代价表计算全部限制在 initialize 阶段一次性预计算，将缓存数组存储于实例属性中；而在 __call__ 中仅执行数组查表、位运算及常数加和，确保节点扩展的时间复杂度严格保持在 \(O(1)\)。

2. 结构化领域提示机制与反模式规避模板：引导模型理解分层语义

为了使 LLM 能够准确理解 HDDL 语法的底层编译细节并产生符合规范的代码，提示词包含十二个标准段落。除了领域定义和极大极小训练实例外，提示词显式注入了包含三要素的领域提示块（Hint Block）：接地元件命名格式（如 +predicate[arg1,arg2]）、主要搜索瓶颈识别（如 Barman 中的倒酒对称性或 Rover 中的路径规划）以及启发式构造建议。同时，提示词明确列出了 4 种致命反模式（A1：完全忽略状态位运算；A2：退化为字符串扫描；A3：在 __call__ 中循环迭代算子；A4：仅读取生成当前节点的上一动作而非剩余网络），强制模型结合独立的下界并通过 \(\max\) 或解耦加和进行组合。

3. 基于单个最小训练算例的极小扩展过滤法：无参数调优的高效模型选择

为实现全自动、模型无关的启发式筛选，管线为每个领域和 LLM 组合批量并发生成 \(N=20\) 个候选脚本。所有候选脚本在当前领域的最小基准问题上直接执行（设定 60 秒硬超时）。执行过程自动过滤掉语法解析失败、抛出运行时异常、内存超限或超时的无效代码；在成功求解的有效候选集合中，选择扩展节点数（Expanded Nodes）最少的启发式，并在节点数打平时优先选择解步长更短者。这一标准完全无需人工审阅代码或微调超参数，仅凭极轻量的离线成本即可筛选出质量优异的启发式。

4. 结合次级单位微小惩罚的对称性打破机制：保持可采纳性同时加速队列收缩

在诸如 Barman（调酒杯对称放置）或 Blocksworld（多个等效积木）等高度对称的规划域中，等价状态导致优先队列大量平局，引起无意义的盲目搜索。设计规范允许并在提示词中指导模型在可采纳整数下界的基础上引入微小的浮点次级惩罚项（例如乘以 \(0.001\)）。该机制能够敏锐区分部分满足前置依赖的中间状态，打破同层对称节点间的扩展顺序，大幅加速最优路径的收敛，且不破坏整体代价估算的相对趋势。

理论分析与设计权衡¶

在全序 HTN 规划中，A* 算法即使配备完美启发式也可能是不完备的（Yousefi et al., 2025），这是因为无代价循环分解会导致算法陷入无限递归分支。因此，寻找全局最优解的理论保证在 HTN 中本身受限，搜索算法的核心诉求在于在有限时间和内存内最大化覆盖率并最小化搜索节点开销。

在设计权衡上，研究对比了贪婪最佳优先搜索（GBFS）、加权 A（WA, \(w=5\)）与标准 A。实验证明，GBFS 在 LLM 启发式驱动下表现最佳，其平均展开节点数仅为 A 的约 \(45\%\)。这一现象揭示了一个深层机理：当 LLM 生成的启发式已经高度编码了剩余复合任务的分层分解代价时，追踪实际消耗的累计动作步长 \(g(n)\) 反而会引入噪声，而纯粹以启发式 \(h(n)\) 指引贪婪搜索更能充分发挥分层知识的剪枝威力。

实验关键数据¶

主实验¶

实验基于 IPC 2020 HTN 规划赛道的 6 个标准全序基准域（共 139 个问题实例），对比了 LLM 启发式（虚拟最佳 LLM 及单模型 Claude Opus 4 / CO4）、Pytrich 原生基线（TDG、LMCount）以及当前最强的完整 HTN 规划器 Panda（配置可达性松弛启发式 \(\text{RC}^{\text{FF}}\) 与 \(\text{RC}^{\text{LMCut}}\)）。资源限制统一为 1 核 CPU、8 GB 内存、30 分钟超时，展示各系统在 A、GBFS 和 WA 上的虚拟最佳覆盖数。

领域（Domain）	问题总数	Panda \(\text{RC}^{\text{FF}}\)	Panda \(\text{RC}^{\text{LMCut}}\)	Pytrich TDG	Pytrich LMCount	Pytrich CO4	Pytrich LLM (Virtual Best)
Barman-BDI	20	18	14	18	19	20	20
Blocksworld-GTOHP	30	30	25	23	30	30	30
Depots	27	27	24	23	27	27	27
Robot	20	20	20	11	11	12	12
Rover-GTOHP	27	26	18	27	16	27	27
Towers	15	13	12	15	15	15	15
总计（Total）	139	134	113	117	118	131	131

消融与模型对比实验¶

实验评估了来自 Anthropic、Google 和 OpenAI 的 9 款大模型在 6 个领域中生成启发式的有效性、中位数搜索扩展节点数，以及不同搜索算法对探索效率的影响。

模型 / 算法配置	可运行领域数	候选通过率 (通过/生成)	中位数展开节点数 (Overall)	胜过 Panda \(\text{RC}^{\text{FF}}\) 胜率	说明
Claude Opus 4 (CO4)	6 / 6	78 / 120	1,878	83.2% (104/125)	最强单模型，性能逼近极度昂贵的 LMCut
Gemini 3 Flash	6 / 6	65 / 120	4,346	68.0%	第二强模型，轻量高效
Gemini 3 Pro	5 / 6	52 / 120	14,746	55.2%	在 Depots 域全量运行时崩溃
Gemini 2.0 Flash	6 / 6	48 / 120	48,631	38.4%	代码常退化为仅统计动作项，指导偏弱
Gemini 2.5 Pro	6 / 6	45 / 120	51,200	36.8%	容易陷入反模式 A1/A4，中位数节点偏高
GPT-4o / Sonnet 4.5	1 / 6	-	8,614*	-	仅在 Depots 存活，其余域全部未通过筛选
GPT-5 / GPT-5.2	1 / 6	-	109,274*	-	仅在 Towers 存活，普遍误解位运算 API
搜索算法消融: GBFS	-	-	10,553	-	效率最高，比 A* 快 2.2 倍
搜索算法消融: WA*	-	-	14,705	-	次优折中
搜索算法消融: A*	-	-	23,502	-	完备但受累计代价 \(g(n)\) 拖累，节点数最多

*注：仅在单领域存活的模型其中位数节点仅代表该特定领域，不可直接横向类比。

关键发现¶

显著降低搜索开销：在与最强基线 Panda \(\text{RC}^{\text{FF}}\) 共同解决的 125 个问题中，LLM 虚拟最佳在 104 个问题（83%）上展开了更少的搜索节点。在 Rover 域展开节点平均减少 74%，Barman 减少 55%，Towers 减少 33%，Blocksworld 减少 26%。
对传统基准的绝对优势：面对同平台的 Pytrich TDG 基线，LLM 启发式在所有共享问题上胜率为 100%，并在 Barman 域将搜索节点缩减了 97%，彻底突破了 TDG 容易因内存溢出（OOM）崩溃的局限。
解步长表现优异：得益于 Pytrich 平台在分层分解中的紧凑探索，Pytrich + LLM 返回的规划解步长比 Panda 短 64%（所有共享问题中位数仅 74 步基元动作，而 Panda 为 232 步）。
模型质量方差剧烈：五款主要模型在中位数节点数上差距高达 27 倍（Opus 4 的 1,878 节点 vs. Gemini 2.5 Pro 的 51,200 节点）。此外，半数模型存在严峻的 API 格式误解（72 个部署崩溃候选中有 83% 误将 bitset 当作普通 set 集合操作）。

亮点与洞察¶

多层知识无缝互补：HTN 的方法库已经承载了第一层“如何拆解任务”的领域知识，而 LLM 生成的启发式提供了第二层“不同拆解路径和目标状态代价几何”的数值指引，两者结合形成了极强的剪枝能力。
单样本极简筛选的惊人泛化力：仅凭领域中规模最小的一个微型问题进行无梯度过滤，筛选出的启发式函数即可直接泛化并扩展到包含上千步分解的大规模测试集上。
符号架构与神经生成的完美分工：LLM 仅负责离线编写确定性的启发式代码，搜索树遍历与动作合法性完全由成熟的符号规划器 Pytrich 校验，在彻底消除 LLM 幻觉风险的同时享受了神经常识带来的启发式红利。

局限与展望¶

规划域覆盖局限：当前工作仅聚焦于全序（Total-Order）HTN 规划，尚未覆盖偏序（Partial-Order）规划、包含数值连续变化（Numerical Fluents）或时间约束（Temporal Planning）的复杂现实场景。
代码生成的鲁棒性瓶颈：尽管给出了详尽的 API 示例与类型声明，仍有近半数 LLM 无法可靠生成可运行代码，高比例的位运算 API 误解表明提示词工程与模型代码遵循能力仍有较大提升空间。
冷启动离线计算代价：每个领域需要采样 20 个候选并在微型实例上预演，对于单次快速部署或动态频繁变更的规划域而言，预生成开销依然不可忽略。

评分¶

新颖性: ⭐⭐⭐⭐☆ (将 LLM 代码生成创新性地迁移至分层任务网络规划，设计了适配任务网络与状态位运算的专属接口)
实验充分度: ⭐⭐⭐⭐⭐ (全面评测 9 款主流 LLM、6 个 IPC 官方基准域、3 种经典搜索算法及多个 SOTA 规划器)
写作质量: ⭐⭐⭐⭐⭐ (结构极为扎实清晰，错误模式分析深入骨髓，附录实验细节详尽)
价值: ⭐⭐⭐⭐⭐ (为神经符号结合提供了极具工业落地价值的范式，对自主智能体规划与复杂长程决策有重大启发)