启发式搜索的广义规划|启发式搜索|广义规划|指针|算法|轨迹|隐式

Generalized planning as heuristic search: A new planning search-space that leverages pointers over objects

作为启发式搜索的广义规划:一个新的规划搜索空间，利用对象上的指针

https://github.com/jsego/bfgp-pp

https://www.sciencedirect.com/science/article/pii/S000437022400033X

摘要

启发式搜索规划是经典规划中最成功的方法之一，但不幸的是，它不能直接扩展到广义规划（GP）；GP旨在计算算法解决方案，这些解决方案对于给定域中的一组经典规划实例有效，即使这些实例在对象数量、初始和目标配置以及状态变量的数量（和可能的值）上有所不同。状态空间搜索，正如启发式规划器所实现的那样，对于GP变得不切实际。在本文中，我们将启发式搜索规划范式适应GP的泛化需求，并提出了第一个GP的启发式搜索方法。首先，本文介绍了一种新的基于指针的GP解决方案空间，该空间独立于GP问题中的经典规划实例数量及其大小（即对象数量、状态变量及其域大小）。其次，本文定义了我们GP算法的升级版本，称为最佳优先广义规划（BFGP），它在我们的基于指针的GP解决方案空间中实现最佳优先搜索。最后，本文为BFGP定义了一组评估和启发式函数，用于评估候选GP解决方案的结构复杂性及其对给定输入经典规划实例集的适应性。这些评估和启发式函数的计算不需要提前接地状态或动作。因此，我们的启发式搜索GP方法可以处理具有大数值域的大量状态变量，例如整数。

关键词：广义规划经典规划启发式搜索规划与学习领域特定控制知识程序综合示例编程

（完整内容请参考原论文）

引言

自动规划（AP）是一种基于模型的自主系统控制方法。更详细地说，AP探索基于模型的计算，以生成在各种领域中完成定义目标的动作序列（也称为计划）。在AP中，计划通常是通过考虑一个模型生成的，该模型包括初始条件、可用动作和要完成的目标。有各种各样的AP模型处理部分状态可观察性、非确定性状态转换、持续动作或时间扩展目标[1,2]。经典规划是最简单的AP模型，它假设系统动态可以建模为有限、确定性和完全可观察的转换系统。在这种转换系统中，经典规划研究能够将初始状态转换为满足一组给定目标的状态的动作序列的综合。

我们使用积木世界（blocksworld）来说明经典规划问题的概念，这是一个流行的经典规划领域，由一组积木、一张桌子和一只机械手组成[3]。机械手可以是空的或拿着一块积木，一块积木可以在另一块积木的顶部或在桌子上。通过改变积木的数量及其初始或目标配置，可以在积木世界中定义不同的经典规划问题。一个著名的积木世界问题，因为它小但非平凡，是Sussman异常[4]（图1中最左边的问题）；在Sussman异常中，有三块积木，我们标记为0、1和2。最初，积木1在桌子上，2在0的顶部，0在桌子上，目标是堆叠这三块积木，使得0在1的顶部，而1在2的顶部。图1显示了积木世界的三个不同的经典规划问题。每个问题有不同数量的积木。该图显示了每个问题的初始状态（左侧）和目标（右侧）的积木配置。最左边的经典规划问题对应于Sussman异常问题。

启发式搜索是经典规划中最成功的方法之一[5–8]。国际规划竞赛的获胜者通常是启发式规划器[9]，启发式和领域独立规划搜索研讨会是国际规划与调度会议（ICAPS）上最具传统的讨论论坛之一，ICAPS是AP研究的主要会议。简而言之，启发式搜索规划方法将顺序计划的合成视为从初始状态可达的状态空间中的组合搜索。这种组合搜索通常实现为前向搜索，由从规划问题表示中自动提取的启发式方法引导。在过去的十年中，已经开发了广泛的有效的搜索算法和启发式函数用于经典规划[10–14]。大多数这些启发式搜索技术基于松弛计划的概念，这是经典规划问题松弛的解决方案；松弛计划的成本是许多不同经典规划问题的实际成本的廉价且信息丰富的估计。

广义规划（GP）解决了从给定域中的一组经典规划实例中表示和计算有效解决方案的问题[15–24]。在最坏的情况下，每个经典规划实例可能需要完全不同的解决方案，但在实践中，许多经典规划领域已知具有算法解决方案[25,26]。换句话说，可以计算一个单一的紧凑通用解决方案，该解决方案利用了给定域中不同经典规划实例的某些共同结构。广义计划是算法解决方案，它们通过控制流补充规划动作序列。例如，一个解决积木世界域中任何经典规划实例的广义计划，无论实际的积木数量或身份如何，也无论积木的初始和目标配置如何，都可以紧凑地指定如下：“将所有积木放在桌子上，然后以适当的顺序将每个积木移动到其目标位置”。

不幸的是，经典规划中的搜索算法和启发式函数不能直接应用于GP。现成的启发式规划器实现的松弛计划的计算需要预处理步骤来接地状态和动作。另一方面，GP解决方案必须能够泛化到（可能是无限的）一组经典规划实例，这些实例具有不同的对象集（即具有不同域大小和/或不同数量的状态变量）以及对象的不同初始状态和目标配置。GP的这些特定泛化要求使其不切实际地接地状态和动作，因此无法直接应用启发式规划器的状态空间搜索或成本估计。

更重要的是，给定的一组经典规划实例中表示的知识可能不足以指定解决它们的算法解决方案。例如，积木世界的经典规划实例不包括明确指定“所有积木都在桌子上”或指定“将积木移动到其目标位置的适当顺序”的表示特征。GP的一个关键挑战是，给定一组规划实例，自动发现计算这些实例的紧凑通用解决方案所需的表示特征。

由于广义计划的算法性质，GP是一个有前途的研究方向，有助于弥合自动规划和编程之间的当前差距[27]。不幸的是，大多数GP工作继承了STRIPS表示，其中状态仅使用布尔变量（即指定世界对象属性和关系的命题）表示，状态转换对应于对象操作的动作。在这项工作中，我们为GP问题和解决方案引入了一种新的基于指针的表示，使我们能够将启发式搜索规划范式适应GP。我们的基于指针的表示更接近Python、C++或Java等常见编程语言，同时它也自然适用于AP社区传统上处理的STRIPS问题。给定一个由给定域中的一组有限经典规划实例组成的GP问题，我们的启发式搜索GP方法实现了一个组合搜索，以合成一个解决整个输入实例集的程序。与以前的工作相比，我们的启发式搜索GP方法引入了以下贡献：

1. 基于指针的GP问题和解决方案表示我们的表示形式更接近常见编程语言，同时它也适用于AP中传统使用的以对象为中心的表示（STRIPS）。

2. 可处理的GP解决方案空间我们利用随机存取机[28]和Intel x86 FLAGS寄存器[29]的计算模型，为GP定义了一个紧凑且通用的解决方案搜索空间。值得注意的是，我们新的GP搜索空间独立于GP问题中的输入规划实例数量及其大小（即对象数量、状态变量及其域大小）。

3. 具有无接地评估/启发式函数的GP启发式搜索算法我们介绍了BFGP算法，该算法在我们的GP解决方案空间中实现最佳优先搜索。我们还为指导BFGP定义了评估和启发式函数。这些函数评估候选GP解决方案的结构复杂性及其对输入经典规划实例集的适应性。评估这些函数不需要提前接地状态/动作，因此它们适用于状态变量具有大域（例如整数）的GP问题。

4. 从PDDL的STRIPS片段到我们基于指针的GP表示的翻译器我们自动化了从PDDL到基于指针的表示的转换，并展示了国际规划竞赛[30]中几个规划领域的解决方案，这些解决方案在大型随机实例上得到了验证。

我们启发式搜索GP方法的初步描述之前作为ICAPS和IJCAI会议论文[31,32]出现。在这项工作中，我们扩展了会议论文中提出的开创性思想，并提供了对我们启发式搜索GP方法的更全面评估。与会议论文相比，本文包括以下新内容：

- 我们形式化了规划问题对象集上的指针概念，并引入了状态、状态约束和规划动作方案的基于指针的形式化。我们还引入了经典规划问题及其解决方案的基于指针的形式化。我们展示了我们的基于指针的形式化自然适用于AP中传统处理的STRIPS规划任务。

- 我们引入了部分指定的规划程序的概念，指的是算法规划解决方案的草图，并使我们能够更好地形式化我们的GP搜索算法和启发式函数。

- 我们提供了我们GP启发式搜索算法的新理论结果，包括终止、健全性、完整性和复杂性证明。我们还为指导我们的启发式搜索GP方法实现了新的评估函数，并扩展了实证评估，包括更多在更广泛规划领域的结果，以更好地表征我们启发式搜索GP方法的性能。

