第10章计划、动作和学习

1、第第1010章章 计划、动作和学习计划、动作和学习 第二部分第二部分 状态空间搜索状态空间搜索 我们已经探讨了在图中查找路径的几种我们已经探讨了在图中查找路径的几种技术，现在来研究这些方法如何被技术，现在来研究这些方法如何被agentagent用于用于现实问题中。现实问题中。 感知计划动作循环感知计划动作循环 基于搜索的规划方法的功效依赖于几个很强的假设。基于搜索的规划方法的功效依赖于几个很强的假设。由于以下原因，这些假设常常得不到满足：由于以下原因，这些假设常常得不到满足： 1) 1)知觉过程不可能总是提供环境状态的必需信息知觉过程不可能总是提供环境状态的必需信息( (由于由于噪声或者对重要

2、的特性不敏感噪声或者对重要的特性不敏感) )。当两种不同的环境状态引。当两种不同的环境状态引起相同的传感器输入时，我们称这种情况为起相同的传感器输入时，我们称这种情况为感知混淆感知混淆( (perceptual aliasing)perceptual aliasing)。 2) 2)动作并不总有其模型效果动作并不总有其模型效果( (由于模型不够精确，或者由于模型不够精确，或者受动器系统在执行动作时偶尔会产生错误受动器系统在执行动作时偶尔会产生错误) )。 3) 3)可能在环境中有其他的物理过程或其他的可能在环境中有其他的物理过程或其他的agent(agent(例例如，在游戏中有对手如，在游戏中

3、有对手) )。这些过程可能会改变环境以致于干。这些过程可能会改变环境以致于干扰扰agentagent的动作。的动作。 4) 4)外部作用的存在会引起其他的问题：在构造一个计外部作用的存在会引起其他的问题：在构造一个计划期间，环境可能变得与原来的计划不相干。这种困难使划期间，环境可能变得与原来的计划不相干。这种困难使得花费太多的时间为一个得花费太多的时间为一个agentagent进行计划而变得毫无意义。进行计划而变得毫无意义。 5) 5)agentagent可能在完成一个到达目标状态的搜索之前被可能在完成一个到达目标状态的搜索之前被要求动作。要求动作。 6) 6)即使即使agentagent有充

4、分的计算时间，但是计算要求的空有充分的计算时间，但是计算要求的空间资源不允许搜索进行到目标状态。间资源不允许搜索进行到目标状态。 感知计划动作循环感知计划动作循环 有两种主要方法可以用来解决这些困难，同时又能保有两种主要方法可以用来解决这些困难，同时又能保留基于搜索的计划的主要特征。留基于搜索的计划的主要特征。一种一种是用概率方法来形式是用概率方法来形式化知觉、环境和受动器的不确定性；化知觉、环境和受动器的不确定性；另一种另一种办法是用各种办法是用各种附加的假设和近似来消除这些困难的影响。附加的假设和近似来消除这些困难的影响。 处理动作的不确定效果的一种正式方法是假定对一定状处理动作的不确定效

5、果的一种正式方法是假定对一定状态下的每一个可执行动作，结果状态由一个已知的概率分布态下的每一个可执行动作，结果状态由一个已知的概率分布给出。在这种情况下找到合适的动作被称为给出。在这种情况下找到合适的动作被称为MarkovMarkov决策问题决策问题( (Markov decision problem , Markov decision problem , MDPMDP) ) 。 通过假定通过假定agentagent的传感设备在它的状态集上提供一个概的传感设备在它的状态集上提供一个概率分布，可以解决有缺陷知觉的其他问题。发现动作则被称率分布，可以解决有缺陷知觉的其他问题。发现动作则被称为为局部

6、可见的局部可见的MarkovMarkov决策问题决策问题( (Partially observable Partially observable Markov decision problemMarkov decision problem， POMDP POMDP) ) 。感知计划动作循环感知计划动作循环 在这里不讨论正式的、基于概率的方法，而是提出一在这里不讨论正式的、基于概率的方法，而是提出一个叫个叫感知计划动作感知计划动作( (sense/plan/actsense/plan/act) )的结构，在很多的结构，在很多应用中它避开了上述的一些复杂性。应用中它避开了上述的一些复杂性。 该结构

