A Review of Machine Learning for Automated Planning

https://www.icaps-conference.org/competitions/ IPC,有关Planning的国际规划大赛

A Review of Machine Learning for Automated Planning¶

自动化计划（AP）是人工智能的一个分支，负责研究执行给定任务的有序行动集合的计算综合。AP于50年代末出现，是对状态空间搜索，定理证明和控制理论进行研究的结果，旨在解决机器人技术和自动演绎的实际需求。斯坦福学院的问题求解器STRIPS（Fikes和Nilsson，1971年）发展成为控制自主机器人Shakey的计划组成部分（Nilsson，1984年），完美地说明了这些影响的相互作用。从Shakey时代到现在，AP已经产生了代表计划任务的公认标准以及解决这些问题的有效算法（Ghallab等，2004）。

（1）学习计划**行动模型**

自动计划员需要对计划任务进行准确的描述。这些描述包括在环境中可以执行的操作的模型，环境状态的规范以及要实现的目标。在现实世界中，执行某个动作可能会导致许多结果，对环境状态的了解可能是不完整的，而目标可能没有完全定义。对于大多数实际问题，提前生成计划任务的精确定义是不可行的。

（2）学习**搜索控制**。

•现成的计划者通常无法扩大规模或无法提供高质量的解决方案。通常，在AP中寻找解决方案的过程是*PSpace-complete*问题（Bylander，1991，1994）。当前最先进的计划者试图通过（1）接地操作和（2）在独立于域的启发式方法指导下执行搜索过程来通过可达性分析来应对这种复杂性。但是，当对象数量很大时，无法在合理的时间内遍历生成的地面搜索树。此外，在启发式信息知之甚少的情况下（例如某些子目标之间具有强大交互作用的域），这种分析会产生误导。特定领域的搜索控制知识已被证明可以改善规划人员在这些情况下的可扩展性（Bacchus和Kabanza，2000； Nau等，2003）。定义搜索控制知识通常比定义计划任务更加困难，因为它不仅需要解决任务，还需要专业知识，

自从AP研究开始以来，机器学习（ML）一直是克服这两个知识获取问题的有用工具。可以在（Zimmerman和Kambhampati，2003）中找到对受益于ML的AP系统的全面调查。

目前，人们对使用ML改进计划有了新的兴趣。2005年举行了首届国际计划系统知识工程竞赛（ICKEPS），并于2008年在**国际计划竞赛（IPC）**中开设了以Learning为基础的计划人员竞赛之路。此外，在国际自动计划和调度会议（ICAPS）内定期举办了有关计划和学习的讲习班。即使此审查包括用于计划和学习的经典系统，主要还是着重于介绍AP机器学习的最新方法。

AP的目标是生产出在遇到不同类型问题时可以选择的求解器。AP生成求解器，这些求解器利用环境动力学模型来推理不同环境中的不同任务。AP任务由两个元素定义：

•The domain, that consists of the set of states of the environmentStogether with the set of actionsAthat indicates the transitions between these states.

•The problem, that consists of the set of factss0∈Sthat indicates the initial state of the environmentand the set of factsG⊆Sthat indicates the goals of the AP task.

正确定义AP任务后，看起来应该很容易通过在状态转换图中搜索路径来解决，这是一个经过充分研究的问题。但是，在AP中，此**state-transition graph**状态转换图通常会变得很大，以至于难以进行搜索。解决这类问题的算法的复杂性随状态数的增加而增加，状态数与问题变量的数目（问题的对象和谓词的数目）成指数关系。在90年代中期5之前，计划者无法在可接受的时间内合成具有十多个动作的计划。

在90年代后期，由于 reachability planning graph（Blum和Furst，1995）可到达性规划图的出现，规划发生了显着的扩大。这一发现允许开发可在多项式时间内计算的强大的独立于域的启发式算法（Hofmann和Nebel，2001a； Bonet和Gef ^ er，2001）。最近的发现，例如搜索地标的自动提取（Porteous和Sebastia，2004年）和符号模式数据库的自动构建（Edelkamp，2002年），提高了计划者，速度和质量性能。使用这些功能的规划人员通常可以在几秒钟内合成一百个行动计划，但是可扩展性限制仍然存在于AP甚至是经过深入研究的领域（例如*Blocksworld）*.

当对象相对较多时，对于计划人员而言就变得充满挑战。

一方面，当前与领域无关的启发式算法计算起来很昂贵。在启发式方法具有误导性的领域中，这种效果更加明显。在这些领域中，计划人员花费大部分计划时间来计算无用的节点评估。

另一方面，鉴于这些与领域无关的技术是基于行动基础的，因此计划者当问题对象**and/or**和/或操作参数的数量达到一定大小时，搜索树将变得棘手。这些问题使与领域无关的计划者难以应用于各种实际问题。

物流应用程序需要与数百个车辆和位置同时处理数百个对象（Florez等，2010），这使得在每个搜索节点中计算评估功能变得不可行。 ML has a role to play in capturing useful control knowledge(捕获有用的policy所对应控制结构) skipped by the domain-independent techniques在这种情况下，ML在捕获由独立于域的技术跳过的有用控制知识中可以发挥作用。

*知识表示。*首先，必须定义机器学习过程将学习的知识类型。在本文中，我们考虑了AP的ML的两个不同目标，即为计划者提供服务的动作模型和指导计划者寻找解决方案的搜索控制。其次，必须决定如何表示所学知识。在这种情况下，必须做出两个代表决定：

（a） *代表语言。*用于对目标概念和体验进行编码的一种表示法。因为AP任务通常以谓词逻辑描述，所以这是用于编码AP概念的最常用的表示语言。也就是说，虽然程度较小，但也使用其他语言，例如描述逻辑或时间逻辑。

（b） *功能空间。*ML算法考虑学习目标概念的一组功能。在AP中，这些功能通常是用于定义AP任务的动作，状态和目标的域谓词。

*汲取经验。*如何收集学习示例。在AP的情况下，学习示例可以由计划系统自主收集，也可以由外部代理（例如人类专家）提供。实现一种自主收集学习示例的机制是一个复杂的过程。使用计划者收集经验是一个未解决的问题，主要是因为要确保使用给定的域模型来解决AP问题的可解决性与原始AP任务一样困难。随机探索经常使AP任务的状态和动作空间采样不足。AP动作通常会提供前提条件，这些前提条件只能由特定的动作序列来满足，这些特定的动作序列偶然被选择的可能性很小。
*学习算法。*如何从收集的经验中捕获模式。不同的方法可以提取这些模式。归纳学习通过对观察到的例子进行概括来构建模式。分析学习使用先验知识和演绎推理来构建模式，以解释学习示例中的信息。混合归纳分析学习结合了两种先前的学习技术，从而获得了两者的好处：当可获得先验知识时，泛化的准确性更高；使用观测到的学习数据来克服先验知识的不足。在设计用于AP归纳学习的学习算法时，最常用的技术是，但是基于AP任务的domain定义，也使用分析和混合方法来构建对收集的学习示例的解释。
开发所学知识。自动系统如何从学到的知识中受益。对前三个问题中的每一个做出的决定都会影响所学知识。如果学到的知识不完善，则必须通过保证可靠利用的机制加以应用。对于AP，知识的不完善可能是多种情况的结果：某些表示选择可能不足以表达给定条件的相关知识。

