Generalizedplanningasheuristicsearch:Anewplanningsearch-spacethatleveragespointersoverobjects
作为启发式搜索的广义规划:一个新的规划搜索空间，利用对象上的指针
摘要
启发式搜索规划是经典规划中最成功的方法之一，但不幸的是，它不能直接扩展到广义规划（GP）；GP旨在计算算法解决方案，这些解决方案对于给定域中的一组经典规划实例有效，即使这些实例在对象数量、初始和目标配置以及状态变量的数量（和可能的值）上有所不同。状态空间搜索，正如启发式规划器所实现的那样，对于GP变得不切实际。在本文中，我们将启发式搜索规划范式适应GP的泛化需求，并提出了第一个GP的启发式搜索方法。首先，本文介绍了一种新的基于指针的GP解决方案空间，该空间独立于GP问题中的经典规划实例数量及其大小（即对象数量、状态变量及其域大小）。其次，本文定义了我们GP算法的升级版本，称为最佳优先广义规划（BFGP），它在我们的基于指针的GP解决方案空间中实现最佳优先搜索。最后，本文为BFGP定义了一组评估和启发式函数，用于评估候选GP解决方案的结构复杂性及其对给定输入经典规划实例集的适应性。这些评估和启发式函数的计算不需要提前接地状态或动作。因此，我们的启发式搜索GP方法可以处理具有大数值域的大量状态变量，例如整数。
关键词：广义规划经典规划启发式搜索规划与学习领域特定控制知识程序综合示例编程
（完整内容请参考原论文）
我们使用积木世界（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]和Intelx86FLAGS寄存器[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方法的性能。
关于问题表示，有两种不同的方法来指定GP问题中包含的一组经典规划实例。显式方法，枚举GP问题中的每个经典规划实例[33]，和隐式方法，定义GP问题的一组经典规划实例所满足的约束。隐式方法是有趣的，因为它可以紧凑地指定无限的经典规划实例集（例如，属于积木世界域的无限经典规划实例集）[34,35,20]。除了经典规划实例集之外，还可以指定额外的背景知识，以减少GP解决方案的空间。例如，计划轨迹演示如何解决一些输入实例[36–38]，完整状态空间[22]，可以用于计算广义计划的状态特征的特定子集[39,40]，指定目标GP解决方案的不期望行为的负例[41,22]，或任何给定域中的状态必须满足的状态不变量[42]。
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的先前工作主要遵循以对象为中心的STRIPS表示。使用这种表示处理编程任务是不切实际的，因为它可能需要将状态变量域中的所有值编码为对象。其他方法，如定性数值规划（QNP）[48,49]，使用命题定性地处理大数值状态变量，以表示变量是否等于零。在这项工作中，我们处理具有整数状态变量的GP问题，这使得自然地处理各种编程任务，就好像它们是GP问题一样。
-显式问题表示。在这项工作中，GP问题包含要解决的有限经典规划实例的显式枚举。有趣的是，我们的实验结果表明，在几个领域中，解决一小部分随机生成的经典规划实例足以获得泛化到属于给定域的无限问题集的解决方案。
-无背景知识。我们的方法不需要任何额外帮助，如状态不变量、计划/轨迹/演示、负例或广义计划中出现的特征子集的指定。在这方面，我们利用随机存取机[28]和Intelx86FLAGS寄存器[29]的计算模型，生成一个与给定域的不同经典规划实例共享的无知状态特征集（无论它们的实际对象数量如何）。
-离线可满足性方法。这项工作遵循GP的离线方法，旨在一次性计算解决作为输入给出的所有经典规划实例的广义计划。由于许多启发式搜索算法很容易扩展到在线版本，我们相信我们的启发式搜索GP方法是迈向可以处理更大经典规划实例集的在线方法的垫脚石。
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问题的解决方案。
3.3规划程序
-规划动作Π[]∈。
-跳转指令Π[]=(′,!)，其中′是程序行0≤′<或+1<′<，是一个命题。
-终止指令Π[]=。规划程序的最后一条指令始终是终止指令，即Π[1]=。
规划程序的执行模型是一个程序状态(,)，即规划状态∈和程序计数器0≤<的配对。给定一个程序状态(,)，执行规划程序指令Π[]定义为：
-如果Π[]∈，则新程序状态为(′,+1)，其中′=Π[]()是在中应用Π[]的后继状态。
-如果Π[]=(′,!)，则新程序状态为(,+1)如果在中成立，否则为(,′)。2命题可以是状态变量的任意表达式的结果，例如状态特征[89]。
-如果Π[]=，程序执行终止。
1.不可应用的程序，即在程序状态(,)中执行动作Π[]∈失败，因为Π[]在中不可应用。
2.不正确的程序，即执行终止于不满足目标条件的程序状态(,)，即(Π[]=)∧()。
3.无限程序，即执行进入无限循环，永远不会到达指令。
3.4.随机存取机
-**Base1.**{(),(),(,),()|∈}。这些指令分别将寄存器增加/减少1，如果寄存器的内容为零（即[]==0）则跳转到程序行0≤<，或者结束程序执行。
-**Base2.**{(1),(1),(1,2,),()|1,2∈}。在这个集合中，寄存器的值不能减少，但可以通过清除指令将其设置为零。此外，如果两个给定寄存器的内容相同（即[1]==[2]），跳转指令会跳转到程序行0≤<。
-**Base3.**{(1),(1,2),(1,2,),()|1,2∈}。这个集合不包含减少或清除寄存器的指令，而是包含将一个寄存器设置为另一个寄存器值的指令。
这三个基本集合是等价的[90]；可以用一个基本集合的指令构建另一个基本集合的指令。此外，扩展指令集（包含Base1、2和3的指令）不会改变各个基本集合的表达能力，因为它们已经是图灵完备的。RAM指令集的选择取决于程序员对所解决问题方便性的考虑。
4.使用随机存取机进行规划
首先，本节展示了如何使用指针紧凑地表示转换系统。然后，本节展示了基于指针的表示自然适用于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}，并且它被构建为一个由对象向量∈Ω()实例化的FOLSTRIPS谓词∈Φ。图6展示了使用STRIPS形式体系和我们的形式体系表示的blocksworld状态。在这个状态中，有三个块Ω={0,1,2}，它们堆叠成一个塔。谓词clear(x)、holding(x)和ontable(x)被编码为三种不同的布尔函数，它们将每个对象向量映射到当前状态中的0或1。省略的状态变量假设为零值。我们的状态变量向量是将谓词和对象元组估值统一为一个向量的结果。状态变量向量的长度上限为||≤∑≥0|Ω|，其中是具有元的一阶谓词的数量。例如，对于blocksworld域，向量最多包含|Ω|2+3|Ω|+1个状态变量。4
**动作表示。**给定一个FOLSTRIPS操作符=(),(),(),eff(),eff+()，我们的基于指针的形式体系生成其相应的基于指针的动作模式name,params,pre,eff：
-动作模式的名称是()，即给定FOLSTRIPS操作符的名称。
-对于()中的每个参数，动作模式有一个指针索引对象∈Ω。
-集合()被转换为具有两种条件类型的合取算术逻辑表达式：(i)断言动作模式的每个指针在其域内的条件，以及(ii)对于()中的每个前提条件，断言由指针内容寻址的状态变量等于其域的某个特定值的条件。
-每个负面效果ineff()被转换为将相应状态变量设置为0的间接变量赋值。同样，每个正面效果ineff+()被转换为将相应状态变量设置为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.理论性质
6.评估
本节评估我们GP作为启发式搜索方法的经验性能。所有实验都在Ubuntu20.04LTS上进行，使用AMDRyzen73700x8核处理器×16和32GB内存。
6.1.基准测试
我们在九个不同的领域报告结果；三个命题领域和六个数值领域。在命题领域中，诱导状态变量的函数Φ是布尔函数。在数值领域中，这些函数是正数值函数。接下来，我们提供每个九个领域的更多细节：
-**Corridor**，一个代理从一个任意初始位置移动到走廊中的目标位置。
-**Gripper**，一个机器人必须从房间A中拾取所有球并将它们放入房间B。
-**Visitall**，从一个方形网格的左下角开始，一个代理必须访问所有单元格。
-**Fibonacci**，计算斐波那契数列的第项。
-**Find**，计算列表中特定值的出现次数。
-**Reverse**，反转列表的内容。
-**Select**，找到列表中的最小值。
-**Sorting**，对向量的值进行排序。
-**TriangularSum**，计算第个三角形数。
Corridor、gripper和visitall是命题领域，其余六个领域是数值领域。对于每个领域，我们构建了一个包含十个随机生成的经典规划实例的GP问题8；在corridor领域中，实例的走廊长度从3到12；在gripper中，实例在房间A中有2到11个球需要放入房间B；在visitall中，实例是2×2到11×11个单元格的方形网格；Fibonacci和triangularsum实例从序列中的第2个到第11个数字；其余领域，find、reverse、select和sorting有向量大小从2到11的实例，初始化为随机内容。在这些领域中，算术运算的结果在合成GP解决方案时限制为102，在验证GP解决方案时限制为。
6.2.GP解决方案的合成和验证
在这里，我们展示了评估BFGP算法性能的第一次实验。首先，我们通过运行BFGP()来评估每个评估/启发式函数。然后，我们展示最佳配置BFGP(5)生成的解决方案。最后，合成的解决方案相对于更大实例（即更多对象）的测试集进行验证。
6.2.1.BFGP()的性能
表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，如果第个值小于第个值，则将该值在向量中向后移动，直到相对排序，然后继续搜索下一对相邻且未排序的值，直到所有值都排序。在TriangularSum中，给定一个初始化为=的向量，每个索引以递增顺序使用指针和访问，使得=1，为每个索引执行←+。
最后一个领域Visitall有两个指针1和2用于行，还有两个1和2用于遍历列。由于代理从左下角开始，策略包括逐行访问网格，首先向右移动，然后向上移动一次，然后向左移动，直到所有行都被访问。
BFGP实现了一种归纳方法来解决GP问题，这意味着计算的广义计划仅满足由有限输入示例给出的形式规范。因此，在输入示例遵循清晰分布的领域中，BFGP可能会利用这一点（例如，走廊或网格的位置，或向量的索引，这些自然以特定顺序表达）。然而，对象顺序不影响方法的正确性/完整性，例如，Sorting程序能够对任何输入列表进行排序，无论其大小或内容如何，或者BlocksOntable程序（图15）将所有块放在桌子上，无论块的名称、顺序或初始塔的设置如何，代价是额外的一次迭代。在Gripper的特定情况下，房间在领域中是常量，因此它们总是以相同的顺序出现。如果我们为每个实例打乱房间的顺序，我们可能需要更多的行来解决Gripper（即为每个可能的排列解决问题），或者在初始状态中添加目标信息，如在Corridor和Grid中所做的那样，以保持解决方案简短。在后一种情况下，图14中的规划程序解决了所有Gripper实例，房间没有特定的顺序。
6.2.3.合成的解决方案的验证
在验证集中，规划领域中的每个状态变量被限制为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。TriangularSum的解决方案在1,000个实例上进行验证，最后一个对应于序列中的第1,011个项，即整数511,566。在Visitall中，有50个验证实例，方形网格范围从12×12到61×61。
6.3.结合函数组合的BFGP性能
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可能需要增加默认的输入指针数量。
6.5.在更复杂领域中验证GP解决方案
-**BlocksOntable**，积木塔，所有积木必须放在桌子上。
-**Grid**，一个代理必须从一个任意位置移动到2D网格中的目标位置。
-**Miconic**，是一个电梯问题，乘客在起点等待电梯进入，然后在目标楼层服务。
-**MichalskiTrains**，是关系监督机器学习的经典问题。一个无噪声的二分类任务，有10列火车，要么向东要么向西，以及多个特征，如每列火车的轮子数量、车厢数量或其形状等。目标是学习将所有火车正确分类的特征。
-**Satellite**，包括使用搭载在卫星上的仪器对不同目标进行成像。此外，仪器需要校准并在特定模式下进行成像；每个卫星一次只能为一个仪器供电，因此在使用新仪器进行成像之前，需要关闭当前仪器，打开下一个仪器并进行校准。
-**SieveofErathostenes**，是一种仅使用加法和迭代机制找到某个界限内的素数的方法。
-**Spanner**，包括在走廊尽头拧紧所有松动的螺母，沿着走廊拾取的扳手。扳手只能使用一次，当代理移动到下一个房间时，它不能返回，因此如果在访问过的房间中有未拾取的扳手，任务可能会变得不可解。
7.结论
本文提出了一种创新的GP解决方案空间，使得可以定义一种启发式搜索方法来解决GP问题。这种新的GP解决方案空间与GP问题中输入规划实例的数量及其大小（即对象数量、状态变量及其域大小）无关。因此，我们的GP作为启发式搜索方法可以处理具有大数值域（例如整数）的大量状态变量。
我们相信，这项工作是朝着在自动规划和编程领域之间建立更紧密联系迈出的一步。本文将经典规划形式化为向量变换任务，这是一种常见的编程任务。根据这种形式体系，计算该任务的顺序计划是计算向量变换操作的组合。同样，计算广义计划是计算向量变换的算法表达。9在这方面，BFGP算法从一个空程序开始，但没有什么能阻止我们从部分指定的广义计划[102]开始搜索，以开发新的在线方法，更好地扩展。事实上，局部搜索方法已经在规划[103]和程序合成[104,68]中取得了成功。
最后但同样重要的是，另一个有趣的研究方向是扩展我们的GP作为启发式搜索方法，以从不同的输入设置开始计算广义计划。例如，从一组计划轨迹计算广义计划，这些轨迹展示了如何解决多个规划问题。我们还对探索将我们的GP作为启发式搜索方法应用于非目标导向的规划问题感兴趣，其中目标是最大化给定的效用函数[115]。在这种特定设置中，可以从近似策略迭代[116]和强化学习[80]中引入思想到我们的框架中。在这方面，我们正在探索将我们的方法扩展到包含实数状态变量的GP问题。我们相信，通过引入实数变量比较的精度概念，并相应地重新定义FLAGS寄存器的更新机制，我们可以解决这类GP问题。