抽象和推理语料库的通用规划

Generalized Planning for the Abstraction and Reasoning Corpus

抽象和推理语料库的通用规划https://arxiv.org/abs/2401.07426

图6展示了GPAR的流水线草图，这是一个两阶段系统，使用GP来解决ARC任务。DSL生成阶段包括一组具有不同节点对象、属性和关系识别的抽象，以为每个ARC任务生成域文件和关联的实例文件，其中动作约束和重复移除确保域文件中只包含有用的动作方案，并使用独特的抽象。在程序综合阶段，通过实例化域文件中描述的动作方案和谓词，在实例文件中声明的对象或用户给定的指针上生成地面规划动作和测试动作，并根据给定的程序行生成goto指令。谓词和参数约束增加了生成的测试动作有用且面向目标的可能性。GP求解器PGP(v)利用用户输入、程序行n、指针Z和新颖性阈值v作为参数来实现应用部分和循环部分编程。PGP(v)的解决方案是一个规划程序Π，通过对每个训练实例中相应的初始状态执行Π，可以将输入图像（初始状态）映射到输出图像（目标状态）。如果在测试实例中验证Π为解决方案，那么Π就是一个经过验证的解决方案。

摘要

抽象和推理语料库（ARC）是一个通用的人工智能基准，由于其对流体智能的要求，侧重于推理和抽象，对于纯粹的机器学习方法来说具有挑战性。在这项工作中，我们引入了一个ARC求解器，即广义规划抽象推理（GPAR）。它将一个ARC问题视为一个广义规划（GP）问题，其中解决方案被形式化为带有指针的规划程序。我们使用标准的规划域定义语言（PDDL）来表达每个ARC问题，并结合外部函数表示以对象为中心的抽象。我们展示了如何通过以行动模型、谓词、参数和规划程序的有效结构的限制形式针对ARC的领域知识来扩展GP求解器。我们的实验表明，GPAR在ARC的以对象为中心的任务上优于最先进的求解器，显示了GP的有效性和PDDL在模拟ARC问题方面的表达能力。ARC基准提供的挑战激励了研究，以推进现有的GP求解器并理解与其他规划计算模型的新关系。代码可在github.com/you68681/GPAR上获得。

引言

抽象视觉推理任务已被用于理解和衡量机器智能（Małki´nski和Ma´ndziuk 2023；Barrett等人，2018；Moskvichev，Odouard和Mitchell 2023）。其中一个任务，由Chollet（2019）引入的抽象和推理语料库（ARC），仍然是一个开放的挑战。ARC任务对机器来说具有挑战性，因为它们需要对象识别、抽象推理和过程类比（Johnson等人，2021；Acquaviva等人，2022）。ARC包含1000个独特的任务，每个任务由一小部分（通常为三个）输入输出图像对组成，用于训练，通常有一个或偶尔有多个测试对用于评估（图1）。每幅图像都是一个2D像素网格，有10种可能的颜色。ARC任务需要根据核心知识先验（包括对象性、目标导向性、数字和计数、拓扑和几何）从几个示例中推断出潜在的规则或程序。

Chollet（2019）提出了一种假设性的ARC求解器，该求解器包括一个程序综合引擎，用于在“类人的推理领域特定语言（DSL）”中生成候选解决方案。很少有成功的求解器采用这种方法。受到人类解决ARC任务策略的启发（Johnson等人，2021；Acquaviva等人，2022），Xu、Khalil和Sanner（2023）提出了一种以对象为中心的方法，即基于图的DSL表示的抽象推理与图抽象（ARGA），并执行约束引导搜索以找到DSL中的程序来解决任务。ARGA展示了相当大的泛化能力和高效的搜索。然而，由于DSL的表达能力有限，其性能在某些ARC任务上比Kaggle竞赛的第一名解决方案（top quarks 2020）更差。该算法在有向无环图中搜索，以合成手工制作的DSL上的程序解决方案，其中每个搜索节点代表对其父节点应用的图像转换。