本文结构如下：第2节回顾了与规划中计算策略和泛化相关的先前研究工作，并指出了与我们方法的主要差异。第3节提供了我们在本工作中依赖的规划模型（即经典规划模型和GP模型），并介绍了我们用于GP解决方案表示的形式化（即规划程序和随机存取机）。第4节展示了如何通过一组对象上的指针扩展经典规划模型，以及用于操作这些指针的相应基本操作。这种扩展使我们能够以不可知的方式定义一组特征和一组用于计算GP解决方案的动作，这些解决方案可以解决给定规划域中的任何实例。第5节描述了我们的启发式搜索GP方法；该节提供了有关我们的解决方案空间、评估函数和GP启发式搜索算法的详细信息。第6节介绍了我们启发式搜索GP方法的实证评估，并与作为基线的经典规划编译进行了比较。最后，第7节总结了我们的工作，并讨论了开放问题和未来工作。

2. 相关工作

在这里，我们首先根据以下三个维度回顾GP的先前工作：问题表示、解决方案表示和计算方法。然后，我们将GP的研究工作与其他相关的人工智能领域联系起来，如程序综合、深度学习和（深度）强化学习。最后，我们讨论了我们的启发式搜索GP方法与回顾的相关工作的区别。

关于问题表示，有两种不同的方法来指定GP问题中包含的一组经典规划实例。显式方法，枚举GP问题中的每个经典规划实例[33]，和隐式方法，定义GP问题的一组经典规划实例所满足的约束。隐式方法是有趣的，因为它可以紧凑地指定无限的经典规划实例集（例如，属于积木世界域的无限经典规划实例集）[34,35,20]。除了经典规划实例集之外，还可以指定额外的背景知识，以减少GP解决方案的空间。例如，计划轨迹演示如何解决一些输入实例[36–38]，完整状态空间[22]，可以用于计算广义计划的状态特征的特定子集[39,40]，指定目标GP解决方案的不期望行为的负例[41,22]，或任何给定域中的状态必须满足的状态不变量[42]。

关于解决方案表示，AP文献中出现了不同的形式化来表示对一组经典规划实例有效的解决方案；顺序计划用于一致性规划[43,44]，条件树状计划用于偶然性规划[45,2]，或策略用于FOND规划以及MDP/POMDP规划[46]。在所有这些规划设置中，具有不同初始状态的不同经典规划实例集可以隐式表示为状态变量的析取公式。不同的目标也可以通过将它们编码为状态表示的一部分来考虑，例如使用静态状态变量[33]。此外，GP中的特征概念与POMDP形式化中的状态观察概念相关，其中观察取决于当前状态和刚刚采取的动作[47]。在这方面，可以理解GP求解器同时计算广义计划和观察函数，该函数有助于紧凑地表示广义计划。GP中的特征概念也与定性数值规划[48,49,20]相关，后者利用命题来抽象数值状态变量的值。

AP与编程表示的联系并不是我们GP方法所独有的；提出了不同种类的程序作为传统规划动作语言的替代方案[50–52,27]。GOLOG程序也被用来表示可以分支和循环的规划解决方案，并且可以包含非确定性部分[53]。此外，GOLOG和PDDL之间的语义兼容性可以被利用，并且可以将PDDL规划器嵌入[54]以解决本质上组合的子问题。自AI早期以来，层次结构、LTL公式和策略也被用来指定一般规划解决方案的草图[55]。在AP文献中，这些解决方案草图通常被称为领域特定控制知识，因为它们传统上用于控制规划过程，并且适用于属于给定域的整个经典规划实例集[56,57,36,37]。最后但并非最不重要的是，算法解决方案，表示为提升策略、有限自动机或带有控制流构造的程序，用于表示GP解决方案[34,58,39,59–61,15,33,21,24]。

关于广义计划的计算，GP有两种主要方法。自顶向下/离线方法将给定GP问题中的整个经典规划实例集视为一个批次，并一次性计算对该完整批次有效的解决方案计划。离线计算广义计划的常见方法是编译GP问题为另一种问题求解形式，并使用现成的求解器来解决编译问题。例如，GP问题已被编译为经典规划问题[61,33]、一致性规划问题[39]、LTL综合问题[62]、FOND规划问题[63,20]、MAXSAT问题[22]或ASP问题[64]。编译方法很有吸引力，因为它利用了其他有坚实基础的科学社区的最新进展，这些社区有强大且可扩展的求解器。此外，这些任务的计算复杂性在理论上根据输入问题的结构特征进行了表征，这可能为所解决的GP问题的难度提供见解。然而，编译方法的一个弱点是编译问题的规模；求解器通常对输入问题的规模敏感。另一方面，自底向上/在线方法增量地处理GP问题中的一组经典规划实例[15,17,65]。给定一个经典规划实例，计算该实例的解决方案，然后，将该解决方案与为先前实例计算的解决方案合并。因此，在线方法对于处理包含大量经典规划实例的GP问题很有吸引力。在线方法的主要缺点是处理GP问题中不同经典规划实例的单独处理产生的过拟合。

正如GP的先前工作所指出的，GP的目标与程序综合[33,20,62,31]有关。程序综合是计算机辅助验证社区传统上研究的任务[66]，其目标是计算满足给定正确性规范的程序[67–69]。程序综合遵循函数式编程范式。这意味着程序是函数组合，其中组合中的每个函数将其输入参数映射到单个输出，并且循环通过递归实现。程序综合的工作根据程序的正确性规范的制定方式进行分类。通过示例编程（PbE）范式使用有限且非空的地面输入/输出示例集来指定所需程序行为。这种方法与GP问题的显式表示相关；地面输入/输出示例可以理解为表示经典规划实例的初始/目标状态对，函数式编程语言的指令集可以理解为将初始状态转换为目标状态的可用动作。程序综合还允许隐式表示输入正确性规范，例如使用SMTLIB中指定的第一阶公式，这是SAT-Modulo理论（SMT）的正式语言[70]。程序综合的主流方法是指定一个形式语法，该语法增量地枚举可能程序的空间，并利用SMT求解器的可满足性机制来验证候选程序是否实际上是解决方案[71]。在这方面，定理证明的工作也与程序综合相关，特别是因为SMT求解器允许表示和满足一阶逻辑公式[72]。最后，程序综合的另一个流行趋势是草图编程，它解决了在提供部分指定解决方案作为输入的特定设置中的程序综合[73]。

除了形式验证和逻辑满足的计算方法外，优化方法（在机器学习中占主导地位[74]）也已应用于计算泛化的规划解决方案。例如，现成的深度学习（DL）工具已成功应用于计算经典和概率规划领域的广义策略[75–77]。广义策略是一种强大的解决方案表示形式化，其适用性超越了经典规划；广义策略可以表示处理非确定性动作的规划解决方案[78]。此外，广义策略可以表示目标不是满足给定目标条件而是优化给定效用函数的规划问题的解决方案[79]。GP的目标也与强化学习（RL）[80]相关；虽然上述DL方法可以被视为GP的离线优化方法，但RL范式可以被视为GP的在线优化方法。RL方法通过迭代解决一组顺序决策制作集来增量计算策略。然而，RL中的学习经验不是事先给出的（学习经验是通过状态空间的自主探索收集的），并且RL假设存在明确的奖励函数概念（这有助于引导探索到状态空间中最有希望的部分）。请注意，DL和DRL方法学习策略，而不需要状态和动作空间的符号表示。这意味着可以计算从原始传感器数据（例如图像序列）泛化的（深度）策略[81,82]。计算表示为深度策略的解决方案的主要缺点是它们是缺乏透明度和解释能力的黑箱模型，这使得解释生成的解决方案变得困难。这是在需要人在回路的应用领域（如健康、法律或国防）中的一个强烈要求[83]。

关于回顾的相关工作，我们的启发式规划GP方法如下：

- 数值状态变量。GP的先前工作主要遵循以对象为中心的STRIPS表示。使用这种表示处理编程任务是不切实际的，因为它可能需要将状态变量域中的所有值编码为对象。其他方法，如定性数值规划（QNP）[48,49]，使用命题定性地处理大数值状态变量，以表示变量是否等于零。在这项工作中，我们处理具有整数状态变量的GP问题，这使得自然地处理各种编程任务，就好像它们是GP问题一样。

- 显式问题表示。在这项工作中，GP问题包含要解决的有限经典规划实例的显式枚举。有趣的是，我们的实验结果表明，在几个领域中，解决一小部分随机生成的经典规划实例足以获得泛化到属于给定域的无限问题集的解决方案。

- 无背景知识。我们的方法不需要任何额外帮助，如状态不变量、计划/轨迹/演示、负例或广义计划中出现的特征子集的指定。在这方面，我们利用随机存取机[28]和Intel x86 FLAGS寄存器[29]的计算模型，生成一个与给定域的不同经典规划实例共享的无知状态特征集（无论它们的实际对象数量如何）。

- 广义计划表示为结构化程序。结构化编程提供了一个广泛流行的白盒建模范式。在这项工作中，我们关注表示为结构化程序的广义计划，具有用于分支和循环程序执行流的控制流构造。然后，广义计划在特定经典规划实例上的应用是一个确定性的无匹配过程，这使得定义有效的评估和启发式函数更容易。此外，结构化程序的渐近复杂性可以从其结构评估，这有助于在可能的广义计划之间建立偏好。

- 离线可满足性方法。这项工作遵循GP的离线方法，旨在一次性计算解决作为输入给出的所有经典规划实例的广义计划。由于许多启发式搜索算法很容易扩展到在线版本，我们相信我们的启发式搜索GP方法是迈向可以处理更大经典规划实例集的在线方法的垫脚石。

