双层规划的谓词发明

Predicate Invention for Bilevel Planning

双层规划的谓词发明

https://arxiv.org/pdf/2203.09634

摘要

在连续状态和动作空间中进行高效规划是根本性的难题，即使转移模型是确定性的且已知的。缓解这一挑战的一种方法是使用抽象进行双层规划，其中高层搜索抽象计划用于指导在原始转移空间中的规划。先前的工作表明，当以符号谓词形式的状态抽象是手工设计时，双层规划的操作符和采样器可以从演示中学习。在这项工作中，我们提出了一种从演示中学习谓词的算法，消除了手动指定状态抽象的需求。我们的关键思想是通过优化一个可处理但忠实于我们实际高效规划目标的代理目标来学习谓词。我们使用这个代理目标在从语法中提取的谓词集上进行爬山搜索。实验上，我们在四个机器人规划环境中展示了我们学习的抽象能够快速解决保留任务，优于六个基线。

1 引言

分层规划是在具有连续状态、连续动作和长时域的环境中进行决策的强大方法。扩展分层规划的一个关键瓶颈是依赖人类工程师手动编程领域特定的抽象。例如，在双层基于样本的任务和运动规划（Srivastava等人，2014；Garrett等人，2021）中，工程师必须设计（1）符号谓词；（2）符号操作符；以及（3）提出符号操作符不同细化到连续动作的采样器。然而，最近的工作表明，当谓词给定时，操作符和采样器可以从适度的演示数量（50-200）中学习（Silver等人，2021；Chitnis等人，2022）。我们在这项工作中的目标是学习谓词，然后可以用于学习操作符和采样器。

双层规划中的谓词表示底层连续状态空间的离散状态抽象（Li，Walsh和Littman，2006；Abel，Hershkowitz和Littman，2017）。例如，On(block1, block2)是一个抽象，它忽略了block1和block2的精确连续姿态。状态抽象本身对于决策是有用的，但谓词更进一步：与操作符一起，谓词使得可以使用高度优化的领域无关AI规划器（Helmert，2006）。

我们考虑一个问题设置，其中有一小部分目标谓词可用且足以描述任务目标，但对于双层规划实际上是不够的。例如，在块堆叠领域（图1），我们从On和OnTable开始，但没有描述块当前是否被持有或可抓取的谓词。我们的目标是发明新的谓词，以丰富状态抽象，超越仅用目标谓词所能表达的内容，从而在抽象层面上进行更强的推理。

我们应该优化什么目标来学习双层规划的谓词？首先，考虑我们的实际目标：我们希望一个谓词集，使得在使用这些谓词学习操作符和采样器进行规划时，双层规划在任务分布上是快速且成功的。不幸的是，这个实际目标过于昂贵，无法直接使用，因为即使单次评估也需要神经网络采样器训练和双层规划。

在这项工作中，我们提出了一种新颖的代理目标，它与我们实际的双层规划目标深度相关，但对于谓词学习是可处理的。我们的主要见解是，演示可以用于分析近似双层规划时间。为了利用这个目标进行谓词学习，我们借鉴了程序合成文献（Menon等人，2013；Ellis等人，2020），并通过语法进行爬山搜索来学习谓词，搜索由目标引导。在谓词学习之后，我们使用谓词来学习操作符和采样器。所有三个组件随后可以用于新任务上的高效双层规划。

在四个机器人规划环境中的实验中，我们发现从50-200个演示中学习的谓词、操作符和采样器能够在保留任务上实现高效双层规划，这些任务涉及不同数量的对象、更长的时域和比演示中看到的更大的目标表达。此外，使用我们提出的代理目标学习的谓词显著优于受先前工作启发的目标学习的谓词，这些目标基于预测误差（Pasula，Zettlemoyer和Kaelbling，2007；Jetchev，Lang和Toussaint，2013）、双模拟（Konidaris，Kaelbling和Lozano-Perez，2018；Curtis等人，2021）和逆向规划（Baker，Saxe和Tenenbaum，2009；Ramírez和Geffner，2010；Zhi-Xuan等人，2020）。我们与几个其他基线和系统的消融进行比较，以进一步验证我们的结果。

2 Problem Setting问题设置

3 谓词、操作符和采样器

由于代理可以访问转移模型f，优化第2节中描述的目标的一种方法是完全放弃学习，并通过在状态空间X和动作空间A上运行规划器来解决任何保留任务。然而，直接在这些大空间中搜索解决方案是高度不可行的。相反，我们建议使用提供的演示来学习抽象。在本节中，我们将描述允许使用抽象进行快速双层规划的表示（第4节）。然后在第5节中，我们将描述如何学习这些抽象。