7、的基本原理是：即使动作偶尔产生了没有预料该结构的基本原理是：即使动作偶尔产生了没有预料的结果，或者的结果，或者agentagent有时不能决定它处于哪一种环境状态有时不能决定它处于哪一种环境状态下，但是通过保证下，但是通过保证agentagent从它的执行环境中得到连续的反从它的执行环境中得到连续的反馈，这些困难可以被充分地解决。馈，这些困难可以被充分地解决。 感知计划动作循环感知计划动作循环 确保连续反馈的一个方法是确保连续反馈的一个方法是计划一个动作序列计划一个动作序列，只执只执行这个序列中的第一个动作行这个序列中的第一个动作，感知结果环境状态，重新计感知结果环境状态，重新计算开始节点，然

8、后算开始节点，然后重复上述过程重复上述过程。这种方式，选择动作的。这种方式，选择动作的agentagent被叫做被叫做感知计划动作感知计划动作agentagent。然而为了使这个方然而为了使这个方法有效，计算一个计划的时间必须比每个动作执行时间要法有效，计算一个计划的时间必须比每个动作执行时间要少。少。 在良性环境中在良性环境中( (容忍几个错误步骤容忍几个错误步骤) )，感知和动作中的，感知和动作中的错误在感知计划动作循环序列中应错误在感知计划动作循环序列中应“达到平均数达到平均数”。 感知计划动作循环感知计划动作循环 感知计划动作循环感知计划动作循环 逼近搜索逼近搜索 定性地讲，定性地讲，

9、只要第一个动作有缩短到达目标距离只要第一个动作有缩短到达目标距离的趋势的趋势( (平均情况平均情况) )，经感知计划动作循环的多次，经感知计划动作循环的多次迭代将最终到达目标。迭代将最终到达目标。 放宽产生最优计划的要求常会减少找到一个计划放宽产生最优计划的要求常会减少找到一个计划的计算代价。的计算代价。 可以对以产生计划的质量为代价的有限计算时可以对以产生计划的质量为代价的有限计算时间资源的搜索算法进行修改，这些计划可能不是最佳间资源的搜索算法进行修改，这些计划可能不是最佳的，或者可能不是总能可靠地到达目标状态。即使这的，或者可能不是总能可靠地到达目标状态。即使这个计划不是最优的个计划不是最

10、优的( (甚至也不正确甚至也不正确) )，这些技术的应用，这些技术的应用也能被合并到感知计划动作循环中。也能被合并到感知计划动作循环中。 一个一个A A* *类型的搜索可用于这两种方法：类型的搜索可用于这两种方法： 对对前者前者，我们用一个不可接纳的启发式函数；，我们用一个不可接纳的启发式函数； 对对后者后者，在到达目标前，在到达目标前( (用可接纳的或不可接纳的用可接纳的或不可接纳的启发式函数启发式函数) )退出搜索。在到达目标前退出搜索是退出搜索。在到达目标前退出搜索是任意任意时间算法时间算法( (anytime algorithm)anytime algorithm) 的一个例子。任意时

11、的一个例子。任意时间算法能在任何时刻停止，结果的质量会随着运行时间算法能在任何时刻停止，结果的质量会随着运行时间的增加而改善。间的增加而改善。 可以从两个方面来减少代价。可以从两个方面来减少代价。一是一是能找到到达目能找到到达目标的一条完整路径但不必要求它是最优的；标的一条完整路径但不必要求它是最优的；或者是或者是能能找到一条局部的路径，它不要求已达到目标节点。找到一条局部的路径，它不要求已达到目标节点。逼近搜索逼近搜索 逼近搜索逼近搜索 孤岛驱动搜索孤岛驱动搜索 在在孤岛驱动孤岛驱动( (island-driven)island-driven)搜索中，来自问题搜索中，来自问题领域的启发性知识