- GP的原生启发式搜索。通过原生启发式搜索，我们指的是我们定义了一个搜索空间、评估/启发式函数和一个专门针对GP的搜索算法。我们的启发式搜索GP方法与现有的经典规划编译GP[33]相关。然而，我们的方法克服了编译的主要缺点，即搜索空间随状态变量的数量和域大小呈指数增长；在实践中，这一缺点限制了编译对小规模规划实例的适用性，因为现成的经典规划器的性能对输入实例的大小敏感。我们的实验支持这一说法，并表明与经典规划编译GP方法[33]相比，我们的BFGP算法显著减少了计算和验证广义计划所需的CPU时间。

3.1 经典规划

我们对经典规划模型的形式化类似于称为有限函数规划的抽象规划框架，该框架是为规划语言的理论分析而引入的[84]。设是一组状态变量，其中每个变量 ∈ 有一个域。命题是一个状态变量 ∈ ，其域 = {0, 1}，其中 = 0和 = 1分别解释为和赋值。状态是状态变量集的值的总赋值，即 = ⟨0 = 0,…, = ⟩，使得∀0≤≤ ∈ ，其中是中的状态变量数量。对于状态变量的子集′ ⊆ ，设[′] = ×∈′表示其联合域。状态空间表示为 = []。给定一个状态 ∈ 和变量子集′ ⊆ ，设|′ = ⟨ = ⟩∈′是在′上的投影，即由赋值给′中状态变量的值定义的部分状态。在′上的投影定义了与相应部分状态一致的状态子集{ ∣ ∈ , |′ ⊆ }。最后，让我们定义一个状态约束为一个布尔函数 ∶ → {0, 1}，它隐式定义了与该约束一致的状态子集 ⊆ 。

设是一组确定性动作，使得每个动作 ∈ 由两个函数表征；适用性函数 ∶ → {0, 1}和后继函数 ∶ → 。一个动作 ∈ 在给定状态 ∈ 中适用当且仅当() = 1。在状态 ∈ 中执行适用动作 ∈ 的结果是后继状态′ = ()。请注意，这种确定性动作的定义概括了具有条件效果的动作[85]，这在GP中很常见，因为它们的状态依赖结果允许广义计划适应不同的经典规划实例。

一个经典规划实例是一个元组 = ⟨, , , ⟩，其中是一组状态变量，是一组动作， ∈ 是一个初始状态，是对状态变量值的约束，它诱导了目标状态子集 = { ∣ ⊨ , ∈ }。给定一个经典规划实例，一个计划是一个动作序列 = ⟨1,…, ⟩，其执行诱导轨迹 = ⟨0, 1, 1,…, , ⟩，使得对于每个1 ≤ ≤ ，在−1中适用并导致后继状态 =

(−1)。计划解决当且仅当在0中执行，其中0 = ，结束于目标状态，即 ∈ 。

规划语言，如PDDL[86]，可以使用一组有限函数和动作方案紧凑地表示给定域的无限经典规划实例集。给定一组有限对象Ω和一组定义在这些对象上的有限函数Φ，我们假设每个状态变量 ∈ 代表一个函数解释 ≡ (⃖⃗)，其中 ∈ Φ是一个具有arity ()的函数，⃖⃗ ∈ Ω()是Ω()的笛卡尔积空间中包含的对象向量；对象和函数签名可以被类型化，因此可能的函数解释的数量受到限制。Φ中的函数可以是布尔值，例如表示PDDL谓词，或者是数值，例如表示PDDL数值流体。同样，给定一组动作方案Ξ，我们假设每个动作 ∈ 是通过用Ω中的对象替换动作方案中的每个变量从动作方案 ∈ Ξ构建的。动作方案 ∈ Ξ是一个元组 = ⟨(), (), (), eff ()⟩，其中：

- ()是动作方案的标识符，

- ()是自由变量的列表，这些变量也可以被类型化，因此它们只能被相同类型的对象替换，

- ()是布尔公式的合取，其中每个公式是两个函数符号1,2 ∈ Φ之间的逻辑评估，即==, <, >, ≤, ≥，定义在()上，或者是定义在()上的函数符号和值，它紧凑地表示相应接地动作适用的状态子集，

- eff()是一组逻辑赋值，其中每个函数符号从另一个函数符号′（都定义在()上）或常数值获取值，它紧凑地表示由相应接地动作的应用引起的状态变量的更新。

3.2 广义规划

广义规划是一个总称，指的是更一般的规划概念[21]。这项工作建立在GP的归纳形式化之上，其中GP问题是一个属于同一域的有限经典规划实例集[19,62]。

定义1（GP问题）。一个GP问题是一个非空集 = {1,…, }，包含来自给定域的个经典规划实例。

每个实例 ∈ ，1 ≤ ≤ ，实际上可能在状态变量集、动作集、初始状态和目标上有所不同，但相应的状态变量集是从公共函数集Φ诱导的。同样，动作集是从公共动作方案集Ξ诱导的，当在实例的特定对象集Ω上接地时。

GP的目标是计算算法规划解决方案，即广义计划，这些解决方案适用于整个输入规划问题集。GP解决方案有多种表示形式，从广义策略[34,58]到有限状态控制器[39,59]、形式语法[60]、层次结构[87,61]或程序[15,33]。每种表示形式都有其自身的表达能力、验证复杂性和计算复杂性。尽管存在这种表示多样性，我们可以定义一个共同条件，在该条件下，广义计划被认为是GP问题的解决方案。

示例。图2显示了两个经典规划实例的初始状态和目标，1 = ⟨, , 1, 1⟩和2 = ⟨, , 2, 2⟩，用于排序两个六元素列表。在这个特定示例中，两个实例共享相同的状态变量集 = { ≡ ()|0 ≤ ≤ 5}，该集合由一元函数Φ = {}和对象集Ω1 = Ω2 = {0,…, 5}构建，其中∀∈ = 0。两个经典规划实例还共享确定性动作集，具有6×5/2个动作(, )，它们交换两个列表位置 < 的内容，并由单个动作方案Ξ = {(, )}诱导。1的一个示例解决方案计划是1 = ⟨(0, 5), (1, 2), (1, 3)⟩，而2 = ⟨(0, 2), (3, 5)⟩是解决2的顺序计划示例。请注意， = {1,2}是一个GP问题，因为它包含两个使用相同函数集Φ和动作方案Ξ构建的经典规划实例。图3显示了一个解决的广义计划示例，该计划表示为排序网络[88]。排序网络使用两种不同类型的项目（即线和比较器）进行说明。对于每个状态变量，有一条线从左到右在网络中携带该变量的值。另一方面，比较器连接两条不同的线，对应于一对变量(, )，使得 < 。当一对值通过一对线(,)时，遇到比较器，则比较器应用动作(, )当且仅当() ≥ ()，即 ≥ 。图3的排序网络实际上可以解决任何排序任何六元素列表内容的实例，无论其初始内容如何。然而，该解决方案对于不同长度的列表排序无效。在本文中，我们将展示如何表示和计算利用间接内存寻址的规划解决方案，以泛化无论对象数量和相应状态变量如何。

3.3 规划程序

在这项工作中，我们将规划解决方案表示为规划程序[33]。与顺序计划不同，规划程序包括一个控制流构造，允许紧凑地表示经典和GP问题的解决方案。形式上，规划程序Π是一个包含条指令的序列，其中每条指令Π[]与程序行0 ≤ < 相关联，并且它要么是：

- 规划动作Π[] ∈ 。

- 跳转指令Π[] = (′,!)，其中′是程序行0 ≤ ′ < 或 + 1 < ′ < ，是一个命题。

- 终止指令Π[] = 。规划程序的最后一条指令始终是终止指令，即Π[− 1] = 。

规划程序的执行模型是一个程序状态(,)，即规划状态 ∈ 和程序计数器0 ≤ < 的配对。给定一个程序状态(,)，执行规划程序指令Π[]定义为：

- 如果Π[] ∈ ，则新程序状态为(′, + 1)，其中′ = Π[]()是在中应用Π[]的后继状态。

- 如果Π[] = (′,!)，则新程序状态为(, + 1)如果在中成立，否则为(,′)。2命题可以是状态变量的任意表达式的结果，例如状态特征[89]。

- 如果Π[] = ，程序执行终止。

要在经典规划实例 = ⟨, , , ⟩上执行规划程序Π，初始程序状态设置为(, 0)，即的初始状态和Π的第一条程序行。程序Π解决当且仅当执行终止于满足目标条件的程序状态(,)，即Π[] = 且 ∈ 。否则程序执行失败。如果规划程序未能解决规划实例，则失败的唯一可能来源是：

1. 不可应用的程序，即在程序状态(,)中执行动作Π[] ∈ 失败，因为Π[]在中不可应用。

2. 不正确的程序，即执行终止于不满足目标条件的程序状态(,)，即(Π[] = )∧ ( ∉ )。

3. 无限程序，即执行进入无限循环，永远不会到达指令。