我们采用了非常一般的抽象定义（Konidaris和Barto，2009）：从X和A到替代状态和动作空间的映射。我们首先描述一个抽象状态空间SΨ和一个从X中的状态到抽象状态的转换。接下来，我们描述一个抽象动作空间Ω和一个抽象转移模型F : SΨ × Ω → SΨ，该模型可用于在抽象空间中进行规划。最后，我们定义采样器Σ，用于将抽象动作细化回A，即可以执行的动作。请参阅右侧的图表以获取总结。

由Ψ诱导的（离散）抽象状态空间记为SΨ。在整个工作中，我们使用谓词集Ψ，它是给定目标谓词ΨG的超集。然而，只有目标谓词是给定的，并且它们通常非常有限；在第5节中，我们将讨论代理如何使用数据来发明谓词，这些谓词将构成Ψ的其余部分。参见图1（第一个面板）以获取示例。

（2）抽象动作空间和抽象转移模型。我们通过让代理学习操作符来解决这两个问题：

我们将操作符集合记为Ω。参见图1（第二个面板）以获取示例。与STRIPS（Fikes和Nilsson，1971）不同，我们的操作符带有控制器和控制器参数，这将允许我们与下面的任务动作（3）连接。现在，给定一个带有对象集O的任务，所有具体操作符的集合定义了我们任务的（离散）抽象动作空间：

4 双层规划

为了使用抽象的组件——谓词Ψ、操作符Ω和采样器Σ——进行高效规划，我们基于双层规划技术（Srivastava等人，2014；Garrett等人，2021）进行构建。我们使用谓词和操作符在外层搜索抽象计划，并使用谓词和采样器在内层搜索将抽象计划细化到任务解决方案π。

由于向下细化性在我们的设置中不成立，抽象计划πˆ不能保证可以细化到任务的解决方案π，这使得双层规划成为必要。我们现在详细描述规划算法。

规划器的整体结构在算法1中概述。对于找到抽象计划πˆ的外层搜索，记为GENABSTRACTPLAN（算法1，第2行），我们利用STRIPS风格的操作符和谓词（Fikes和Nilsson，1971）来自动推导出AI规划社区普及的领域无关启发式方法，如LMCut（Helmert和Domshlak，2009）。我们使用这个启发式方法在抽象状态空间SΨ和抽象动作空间Ω上运行A*搜索。这个A*搜索被用作抽象计划πˆ的生成器（因此得名GENABSTRACTPLAN），一次输出一个1。参数nabstract控制了在规划器终止并失败之前可以生成的抽象计划的最大数量。

5 从演示中学习

为了在评估时使用双层规划，我们必须在训练时学习谓词、操作符和采样器。我们使用Chitnis等人（2022）的方法进行操作符学习和采样器学习；详见第A.1节和第A.3节。对于接下来的内容，重要的是理解操作符学习是快速的（O(|D|)），但采样器学习是缓慢的，并且两者都需要给定的谓词集。我们的主要贡献是一种谓词发明方法，它在训练管道中先于操作符和采样器学习。

受先前工作（Bonet和Geffner，2019；Loula等人，2019；Curtis等人，2021）的启发，我们从程序合成角度（Stahl，1993；Lavrac和Dzeroski，1994；Cropper和Muggleton，2016；Ellis等人，2020）来解决谓词发明问题。首先，我们定义了一个紧凑的谓词无限空间的表示形式，即语法。然后，我们从该语法中枚举大量候选谓词，首先枚举较简单的候选谓词。接下来，我们在候选谓词的子集上进行局部搜索，目的是识别一个好的最终子集作为Ψ。这一步骤中的关键问题是：我们应该使用什么目标函数来指导候选谓词集的搜索？

5.1 评分候选谓词集

最终，我们希望找到一组谓词Ψ，在我们使用这些谓词学习操作符Ω和采样器Σ后，能够实现高效的规划。即，我们的实际目标是：

其中Ω和Σ是使用我们在第A.1节和第A.3节中描述的Ψ学习的，PLAN是第4节中描述的算法，TIME(·)测量PLAN找到解决方案所需的时间2。然而，我们需要一个可以用于指导候选谓词集搜索的目标，这意味着目标必须被多次评估。由于两个速度瓶颈，Jreal过于昂贵：采样器学习，涉及训练多个神经网络；以及从PLAN内部重复调用REFINE，每个调用都执行回溯搜索以细化抽象计划。

为了克服这种不可行性，我们将使用一个代理目标Jsurr，它比Jreal更便宜，但近似保留了谓词集的排序，即：

