4.12 新的問(wèn)題來(lái)了：猴子和香蕉問(wèn)題

為了顯示我們的GPS真的是通用的套利，需要在不同的問(wèn)題中檢驗(yàn)。我們來(lái)看一看一個(gè)經(jīng)典的AI問(wèn)題悉默，最初是由Saul Amarel在1968年提出的城豁。想象下面的場(chǎng)景：一只饑餓的猴子正站在一個(gè)房間的門口，在房子的正中間房頂上抄课，用繩子吊著一串香蕉唱星，剛剛好高度是猴子夠不著的。在門附近有一把椅子剖膳，足夠輕便魏颓，猴子推得動(dòng)，也足夠高度吱晒，猴子可以站在上面拿到香蕉甸饱。為了讓事情再?gòu)?fù)雜些，假設(shè)猴子手里拿著一個(gè)玩具球仑濒，而且規(guī)定一次只能在手里持一件東西叹话。
在嘗試表現(xiàn)這樣的場(chǎng)景的時(shí)候，我們可以靈活選擇把什么放到當(dāng)前狀態(tài)墩瞳，把什么放進(jìn)操作符驼壶。假設(shè)我們?nèi)绱硕x操作符：

(defparameter *banana-ops*
?(list
? ?(op ‘climb-on-chair
? ? ?:preconds ‘(chair-at-middle-room at-middle-room on-floor)
? ? ?:add-list ‘(at-bananas on-chair)
? ? ?:del-list ‘(at-middle-room on-floor))
? ?(op ‘push-chair-from-door-to-middle-room
? ? ?:preconds ‘(chair-at-door at-door)
? ? ?:add-list ‘(chair-at-middle-room at-middle-room)
? ? ?:del-list ‘(chair-at-door at-door))
? ?(op ‘walk-from-door-to-middle-room
? ? ?:preconds ‘(at-door on-floor)
? ? ?:add-list ‘(at-middle-room)
? ? ?:del-list ‘(at-door))
? ?(op ‘grasp-bananas
? ? ?:preconds ‘(at-bananas empty-handed)
? ? ?:add-list ‘(has-banans)
? ? ?:del-list ‘(empty-handed))
? ?(op ‘drop-ball
? ? ?:preconds ‘(has-ball)
? ? ?:add-list ‘(empty-handed)
? ? ?:del-list ‘(has-ball))
? ?(op ‘eat-banans
? ? ?:preconds ‘(has-bananas)
? ? ?:add-list ‘(empty-handed not-hungry)
? ? ?:del-list ‘(has-bananas hungry))))

使用這些運(yùn)算符，可以展現(xiàn)的問(wèn)題就是讓猴子不再饑餓喉酌，給定的初始狀態(tài)热凹，在門口泵喘，站在地板上，拿著球般妙，饑餓纪铺，在門口有把椅子。GPS可以找到一個(gè)這個(gè)問(wèn)題的解決方案：

