实时启发式搜索：第一个结果
联合编译：章敏、陈圳
摘要
现有的启发式搜索算法不能在找到完整的解决方案之前采取行动，所以它们不适用于实时应用。因此我们提出了一种极大极小前向搜索（minimax lookahead search）的特殊情况来处理这一问题，还提出了一种能显著提升该算法的效率的类似于 α-β 剪枝的算法。此外，我们还提出了一种名为 Real-Time-A* 的新算法，该算法能用在动作必须被确实执行而不仅仅是模拟时来进行搜索。最后，我们检查了计算和执行成本之间的权衡的性质。
1.简介
启发式搜索是人工智能领域一个基础的问题解决方法。对于大多数AI问题，解决方法所需的步骤序列可以是不知道先验的，但它必须由一个系统反复试验决定探索替代方法。所有的这些要求构造一个搜索问题——一系列的状态，一系列状态映射到状态的操作员，一个初始状态，和一系列目标状态。这个任务典型的问题是：找到一个最廉价的操作员将初始状态映射到目标状态。使用启发式评估函数（一般不会牺牲最优解），很大程度上降低了搜索算法的复杂性。计算和评估从给定状态到目标状态最实惠方法的支出时，启发式函数相对来说更实惠。
AI文学界在搜索问题方面共同的例子是Eight Puzzle和其相对较大的Fifteen Puzzle。Eight Puzzle由一个3x3的序列框组成，包含8个编号棋子和一个称为“空白”的空位置。法定操作人员水平或垂直从相邻的位置滑动棋子。其任务是在一个随机的初始状态下重新排列棋子到所需的设定。该问题有一个共同的启发式函数称为“曼哈顿距离”（（Manhattan Distance）。它以计数的方式进行计算，对于每一个不再其目标位置的棋子，沿着网格移动的数量是远离它的目标位置，并且总计所有棋子的值，不包括空白的。
一个实时的例子如网络路径自动导航，或在任意地形从一个初始位置到所需的目标位置。这是典型的找出目标和初始位置之间最短路径问题。针对该问题的一个典型的启发式评估函数是，从给定位置到目标位置的空间直线。
2.现存的算法
最著名的启发式搜索算法是A*。A*是计算哪一个点f（n）是最好的首选最优搜索算法，g（n）是搜索该点的实际总支出，而h（n）是搜索该点解决方法的评估支出。当启发式函数可被采纳时，A*有着一个特性，即它总是可以找到问题的最优解决方案。例如，从来都不会高估解法的实际支出。
Iterative-Deepening-A*( IDA*)是改良版的A*，它降低了从指数到线性实践的空间复杂度。IDA*进行了一系列深度优先搜索（depth-first searches），当边界点的支出超过终止阈值时，它的分支被截断，f（n）=g（n）+h（n）。这个阈值始于初始状态的启发式评估，并增加每个迭代到最小值（超过原来的阈值）。IDA*在最优解法方面和A*有着相同的特性，并且扩展相同实例的点，进一步说，就像是在一个指数树上的A*，但是它仅使用线性空间。
A*和IDA*共同的缺点是：他们在实践中运行所发费的时间非常多。这是获得最优解法不可避免的支出。如Simon所注意到的一样，然而，最优解法虽然相对稀少，但对于大多数的实时问题接近最优或者“满意”的解法通常也能被完全接受。
还有一个相关的A*和 IDA*的共同缺点是：他们在进行第一步之前必须搜索所有的解法。原因是直到找到整个解法，且证明它至少和其它解法一样好时，才可以保住第一步是最优的。因此，在现实世界中执行产生的解决方案的第一步之前，A*和IDA*就在计划或模拟阶段运行完成。这大大限制了这些算法应用于实时应用。
3.实时问题
在该部分，我们展示了几个实时问题非常重要的特性，这些特性在任何的实时启发式搜索算法中都要被考虑到。
第一个特性是：在实际问题中，问题解决者必须面对有限的范围。这主要是由计算或者信息的限制造成。例如，由于Fifteen Puzzle的组合方式猛增，在DEC20使用“曼哈顿距离”（Manhattan Distance）的IDA*算法时，每一个问题平均发费的时间为5个小时。在大规模一点的难题将无法解决。为了防止没有完全细节映射的消极影响，搜索范围（迭代，在该情况下）取决于信息的限制——视觉相同能够看到多远。尽管有着精准的映射，细节的等级仍然受到限制。这引发了“fuzzy horizon”，其中地形知识的细节等级是到问题解决者距离的递减函数。
一个相关的特性是：在实时设置中，在他们的最终结果已知之前必须采取行动。例如，下棋时，要求棋子必须移动以延长方向选择的搜索范围。
最后最重要的一个特性是：行动的支出和计划的支出可以用相同的发生表达，引起了两个之间的权衡。例如，如果Fifteen Puzzle的目标是，以最短时间解决问题的同时移动数量最少，那么相对于在机器中模拟运动，我们会量化时间进行实际的物理运动，然后原则上我们会找到一个算法，通过平衡“思考”时间和“行动”时间最小化解法的总时间。
4.最小化前瞻搜索
在该部分，我们展示了一个简单的算法，用于在单代理（single-agent）问题的启发式搜索（将前面所有的特性包括其中）。这相当于双玩家游戏（two-player game）极小极大值算法的情况。这并不新奇，因为双玩家游戏分享有限搜索范围的实时特性，并且在最终结果已知之前采取行动。首先我们设想所有的操作者有着相同的支出。
算法从当前状态向前搜索到固定深度（取决于计算或者信息可利用的单体信息），并且应用启发式评估函数到搜索前沿的点。在双玩家游戏中值会被极小极大化到树中，致使玩家之间交替移动。在单代理（single-agent）设置中，由于单代理控制所有的运动，所以每一个点的备份值是它下一步点的极小值。一旦当前状态的下一步备份值被决定，就会在该方向上进行单独的最优下一步运动，并且这个过程都是这样重复的。不直接移动到前沿点极小极大值的原因是：遵循最小承诺的策略。在该设想下，在安排第一步行动之后，增加的信息（来自于扩展搜索前沿）或许会比第一搜索更能影响到第二步的选择。为了与极小极大值搜索对比，我们称该算法为极小值搜索。
注意：除了交错模型，两个方法的搜索过程完全不同。极小极小前瞻搜索在模拟模型中进行，其中假设的移动不会实际执行，仅仅在机器中进行模拟。在一个完整的前瞻搜索之后，找到最优移动由问题解决者在现实中进行运动。随后在当前状态进行另一个前瞻搜索，和实际运动。
在很多普遍的情况中，操作者有着不统一的支出，我们必须计算目前为止路径的支出，以便启发式评估剩余支出。为了进行该计算，我们采用了A*支出函数f（n）=g（n）+（h）。算法随后前进固定量的移动，并且备份每一个前沿点的最小值f。替代方案向前搜索固定量的移动，同时会向前搜索一个固定的g（n）支出。我们在该设想下采用原先的算法，即在计划阶段计算支出是移动数量的函数，而不是实际执行移动支出的函数。
为了确保终止，必须注意防止问题解决者实际所走过的路径无限循环。这已经被完成了， 通过维持这些状态（问题解决者实际访问过和移动过的状态）的CLOSED表，和从初始状态到当前路径点的OPEN堆栈。移动到CLOSED状态是结果输出，随后OPEN堆栈用于反向追踪直到移动可以用于一个新状态。这种保守的策略禁止算法毁灭以前的运动，除非它遇到一个死胡同。该限制在后文中将被移除。
5.α剪枝算法（Alpha Pruning）
到这一步自然而然的会问道：是否每一个前沿点都必须被检测以便找到极小值支出，或者是否存在一个 α-β 剪枝的算法，在探索本质上更少的点时，允许同样的决定。如果我们的算法只使用前沿点评估，然后一个简单的反观点可确定没有这样的剪枝算法存在，因为决定最小值支出前沿点要求检测每一个点。
然而，如果我们允许启发式评估内部点，且支出函数是单调函数，那么本质上的剪枝是可行的。如果支出函数f（n）不会递减到初始状态，那么它就是单调函数。f（n）=g（n）+h（n）的单调性和h（n）一样，或遵循三角形不等式，满足最自然产生的启发式函数的属性，包括曼哈顿距离（Manhattan Distance）和空间线距离（air-line distance）。此外，如果启发式函数是容许的但不单调，那么一个容许的，单调的函数f（n）可以显然是以其路径的最大值进行构建。
一个单调f函数允许我们应用分支界定法（branch-and-bound）在不影响决定的情况下，大量减少检测点的数量。类比于α-β 剪枝算法我们称该算法为α剪枝算法，如下：在生成树的过程中，保持在一个变量α（它是搜索范围中目前所有遇到点的f最低值）。当每一个内部点生成时计算f的值，并在f的值等于α时切断相应的分支。可以这样做的原因是因为函数是单调的，前沿点f的值只能从更好或者等于该点支出的点开始递减，并且不可以影响到运动，因为我们仅移向最小值的前沿点。当每一个前沿点生成时，同样计算f值，如果它小于α，就用更小的值代替α，并且进行搜索。
在使用曼哈顿距离（Manhattan Distance）评估函数的Fifteen Puzzle实验中，α剪枝算法通过远远多于蛮力分支因子（brute-force branching factor从2.13到1.41）的平方根减少了有效分支因子。在相同数量的计算时，它的效果比两倍的搜索范围效果还好。例如，如果计算源允许在移动时检测上百万的点，那么β压迫算法可以搜索深度为18的移动，而α剪枝算法允许搜索将近两倍的深度（40步移动）。
α剪枝算法中，α剪枝算法的效率可以通过node ordring进行提升。该想法命令每一个内部点的继承点增加f值的次序，希望找到更早的找到前沿点的最低支出，并更快的裁剪跟多的分支。
尽管这两种算法是各自发展的，最小化α剪枝算法非常类似于iterative-deepening-A*的单独迭代。唯一的不同点是在α剪枝算法中，中止阈值由前沿点最小值动态决定和调整的，而不是由先前在IDA *中迭代预先静止和设置的。
6.实时A *
目前为止我们设想了，行为一旦被执行除非遇到死胡同，不然它不会被逆转。——主要的动机是阻止问题解决者无限循环。我们现在解决的问题是：如何在它有用进行返回，而不是死胡同时返回，同时仍然反正无效循环。基本想法非常简单。从状态（加返回的支出）到状态（少于从当前状态向前移动的评估支出）评估解决方法时，它应该返回到原来的状态。Real-Time-A*是实施这一基本想法非常有效的一个算法。
最小值前瞻算法是控制搜索仿真阶段的算法，RTA *是控制搜索执行阶段的算法。因此，它独立于所选择的模拟算法。简单的说，我们假设：极小极小前瞻深度是封装在计算h（n）内部的，因此，变得简单，更准确，和更昂贵的方式计算h（n）。
RTA *中，点n的优点是f（n）=g（n）+h（n），如A *中的一样。然而，不像A *的是，RTA *中g（n）的理解是点n到问题解决者当前状态的距离，而不是原来的初始状态。RTA *只不过是给出略有不同支出函数的最好的第一搜索。原则上，它可以通过储存原先所有访问过的点的h值OPEN表实现，并且每一次移动，都会更新OPEN上所有状态的g值，以便准确反映它们到新的当前状态的实际距离。然后在每一个移动循环，问题解决者通过g+h的最小值选择下一个状态，向它移动，并且再一次更新OPEN上所有状态的g值。
这种单纯实现的缺点是：1）在OPEN列表中时间的大小是进行线性移动的。2）不是非常的清楚如何更新g的值，3）不清楚如何如何从OPEN中选择下一个目标节点的路径。有趣的是，在恒定的时间中，每次只使用图中本地的信息移动就可以解决这些问题。想法如下：从给定的当前状态，相邻的状态可以产生，启发式函数通过前向搜索增强（这适用于所有情况）然后，每一个邻近状态的边缘支出会增加这个值，产生当前状态每一个邻域的f值。有着极小f值的点是从新的当前状态和移动（已经被执行的状态）中选择出来的。与此同时，下一个f值储存在以前的当前状态。
这代表了通过回到原状态来解决此类问题所需的代价h。接下来，新状态下的新邻近点就产生了，而它们的h值也就此进行计算，并且所有新状态下的邻近点的边成本包括之前的状态的都会加入h值中，导致了所有邻近状态一系列的f值。再一次，节点值最小的会被除去，第二优的节点值会储存在旧状态的h值中。
注意到RTA不需要吧OPEN和CLOSED列表分开，之前评价过的节点值的单一列表就以足够。表的规模与移动的步数成线性关系，因为前馈搜索仅仅只会保留根节点值。并且运行时间也与步数成线性关系。原因在于尽管前馈研究所需时间与研究的深度成指数增长的关系，但研究深度会受到常数的约束。
有趣的是，人能够创建一个例子证明RTA*在在同一领域内追溯任意次数。例如，在图1中最简单的strighthne图，最开始的状态是节点a，所有的edge有一个总体的值，而在每一个节点下的数值就代表了这些节点的启发式评价。因为前馈只会让例子变得更加复杂，我们会假设没有前馈能去计算h值。并在节点a开始，f(b)=g(b)+h(b)=1+1=2，但f(c)=g(c)+h(c)=1+2=3。因此，问题求解程序移向节点b，并把节点a遗留在h(a)=3的信息状态。接下来，节点d会在f(d)=g(d)+h(d)=1+4=5结果下进行评价，所以节点a就变成了f(a)=g(a)+h(a)=1+3=4的结果。因此问题求解程序就移回了节点a，而在节点b之后的h(b)=5。基于此点，f(b)=g(b)+h(b)=1+5=6，并且f(c)=g(c)+h(c)=1+2=3，导致问题求解程序又移到了节点c，让在节点a之后的h(a)=6。阅读者会迫不及待的把实例继续进行下去以见证问题求解程序不断地往返，直到达到目标。其原理不是在于它是一个无限的环，而是在于当它每改变一次方向，就能比之前更深入一步，就能收集到更多关于空间的信息。这看似不合理的行为是由合理的行为在有限的探索界限和病理空间内产生的。
不幸的是，RTA*的追溯能力不能作为Fifteen Puzzle和Manhattan Distance评价函数。因为在于Manhattan Distance在一次移动中只会改变一次，而这会让RTA*在追溯一次就终止。
7.解决方法的质量
除了算法的效率之外，由最小前馈搜索所带来的解决方法长度也是关注的焦点。最正常的期待是希望随着解决长度的减少而深度却会增加。在带有Fifteen Puzzle的实验中使用Manhattan Distance，结果显示是期待是正确的，但并不一致。
Fifteen Puzzle的一千个原始解决状态是随机产生的。对于每一个原始状态，阿尔法剪枝算法的最小值是在搜索深度在1步到30步之间。为找到解决方法，会不停的进行移动，所以步数达到一千步也是有可能的，所以为防止步数过长，会对所有的结果步数进行记录。图2显示的是在所有超过千步的解决方法中平均解决的长度以及搜索限制的深度。底部的线显示的是在100个不同的原始状态中53个平均最优步骤。最优解决方法的长度是使用IDA*进行计算的，需要几周的CPU时间去解决上百的原始状态。
曲线的大体形状肯定了最初的假设增加搜索范围限制能减少解决运算成本。在深度为25时，平均的解决方法的长度只在一个因素上优于最优解决方案的平均长度。这一结果的实现是通过只在每一步只搜索6000个节点，或是整个解决过程只搜索6000,000个节点。这一过程能在Hewlett-Packard HP-9000工作站中只需CPU一分钟的运行时间。
但是在深度为3,10或是11时，增加的搜索限制会导致解决方法长度的轻微增加。这一现象首先是在有两个玩家的游戏中和Dana Nau命名的Pathology中发现的。他发现在某些游戏中，增加搜索深度但游戏结果还是较差。直到，在真实游戏中进行路径观察。
尽管在涉及到大量问题时路径的影响会相对来说较小，但在单个问题上，其影响还是很重要的。在多数案例中，通过一步来增加搜索的深度会让解决方法的长度增加上百步。
为更好的理解这一现象，我们对“决定质量”进行试验，这与解决方法质量是相对应的。它们之间的区别在于一个解决方法包括大量的个别决定。解决方法的质量是由解决方法的长度决定的，决定的质量是由最优步选择所花的时间决定的。因为在一个状态下必须知道最优步才能确定决定的质量，所以要选择较小或是叫温顺的Eight Puzzle，并用相同的Manhattan Distance评价函数。
图2：搜索限制VS 解决长度
在这个情况下，成千上万原始状态是随机产生的。我们不会探索整个解决方法，因为这是由最小算法产生的；我们仅仅最考虑原始状态下的第一步移动。在不同的搜索限制和不同起始状态下，第一步的最优步的决定时间都会被记录下来。搜索限制的范围从一步到低于最优选择的步数。图3展示的是错误率和搜索限制。随着搜索限制的增加，最优步数也会随之增加。因此，pathology并未在决定质量方面出现。
如果决定的质量能随着搜索的深度而增加，那为什么解决方法的质量会如此飘忽不定？其中一个原因是当犯错的几率增加时，就整体解决成本而言，个别错误的代价就会变高。这一点在追溯仅在遇到死胡同才会发生时表现的尤为明显。
图3：搜索限制VS.决定质量
另一个错误的根源在于节点位于备选方案之中。当信息不确定是必须确定移动，但连接不应随意破坏。更加普遍一点，当基于不准确的启发评价时进行处理，两个数值更加接近函数的准确度不应该被认为是虚拟的连接，而对于这一的处理也应是把它们看做是无法区分的。为解决这一问题，连接和虚拟连接必须在第一眼就认出来。这也就意味着当数值超过最初由错误因素所影响的最好结果之后，阿尔法剪枝算法必须改变。这会导致由此产生的节点的增加。
一旦确认节点之后，必须破坏它。最理想的方法是在候选方案之中实施更深度的二次搜索，直到连接崩坏。然而，这一二次搜索也有深度的限制。如果二次搜索达到了深度限制，而连接没有崩坏，虚拟连接会在较低成本下解体。
8. 计算&执行
用前馈搜索检查启发式评价函数，根据搜索的深度不同，更准确的启发式函数能生出一系列启发式函数。而这一系列的函数计算复杂性和准确度都不一样，但一般更加昂贵的函数就算的要更准确一些。
选择哪一个评价函数去平衡搜索成本和决定成本。时间最小化依赖于相关的计算成本和决定，但一个合理的模式是彼此都是相互成线性关系。换一种说法如果我们假设在实际中运用一个运算操作的成本是在所有模拟实验中运用的总和。
图4显示出与图2相同的数据，但是水平轴线与每一步节点的产生数量成线性关系，这与搜索的深度也有很大的关系。这一曲线图显示了计算—执行在最初某种程度上是有利的，例如小量的计算增加会带来大量的决定成本减少。但是，当达到减少转折点时，决定成本上的减少需要大量的计算。这一影响还有可能比当初的还要大，因为长度决定过程需要任意一百步。不同的计算成本和执行之间的关系会改变两个轴之间的关系，但不会改变基本的曲线的基本形状L。
9.结论
现存的单代理启发式算法不能在实际中进行运用，因为计算成本在停止计算之前都无法预知。最小化的前馈搜索是对于这类问题的最好解决方法。此外，α剪枝算法能提高算法的有效性，但却不影响决定的执行。此外，实时α算法解决了当遇见更有希望的算法而放弃当前算法的问题。大量的模拟显示搜索深度增加一般会提高决定的质量，但是出现与之相反的情况也是正常的。为避免虚拟连接对于决定质量产生决定性影响，附加算法也是很必要的。最后，前馈算法能看成是产生一系列具有不同准确度和计算难度的搜索。决定质量和计算成本之间最初是相互支持的关系，但到同时也会迅速达到一个收益递减的点。
via：论文原址
哈尔滨工业大学李衍杰副教授的点评：由于传统单智能体启发式搜索算法，如A*算法，计算量比较大，且需要搜索完最终结果后才能执行，因而不适用于实时性要求比较高的场合，为此，这篇论文研究了实时启发性搜索的问题，文中利用最小最小（minimin）前瞻搜索来避免传统启发式搜索所存在的前面所述问题，同时利用alpha剪枝方法来改进算法的效率，这两种思路的结合实际上是IDA*算法的一个自适应版本，即剪枝阈值随搜索节点的变化自适应地动态调整，而非像IDA*算法那样静态预先设定。此外，文中给出了一种实时的A*算法来实现当前搜索路径到更好的路径的转换。
本文作者：章敏
本文转自雷锋网禁止二次转载，原文链接
