5th-ans.pptx

Size: px

Start display at page:

Download "5th-ans.pptx"

ともあきふじた
7 years ago
Views:

1 STRIPS のアルゴリズム STRIPS(I,G) : I 初期状態のリスト G 目標状態のリスト Step1. Step2. Step3. 差 D の中から副目標を一つ選択しそれを達成する動作規則 O を選択する Step4. 再帰的に STRIPS(I, P) を呼ぶただし P は動作規則 O の前提条件式である Step5. Step 4 で得た計画 (P を充足する状態に到達するための計画 ) の最後にO を追加する Step6. 状態 I に Step5で得られた計画を適用しその結果得られた状態をQ とする Step7. 再帰的にSTRIPS(Q, G) を呼ぶ Step8.Step5で得られた計画の末尾にStep7で得られた計画を付加する Step9.Step8で得られた計画を返却して終了する動作規則 l pickup(x): テーブル上のブロック x を手に持つ前提条件 :OnTable(x) Clear(x) HandEmpty 削除リスト : OnTable(x), Clear(x), HandEmpty 追加リスト :Holding(x) l putdown(x): 手に持ったブロック x をテーブル上に置く前提条件 : Holding(x) 削除リスト : Holding(x) 追加リスト :OnTable(x), Clear(x), HandEmpty l stack(x, y): 手に持ったブロック x を y の上に積む前提条件 :Holding(x) Clear(y) 削除リスト : Holding(x), Clear(y) 追加リスト : HandEmpty, On(x,y), Clear(x) l unstack(x, y): y の上に積まれたブロック x を手に持つ前提条件 : HandEmpty On(x,y) Clear(x) 削除リスト : HandEmpty, On(x,y), Clear(x) 追加リスト : Holding(x), Clear(y) やってみよう Step1 目標状態 G: {On(A,C)} (2) D: {On(A,C)} (1) 予想 :unstack(c,a),putdown(c),pickup(a),stack(a,c) C A プラン à a1, a2, a3,,an A C 目標状態 G: {On(A,C)} Step2 Dは空ではないのでスキップ D: {On(A,C)} (3) Step3 差 D の中から副目標を一つ選択しそれを達成する動作規則 O を選択する D: {On(A,C)} 手段目標分析 Dを実現する動作 :stack(a,c) Dを最も破壊しない動作 :unstack(a,c) (Dを逆方向に一つ戻る動作) Iで最も実行できそうな動作 :unstack(c,a) stack(a,c), を選ぶ (4) 1

2 Step4 再帰的に STRIPS(I, P) を呼ぶただし P は動作規則 O の前提条件式である Step4(Step1) stack(a,c) (5) P:{Holding(A),Clear(C)} 新たなサブゴールこれが成立しないとstack(A,B) が実行できない D:{Holding(A)} STRIPS(I, P): 初期状態 Iから新たなサブゴールPまでのプランを作る (6) つまり STRIPS(, {Holding(A),Clear(C)} ) を呼ぶ (5) (6) {Holding(A),Clear(C)} (5) Step4(Step2) Dは空ではないのでスキップ D:{Holding(A)} Step4(Step3) 差 D の中から副目標を一つ選択しそれを達成する動作規則 O を選択する D:{Holding(A)} 手段目標分析 (7) Dを実現する動作 :pickup(a), unstack(a,c) Dを最も破壊しない動作 :putdown(a), stack(a,c) (Dを逆方向に一つ戻る動作) Iで最も実行できそうな動作 :unstack(c,a) (8) pickup(a) をまず試す ( 失敗したら次を試す ) Step4(Step4) 再帰的に STRIPS(I, P) を呼ぶただし P は動作規則 O の前提条件式である Step4(Step4(Step1)) pickup(a) (9) P:{Ontable(A),Clear(A),HandEmpty} 新たなサブゴールこれが成立しないと pickup(a) が実行できない D:{Clear(A)} STRIPS(I, P): 初期状態 Iから新たなサブゴールPまでのプランを作る (10) STRIPS(, {Ontable(A),Clear(A),HandEmpty} ) を呼ぶ (9) (10) {Ontable(A),Clear(A),HandEmpty} (9) 2