在这项工作中，我们将指令Π[] ∈ 建模为始终可应用，但其效果仅在当前规划状态中动作的先决条件成立时更新当前状态。形式上，在(,)中执行Π[]时，新程序状态为(′, + 1)当且仅当Π[]可应用，否则为(, + 1)。因此，在这项工作中，程序在经典规划实例上的执行永远不会返回不可应用的程序，只有不正确或无限程序是可能的失败来源。这种特定的动作建模在强化学习[80]和一致性规划[44]中很常见，因为它提供了适用于不同问题集（通常具有不同的初始状态）的紧凑解决方案。

3.4. 随机存取机

随机存取机（RAM）是一种抽象的计算机器，属于寄存器机器的类别，与图灵机在多项式时间内等价[90]。RAM通过间接内存寻址增强了多寄存器计数器机器[91]的功能；间接内存寻址对于编写访问无界数量寄存器的RAM程序非常有用，无论实际有多少寄存器。RAM机器中的寄存器是一个内存位置，具有地址（即作为自然数的唯一标识符，我们记作）和内容（即单个自然数，我们记作[]）。

RAM程序Π是一个由条指令组成的有限序列，其中每条程序指令Π[]与程序行0 ≤ < 相关联。RAM程序的执行从其第一条程序指令Π[0]开始。程序指令Π[]的执行会更新RAM寄存器和当前程序行。可以定义多种基本指令集，这些指令集是图灵完备的。我们关注三种基本的RAM指令集：

- **Base1.** {(), (), (,), () | ∈ }。这些指令分别将寄存器增加/减少1，如果寄存器的内容为零（即[] == 0）则跳转到程序行0 ≤ < ，或者结束程序执行。

- **Base2.** {(1), (1), (1, 2,), () | 1, 2 ∈ }。在这个集合中，寄存器的值不能减少，但可以通过清除指令将其设置为零。此外，如果两个给定寄存器的内容相同（即[1] == [2]），跳转指令会跳转到程序行0 ≤ < 。

- **Base3.** {(1), (1, 2), (1, 2,), () | 1, 2 ∈ }。这个集合不包含减少或清除寄存器的指令，而是包含将一个寄存器设置为另一个寄存器值的指令。

这三个基本集合是等价的[90]；可以用一个基本集合的指令构建另一个基本集合的指令。此外，扩展指令集（包含Base 1、2和3的指令）不会改变各个基本集合的表达能力，因为它们已经是图灵完备的。RAM指令集的选择取决于程序员对所解决问题方便性的考虑。

4. 使用随机存取机进行规划

为规划领域合成有效的特征是一个具有挑战性的研究问题，自AP早期以来一直受到关注[92]。此外，给定领域的不同问题的基本动作集通常是不同的，因为它取决于问题中对象的数量；例如，回到图2和图3中所示的排序示例，对长度为六的向量进行排序的经典规划问题引入了6×5/2个(, )动作，而对长度为七的向量进行排序的实例将引入7×6/2个(, )动作。本节通过一组指针扩展了经典规划模型，这些指针定义在经典规划实例的对象上，并提供了操作这些指针的基本指令；扩展允许对状态特征和动作集进行无知的定义，这些特征和动作集由经典规划领域的不同实例共享（无论其实际对象数量如何）。

首先，本节展示了如何使用指针紧凑地表示转换系统。然后，本节展示了基于指针的表示自然适用于STRIPS形式体系。最后，本节通过RAM机器正式化了我们对经典规划模型的扩展，该机器生成了旨在共享的状态特征和动作集，这些特征和动作集由经典规划领域的所有实例共享。这些共享的状态特征和动作集随后被用于（在第5节中）计算GP解决方案，这些解决方案无论对象数量如何都能推广。

4.1. 使用对象上的指针表示转换系统

转换系统可以图形化地表示为一个有向图，因此可以形式化为一对 (,→)，其中是一组状态，→ 表示状态转换关系 × 。转换系统与有限自动机不同，因为状态和转换的集合不一定是有限的。此外，转换系统不一定定义起始状态或最终目标状态的子集。状态之间的转换可以被标记，3 并且同一个标签可能出现在多个转换上。一个突出的例子是与经典规划问题[1,2]相对应的转换系统，其中状态转换用动作标记（即，对于两个状态 , ′ ∈ ，存在一个转换 ( ←←←←←←→ ′) 当且仅当在状态中执行动作会产生状态 ′）。给定一个状态和一个动作标签，如果 → 中只存在一个唯一的元组 (, , ′)，则称该转换是确定性的。在这项工作中，我们仅限于确定性转换系统，即所有转换都是确定性的转换系统。

状态。在不失一般性的情况下，我们假设转换系统的状态是因子化的；给定一组世界对象 Ω，一个状态被因子化为一组有限的变量，使得每个变量 ∈ 要么表示世界对象的属性，要么表示个世界对象之间的关系。形式上， ≡ (1,…, )，其中是 ℕ 中的元函数，{}1 是 Ω 中的对象。例如，在图2和图3所示的示例中，给定一元函数和六对象集合 Ω = {0, 1, 2, 3, 4, 5}，每个状态变量 ∈ 定义为 ≡ ()。

指针和状态约束指针是用于索引转换系统对象的变量。结合函数符号，指针有助于定义状态约束，这些约束不仅产生紧凑的表示，而且产生可能无限状态集的通用表示。我们所说的通用是指一个约束表示一组具有某些共同结构的状态，无论实际对象的数量如何。图4展示了布尔函数 `constraint_all_sorted`，它实现了一个全局约束，用于检查状态变量向量的内容是否按升序排序；`constraint_all_sorted` 函数是程序化定义的，利用单个指针，并且适用于任意数量的对象和相应状态变量的任意域大小。

动作模式动作模式紧凑地指定了一组（可能是无限的）共享共同结构的转换；动作模式概括了任意数量或世界对象的身份。它们不涉及特定对象，而是利用参数间接引用不同的世界对象。接下来，我们将展示对象上的指针能够通过动作模式紧凑且通用地定义（可能是无限的）状态转换集。

定义 4（带指针的动作模式）。给定一组状态变量，带指针的动作模式是一个元组 ⟨name, params, pre, eff⟩，其中：

- **name** 是唯一标识动作模式的标签。

- **params** 是在对象集 Ω 上定义的有限指针集。

- **pre** 是一个状态约束，其中状态变量通过函数符号和 params 中的指针间接寻址，即 ≡ (⃖⃗)，使得 ∈ Φ 且 ⃖⃗ ∈ ()。pre 状态约束隐式表示动作模式适用的状态子集。

- **eff** 是对状态变量的部分赋值，其中状态变量的子集通过函数符号和 params 中的指针间接寻址。eff 部分赋值隐式表示在给定状态下执行动作模式后产生的结果状态。

图5展示了我们基于指针的动作模式定义；当适用时，`swap` 动作模式交换其两个参数（指针 1 和 2）索引的状态变量的值。状态变量是全局的，因此可以从任何动作模式访问。`swap` 动作模式是简洁的，因为它紧凑地定义了一组共享共同结构的无限不同状态转换。`swap` 动作模式也是通用的，因为它适用于任何排序实例，无论状态变量向量的长度或这些变量的域大小如何。更重要的是，`swap` 动作模式的执行是一个确定性的无匹配过程，因为输入指针总是索引 Ω 中的单个对象。

4.2. 使用对象上的指针表示STRIPS问题

自20世纪70年代初以来，STRIPS形式体系广泛用于自动规划研究[93]。即使在今天，STRIPS仍然是PDDL[86]（国际规划竞赛的输入语言）的重要组成部分，大多数规划器都支持STRIPS表示。在这里，我们展示了我们的基于指针的表示自然适用于以对象为中心的经典规划形式体系，如STRIPS。事实上，我们的基于指针的表示可以理解为F-STRIPS[94]的一个实例化，其中对象上指针的单层间接寻址足以表示具有常量内存访问的STRIPS问题。

STRIPS使用有限的对象集和有限的一阶逻辑（FOL）谓词集紧凑地表示转换系统的状态集，这些谓词指示对象的属性和它们之间的关系。同样，STRIPS使用FOL操作符紧凑地表示可能的状态转换空间，这些操作符定义为元组 = ⟨(), (), (), eff −(), eff +()⟩，其中 () 是操作符的唯一标识符，() 是指定操作符参数的变量符号集，()、eff −()、eff +() 是分别指定前提条件、负面效果和正面效果的FOL谓词集，这些谓词的变量仅从 () 中取。STRIPS问题的表示通过指定初始状态（定义对象的初始情况）和目标状态集（通常指定为部分状态）来完成。

**状态表示。** 当将我们的基于指针的形式体系应用于STRIPS问题时，每个状态变量 ∈ 的域 = {0, 1}，并且它被构建为一个由对象向量 ⃖⃗ ∈ Ω() 实例化的FOL STRIPS谓词 ∈ Φ。图6展示了使用STRIPS形式体系和我们的形式体系表示的blocksworld状态。在这个状态中，有三个块 Ω = {0, 1, 2}，它们堆叠成一个塔。谓词 clear(?x)、holding(?x) 和 ontable(?x) 被编码为三种不同的布尔函数，它们将每个对象向量映射到当前状态中的0或1。省略的状态变量假设为零值。我们的状态变量向量是将谓词和对象元组估值统一为一个向量的结果。状态变量向量的长度上限为 || ≤ ∑≥0 |Ω|，其中是具有元的一阶谓词的数量。例如，对于blocksworld域，向量最多包含 |Ω|2 + 3|Ω| + 1 个状态变量。4

