用状态空间法求猴子香蕉问题_猴子摘香蕉状态空间图

猴子和香蕉问题(monkey and banana problem)

在一个房间内有一只猴子(可把这只猴子看做一个机器人)、一个箱子和一束香蕉。香蕉挂在天花板下方，但猴子的高度不足以碰到它。那么这只猴子怎样才能摘到香蕉呢？图2.1.1

表示出猴子、香蕉和箱子在房间内的相对位置。用一个四元

表列(W,x,Y,z)来表示这个问题的状态，

其中

W－猴子的水平位置

x－当猴子在箱子顶上时取x=1；否则取x=0

Y－箱子的水平位置

z－当猴子摘到香蕉时取z=1；否则取z=0

这个问题中的操作(算符)如下：

(1) goto(U)猴子走到水平位置U，或者用产生式规则表示为

(W，0，Y，z) (U ，0 ，Y ，z )(2.3)

即应用操作goto(U)，能把状态(W，0，Y，z)变换为状态(U，0，Y，z)。

(2) pushbox(V)猴子把箱子推到水平位置V，即有

(W，0，W，z)(V ，0 ，V ，z )(2.4)

应当注意的是，要应用算符 pushbox(V)，就要求

产生式规则的左边，猴子与箱子必须在同一位置上，并且，猴子不是在箱子顶上。这种强加于操作的适用性条件，叫做产生式规则的先决条件。

(3)climbbox猴子爬上箱顶，即有

(W，0，W，z)(W，1，W，z) 　　(2.5)

在应用算符climbbox

时也必须注意到，猴子和箱子应当在同一位置上，而且猴子不在箱顶上。

(4) grasp猴子摘到香蕉，即有

(c，1，c，0) (c，1，c，1)　 　(2.6)

其中，c是香蕉正下方的地板位置，在应用算符grasp时，要求猴子和箱子都在位置c上，并且猴子已在箱子顶上。

应当说明的是，在这种情况下，算符(操作)的适用性及作用均由产生式规则表示。例如，对于规则(2)，只有当算符pushbox(V)的先决条件，即猴子与箱子在同一位置上而且猴子不在箱顶上这些条件得到满足时，算符pushbox(V)才是适用的。这一操作算符的

作用是猴子把箱子推到位置ｖ。在这一表示中，目标状态的集合可由任何最后元素为1的表列来描述。

令初始状态

为(a,0,b,0)。这时，goto(U)是唯一适用的操作，并导致

下一状态(U,0,b,0)。现在有3个适用的操作，即goto(U)，pushbox(V)和climbbox(若U=b)。

把所有适用的 操作继续应用于每个状态，我们

就能够得到状态空间图，如图图2-1-2所示。从图图2-1-2不难看出，把该初始状态变换为目标状态的操作序列为

猴子与香蕉的问题

状态空间表示

用四元组(W，x，y，z)其中：W-猴子的水平位置；x－当猴子在箱子顶上时取x=1；否则取x=0；Y－箱子的水平位置；z-当猴子摘到香蕉时取z=1；否则取z=0。

算符

(1) goto(U)猴子走到水平位置U；

(2) pushbox(V)猴子把箱子推到水平位置V；

(3) climbbox猴子爬上箱顶；

(4) grasp猴子摘到香蕉。

求解过程

令初始状态为(a,0,b,0)。这时，goto(U)是唯一适用的操作，并导致下一状态(U，0，b,0)。现在有3个适用的操作，即goto(U)，pushbox(V)和climbbox(若U=b)。把所有适用的操作

继续应用于每个状态，我们就能够得到状态空间图，如图所示。从图不难看出，把该初始状态变换为目标状态的操作序列为：

｛goto(b),pushbox(c),climbbox,grasp｝