其中ETPT缩写为Estimate Total Planning Time（算法2）。ETPT使用候选谓词和诱导的操作符来执行双层规划的第一部分：抽象计划上的A*搜索。然而，对于每个生成的抽象计划，我们不学习采样器并调用REFINE，而是使用可用的演示来估计如果我们学习采样器并调用REFINE，细化成功的概率。由于双层规划在成功细化抽象计划时终止，我们可以使用这些概率来近似总预期规划时间。我们现在详细描述这些步骤。

估计细化概率 ETPT维护一个概率pterminate，初始化为0（第2行），表示在每个生成的抽象计划后规划会终止。为了更新pterminate（第5-6行），我们必须估计PLAN是否会在此步骤之前终止，以及PLAN是否会在此步骤终止。对于前者，我们可以使用。对于后者，由于PLAN仅在REFINE成功时终止，我们使用一个辅助函数ESTIMATEREFINEPROB来近似成功细化给定抽象计划的概率，如果我们学习采样器Σ并调用REFINE。我们使用以下实现：

5.2 候选谓词集的局部搜索

在建立了我们的代理目标Jsurr之后，我们转向如何最好地优化它的问题。我们使用一个简单的爬山搜索，初始化为Ψ0 ← ΨG，并在每一步i中从池中添加一个新谓词ψ：

我们重复直到找不到改进，并使用最后一个谓词集作为我们的最终Ψ。请参阅图2，了解从我们在Blocks环境中的实验中提取的示例。

设计谓词语法 设计谓词语法可能很困难，因为语法的表达能力与在其上搜索的实用性之间存在权衡。对于我们的实验，我们发现类似于Pasula、Zettlemoyer和Kaelbling（2007）的简单语法就足够了，其中包括单特征不等式、逻辑否定和全称量化。详见第A.4节，图1和附录A.7中提供了示例。

生产规则累积的成本使我们得到与每个谓词ψ相关的最终成本，记为PEN(ψ)，其中较高的成本表示具有较高复杂性的谓词。我们在局部搜索期间使用这些成本来正则化Jsurr，权重足够小，主要防止添加既不损害也不改善Jsurr的“中性”谓词。正则化项为Jreg(Ψ)，wreg P ψ∈Ψ PEN(ψ)，其中wreg = 10−4在我们的实验中。

为了生成用于局部搜索的候选谓词集，我们按照成本递增的顺序从语法中枚举ngrammar（实验中为200）个谓词。

6 实验

我们的实验旨在回答以下问题：（Q1）我们学习的抽象在多大程度上有助于规划的有效性和效率，并且与使用其他目标函数学习的抽象相比如何？（Q2）我们学习的状态抽象在性能上与手动设计的状态抽象相比如何？（Q3）学习在演示数量方面有多高效？（Q4）当我们改变规划器配置时，我们的抽象是否有所不同，如果是，如何不同？

实验设置 我们在四个机器人规划环境中评估了10种方法。所有结果均在10个随机种子上取平均值。对于每个种子，我们采样了一组50个评估任务，这些任务涉及比训练时看到的更多对象和更难的目标。演示通过使用手动定义的抽象进行双层规划收集（见下面的Manual方法）。规划总是限制在10秒的超时时间内。详见附录A.6以获取更多细节。

环境 我们现在简要描述环境，更多细节见附录A.5。前三个环境在Silver等人（2021）的先前工作中建立，但在该工作中，所有谓词都是手动定义的；我们在Manual基线中使用相同的谓词。

- **PickPlace1D**：机器人必须拾取块并将它们放置在桌子表面上的目标区域。所有拾取和放置姿势都在一条1D线上。评估任务需要1-4个动作来解决。

- **Blocks**：3D中的机器人必须与桌子上的块进行交互，将它们组装成塔。这是经典块世界领域的机器人版本。评估任务需要2-20个动作来解决。

- **Painting**：3D中的机器人必须拾取、清洗、干燥、涂漆并将小部件放入盒子或架子中。评估任务需要11-25个动作来解决。

- **Tools**：在2D桌子表面上操作的机器人必须使用提供的螺丝刀、锤子和扳手分别用螺丝、钉子和螺栓组装装置。此环境具有无法通过我们的谓词语法建模的物理约束。评估任务需要7-20个动作来解决。

方法 我们评估了我们的方法、六个基线、一个手动设计的状态抽象和两个消融实验。请注意，Bisimulation、Branching、Boltzmann和Manual基线与我们的方法仅在谓词学习方面有所不同。

- **Ours**：我们的主要方法。

