人工智能-21状态演算

《人工智能-21状态演算》由会员分享，可在线阅读，更多相关《人工智能-21状态演算（7页珍藏版）》请在金锄头文库上搜索。

1、下载 第2 1章状 态 演 算 21.1 状态和动作推理 第7章介绍了状态空间的概念及如何搜索来计算动作计划以到达目标。当时还将讨论了基 于图标或基于特征的状态空间搜索。现在，我们有更丰富的语言来描述特征和特征之间的约束， 能更全面地研究基于特征的规划方法。 我们能删掉世界状态的一些属性，它们与当前的问题不相关或是未知的，这个事实是使用 基于特征方法的强有力的方面。这在描述我们想让 a g e n t通过其动作达到的目标条件方面尤其 重要。从图2 1 - 1中的配置开始，我们想让a g e n t生成一个计划以让某个积木在B上面（不必关心 哪个积木在B上或者B在那里） 。这个目标能用公式（x）

2、O n ( x, B)简单地描述。一般地讲，在 谓词演算中，一个目标条件能用任何合式公式描述，我们能通过试图从这些公式证明目标合式 公式来确定一个目标能否在一个由这些公式描述的状态空 间中被满足。 在本章和下一章，将介绍一些用来寻找一组动作以获 得由合式公式描述的目标状态的技术。这里用谓词演算机 制直接推理状态和动作。就像在所有的谓词演算推理中一 样，搜索仍然是必要的，但现在搜索是在一个逻辑表达式 空间上进行，而不是在一个世界状态的模型空间上进行。在下一章，描述了另一个方法，在那 里算子被用来改变状态描述，搜索将在一个状态描述空间上进行。 状态演算(situation calculus)McC

3、arthy & Hayes 1969, Green 1969a是一种状态、动作和动 作作用于状态的结果的谓词演算的形式化。在一阶谓词演算中我们把知识表达为关于状态和动 作的公式，然后用一个演绎系统来问这样的问题： “存在满足一定（目标）属性的状态吗？如 果存在，现在的状态如何通过动作才能被转换为那种状态呢？” 。对这样一个询问的回答是构 造一个到达希望状态的计划。虽然状态演算在一些早期的 A I规划系统中有显著的地位，但现在 很大程度上已被下一章讲到的方法所替代。然而，这种方法对研究和帮助澄清有关动作结果的 概念问题仍有重要作用。 通过一个积木世界的例子引入状态演算。假如把图 2 1 - 1中

4、的状态标识为S 0。用一阶谓词演 算，我们可以用下面的公式描述S 0： 为了描述状态演算中的这个状态和其他状态，我们把状态具体化，即将它们作为现存实 第四部分基于逻辑的规划方法 图21-1 积木的一个配置 动词reify 意思是说把某个抽象的东西看作是一个实在的或具体的东西。 体包括进我们的世界概念中。可能有很多这种状态，它们能用常量符号（如S 0，S 1，S 1，） 、 变量或者函数表达式表示。改变原子合式公式以包括一个指称包含预期关系的状态项。要对这 些原子合式公式的预期解释进行一个相应的变化，这些原子合式公式现在指称状态间的关系， 它们被称为流（f l u e n t） 。用公式构造一个

5、在状态S 0中为真的句子： 我们也可以有所有状态的命题真值。例如： 和 (C l e a r（x，s）的意思是x上可以放某个东西。)用这些一般公理，我们能证明S0的各种命题。 例如，我们能证明 c l e a r(A, S 0)和C l e a r(F l，S 0)。 为了表示动作及其结果，我们采取下面的步骤： 1) 把动作具体化（即我们想像有这样一个东西来做为动作） 。这样，动作能用常量、变量 或函数表达式表示。在状态演算形式中，一个动作被看作为动作涉及的实体的函数。在 例子中，动作是积木的函数。例如，考虑把一个积木从一个地方移到另一个地方的动作。 用表达式m o v e（B，A，F l）表

