执行监控和重新规划

12.5 执行监控和重新规划

执行监控智能体检验它的感知信息来观察是否每件事都根据规划进行。墨菲法则告诉我们，即使是为老鼠、人和条件规划智能体安排最好的规划也常常会失败。面对的问题是无界非确定性的——对那些智能体行动描述不正确的情况，某些不可预料的情形总是发生。因此，执行监控在现实环境中是必要的。我们考虑两种形式的执行监控：一种简单而较弱的形式称为行动监控，由此智能体检验环境来核实下一个行动是可行的；一种更复杂但更有效的形式称为规划监控，其中智能体核实整个剩余规划。

一个重新规划智能体知道当未预料的事情发生时该做什么：再次调用一个规划器，提出一个到达目标的新规划。为了避免消耗太多时间进行规划，这通常是通过尝试修补旧规划实现的——从当前未预料状态找到一条回到原规划的途径。

作为一个例子，让我们回顾图12.9的双重墨菲真空吸尘器世界。在这个世界中，有时移动到一个干净方格会在那个方格留下灰尘；但是如果智能体不知道或不担心这个会如何？那么它会提出一个十分简单的解：[Left]。如果规划实际执行中在到达时没有倾倒灰尘，那么智能体将检验到取得了目标。否则，因为隐含的Finish步骤的前提CleanL没有得到满足，智能体会产生一个新的规划：[Suck]。执行这个规划总是成功的。

行动监控和重新规划一起形成了一个通用策略，它能在完全或部分可观察环境中应用，也能在包含状态空间、偏序以及条件规划的各种规划表示中应用。状态空间规划的一个简单方法如图 12.13 所示。规划智能体从一个目标开始并创建一个初始规划以获得它。然后智能体开始一个接一个地执行行动。重新规划智能体，不像我们的其它规划智能体，它要记录剩余的未执行规划片断plan和完全的原始规划whole_ plan。它使用行动监控：在执行plan的下一个行动之前，智能体检查它的感知信息来看规划的任何前提是否已经意外地变成未满足。如果它们已经如此，智能体会尝试回到正轨，通过重新规划一个能够带它回到whole_ plan中某点的行动序列。

图12.13 进行行动监控和重新规划的智能体。它用一个称为PLANNER的完整状态空间规划算法作为子程序。如果下一个行动的前提未得到满足，智能体通过在whole_plan中的可能点p循环运转，尝试找到一个PLANNER能够规划一条路径到达的点。这条路径称为repair（修补），如果PLANNER成功找到一个修补，智能体添加repair和p之后的规划尾部，以创建一个新的规划。然后智能体返回该规划中的第一步

图12.14提供了这个过程的示意性图解。重规划器注意到plan中第一个行动的前提没有被当前状态满足。然后它调用规划器提出一个新的称为repair的子规划，它将从当前情景到达whole_ plan上的某个状态s。在这个例子中，状态s碰巧是从当前剩余plan后退一步。（这也是为什么我们要记录整个规划，而不仅仅是剩余规划）。一般而言，我们选择离当前状态尽可能近的s。把repair和whole_ plan从s开始向前的部分串接起来，我们称之为continuation（延续），产生了一个新的plan，智能体准备好继续执行。

图12.14 在执行前，规划器提出一个这里称为whole_plan的从S到G的规划。智能体执行这个规划直到标记为E的点。在执行剩余plan之前，它照常检验前提并发现它实际上处于状态O而不是E。然后它调用它的规划算法提出repair，这是一个从O到原始whole_ plan上某点P的规划。新的plan现在变成repair和continuation（原始whole_ plan的继续）的串接

现在让我们回到获得颜色匹配的椅子和桌子的样例问题，这次通过重新规划。我们假设环境是完全可观察的。在初始状态中椅子是蓝色的，桌子是绿色的，有一罐蓝色的油漆和一罐红色的油漆。这给了我们如下的问题定义：

Init(Color(Chair,Blue)∧Color(Table,Green )

∧ContainsColor(BC,Blue)∧Paint Can(BC ))

∧ContainsColor(RC,Re d)∧Paint Can(RC )

Goal(Color(Chair,x)∧Color(Table,x ))

Action(Pa int(object,color ),

PRECOND:HavePa int(color)

EFFECT:Color(object,color))

