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