完全可观察环境中的条件规划

时间：2022-02-11 理论教育版权反馈

【摘要】：完全可观察性意味着智能体总是知道当前的状态。通过嵌套的条件步骤，规划成为了树。我们希望条件规划不管哪个行动结果实际出现都能运转。因为环境是完全可观察的，智能体知道完全的状态描述，AtR∧CleanL∧CleanR。图 12.9 显示了这个环境的一棵“博弈树”。对于条件规划，有两个典型的修改。事实上，倘若状态是完全可观察的，对单个变量的if-then-else测试序列总能将一组状态分成单

12.4.1 完全可观察环境中的条件规划

完全可观察性意味着智能体总是知道当前的状态。然而如果环境是非确定性的，那么智能体将不能预知它的行动的结果。条件规划智能体通过在规划内建立（在进行规划的时候）会检查环境状态（在执行的时候）以决定下一步做什么的条件步骤来处理非确定性。那么，问题是如何构造这些条件规划。

我们将古老的真空吸尘器世界用作我们的样例领域，它在确定性情况下的状态空间展示在第3.2.1节中。回忆一下，可利用的行动是Left，Right和Suck。我们需要一些命题定义这些状态：如果智能体在左（右）状态，那么AtL（AtR）为真[12]，如果左（右）状态是干净的（clean），那么ClearnL（CleanR）为真。我们需要做的第一件事是扩展STRIPS语言以允许非确定性。为了实现这个，我们允许行动具有分离性效果，意为任何时候行动被执行，它就可能有两个或更多的不同结果。例如，假设有时遇到Left会失败。那么正常的行动描述

Action(Left,PRECOND:AtR,EFFECT:AtL)

必须修改为包含一个分离性效果：

我们还发现允许行动有条件效果也是有用的，其中行动的效果依赖于执行时所处的状态。条件效果出现在行动的EFFECT槽中，并且使用语法“when<condidtion>:<effect>”。例如，给Suck行动建模，我们会如此写：

Action(Suck,PRECOND:,EFFECT:(when AtL:CleanL)∧(when AtR:CleanR))

条件效果没有引入非确定性，但是它们能帮助对它建立模型。例如，假设我们有一个不可靠的真空吸尘器，有时当它移动时会将灰尘倒在目标方格，不过只有当方格干净时。这可以用如下的描述来模型化

Action(Left,PRECOND:AtR,EFFECT:AtL∨(AtL∧when CleanL:¬CleanL))

其中既有分离性也有条件性[13]。为了构造条件规划，我们需要条件步骤。我们用语法“if<test>then plan_A else plan_B”来写这些，其中<test>是状态变量的一个布尔函数。例如，对于真空吸尘器世界的一个条件步骤可能是“if AtL∧CleanL then Right else Suck”。执行这样一个步骤将以明显的方式前进。通过嵌套的条件步骤，规划成为了树。

我们希望条件规划不管哪个行动结果实际出现都能运转。这个问题我们以前已经看到过，以不同的外观出现。在二人游戏中（第六章），我们希望不管对手如何行棋我们的走法都能赢。由于这个原因，非确定性规划问题通常称为反自然的游戏。

让我们考虑真空吸尘器世界中一个特定的例子。初始状态是机器人在右方格的清洁世界中。因为环境是完全可观察的，智能体知道完全的状态描述，AtR∧CleanL∧CleanR。目标状态是让机器人在左方格的清洁世界中。这可能是相当不重要的，如果不是为了考虑“双重墨菲的”真空吸尘器，那种吸尘器当移动到一个干净的目标方格时有时会留下灰尘，当Suck被应用到一个干净的方格时有时也会留下灰尘。

图 12.9 显示了这个环境的一棵“博弈树”。机器人在树的“状态”节点采取行动，而自然环境决定在用圆圈表示的“机会”节点会有什么结果。解是一棵子树，（1）在每个叶子上都有一个目标节点，（2）在它的每个状态节点都指定了一个行动，（3）在它的每个“机会”节点都包含每个结果分支。图中用粗线显示出解，它对应于规划[Left,if AtL∧CleanL∧CleanR then[]else Suck]。（到现在为止，因为我们使用的是一个状态空间规划器，条件步骤中的测试是完全状态描述。）