6、示把B从A移到地板上的动作（把一个动作看作为由那 个函数值给定的一个“对象” ） 。 一般地讲，我们能用模式(s c h e m a)m o v e (x, y, z)表达一个m o v e动作系列，其中x、 y和z是模式变量。利用常量，这些变量的实例化可以产生指称真正动作实例的表达式。 2) 接下来，想像一个函数常量 d o，它指称一个可以把动作和状态映射到状态的函数。如 果 代表一个动作， 代表一个状态，那么d o（ ， ）指称把状态动作对映射到通过 在 指称的状态中执行由 指称的动作获得的状态的一个函数。 3) 用合式公式表达动作的结果。在某些形式中，对每个动作-流对有两个这种合式公式

7、（目前，我们忽略动作对流没有影响的对） 。对On, m o v e对，合式公式是 和 这里我们假定公式中提到的所有变量都被全称量化。这些公式中的第一个被称为正效应 公理(positive effect axiom)，它描述了一个动作怎么使一个流为真。第二个叫负效应公 理(negative effect axiom)，它描述一个动作如何使一个流为假。在这个例子中，一个效 应公理的先行条件描述了为了应用那个动作必须满足的前提条件 (p re c o n d i t i o n)，结果描 述了在应用动作后流是如何被改变的。 即使已根据O n定义了C l e a r，我们也能为C l e a r, m

8、 o v e对写出效应公理。当然，它们 必须和定义以及O n ,m o v e的效应公理相一致。对C l e a r, m o v e的效应公理是： 228计计第四部分基于逻辑的规划方法 下载 注意，和前面用到的m o v e算子相比，这里移动一个积木块的表达式包括那个积木被移走的地方。 和 在这个例子中，前提由两部分组成。一部分表达了执行动作的前提条件；另一部分表达了 条件，在这个条件下，如果动作被执行，动作将产生表达在公理结果中的效果。在正效应公理 中，第二部分是（yz） （即使y = z，动作也能被执行把一个积木从一个位置向后移到相 同的位置，但它没有在结果中声明的效果） 。在负效应公理

9、中，第二部分是（zF l） 。 （由于我 们假定地板总是空的，没有任何动作可使它不空的） 。 为了说明如何使用效应公理，考虑图 2 1 - 2顶部的积木世界状态。这个状态满足使用置换 B / x，A / y，S 0 / s，F l / z的效应公理的前提条件。因此，我们能应用由m o v e(B, A, F l)指称 的动作推出如下结果： 这些表达式中的每一个都有d o ( m o v e ( B , A , F l ) , S 0 )）作为它的动作后的状态项（为简短起见， 用S 1 指称这个动作后状态） 。在图2 1 - 2中，显示了应用动作后的结果状态和描述那个状态的公 式（除了从效应公理

10、推出的公式，还有一些其他的公式也是 S 1 的真值公式；下面将简要描述 这些其他的公式是如何被推导的。 ） 即使在一个动作后，在执行动作允许的推导之前我们拥有的所有公式仍是真的！意识到这 一点是很重要的（在把 B移到地面后，在状态S 0中，B仍在A的上面。同样，在把B移到地板之 前,在由d o(m o v e(B, A, F l), S 0)指称的状态中，B在地板上面。 ）状态演算中的公式在感觉上是 “无状态的” ，它们总是真值（它们谈论的状态） 。 21.2 存在的一些困难 21.2.1 框架公理 图2 1 - 2明显地表明，并不是所有关于状态d o(m o v e (B, A, F l),

11、 S 0)为真的语句都能从效应 公理中推导出。例如，在移动之后，很明显在移动之前的状态为真的事实，如 C在地板上和B 是空的，在移动之后状态仍为真值。典型地讲，动作只有“局部”影响，故留下很多流没有改 变。为了对这些恒久不变的状态做推理，我们为每个动作和每个流提供一对所谓的框架公理 (frame axiom)，它不会因动作的结果而改变。例如，m o v e, On的框架公理是： 和 (如果在一个动作前一个积木在第二个积木上，那么在动作后它仍在第二个的上面，条件是那 个动作没有把它从第二个积木上移走。如果动作前一个积木不在第二个积木上面，那么动作后 它仍不在第二个上面，条件是该动作没有把它放在第

12、二个上面 )。 第21章 状 态 演 算计计229 下载 和 和效应公理类似，框架公理的第一个叫正框架公理 (positive frame axiom)，第二个叫负框 架公理(negative frame axiom)。 move, Cl e a r的框架公理是 (假如动作前一个积木是 c l e a r，如果那个动作 没有把另一个积木放在它上面，那么该动作后 那个积木仍是c l e a r。如果动作前一个积木不是 c l e a r, 而该动作没有从它上面移去另一个积木， 那么该动作后它仍不是c l e a r )。 框架公理被用来证明如果状态由一个不影 响某个属性的动作改变，那个属性保持为

