可能有界次优启发式搜索

−+++人工智能267（2019）39可能有界次优启发式搜索Roni Sterna，Renni，Gal Dreimana，Richard Valenzanoba以色列内盖夫本古里安大学加拿大多伦多大学Ar ticleinf oa bst ra ct文章历史：2017年3月10日收到收到修订版，2018年6月15日接受，2018年在线发售2018年关键词：人工智能启发式搜索为搜索问题找到一个最佳的解决方案通常是可取的，但可能太困难了在许多情况下。在这种情况下，一种常见的方法是试图找到一个次最优性有界的解决方案，其中一个参数定义了 一 个 解 决 方 案 离最优解的距离可以，同时也可以接受。一个很少被研究的替代方法是试图找到一个可能是最优的解，其中参数δ定义了解的最优性所需的置信度 本文探讨了这一选择，并介绍了概念一种可能有界次优搜索（probably bounded-suboptimal search，pBS search）算法。这样的搜索算法接受两个参数，和δ，并且输出具有至少1δ成本最多为1 最优解的时间。一个通用的算法框架， pBS搜索算法。这个框架的几个实例进行了描述和分析，在一系列的搜索域的理论和实验结果表明pBS搜索算法通常比现有技术的有界次优搜索算法更快。这在实践中表明，找到满足给定次优界的高概率解决方案可以比找到满足相同次优界的确定性解决方案更快。2018 Elsevier B.V.保留所有权利。1. 介绍考虑一个搜索问题，我们必须在状态空间中找到一条从给定的初始状态到目标状态的路径。 给定足够的内存和运行时间，标准的启发式搜索算法，如A-算法[1]，可以解决给定的 最优搜索问题，即，找到从初始状态到目标的最低成本路径。 然而，通常情况下，没有足够的内存或运行时间来找到最佳解决方案。 对于这种情况，已经提出了一系列返回次优解的搜索算法[2特别地，有界次优搜索算法是保证返回的解的成本最多是最优解的（1<$）倍。理想的有界次优算法在解决方案质量和搜索运行时间之间引入了一个自然的权衡：当<$很高时，解决方案会很快返回，但质量可能会更差，而当<$很低时，解决方案更难找到，但通常质量更高（即，较低的成本）。有界次优搜索算法是非常严格的，因为它们返回的解的代价必须是最多是最优解成本的1<$目前的技术，以实现这一保证依赖于可接受的化学品– 是最优解决方案成本的下限。这样的搜索通常是不准确的，导致增加搜索运行时间。*通讯作者。电子邮件地址：sternron@post.bgu.ac.il（R. Stern），gal. gmail.com（G. Dreiman），rvalenzano@cs.toronto.edu（R.Valenzano）。https://doi.org/10.1016/j.artint.2018.08.0050004-3702/ 2018 Elsevier B. V.保留所有权利。目录可在ScienceDirect人工智能www.elsevier.com/locate/artint40R. Stern等人 /人工智能267（2019）39-57+ − +−⊆∈在本文中，我们提出了一种替代类型的解决方案的质量保证。具有这种质量的搜索算法保证返回具有高概率的最优解而不是控制返回的解的次优性（即，这些算法接受一个参数δ，该参数控制返回的解是最优的置信度。δ允许a解决方案质量和运行时间的类似折衷，其中增加δ预计将以增加返回次优解决方案的可能性为代价来这两种类型的解决方案的质量保证可以结合起来，通过一个新的概念，可能有界次优搜索（pBS搜索）。pBS搜索算法被赋予两个参数，<$和δ，并且需要返回最多为最优解的1 <$倍的解，概率高于1δ。我们称1 <$为期望的次优性，1δ为期望的次优性。所需的信心。引入和定义pBS搜索的概念是这项工作的第一个主要贡献。在许多领域中，通过当前有界次优搜索算法找到的解具有低得多的（即，更好的）次优性在实践中比次优性保证的界限。由于运行时间和运行时间之间通常存在折衷，和解决方案质量，这意味着搜索算法的用户在运行时支付的费用超过了所需解决方案质量所需的费用。我们提出的有界次优性的新形式的一个关键好处是，它为搜索算法的用户提供了对时间质量权衡的更多控制。我们在实验中观察到这一点：通过使用我们提出的一些pBS算法，通常可以通过将所需的置信度从1.0稍微放宽到0.9来显著更快地获得具有所需次优性的解。第二个贡献是一个通用的框架，用于开发pBS算法称为PSF。Psf有两个主要的构建块：解生成器和停止条件。解决方案生成器可以是产生解决方案序列的任何算法停止条件负责识别当前解何时是足够的，在这个意义上，它具有所需的次优性和所需的置信度。我们提出了三个这样的停止条件-对于绝对和h-比率条件，我们还提出了一个专门设计的解决方案生成器，以快速满足这些停止条件。这些停止条件和新的解生成元是本文的第三个贡献最后，我们评估了不同的实例Psf实验上的四个搜索域：煎饼难题，船坞机器人，吸尘器，和基于网格的路径查找。在这些不同领域的实验表明，<$andδ提供了对解决方案质量与运行时权衡的灵活控制：通常，增加<$orδ结果运行时间更短，溶液质量更低特别是，设置δ>0确实可以让我们更快地找到解决方案这项工作中的一些材料以前发表在组合搜索研讨会（SoCS）的会议记录中[6，7]。本文总结并超越了这两份会议文件。 特别是，它通过以下方式扩展了这些先前的工作：这些先前会议出版物中的实验评估只考虑了一个领域：15-难题。 这项工作通过在四个额外的域上实现和评估所有Psf实例来显着扩展该评估（见第5节）。对pBS搜索的理论基础进行了适当的定义和分析。 这包括对原始作品的几处更正（见附录B）。对于绝对和h比停止条件，我们提出了一个专门为它们设计的解生成器，它基于最近的有界成本搜索算法（见第6节）。此外，在以前的工作中[6，7]，这一系列研究被称为可能近似正确（PAC）搜索，因为它受到理论机器学习文献中PAC学习概念的启发[8]。考虑到PAC的概念和本文中考虑的解决方案质量保证之间存在显著差异，我们将其名称改为可能有界次优搜索以避免混淆。这些相关概念的比较可以在第8节中找到。2. 附件和背景图搜索问题或搜索问题由图G、源顶点S V和目标顶点的非空集合T V定义。G中的边与由c（ e）表示的非负成本相关联，并且G中的路径p的成本（表示为c（ p））是其组成边的成本之和。 搜索问题P的解是G中从s到T中顶点的路径。如果没有其他解决方案具有更低的成本，则该解决方案被称为最优解决方案。 设OptP表示P的最优解的成本。解决方案的次优性是其成本与OptP之间的比率。因此，次优最优解是1。 注意，次优性的替代形式也被引入[9]，本文中的概念可以很容易地扩展到它们。为了清楚起见，我们在本文中集中讨论上述次优性的定义。搜索算法是接受搜索问题并尝试返回其解决方案的过程。在基础图G没有被明确地给予搜索算法的情况下，例如，因为它太大了，无法容纳在内存中。相反，搜索算法可以给定一个源顶点s和一组状态转换算子，这隐式地定义了G是通过对s应用状态转移算子序列可到达的所有状态的集合。···R. Stern等人 /人工智能267（2019）39-5741+·+≤=+PP+−≤ +·=2.1. 搜索算法的性质令cost（A，P）表示给定问题P时算法A返回的解的成本。一个搜索算法A称为最优搜索算法，如果对于每个搜索问题P 它持有成本（A，P）OptP。搜索算法A被称为有界次优搜索算法，如果它接受一个参数<$，并且对于每个问题P，它保持成本（A，P）（1<$）OptP，即，它返回的解的次优性至多为1<$。[10][11][12][13][14][15][16]最佳搜索算法的例子，而加权A [2]，A[3]，显式估计搜索[4]，和动态势搜索[5]是有界次优搜索算法的示例另外两种类型的搜索算法，我们在本文中使用的任何时间搜索算法和有界成本搜索算法。任何时间搜索算法在找到初始解之后继续搜索更好的解，如果给定更多的运行时间。任意时间搜索算法的突出示例是任意时间加权的A/S [12]，波束堆栈搜索[13]，任意时间窗口A/S [14]和任意时间潜在搜索（APTS）[15]，也称为任意时间非参数A/S（ANA）。如果一个搜索算法接受一个参数B并且返回一个解，那么它就是一个有界代价搜索（BCS）算法。 如果存在这种解决方案，则成本最多为B。潜在搜索（PTS）[15]和有界成本显式估计搜索（BEES）[16]是BCS算法的示例请注意，我们在这项工作中的重点是图搜索问题，其中需要以较小的成本找到解决方案。搜索算法也被应用于其他设置，例如，其中目标是找到具有最大成本的解决方案[17]。我们期望将我们的结果扩展到这样的设置将不会是困难的。2.2. 最佳-第一搜索许多启发式搜索算法都适用于最佳优先搜索的一般框架.最佳优先搜索（BFS）是一种迭代算法，它维护一个称为Open的节点列表。在每次迭代中，该算法从Open中选择一个节点进行扩展，其中扩展节点意味着生成其子节点并将其插入Open。初始打开只包含初始状态si。BFS算法还维护另一个称为Closed的节点列表，其中包含所有先前扩展的节点。Closed用于避免在不需要的情况下多次生成状态最佳优先搜索算法的不同之处在于它们如何选择从Open扩展哪个节点。例如，A算法-rithm [1]选择展开Open中具有最小g的节点h值，其中节点n的g值，表示为g（ n）是迄今为止从si到n找到的最低成本路径，并且h（ n）是从n到目标节点的成本的启发式估计。如果启发式函数是可容许的（即，总是一个下界），那么保证找到一个最优（最低成本）的解决方案[1]。3. 可能有界次优搜索在本节中，我们定义了可能有界次优搜索的概念。让是一组搜索问题，设D在它们上面做一个分布。 PD被定义为根据分布D抽取的随机变量。根据这个符号，cost（ A， PD）是当给定根据分布D从P得出的搜索问题时，由搜索算法A返回的解的成本的随机变量。类似地，OptPD是根据D从P得出的问题的最优解成本的随机变量。定义1（pBS搜索算法）。搜索算法是pBS搜索算法w.r.t. P和D如果它接受输入<$>0和1>δ > 0，并且概率至少为1−δ，则它输出次最优解至多为1+<$，即，Pr.cost（A，PD）≤（1+<$）·OptPD<$≥ 1−δ（1）我们参考1作为期望的次优性，并参考1δ作为所需的置信度。因此，pBS搜索算法是一种搜索算法，它返回一个具有所需次优性和所需置信度的解经典的搜索算法可以被看作是pBS搜索算法的特殊情况。最优搜索算法是pBS搜索算法，因为如果cost（ A， P）OptPD，则显然等式（1）对于任何非负的和δ也对A成立。类似地，任何有界次优搜索算法也是pBS搜索算法，因为如果cost（ A， P）（1<）OptPD，则显然等式（1）也适用于任何非负δ。然而，这两类算法都忽略了δ的值，从而错过了加速的潜在机会搜寻接下来，我们提出了一个pBS搜索算法的一般框架，该算法同时考虑了<和δ。3.1. pBS搜索算法框架我们提出的pBS搜索框架，简称为PSF，有两个主要的构建块：一个解决方案生成器和停止条件。解决方案生成器的作用是找到解决方案，使每个解决方案的成本低于前一个。停止条件的作用是决定何时找到迄今为止的最佳解– 具有所需的次优性和所需的置信度。42R. Stern等人 /人工智能267（2019）39-57←←←←←∞−++ ≥P算法1：pBS搜索算法框架（Psf）。输入：1 ·期望的次优性输入：1δ，所需的置信度1 U;2 现任者3 虽然改善U是可能的，4新解决方案生成解决方案（U）5如果NewSolution为空，则6return现任7其他8现有新解决方案9UNewSolution. 成本10如果ShouldStop（U），则返回现任11端12 端Psf如下使用这些构建块（参见算法1中的伪代码）。 首先，运行解决方案生成器（算法1中的第4行）以找到初始解决方案。 如果它成功地找到了一个解决方案，那么该解决方案及其成本分别存储在变量Incumbent和U中。接下来，停止条件（ShouldStop，第10行）检查U是否具有所需的次优性和所需的置信度。1如果是，则返回现任。否则，将开始另一次迭代，其中解决方案生成器将查找新的解决方案，更新现任者和U，然后调用停止条件检查U是否具有所需的次优性和所需的置信度（第3-11行）。 这个迭代过程一直持续到找到满足停止条件的现任解，或者直到解生成器无法找到更多的解。请注意，解决方案生成器接受U作为参数，因为它试图找到成本低于现任者如果不存在这样的解决方案，则返回Incumbent。在这种情况下，如果解生成器是完整的，则返回Incumbent是安全的，因为如果它不能找到成本低于U的解，则Incumbent是最优的。实现Psf的关键问题是如何实现解生成器和停止条件。随时搜索算法特别适合作为解决方案生成器：如果有足够的时间，它们将返回一个序列这样，每个后续的解决方案都比它的前任更好。 此外，修改许多现有的随时搜索算法是简单的，使得它们接受现任解决方案（U）的成本并修剪搜索空间的不能导致改进现任解决方案的部分。例如，如果一个随时搜索算法使用了一个可接受的启发式算法，那么它可以用g h U来修剪节点。一些随时随地算法保证最终找到最优解。 如果Psf使用这样的任意时刻算法作为解生成器，则存在Psf是健全和完整的停止条件，即，对于任何值<$和δ，它将找到一个具有所需次优性和所需置信度的解。这种停止条件的一个例子是永远不满足的停止条件，即，永远不会停止搜索。在这种情况下，解决方案生成器最终会找到一个最优解，满足任何期望的次优性要求。 对于下面的所有讨论，我们假设所使用的解决方案生成器是收敛到最优解决方案的生成器4. pBS停止条件显然，使用永不停止的停止条件是不明智的。在本节中，我们提出了更好的停止条件，这可以更早地停止搜索并且仍然保持pBS搜索保证（定义1）。 这种停止条件被称为pBS条件。定义2（pBS条件）。 pBS条件是Psf算法的停止条件，其保证PSF使用这个停止条件和一个完整的解决方案生成器将是一个pBS搜索算法。pBS条件和pBS搜索的概念都是相对于问题集定义的和分布D在他们身上。为了开发有效的pBS条件，我们假设一个预处理阶段，在该阶段中，我们被给予一组搜索问题，每个问题独立地从相同的分布（D）（即，他们被随机抽样。方式），我们有足够的资源来最佳地解决它们。 我们将这组给定的搜索问题称为训练集。 拥有一个有代表性的训练集并能够最佳地解决其中的问题当然并不总是可能的。 然而，在许多现实的情况下，这些都是合理的假设参见第7节中的讨论。4.1. 绝对条件有了问题的样本和它们的最优解，我们就可以近似计算累积分布函数(CDF)随机变量OptPD。例如，这可以通过计算具有最优1 正如我们稍后讨论的那样，创建这样一个停止条件是不平凡的，本文的大部分内容都致力于提出这样的停止条件。R. Stern等人 /人工智能267（2019）39-5743=≤P≤1+<$≤PFig. 1. 在我们的实验结果中使用的4个域的F（v）的分布。x轴显示最优解决方案成本，用v表示，y轴显示F（v）值。对于v值的范围，高于v的解。也可以使用其他统计上有效的曲线拟合技术。 令F（ v）表示所得到的CDF。F（ v）与OPTPD的实际CDF的接近程度取决于训练集的大小和所使用的近似技术。为了简单起见，我们在本文中假设F（ v）是OPTPD的实际CDF，即，我们假设F（ v） Pr（ vOptPD）。未来的工作将研究如何使用问题的数量来创建这个CDF会影响最终的不准确度，并且可能修改δ以包含此误差。图1显示了我们在实验中使用的CDF，它们是使用上面提到的简单问题计数方法生成的。X轴示出OptPD的可能值，并且y轴示出累积分布，即，为给定x值，它表示Pr的值（x≤OptPD）。有关不同域的描述，请参见第5对于给定的CDF F（v），我们定义一个阈值 T（<$，δ）作为最大数 v 为此 F（1v ）等于或大于1-δ。形式上，+<$T（<$， δ）=argmax.F.vΣ≥1−δΣv≥01+<$T（<$，δ）是我们引入的第一个pBS条件的关键，我们称之为绝对条件。 根据这个条件，如果U≤T（<$，δ），则停止搜索。定理1. 绝对停止条件是pBS条件。证据设P是根据分布D得出的问题，设A是使用绝对条件的Psf的实例。当A停在P上时，它要么找到了一个最优解（算法1中的第6行），要么因为绝对值被满足而停下来（第10行）。在最坏的情况下，A总是由于后一个原因而停止。在这种情况下，cost（ A， P） T（<$，δ）。这意味着F.cost（A，P）≥ 1 − δ（2）Pr（成本（A，P）选项1+<$D）≥1−δ（3）Pr（cost（A，P）≤（1+<$）·OptPD）≥ 1−δ（4）由于P是从PD中采样的，因此其最优解OptP是从最优解的分布中采样的选择PD，因此Pr（cost（A，P）≤（1+<$）·OptP）≥ 1−δ□（5）44R. Stern等人 /人工智能267（2019）39-57绝对条件有几个吸引人的性质。首先，它非常容易实现：当当前解低于T（δ）时简单地停止。因此，该条件易于集成到现有的搜索算法中。二是要求R. Stern等人 /人工智能267（2019）39-5745=+∈==+·h（ si）h（ si）T R（<$， δ）=argmax.F R.vΣ≥1−δΣ·几乎没有额外的内存或运行时间，因为阈值T（<$，δ）不依赖于手头的问题（P），并且可以对该域中的所有问题计算一次AbsOlute条件不考虑关于当前正在解决的搜索问题的任何信息。为了说明为什么这可能是一种浪费，考虑下面的例子。例1. 假设我们有一个可接受的启发式函数h，我们试图解决一个搜索问题P，其起始状态为s i，使得h（s i）40。由于h是可容许的，我们知道选项P不可能小于40。 因此，如果我们找到一个成本为40的现有解决方案，我们可以立即停止，而不管δ的值如何。然而，如果我们的训练集包含即使一个状态的最优解为35，那么我们将具有F（40）> 0，因此对于δ的某些值，绝对条件将不会停止搜索。此外，假设我们使用的启发式算法几乎总是将最优解低估5。在这种情况下，如果我们碰巧找到一个成本为44的解决方案，那么它很可能是最优的，我们可以站住。同样，AbsOlute条件对此是不可知的，并且不会利用此信息。4.2. 启发式感知pBS条件我们现在提出两个互补的解决方案，以解决上述例子所确定的问题4.2.1.最优解的许多搜索算法保持最优解的下限。 例如，任何在开放列表中维护所有生成的节点的搜索算法，如A[1]，WA [2]，ARA [18]和APTS [5]，都可以使用 f最小值min nOpen（g（n）h（n））作为最优成本的下界，如果h是可容许的。fmin的值可能会增加并降低-折痕（例如，当使用不一致的语义学[19]时），节点被扩展和生成。因此，为了获得最紧的下限，一些搜索算法保持迄今为止观察到的最大fmin我们将该值表示为Maxfmin。显然，如果现任解决方案等于或小于（1<$）Maxfmin，则它具有所需的次优性具有完全的确定性（即，甚至对于δ0）。这种停止条件，我们在这里称为最大fmin条件，在任何时间搜索算法[12]和有界次优搜索算法[4，5，3]的文献中是众所周知的。重要的是，Maxfmin条件可以与任何其他pBS条件一起使用，如果满足任何一个条件，则停止搜索。因此，我们在所有pBS条件下实现了这个额外的停止条件观察到Maxfmin条件解决了例1中的第一个问题，其中h（ si）=40，现任解决方案的成本也是40，因为如果h（ si）=40，则Maxfmin≥40。4.2.2.h-比率条件下面的pBS条件，称为h-ratIO条件，旨在通过考虑启发式函数在开始状态的误差来解决示例1中的第二个对于一个启发式函数h，一个搜索问题P和一个相应的起始状态si，我们将h的误差定义为OptP和h（ si）之间的比值。对于随机搜索问题PD，h的误差本身是随机变量，表示为Opt（PD）。使用h-ratIO条件所需的统计量是该随机变量的CDF，表示为FR（v）=Pr（ v≤Opt（PD））。在绝对条件下，我们定义一个阈值 TR（<$，δ）v≥01+<$h-ratIO条件满足，如果对于现任解U，它保持U≤h（si）·TR（<$，δ）。定理2. h-ratIO条件是pBS条件。定理2的证明是定理1的证明的直接改编。为了完整，在附录A与AbsOlufsen条件类似，在Psf中使用h-ratIO条件几乎不会产生开销。简单地计算h（ si）TR（<$，δ）在搜索开始时一次，从那时起只检查U是否小于它，在这种情况下，我们可以停止搜索。h-ratIO条件是更一般的pBS条件的特殊情况，其考虑在给定初始状态的启发式值的情况下具有某个值的最优解的搜索问题的可能性。 为了实现这个条件，我们需要累积分布函数F h=t（v）= Pr（Opt≤v|h（s i）=t）。相应的阈值参数为argmax.Fh=hs （五））≥1−δv≥0（i） 1+<$并且所得到的停止条件是当现任解等于或小于该阈值时停止搜索。然而，正确地实现该pBS条件需要比h-ratIO更大的训练集，因为它需要足够的问题来训练每个启发式值。46R. Stern等人 /人工智能267（2019）39-57+·h（ n）（，）（≤）--（n）+m在Open中，我们假设Open中的所有节点都不拒绝成本U，则U≤..ΣΣ=+·+·≤g（ m）+ h（ m）·（1+<$）。Open中的一个节点，它是g（m）=g（m）的非最优解的一部分[1]。 因此，OptP=h（s.i）=g（m）+h（m）. 以来Fh.h（n），1·.U−g（n）Pr. h∈（Nh=h（n））≤1·. U−g（n）4.3. 开基条件到目前为止提出的pBS停止条件与所使用的解决方案生成器无关。事实上，关于这些停止条件考虑的潜在搜索问题的唯一知识是从训练集和当前开始状态的启发式生成的统计数据。虽然这使得它们更容易实现，但这也意味着如果现任解决方案U不满足这些pBS条件，则搜索不能停止，直到找到新的现任解决方案。此外，这些pBS条件不考虑解决方案生成器如何找到解决方案。因此，它们忽略了解决方案生成器在搜索过程中收集的关于潜在问题的任何信息。Maxfmin条件在某种程度上弥补了这一点，因为它考虑了由解生成器获得的下限，并且当下限增加时可能会停止，但该条件忽略了δ，并且增加该下限可能很困难。在本节中，我们提出了一个pBS条件，用于监控解决方案生成器执行的搜索，并根据它收集的有关潜在搜索问题的信息，即使没有找到新的现任解决方案，也可以决定停止搜索。这个pBS条件称为基于开放的条件，是为特定类型的解决方案生成器设计的：基于最佳优先搜索的解决方案生成器许多随时搜索算法都是最佳优先搜索，[18][19][20][21][22][23][24][25][26][27][基于Open的条件在搜索时监视处于Open状态的节点一个新的现任解决方案，并决定停止时，它是不可能的，任何节点在开放是一个解决方案的一部分，将显示现任解决方案不具有所需的次优性。接下来我们将详细解释基于Open的条件首先，介绍几个定义设h（n）表示成本从n到目标的最低成本路径因此，对于一个起始状态为si的搜索问题P，我们有h（si）=OptP。定义3（b）. 节点n拒绝成本Uw.r.t. 如果。g（n）+h<$（n）<$·（1+<$）U.直观地说，如果存在通过节点n的底层搜索问题的解，则节点n拒绝成本U并且该解决方案具有足够小的成本以拒绝U具有期望的次优性（1+<$）的假设引理1. 如果没有找到最优解，并且Open中的每个节点n都没有拒绝解成本U，则U达到了期望的次优性。证据这一证明是通过矛盾来实现的。假设U没有达到期望的次优性，即，U>（1选择P。让表示从初始状态si到节点n的最优路径。由于没有找到最优解，因此，我们有U ≤（1 +<$）·OptP，与U不具有期望的次优性的假设相矛盾。 □当一个节点n处于Open时，h（n）的值是未知的。因此，确定节点n是否拒绝成本U是不可行的。 然而，给定适当的统计数据，可以估计节点拒绝成本U的概率。 为此，我们收集和考虑的启发式错误的搜索节点所遇到的解决方案生成器的统计数据。这些统计量类似于h-ratIO使用的统计量，并由CDF函数F（n，v）= Pr（h（n）≤ v）表示。有几种方法可以近似这个CDF。在我们的实验中，我们通过将具有相同h值的节点分组在一起来做到这一点，这样我们就有了一个随机变量Nhv，它表示从搜索期间观察到的节点分布中抽取一个具有h（ n） v的节点，并且h值等于v。然后，我们用Prh<$（Nh=h（n））v逼近Fnv，h（Nh= h（ n））表示为Fh（ h（ n）， v）。有关我们如何收集信息以生成这些统计数据的详细信息，请参见第5.2推论1. 随机抽取的节点拒绝成本U的概率由下式给出：h（n）1+<$P roof. 根据定义，Fh.h（n），h1·1U<$−g（n）n=0，h（Nh=h（n））h（n）1+<$PR（1 <$）g（n）h（n）h<$（Nh=h（n））U（7）h（Nh= h（ n））这是n拒绝U的概率（定义3）。□对于给定的节点n，我们将值h1 （1U<$−g（n））乘以P（U，n，<$），当<$从上下文中很清楚时，我们省略它写P U n（n）P+Un是节点n拒绝成本U的概率。（，）。因此，推论1指出，（，）R. Stern等人 /人工智能267（2019）39-5747.Σ.← +−← −−←−r−定义4（开放式）。如果满足基于开放的条件，n∈。开放log（1−P（U，n））≥log（1−δ）（8）基于Open的条件的正确性依赖于以下假设：对于Open中的任何两个节点n和nr，n拒绝U的事件与nr拒绝U的事件不负相关。在这个假设下，n和nr都不会拒绝U的概率至少是这将发生的各个概率的乘积，即，Pr（nrrejectsU）≥（1−P（U，n））·（1−P（U，nr））（9）定理3.如果等式（9）中的假设成立，则基于开放的条件是pBS条件。证据 如果满足基于开放的条件，n∈。开放log（1−P（U，n））≥log（1−δ）（10）n ∈。开放（1−P（U，n））≥1−δ（11）由于等式（9），我们有Pr（n∈Open<$（nrejectsU））≥n∈开（1−P（U，n））≥ 1−δ（12）根据引理1，这意味着U具有期望的次优性和所需的置信度。□注意，基于开放的条件可以如等式（11）中定义，即，没有对数。我们描述它与对数，以避免精度问题。算法2：基于开放的pBS条件更新规则。输入：m，当前展开1如果m是一个目标节点，并且U是递减的，则2P（U）←0 ;r3456其他78910111213141516端部foreachnode m∈OpendoP（U ）P（U）log（1P（U，mr））;端P（U）P（U）log（1P（U，m））;foreachchild m of mdo如果g（mr）在m扩展时更新，则如果mr先前处于打开状态，则P（U ）P（U）log（1Pold（U，mr））;端P（U ）←P（U）+log（1−P（U，mr））;端端基于Open的条件相对于AbsOlute和h-ratIO条件的一个显著优点是，即使Maxfmin和U没有改变，在Open中扩展节点后也可以满足。因此，有效地检查这种情况尤为重要。检查是否满足基于Open的条件所需的运行时由运行时控制48R. Stern等人 /人工智能267（2019）39-57是覆盖Open中的所有节点。在每个节点都展开之后，以这种方式计算P（ U）显然是不高效的requiredtocalculate-是的logg（1−P（U，n））. L etP（U）=.logg（1−P（U，n））. 正确的方向是计算P（U ）n∈开n∈Open其中，Open是最大的。当然，P& O（U）可以以更合理的方式进行计算：通过log（1 − P（U，m））从OpenwedecreeasP（U）中移除，并且其中添加节点m以通过log（1 − P（U，m））从Open w eincreeas P（U）中移除。在算法2中给出了P（ U， n）的这种增量计算的细节，并在下面进行解释我选择了一个非政府组织的节点来进行扩展。当m被扩展时，它从Open中恢复，并且剩余的P（U ）必须减少log（ 1-P（ U， m））（算法2中的第7行）。由m生成的节点可以被添加到Open，因此我们需要更新P（U）。具体而言，以下情况中的一个常见问题是：R. Stern等人 /人工智能267（2019）39-5749-||−××情况1：mr不在打开或关闭状态。 在这种情况下，将mr添加到Open。因此，P_（U ）按log（1）增加P（U，mr））（第7行）。案例2：mr已处于打开状态。当生成已经处于Open中的节点时，如果到它的路径具有较低的成本，则它的g值可以被更新。 如果g（mr）不挂起，则n个P（U ）也不挂起。如果g（mr）改变，则如下更新nP_n（U ）。 Let PoId（U，mr）和Pnew（U，mr）表示P（U，mr）的值是通过新的数值计算的，是精确的。通过移动Pold（U ，mr）（第7行）和添加Pnew（U，m r）（第13行），更新更新Pnew（U情况3：mr处于Closed（即， 它以前是扩展的）。 在这种情况下，在通过m到mr的路径的成本低于g（ mr）的情况下，mr的g值仍然可以在m被扩展时被更新。然后，节点mr被重新插入到Open中，并且被重新加载到Pnew（U，mr）到Pnew（U ）。2以这种增加的方式增加P_（U ），在给定的每个头部时间内都将导致O（1）。我不知道，什么时候扩展了所有节点，并在找到解决方案的基础上，减少了U。因此，在计算P_（U ）时，值日志（1 P（ U， n））必须为Open中的每个节点n更新（第1-5行）。这需要O（Open）开销。然而， 这仅在找到新的现任解决方案时发生。如果现任解决方案更新的次数为D，更新的第n个周期P（U ）可以分摊到Open中每个节点的第n个成本，包括每个生成节点的额外D5. 实验结果在pBS搜索的初步工作中，我们评估了pBS搜索框架和著名的15-puzzle上的几个pBS条件。在这里，我们将我们的评估扩展到四个额外的领域，我们将在下面描述。 用于运行我们实验的所有源代码都是公开的。有关如何获取和运行它的详细信息，请参见附录D5.1. 域我们使用的前两个域（煎饼和基于网格的路径查找）是标准的启发式搜索基准。 其他两个领域（真空吸尘器和船坞机器人）的灵感来自经典的规划问题，以前曾被Thayer和Ruml [4]和其他人[5，20]用于评估搜索算法。为了简洁起见，我们将这些域称为Pancakes、Path finding、Vacuum和Dockyard。5.1.1. Pancakes（煎饼）在这个域中有k个不同大小的煎饼，由1到k之间的唯一数字表示。这个域中的一个状态是一堆这样的k个煎饼，表示为数字1，.的排列。，k. 有一个单一的目标状态，即煎饼从大到小排序的状态。有k1个状态转换算子，其中算子i反转排列中的第一个i个煎饼。我们在这个领域使用的启发式是GAP启发式[21]，它为每两个不连续的相邻煎饼加1，例如，4-pancake状态的启发式算法（1，3，2，4）是2，由于煎饼1和2之后的“间隙“。在我们的实验中，我们尝试了40个煎饼的难题。问题是通过从目标状态执行1000次随机迭代而随机生成的5.1.2. 基于网格的路径查找（Path Finding）在这个域中，我们有一个网格和两个单元格，任务是找到从一个单元格到另一个单元格的路径。 作为一个网格，我们使用了流行的“Dragon Age：Origins”视频游戏中的brc202dmovingai.com一个状态是这个网格中的一个单元，我们允许在四个基本方向上进行转换。问题是通过在给定的地图中随机选择两个单元格产生的。我们在这个域中使用的启发式算法是曼哈顿距离。网格路径发现与煎饼谜题有很大的不同，因为表示状态空间的图是作为输入显式给出的，而表示40煎饼谜题的状态空间的图是由起始状态和允许的运算符集隐式给出的。因此，煎饼状态空间组合地大. 当然，这意味着解决网格路径查找问题通常比解决煎饼难题更容易5.1.3. 吸尘器（Vacuum）这个域的灵感来自于Russell和Norvig的教科书中提出的第一个状态空间真空吸尘器在具有障碍物（35%的单元格）的网格（200 200）中工作，并且存在许多脏点。清洁工应该找到一个清洁所有脏点的巡回赛。这个问题是旅行商问题（TSP）的一个变种，因此我们使用了基于最小生成树的启发式算法。3个问题是随机将吸尘器和5个脏的位置放在一个200第200章有障碍网格中障碍物的数量和位置不同 在每一个问题中，也是随机设置的。2在案例3中，有一些搜索算法不会重新插入节点。例如，Anytime Repairing A将这些节点存储在一个单独的列表（称为inconsistentlistt）中，以备将来使用。在这种情况下，没有人可以在Open和不一致列表的unio上计算P（U）。3 有一个变体，其中机器人在搬运泥土时变得更重，但我们使用了这个域的单位成本版本。−50R. Stern等人 /人工智能267（2019）39-57≥图2. 从我们的40-Pancakes难题（左）的训练集生成的h/ h比率的累积分布函数（CDF）样本，真空吸尘器领域（右）。图中的不同线对应于针对不同范围的h值生成的CDF。该图表明，两个域中的启发式函数对于小h和非常大的h值都是准确的，而对于这些极值之间的h值则不太准确5.1.4.船坞机器人（Dockyard）该域名的灵感来自Ghallab等人[24]和国际规划竞赛中的仓库域名 （IPC）。任务是将船坞中的集装箱从一个位置移动到另一个位置。与经典的blocksworld域类似，容器堆叠在不同的堆上，并且只有堆上最顶部的容器可以随时访问。 通过起重机将集装箱堆叠在堆上或从堆上拆下集装箱。将集装箱X从堆Y移动到堆Z涉及几个动作：使用起重机从Y卸下X X 移动机器人，从Y的位置移动， 到Z的位置，从机器人上卸下X，最后使用起重机将X堆叠到Z上。每个动作都与成本相关联。堆叠或从一堆中拆垛的成本是5加上堆的高度。从机器人上装载或卸载一个集装箱的成本为1.移动桩之间的机器人消耗桩之间的距离。参见Thayer和Ruml [4]，了解如何计算启发式算法的细节。我们生成的问题有5台起重机，8个集装箱堆放在5个桩上，piles是5.5.2. 统计信息收集在这4个领域中的每一个领域中，我们使用50个问题作为训练集，用于生成各种pBS条件。剩余的问题（40个问题在船坞领域和50个问题在所有其他领域）被用来评估不同的pBS条件和搜索算法的性能。这组问题被称为作为测试集。AbsOlute条件（F（ v））所需的分布是通过最优地解决训练中的所有问题来创建的集对于h-ratIO条件，我们还计算了这些问题的起始状态的h值。 生成基于开放的条件（Fh（ h（ n）， v））所需的分布更复杂，因为它需要从搜索期间观察到的状态收集统计数据。为了获得这样的统计数据，我们对训练集中的每个问题运行APTS，直到找到最佳解决方案。然后，我们对这些APTS运行期间生成的状态进行采样，以从h值范围内获得状态对于这些状态中的每一个，我们通过找到从它们到相应目标的最佳路径来计算h/h值根据它们的h值将具有它们的h和h/h每个bin包含至少50个问题，并且每个bin中的平均h/hh/h值。附录C更详细地描述了此分发生成过程的细节为了说明这个过程的结果，图2显示了这个过程产生的几个累积分布函数为煎饼（左）和真空（右）。在这两个图中，x轴是h/h比率，y轴是该比率的累积分布函数（CDF），计算为训练集中h/h小于x轴