3 Step4(Step4(Step2)) Dは空ではないのでスキップ D:{Clear(A)} Step4(Step4(Step3)) 差 D の中から副目標を一つ選択しそれを達成する動作規則 O を選択する D:{Clear(A)} 手段目標分析 (11) Dを実現する動作 : unstack(c,a), stack(a,c),putdown(a) Dを最も破壊しない動作 :pickup(a),stack(c,a), unstack(a,c) (Dを逆方向に一つ戻る動作) Iで最も実行できそうな動作 :unstack(c,a) (12) unstack(c,a) をまず試す ( 失敗したら次を試す ) Step4(Step4(Step4)) 再帰的に STRIPS(I, P) を呼ぶただし P は動作規則 O の前提条件式である Step4(Step4(Step4(Step1))) unstack(c,a) (13) P:{HandEmpty,On(C,A),Clear(C)} 新たなサブゴールこれが成立しないと unstack(c,a) が実行できない D:{ } STRIPS(I, P): 初期状態 Iから新たなサブゴールPまでのプランを作る (14) STRIPS(, {HandEmpty,On(C,A),Clear(C)} ) (13) (14) {HandEmpty,On(C,A),Clear(C)} (13) Step4(Step4(Step4(Step2))) (15) Dは空なので終了 Step4(Step4(Step5) へ行く返り値 : path = {} Step4(Step4(Step5)) Step 4 で得た計画 (P を充足する状態に到達するための計画 ) の最後に O を追加する (16) Step4(Step4(Step4))) で得た計画 = {} <- STRIPS(I,P) の返り値 O(Step4(Step4(Step3)) で得た計画 ) = unstack(c,a) (17) Plan = {} + unstack(c,a) = {unstack(c,a)} (16) (17) (18) 3

4 Step4(Step4(Step6)) 状態 I に Step5 で得られた計画を適用しその結果得られた状態を Q とする (19) Plan = {unstack(c,a)} (20) Holding(C), Clear(A)} Step4(Step4(Step7)) 再帰的に STRIPS(Q, G) を呼ぶ Holding(C), Clear(A)} この間のプランを見つける {Ontable(A),Clear(A),HandEmpty} (21) STRIPS( Holding(C), Clear(A)}, {Ontable(A),Clear(A),HandEmpty} ) (22) STRIPS(Q,G) と書いてあるので G:{on(A,C)} が目標になると一瞬思うかもしれないが Step4(Step4(Step1))) で呼ばれた STPRIS(I, G) の G はこの P であることに注意! 再帰呼び出しに慣れる! Step4(Step4(Step7(Step1))) D:{HandEmpty} Step4(Step4(Step7(Step2))) Dは空ではないのでスキップ D:{HandEmpty} Holding(C), Clear(A)} (21) {Ontable(A),Clear(A),HandEmpty} (22) Step4(Step4(Step7(Step3))) 差 D の中から副目標を一つ選択しそれを達成する動作規則 O を選択する D:{HandEmpty} 手段目標分析 D を実現する動作 : putdown(a),putdown(c),stack(a,c),stack(c,a) D を最も破壊しない動作 (D を逆方向に一つ戻る動作 ) pickup(a),pickup(c),unstack(a,c),unstack(c,a) I( ここでは Q) で最も実行できそうな動作 :putdown(c),stack(c,a) Putdown(C) をまず試す ( 失敗したら次を試す ) Step4(Step4(Step7(Step4))) 再帰的に STRIPS(I, P) を呼ぶただし P は動作規則 O の前提条件式である putdown(c) P:{Holding(C)} 新たなサブゴールこれが成立しないと putdown(c) が実行できない STRIPS(I, P): 初期状態 Iから新たなサブゴールPまでのプランを作るつまり STRIPS( Holding(C), Clear(A)}, {Holding(C)} ) を呼ぶ (23) (24) 4