12、被用于在搜索空间中建立一个领域的启发性知识被用于在搜索空间中建立一个“岛节点岛节点”序列，假定有好的路径通过这个搜索空序列，假定有好的路径通过这个搜索空间。间。 例如，在计划通过有障碍的地形时，这些岛就例如，在计划通过有障碍的地形时，这些岛就是相应的山。假如是相应的山。假如n n0 0是开始节点，是开始节点， n ng g是目标节点，是目标节点，( (n n1 1，n n2 2，n nk k) )是这些岛的一个序列。我们用是这些岛的一个序列。我们用n n0 0作为开始节点，作为开始节点，n n1 1作为目标节点，开始一个启发式作为目标节点，开始一个启发式搜索搜索( (用一个同那个目标相适应的启

13、发式函数用一个同那个目标相适应的启发式函数) )。 当搜索找到了一条到当搜索找到了一条到n n1 1的路径时，就用的路径时，就用n n1 1作起始作起始点，点，n n2 2作目标点开始另一个搜索，等等，直到我们作目标点开始另一个搜索，等等，直到我们发现了一条到达发现了一条到达n ng g的路。的路。 逼近搜索逼近搜索 层次搜索层次搜索 逼近搜索逼近搜索 除了没有显式的岛集合外，除了没有显式的岛集合外，层次搜索层次搜索( (hierarchical hierarchical search)search)非常像孤岛搜索。非常像孤岛搜索。 假定有一些假定有一些“宏算子宏算子”，它们能在一个隐式的岛搜

14、索空，它们能在一个隐式的岛搜索空间中采取大步骤。一个起始岛间中采取大步骤。一个起始岛( (在开始节点附近在开始节点附近) )和这些宏算和这些宏算子构成了岛的一个隐式的子构成了岛的一个隐式的“元级元级”超大图。超大图。 首先用一个首先用一个元元( (metalevel)metalevel)搜索来搜索这个超大图，直搜索来搜索这个超大图，直到找到一条到找到一条宏算子路径宏算子路径，它可以让我们从基级开始节点附近，它可以让我们从基级开始节点附近的一个节点到达基级目标节点附近的一个节点。如果已经按的一个节点到达基级目标节点附近的一个节点。如果已经按照一个基级算子序列定义过宏算子，宏算子可扩展为一条基照一

15、个基级算子序列定义过宏算子，宏算子可扩展为一条基级算子路径，然后根据基级搜索，这条路径与开始和目标节级算子路径，然后根据基级搜索，这条路径与开始和目标节点相连接。点相连接。如果没有以基级算子定义的宏算子，我们必须顺如果没有以基级算子定义的宏算子，我们必须顺着元级搜索中的岛节点路径进行基级搜索着元级搜索中的岛节点路径进行基级搜索。 逼近搜索逼近搜索 逼近搜索逼近搜索 例子例子：考虑在一个网格空间中机器人要将一个方块推到：考虑在一个网格空间中机器人要将一个方块推到一个给定的目标位置。一个给定的目标位置。 元级计划元级计划 ：如何推方：如何推方块移动到块移动到G G单元。单元。 基级计划基级计划 ：

16、方块移动：方块移动的每一步就能展开成的每一步就能展开成一个基级计划一个基级计划 。逼近搜索逼近搜索 有限范围搜索有限范围搜索 在某些问题中，用任何方法搜索方法发现一条到在某些问题中，用任何方法搜索方法发现一条到达目标的路径从计算上讲都是不可能的；而在另外一达目标的路径从计算上讲都是不可能的；而在另外一些问题中，一个动作必须在一个限定的时间内做出选些问题中，一个动作必须在一个限定的时间内做出选择，而不能在这个时间内搜索到所有到达目标的路径。择，而不能在这个时间内搜索到所有到达目标的路径。 在这些问题中，用有限的时间和计算量找到一条在这些问题中，用有限的时间和计算量找到一条被认为是在到达目标的好路

