Next: 練習問題
Up: ソフトウェア特論 講義資料 グラフ探索，問題解決
Previous: 7 統一的状態空間探索手続きの構造
例として，迷路の問題へ適用してみます．
図6の番地ごとに
壁データを次の様に初期化する関数を用意します．
(defun maze-init2 nil
(put 'p1 'walls '(n w s))
(put 'p2 'walls '(n s))
(put 'p3 'walls '(n s))
(put 'p4 'walls '(n e))
(put 'p5 'walls '(n w e))
(put 'p6 'walls '(n w e))
(put 'p7 'walls '(n w))
(put 'p8 'walls '(n s))
(put 'p9 'walls '(e))
(put 'p10 'walls '(e w))
(put 'p11 'walls '(e w))
(put 'p12 'walls '(s))
(put 'p13 'walls '(n e s))
(put 'p14 'walls '(w s))
(put 'p15 'walls '(e))
(put 'p16 'walls '(w s))
(put 'p17 'walls '(n e))
(put 'p18 'walls '(n w e))
(put 'p19 'walls '(n w))
(put 'p20 'walls '(e))
(put 'p21 'walls '(n w s))
(put 'p22 'walls '(s))
(put 'p23 'walls '(s))
(put 'p24 'walls '(e s))
(put 'p25 'walls '(w s e))
)
ロボットがどこにいるかで状態を表すことにします．
たとえば，
(robot at (0.2 0.3))
というように，座標ベクトルを第三要素として
持つ形で状態を表現することにします．
そうすると，状態と状態が等しいかどうか
を調べるnode-equalは，
(defun robot-position (state)
(third state))
(defun node-equal (s1 s2)
(< (distance
(robot-position s1)
(robot-position s2)) 0.8)
)
というように，ある程度の距離範囲内にあれば
同じとみなすようにします．
> (node-equal '(robot at (0 0)) '(robot at (0.1 0.1)))
t
次に，
壁の無い方向を調べて，next-statesを
作るとすれば，
(defun position-name (p)
(intern
(concat
"p"
(+ 1 (round (car p))
(* 5 (round (cadr p))))))
)
(defun next-dirs (state)
(let* ((v (robot-position state))
(sym (position-name v)))
(set- '(n w s e)
(get (position-name v) 'walls))))
(defun next-state (dir state)
(let ((v (robot-position state)))
(case
dir
(n (list 'robot 'at (v+ '(0 -1) v)))
(w (list 'robot 'at (v+ '(-1 0) v)))
(s (list 'robot 'at (v+ '(0 1) v)))
(e (list 'robot 'at (v+ '(1 0) v))))))
(defun next-states (state)
(let ((dirs (next-dirs state))
result)
(dolist
(d dirs)
(setq result
(cons (next-state d state)
result)))
result))
となって，場所ベクトルからシンボルを取り出し，
シンボルから壁の無い方向を集合演算で取り出す
というような形で計算をします．
> (next-states '(robot at (2 2)))
((robot at (1 2)))
> (next-states '(robot at (2 3)))
((robot at (2 4)))
> (next-states '(robot at (1 3)))
((robot at (1 4)) (robot at (0 3)))
next-statesを使ってnew-nodesと，
goal-search を定義すると，
(defun new-nodes (path graph)
(remove-if
#'(lambda (n) (node-member n path))
(next-states (first path))))
(defun goal-search (s g)
(breadth-first nil s g))
というような形になって，
> (goal-search '(robot at (0 0)) '(robot at (4 3)))
((robot at (0 0))
(robot at (1 0))
(robot at (2 0))
(robot at (3 0))
(robot at (3 1))
(robot at (3 2))
(robot at (4 2))
(robot at (4 3)))
> (goal-search '(robot at (0 0)) '(robot at (0 3)))
((robot at (0 0))
(robot at (1 0))
(robot at (2 0))
(robot at (3 0))
(robot at (3 1))
(robot at (2 1))
(robot at (1 1))
(robot at (1 2))
(robot at (0 2))
(robot at (0 3)))
> (goal-search '(robot at (0 0)) '(robot at (2 4)))
((robot at (0 0))
(robot at (1 0))
(robot at (2 0))
(robot at (3 0))
(robot at (3 1))
(robot at (3 2))
(robot at (4 2))
(robot at (4 3))
(robot at (3 3))
(robot at (3 4))
(robot at (2 4)))
というようになります．
(defun maze-operation (s1 s2)
(cond
((> (distance
(robot-position s1)
(robot-position s2))
1.2)
(print 'error))
(t (list 'move
(v- (robot-position s2)
(robot-position s1)))))
)
(defun maze-operations (state-path)
(let ((state (pop state-path))
(result nil))
(dolist (s state-path)
(setq result
(cons (maze-operation state s)
result))
(setq state s))
(reverse result)))
(defun operations-from-path
(path)
(maze-operations path))
(defun motion-planning
(start goal)
(operations-from-path
(goal-search start goal)))
> (motion-planning '(robot at (0 0)) '(robot at (3 3)))
((move (1 0))
(move (1 0))
(move (1 0))
(move (0 1))
(move (0 1))
(move (1 0))
(move (0 1))
(move (-1 0)))
> (motion-planning '(robot at (0 0)) '(robot at (0 3)))
((move (1 0))
(move (1 0))
(move (1 0))
(move (0 1))
(move (-1 0))
(move (-1 0))
(move (0 1))
(move (-1 0))
(move (0 1)))
> (motion-planning '(robot at (0 0)) '(robot at (2 4)))
((move (1 0))
(move (1 0))
(move (1 0))
(move (0 1))
(move (0 1))
(move (1 0))
(move (0 1))
(move (-1 0))
(move (0 1))
(move (-1 0)))
generated through LaTeX2HTML. M.Inaba 平成18年5月6日