- **Bisimulation**：一个基线，通过近似优化双模拟标准（Givan、Dean和Greig，2003）来学习抽象，如先前工作（Curtis等人，2021）。具体来说，此基线学习抽象，以最小化演示中抽象转移模型F适用但对下一个抽象状态做出错误预测的转移次数。请注意，由于目标谓词是给定的，任何抽象下都满足目标可区分性。

- **Branching**：一个基线，通过优化规划的分支因子来学习抽象。具体来说，此基线学习谓词，以最小化演示状态上适用操作符的数量。

- **Boltzmann**：一个基线，假设演示者在（未知）最优抽象下以噪声理性行为（Baker、Saxe和Tenenbaum，2009）。对于任何候选抽象，我们使用规划启发式作为真实成本到目标的代理，计算演示在Boltzmann策略下的似然。

- **GNN Shooting**：一个基线，训练一个图神经网络（Battaglia等人，2018）策略。该GNN接收当前状态x、抽象状态s和目标g。它通过一个在C上的独热向量输出动作a，对应于要执行的控制器，在每个离散参数位置上的所有对象的独热向量，以及连续参数的向量。我们使用行为克隆在数据D上训练GNN。在评估时，我们将输出的连续参数视为具有固定方差的高斯分布的均值来采样轨迹。我们使用转移模型f检查是否达到目标，并重复直到达到规划超时。

- **GNN Model-Free**：一个基线，使用相同的GNN，但直接执行策略而不是shooting。

- **Random**：一个基线，在每一步简单地执行一个带有随机参数的随机控制器。无学习。

- **Manual**：一个oracle方法，使用为每个环境手动设计的谓词进行规划。

- **Down Eval**：我们的一个消融实验，在PLAN（算法1）中仅在评估时使用nabstract = 1。

- **No Invent**：我们的一个消融实验，使用Ψ = ΨG，即仅使用目标谓词进行状态抽象。

结果与讨论 我们在附录A.7中为所有环境提供了学习到的谓词和操作符的真实示例。图3显示，我们的方法在超时内解决了比基线更多的保留任务。这种性能差距的一个主要原因是我们的代理目标Jsurr明确近似了规划的效率。Bisimulation基线的表现不佳尤其值得注意，因为其在文献中广泛存在（Pasula、Zettlemoyer和Kaelbling，2007；Jetchev、Lang和Toussaint，2013；Bonet和Geffner，2019；Curtis等人，2021）。我们更仔细地检查了其失败模式，发现它始终选择好的谓词，但数量不够。这是因为要求操作符在抽象空间中成为完美的预测模型通常不足以确保良好的规划性能。例如，在Blocks环境中，目标谓词与谓词Holding(?block)一起足以在我们的数据上满足双模拟，而从规划角度来看，其他谓词如Clear(?block)和HandEmpty()是有用的。检查GNN基线，我们发现尽管shooting相对于使用GNN model-free是有益的，但性能通常远不如我们的方法。我们进行的额外实验表明，GNN在数据量增加一个数量级时会变得更好。

右侧的图表说明了我们的数据效率。每个点显示10个种子的平均值，标准偏差显示为垂直条。我们通常在仅50个演示中就能获得非常好的评估性能。

在表1中，No Invent的结果显示，正如预期的那样，仅目标谓词对于大多数任务是完全不足的。将我们的方法与Down Eval进行比较，结果表明，假设在评估时向下可细化性适用于PickPlace1D、Blocks和Painting，但不适用于Tools。我们还发现，学习到的谓词（Ours）与手动设计的谓词（Manual）相当，有时甚至更好。例如，考虑PickPlace1D，学习到的谓词比手动设计的谓词好7.5倍。手动设计的谓词是Held(?block)和HandEmpty()，以及始终给定的目标谓词Covers(?block, ?target)。除了发明与Held和HandEmpty等效的两个谓词外，Ours还发明了两个更多的谓词：P3(?block)，∀?t . ¬Covers(?block, ?t)，和P4(?target)，∀?b . ¬Covers(?b, ?target)。直观地说，P3表示“给定的块不在任何目标上”，而P4表示“给定的目标是空的”。P3在拾取的操作符前提条件中使用，这减少了抽象搜索的分支因子。这个前提条件是合理的，因为一旦块已经在其目标上，就没有必要移动它。P4防止考虑不可细化的抽象计划，这些计划将对象“停放”在必须被其他对象覆盖的目标上。