图12.9 “双重墨菲”真空吸尘器世界搜索树的前两层。状态节点是某个行动必须被选择的或节点。显示为圆圈的机会节点是每个结果都必须被处理的与节点，结果用连接外出分支的弧表示。解用粗线显示

为了游戏的精确解，我们使用极小极大值算法（图6.3）。对于条件规划，有两个典型的修改。第一，MAX和MIN节点能够变成OR（或）和AND（与）节点。直观地，在每个到达的状态，规划只需要采取某个行动，但是需要处理它所采取的行动产生的每个结果。第二，算法需要返回一个条件规划，而不仅仅是一个单步移动。在或节点，规划只是被选中的行动，伴随着下一步会出现的任何情况。在与节点，规划是用来指定每个结果的子规划的if-then-else步骤嵌套序列；这些步骤中的测试是完全状态描述。[14]

形式化地说，我们定义的搜索空间是一个与或图（AND-OR graph）。在第七章中，与或图出现在命题的霍恩子句推理中。这里，分支是行动，而不是逻辑推理步骤，但是算法是相同的。图 12.10 给出了与或图搜索的一个递归的深度优先算法。

图12.10 用于非确定性环境产生的与或图的一个搜索算法。我们假定SUCCESSORS返回一个行动列表，每个行动与一组可能结果相关联。目标是找到一个在所有环境下都能达到目标状态的条件规划

算法的一个关键方面是它处理环的方法，环经常出现在非确定性规划问题中（例如，当一个行动有时没有效果时，或者当一个非预期的效果可能正确时）。如果当前状态与从根节点开始的一条路径上的一个状态完全相同，那么它返回失败。这并不意味着从当前状态开始没有解；它只是简单地意味着如果有无环解，它肯定能从当前状态的早期具体化到达，所以新的具体化可以被丢弃。用这种检验方法，我们确保算法在每个有限的状态空间中能终止，因为每条路径一定到达一个目标、死路或者一个重复状态。注意算法没有检验当前状态是否为某条从根节点开始的其它路径上的状态的重复。习题12.15研究了这个问题。

AND-OR-GRAPH-SEARCH 返回的规划包含测试整个状态描述以决定一个分支的条件步骤。在许多情况下，我们能够侥幸进行不那么彻底的测试。例如，图 12.9 的解规划可以简单地写作[Left, if CleanL then[] else Suck]。这是因为最简单的测试CleanL就足以将与节点的状态划分成两个单元素集合，以便在测试之后智能体知道它所处的确切状态。事实上，倘若状态是完全可观察的，对单个变量的if-then-else测试序列总能将一组状态分成单元素集合。因此，我们能够限制单个变量的测试而不失一般性。

最后，有一个在非确定性领域中经常出现的复杂因素：事物并不总是在第一次就可行，从而不得不再次尝试。例如，考虑“三重墨菲”真空吸尘器，它（除了先前提到的它的习惯以外）有时收到命令时会不能移动——例如，Left可以有分离性效果AtL∨AtR，如公式（12.1）那样。现在规划[Left,if CleanL then[]else Suck]不再保证是可行的。图12.11显示了部分搜索图。清楚地，不再有任何无环解，AND-OR-GRAPH-SEARCH会返回失败。然而，存在有环解，即不断尝试Left直到它可行。我们可以通过添加一个用来表示规划某些部分的标签并稍后用这个标签而不是重复规划自身的方法来表示这个解。这样，我们的有环解是

[L1:Left,if AtR then L1 else if CleanL then[]else Suck]

（一个用来表示这个规划的循环部分的更好语法是“while AtR do Left”）。习题 12.16 论及了AND-OR-GRAPH-SEARCH所需要的修改。关键的实现是状态空间中返回到状态L的一个循环转换成为规划中返回到状态L的子规划被执行的点的一个循环。