Ex4.5 WarrenのWARPLAN その１

;; Exercise 4.5[d] Write a planning program that, like Warren's
;; WARPLAN, keeps track of the list of goals that remain to be done as
;; well as the list of goals that have been achieved and should not be
;; undone. The program should never undo a goal that has been
;; achieved, but it should allow for the possibility of reordering
;; step that have already been taken. In this way, the program will
;; solve the Sussman anomaly and similar problems.

GPSをさらに改良する問題です。
Sussman anomalyとは、複数のゴールが関連性を持っていて、それぞれのゴールを順に達成するだけでは全てのゴールを達成出来ない問題のことです。
この問題は4.14 The Blocks World Domainの最後で議論していました。

(defparameter *block-ops* (make-block-ops '(a b c d e)))

(use *blocks-ops*)

(defparameter start '((space on c) (c on a) (a on table) 
		      (space on b) (b on table)
		      (space on table)))

(gps start '((a on b) (b on c)))
;; => NIL

The Blocks World DomainはあるBlockの状態からBlockを一つづつ動かして別のBlockの状態へ移動させる問題です。
上の例では、

としたいのですが、それぞれ別個に達成しても、

と、なってしまいゴールを達成できません。

取りあえずは、achieve-eachでgoalsを２回走査することで、上記の問題には対応できました。

(defun achieve-each (state goals goal-stack)
  "Achieve each goal, and make sure they still hold at the end."
  (let ((current-state state))
    (if (and (every #'(lambda (g)
                        (setf current-state
                              (achieve current-state g (remove g goals) goal-stack)))
                    goals)
	     (every #'(lambda (g)
                        (setf current-state
                              (achieve current-state g (remove g goals) goal-stack)))
                    goals)
             (subsetp goals current-state :test #'equal))
        current-state)))

以下の様に解決できました。

(gps start '((a on b) (b on c)))
;; => ((START) (EXECUTING (MOVE C FROM A TO TABLE))
;;  #1=(EXECUTING (MOVE A FROM TABLE TO B)) (EXECUTING (MOVE A FROM B TO TABLE))
;;  (EXECUTING (MOVE B FROM TABLE TO C)) #1#)

(gps start '((a on b) (b on c) (c on a)))
;; => NIL

問題の意図としては、

達成したゴールのリストを持つ
達成したゴールは崩れない様にする
ただし、元に戻せる手順がある場合は、達成したゴールを崩しても良い

というプログラムを作ることですので、もう少し考える必要があります。