计划、动作和学习

基于搜索的规划方法依赖于几个很强的假设：

agent必须能在图节点中表示所有相关的环境状态，它必须有在一对节点间如何动作的精确模型。
动作必须总有其模型化的结果，即在agent的操作系统中不能有错误或不确定性。
agent感知系统必须精准的指定开始节点，并且没有任何其他的agent或动态过程会改变环境。

如果这些假设满足，且搜索到目标状态的时间允许，就能进行规划，并执行一个完整序列的动作，不需要任何环境的信息反馈。

感知/计划/动作循环

由于以下原因，上面的那些假设通常得不到满足：

知觉过程不可能总是提供环境状态的必须信息，当两种不同状态的环境引起相同传感输入时，我们称这种情况为感知混淆（perceptual aliasing）
动作并不总有其模型效果（模型可能不够精准，或者受动器系统在执行动作时偶尔会产生错误）
可能在环境中有其他物理过程或其他agent。这些过程可能会改变环境以致于干扰agent动作。
外部作用的存在会引起其他问题：在构造一个计划期间，环境可能变得与原来的计划不相干。
agent可能在完成一个到达目标状态的搜索之前被要求动作。
即使agent有充分的计算时间，但是计算要求的空间资源不允许搜索进行到目标状态。

有两种方法可以用来解决这些困难，同时又保留基于搜索的计划的主要特征：

用概率的方法来形式化知觉、环境和受动器的不确定性。
用各种附加的假设和近似来消除这些困难的影响。

在这里暂时先不讨论正式的、基于概率的方法，而是提出一个叫感知/计划/动作的结构，在很多应用上避开了上述的一些复杂性。该结构的基本原理是即使动作偶尔产生了没有预料的结果，或者agent有时不能决定它处于哪一种环境状态下，但是通过保证agent从它执行环境中得到的连续的反馈，这些困难可以被充分的解决。

确保连续反馈的一个方法是计划一个动作序列，只执行这个序列中的第一个动作，感知结果环境状态，重新计算开始节点，然后重复上述过程。这种方式，选择动作的agent被叫做感知/计划/动作agent。为了使这个方法有效，计算一个计划的时间必须比每个动作执行时间要少。

逼近搜索

1. 孤岛驱动搜索

在孤岛驱动（island-driven）搜索中，来自问题领域的启发知识被用于在搜索空间中建立一个“岛节点”序列，假定有好的路径通过这个搜索空间。例如，在计划通过有障碍的地形时，这些岛就是相应的山。假如n0是开始节点，ng是目标节点，(n1,n2,......,nk)是这些岛的一个序列。我们用n0作为开始节点，n1作为目标节点开始一个启发式搜索，当搜索找到了一条到n1的路径时，再用n1作为目标点开始另一个搜索，等等，直到我们发现了一条到达ng的路。