**动作表示。** 给定一个FOL STRIPS操作符 = ⟨(), (), (), eff −(), eff +()⟩，我们的基于指针的形式体系生成其相应的基于指针的动作模式 ⟨name, params, pre, eff⟩：

- 动作模式的名称是 ()，即给定FOL STRIPS操作符的名称。

- 对于 () 中的每个参数，动作模式有一个指针索引对象 ∈ Ω。

- 集合 () 被转换为具有两种条件类型的合取算术逻辑表达式：(i) 断言动作模式的每个指针在其域内的条件，以及 (ii) 对于 () 中的每个前提条件，断言由指针内容寻址的状态变量等于其域的某个特定值的条件。

- 每个负面效果 in eff −() 被转换为将相应状态变量设置为0的间接变量赋值。同样，每个正面效果 in eff +() 被转换为将相应状态变量设置为1的间接变量赋值。

接下来，我们将展示用于形式化我们基于指针的STRIPS动作模式表示的语法。

语法以下是我们基于指针的STRIPS动作模式表示的语法，其中包括对谓词 (1,…, ) 的断言，这些谓词由动作参数（即指针）实例化，并表示操作符的前提条件（表示相等运算符，∶=表示赋值，分号表示程序指令的结束）。是表示操作符正/负效果的赋值的合取；更详细地说，(1,…, ) ∶= 1 表示正面效果，而 (1,…, ) ∶= 0 表示负面效果。图8展示了我们基于指针的定义，用于blocksworld中的unstack动作模式，该动作模式实现了图7中PDDL的STRIPS片段中表示的相应操作符。图8的动作模式使用两个指针（1 和 2）实现，并且适用于任何blocksworld实例，无论块的数量或其身份如何。问题表示我们通过initgoals过程完成基于指针的STRIPS问题表示：init过程是一个只写过程，实现状态变量的完全赋值，以指定STRIPS问题的初始状态。goals过程是一个只读布尔过程，编码指定目标状态子集的状态约束。图9展示了图6中3块塔的规划问题的initgoals过程。initgoals过程的内容归纳形式化如下：

图10展示了我们基于指针的表示，用于表示四步顺序计划 = ⟨unstack(b0,b1), putdown(b0), unstack(b1,b2), putdown(b1)⟩，以解开图6中的三块塔。更详细地说，`ONTABLE-SEQUENTIAL-PLAN()` 程序利用了两个指针， = {1, 2}，它们被初始化为零，因此最初指向第一个对象（在这种情况下是块 0）。在执行第一个 2++ 指令后，2 指向第二个块 1，而 1 仍然指向块 0。这意味着图10中程序的第一个 _(, ) 指令实际上执行了具体动作 (, )，对应于计划的第一步。同样，第一个 _() 程序指令执行具体动作 ()，即顺序计划的第二步。第二个 _(, ) 程序指令执行具体动作 (, )，因为 1 和 2 在执行该指令之前都增加了。最后，第二个 _() 执行具体动作 ()，这是顺序计划的第四步也是最后一步。

图11展示了动作模式（i）与其在指针上实例化的相应动作（ii）以及在对象集 Ω 上实例化的具体动作之间的特定关系。在图11中，指针 1 和 2 是绑定变量 [0,…,|Ω|)，当前分别索引块 0 和 1。

超越STRIPS

我们的基于指针的表示通过简单地将指针专门化为特定类型的对象子集[86]来支持对象类型化。此外，我们的基于指针的表示自然支持具有数值状态变量的经典规划，如PDDL2.1[96]中定义的那样。为了支持数值状态变量的表示，状态变量向量存储整数而不是布尔值。目标和动作前提条件可以包括对数值状态变量的断言，动作效果可以包括对数值状态变量的赋值。例如，`distance(b0,b1)=7` 可以用来表示块 0 和 1 之间的物理距离为7个单位。同样，`distance(z1,z2)>distance(z2,z3)` 可以用来表示指针 1 和 2 索引的块之间的距离大于指针 2 和 3 指向的块之间的距离。

4.3. 使用RAM扩展经典规划模型

现在我们准备利用我们的基于指针的表示和随机存取机（RAM）的概念来扩展经典规划模型。扩展产生了一组无知的共享状态特征和动作集，这些特征和动作集由给定领域的不同经典规划实例共享（无论其实际对象数量如何）。

给定一个经典规划实例 = ⟨, , , ⟩，其中状态变量和动作由给定领域的函数集 Φ 和动作模式 Ξ 生成，并由对象集 Ω 实例化。然后，扩展了具有 ||+ 2 个寄存器的RAM机器的经典规划实例（即 || 个引用规划对象的指针，加上两个专用的FLAGS寄存器，即零标志和进位标志）定义为 ′ = ⟨′ , ′, ′ , ⟩，其中：

新的状态变量集 ′ 包括：

- **原始规划实例的状态变量 **，其中每个状态变量 ∈ 是 ≡ (⃖⃗)，其中 ∈ Φ 且 ⃖⃗ ∈ Ω()，如上所述。

- **两个布尔变量 = {, }**，分别扮演零标志和进位标志寄存器的角色。

- **指针 **，一组额外的状态变量，其中每个 ∈ 具有有限域 = [0,…,|Ω| − 1]。

指针数量 || 是一个参数，表示在扩展中使用了多少指针。至少必须包含与给定领域中函数 Φ 和动作模式 Ξ 的最大元数相同的指针数量。因此，{ ∪ ∪ } 成为所有属于同一领域的实例共享的状态变量子集，无论它们有多少对象。同样，′

成为所有属于同一领域的实例共享的动作集，无论它们的实际对象数量如何。

4.3.1. 理论性质

我们对经典规划问题使用RAM机器的扩展保留了原始问题的解空间。然而，扩展规划模型中的顺序计划可能会更长（例如，前一个示例中计划 1 的基于指针的版本需要十三步，而原始顺序计划只有三步）。作为一个经验法则，当指针在执行相应动作之前必须多次递增（或递减）以访问相应对象时，原始计划长度会增加。

5. 作为启发式搜索的广义规划

本节介绍我们的GP作为启发式搜索方法；首先详细说明我们GP作为启发式搜索方法的搜索空间，然后解释我们用于GP的启发式搜索算法BFGP的具体细节。

5.1. 搜索空间

在这里，我们描述了第3.3节中引入的规划程序空间的分支因子，并展示了其大小取决于规划状态变量的域（不幸的是，这可能是无界的）。然后，我们通过使用RAM模型的FLAGS寄存器来限制规划程序的分支和循环，定义了一个可处理的GP搜索空间。我们展示了我们的新GP搜索空间与GP问题中输入规划实例的数量及其大小（即对象数量、状态变量及其域大小）无关。这使得能够定义一种启发式搜索方法，能够处理具有大数值域（如整数）的大量状态变量。

5.1.1. 基于值状态变量的规划程序条件

第3.3节中引入的规划程序的分支和循环是基于值状态变量[33]进行条件的，即如果状态变量具有值，则跳转到某一行。这种解决方案空间可以通过二进制编码来表征；给定一组状态变量，一组动作，一个最大程序行数，使得最后一行指令为 Π−1 = ，并将指令的命题定义为 ( = ) 原子，其中 ∈ 且 ∈ ，可能的规划程序空间用三个位向量编码：

1. **动作向量**，长度为 ( − 1) × ||，指示是否在行 0 ≤ < − 1 上编程了动作 ∈ 。

2. **转换向量**，长度为 ( − 1) × ( − 2)，指示是否在行 0 ≤ < − 1 上编程了 (′, ∗) 指令。

3. **命题向量**，长度为 ( − 1) × ∑∈ ||，指示是否在行 0 ≤ < − 1 上编程了 (∗,!⟨ = ⟩) 指令。

一个部分指定的规划程序通过将前面三个位向量的连接进行编码，结果位向量的长度为：

前面的二进制编码允许我们量化两个部分指定的规划程序的相似性（例如，它们相应位向量表示的汉明距离），更重要的是，可以系统地枚举具有最多行的所有可能的规划程序。让我们将空程序定义为特定部分指定的规划程序，其所有指令都是未定义的（即其位向量表示的所有位都设置为False）。从空程序开始，我们可以使用两个搜索操作符枚举整个可能的规划程序集：

这两个搜索操作符仅在 Π[] =< > 时适用（这意味着是一个未定义的程序行，即在其位向量表示中，对应于程序行编码的位被设置为False）。给定部分指定的规划程序的位向量表示，应用 program(i,a) 或 program(i,i’,x,v) 搜索操作符将相应位设置为True。在这方面，当使用 program(i,a) 编程规划动作时，给定搜索节点的部分指定规划程序与其父节点的汉明距离为1，或者当使用 program(i,i’,x,v) 编程指令时，汉明距离为2。事实上，这是经典规划编译方法利用的搜索空间，用于计算具有现成经典规划器的规划程序[33]。方程(2)表明，具有行的规划程序的数量取决于具体动作的数量 ||，以及状态变量 ∈ 及其域。这种依赖性导致可扩展性问题，限制了所引用编译方法对有限大小规划实例的适用性。在最坏的情况下，状态变量的域可能是无限的，例如数值状态变量，因此搜索空间可能是难以处理的。