域; 收集学习经验的策略可能会遗漏目标知识的大量示例；否则学习算法可能会陷入局部最小值，或者无法在合理的时间和内存要求内捕获目标知识的模式。在这些情况下，直接使用所学知识可能会破坏计划过程。规划和学习系统需要配备各种机制，以使尽管学习到的知识存在缺陷，它们也可以尽可能强大地进行规划。

学习计划行动模型¶

AP算法需要正确和完整的动作模型，这些动作模型指示了世界的状态转换。从头开始构建计划行动模型既困难又耗时，即使对于AP专家而言也是如此。另一种方法是使用ML，这样人们就不必手动编写动作模型了。本节回顾了用于自动定义AP动作模型的ML技术。综述通过动作效果的随机性和环境状态的可观察性对技术进行了分类。

*动作效果。*在许多计划任务中，无法假设确定性的世界动态。在规划领域中，包括随机过程（例如投掷硬币或掷骰子）或不确定性结果（例如现实世界中的机器人导航）就是这种情况。
*state可观察性。*在许多计划任务中，处理完整，准确的环境状态描述是不可想象的。由于传感器的故障或无法完全感知世界，当前状态的某些部分可能会混乱或丢失。例如，在现实世界中控制机器人时。

因此，我们为AP建模定义了四类：

完全可观察的环境中的确定性操作；
在部分可观察的环境中的确定性动作；
在完全可观察的环境中的随机动作；
可观察部分环境中的随机动作。

尽管存在其他分类的可能，例如根据学习目标进行分组（前提条件，效果，效果条件，结果的概率...），但我们认为这一分类对于计划目的很有用，因为每个类别对应于不同的计划范式。图通过给出一些示例实现总结了计划行动建模系统的分类。该表并不是详尽的列举，因此表中的系统仅是示例。

模型	特征		实施方式
	长处	弱点
确定性影响完整的状态可观察性	•学习复杂性在理论上是有限的 •高效的计划算法 •完整涵盖学习示例	•表现力差	LIVE（Shen and Simon，1989），EXPO（Gil，1992），OBSERVER（Wang，1994）
确定性影响部分状态的可观察性	•完整涵盖学习示例	•表现力差 •低效的计划算法	ARMS（Yang等，2007），（Amir and Chang，2008），（Mourao等，2008），LOCM（Cresswell等，2009）
概率效应完全状态可观察性	•丰富的表现力•高效的计划算法	•不存在的在线学习	（Oates and Cohen，1996），TRAIL（Benson，1997），LOPE（Garcla-Martlnez and Borrajo，2000），（Pasula et al。，2007），PELA（Jimenez等，2008）
概率效应部分状态可观察性	•富有表现力	•高计划和学习复杂性	（Yoon和Kambhampati，2007年）

**图**用于计划动作建模的系统的实现。

完全可观察的环境中的确定性操作(The learning task+mplementations)；

重要！和程序生成有关，QNP之类的也是确定性规划，问题假设条件已经给完整，不需要sensor探测不断扩充，不需要探索，不需要走一步看一步。就像围棋一样规则已经定下来。

当然也可以实例中学习抽象通用方法，重用已有的不断扩充

ML_AP

在部分可观察的环境中的确定性动作(The learning task+mplementations)；

不关心

在完全可观察的环境中的随机动作(The learning task+mplementations)；

不关心

可观察部分环境中的随机动作(The learning task+mplementations)

不关心

Learning Planning Search Control Knowledge 学习规划图的控制结构知识(类比tf计算图)¶

学习AP的搜索控制知识的四种不同方法（宏动作，广义策略，广义启发式函数和层次分解方法）

学习macro-actions¶

1.知识表示。宏动作被表示为动作模型的新动作，因此它们遵循AP动作的*谓词逻辑*表示。动作*ai* 和*aj* 组合为一个宏动作

2.学习实例。学习示例是解决方案计划p，该计划计划由实例化操作序列组成，这些实例化操作对应于状态转换序列,从而I→ G

模型	特征		实施方式
	长处	弱点
Macro-actions	•对错误的学习知识有较强的把握 •适用于不同的计划者	•Utility problem	REFLECT（Dawson and Silklossly，1977），MORRIS（Korf，1985），MacroFF（Botea等，2005a），Marvin（Coles and Smith，2007），（Newton et al。，2007）
Generalized Policies	•标准关系分类算法	•Engineering effort to整合不同的搜索算法和与领域无关的启发式方法	（Minton，1988年），PRIAR（Kambhampati and Hendler，1992），HAMLET（Borrajo and Veloso，1997），（Khardon，1999），（Martin and Geffner，2000），DISTILL（WinnerandVeloso，2003），OBTUSEWEDGE（Yoon等人，2007），CABALA（de la Rosa等人，2007），ROLLER（de la Rosa等人，2008）
Generalized Heuristics	•标准关系回归算法 •轻松集成不同的搜索算法和启发式方法	•可读性差	（Yoon等，2006），（Xu等，2007）
Decomposition Methods	•富有表现力	•无需全自动学习	CAMEL（Ilghami等，2002），HDL（Ilghami等，2006），HTNMAKER（Hogg等，2008）

Overview of AP systems that benefit from ML for the extraction of domain-specific search control

3.学习算法。学习宏动作的算法从解决方案中提取动作子序列，并对它们的出现进行计数以捕获最有用的子序列。通常，提取动作子序列的过程定义了两个参数：

• *l，*宏动作的长度。l的最小值是l = 2，因为宏动作应至少具有两个动作。l的最大值是学习示例中最长解决方案的长度。实际上，该值必须较小才能有用。

• *k，*可以从解决方案计划中跳过的操作数。该参数允许学习系统提取宏观行动，而宏观行动最多只能从解决方案中忽略*k个*不相关的中间行动。实际上，k的较小值会减少宏动作的数量，但是k值太小可能会跳过有用的宏动作发生。

对于这些参数，从具有*n个*动作的计划中提取长度为l的宏动作的复杂度为（W第一个因素是在al + k大小的窗口内枚举长度为l的宏动作的成本。第二个因素是成本沿着解决方案计划滑动窗口的方法，可以使用类似的方法从部分有序计划中提取宏观作用（Botea等人，2005b）。