在附录A.8中，我们描述了一个额外的实验，其中我们改变了在抽象搜索中使用的AI规划启发式。我们分析了Blocks中的一个案例，其中发明谓词的变化在初步检查时似乎无关紧要，但实际上对规划效率有重大影响。这一结果强调了使用对下游规划效率敏感的代理目标进行谓词发明的好处。

7 相关工作

我们的工作延续了关于学习决策状态抽象的长期研究（Bertsekas、Castanon等人，1988；Andre和Russell，2002；Jong和Stone，2005；Li、Walsh和Littman，2006；Abel、Hershkowitz和Littman，2017；Zhang等人，2020）。最相关的是那些学习与AI规划器兼容的符号抽象的工作（Lang、Toussaint和Kersting，2012；Jetchev、Lang和Toussaint，2013；Ugur和Piater，2015；Asai和Fukunaga，2018；Bonet和Geffner，2019；Asai和Muise，2020；Ahmetoglu等人，2020；Umili等人，2021）。我们的工作特别受到Pasula、Zettlemoyer和Kaelbling（2007）的影响，他们通过概念语言的搜索来发明符号状态和动作抽象，以及Konidaris、Kaelbling和Lozano-Perez（2018），他们通过利用满足抽象子目标属性的选项的启动和终止集来发现符号抽象。这些先前工作中使用的目标基于自动编码、预测误差或双模拟的变体，这些目标源于抽象应该取代原始转移空间中的规划，而不是指导规划的观点。

最近的工作还考虑了学习多级规划的抽象，如任务和运动规划（TAMP）（Gravot、Cambon和Alami，2005；Garrett等人，2021）和分层规划（Bercher、Alford和Holler，2019）文献中的那些。一些努力考虑学习符号动作抽象（Zhuo等人，2009；Nguyen等人，2017；Silver等人，2021；Aineto、Jimenez和Onaindia，2022）或细化策略（Chitnis等人，2016；Mandalika等人，2019；Chitnis、Kaelbling和Lozano-Perez，2019；Wang等人，2021；Chitnis等人，2022；Ortiz-Haro等人，2022）；我们的操作符和采样器学习方法受到这些先前工作的启发。Loula等人（2019）和Curtis等人（2021）的最新努力考虑了学习TAMP的状态和动作抽象，就像我们做的那样（Loula等人，2019，2020；Curtis等人，2021）。我们工作的主要区别特征是我们的抽象学习框架明确优化了一个考虑下游规划效率的目标。

8 结论与未来工作

在本文中，我们描述了一种学习谓词的方法，这些谓词明确优化了高效的双层规划。未来工作的关键领域包括（1）通过主动学习在线收集更多数据，从更少的演示中学习更好的抽象；（2）扩展语法的表达能力，以学习更复杂的谓词；（3）将这些思想应用于部分可观察的规划问题；以及（4）学习我们在本文中假设给定的控制器。

对于（1），我们希望研究关系探索算法（Chitnis等人，2020）如何作为代理决定执行哪些动作的机制，以构建更好的状态和动作抽象为目标。对于（2），我们可以从程序合成中获得灵感，特别是那些可以学习具有连续参数的程序的方法（Ellis等人，2020）。对于（3），我们可以从最近在部分可观察设置中的任务和运动规划的进展中获得见解（Garrett等人，2020）。最后，对于（4），我们最近提出了一种假设已知谓词从演示中学习控制器的方法（Silver等人，2022）。如果我们能够消除后一个假设，我们将拥有一个完整的管道，用于学习双层规划的谓词、操作符、采样器和控制器。

附录A

A.1 操作符学习

这里我们描述如何假设已经学习了完整谓词集Ψ的情况下学习操作符Ω（Chitnis等人，2022）。该方法对表示形式施加了两个限制，这两个限制共同导致了非常高效的操作符学习（在D中的转移数量上是线性时间）。首先，对于每个CON和每个可能的效果集对(EFF+, EFF−)，最多有一个具有该(CON, EFF+, EFF−)的操作符。这个限制使得无法为同一控制器和效果集学习具有不同前提条件的多个操作符。其次，PAR中的每个参数必须出现在PARCON、EFF+或EFF−中。这个限制防止了建模“间接效果”，即某些对象影响控制器的执行而其自身状态没有改变。尽管这两个限制是有限的，但我们愿意接受它们，因为谓词发明可以补偿。例如，一个发明的谓词可以量化出一个对象，该对象不出现在控制器或效果中，以捕捉间接效果。

A.2 操作符学习扩展示例

我们通过一个扩展示例来结束对操作符学习的讨论。我们从一个小型玩具数据集开始，并使用它来逐步介绍程序中的每个步骤。