13、真。 例如，m o v e, Cl e a r框架公理之一能用来推理 图2 1 - 2中的c l e a r (B, d o(m o v e (B, A, F l) )， S 0) )。 典型地讲，由于对每一个流和动作的组合我们 将有一对框架公理，在现实问题中用状态演算 方式表达动作如何改变世界变得相当的难管理。 有几个作者已经探索了如何减少大量的框 架公理，以及如何从效应公理自动导出框架公 理。这里不想讨论这些技术，但是它们涉及到 了那个假设能施加于一个流的变化仅仅是 那些被效应公理明确指定的变化（你可以参考 Pednault 1986, Schubert 1990, Reiter 1991

14、, Elkan 1992） 。即使能够减少大量的框架公理， 用它们对关于在几个动作序列上什么流不会改 变做推理的计算仍是笨重的。各种与解决不受动作影响的流有关的困难被称为框架困难。下一 章将讨论解决框架问题某些方面的一个方法。 21.2.2 条件 描述一个形如m o v e的动作的转换公式的前提为一个相当理想的事件给出了一个前提条件。 假如我们想通过确认被移动的对象不是太重而更准确一些，那么我们必须给前提条件加上另一 个合取式 T o o_heavy (x, s)。这个特别关注能被无穷无尽地进行，导致要加上其他的条件 像 G l u e d_d o w n (x, s)、 A r m b r

15、o k e n (s) , ，和那个明确的预期解释。指定所有的重要条 件的困难称为条件问题。已进行使用非单调推理的很多尝试以解决条件问题。这个思想是效应 公理允许缺省的结论，如果要加入进一步的条件，这个结论能被撤消（例如，参见Dean & Wellman 1991, pp, 63以后） ，这些尝试还没有完全成功。 21.2.3 分枝 还有其他的问题。在复杂的领域，我们常常用基于领域的一般知识演绎有关对象的语句。 230计计第四部分基于逻辑的规划方法 下载 地面 地面 用效应公理推出： 在所有状态为真： 用框架公理推出： 图21-2 将状态-动作对映射为一个状态 例如，一个机器人可能推导出，如果

16、它自己在一个房间里，那么它正在推的一个包也是在那个 房间里。不用效应和框架公理推断包的位置，我们可能宁愿推理机器人的位置，然后用我们的 普通知识去推理包的位置。例如，假如在状态S 0我们有事实I n(P A，R 1)，其中P A指称某个包， R 1指称某个房间。用它的效应公理，在移进某个不同的房间后（用 R 2表示） ，机器人能推断它 （机器人）确实是在一个新的状态下。它还能推断出那个包也在一个新的状态下。但是现在我 们如何才能阻止在新的状态下，框架公理断定那个包不是仍在由 R 1指示的房间里呢？跟踪导 出的公式哪一个在随后的状态转换中幸存被称为分枝问题。已经提出各种机制（与真值维护过 程有关）以解决分枝问题。 21.3 生成计划 让我们暂时不考虑框架、条件和分枝问题，从原则上说明状态演算如何用来规划一个使用 推理方法的动作序列。为了生成到达某个目标(s)的一个计划，我们设法证明(s) (s)，并用 应答谓词提取状态作为嵌套动作的一个函数，那个动作产生了状态。 例如，假定我们想生成一个计划，它把积木