PDDL规划中的实例生成器生成

# PDDL规划中的实例生成器生成
来源：https://arxiv.org/html/2609.06071
Naya Rudolph Katharina Stein Jörg Hoffmann Ayal Taitler Timo P. Gros

###### 摘要

PDDL是AI规划社区中事实上的标准语言，旨在规范规划领域：共享相同谓词和操作模式的一组实例。然而，它并未提供任何指定实际实例集的方法，即对初始状态和目标条件的合法性约束，以及可能指定我们感兴趣的实例子集的领域子集约束。由此产生的一个后果是，实例生成一直是临时性的，采用手动编写的针对特定领域和子集的实例生成器。近期工作已开始解决这个问题，通过推理和学习方法，但这些方法存在可扩展性限制。本文引入了一种替代方法，利用大语言模型生成实例生成程序，并通过规定检查内置健全性保证。我们证明这些自动生成的实例生成器能高效返回大量健全且多样的实例。

¹德国人工智能研究中心（DFKI），德国萨尔布吕肯
²萨尔大学，萨尔信息学园，德国萨尔布吕肯
³可信人工智能欧洲研究中心（CERTAIN）
⁴内盖夫本-古里安大学

{Nicola.Mueller, Naya.Rudolph, Timo_Phillip.Gros}@dfki.de, [email protected], [email protected], [email protected]