直观地说，第一个和第二个转移可能发生在拾取对象（分别是o1或o4）时，而第三个和第四个转移可能发生在存放对象（分别是o1或o8）时。我们首先注意到，我们可以忽略C的连续参数θi，因为它们对操作符学习无关紧要（它们将在采样器学习中使用）。

A.5 附加环境细节

- **PickPlace1D**：在这个玩具环境中，机器人必须拾取块并将它们放置在桌子表面上的目标区域。所有拾取和放置姿势都在一条1D线上。三种对象类型是块、目标和机器人。块和目标有两个特征表示它们的姿势和宽度，机器人有一个特征表示夹爪关节状态。块的宽度大于目标的宽度，目标要求每个块放置时完全覆盖各自的目标区域，因此ΨG = {Covers}，其中Covers是一个二元谓词。只有一个控制器PickPlace，没有离散参数；其Θ是一个实数，表示执行拾取或放置的位置，取决于机器人夹爪的当前状态。每个动作最多更新一个块的状态，基于是否有块在连续参数θ的小半径内。训练任务和评估任务都涉及2个块、2个目标和1个机器人。在每个任务中，机器人有75%的概率开始时持有随机块；否则，两个块都开始时在桌子上。评估任务需要1-4个动作来解决。该环境由Silver等人（2021）建立，但该工作涉及手动定义的状态抽象，我们在本文中不提供这些抽象。

- **Blocks**：在这个环境中，3D中的机器人必须与桌子上的块进行交互，将它们组装成塔。这是AI规划中块世界领域的机器人改编。两种对象类型是块和机器人。块有四个特征：x/y/z姿势和一个表示当前是否被抓取的位。机器人有四个特征：x/y/z末端执行器姿势和手指关节的对称值。目标涉及组装塔，因此ΨG = {On, OnTable}，其中前者是二元谓词，描述一个块在另一个块的顶部，而后者是一元谓词。有三个控制器：Pick、Stack和PutOnTable。Pick由机器人和一个要拾取的块参数化。Stack由机器人和一个要将当前持有的块堆叠在其上的块参数化。PutOnTable由机器人和一个表示桌子表面归一化坐标的位置参数化，表示要放置当前持有的块的位置。训练任务涉及3或4个块，而评估任务涉及5或6个块；所有任务都有1个机器人。在所有任务中，所有块开始时都在桌子上无碰撞的姿势。评估任务需要2-20个动作来解决。该环境由Silver等人（2021）建立，但该工作涉及手动定义的状态抽象，我们在本文中不提供这些抽象。

- **Painting**：在这个具有挑战性的环境中，3D中的机器人必须拾取、清洗、干燥、涂漆并将小部件放入指定的盒子或架子中。五种对象类型是小部件、盒子、架子、盒子盖和机器人。小部件有八个特征：x/y/z姿势、脏污程度（需要清洗）、湿度水平（需要干燥）、颜色、当前是否被抓取的位，以及如果被抓取，则抓取的1D夹爪旋转。盒子和架子有一个特征表示它们的颜色。盒子盖有一个特征表示是否打开。机器人有一个特征表示夹爪关节状态。目标涉及将小部件涂成与盒子或架子相同的颜色，然后将每个小部件放入适当的盒子或架子中，因此ΨG = {InBox, InShelf, IsBoxColor, IsShelfColor}，所有这些都是二元谓词（一个小部件和一个盒子或架子）。该环境有两个物理约束：（1）放入盒子只能成功，如果机器人顶部抓取小部件，而放入架子只能成功，如果机器人侧面抓取小部件；（2）只有当相应的盖子打开时，才能将盒子放入。有六个控制器：Pick、Wash、Dry、Paint、Place和OpenLid。所有六个都由机器人参数化；Pick还由要拾取的小部件参数化，OpenLid由要打开的盖子参数化。Pick有4个连续参数：从该小部件质心开始的3D抓取姿势增量和夹爪旋转。Wash、Dry和Paint各有1个连续参数：分别表示清洗量、干燥量和所需的新颜色。Place有3个连续参数：对应于当前持有的小部件应放置位置的3D放置姿势。训练任务涉及2或3个小部件，而评估任务涉及3或4个小部件；所有任务都有1个盒子、1个架子和1个机器人。在每个任务中，机器人有50%的概率开始时持有随机小部件；否则，所有小部件都开始时在桌子上。此外，在每个任务中，盒子盖有30%的概率开始时打开。评估任务需要11-25个动作来解决。该环境由Silver等人（2021）建立，但该工作涉及手动定义的状态抽象，我们在本文中不提供这些抽象。