5.1.2. 基于特征语言的规划程序条件

我们通过使用有限特征语言来限制规划程序的分支和循环，克服了前面解决方案空间的难以处理性。更详细地说，我们利用了我们对经典规划模型使用RAM的扩展，因为它为给定领域的经典规划实例生成了一组最小但通用的特征。

根据定义7，我们将GP解决方案表示为规划程序，其中goto指令只能基于  中的特征进行条件化。将goto指令的条件限制为  中的任何四个特征之一，限制了规划程序的数量。尽管 = {, } 标志有四种可能的值组合，但第四种情况 ( ∧ ) ∈  作为比较结果永远不会发生；然而，这第四种情况对于表示无条件goto是有用的。现在，编码规划程序所需的命题向量变成了只有 ( − 1) × 4 位的向量（ 中的每个特征对应一位）。方程(2)简化为：

方程(3)表明，我们新的GP解决方案空间的大小与对象数量无关，因此与原始状态变量及其域大小无关；定理2已经表明 ′ 不再随对象数量增长。这种新的GP解决方案空间现在可以扩展到状态变量具有大域（例如整数）且具有大量状态变量的规划问题。

示例图12展示了我们的BFGP算法在我们可处理的GP解决方案空间中合成的两个规划程序示例：（左）用于反转列表的广义计划，（右）用于排序列表的广义计划。注意，goto指令只能基于  中的特征进行条件化，并且这两个规划程序都是无限经典规划问题集的解决方案；它们无论对象数量 Ω 和状态变量内容如何，都具有泛化性，即 ≡ vector()，其中 ∈ Ω， ∈ 且 ⊆ ℕ0。在反转列表的规划程序（左）中，第0行将指针设置为列表的最后一个元素。第1行在向量中交换由指向的元素（最初设置为零）和由指向的元素，然后指针递减，指针递增，并且重复这一系列指令，直到第5行的条件变为假，即当 > 时，这意味着列表反转完成。排序列表的规划程序（右）实际上是选择排序算法的实现。在这个程序中，指针和分别用于内循环（第5-7行）和外循环（第8-11行），而指向内循环中的最小值（第3-4行）；第2行的 ¬ ∧ ¬ 表示 vector() 的内容是否小于 vector() 的内容，而第7行的 ∧ ¬ 表示 == ℎ（第11行的 == ℎ 同理）。注意，对象顺序会影响广义计划执行最终生成的顺序计划，但对象顺序不影响广义计划的正确性/完整性。这是结构化程序的常见特征，例如，SelectionSort 程序是健全且完整的，但实际执行的交换指令数量取决于要排序的输入列表。

5.2. 搜索算法

给定一个GP问题，我们的启发式搜索算法（称为BFGP）在我们的具有行程序和 || 个指针的RAM机器的规划程序解决方案空间中实现最佳优先搜索（BFS）。算法1展示了BFGP伪代码；BFGP是一个前沿搜索算法，这意味着为了减少内存需求，BFGP仅存储生成的节点开放列表，而不存储扩展节点的封闭列表[98]。BFGP算法运行如下：

1. **初始化**。空程序是BFGP开发的搜索树的根节点。这意味着最初，空程序 Π 由评估函数 ∈  进行评估，然后插入到  列表中，该列表实现为一个优先队列。

2. **选择**。当  列表不为空时，extractBestProgram 从  中获取最佳部分程序 Π。如果存在 Π 的值的前缀小于 Π′ 的相同前缀，则程序 Π 优于另一个程序 Π′，例如，给定  = ⟨5, 1⟩，如果 5(Π,) < 5(Π′,)，或者如果它们在 5 上打平但 1(Π) < 1(Π′)，则 Π 优于 Π′。如果两个程序在所有 ∈  上都打平，则较旧的程序（那些较早插入到  中的程序）将被认为更好，因此首先从  中提取。

3. **扩展**。一旦从  中提取出最佳部分程序 Π，expandProgram 过程将计算 Π 的所有子程序，这些子程序在给定的指针集和有限的程序行数下是语法有效的。更详细地说，BFGP 通过生成一个后继节点 Π′ 来扩展 Π，该后继节点是编程在所有实例  上执行 Π 后达到的最大未定义程序行。给定一个部分指定的程序 Π，只有其 ∈( )4(Π,) 行是可编程的。BFGP 实现这个特定的节点扩展过程，因为它保证了在 BFGP 搜索树中不会生成重复的后继节点。此外，这个节点扩展过程导致了一个可处理的 (|′| + ( − 2) × 4) 的分支因子；在给定的程序行上，BFGP 只能编程 ′ 中的规划动作或一个指令，该指令可以跳转到 − 2 个不同的目标程序行，并且由  中的任何四个不同特征进行条件化。BFGP 算法开发的搜索树的深度是程序行数，因为只有未定义的行可以编程。

4. **插入**。在将新搜索节点插入开放列表之前，相应的程序 Π′ 在  中的经典规划实例上执行。此执行可能导致以下三种不同结果之一：

(a) Π′ 是  的解决方案。如果 Π′ 的执行解决了所有实例 ∈ ，则搜索结束，并且 Π′ 将作为 GP 问题  的有效解决方案返回。

(b) Π′ 未能解决 。如果 Π′ 在给定实例 ∈  上的执行失败，这意味着对应于部分规划程序 Π′ 的搜索节点是一个死胡同。搜索节点将被丢弃，因此 Π′ 不会插入到开放列表中。失败的原因可能是因为执行了终端指令但目标条件不成立，或者检测到无限循环。

(c) Π′ 可能仍然是  的解决方案。这意味着 Π′ 在  中的一些经典规划实例上的执行达到了未定义的程序行（Π′ 可能解决了  中的一些实例）。因此，Π′ 通过调用 insertProgram 插入到  中，根据其在  函数上的评估结果插入到相应位置。

5.2.1. 评估函数

在这里，我们介绍指导BFGP算法的评估和启发式函数。从 1 到 6 的函数在先前的工作[31]中引入，而 7、8 和 9 是本文首次引入。在这里，我们定义了两个不同的评估函数族，利用两种不同的信息源，以指导在我们部分指定的规划程序的GP解决方案空间中的组合搜索：

- **程序结构**。给定一个部分指定的规划程序 Π，我们定义一组评估函数 (Π)，它们在目标广义计划的结构上建立偏好/先验。例如，遵循奥卡姆剃刀原则，结构函数可以偏好更简单复杂度的广义计划，或者偏好具有更多编程行的广义计划，以便在搜索中更早地检测到执行失败。

- **1(Π)**，Π 中指令的数量。

5.2.2.理论性质

BFGP 可能是不完备的，因为最大程序行数或可用指针的最大数量 || 可能太小，无法容纳给定GP问题的解决方案。关于解决方案质量，BFGP 不保证计算的规划程序是最优的。然而，BFGP 可以以任何时间模式运行，并使用 6(Π,) 根据给定GP问题中包含的经典规划实例的执行成本对GP解决方案进行排序（例如，偏好具有较小计算复杂度的排序规划程序）。

6. 评估

本节评估我们GP作为启发式搜索方法的经验性能。所有实验都在 Ubuntu 20.04 LTS 上进行，使用 AMD® Ryzen 7 3700x 8 核处理器 × 16 和 32 GB 内存。

6.1. 基准测试

我们在九个不同的领域报告结果；三个命题领域和六个数值领域。在命题领域中，诱导状态变量的函数 Φ 是布尔函数。在数值领域中，这些函数是正数值函数。接下来，我们提供每个九个领域的更多细节：

- **Corridor**，一个代理从一个任意初始位置移动到走廊中的目标位置。

- **Gripper**，一个机器人必须从房间A中拾取所有球并将它们放入房间B。

- **Visitall**，从一个方形网格的左下角开始，一个代理必须访问所有单元格。

- **Fibonacci**，计算斐波那契数列的第项。

- **Find**，计算列表中特定值的出现次数。

- **Reverse**，反转列表的内容。

- **Select**，找到列表中的最小值。

- **Sorting**，对向量的值进行排序。

- **Triangular Sum**，计算第个三角形数。

Corridor、gripper 和 visitall 是命题领域，其余六个领域是数值领域。对于每个领域，我们构建了一个包含十个随机生成的经典规划实例的GP问题8；在 corridor 领域中，实例的走廊长度从3到12；在 gripper 中，实例在房间A中有2到11个球需要放入房间B；在 visitall 中，实例是2 × 2到11 × 11个单元格的方形网格；Fibonacci 和 triangular sum 实例从序列中的第2个到第11个数字；其余领域，find、reverse、select 和 sorting 有向量大小从2到11的实例，初始化为随机内容。在这些领域中，算术运算的结果在合成GP解决方案时限制为102，在验证GP解决方案时限制为。