4.开发所学知识。宏动作可以由任何现成的计划者立即使用，因为宏动作可以作为标准动作包含在动作模型中。包含宏动作可能会破坏原始动作模型的时间和质量性能。当宏动作导致搜索深度减小而不能弥补分支因子的增加（the utility problem）时，就会发生这种情况。当前的学习宏动作的系统通过实验评估此问题。例如，他们定义了一组与目标问题类似的AP问题，并且如果学习到的宏观行动可以改善计划者在这些问题上的表现，那么可以认为填充行动模型是一个不错的选择。这种解决 theutility problem问题的方法最初是在学习控制规则的系统中引入的（Minton，1988）。

实现macro-action¶

自从AP开始以来，就广泛地使用了宏动作。第一个宏观动作学习系统是STRIPS（Fikes等，1972）。它使用以前的解决方案计划作为宏观行动来解决随后的问题，并监视现实世界中计划的执行情况。后来，MORRIS（Korf，1985年）通过添加过滤试探法来修剪生成的宏动作集，从而扩展了这种方法。这种方法区分了两种类型的宏动作：在搜索过程中频繁发生的S宏和在宏事件中发生不多的T宏，但是在启发式算法中建立了一些弱点。REFLECT系统（Dawson和Silklossly，1977）采用了基于域预处理生成宏动作的替代方法。所有合理的动作组合都被视为宏动作，并通过基本修剪规则进行了过滤。

传统上，宏动作系统在使用宏动作之前先使用离线方法来生成和过滤宏动作，但是一些系统已尝试使用ML在搜索过程中过滤宏动作。在（McCluskey，1987）中，作者使用了块；在（Garcia-Duran等，2006）中，他们使用了控制规则来决定何时应用宏动作。

最近的工作成功地将宏与最新的启发式搜索计划器集成在一起。这些作品包括IPC-2004的竞争对手M acro FF（Botea等，2005a，2007）。在这里，通过识别静态连接的抽象组件来提取部分排序的宏动作，然后使用离线过滤技术来修剪宏动作列表。Marvin （Coles and Smith，2007），也是IPC-2004的参与者，使用动作序列记忆技术在线生成宏动作，使计划者无需进行任何探索即可从高原逃脱。向导（Newton et al。，2007）使用遗传算法来生成和过滤独立于基线计划程序的宏动作集合。算法*正克* 最近，分析法也已用于学习启发式计划程序FF的宏动作（Muise等，2009）。

Generalized Policies¶

通用策略是将计划上下文（有时也称为元状态）映射到要在上下文中应用的首选操作。计划上下文通常包括当前状态以及目标集。通过针对每个计划上下文重复应用首选操作，准确的通用策略可以解决给定域中的任何问题，而无需进行任何搜索。

¶

学习通用策略

• 知识表示。表示计划上下文时的关键问题是选择*要素空间。特征空间是用于学习过程的谓词集。该集合必须足够通用以捕获领域5的相关知识，并且必须足够具体以使学习变得容易。在AP中，特征空间通常由谓词组成，用以描述计划任务的当前状态和目标。所述PRODIGY系统富含额外谓词，称为特征空间*metapredicates （明顿，1988）。*元谓词*捕获有关计划上下文的有用知识，例如当前适用的运营商或仍需要实现的目标。学习推广政策的最新作品已经扩展metapredicates的定义，包括从启发式的规划理念，好像metapredicates用于捕捉*宽松计划的行动*在当前状态（Yoon等，2008）或捕获组的*有益行动*中当前状态（de la Rosa等，2008）。

代表广义策略的主要方法有两种。

通用策略可以表示为一组规则，这些规则捕获了要在给定计划上下文中应用的首选操作。在这种情况下，广义策略被正式定义为元组n *= ，*其中

-L用于描述不同计划环境的一组文字。它定义了学习期间使用的特征空间。

-R是一组规则，其中规则的标题是要应用的操作，而主体是一组谓词，这些谓词描述了应在其中应用操作的计划环境。

通用策略也可以表示为一组具有距离度量的检索实例，以检索相似实例。这是CBR（基于案例的推理）计划者遵循的表示方法。即使该表示能够捕获更多特定的域规则性，也具有需要适当的相似性度量的严重缺陷。处理大量决策实例集合时，效用也是一个问题，因为随着集合变大，搜索相似实例所需的时间也会增加。

广义策略的第二种表示形式被正式定义为元组n = < L，I，D> ，其中：

-L用于描述计划环境的一组文字。它定义了*特征空间。*

-I是一组元组，i = ，其中ci是实例化的计划上下文，ai是在*ci中*应用的实例化操作*。*

-D is a distance metric that computes the distance between two different planning contexts. Givena new planning contextc, the policy decides the actionaito execute incby computing the closesttuple inIand returning its associated actionai, as shown in:

\(\pi(c) = arg_{a_i} \mathop{min}\limits_{<c_i,a_i>\in I} D(c,c_i)\)

两种方法通常以谓词逻辑表示计划上下文，因为这是AP任务的自然编码。谓词逻辑提供了定义额外谓词的机制，这些谓词可以丰富计划环境。作为这些额外谓词的一个示例，图14显示了 Blocksworld的wellplaced（Block）谓词的*定义*（Khardon，1999）。这个概念不在 Blocksworld 域的原始编码中，但是定义紧凑的广义策略很有用.

在谓词逻辑中学习这类谓词仍然是一个悬而未决的问题，因此必须对其进行手工编码。计划系统使用了其他表示语言，可以成功地学习这些概念。已经显示出用于描述对象类的语言为学习这些概念提供了有用的偏见。这些语言包括*概念语言*（Martin和Ge ^ ner，2000）和 分类语法（Mcallester和Givan，1989），它们提供运算符来定义谓词上的递归概念，例如* 运算符。*例如，在*Blocksworld 域中，可以使用这些语言以非常紧凑的方式定义*放置*适当的块的有用概念.

用*时间逻辑*表达计划知识也被证明是有用的。TLPLAN就是这种情况（Bacchus和Kabanza，2000年）。不幸的是，学习*时间逻辑中的*计划知识尚未解决。

• 学习实例。学习示例是针对培训问题的解决方案。学习示例包括元组< ci ，〇i + i> ，其中*ci* 是计划上下文，而*〇i* + i 是在上下文*ci上*应用的操作*。*

