白井 良明 立命館大学情報理工学部 知能情報学科

Presentation on theme: "白井 良明 立命館大学情報理工学部 知能情報学科"— Presentation transcript:

1 白井 良明 立命館大学情報理工学部 知能情報学科 shirai@ci.ritsumei.ac.jp
種々のデータ構造の探索 白井 良明 立命館大学情報理工学部 知能情報学科

2 AND-OR木の探索 Ｓ Ａ Ｂ （ Ｃ Ｄ Ｅ （ （ Ｆ t１ t２ G t３ t４ H

3 Ｂ Ｄ Ａ Ｓ Ｃ Ｅ Ｆ t１ G t３ t４ H t２ （

4 procedure depth-first and-or
add (s, open); LOOP: if open = null then exit(fail); p:= first(open); If solved(p) then exit (success); Remove(p, open); Expand(p); Put all partial graphs except unsolved one into the top of open; Go to LOOP.

5 procedure optimal depth-first and-or
add (s, open); f(s):=0 LOOP: if open = null then exit(fail); p:= first(open); If solved(p) then exit (success); Remove(p, open); Expand(p); Put all partial graphs except unsolved one into the top of open; Sort nodes in open in increasing order of f(p); Go to LOOP.

6 （ （ （ （４） Ｓ （３） （３） Ａ Ｂ （３） Ｃ Ｄ （２） （１） Ｆ G （２） （１） I H （１） t２ t１ （０）

7 （ （ 道のコストがない場合 ① ② ３ ４ ５ ６ ⑦ ⑧ ⑨ ⑩ ⑪ ⑫ ⑬ ⑭ ⑮ ⑯ ⑰ ⑱ 3 Ｓ 3 4 3 4 2 3
min ① 3 ② 4 （ max （ max ３ ４ ５ ６ 3 4 2 3 min min min min ⑦ ⑧ ⑨ ⑩ ⑪ ⑫ ⑬ ⑭ ⑮ ⑯ ⑰ ⑱ ３ ５ ４ ７ ５ ４ ４ ３ ２ ３ ８　６

8 minimax 法 ① ② ３ ４ ５ ６ ⑦ ⑧ ⑨ ⑩ ⑪ ⑫ ⑬ ⑭ ⑮ ⑯ ⑰ ⑱ Ｓ 5 5 4 5 7 4 8
⑦ ⑧ ⑨ ⑩ ⑪ ⑫ ⑬ ⑭ ⑮ ⑯ ⑰ ⑱ ３ ５ ４ ７ ５ ４ ４ ３ ２ ３ ８　６

9 アルファ・ベータ法 ３ ４ ５ ６ ① ② ⑦ ⑧ ⑨ ⑩ ⑪ ⑫ ⑬ ⑭ ⑮ ⑯ ⑰ ⑱ ３ ５ ４ ４ ５ ７ ４ ３ ２ ５ ８ ６
Ｓ (α,β) (5, ∞) αカット ① (-∞,4) ② (-∞,5) βカット 5 (5, ∞) 4 ３ ４ ５ ６ ⑦　⑧　⑨ ⑩　⑪　⑫ 　⑬　⑭　⑮ 　⑯　⑰　⑱ ３ ５ ４ 　４ ５ ７ 　 ４ ３ ２ 　５ 　８　 ６

10 αβ法 ０ ① ② ③ ３ ４ ５ ４ ５ ６ ７ ８ ９ １０ １１ １２ ４ ３ ４ ４ ６ ５ （６） （５） （６） ４　　３　　３　　２　　６　　５　　４　　２　　３　　４　　３　　６　　３　　５　　５　　４　　６　　８

11 最適解の探索 ０ ① ② ③ ４ ４ ５ ６ ４ ７ ８ ９ ５ １０ １１ １２ （５） （６） ４　　３　　３　　２　　６　　５　　４　　２　　３　　４　　３　　６　　３　　５　　５　　４　　６　　８

12 Αβ法と最適解の探索との比較 ０ ① ② ③ ３ ４ ５ ４ ４ ５ ６ ４ ７ ８ ９ ５ １０ １１ １２ ４ ３ ４ ４ ６ ５ （６） （５） （６） （５） （６） ４　　３　　３　　２　　６　　５　　４　　２　　３　　４　　３　　６　　３　　５　　５　　４　　６　　８ αβ 最適解

13 B A C A C B

14 D１：さるの位置の差 D２：箱 〃 〃 D３：バナナ〃 〃 AT（monkey, a） EMPTY AT（box,b） b c a | |

15

16 オペレータ GOTO(u) MOVEBOX(v) CLIMB GRASP 前提条件： AT(monkey, x), AT(box, x)
前提条件：　AT(box, c), ON(monkey, box)

17 ゴール　　　So → Go D３を減らす S４ → Go GRASPを適用 　　　S２　　　　GRASPを適用 D２を減らす MOVEBOXを適用 D１を減らす 　　　S３　　　　GRASPを適用 D１を減らす 　　　S１　　　　MOVEBOXを適用 　　　S２　　　　CLIMBを適用 GOTOを適用

18 recursive procedure GPS(S,G)
1 　LOOP1: if S satisfy G, then exit(S) 2　G と S の差異をすべて求め、最も重要な差異をdとする 3　d を減らすオペレータをすべてoplistに入れる 3　LOOP2: if empty(oplist) then return(fail) 5　operator:= first(oplist), remove(operator, oplist) 　　pc:= operator’s precondition if pc does not decrease the difference, then goto LOOP2 6 if pc= null then goto APPLY 7 S1:= GPS(S, pc) 8 if S1= fail then goto LOOP2 9 APPLY: S:= operator(S1) 10 goto LOOP1

19 階層的計画のオペレータ GOTO(u) MOVEBOX(v) CLIMB GRASP 前提条件： (1)AT(monkey, x)
(3)AT(box, x) CLIMB GRASP 前提条件：　(3)AT(box, c) (2)ON(monkey, box)

20 階層的計画のオペレータ 計画 MOVEBOX(c) GRASP GOTO(u) MOVEBOX(v) CLIMB GRASP
前提条件：　 (3)AT(box, x) CLIMB GRASP 前提条件：　(3)AT(box, c)

21 階層的計画のオペレータ 計画 MOVEBOX(c) CLIMB GRASP GOTO(u) MOVEBOX(v) CLIMB GRASP
前提条件：　 (3)AT(box, x) CLIMB GRASP 前提条件：　(3)AT(box, c) ) (2)ON(monkey, box)

22 階層的計画のオペレータ 計画 GOTO(b) MOVEBOX(c) CLIMB GRASP GOTO(u) MOVEBOX(v) CLIMB
前提条件：　 (3)AT(box, x) (1)AT(monkey, x) CLIMB GRASP 前提条件：　(3)AT(box, c) (2)ON(monkey, box)

23 塔を作る例題 複数の目標のAND/OR木 A B A B C C 初期状態 目標状態 ON(A,B) ON(B,C) ON (B,C)
ON (B,C) 追加:3 ON (A,B) 追加:1 PUTON(A,B) 3 PUTON(B,C) 1 HOLD (A) CLEAR (B) HOLD (B) CLEAR (C) 追加:2 追加:4 追加:３ 削除:４ PICKUP(B) PICKUP(A) 2 4 ONTABLE (A) CLEAR (A) EMPTY ONTABLE (B) CLEAR (B) EMPTY 追加:３ 削除:４ 追加:１ 削除:２ 削除:１