6.2. GP解决方案的合成和验证

在这里，我们展示了评估BFGP算法性能的第一次实验。首先，我们通过运行 BFGP() 来评估每个评估/启发式函数。然后，我们展示最佳配置 BFGP(5) 生成的解决方案。最后，合成的解决方案相对于更大实例（即更多对象）的测试集进行验证。

6.2.1. BFGP() 的性能

表1详细列出了第一次合成实验的结果，其中BFGP算法使用了我们九个不同的评估/启发式函数（计算边界为3,600秒CPU时间和32GB内存，最佳结果以粗体显示）。关于基于结构的函数，2 在所有领域和指标中占主导地位（除了在 reverse 领域中 3 更快且 1 扩展的节点更少），并且它还具有最高的覆盖率，解决了7个领域（1、3 和 7 的覆盖率较低，在相同的四个领域中失败，即 corridor、gripper、sorting 和 visitall）。关于基于性能的函数，5 是明显的赢家，在超过一半的领域中得分最高，并且在基准测试中具有完全覆盖，其次是 4 和 9，覆盖了6个领域，但在多个领域中改进了 5 的指标，例如，4 在所有领域中具有最低的内存消耗，并且在 Fibonacci、reverse 和 triangular sum 中扩展和/或评估的节点更少。

表2总结了表1的结果，按领域分组并按解决每个领域的函数总数平均指标。有5个领域被所有九个评估/启发式函数解决。在其余领域中，至少有5个或更多的函数无法解决它们，即 gripper 仅被 2、4、5 和 8 解决；corridor 和 visitall 是最难解决的领域（只有 5 解决了它们）；而 sorting 被 2 和 5 解决，但在每个指标平均值方面是最难的。

6.2.2. 合成的解决方案

图13展示了由 (5) 计算的程序。在 Corridor 中，有两个指针 1 和 2，它们开始指向第一个位置；解决方案将代理移动到最右边的单元格，然后一个接一个地向左移动，直到不在目标单元格。在 Fibonacci 中，指针和用于计算第个斐波那契数，其中指向数，−1 和 −2 使用作为辅助指针相加；当达到第个元素（最后一个）时结束。在 Find 中，有一个指针用于遍历向量，为每个向量位置累积目标值的出现次数。

Gripper 解决方案使用一个指针用于球（1），两个用于房间（1 和 2），一个用于夹子 1；对于每个球 1，代理将从房间 1（总是房间A）使用夹子 1（总是左夹子）拾取，将 2 设置为房间B，从A移动到B，在房间B放下球 1，回到房间A，并继续下一个球。Reverse 领域使用两个指针和，并在大小为的向量中找到一个具有 (2) 复杂度的解决方案；它将所有值从移动到 − 1 索引一次向右移动，并将最后一个元素放在第个位置，使用作为辅助指针；然后增加1，直到到达向量的末尾。Select 领域有两个指针和；它使用指针遍历向量，每次指向的值小于指向的值时，将赋值给，最后将指向最小的值，该值将被选中。

Sorting 解决方案简洁但易于解释；在递增顺序访问每个向量索引时使用和指针，使得 = − 1，如果第个值小于第个值，则将该值在向量中向后移动，直到相对排序，然后继续搜索下一对相邻且未排序的值，直到所有值都排序。在 Triangular Sum 中，给定一个初始化为 = 的向量，每个索引以递增顺序使用指针和访问，使得 = − 1，为每个索引执行 ← + 。

最后一个领域 Visitall 有两个指针 1 和 2 用于行，还有两个 1 和 2 用于遍历列。由于代理从左下角开始，策略包括逐行访问网格，首先向右移动，然后向上移动一次，然后向左移动，直到所有行都被访问。

BFGP 实现了一种归纳方法来解决GP问题，这意味着计算的广义计划仅满足由有限输入示例给出的形式规范。因此，在输入示例遵循清晰分布的领域中，BFGP 可能会利用这一点（例如，走廊或网格的位置，或向量的索引，这些自然以特定顺序表达）。然而，对象顺序不影响方法的正确性/完整性，例如，Sorting 程序能够对任何输入列表进行排序，无论其大小或内容如何，或者 Blocks Ontable 程序（图15）将所有块放在桌子上，无论块的名称、顺序或初始塔的设置如何，代价是额外的一次迭代。在 Gripper 的特定情况下，房间在领域中是常量，因此它们总是以相同的顺序出现。如果我们为每个实例打乱房间的顺序，我们可能需要更多的行来解决 Gripper（即为每个可能的排列解决问题），或者在初始状态中添加目标信息，如在 Corridor 和 Grid 中所做的那样，以保持解决方案简短。在后一种情况下，图14中的规划程序解决了所有 Gripper 实例，房间没有特定的顺序。

6.2.3. 合成的解决方案的验证

在这里，我们使用更大且更难的实例集验证图13中 BFGP(5) 合成的解决方案。表3报告了在验证集上运行 (5) 合成的解决方案时产生的CPU时间和峰值内存。所有由 (5) 合成的解决方案都成功验证。最大的CPU时间和内存峰值对应于实现无限程序检测的配置，这需要在执行期间保存状态以检测它们是否被重新访问。跳过此机制可以更快且使用更少的内存验证终止程序[41]。

在验证集中，规划领域中的每个状态变量被限制为109，而不是合成时的102。Corridor 在100个实例上进行验证，走廊长度 ∈ [13, 112]，初始和目标位置随机。Gripper 在1,000个实例上进行验证， ∈ [12, 1011] 个球最初在房间A中，需要移动到房间B。Fibonacci 有一个包含33个实例的验证集，范围从第12个斐波那契数到第44个，即整数701,408,733（第45个数将超出验证边界）。Select 和 Find 领域的解决方案在100个实例上进行验证，向量大小范围从100到1,090，随机整数元素被限制为109。同样，Reverse 和 Sorting 有100个验证实例，向量包含随机整数，但大小范围从12到111。Triangular Sum 的解决方案在1,000个实例上进行验证，最后一个对应于序列中的第1,011个项，即整数511,566。在 Visitall 中，有50个验证实例，方形网格范围从12 × 12到61 × 61。

6.3. 结合函数组合的BFGP性能

结合结构和代价到目标信息可以提高使用单一评估/启发式函数的BFGP的基本性能；我们可以使用代价到目标启发式函数指导BFGP的搜索，并用结构评估函数打破平局，反之亦然。因此，我们运行所有 BFGP(,) 和 BFGP(,) 配置，其中 ∈ {1,2,3,7} 和 ∈ {4,5,6,8,9}，并选择在所有领域中以最佳平均时间解决问题的配置。有40个 BFGP(,)/BFGP(,) 配置，但只有 BFGP(3,5) 和 BFGP(5,3) 能够解决所有领域。然后将这两个配置的性能与 BFGP(5) 进行比较，因为它是前一个实验中唯一能够解决所有领域的单一评估/启发式函数。表4总结了这一比较，显示 BFGP(5) 在每个领域中都被 BFGP(3,5) 或 BFGP(5,3) 改进。此外，BFGP(3,5) 在时间和内存上具有最佳平均性能，紧随其后的是 BFGP(5,3)，在节点扩展和评估上具有最佳平均性能，经验证明目标导向函数在与基于结构的函数结合时可能会受益。

6.4. 与相关GP求解器的比较合成性能

GP求解器性能的比较分析很复杂，主要是因为它们的假设、问题规范、特征语言、超参数和不同的解决方案表示（非/确定性、布尔/数值等）[21]。在这方面，我们选择了在解决方案表示方面最接近的两个GP求解器，即规划程序（PP）[33]和分层有限状态控制器（HFSC）[61]。这两种方法都是基于编译的，输入是一个带有某些实例的经典规划领域，以及规划程序行数的上限（）或控制器状态数的上限（||）。这两种方法都生成一个单一的领域和实例，可以使用现成的经典规划器解决。生成实例的解决方案是按照自顶向下的策略计算的，使用Fast-Downward[8]系统的LAMA-2011[99]规划器（首次解决方案设置），生成编程和执行动作交替的序列，从中可以推导出程序、控制器和经典计划。

第5节已经讨论了PP（最坏情况下难以处理，例如整数表示）和BFGP（具有有界大小的可处理性）搜索空间之间的关系。PP和HFSC在另一种表示中被证明具有等价的解决方案[61]，因此第5节中的理论实际上适用于两者。先验地，PP和HFSC的一些优缺点已经在之前被识别[61,33]：

- **优点**：

- 可以使用现成的经典规划器解决GP问题，

- 经典规划器偏向于更短的解决方案计划（可能会产生简洁的广义计划），

- 对于小边界和小对象数量的问题表现良好。

- **缺点**：

- 计算对输入实例的顺序及其对象数量敏感，

- 当输入实例数量增加时，可扩展性急剧下降，

- 需要手动编码特征作为多个领域中的派生谓词，或额外的知识来计算具有确定性行为的广义计划，例如在gripper领域中，需要对球进行序列化以知道下一个要拾取的球，