> (use *banana-ops*) => 6
?> (GPS '(at-door on-floor has-ball hungry chair-at-door)
'(not-hungry) )
((START)
(EXECUTING PUSH-CHAIR-FROM-DOOR-TO-MIDDLE-ROOM)
(EXECUTING CLIMB-ON-CHAIR)
(EXECUTING DROP-BALL)
(EXECUTING GRASP-BANANAS)
(EXECUTING EAT-BANANAS))

這里沒(méi)有對(duì)原來(lái)的GPS程序作出任何的改動(dòng)碟渺，僅僅是使用了一個(gè)新的操作符集合鲜锚。

4.13 迷宮搜索問(wèn)題

現(xiàn)在我們來(lái)看看另一個(gè)經(jīng)典問(wèn)題，迷宮搜索苫拍。我們假定有一個(gè)迷宮芜繁，如下圖所示：

Maze.JPG

定義一些函數(shù)來(lái)幫助構(gòu)建針對(duì)問(wèn)題的操作符，比直接定義一大串操作符要容易得多绒极。下面的代碼定義了一般的迷宮操作符集合骏令，以及這個(gè)特定迷宮：

(defun make-maze-ops (pair)
? “Make maze ops in both directions”
? (list (make-maze-op (first pair) (second pair))
? ? (make-maze-op (second pair) (first pair))))

(defun make-maze-op (here there)
?“Make an operator to move between two places”
?(op ‘(move from ,here to ,there)
? ?:preconds ’((at ,here))
? ? ?:add-list ‘((at ,there))
? ?:del-list ’((at ,here))))

(defparameter *maze-ops*
?(mappend #’make-maze-ops
? ?‘((1 2) (2 3) (3 4) (4 9) (9 14) (9 8) (8 7) (7 12) (12 13)
? ?(12 11) (11 6) (11 16) (16 17) (17 22) (21 22) (22 23)
? ?(23 18) (23 24) (24 19) (19 20) (20 15) (15 10) (10 5) (20 25))))

現(xiàn)在我們可以使用操作符的列表來(lái)解決這個(gè)迷宮的一些問(wèn)題。我們也可以通過(guò)給定的連接的列表來(lái)創(chuàng)建另一個(gè)迷宮垄提。注意沒(méi)有證據(jù)表明迷宮的形式必須是55一層的伏社，他僅僅是一種連接具象化的表示方式。
> (use *maze-ops*) => 48
> (gps '((at 1)) '((at 25)))
((START)
(EXECUTING (MOVE FROM 1 TO 2))
(EXECUTING (MOVE FROM 2 TO 3))
(EXECUTING (MOVE FROM 3 TO 4))
(EXECUTING (MOVE FROM 4 TO 9))
(EXECUTING (MOVE FROM 9 TO 8))
(EXECUTING (MOVE FROM 8 TO 7))
(EXECUTING (MOVE FROM 7 TO 12))
(EXECUTING (MOVE FROM 12 TO 11))
(EXECUTING (MOVE FROM 11 TO 16))
(EXECUTING (MOVE FROM 16 TO 17))
(EXECUTING (MOVE FROM 17 TO 22))
(EXECUTING (MOVE FROM 22 TO 23))
(EXECUTING (MOVE FROM 23 TO 24))
(EXECUTING (MOVE FROM 24 TO 19))
(EXECUTING (MOVE FROM 19 TO 20))
(EXECUTING (MOVE FROM 20 TO 25))
(AT 25))

迷宮問(wèn)題指出了一個(gè)隱秘的小bug塔淤。我們要GPS返回的是一系列執(zhí)行的操作的列表摘昌。然而，因?yàn)榭紤]到目標(biāo)達(dá)成也可以沒(méi)有任何操作高蜂，所以聪黎，在GPS返回值中加上了(START)。這些例子包含了START和EXECUTING形式备恤，但是也包含了一系列的(AT n)稿饰。這就是bug。如果我們回過(guò)頭看看函數(shù)GPS露泊，就會(huì)發(fā)現(xiàn)他的結(jié)果是根據(jù)achieve-all返回的狀態(tài)刪除所有的原子得來(lái)的喉镰。這是一個(gè)雙關(guān)，我們所說(shuō)的移除原子就是移除除了(start),(executing action)之外的形式惭笑。到現(xiàn)在為止侣姆，所有的這些條件都是原子，所以方法可用沉噩。迷宮問(wèn)題是從形式(AT n)中引入條件捺宗，所以首先這就是個(gè)問(wèn)題〈桑基本的精神就是當(dāng)一個(gè)程序員使用雙關(guān)的時(shí)候蚜厉，也就是將真正發(fā)生的事情用比較通俗的話來(lái)說(shuō)，就會(huì)出現(xiàn)一些麻煩畜眨。我們真正想要做的不是刪除原子昼牛，而是找到所有知識(shí)操作的元素术瓮。下面的代碼就是主要的意思：
(defun GPS (state goals &optional (*ops* *ops*))
?“General Problem Solver: from state, achieve goals using *ops*.”
?(find-all-if #’action-p
? ?(achieve-all (cons ‘(start) state) goals nil)))

(defun action-p (x)
?“Is x something that is (start) or (executing …)?”
?(or (equal x ‘(start)) (executing-p x)))

迷宮問(wèn)題也顯示出了一個(gè)版本2的優(yōu)點(diǎn)：就是他會(huì)返回所做的操作的表現(xiàn)，而不僅僅是打印他們贰健。這樣子就可以利用結(jié)果來(lái)進(jìn)行一些處理斤斧，而不是僅僅看看而已。假設(shè)我們想要一個(gè)函數(shù)霎烙，給我們一個(gè)穿越迷宮的路徑，用一系列的位置表示蕊连。我們可以將GPS作為一個(gè)子函數(shù)調(diào)用悬垃，之后再操作結(jié)果。
(defun find-path (start end)
?“Search a maze for a path from start to end.”
?(let ((results (GPS ‘((at ,start)) ’((at ,end)))))
? ?(unless (null results)
? ? ?(cons start (mapcar #’destination
? ? ? ?(remove ‘(start) results
? ? ? ? ?:test #’equal))))))

(defun destination (action)
?“Find the Y in (executing (move from X to Y))”
?(fifth (second action)))
函數(shù)find-path調(diào)用GPS來(lái)獲取results甘苍。如果是nil就沒(méi)有答案尝蠕，如果不是nil就會(huì)提取results的rest部分（也就是移除start）。從每一個(gè)形式(executing (move from x to y))中挑選出目的地载庭，y看彼，并且記住起始點(diǎn)。
> (use *maze-ops*) => 48
?> (find-path 1 25) =>
(1 2 3 4 9 8 7 12 11 16 17 22 23 24 19 20 25)
> (find-path 1 1) => (1)
> (equal (find-path 1 25) (reverse (find-path 25 1))) => T