- **Tools**：在这个具有挑战性的环境中，在2D桌子表面上操作的机器人必须使用提供的螺丝刀、锤子和扳手分别用螺丝、钉子和螺栓组装装置。该环境具有超出我们谓词语法范围的物理约束，因此测试了学习者在无法克服的向下可细化性缺乏情况下的鲁棒性。八种对象类型是装置、螺丝、钉子、螺栓、螺丝刀、锤子、扳手和机器人。装置有两个特征：x/y姿势。螺丝、钉子、螺栓和三种工具各有五个特征：x/y姿势、形状、大小和一个表示是否被抓取的位。机器人有一个特征表示夹爪关节状态。目标涉及将螺丝、钉子和螺栓固定在目标装置上，因此ΨG包括ScrewPlaced、NailPlaced、BoltPlaced、ScrewFastened、NailFastened和BoltFastened。前三个是二元谓词（一个螺丝/钉子/螺栓和它被放置的装置）；后三个是一元谓词。该环境有三个物理约束：（1）只有当螺丝刀的形状与螺丝足够接近时，才能用螺丝刀固定螺丝；（2）有些螺丝的形状与任何螺丝刀都不匹配，因此这些螺丝必须手工固定；（3）如果三种工具的尺寸太大，则无法拾取它们。有十一个控制器：Pick{Screw, Nail, Bolt, Screwdriver, Hammer, Wrench}、Place、FastenScrewWithScrewdriver、FastenScrewByHand、FastenNailWithHammer和FastenBoltWithWrench。所有十一个都由机器人参数化；Pick控制器还由要拾取的对象参数化，Fasten控制器由螺丝/钉子/螺栓和工具参数化（除了FastenScrewByHand，它没有工具参数）。Place有2个连续参数：对应于当前持有对象应放置位置的2D放置姿势，可以是放在桌子上或装置上（只有当前持有对象不是工具时）。训练任务涉及2个螺丝/钉子/螺栓和2个装置，而评估任务涉及2或3个螺丝/钉子/螺栓和3个装置；所有任务都有3个螺丝刀、2个锤子、1个扳手和1个机器人。评估任务需要7-20个动作来解决。

A.6 附加实验细节

所有实验都在四核Intel Xeon Platinum 8260处理器上进行。所有采样器神经网络都是全连接的，具有两个大小为32的隐藏层，并使用Adam优化器（Kingma和Ba，2014）进行训练，学习率为1e-3，训练1K个epoch。回归网络被训练来预测多元高斯的均值和协方差矩阵；该协方差矩阵被限制为对角线且PSD，使用指数线性单元（Clevert、Unterthiner和Hochreiter，2015）。对于训练分类器网络，我们对数据进行子采样，以确保正例和负例之间的1:1平衡。所有AI规划启发式方法都使用Pyperplan实现（Alkhazraji等人，2020）；除非另有说明，所有实验都使用LMCut启发式。规划参数为Tools的，其他环境的nabstract = 8，Tools的，其他环境的 = 10。

A.7 附加实验结果

表3提供了所有实验的学习时间。表4、5和6分别报告了所有评估任务的成功率、创建的节点数和挂钟时间。

图4分析了我们代理目标函数使用的两个主要特征。详见图注以获取进一步描述。

我们现在逐一介绍我们的四个环境，提供从成功种子中随机选择的一个种子的学习到的谓词和操作符示例。我们还为主方法提供了额外的统计数据，以补充我们提供的其他结果。请注意，评估计划长度统计数据在10个种子和每个种子的50个评估任务上取平均值，标准偏差仅在种子上。

PickPlace1D 我们主方法的统计数据，在10个随机种子上取平均值（标准偏差在括号中）：

- **Ψ中的平均谓词数量（发明的和目标谓词）**：5.9 (0.54)

- **Ω中的平均操作符数量**：2.1 (0.3)

- **评估期间的平均计划长度**：2.44 (0.09)

参见图5以获取随机选择的成功种子的示例学习到的谓词和操作符。

Blocks 我们主方法的统计数据，在10个随机种子上取平均值（标准偏差在括号中）：

- **Ψ中的平均谓词数量（发明的和目标谓词）**：6.0 (0.0)

- **Ω中的平均操作符数量**：4.0 (0.0)

- **评估期间的平均计划长度**：9.17 (0.69)

参见图6以获取随机选择的成功种子的示例学习到的谓词和操作符。

Painting 我们主方法的统计数据，在10个随机种子上取平均值（标准偏差在括号中）：

- **Ψ中的平均谓词数量（发明的和目标谓词）**：22.1 (1.45)