17、径上的节点可能是有用的，被认为是在到达目标的好路径上的节点可能是有用的，尽管该节点并不是目标节点本身。尽管该节点并不是目标节点本身。 当必须终止搜索时，这个替身节点当必须终止搜索时，这个替身节点n n* *在搜索前沿的所有节点中，有最小的在搜索前沿的所有节点中，有最小的 值值。 f f 假定在一个动作被选择前的可用搜索时间允许搜索假定在一个动作被选择前的可用搜索时间允许搜索到深度到深度d d，即所有深度为即所有深度为d d或小于或小于d d的路径都能被搜索到；的路径都能被搜索到；在该深度的节点在该深度的节点将被称为将被称为范围节点范围节点。那么我们的搜索。那么我们的搜索过程将搜索到深度过程将搜

18、索到深度d d，然后选择然后选择 )(minarg*nfnHn作为目标节点的替代。这个方法叫做作为目标节点的替代。这个方法叫做有限范围搜索有限范围搜索( (limited-horizon search)limited-horizon search)。Korf 1990Korf 1990研究了这研究了这个算法并称它为个算法并称它为最小搜索最小搜索( (minimin search)minimin search)。 逼近搜索逼近搜索 一个感知计划动作系统将在到达一个感知计划动作系统将在到达n n* *的路径上采的路径上采取第一个动作，感知结果状态，再迭代搜索，一遍一遍取第一个动作，感知结果状态，再

19、迭代搜索，一遍一遍地进行下去。地进行下去。 我们希望朝着一个拥有最优启发式指标的节点的第我们希望朝着一个拥有最优启发式指标的节点的第一步动作，正好是在朝着目标的路径上。一步动作，正好是在朝着目标的路径上。 通常，一个通常，一个agentagent没有必要去搜索所有到达目标的没有必要去搜索所有到达目标的路径；因为不确定性，远距离搜索可能是不相关的，不路径；因为不确定性，远距离搜索可能是不相关的，不能提供比应用在搜索水平上的启发式函数更好的信息。能提供比应用在搜索水平上的启发式函数更好的信息。 逼近搜索逼近搜索 逼近搜索逼近搜索 循环循环 在存在不确定性和在存在不确定性和agentagent依赖逼

20、近计划的所有情依赖逼近计划的所有情况中，用感知计划动作循环可以产生重复的循环。况中，用感知计划动作循环可以产生重复的循环。即即agentagent可能会回到前面遇到过的环境状态，重复在可能会回到前面遇到过的环境状态，重复在那里采用过的动作。那里采用过的动作。 当然，这种反复并不意味着当然，这种反复并不意味着agentagent永远不能达到永远不能达到目标状态。目标状态。 Korf Korf提出了一个计划执行算法叫提出了一个计划执行算法叫实时实时( (real-real-time)Atime)A* *(RTA(RTA* *) )，它建立了所有已经遍历过的状态的它建立了所有已经遍历过的状态的一个显

21、式图，同时调整这个图中节点的一个显式图，同时调整这个图中节点的 值，使它值，使它们在到达前面已经遍历过的节点时不会采取动作们在到达前面已经遍历过的节点时不会采取动作。 h h逼近搜索逼近搜索 建立反应过程建立反应过程 在一个反应型机器中，设计者已为每一个可能的在一个反应型机器中，设计者已为每一个可能的状态提前计算了合适的到达目标的动作。存储这些和状态提前计算了合适的到达目标的动作。存储这些和环境状态相对应的动作可能需要大量的内存。环境状态相对应的动作可能需要大量的内存。 另一方面，反应型另一方面，反应型agentagent常常比计划型常常比计划型agentagent反应反应更快。在某些情况下，

22、提前计算更快。在某些情况下，提前计算( (汇编汇编) )一些频繁使用一些频繁使用的的离线离线( ( offline)offline)计划计划，把它们存储为反应例程以便，把它们存储为反应例程以便可以可以在线在线( (online)online)快速产生适当的动作，这样做是有快速产生适当的动作，这样做是有益的。益的。 例如例如，离线搜索能计划一个以状态空间图中的目，离线搜索能计划一个以状态空间图中的目标节点为根的标节点为根的生成树生成树( (spanning tree)spanning tree)，它包含从状它包含从状态空间中所有态空间中所有( (至少很多至少很多) )节点到达目标的路径。能从节点

23、到达目标的路径。能从目标节点向后搜索产生一个生成树。目标节点向后搜索产生一个生成树。逼近搜索逼近搜索 例如，一个获得目标例如，一个获得目标( (块块A A在块在块B B上，块上，块B B在块在块C C上上) )的积木问的积木问题的生成树如图所示，它表示了从所有其他节点到达目标题的生成树如图所示，它表示了从所有其他节点到达目标的路径。的路径。 生成树和局生成树和局部生成树能容易部生成树能容易地转换成完全反地转换成完全反应型的应型的T-RT-R程序。程序。 如果：一个如果：一个反应程序为每一反应程序为每一个可能的状态指个可能的状态指定了一个动作，定了一个动作，就被称为就被称为通用计通用计划划( (

24、universal universal plan) plan) 或动作策或动作策略略( (action action policy)policy)。 学习启发式函数学习启发式函数 如果如果agentagent没有一个好的启发式函数来评估到达目没有一个好的启发式函数来评估到达目标的代价，有时就需要学习这样一个函数。首先解释标的代价，有时就需要学习这样一个函数。首先解释一个非常简单的适合特定情况的学习过程，在这种情一个非常简单的适合特定情况的学习过程，在这种情况下可能会存储所有可能节点的一个显式列表。况下可能会存储所有可能节点的一个显式列表。 这个特殊的学习过程从一个随机步开始，执行一这个特殊的学

25、习过程从一个随机步开始，执行一个由评估函数导向的搜索过程，最终慢慢到达目标，个由评估函数导向的搜索过程，最终慢慢到达目标，在随后的试验中向后传播来自更好路径的更好的值。在随后的试验中向后传播来自更好路径的更好的值。连续的环境反馈减少了不确定性和弥补一个连续的环境反馈减少了不确定性和弥补一个 agentagent缺缺乏对自己动作结果的知识了解。乏对自己动作结果的知识了解。奖赏代替目标奖赏代替目标 在讨论状态空间的搜索策略中，假定在讨论状态空间的搜索策略中，假定agentagent有一有一个简单的短期任务，它由一个目标条件描述。目标改个简单的短期任务，它由一个目标条件描述。目标改变着世界，直到它的

26、图标模型变着世界，直到它的图标模型( (以数据结构的方式以数据结构的方式) )满满足给定的条件。足给定的条件。 在很多实际问题中，任务并不像刚才描述的那样在很多实际问题中，任务并不像刚才描述的那样简单。相反，任务可能是正在进行的。用户按照给简单。相反，任务可能是正在进行的。用户按照给agentagent一些偶然的正负一些偶然的正负奖赏奖赏( (reward)reward)来表达他对任务来表达他对任务执行的满意程度。执行的满意程度。 agentagent的任务的任务是把它收到的奖赏数量最大化是把它收到的奖赏数量最大化( (一个一个简单到达目标的特例也可用这种框架来描述，在这个简单到达目标的特例也

27、可用这种框架来描述，在这个框架中，当框架中，当agentagent到达目标时，给到达目标时，给agentagent一个正的奖赏一个正的奖赏( (只有一次只有一次) )，而每次当，而每次当agentagent采取动作时给它一个负采取动作时给它一个负的奖赏的奖赏( (根据动作的代价根据动作的代价)。 奖赏代替目标奖赏代替目标 在这种任务环境下，我们要寻找使奖赏最大化的在这种任务环境下，我们要寻找使奖赏最大化的动作策略。动作策略。 对于正在进行还没有终止的任务，存在的一个问对于正在进行还没有终止的任务，存在的一个问题是未来的奖赏可能是无限的，因此难以决定如何使题是未来的奖赏可能是无限的，因此难以决定如何使它最大化。它最大化。 一种处理办法是通过一些因子对未来的奖赏打折一种处理办法是通过一些因子对未来的奖赏打折扣，即扣，即agen