• 学习算法。当策略由一组规则组成时，学习任务与ILP任务非常相关。学习通用策略可以定义为对域中每个动作的逻辑程序的归纳。该逻辑程序捕获何时应用该动作。该逻辑程序中规则的头由动作名称和参数组成，主体是计划上下文中最能涵盖学习示例的文字的子集。可以通过学习示例的覆盖范围将这种学习任务实现为启发式搜索。当策略由一组相关实例组成时，学习任务将存储和管理该组实例。在这种情况下，学习大量实例实际上可能适得其反，因为难以存储和管理它们，并且由于在确定使用哪个实例来解决特定问题方面涉及困难。解决此问题的方法是对存储的实例进行后处理，以仅管理最相关的实例。例如REPLICA（Garcia-Duran等，ress）从实例中提取一组原型，或DISTILL（Winner和Veloso，2003），通过归纳和合并解决方案计划来构建高度压缩的实例库。

•开发所学知识。通用策略可用于直接选择要应用于给定计划上下文的操作。但是，当学到的通用策略不完善时，其应用可能无法解决此类早期系统中的问题。这些系统学习了控制规则，以指导探索搜索树的计划。控制规则是IF-THEN规则，它建议在树探索期间进行节点选择，修剪或排序。一组控制规则可以看作是*部分*通用政策，因为它们未针对所有可能的规划环境提供行动建议。当给定的控制规则建议不完善时，通常会阻止计划者找到解决方案。为了更有效地利用通用策略，最近的工作已将学习到的策略用作Beam-Search或Limited Discrepency Search等搜索算法中的评估功能。这些搜索算法允许计划将学习到的知识提供的指导与其他建议来源（例如与领域无关的启发式方法）相结合。

实现Generalized Policies¶

有一组系统可以归纳学习控制规则。其中归纳学习编程（ILP）是最流行的学习技术。G rasshopper 系统（Leckie和Zukerman，1991）使用F 油（Quinlan和Cameron-Jones，1995）来学习指导神童计划者的控制规则。也有分析系统：神童/ EBL 模块（明顿，1988年）了解到搜索控制规则的PRODIGY 从正确和错误决策的几个例子规划师。小号tatic（Etzioni，1993）获得控制规则而没有解决任何问题。它仅使用基于解释的学习（EBL）来分析动作前提条件和效果之间的关系。为了克服纯归纳法和纯分析法的局限性，一些研究人员试图将它们结合起来：基于该原理的开拓性系统是LEX-2（Mitchell等，1982）和M eta -L ex （Keller，1987）。）。A x A-EBL（Cohen，1990）结合了EBL和归纳法。它首先使用EBG学习控制规则，然后通过学习示例对其进行完善。D olphin （Zelle and Mooney，1993; Estlin and Mooney，1996）是A x A-EBL 的扩展，它使用F 油作为归纳学习模块。H amlet （Borrajo和Veloso，1997）系统将演绎和归纳相结合。首先，它使用EBL学习通常过于具体或笼统的控制规则，然后使用归纳法对规则进行泛化和专门化。E vo CK（Aler et al。，2002）使用*遗传编程*来发展H amlet 学习的规则并产生更有效的搜索控制。

学习广义策略的问题最早由Roni Khardon研究。Khardon的L2A CT （Khardon，1999年）通过将决策列表学习算法（Rivest，1987年）扩展到关系环境，为*Blocksworld* 和*Logistics* 领域引入了通用策略。第一种方法存在两个重要的弱点：（1 ）它依靠人类定义的背景知识来表达关键特征软域，例如Blocksworld上的谓词（block1，block2）或i ^ place（block），以及（2）学习的策略没有当问题的规模增加时，可以很好地概括。Martin和Geffner解决了*Blocksworld中的*这些限制通过将广义策略的表示语言从谓词逻辑更改为*概念语言*来学习递归概念（Martin and Gef ^ er，2000）。