- **Ω中的平均操作符数量**：11.2 (0.6)

- **评估期间的平均计划长度**：14.76 (0.29)

参见图7和图8以获取随机选择的成功种子的示例学习到的谓词和操作符。

Tools 我们主方法的统计数据，在10个随机种子上取平均值（标准偏差在括号中）：

- **Ψ中的平均谓词数量（发明的和目标谓词）**：27.4 (4.39)

- **Ω中的平均操作符数量**：17.8 (0.98)

- **评估期间的平均计划长度**：10.1 (0.12)

参见图9和图10以获取随机选择的成功种子的示例学习到的谓词和操作符。

A.8 改变规划器启发式

表2展示了一个额外的实验，我们在Blocks环境中改变了双层规划器GENABSTRACTPLAN例程使用的AI规划启发式。回想一下，我们的谓词发明方法也使用了GENABSTRACTPLAN，因此它也受到这个启发式变化的影响。所有数字显示了10个种子的平均值。有趣的是，尽管在使用LMCut时性能差距有限，但当使用hAdd时，我们的系统相比Manual显示出巨大的改进（创建的节点数减少了30倍以上）。这些结果特别令人惊讶，因为A*与hAdd通常被认为不如其他启发式搜索算法。

检查学习到的抽象，我们发现我们的方法发明了四个具有直观意义的一元谓词：Holding、NothingAbove、HandEmpty和NotOnAnyBlock，以补充给定的目标谓词On和OnTable。与Manual相比，Manual具有与国际规划竞赛（IPC）（Bacchus，2001）相同的谓词和操作符，我们看到了以下差异：Clear被省略4，而NothingAbove和NotOnAnyBlock被添加。

我们观察到，NothingAbove和NotOnAnyBlock是标准IPC表示中使用的谓词的逻辑变换。这促使我们进行了一个单独的、仅符号的实验，我们在其中收集了IPC块世界问题，并将其转换为使用这些学习到的谓词。我们发现，使用A*和hAdd，使用我们学习到的表示进行规划比使用IPC表示要快得多。例如，在Pyperplan中打包的最难问题中，包含17个块，使用我们的操作符进行规划大约需要30秒和841个节点扩展，而使用标准编码需要560秒和17,795个扩展。我们还尝试了Fast Downward（Helmert，2006）（再次使用A*和hAdd）在一个更难的IPC 2000问题中，包含36个块。使用我们学习到的表示，规划在12.5秒后大约7,000次扩展后成功，而使用标准编码，规划器在2小时超时内未能找到计划。请注意，所有这些结果都特定于Blocks、A*和hAdd，而这正是重点：即使使用非传统的搜索算法和启发式组合，我们面向规划器的方法也能学习到优化给定环境中给定规划器效率的抽象。

为什么当使用A*和hAdd进行规划时，我们学习到的谓词和操作符比标准谓词和操作符表现更好？首先，我们注意到，在实践中使用hAdd与A*与手动定义的PDDL表示是非常罕见的，因为hAdd是不可采纳的，并且会因高估问题而受到严重影响（Bonet和Geffner，2001）。然而，我们工作中有趣的现象是，我们的系统能够学习到一种抽象，能够应对这种搜索算法和启发式组合的缺陷。为了进一步理解这一点，我们做出以下观察：

- 在这两种情况下，规划器几乎每次拾取操作都必须从一个局部最小值中逃脱。例如，在一个初始手为空的5个块的小问题中，使用标准操作符进行规划时，找到的计划中的状态的hAdd值为[9, 13, 9, 11, 6, 8, 4, 5, 2, 1, 0]，而使用我们学习到的操作符时，值为[14, 16, 11, 10, 6, 7, 4, 4, 2, 1, 0]。注意值的交替增加和减少；规划的理想情况是这些值平滑地减少。

- 在拾取后的状态中，hAdd值在这两种情况下都一致地高估了真实的到目标成本。例如，在使用标准操作符进行第一次拾取后，hAdd值和真实到目标成本分别为13和9；对于学习到的操作符，它们分别为16和9。

- 这里的主要区别在于：在使用标准操作符的状态中，hAdd值有时会低估真实的到目标成本。在上面的例子中，初始状态的hAdd值为9，但真实的到目标成本为10。在更难的问题中，这些低估更频繁地发生；例如，在一个包含20个块的问题中，在找到的计划中有8个案例，其中拾取前的状态低估了真实的到目标成本。相比之下，我们学习到的操作符的hAdd值在我们分析的问题中似乎从未低估真实的到目标成本。

原文链接：https://arxiv.org/pdf/2203.09634