广义规划（GP）是一种程序综合方法，研究一组问题的有效解决方案的表示和生成，非常适合于ARC（Srivastava、Immerman和Zilberstein，2008；Hu和De Giacomo，2011；Jiménez、Segovia-Aguas和Jonsson，2019）。解决方案，称为广义计划，可以形式化为带有指针的规划程序（Segovia-Aguas、Jiménez和Jonsson，2019），其中条件语句以及循环和分支结构允许紧凑地表示解决方案。GP求解器的最新进展显著提高了搜索效率，使得GP能够应用于新的具有挑战性的基准测试（Lei、Lipovetzky和Ehinger，2023）。

在这项工作中，我们提出了一种名为广义规划抽象推理（GPAR）的ARC求解器，它将每个ARC任务建模为一个广义规划问题，并采用最先进的规划器进行程序综合。我们改进了现有的图抽象，以提高对象意识，并引入了一种基于规划域定义语言（PDDL）（Haslum等人，2019）的新型DSL，其中混合声明式和命令式建模语言相结合，以保证足够的表达能力，并简洁地表示转换函数。我们的主要贡献是：1）一种基于广义规划的解决抽象推理任务的新方法，它在ARC基准测试上实现了最先进的性能；2）基于PDDL的编码，使得可以采用替代规划模型进行视觉推理；3）使用其他ARC求解器可以用来减少解空间大小的新型ARC领域知识。

背景

规划域定义语言PDDL是几类不同规划问题的实际标准建模语言，它允许使用自动规划求解器来找到将初始状态映射到转换系统的一个目标状态的规划（Haslum等人，2019）。PDDL将规划问题的表示分为两部分，一部分是定义谓词和动作方案的域D，包括前提条件和效果，其参数可以用常量对象的类型化系统实例化；另一部分是定义对象、初始状态和目标公式的问题或实例I，目标公式包含一组目标状态。通过更改任何问题定义元素：对象、初始状态或目标条件，可以创建具有相同域的不同问题。

PDDL divides the representation of a planning problem into two parts,

a

domain

predicates

action schemes

problem

instance

objects

initial state

goal formula

通过应用动作可以遍历诱导的转换系统。实际上，一个计划通常由一系列动作组成。要适用，动作前提条件需要在某个状态下为真，并且通过合并动作的效果来生成结果状态，其中谓词的一些基本原子变为真或假。前提条件和效果通常通过一阶逻辑中的公式来描述。众所周知，某些效果可以通过备选语言或模拟器更简洁地描述，这些语言或模拟器更适合对复杂的数值操作进行推理，例如Dornhege等人（2009）。我们使用带有外部函数的PDDL，其表示使用命令式语言指定，以表达ARC任务的复杂前提条件和效果（Frances等人，2017）。

图2展示了一个ARC任务片段的PDDL域和实例文件。动作方案和谓词的参数前面有“?”符号，外部函数前面有“@”符号。

广义规划GP旨在解决同一域D上的一组有限的经典规划问题P，其中每个实例I可能在初始状态I、目标条件G或对象∆上有所不同。GP解决方案是一个单一的程序，为每个经典规划实例生成一个有效的计划。

带有指针的规划程序带有指针的规划程序Z，其中每个指针索引P中的一种对象类型，紧凑地描述了GP的可扩展解空间（Segovia-Aguas等人，2022）。规划程序Π是一系列可编程指令，即Π = ⟨w0, . . . , wn−1⟩，给定最大程序行数n。

指令wi，其中i是程序行的位置，0 ≤ i < n − 1，可以是从指针或常量对象的动作方案实例化的规划动作az、操纵指针的RAM动作ar、返回谓词解释的测试动作、用于非顺序执行的goto指令，或总是编写在最后一行的特殊终止指令。goto指令是一个元组goto(I′, y)，其中I′是目标行，y是一个命题，捕获最后执行的RAM或测试动作的结果。我们建议读者参考Segovia-Aguas、Jiménez和Jonsson（2019）以获取完整的规范。

