next up previous
Next: 8 迷路問題への適用 Up: ソフトウェア特論 講義資料 グラフ探索,問題解決 Previous: 6.5 積み木での最終手続き

7 統一的状態空間探索手続きの構造

積み木の問題にかぎらず, 一般的な状態空間探索法の構造として,

(defun new-nodes (path graph)
  (remove-if
   #'(lambda (n) (node-member n path))
   (next-states (first path))))

(defun operations-from-path (state-path)
  (let* ((state (pop state-path))
         (result nil))
    (dolist (s state-path)
      (setq result
        (cons (node-operation state s)
              result))
      (setq state s))
    (reverse result)))

(defun motion-planning
  (start goal)
  (operations-from-path
   (goal-search start goal)))
というような手続きを用意して,最終的には, motion-planningという手続きである状態から次の状態へ 移る動作命令の列を生成する関数が使えるようにするには,
  1. (node-equal s1 s2): ある状態とある状態が同じ状態かどうかを調べる
  2. (next-states s) : ある状態から遷移可能な次の状態のリスト
  3. (node-operation s) : ある状態から次の状態へ移る操作命令を返す
  4. (goal-search s g) : 探索戦略に応じた探索手続き
というような手続きを構成すればよいことになります. 積み木の問題では,

(defun node-equal (a b) (set= a b))

(defun next-states (state)
  (next-block-states state))

(defun node-operation
  (state1 state2)
  (block-operation state1 state2))

(defun goal-search (s g)
  (breadth-first nil s g))
という具合な設定になります.

generated through LaTeX2HTML. M.Inaba 平成18年5月6日