5 Step4(Step4(Step7(Step4(Step1)))) D:{} Step4(Step4(Step7(Step4(Step2)))) D は空なので終了 Step4(Step4(Step7(Step5))) へ行く Holding(C), Clear(A)} {Holding(C)} 返り値 : path = {} Step4(Step4(Step7(Step5))) Step 4 で得た計画 (P を充足する状態に到達するための計画 ) の最後に O を追加する (25) Step4(Step4(Step7(Step4)))) で得た計画 = {} <- STRIPS(I,P) の返り値 (26) O(Step4(Step4(Step7(Step3))) で得た計画 ) = putdown(c) Plan = {} + putdown(c) = {putdown(c)} (25) (26) (27) Step4(Step4(Step7(Step6))) 状態 I に Step5 で得られた計画を適用しその結果得られた状態を Q とする (28) 中間状態 Q( 再帰的に呼ばれているので一つ上の Q が初期状態 ): Holding(C), Clear(A)} Plan = {putdown(c)} 新 Clear(C), Ontable(C), HandEmpty,Clear(A)} (28) Step4(Step4(Step7(Step7))) 再帰的に STRIPS(Q, G) を呼ぶ新 Clear(C), Ontable(C), HandEmpty,Clear(A)} Step4(Step4(Step7(Step7(Step1)))) D:{} (29) この間のプランを見つける {Ontable(A),Clear(A),HandEmpty} (28) STRIPS( Clear(C), Ontable(C), HandEmpty,Clear(A)}, {Ontable(A),Clear(A),HandEmpty} ) を呼ぶ (29) 新 Clear(C), Ontable(C), HandEmpty,Clear(A)} (28) {Ontable(A),Clear(A), HandEmpty} (29) 5

6 Step4(Step4(Step7(Step7(Step2)))) Dは空なので終了 Step4(Step4(Step7(Step8))) へ行く返り値 : path = {} Step4(Step4(Step7(Step8))) Step5( 実際には step4(step4(step7(step5)))) で得られた計画の末尾にStep7( 実際には step4(step4(step7(step7)))) で得られた計画を付加する step4(step4(step7(step5)))) の計画 : (30) Plan = {putdown(c)} step4(step4(step7(step7)))) の計画 : Plan = {} Plan = {putdown(c)} + {} = {putdown(c)} (30) (31) Step4(Step4(Step7(Step9))) Step8( 実際には step4(step4(step7(step8)))) で得られた計画を返却して終了するつまり (31) Plan = {putdown(c)} を Step4(Step4(Step7)) の計画として返り値を返す Step4(Step4(Step8)) Step5( 実際には step4(step4(step5))) で得られた計画の末尾にStep7( 実際には step4(step4(step7))) で得られた計画を付加する step4(step4(step5))) の計画 : (32) Plan = {unstack(c,a)} step4(step4(step7))) の計画 : (33) Plan = {putdown(c)} (32) (33) Plan = {unstack(c,a)} + {putdown(c)} = {unstack(c,a), putdown(c)} (34) Step4(Step4(Step9)) Step8 で得られた計画を返却して終了する (34) Plan = {unstack(c,a), putdown(c)} を Step4(Step4) の計画として返り値を返す Step4(Step5) Step 4 で得た計画 (P を充足する状態に到達するための計画 ) の最後に O を追加する Step4(Step4)) で得た計画 : Plan = {unstack(c,a), putdown(c)} <- STRIPS(I,P) の返り値 (35) O(Step4(Step3) で得た計画 ) = pickup(a) (36) (35) (36) Plan = {unstack(c,a), putdown(c)} + pickup(a) = {unstack(c,a), putdown(c), pickup(a)} (37) 6