当Π开始在一个实例It上执行时，程序状态对(s, i)被初始化为(It, 0)，其中It是实例It的初始状态。同时，指针等于零，所有的y都被设置为False。当wi = az或wi = ar时，指令wi ∈ Π将(s, i)更新为(s', i + 1)，其中如果wi适用，则s'是结果状态，否则s' = s。

当wi = go(I', y)且y在s中成立时，指令将程序状态重新定位到(s, I')，否则定位到下一行(s, i + 1)。如果Π在(s, i)终止并满足目标条件，即wi = end且G ⊆ s，那么Π就是It的解决方案。如果Π是每个实例It ∈ P的解决方案，那么Π就是GP问题P的解决方案。

图3的上半部分展示了一个由我们的求解器发现的规划程序，该程序使用两个指针no和co迭代节点和颜色对象，将任何大小为1的节点（像素集合）的颜色更新为黑色。下半部分展示了单个规划动作如何表示大量对象实例化的动作执行。内部循环，第0到4行，将大小为1的节点no的颜色co更新为黑色。如果动作UpdateColor的前提条件为假（见图2），那么动作的效果将不会执行。当no指向最后一个节点对象时，第3行无法增加指针，然后执行第5-7行，将no设置为第一个节点，并让co指向下一个颜色。当所有颜色都尝试过后，程序将结束。

ARC的抽象

抽象使GPAR具有对象意识，允许动作一次性修改一组像素，而不是单独修改，从而减小了搜索空间。对象内聚力是人类视觉理解的核心（Spelke和Kinzler，2006），而从事ARC任务的人类似乎会想出涉及对象和对象关系的解决方案（Acquaviva等人，2022；Johnson等人，2021）。然而，ARC任务的部分挑战来自于有多种方式解释图像，不同的任务可能需要不同的“对象”。因此，我们考虑多种可能的抽象表示。与Xu、Khalil和Sanner（2023）一样，我们将图像表示为表示对象及其空间关系的节点的图。

受Xu、Khalil和Sanner（2023）的启发，我们考虑以下抽象：1）4-连接，将4-连接组件视为节点，排除背景；2）8-连接，将8-连接组件视为节点，排除背景；3）同色，将所有相同颜色的像素视为一个节点，无论它们的连接性如何；4）多色，将所有非背景颜色视为相同，用于形成4-连接和8-连接组件（因此允许创建多色节点）；5）垂直和水平，分别形成列或行的节点，由相同颜色的非背景像素组成；6）像素，将每个像素视为一个节点；7）图像，将整个图像视为一个节点；8）最大矩形，识别可以在4-连接组件内刻画的最大的矩形作为一个节点，然后在非背景和背景区域中将剩余的像素作为4-连接组件处理。

不同的节点定义可以弥补某种抽象的限制，如图4（左）所示，只有4-连接抽象是合理的。然而，对于给定的ARC任务，两种抽象可能会产生相同的节点，如图4（右）所示。为了避免重复，我们只考虑一种抽象，如果它至少对一个训练实例产生了不同的大小、颜色或形状的节点表示。

节点属性。每个识别的节点都与基本属性相关联，包括颜色、大小和形状。形状可以是单个像素、正方形、矩形、水平线、垂直线、左对角线、右对角线或未知。为了解决涉及计数或排序对象的任务，还指示具有最大和最小大小、奇数和偶数大小以及最频繁和最不频繁出现的颜色的节点。

对于一些抽象，上述属性是不合适的，使用替代属性。对于多色节点，省略颜色属性。当考虑像素节点或图像节点时，只识别最频繁和最不频繁的颜色。对于像素节点，我们使用额外的属性来表示图像几何，表示哪些节点位于图像边界、中心对角线、中间垂直和中间水平线上，并检测和移除可能是噪声的像素（定义为大小为1像素的4-连接组件）。

领域特定语言

PDDL利用一阶逻辑的一个子集，这是一个强大的工具，用于表示推理目的的知识。它提供了一种结构化且简洁的方式来表达对象和属性之间的关系（Genesereth和Nilsson，1987；Levesque，1986）。PDDL通过单个域文件和一组有限的实例文件描述每个ARC任务，每个输入输出图像对都有一个实例文件。域文件包含节点及其属性之间的关系，建模为谓词，以及节点转换，由动作方案建模。动作方案和谓词通过实例文件中指定的对象实例化，其中实例化谓词的合取公式描述了表示输入图像的初始状态，以及建模目标图像配置的目标状态。

对于一个ARC任务，表1显示了可用的对象及其类型，而表2展示了可用的谓词来建模节点属性及其关系。我们区分了可以被测试动作解释以条件goto指令的谓词，由testp列指示，以及其主要目的是在我们的DSL中编码知识的谓词。表3介绍了我们的DSL中包含的主要动作方案的一个子集，其中前提条件或效果由外部函数实现，要么检查某些动作的适用性，要么促进节点转换。我们编码了低级和高级动作的混合，其中一些高级动作编码了复杂的转换，否则需要多个低级动作。这使得求解器能够在适当的抽象级别上进行推理，并在可能的情况下降低程序复杂性。例如，SwapColor和CopyColor可以通过地面动作UpdateColor实现，并附加程序逻辑来操纵指针，但这需要增加编码解决方案的程序行数。

每个抽象都与其各自的动作和谓词集相关联，完整描述可在补充材料中找到。我们还考虑了两个额外的抽象，以实现复杂的移动、扩展和一致节点操作，其中两个节点定义与4-连接抽象相同。这些只有在更简单的抽象中找不到解决方案时才会尝试。

动作修剪抽象可以在一个域中引入不相关的动作。例如，对于图1中的第一个任务，不应该包括涉及改变节点位置的动作，而在第二个任务中，应该避免与颜色更新相关的动作。Xu、Khalil和Sanner（2023）讨论了一个类似的想法，其中如果在搜索过程中新生成的节点无法满足通过比较每个抽象定义的节点生成的一组约束，那么这个节点将被剪枝。GPAR支持他们所有的约束。然而，我们在生成域文件时获取并使用动作约束来剪枝不相关的动作方案，而不是剪枝生成的节点。

我们主要考虑三个约束，基于所有节点的位置、颜色或大小在训练输入和输出图像中是否保持不变。如果在训练集中上述任何一个属性都为真，那么涉及移动、颜色或大小更新的相关动作将被剪枝。还包括一些额外的约束来剪枝不适用于给定抽象的动作；例如，当输入图像中没有一致的图案（具有相同颜色、大小和形状的节点）时，将避免InsertNode。参见补充材料，了解与每个约束相关的动作完整列表。

程序综合

我们使用并改进PGP(v)求解器（Lei、Lipovetzky和Ehinger，2023）在每个ARC任务的训练实例的规划程序空间中进行搜索。一旦求解器返回一个解决所有训练实例的程序，我们就使用测试实例来评估解决方案。求解器核心引擎是一个启发式搜索算法，从空程序开始，尝试一次编写一条指令，直到找到解决方案。PGP(v)使用动作新颖性排名的概念来扩大搜索范围，如果新生成的规划程序的最频繁动作重复次数大于给定的界限v，那么就会被剪枝。

谓词和参数约束谓词约束限制了测试动作允许的参数。这个动作返回程序中谓词的解释，随后用于条件goto指令。谓词约束在搜索开始之前确定，以确保只编写相关的测试动作。我们限制了一个描述节点属性的谓词，它可以被测试动作解释，当且仅当在所有训练和测试输入图像中有两个节点具有该属性的不同值。如果所有图像节点的属性值都由一个谓词描述，那么该谓词的解释将不会是有帮助的goto指令的条件，因为解释值总是真的。例如，在图1的第三个任务中，一个有效的条件应该是节点颜色谓词的解释，而不是节点大小谓词，因为输入图像中的所有节点都是大小为1。

参数约束确保如果一个节点颜色或大小谓词在测试动作中使用，那么选择的参数描述了存在于所有训练和测试输入图像中的属性。这些约束防止过度拟合程序只在输入实例的一个子集上工作，增加了解决方案程序的泛化能力。例如，在图1的第二个任务中，对大小为3的节点进行条件设置不会导致有效的计划，因为测试实例中的节点大小为2。在这种情况下，应该使用其他条件来创建一个解决方案，将每个节点向下移动一步。

结构限制对程序结构的限制是减少搜索空间对称性的有效策略（Lei、Lipovetzky和Ehinger，2023）。我们通过将规划程序分为两部分来采用结构限制：应用部分和循环部分。应用部分可以用规划动作、测试和goto指令编写，循环部分有一系列指针操作和goto指令，以确保所有可能的指针值组合的迭代，然后是一个终止的end指令。

我们在搜索开始之前根据给定的指针编写循环部分。在应用部分，指令序列受到以下规则的约束：1）测试动作必须后跟一个goto指令；2）第一行只能编写一个测试动作；3）一旦编写了来自DSL的动作，后续行必须用来自DSL的动作编写，或者后跟循环部分。为了解决不需要条件的场景，我们包括一个虚拟的test(true)动作，其解释总是真的。在GPAR中，程序行数n指的是应用部分的行数，而不是整个程序。

图5展示了一个具有复杂逻辑的规划程序的规划过程：规划动作ExtendNodeDirection仅在第一个测试属性为假（第0行）且第二个测试空间关系为真（第2行）时执行，总共使用三个指针。这些限制伴随着使求解器不完整的警告。即使不使用限制，现有的ARC方法已经是不完整的，因为它们的DSL的表达能力限制了可以找到的解决方案的类型。

启发式函数受益于与像素相关的谓词，我们利用像素信息来指导搜索。每次生成新程序时，我们执行它，并引入一个启发式函数hp，该函数通过计算与目标状态不同的像素数量，并对已从初始状态更改但尚未与目标状态中的值匹配的进一步像素进行惩罚，超越了目标计数启发式。这与手段-目的分析（Newell和Simon，1963）中的想法非常相似，倾向于使当前状态抽象更接近目标状态的程序。我们使用hp来指导求解器使用的搜索算法，并用hln启发式打破平局，这促进了DSL中定义的动作方案的应用。求解器和hln的完整细节可以在Lei、Lipovetzky和Ehinger（2023）中找到。

指针上的实例化GPAR支持指针上的部分实例化，其中谓词或动作模式中的一组参数被指针替换，其他参数被对象替换，如图3所示的规划动作。这发生在用于索引对象类型的指针数量少于该对象类型指定的参数数量时。部分实例化允许测试动作为循环和分支修复特定属性，并自然地支持参数绑定（Xu、Khalil和Sanner，2023），而无需在我们的DSL中进行额外的语法扩展。

系统概述

图6展示了GPAR的流水线草图，这是一个两阶段系统，使用GP来解决ARC任务。DSL生成阶段包括一组具有不同节点对象、属性和关系识别的抽象，以为每个ARC任务生成域文件和关联的实例文件，其中动作约束和重复移除确保域文件中只包含有用的动作方案，并使用独特的抽象。在程序综合阶段，通过实例化域文件中描述的动作方案和谓词，在实例文件中声明的对象或用户给定的指针上生成地面规划动作和测试动作，并根据给定的程序行生成goto指令。谓词和参数约束增加了生成的测试动作有用且面向目标的可能性。GP求解器PGP(v)利用用户输入、程序行n、指针Z和新颖性阈值v作为参数来实现应用部分和循环部分编程。PGP(v)的解决方案是一个规划程序Π，通过对每个训练实例中相应的初始状态执行Π，可以将输入图像（初始状态）映射到输出图像（目标状态）。如果在测试实例中验证Π为解决方案，那么Π就是一个经过验证的解决方案。

实验

作为一个基准，我们使用Xu、Khalil和Sanner（2023）引入的160个以对象为中心的ARC任务的子集。这些任务进一步分为：1）重着色任务，涉及改变对象颜色；2）移动任务，涉及改变对象位置；3）增强任务，涉及改变对象的方面，如大小或图案。图1显示了每个类别的示例任务。

因素

在GPAR中，PGP(v)将n、v和Z作为参数。程序行数n的范围从3到10，其中n = 3的有效Π配置为v = 1，因为n = 3时Π中包含的每个指令只能出现一次，例如一个测试动作、一个goto指令和一个规划动作。对于n = 4，合理的配置包括v = 1和v = 2，因为一个规划动作可以出现两次。对于n 4，v的值范围从1到3。表4中给出了所有可能的Z组合，其中只引用了对象类型NODE、COLOR和M-DIRECTION，因为它们是设计动作方案中参数的典型规格。搜索空间的复杂性与n和v的值成正比。n和v的上限值确保了搜索空间足够大，可以覆盖大多数解决方案，同时仍然是可处理的。

可行的参数组合和有效的DSL作为PGP(v)的输入。对于每个ARC任务，可能的组合按复杂性递增的顺序执行，从较低的n和v值、较少的指针和较简单的抽象（例如，在8-连接抽象之前考虑4-连接）开始，每个任务的时间限制为1800秒。我们将遇到的第一个Π视为解决方案，以生成测试输出图像进行验证。我们的方法保持了搜索空间的可处理性，并确保我们找到了最简单的解决方案。

Kaggle挑战赛的第一名模型和ARGA被用作最先进的基线。所有实验都在一台时钟速度为2.00 GHz Xeon处理器的云计算机上进行。对于Kaggle第一名模型和ARGA，每个任务的时间限制为1800秒，选择模型生成的最高得分的候选者作为最终解决方案。

解决方案的综合

表5显示了GPAR、ARGA和Kaggle获胜者的训练和测试准确率。如果模型能够找到一个解决给定任务的所有训练实例的解决方案，我们在训练中将其评为“正确”，如果其解决方案也在测试实例上给出正确的基本事实输出，我们在测试中将该模型评为“正确”。在训练中，GPAR在重着色类别中表现优于其他模型，并且在测试实例上优于所有其他方法。GPAR是唯一解决了一半以上任务的规划器，总体训练准确率为53.75%，测试准确率为50.63%。GPAR还展示了出色的泛化能力，训练和测试准确率之间的差距最小。在测试中，GPAR独家解决了16个任务，与Kaggle获胜者和ARGA分别重叠解决了13个和20个任务，所有求解器共同解决了32个任务，如补充材料中的图8所示。

GPAR在重着色类别中具有明显优势，其中解决方案主要通过描述属性（如大小、形状和颜色）的谓词的条件命令式程序紧凑实现。对于移动类别，当需要节点之间的动态属性时，空间关系的描述仍然具有挑战性，例如中心、角落和区域。同时，一些任务需要定义了大量数值参数的移动动作，这在我们的DSL中目前没有得到很好的支持。增强类别涉及形状变换，包括重新缩放、完成和类比复制，这些在基于DSL的命令式程序中难以实现。所有现有的规划器都在这个类别中挣扎，训练和测试准确率都低于50%。

与之前的模型一样，GPAR在训练和测试之间显示出一些差距，这意味着解决训练集的解决方案不能泛化以在测试实例上产生正确的结果。图7显示了一个例子，其中GPAR未能泛化，因为4-连接和8-连接抽象都可以解决训练实例；然而，只有8-连接抽象为测试实例提供了正确的解决方案。鉴于训练实例，这个任务的正确解决方案是不明确的。

在GPAR在测试中解决的任务中，超过50%的任务只需要新颖性阈值为1（v = 1）和只有三行程序（n = 3）。低新颖性阈值意味着大多数任务可以在没有重复动作的情况下解决，而程序行数的减少表明只需要很少的条件和/或动作就可以产生解决方案（44/81个任务只需要一个条件）。这表明了GPAR使用的DSL和PGP(v)求解器的效率，这也为其高泛化性能做出了贡献。补充材料中的图9说明了测试中GPAR解决的任务的v和n的分布。

补充材料中的图10比较了ARGA、Kaggle第一名和GPAR在测试中所有已解决任务（“全部”）、测试中所有三个模型解决的子任务（“公共”）和测试中仅由给定模型解决的子任务（“独有”）之间扩展节点的数量。对于GPAR，扩展节点的数量是针对每个抽象和合理参数组合的执行累积的，直到遇到第一个解决方案Π。

GPAR扩展的节点比ARGA多，但比Kaggle第一名的所有已解决任务少。如果对第一个返回解决方案的扩展节点数量感兴趣，GPAR的性能差异很大，如补充材料中图11的最左边部分所示。由所有三个模型解决的“公共”任务通常需要GPAR扩展较少数量的节点，这对于图11中间显示的第一个返回解决方案也是如此。仅由GPAR解决的任务往往需要大量的扩展节点，甚至超过了Kaggle方法中观察到的数量。然而，对于第一个返回的解决方案，扩展节点的数量仍然相对较低，如图11的最右边部分所示。相反的分布表明，在发现正确的解决方案之前，对不正确的抽象和参数进行了大量的探索。

结论

我们利用现有的广义规划求解器来综合带有指针的程序，这些指针代表了具有分支和循环的表达性解决方案，用于ARC任务。我们展示了如何利用实际的规划语言来建模对象感知的抽象，从而在ARC上取得了最先进的性能，具有更大的泛化结果。识别最有用的抽象仍然是一个开放的问题。在未来，可以定义新的启发式方法，通过从DSL表示中进行放松来指导程序的搜索，并且可以探索与其他规划计算模型的联系，以提高视觉推理性能。