最近，广义策略学习的范围已在多个领域中增加，从而使该方法可与最新的计划者竞争。这一成就归功于两个新思想：（1）策略表示语言中包含了额外的谓词，可以捕获更有效的特定领域知识；（2 ）学习策略不是贪婪地应用，而是在启发式搜索算法的框架内应用。一个突出的例子是O btuse W 边缘系统（Yoon等，2007），它是IPC-2008学习轨迹的最佳学习者。该系统通过宽松的计划图丰富了当前状态的知识，并使用学习到的策略在“最佳优先搜索”中生成超前状态。[R 奥勒（de la Rosa等，2008）将学习广义策略的问题定义为两步标准分类过程。第一步，分类器捕获要在不同计划上下文中应用的首选运算符。在第二个中，另一个分类器在给定域5的不同计划上下文中捕获每个操作员的首选绑定。这些上下文由从给定状态的宽松计划图中提取的有用操作集，仍未实现的目标以及计划任务5的静态谓词定义。

还存在通过规划实例的集合表示广义策略的系统，如AP的CBR系统。基于实例的AP系统通常在各种域中都不具有竞争力，因为它们存在必须定义在不同类型的域中都能很好工作的适当相似性度量的缺点。PRIAR系统（Kambhampati和Hendler，1992）建议将计划的修改与生成计划结合起来。OBTUSEWEDGE/ ANALOGY（Veloso and Carbonell，1993）介绍了将推导类比应用于规划。它存储了计划跟踪，以避免在将来解决问题时出现故障路径。要检索类似的计划痕迹，OBTUSEWEDGE/ ANALOGY 使用最小前提条件为它们建立索引，以实现一组目标。基于案例的计划系统PARIS（Bergmann和Wilke，1996）提出引入抽象技术来将案例组织起来存储在分层存储器中。该技术提高了案件修改的灵活性，从而增加了单个案件的覆盖范围。DISTILL（Winner和Veloso，2003年）将示例计划合并到称为*dsPlanner* 的结构中*。DISTILL将计划转换为参数化的if语句，并搜索已经存储在*dsPlanner 中的每个if语句以合并它们。如果学到的*dsPlanner* 是准确的，则可以直接使用它来解决域中的任何问题，而无需进行搜索。卡巴拉（德拉罗莎等人，2007）使用启发式计划中的计划搜索过程中，以对象为中心的解决方案计划（称为类型序列）对节点进行排序。另一位基于实例的学习者REPLICA 使用受关系数据挖掘中使用的度量启发的关系距离，实现了“ 最近原型学习” （Garcia-Duran等人，ress）。OAKPlan（Serina，2010年）使用紧凑的图形结构来编码规划问题。该结构提供了规划问题拓扑的详细描述，并允许学习者基于内核功能定义选择性检索过程。

在（de la Rosa等人，2009）中，最近描述了一种计划系统，该系统能够从两种方法（规则或实例）中的任何一种所代表的广义政策中受益。该系统查询用于修复*宽松计划*缺陷的策略*，然后将最终放松的计划用作“ *最佳优先搜索” 中的基础宏操作*。*

Generalized Heuristics¶

在AP中使用启发式功能将解决方案计划的搜索集中在看起来最有前途的搜索节点上。用于AP的启发式函数计算从给定搜索节点到满足目标的节点的距离的估计。可从轻松任务的解决方案成本中直接得出AP的与域无关的启发式功能。

AP任务最常见的放松方法是**忽略操作的删除效果**。如今，大多数启发式计划者都依赖此想法来实施他们的启发式方法。由于此方法与领域无关，因此无法捕获规划领域的奇异之处。

本节介绍如何获取使用ML捕获特定领域知识的AP启发式方法。它着重于启发式算法，以寻找AP中最流行的搜索方法，即**前向状态空间**搜索。

学习广义启发式函数

• 知识表示。它们是状态s的函数*H（s; A; G），动作模型*A 和目标集*G，它们估计从s开始并使用A的动作来实现目标*G 的成本。谓词逻辑*是自然的编码AP启发式功能，因为它们表达了有关AP任务的当前状态，目标和操作的知识。还使用了集中于对象属性的表示语言，例如*分类语法。

实现Generalized Heuristics¶

学习实例。学习示例由元组组成，其中si是当前状态

和*CI* 是实现这些目标的实际成本*GI* 从国家*SI。*

•学习算法。学习算法的目的是概括学习示例中捕获的成本值。由于要从学习示例中概括的目标概念是数字，因此该学习任务对应于回归任务。当学习实例以谓词逻辑表示时，可以使用标准的关系回归算法，例如学习关系回归树（Blockeel等，1998）。

•开发所学知识。这种方法的主要优点是，可以将学习到的知识直接与AP的其他标准指导资源（例如，独立于域的启发式方法）组合。所学的知识是人类难以理解的。

在（Yoon等人，2006）中，作者通过线性回归建立了广义启发式函数。他们学习针对特定领域的校正\(\Delta (s;A;G) =\sum_i w_i * f_i(s;A;G)\)到*轻松计划的启发式*

FF计划者介绍了\(RPH（s; A; G）\)（Hoffmann and Nebel，2001b）。这些校正表示为要素的加权线性组合，其中wi是权重，fi表示计划上下文的不同要素。回归示例包括对通过FF计划器获得的不同状态到目标的真实距离的观察。由此产生的启发式功能，

\(H（s; A; G）= RPH（s; A; G）+ \Delta（s; A; G）\)

提供更准确的估计，以捕获特定于域的规则。

以前的方法在搜索算法中使用时会忽略启发式方法的实际性能。即使它在搜索过程中提供了很好的指导，它也可能尝试学习启发式的校正。在（Xu et al。，2007）中，他们提出了一种替代方法，该方法仅在启发式误导给定搜索策略时才考虑学习。通过这种方法学到的启发式方法

\(H(s; A; G)= \sum_i w_i * f_i(s; A; G）\)

仅尝试很好地区分好状态和坏状态，以在“ 波束搜索” 过程中找到目标，而不是尝试精确建模到目标的距离。这种方法实现了以下权重学习策略。对于学习问题解决方案中的每个状态*sj* ，如果sj不包含在搜索的beamj中，则存在搜索错误。在这种情况下，权重像感知的权重一样被更新，因此状态sj将被启发式方法优先使用，并保留在未来的搜索情节中的Beamj中。

Decomposition Methods¶

层次分解方法

解决问题复杂性的扩展策略是将问题分解为更简单的子问题。当找到有效的分解时，解决子问题的成本之和小于直接解决原始问题的成本。分层任务网络（HTN）是对AP任务分解建模的最佳研究方法之一。HTN方法结合了规划任务的分层特定于域的表示形式和用于解决问题的独立于域的搜索策略。

HTN计划者的输入包括一个动作模型，该动作模型对一组*原始动作进行*编码，该*动作*类似于经典计划中使用的STRIPS动作和*任务模型。任务模型定义了一组*方法，这些*方法* 描述了应如何将任务分解为特定域中的子任务。HTN计划者的工作包括利用任务模型将给定的计划任务分解为更简单的子任务，直到生成一系列原始操作为止。图17显示了来自*Blocksworld* 域的HTN描述中的原始动作堆栈和用于任务移动块的方法。此方法通过定义两个子任务将一个块移动到其最终位置：将x从y移到z，从而将块*x* 堆叠从*y开始，以便将*x 堆叠在z上，然后将x从表移动到z，从而从表中拾取块*x* 并将其堆叠在z上。在这两个子任务中，该方法都会*检查*块*x是否*可以直接移动到其最终位置（原始动作*check，check2* 和*checkS）*，并确保将来不会移动x。

当前的HTN计划者，例如SHOP2（Nau等人，2003），可以胜过最新的领域独立计划者，并为诸如灭火之类的许多实际应用提供自然的建模框架（Castillo等人， 2006年），疏散计划（Muiioz-Avila等，1999）或游戏（Nau等，1998）。定义有效的*分解方法*仍然很复杂，因为这些方法反映了该领域的深入知识。图17所示的算子和方法属于块堆叠算法的HTN表示（Erol等，1992）。下面我们回顾一些在HTN规划范式中自动定义分解方法的学习方法。

学习分层分解方法

1.知识表示。一个HTN方法是描述如何分解一个过程*非原始*任务为*基本*任务或简单的*非原始*任务。一种方法，米正式通过三米定义*= <头，preconds，子任务>，其中*头*表示的名称和以分解任务的参数，*preconds 是一个逻辑式表示的方法的先决条件，以及*子任务*是的局部有序序列子任务。如果*head（m）* 匹配*t* 并且*preconds（m），则方法m适用于状态s和任务t对感到满意。将方法m应用于状态s和任务*t的结果*是子*任务subtasks（m）*的序列。*

2.学习实例。学习示例包括一组计划问题，即一组\(< s_0，G>\) 对 ，*其中s〇是初始状态，*G 是一组目标，以及相应的解决方案\(p =（a_1,a_2 ,...a_n）\)。这些解决方案计划可以由人为提供，也可以由经典计划者生成。

3.学习算法。第3节中介绍的学习动作模型前提条件的算法也可以应用于学习HTN方法前提条件。可以通过使用宏的分层层来简化HTN方法分解的版本。按照这种方法引起的分解不会利用HTN的全部表达能力，包括替代分解，递归概念或循环的定义。在这一点上，还没有用于从HTN的完整表达能力中受益的用于学习子任务分解的全自动算法。一些算法需要从人类部分指定的*分解方法*开始，另一些需要层次计划（这意味着以前指定的方法），而另一些则需要某些任务，称为带*注释的任务*规定在AP问题的经典版本中定义HTN任务和目标集*G* 的等价关系。

4.开发所学知识。学习的知识的普遍性水平是使给定的HTN描述选修的关键问题。学习过于通用的分解方法可能会在解决问题时产生无限递归，从而降低了HTN规划相对于传统规划的优势。另一方面，学习过于具体的HTN方法不太可能有效地分解新问题。解决这种折衷的当前方法是基于针对一系列测试问题测量学习模型的性能。

实现Decomposition Methods¶

CAMEL（Ilghami et al。，2002）使用version space*版本空间*算法（Mitchell，1997）学习了HTN *分解方法*和对平面迹线的观察的前提条件。CAMEL被设计用于规划器接收每个任务的多个方法结构域，而不是它们的先决条件。此处的层次结构是事先已知的，学习任务会尝试确定不同的层次结构在哪些条件下适用。此方法需要许多计划跟踪才能完全收敛（完全确定所有方法的先决条件）。CAMEL++（Ilghami等人，2005）使计划人员可以在完全了解方法前提之前开始进行计划。这样，计划者可以使用较少的培训示例来开始解决计划问题。CAMEL和CAMEL++都要求每个输入计划跟踪都需要包含额外的信息，以便学习者可以获取模型。在计划跟踪的每个分解点，学习者需要拥有所有适用的方法实例，而不仅仅是实际使用的方法实例。

HTN域学习（HDL）算法（Ilghami等，2006）在开始时没有有关该方法的任何先验信息。它检查由专家问题解决者产生的分层计划跟踪。对于跟踪中的每个分解点，HDL会检查是否已经存在负责的方法。否则，HDL将创建一个新方法并初始化一个新*版本空间*以捕获其先决条件。实际用于分解相应任务的方法用作肯定示例，而与该任务匹配但前提条件失败的方法则作为相应版本空间的否定示例。

HTN-Maker（Hogg等人，2008）从STRIPS域模型，STRIPS计划程序生成的计划*p* 的集合以及带*注释的任务*的集合中生成HTN领域模型*。带*注释的任务*是一个三元组（n，Pre，Effects），其中*n 是任务，Pre 是一组原子，称为前提条件， Eff 是一组原子，称为效果。HTN-Maker首先通过从初始状态s〇开始应用计划p中的动作来生成状态列表\(s=（s_0，...，s_n)\) 。然后，它遍历这些状态，并且如果存在一个带注释的任务，其影响匹配状态si + n和其先决条件相匹配的状态 \(s_{i+n}\)，它通过（倒退注释任务的影响1 ）先前学习的方法或（2 ）如果没有以前学习过的方法，则执行原始任务。

Learning Planning Search Control in Domains with Uncertainty¶

用不上

Reinforcement Learning¶

RL代理与环境交互以收集经验，并使用适当的算法对其进行处理以生成最佳策略（Kaelbling等，1996； Sutton和Barto，1998）。建立RL代理涉及的决策与AP学习中的决策类似：表示（如何对代理的环境和行为进行编码）；学习实例（代理商收集经验的策略）；学习算法（哪种算法在指定任务上表现最佳）；以及对所学知识的利用（代理如何从所学知识中受益）。与大多数针对AP方法的学习不同，RL为知识获取和知识开发提供了紧密集成的解决方案。这些集成解决方案中的关键问题是确定何时尝试新动作以及何时使用已知动作。exploration-exploitation dilemma，其中 exploration定义为尝试新的动作和exploitation被定义为应用在过去已经成功过的行动。

总体而言，对exploration-exploitation dilemma的良好答案要考虑允许的试验次数。试验次数越多，过早收敛到已知操作的效果就越差，因为它们可能不是最佳的。有关有效exploration-exploitationstrategies的调查，请参见（Wiering，1999； Reynolds，2002）。

Model-Based and Model-Free RL¶

L主要关注在环境模型未知的情况下获得最佳策略，但实际上有两种方法可以进行。基于模型的*RL需要由过渡和奖励模型组成的环境模型。*基于模型的*RL通常依赖于标准*动态规划*算法（Bellman和Kalaba，1965； Bertsekas，1995）来找到提供最优策略的价值/启发式函数。在*基于模型的*RL中的学习被理解为*实时启发式搜索（Korf，1990； Bulitko和Lee，2006； Hernandez和Meseguer，2007），即使用从仿真中获得的信息对价值/启发式函数进行局部更新。

*无模型*RL不需要环境模型。下面，有两种不同的方法可以实现无*模型*RL任务Reinforcement Learning

*将学习行动模型与基于模型的RL相结合。*这种方法学习环境的转换模型，并应用标准的*动态编程*算法来找到好的策略。

• 纯无模型的RL。*在不确定性较大的领域中，学习实现目标要比学习环境模型容易。*无纯模型的RL 算法不会将决策建模为状态的函数（如*值/启发式函数），而是使用成对的< *状态，动作> 函数（*称为*动作值函数）。*的*Q函数，*其提供用于采取动作的预期回报的量度*一个*在状态s，是一个的例子*动作值函数。Q学习（Watkins，1989）是一种著名的无*纯模型*RL算法，它更新了*Q函数*与每个观察到的元组\(<s，a，s'，r>\)（\(s'\)代表新状态，r代表获得的奖励）。 Q学习*使用**贝尔曼方程**完成*Q函数*的更新，其中，a是学习率，它确定新获取的信息在多大程度上覆盖旧信息。当a = 0时，代理不学习任何信息，而当a = 1时，代理仅考虑最新信息。7 是确定未来奖励重要性的折扣因子。7 = 0的因子会使代理变得*贪婪（代理只考虑当前的奖励），而接近1的因子会使代理努力争取长期的高回报。

*纯无模型的*RL也包括*蒙特卡洛*方法（Barto和Duff，1994）。大部分无*模型*RL方法可以确保找到最佳策略，并且每次观察只需要很少的计算时间。但是，它们通常无法有效利用所收集的观测值，并且需要丰富的经验才能实现良好的性能。

考虑到RRL使用的知识表示类似于AP学习中的知识表示，本节将回顾关系增强学习（RRL）（Dzeroski等人，2001； Otterlo，2009）。本节专注于*无模型的纯*RRL，因为在第3节中已经讨论了学习关系行为模型的技术。有关基于模型的RRL的更多说明，请参见（Boutilier等，2001； Wang等，2007； Sanner和Kersting，2010年）也称为关系，符号或一阶动态规划。

1.知识表示。学到的知识以*一阶策略n：S ^ A* 的形式表示，该*策略*将以谓词逻辑编码的关系状态映射到首选动作，然后再应用该动作来实现一组*一阶目标。与针对AP的通用策略（第4节）不同，RRL策略不包含有关不同目标的信息。RRL策略仅捕获如何解决特定任务或一组特定任务，例如具有不同对象数的同一任务。因此，当目标的性质发生变化时，RRL要求从头开始学习，或者至少需要某种*转移学习（Taylor和Stone，2007； Mehta等，2008）。转移学习 定义为利用来自一个或多个源任务的数据来提高另一目标任务的学习性能。

甲*阶策略*可以被隐式地表示为*一阶Q函数Q（）= R* 该映射对状态-动作*的S -甲*到其预期回报*R.* 这种表示是密切相关的启发式的概念AP中使用的函数，用于将状态映射为实现目标所需支付的费用（负回报）的估算值。在AP中，可以通过忽略操作的*删除*效果从问题表示中自动提取此成本估算。

2.学习实例。学习示例由元组组成，其中ai是在状态s ^处施加的动作，s ^ + i是结果状态，ri 是获得的奖励。RRL中的学习示例通常是从随机探索中生成的。

3.学习算法。Model- ^ ee RRL有不同的方法：

• q值函数的关系学习。*这种方法使用关系回归来概括值函数。图18显示了一个关系回归树，当在三个块的*Blocksworld中*求解*on（Block，Block）*上的一组任务时，该树捕获了动作*move（Block，Block）*的*q值

• 最佳策略的关系学习。*另一种方法是直接学习该策略。这种方法需要**关系分类(PONG的动作分类网络)**而不是**关系回归*。这种方法的优势在于，通常，与理解结构化域的价值功能相比，理解策略要容易得多。图19显示了一个RRL策略，该策略捕获何时选择动作*move（Block，Block）来解决三个*Blocksworld 域中*on（Block，Block）*上的一组任务是最佳的。

implementations¶

关于学习关系*Q函数，*已经尝试了不同的关系回归算法：

•关系回归树（Dzeroski等，2001）。对于每一对*（动作，关系目标），从一组形式为（state，q-value）*的示例中构建回归树。树的叶节点表示*q值*的预测。树的测试节点表示要实现预测所必须具备的事实。

•具有关系距离的基于实例的算法（Driessens和Ramon，2003年）。这项工作实现了k近邻预测。该预测为收集的示例的*q值* 计算加权平均值。用于预测的权重与到示例的距离成反比。使用的距离可以处理状态和动作的关系表示。

•关系核方法（Gartner等，2003）。这些方法使用可增量学习的 高斯过程*进行贝叶斯回归，以将（状态，动作）对映射为*q值。图内核被用作状态动作对之间的协方差函数，以在关系设置中采用*高斯过程*。

对于直接学习相关的政策，（Dzeroski等，2001）采用关系决策树来确定哪些行为是在不同的环境最优，实现特定任务时S状态。

RL的目的与AP的学习目的紧密相关。但是，RL在解决AP问题时通常表现出两种缺点：

• 可伸缩性。*象征性规划问题的空间状态通常很大。这个空间随着对象和谓词数量的增长而呈指数增长。许多RL算法（例如 *Q学习）*都需要一张表，*该表在状态空间中为每个状态提供一个条目，从而限制了它们对AP问题的适用性。解决此限制的方法是使用关系模型，该模型采用与符号计划相同的状态表示形式，就像在RRL中所做的那样。

• *泛化。*RL专注于实现特定目标的学习。每次目标更改时，RL代理都需要从头开始学习，或者至少要学习*迁移学习*过程。RRL并非完全如此。假定RRL使用一阶谓词表示目标，则RRL代理可以在具有其他对象的任务中进行操作，而无需重新调整其学习的策略，尽管可能需要进行额外的培训才能获得最佳（甚至可接受的）性能水平。甚至在*基于模型的*RL 的情况下，代理还学习环境模型并利用它来更有效地学习策略。习得的模型通常用于生成有关如何探索或计划轨迹的建议，以便代理可以获取更高的回报。什么时候*基于模型的*技术应用于RRL（Croonenborghs等，2007b），它们产生的符号动作模型与AP中学习的相似。在这种情况下，主要区别在于以下事实：AP用标准的计划表示语言学习动作模型，而解决问题的方法则由现成的计划者完成。

尽管RRL取得了进步，但将RRL应用于计划问题仍然是一个未解决的问题。在像*Blocksworld* 这样的复杂计划任务中，RRL代理花费大量时间来探索动作，却没有学到任何东西，因为没有遇到任何奖励（目标状态）。目前，通过两种方法可以缓解RRL中随机探索的局限性。第一个使用人类定义的*合理政策的*痕迹为学习提供了一些积极的奖励（Driessens和Matwin，2004）。第二种将转移学习应用于关系环境（Croonenborghs等，2007a）。

综上所述，RRL专注于针对特定目标的学习策略，例如*Blocksworld的**on（X，Y），但*无法解决*必须实现交互目标的问题，例如*在（X， Y），on（Y，Z），on（Z，W）。*在传统上在AP中解决的这类问题中，特定目标的实现可能会使以前满足的目标无法实现。必须以特定的顺序实现这种目标（就像*Sussman异常中*所发生的那样）。*据我们所知，没有一个报告的RRL方法具有自动捕获有关目标交互的知识的机制。

Discussion¶

在90年代中期前5小号的ML尽数用于AP获悉提高规划者的性能搜索控制知识。在此期间，计划人员实施了不了解情况的搜索算法，因此ML帮助计划人员在许多领域中实现了更好的性能。在90年代后期，规划界对ML的兴趣下降了，原因有两个。强大的独立于域的启发式方法的出现提高了计划者的绩效。突然之间，评估ML收益的基准发生了巨大变化。也就是说，现有的关系学习算法效率低下，并且在多个领域中的表现都很差。

如今，受AP在实际问题中的应用以及关系学习的成熟所鼓舞，人们对计划学习的兴趣再次兴起。2005年，国际规划系统知识工程竞赛（ICKEPS）开始了，2008年，IPC开设了学习路径。在自动规划和日程安排国际会议上定期举办了有关规划和学习的讲习班。ML似乎再次成为应对AP挑战的解决方案之一。

Conclution¶

在本文中，我们重点介绍了AP面临的两个挑战：定义有效的AP行为模型和定义搜索控制知识以提高规划人员的绩效。对于第一个挑战，我们回顾了学习具有多种形式的前提条件和效果的行动模型的系统。这些系统通常提供在收集适当的学习示例时有效的学习算法，尽管仍不清楚如何在AP中自动收集良好的学习示例集。当学习导致动作模型不完善时，几乎没有机制可以诊断模型或算法的缺陷以对其进行健壮的计划。

对于第二个挑战，我们回顾了不同形式的搜索控制知识，以改进现成的计划者。已经显示出这种知识可以提高特定领域规划人员的表现。由于不同的计划领域可能呈现出截然不同的结构，因此在一系列领域中学习有效的搜索控制知识仍然具有挑战性。我们还回顾了针对HTN计划者的学习搜索控制，这是控制知识的一种更具表达性的形式，它使用基于特定领域问题分解的不同计划范式。在这种计划范式中，搜索控制知识和动作模型没有在领域理论的定义中分开。

本文还回顾了RRL的技术，RRL是一种类似于AP的RL形式，它使用谓词逻辑来表示状态和动作。尽管当前的RRL技术可以解决关系任务，但与AP技术的学习相比，它们专注于实现一组特定的目标并存在普遍性局限性。此外，他们在解决复杂任务（如AP中传统解决的任务）方面积累了大量经验方面存在问题，在这些任务中，实现特定目标可能会使以前达到的目标无法实现。

6.2未解决的问题

下面，我们提供了一份清单，列出了我们认为是AP学习的未解决问题或未来途径。我们根据本文的四个主要主题对这些问题进行划分：知识表示，学习示例，学习算法和对所学知识的利用：

•知识表示。

在一个集合中查找AP的选修知识表示形式 Domain 仍然是一个未解决的问题。如果所选的表示形式无法在给定的领域中表达关键知识，则学习算法将不会为该领域生成有效的AP知识。例如，在*Blocksworld* 领域中*放置**适当的*区块的概念或在*Logistics中**最终城市的*概念就是这种关键知识的例子域（Khardon，1999）。进一步的研究需要归纳出给定领域的关键知识是什么，以及表达它的合适表示形式。在这方面，（Yoon等人，2008）中提出的工作使用了一系列测试问题，以在学习通用政策时评估规划环境不同特征的效用。

另一个潜在相关的方面是表示语言如何影响学习有效知识的能力。在（Martin和Geffner，2000； Cresswell等人，2009）中，作者展示了使用对象中心表示进行AP学习的影响，但尚未使用诸如SAS +（Helmert，2009）等**新的标准表示代替PDDL**。详细研究。

更具表达性的形式化表示形式，例如**程序**，已经显示了时间公式或层次表示形式来描述抽象结构，例如代表许多AP域有效知识的循环或层次结构。然而，学习这些表示的大多数方法都需要额外的标签，例如标记抽象任务的注释，循环的开始和结束，结束条件等。这种标签不能轻易地从观察到的执行中自动获得。现成的计划者不能直接使用此知识，需要能够利用这种知识的“临时”计划系统。需要进一步学习和为现成的计划者进行汇编。

•学习实例。

实施机制以自动收集AP的学习示例仍然是一个悬而未决的问题。随机探索通常会对AP状态和动作空间进行欠采样。AP动作呈现的前提条件只有特定的动作序列才能满足，这些特定的动作序列偶然被选择的可能性很小。可以从AP培训问题的解决方案中提取学习示例。传统上，这些训练问题是由带有一些参数的随机生成器获得的，以调整问题的难度。这种方法有两个局限性。

（1）保证AP问题的可解决性并非易事。表明从给定的初始状态可以达到目标与解决原始AP任务一样困难。

（2）AP问题生成器的参数是特定于域的。对于不同的AP域，世界对象的数量和类型是不同的，并且调整这些参数以生成高质量的学习示例意味着域的专业知识。

在（Fern等人，2004）中，Random Walks被引入，因为他们不必具有领域专业知识就能获得良好的学习实例。随机游走是一种自动且独立于域的策略，用于自动生成逐渐增加游走长度的问题。但是，在复杂度取决于世界对象数量的域中，这种方法是不够的。另一种方法是使用从先前状态开始的主动学习方法来产生训练问题（Fuentetaja和Borrajo，2006年）。在这种情况下，学习过程会受到上述问题的影响，但是它可以对复杂度取决于世界对象数量的领域中难度不断增加的问题进行随机探索。鉴于域是非对称的，后一种方法可能会产生无法解决的问题，因此，这个问题仍然存在。必须进行进一步的研究以提出更通用的解决方案。

•学习算法。

AP的新ML算法的应用和组合仍然是一个未解决的问题。ML不断开发新的学习算法，并将其潜在地应用于AP。在关系学习的情况下，AP仅受益于**分类和回归**算法，但是现有的关系学习算法几乎涵盖了所有机器学习任务。在AP中尚未探索用于**关系聚类或推断关联规则**的算法（Raedt，2008年）。命题数据的ML算法可以适应AP中使用的关系设置（Mourao等，2010）。

将新的ML算法应用于AP的另一个示例是使用内核函数有效地匹配计划实例（Serina，2010年）。尽管有所有这些新的ML技术，学习算法存在影响学习过程的偏见。用于AP的ML研究可以采取新的研究方向来研究不同学习算法的组合，以减少给定算法偏差的负面影响（Kittler，1998）。

•开发所学知识。

AP学习中的这些开放性问题经常导致学习知识的不完善。如IPC-2008学习轨迹所示，直接应用有缺陷的学习知识可能会损害AP的过程性能。所学知识的应用越贪婪，则AP算法对所学知识的缺陷越敏感。在规划和学习系统的开发方面，最近有一条工作线，旨在建立即使在学习到有害知识的情况下也能确保进行可靠规划的机制。这些系统不仅专注于学习过程，而且专注于所学知识的强大应用。将学到的知识与独立于领域的启发式方法相结合，产生了一个计划系统，该系统在众多领域中都与最新的计划者竞争（Yoon等人，2007，2008）。另一个有趣的研究领域是评估所学域控制知识的质量的机制的开发。这样的机制对于定义不同的利用策略可能是有用的。当前可用于学习的知识的唯一评估机制是经验性的，包括使用学习的知识来解决一组训练示例以估计其性能。除竞争外，在AP中利用已学知识的另一种方法是与最终用户进行交互。混合主动计划系统（Ferguson等，1996； Bresina等，2005； Cortellessa和Cesta，

这次审查的重点是学习AP过程的两个输入，动作模型和搜索控制知识。有全套技术旨在捕获有关AP进程的第三个输入信息的信息。计划识别技术（Charniak和Goldman，1993； Bui等，2002）试图通过观察代理5的行为来推断代理5的目标和计划。传统上，计划识别任务假定存在一个具有可能被识别的计划的空间的库，但是最近的工作不需要使用该库。这些作品（Ram ，irez和Geffner，2009年；Ramirez和Geffner，2010）也可以使用略微修改的规划算法来计算观察到的示例的目标。需要进行进一步的研究，以分析计划识别技术与AP的学习技术之间的关系。

参考

temp¹和文献²。

Relational reinforcement learning(RRL)(Dzeroskietal.,2001),used Q-learning with a relational function approximator, and demonstrated good empirical results in the Blocksworld.

G ↩
C ↩