7 Step4(Step6) 状態 I に Step5 で得られた計画を適用しその結果得られた状態を Q とする Plan = {unstack(c,a), putdown(c), pickup(a)} {OnTable(C), Clear(C), Holding(A)} (38) 再帰的に STRIPS(Q, G) を呼ぶ Step4(Step7) {OnTable(C), Clear(C), Holding(A)} {Holding(A),Clear(C)} (39) この間のプランを見つけるつまり STRIPS({OnTable(C), Clear(C), Holding(A)}, {Holding(A),Clear(C)} ) を呼ぶ (39) Step4(Step7(Step1)) (40) D:{} Step4(Step7(Step2)) D は空なので終了 Step4(Step8)) へ行く返り値 : path = {} {OnTable(C), Clear(C), Holding(A)} {Holding(A),Clear(C)} Step4(Step8) Step5( 実際には step4(step5)) で得られた計画の末尾に Step7( 実際には step4(step7)) で得られた計画を付加する step4(step5) の計画 : (41) Plan = {unstack(c,a), putdown(c), pickup(a)} Step4(step7)) の計画 : Plan = {} (41) Plan ={unstack(c,a), putdown(c), pickup(a)}+ {} = {unstack(c,a), putdown(c), pickup(a)} (41) Step4(Step9) Step8 で得られた計画を返却して終了する (41) Plan = {unstack(c,a), putdown(c), pickup(a)} を Step4の計画として返り値を返す 7

8 Step5 Step 4 で得た計画 (P を充足する状態に到達するための計画 ) の最後に O を追加する Step4で得た計画 : (42) Plan = {unstack(c,a), putdown(c), pickup(a)}<- STRIPS(I,P) の返り値 (43) O(Step3で得た計画 ) = stack(a,c) (42) (43) Plan = {unstack(c,a), putdown(c), pickup(a)} + stack(a,c) = {unstack(c,a), putdown(c), pickup(a),stack(a,c)} (44) Step6 状態 I に Step5 で得られた計画を適用しその結果得られた状態を Q とする {Clear(B), Clear(C), On(C, A), HandEmpty, OnTable(A), OnTable(B)} (45) Plan = {unstack(c,a), putdown(c), pickup(a),stack(a,c)} {Clear(A), OnTable(C), On(A,C), HandEmpty} (45) 再帰的に STRIPS(Q, G) を呼ぶ Step7 {Clear(A), OnTable(C), On(A,C), HandEmpty} Step7(Step1) D:{} 目標状態 P: D:{On(A,C)} この間のプランを見つける (45) つまり STRIPS({Clear(A),OnTable(C), On(A,C), HandEmpty}, {On(A,C)}) を呼ぶ {Clear(A), OnTable(C), On(A,C), HandEmpty} (45) {On(A,C)} Step7(Step2) Dは空なので終了 Step8へ行く返り値 : path = {} Step8 Step5 で得られた計画の末尾に Step7 で得られた計画を付加する step5 の計画 : Plan = {unstack(c,a), putdown(c), pickup(a),stack(a,c)} step7 の計画 : Plan = {} Plan ={unstack(c,a), putdown(c), pickup(a),stack(a,c)} + {} = {unstack(c,a), putdown(c), pickup(a),stack(a,c)} 8

9 Step9 Step8 で得られた計画を返却して終了する Plan = {unstack(c,a), putdown(c), pickup(a),stack(a,c)} を計画として返り値を返す 9

4th.pptx

4th.pptx SHRDLU の実行例人工知能今井倫太 pick up a big red block. OK Pickup 4 Put 4 Table 4 3 2 1 7 6 8 5 Real World Interac.on Pickup 3 SHRDLU SHRDLU のままでは応用が効かない任意の行動系列 ( 行動の順番 ) を生成するプログラムの作り方の理論には成っていないプランニングアルゴリズム