- 合成的广义计划可能会过拟合，因为特征语言包括作为输入的所有经典规划实例中的所有流。

与PP和HFSC相比，BFGP的优缺点是：

- **优点**：

- 广义计划的计算不受输入实例顺序的影响，

- BFGP的可扩展性随着对象数量的增加平滑且连续地下降，

- 解决方案不会过拟合，因为特征语言（过拟合仅由于输入实例采样不佳），

- 领域不需要额外知识（BFGP实现了无知的特征生成）。

- **缺点**：

- BFGP没有使用现成的经典规划机制，尽管大多数机制可以适应[65]，

- 广义计划由于指针操作而更长，这可能会降低简单实例的性能，

- BFGP可能需要增加默认的输入指针数量。

比较GP求解器的实验设置使用与BFGP合成实验相同的 || = 10 个随机输入实例。由于我们观察到PP和HFSC受限于此数量，我们继续从实例池中移除最大的实例，直到其中一个在没有过拟合的情况下解决问题。此外，当必要时，我们在PP和HFSC领域中以派生谓词的形式编码额外知识，以保证泛化，这反过来有助于计算更短的广义计划，例如在corridor领域中，需要知道代理是否在目标位置或在最右边的位置；在gripper中，需要对球进行序列化并知道房间A中是否没有更多的球；等等。三种GP求解器的比较如表5所示；即使给PP和HFSC提供了手工制作的额外知识和减少输入实例的优势（导致在半数领域中执行指令的最小数量，即∑ |Π|），BFGP在许多方面仍然优于PP和HFSC，即在基准测试中具有完全覆盖，在9个领域中的6个领域中具有最佳计算时间，并且在所有领域中具有最短的经典计划（即∑ ||），且假设更少。

6.5. 在更复杂领域中验证GP解决方案

在这里，我们介绍几个已知具有多项式时间解决方案的GP基准测试，这些基准测试对于我们当前的BFGP算法来说过于复杂（在给定的时间和内存限制内）。我们的目标是展示我们的方法在表达上足以表示来自IPC规划领域、无噪声监督分类任务和数值领域的GP问题的解决方案。这些解决方案简洁地表示为GP计划，而不是大型问题的长序列基础动作，并且可以高效验证，不受当前现成经典规划器的实例化方法的影响。

- **Blocks Ontable**，积木塔，所有积木必须放在桌子上。

- **Grid**，一个代理必须从一个任意位置移动到2D网格中的目标位置。

- **Miconic**，是一个电梯问题，乘客在起点等待电梯进入，然后在目标楼层服务。

- **Michalski Trains**，是关系监督机器学习的经典问题。一个无噪声的二分类任务，有10列火车，要么向东要么向西，以及多个特征，如每列火车的轮子数量、车厢数量或其形状等。目标是学习将所有火车正确分类的特征。

- **Satellite**，包括使用搭载在卫星上的仪器对不同目标进行成像。此外，仪器需要校准并在特定模式下进行成像；每个卫星一次只能为一个仪器供电，因此在使用新仪器进行成像之前，需要关闭当前仪器，打开下一个仪器并进行校准。

- **Sieve of Erathostenes**，是一种仅使用加法和迭代机制找到某个界限内的素数的方法。

- **Spanner**，包括在走廊尽头拧紧所有松动的螺母，沿着走廊拾取的扳手。扳手只能使用一次，当代理移动到下一个房间时，它不能返回，因此如果在访问过的房间中有未拾取的扳手，任务可能会变得不可解。

图15展示了这些基准测试的手工编码解决方案。在Blocks Ontable中，给定个积木，解决方案的复杂度是三次的，即 (3)，其中它搜索次，每次 1 积木在 2 积木的顶部，然后解堆叠并将 1 放在桌子上。在Spanner中，代理在位置 2 拾取所有可用的扳手，走到下一个 1 位置并重复该过程，直到到达最后一个位置（门），收集其路径上的所有扳手；一旦在门中，它用扳手拧紧每个松动的螺母。Michalski Trains的解决方案总结为，每列火车 1 如果有一个封闭且短的车厢，将向东行驶，否则将向西行驶。在Sieve of Eratosthenes中，所有数字最初都被分类为素数，并且应该决定它们是否不是；因此它遍历并使用和作为辅助指针，其中第一个作为计数器，范围从0到，第二个加到的下一个倍数，即 % = 0；然后每个第个数字将被设置为非素数，增加1，该过程重复直到到达最后一个元素。在Grid中，代理移动到右上角，然后在不在目标列时向左移动，然后在不在目标行时下移，访问结果坐标。在Miconic中，电梯移动到最顶层，然后每层向下移动，登机并离开所有可用的乘客，一旦在最底层，它向上移动，服务电梯中剩余的乘客，直到再次到达最顶层。最后一个领域Satellite是最复杂的，因为它需要在多个变量类型上进行迭代，即卫星、仪器、模式和方向。该领域的解决方案包括关闭所有仪器并将所有卫星转向第一个方向；然后对于每个卫星，1 仪器被打开，用其校准目标方向 2 进行校准，并用于在每个模式 1 中对每个方向 2 进行成像；完成后，卫星再次转向第一个方向 1，关闭当前仪器，并继续下一个仪器，直到所有卫星都使用了所有仪器。

7. 结论

本文提出了一种创新的GP解决方案空间，使得可以定义一种启发式搜索方法来解决GP问题。这种新的GP解决方案空间与GP问题中输入规划实例的数量及其大小（即对象数量、状态变量及其域大小）无关。因此，我们的GP作为启发式搜索方法可以处理具有大数值域（例如整数）的大量状态变量。

我们相信，这项工作是朝着在自动规划和编程领域之间建立更紧密联系迈出的一步。本文将经典规划形式化为向量变换任务，这是一种常见的编程任务。根据这种形式体系，计算该任务的顺序计划是计算向量变换操作的组合。同样，计算广义计划是计算向量变换的算法表达。9 在这方面，BFGP算法从一个空程序开始，但没有什么能阻止我们从部分指定的广义计划[102]开始搜索，以开发新的在线方法，更好地扩展。事实上，局部搜索方法已经在规划[103]和程序合成[104,68]中取得了成功。

我们的代价到目标启发式仍然不如当前经典规划的最先进启发式信息丰富；请注意，我们的启发式仅考虑问题表示中明确提供的目标。一个明显的例子是 5(Π,)，它建立在欧几里得距离之上，对于STRIPS规划问题实际上是一个目标计数器。我们相信，通过借鉴现代规划启发式的强大思想[105,8,106]，可以获得更好的估计。更详细地说，开发更信息丰富的GP启发式的一个有前途的方法是考虑子目标，这些子目标在问题表示中没有明确给出[10,65]。例如，可以在预处理步骤中发现子目标集，而不进行实例化，考虑多项式IW(1)算法在实现单个目标时遍历的相关原子集[107]。除了地标，启发式规划器还实现了互补的思想，如有帮助的动作[7]、用于组合不同启发式的多个队列[8]，或基于新颖性的探索[108]。将这些经典规划技术融入GP作为启发式搜索方法是一个有前途的研究方向[109]。除了更信息丰富的启发式，我们还对更具表现力的解决方案表示感兴趣，不仅计算目标无关（例如图6中的Blocks Ontable）和目标导向（例如图6中的Grid）的广义计划，还包括包含距离函数的解决方案，这些函数测量向（子）目标的进展；距离函数已知是表示多项式可近似（poly-APX）领域紧凑算法解决方案所必需的[110]。

由于我们将GP视为经典的树搜索，来自组合搜索和经典规划的广泛有效技术可以帮助提高我们方法的基本性能。我们提到了一些更有前途的技术。当为每个评估函数添加一个开放列表时，搜索中的探索可以更有效[8]，并且可以实现更复杂的机制来处理封闭节点。例如，可以实现延迟重复检测，以使用磁盘内存管理大型封闭列表[111]。此外，一旦搜索节点被取消（例如，因为 (Π,) 识别到规划程序在给定实例上失败），任何与此节点等价的程序也应被取消，例如，任何可以通过因果独立指令的转置构建的程序。鉴于搜索树的深度是有限的，来自SAT/CSP/SMTs的技术，如非时间回溯、有限差异搜索[112]或禁忌搜索[113]，也可能有效地改进我们的方法。SATPLAN规划器利用多线程计算来并行化具有不同边界的解决方案空间中的搜索[114]。这一相同的想法可以应用于具有不同程序大小的GP解决方案的多次搜索。

最后但同样重要的是，另一个有趣的研究方向是扩展我们的GP作为启发式搜索方法，以从不同的输入设置开始计算广义计划。例如，从一组计划轨迹计算广义计划，这些轨迹展示了如何解决多个规划问题。我们还对探索将我们的GP作为启发式搜索方法应用于非目标导向的规划问题感兴趣，其中目标是最大化给定的效用函数[115]。在这种特定设置中，可以从近似策略迭代[116]和强化学习[80]中引入思想到我们的框架中。在这方面，我们正在探索将我们的方法扩展到包含实数状态变量的GP问题。我们相信，通过引入实数变量比较的精度概念，并相应地重新定义FLAGS寄存器的更新机制，我们可以解决这类GP问题。