Action(Open(can ),

PRECOND:Paint Can(can)∧ContainsColor(can,color)

EFFECT:HavePaint(color )

智能体的PLANNER会给出如下的规划：

[Start; Open(BC); Paint(Table, Blue); Finish]

现在智能体准备好执行规划。假设当智能体打开蓝色油漆并用到桌子上时，一切运转正常。前面部分的智能体将会在这一点宣布胜利，已经完成了规划中的步骤。但是执行监控智能体必须首先检验Finish步骤的前提，要求两件家具必须有相同的颜色。假设智能体感知到它们没有相同的颜色，因为它遗漏了桌子上的一个绿点。然后智能体需要计算出whole_ plan中的一个目标位置和一个达到那里的修补行动序列。智能体注意到当前状态跟Paint行动前的前提是一样的，所以智能体为repair选择空序列，并让它的plan与刚刚尝试过的[Paint, Finish]序列一样。把这个新的序列放在适当位置，执行监控继续进行，而且 Paint 行动再次被尝试。这个行为会循环往复，直到桌子被感知到已经被完全漆过了。但是应该注意到的是，循环是由规划-执行-重新规划的过程创建的，而不是由规划中的一个明确的循环创建的。

行动监控是执行监控的一个十分简单的方法，但是它有时导致不太智能的行动。例如，假定智能体构造一个通过将桌子和椅子漆成红色解决油漆问题的规划。然后它打开红色油漆的罐子，发现只有够用来漆椅子的油漆。行动监控不会检测到失败，直到椅子被漆完之后，在那时 HavePaint(Red)变为假。我们真正需要做的是检测到任何时候剩余规划不再可行的状态形成的失败。规划监控通过检验整个剩余规划成功的前提——也就是，规划中每一步的前提，除了那些被剩余规划中另一个步骤获得的前提之外——来实现这个目的。规划监控尽早截断注定失败的规划的执行，而不是继续执行直到失败确实出现[20]。在某些情况下，当一个注定失败的规划将把智能体引入不可能达到目标的死胡同时，规划监控能够将智能体从灾难中解救出来。

修改一个规划算法是相对直接的，所以它在每一点用剩余规划成功的前提标注规划。如果我们扩展规划监控来检验当前状态是否在任何未来的点都满足规划前提，而不只是当前点，那么规划监控会有利用偶然发现有价值行动的能力——也就是，偶然的成功。如果有人一起过来，在智能体把椅子漆成红色的同时，把桌子漆成红色，那么最后规划前提得到满足（已经获得目标），智能体能够早早回家。

迄今为止，我们已经在完全可观察的环境中描述了监控和重新规划。当环境是部分可观察时，事情会变得更加复杂。首先，如果智能体不能够检测环境，很可能会出错。其次，“检验前提”需要执行感觉行动，这必须被规划——要么在规划时，这将我们带回到条件规划中，要么在执行时。在最坏情况下，执行感觉行动需要一个复杂规划，它自身就需要监控以及因此进一步的感觉行动，依此类推。如果智能体坚持检验每个前提，它可能永远不能抽出时间来真正做任何事情。智能体应该更倾向于检验那些重要又很有可能出错的、而且不是代价太昂贵而不能感知的变量。这允许智能体对重要威胁做出适当的反应，而不是在检验“天是否会塌”上面浪费时间。

现在我们已经描述了监控和重新规划的一种方法，我们需要问“它可行吗？”这是一个令人惊异的棘手问题。如果我们的意思是“我们能够保证智能体总能获得目标吗，即使在无界非确定性的情况下？”那么答案是不能，因为智能体可能不留神到达一条死路，如同第 4.5 节中对联机搜索的描述。例如，真空吸尘器智能体也许不知道它的电池可能会被用完。让我们排除死路，也就是，让我们假设智能体能够从环境任何状态构造一个到达目标的规划。如果我们假设环境是真正非确定性的，在某种意义下这样的一个规划在任何给定的执行尝试下总是有一些成功的机会的，那么智能体最后将到达目标。因此重新规划智能体具有与条件规划智能体类似的能力。事实上，我们能够修改一个条件规划器，这样它构造的只是一个包含形如if<test>then plan_A else replan的步骤的部分解规划。在我们的假设下，这样一个规划能够成为原始问题的一个正确解；它还可能比构造一个完整的条件规划便宜得多。

当智能体重复尝试达到失败的目标时，麻烦出现了——当它们被一些它不知道的前提或效果阻塞时。例如，如果智能体有它旅馆房间的错误房卡，再多的插、拔卡的动作也打不开门[21]。一个解是从可能的修补规划集中随机选择，而不是每次都试同一个。在这种情况下，走到前台并取得房间房卡的修补规划是一个有用的可选方案。已知智能体也许不能区分真正非确定性情况和失败情况，修补中的一些变化通常是一个好主意。

不正确行动描述问题的另一个解决方法是学习。在少数尝试之后，学习智能体应该能够修改说明钥匙开门的行动描述。在那一点，重新规划器会自动地提出一个可供选择的规划，诸如拿到一把新钥匙。这种类型的学习将在第二十一章中描述。

即使有了这些潜在的提高，重新规划智能体仍然有一些缺点。它不能在实时环境中执行，并且它花在规划上的时间量没有界限，因此它在决定行动上所需要的时间也是没有界限的。同时，它不能形式化它自己的新目标，或者不能接受除了它的当前目标之外的新目标，所以它不可能成为复杂环境中的长寿的智能体。这些缺点将在下一节中加以解决。