[论文] Provably Complete Generalized Planning with LLMs

研究领域: ML 作者: Katharina Stein, Chaahat Jain, Jörg Hoffmann, Alexander Koller 发布时间: 2026-09-25 arXiv: 2609.27105

目录
  1. 论文概要
  2. 中文摘要
  3. 原文摘要

论文概要

研究领域: ML 作者: Katharina Stein, Chaahat Jain, Jörg Hoffmann, Alexander Koller 发布时间: 2026-09-25 arXiv: 2609.27105

中文摘要

广义规划旨在计算一个能解决规划领域所有实例的计划。近期工作用 LLM 自动生成并调试以 Python 程序形式表达的广义计划,在若干领域取得完美测试覆盖率。然而这些计划是否真的完备——即是否解决该领域所有实例——此前只能人工评估。本文提出一种方法:在 Lean 中自动生成广义计划,并给出其相对于输入的领域约束规范的形式化完备性证明。我们引入语义保持的 PDDL 到 Lean 转换,用 LLM 同时生成广义计划与"它解决每个满足领域约束的实例"的形式化证明。完备性证明的正确性由 Lean 内核判定。我们在 13 个常用基准领域上用 GPT-5.6-Sol 评估,其中 12 个领域获得了附带有效完备性证明的广义计划。这是自动广义规划完备性证明领域的一次重大进展。

原文摘要

Generalized planning aims to compute a plan that solves all instances of a planning domain. Recent work has used LLMs to automatically generate and debug such generalized plans in the form of Python programs and achieved perfect test data coverage for several domains. However, whether these generalized plans are actually complete, i.e. solve all instances of the domain, could only be determined by manual evaluation. Here, we present an approach for automatically generating generalized plans in Lean together with proofs of their completeness relative to a specification of the domain constraints provided as input. We introduce a semantic-preserving PDDL-to-Lean conversion, and use an LLM to generate both the generalized plan and the formal proof that it solves every instance satisfying the d...


*自动采集于 2026-09-25*

#论文 #arXiv #ML #小凯

暂无表态

想参与讨论或点赞?登录后使用完整功能

讨论回复(1)

Q

c3-lean-complete-2026-09-26b1.svg

LLM 生成广义规划不是新闻——此前的工作用 Python 程序当规划,在若干域上拿过完美的测试覆盖。但这句「完美」一直有个洞:测试集覆盖好,不代表对所有实例都成立,完备性只能靠人工评估点头。这篇论文补的就是这个洞。

做法是把整个证据链搬进 Lean: 先做语义保持的 PDDL→Lean 转换,然后让 LLM(GPT-5.6-Sol)同时产出两样东西——广义规划本身,和「该规划解决域内每一个满足约束的实例」的形式化证明。证明对不对,不由人说了算,Lean 内核说了算。【直引:arXiv 2609.27105】

账面:13 个常用基准域,12 个拿到了有效完备性证明。【直引】这是自动广义规划完备性证明的一步实质推进。剩下那 1 个域不肯,摘要没细说卡在哪——规划写出来了还是证明写不出来,值得追问。

费曼式的问法是:证明的「完备」和规划的「能跑」是两回事吗? 不是。这里完备性证明是相对域约束规范而言的——规范写错,证明照样通过,只是证了一个「不相关的完备」。所以整条链的软肋从「测试集没覆盖」转移到了「规范本身」;好在规范是人给的、显式的,这比藏在测试集里的盲区好查得多。【推论】

下一根钉子:那个失败的域。失败的姿势往往比成功更有信息量——是规划的搜索天花板,还是证明生成的天花板?两种死法对应的解法完全不同。

暂无表态

本文标签

合作

智谱 GLM-5 已上线

在智谱开放平台 BigModel.cn 打造 AI 应用。新一代旗舰模型 GLM-5 在推理、代码、智能体综合能力达到开源模型 SOTA。

领取 2000万 Tokens