规划领域定义语言PDDL是AI规划社区的事实上的标准语言（McDermott 2000 (https://arxiv.org/html/2609.06071#bib.bib27); Bacchus 2000 (https://arxiv.org/html/2609.06071#bib.bib28); Long and Fox 2003 (https://arxiv.org/html/2609.06071#bib.bib26); Hoffmann and Edelkamp 2005 (https://arxiv.org/html/2609.06071#bib.bib25); Gerevini et al. 2009 (https://arxiv.org/html/2609.06071#bib.bib24); Haslum et al. 2019 (https://arxiv.org/html/2609.06071#bib.bib23)）。PDDL旨在规范规划*领域*：通常是共享相同谓词和操作模式的无限实例集。然而，PDDL并未提供任何指定预期实例集的方法。

首先，在大多数领域中，并非所有可能的实例都定义了合法的初始状态或目标条件。例如，在积木世界（Blocksworld）领域中，一个积木不能位于自身之上；在运输领域中，一辆卡车必须恰好位于一个地点等。其次，在许多情况下，我们实际上只对合法领域实例的一个子集感兴趣；例如，我们可能希望目标是所有积木堆成一个单一塔，或者我们可能只希望为包裹指定目标地点，而不为卡车指定。我们将前者称为*合法性约束*，后者称为*子集约束*。文献中通常未区分这两者。这纯粹是概念上的区分，因为两者都是对初始状态、目标及其组合的约束。然而，这种区分在实践中是有意义的，因为合法性约束在每个领域中是固定的，而子集约束可能根据目的而变化。

由于PDDL缺乏用于此类约束的规范语言，过去的实例生成方法大多是临时性的。研究人员手动编写实例生成器，这些针对特定领域的程序生成领域实例的某个子集，其潜在的合法性约束和子集约束隐含在代码中。这种不透明性长期以来一直是识别领域实际定义方式的障碍，在对领域进行断言时，需要诸如“由生成器X可生成的实例集”这样的陈述（例如（Helmert 2003 (https://arxiv.org/html/2609.06071#bib.bib22); Hoffmann 2005 (https://arxiv.org/html/2609.06071#bib.bib21); Stein et al. 2026 (https://arxiv.org/html/2609.06071#bib.bib13)））。缺乏更通用的方法也意味着，为了适应新的领域或实例子集，需要艰苦地实现新的实例生成器。

Haslum和Scholz (2003) (https://arxiv.org/html/2609.06071#bib.bib20) 的工作是解决此问题的早期尝试，他们提出了一种允许指定状态不变量等特性的语言。然而，该语言从未被社区采用。后来，Fuentetaja和De la Rosa (2012) (https://arxiv.org/html/2609.06071#bib.bib18) 引入了第一个与领域无关的实例生成方法，包括一种用于指定合法性约束的语言，其实例生成被表述为一个规划问题。但该合法性语言受限（每个约束仅针对单个谓词），并且未发表任何实验。¹¹¹更多关于自动化实例生成的工作已在特定领域内进行，自动调整实例规模/难度以适应需求，例如用于学习目的或规划竞赛（例如（Fern et al. 2004 (https://arxiv.org/html/2609.06071#bib.bib19); Marom and Rosman 2020 (https://arxiv.org/html/2609.06071#bib.bib17); Torralba et al. 2021 (https://arxiv.org/html/2609.06071#bib.bib11)））。

最近，两种新方法解决了与领域无关的实例生成问题。Grundke et al. (2025) (https://arxiv.org/html/2609.06071#bib.bib9) 将合法性约束规范为PDDL公理，并使用答案集编程（ASP）自动生成实例。Núñez-Molina et al. (2024) (https://arxiv.org/html/2609.06071#bib.bib10); Núñez-Molina et al. (2025) (https://arxiv.org/html/2609.06071#bib.bib7) 将生成多样且困难实例的问题表述为马尔可夫决策过程，并使用深度强化学习（RL）训练生成初始状态和目标的策略。尽管这些工作取得了重大进展，但两种方法的弱点都是可扩展性限制。答案集编程在最坏情况下，其复杂度随生成实例的规模呈指数级增长，因此在实践中很快达到其计算极限。RL在实践中需要为每个领域子集进行数天的训练时间；并且学习到的实例生成策略必须能够从小型训练实例泛化到我们期望生成的大型实例，这具有挑战性。

在本文中，我们引入了一种替代方法，利用大语言模型生成Python实例生成程序。这些自动生成的Python程序针对特定领域和预期的实例子集，并且往往效率很高。生成实例的健全性通过一个规定的后处理程序来保证，该程序检查合法性约束和子集约束。合法性约束由用户*每个领域只需实现一次*，形式为Python测试，支持高效检查。对于子集约束，我们支持使用一阶逻辑进行声明式规范，便于修改和维护。给定这些输入，我们提示LLM生成一个作为独立Python模块的实例生成器。然后我们通过一个调试循环来改进该模块（大致遵循为按领域规划器生成提出的思想（Silver et al. 2024 (https://arxiv.org/html/2609.06071#bib.bib14)））。我们测试该实例生成器在多种规模下生成大量实例，验证它们是否满足约束。结果作为调试提示的一部分反馈给LLM，循环重复。经过几次迭代后，我们返回一个平衡实例健全性与多样性的生成器（后者灵感来源于Núñez-Molina et al. (2024) (https://arxiv.org/html/2609.06071#bib.bib10); Núñez-Molina et al. (2025) (https://arxiv.org/html/2609.06071#bib.bib7)）。在部署时，后处理程序保证只返回健全的实例。

我们通过实验证明，我们的方法能在几分钟内生成健全且多样的实例生成器。此外，我们证明，所生成的实例生成器比Grundke et al. (2025) (https://arxiv.org/html/2609.06071#bib.bib9) 和Núñez-Molina et al. (2024) (https://arxiv.org/html/2609.06071#bib.bib10); Núñez-Molina et al. (2025) (https://arxiv.org/html/2609.06071#bib.bib7) 的方法能更高效地生成大量实例。

此外，我们进行了一个案例研究，旨在评估广义规划方法的实例生成，该方法试图计算能跨领域所有合法实例泛化的规划（Bonet et al. 2019 (https://arxiv.org/html/2609.06071#bib.bib16); Ståhlberg et al. 2022 (https://arxiv.org/html/2609.06071#bib.bib15); Ståhlberg and Geffner 2026 (https://arxiv.org/html/2609.06071#bib.bib6); Silver et al. 2024 (https://arxiv.org/html/2609.06071#bib.bib14); Stein et al. 2026 (https://arxiv.org/html/2609.06071#bib.bib13)）。广义规划往往在泛化能力上有所不同，特别是它们有效作用的*实例子集*。我们的方法首次允许在无需大量手动编码工作或生成器学习的情况下，高效评估这些方面。我们的案例研究展示了如何通过这种方式获得有趣的见解。

## 1背景

我们简要概述PDDL规划以及与领域无关的实例生成的相关工作。

#### PDDL规划\.
规划领域定义语言（PDDL）是规划问题的提升表示，问题由领域D和问题实例I组成（Haslum et al. 2019 (https://arxiv.org/html/2609.06071#bib.bib23)）。领域D定义了一组谓词P∈𝒫和一组操作模式A∈𝒜，它们定义了参数、前提条件、效果和操作代价。实例I定义了一组对象o∈𝒪、一个初始状态Init和目标条件𝒢 grounding D中的谓词和操作模式与I中的对象，我们得到一个问题⟨S, s₀, S_𝒢, Act, f⟩，它包含一组状态s∈S、初始状态s₀、目标状态集合S_𝒢、每个状态s的适用ground动作集合Act(s)以及转换函数f: S × Act → S（Ghallab et al. 2004 (https://arxiv.org/html/2609.06071#bib.bib3)）。实例I的一个规划是一个ground动作序列→a = ⟨a₀, ..., a_T₋₁⟩，它将初始状态s₀转移到目标状态s_T ∈ S_𝒢。

#### 相关工作\.
Grundke et al. (2025) (https://arxiv.org/html/2609.06071#bib.bib9) 提出了一种与领域无关的实例生成方法，该方法基于PDDL领域的形式化规范，这些规范使用公理来刻画合法的初始状态和目标。我们将此方法称为“Gr25”。给定所需的对象数量，Gr25将形式化领域规范翻译成答案集程序（ASP），其答案集对应于合法的规划实例。然后使用现成的ASP求解器来计算一组答案集，对应于合法实例。

Núñez-Molina et al. (2024) (https://arxiv.org/html/2609.06071#bib.bib10) 的NeSIG方法将实例生成表述为一个序贯决策问题，并学习独立的强化学习策略来构建初始状态和目标。在每一步，策略向部分生成的实例添加一个对象或事实，或者终止相应的生成阶段。在此过程中，用户提供的规则检查实例的初始状态是否合法。NeSIG的奖励函数鼓励策略构建合法、多样且困难的实例。为计算多样性，NeSIG为每个构建的实例计算一组特征，然后计算这些特征向量之间的距离。为计算难度，NeSIG在构建的问题上运行一组现有规划器，并测量扩展的搜索节点数。

## 2实例生成器的生成

我们现在介绍在PDDL规划中生成实例生成器的方法，我们称之为I2G（InstanceGeneratorGeneration）。我们的方法包括四个步骤：首先，我们提示LLM生成一个实例生成器。其次，我们测试生成的实例生成器。第三，基于测试结果，我们提示LLM改进其生成器并返回第二步。最后，经过多次改进迭代后，我们选择平衡健全性和多样性的生成器作为最终生成器。

### 2\.1大语言模型提示

为了生成初始实例生成器，我们使用三个输入构建LLM提示：一个PDDL领域文件、作为Python测试实现的合法性约束，以及作为一阶逻辑（FOL）公式指定的子集约束。

#### 合法性约束\.
合法性约束只需要为每个领域定义一次。因此，我们将它们实现为Python测试，以实现高效的合法性验证。这也允许用户实现信息丰富的错误消息和支持LLM代码生成的可重用代码工具。I2G要求合法性约束以独立的Python脚本形式提供，其中包含一个verifyLegality方法，该方法输入一个实例文件，返回一个布尔值和一个可选的错误消息列表。

#### 子集约束\.
子集约束根据实际设置进行选择，因此经常更改，甚至可能自动计算。因此，我们使用FOL公式对其进行声明式指定。I2G要求子集约束以类似PDDL的语法提供的公式列表形式提供，该语法支持标准的FOL运算符，如全称量化和存在量化、异或（XOR）和等式。此外，我们支持传递闭包和整数算术。如果谓词引用初始状态或目标条件，则必须分别以“I”或“G”为后缀。以“G”为后缀的谓词是新的谓词符号，表示与初始状态谓词并存的目标事实。其真值由目标条件中列出的正ground原子推导得出，按照封闭世界假设解释。例如，在积木世界领域中，子集约束“初始状态中所有积木必须在桌子上，目标中所有积木必须在一个单一塔中”可以指定为：
`forall(?b-block) on-table_initial(?b)`
`exists(?b1-block) and clear_goal(?b1) forall(?b2-block) implies clear_goal(?b2) = ?b1 ?b2`。

I2G还支持引入以“new”为后缀的新辅助谓词，以便更轻松地定义子集约束。这些谓词是语法糖，并且明确告知LLM它们在生成的实例中绝不能出现。此外，I2G支持在开放世界假设下定义和验证目标条件上的子集约束，这适用于目标不是正ground原子合取的领域。

#### 提示\.
给定PDDL文件、合法性约束和子集约束，我们提示LLM实现一个独立的Python模块，该模块能高效生成满足合法性和子集约束的多样实例。该实例生成器必须由一个具有预定义名称的单个类组成，并且必须公开一个generateInstanceForSize方法，该方法输入一个实例大小（即非常量对象的数量）和一个可选的随机种子，返回一个字符串（对应于实例文件）或None（当不存在所请求大小的实例时）。例如，在某些领域中，t