4th.pptx

Size: px

Start display at page:

Download "4th.pptx"

がんまはぎにわ
7 years ago
Views:

1 SHRDLU の実行例人工知能今井倫太 pick up a big red block. OK Pickup 4 Put 4 Table Real World Interac.on Pickup 3 SHRDLU SHRDLU のままでは応用が効かない任意の行動系列 ( 行動の順番 ) を生成するプログラムの作り方の理論には成っていないプランニングアルゴリズムロボットやエージェントが与えられた目標を達成するために必要な行為 (c.on) の系列を自動的に生成する際のアルゴリズムプランニングアルゴリズムプランニングアルゴリズムロボットやエージェントが与えられた目標を達成するために必要な行為 (c.on) の系列を自動的に生成する際のアルゴリズム行為の系列が生成されたら実世界で実行される例 :SHRDLU 1

2 プランニングアルゴリズムロボットやエージェントが与えられた目標を達成するために必要な行為 (c.on) の系列を自動的に生成する際のアルゴリズム初期状態からゴールを実現する行動プランを生成ゴール :Pickup 3 (pick up a big red block.) プラン Pickup 4 初期状態からゴールを実現する行動プランを生成初期状態 Real World Interac.on Put 4 Table Pickup 3 最も基礎的なプランニングアルゴリズム STRIPS 1971 年スタンフォード大学で開発される STRIPS: Stanford Research Ins.tute Problem Solver 最も基本的なプランニングアルゴリズム複雑な問題には対処できない場合あり実世界 ( ロボットへの使用 ) にも不向きな場合あり構成要素状態集合例 :SHRDLU の環境状態を表す D 初期状態今の環境の状態目標状態動作規則の集合状態集合現在の環境の状態を表す集合の要素をリテラルと呼ぶ状態集合現在の環境の状態を表す集合の要素をリテラルと呼ぶ {lear(), lear(), On(, ), HandEmpty, OnTable(), OnTable()} D { } 2

3 初期状態と目標状態動作規則 {lear(), lear(), On(, ), HandEmpty, OnTable(), OnTable()} 目標状態 G: {On(,), On(,)} 動作条件リスト : 実行するための条件削除リスト : 実行の結果消える事実追加リスト : 実行の結果生じる事実プラン à a1, a2, a3,,an 動作規則動作条件リスト : 実行するための条件削除リスト : 実行の結果消える事実追加リスト : 実行の結果生じる事実 pickup(x): テーブル上のブロックを持ち上げる条件リスト :[OnTable(X), lear(x), HandEmpty] 削除リスト :[OnTable(X), lear(x), HandEmpty] 追加リスト :[Holding(X)] 動作の適用動作の実行によって変更されていない事実 ( リテラル ) は不変のまま保たれる動作の適用動作の実行によって変更されていない事実 ( リテラル ) は不変のまま保たれる動作規則に変化するリテラルのみを記述する記述の無い物は変化しない動作の適用動作の実行によって変更されていない事実 ( リテラル ) は不変のまま保たれる動作規則に変化するリテラルのみを記述する記述の無い物は変化しない pickup(x): テーブル上のブロックを持ち上げる条件リスト :[OnTable(X), lear(x), HandEmpty] 削除リスト :[OnTable(X), lear(x), HandEmpty] 追加リスト :[Holding(X)] pickup() {lear(), lear(), On(, ), HandEmpty, OnTable(), OnTable()}?? pickup(x): テーブル上のブロックを持ち上げる条件リスト :[OnTable(X), lear(x), HandEmpty] 削除リスト :[OnTable(X), lear(x), HandEmpty] 追加リスト :[Holding(X)] pickup() {lear(), lear(), On(, ), HandEmpty, OnTable(), OnTable()}?? 3

4 動作の適用動作の実行によって変更されていない事実 ( リテラル ) は不変のまま保たれる動作規則に変化するリテラルのみを記述する記述の無い物は変化しない削除リスト追加リストの順に状態に適用する pickup(x): テーブル上のブロックを持ち上げる条件リスト :[OnTable(X), lear(x), HandEmpty] 削除リスト :[OnTable(X), lear(x), HandEmpty] 追加リスト :[Holding(X)] pickup() {lear(), lear(), On(, ), HandEmpty, OnTable(), OnTable()}?? プランの生成線形仮説前向きプランニング初期状態から目標状態に向かって動作規則を探す後ろ向きプランニング目標状態から初期状態に向かって動作規則を探す前向きプランニング後ろ向きプランニング STRIPS 手段目標解析 Means- ends analysis 初期状態とゴールの差を減少させるように目標 ( ゴール ) を副目標 ( サブゴール ) に分解して動作系列を見つけて行く指数的に探索木が大きくなってしまう 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) lear(x) HandEmpty 削除リスト : OnTable(x), lear(x), HandEmpty 追加リスト :Holding(x) l putdown(x): 手に持ったブロック x をテーブル上に置く前提条件 : Holding(x) 削除リスト : Holding(x) 追加リスト :OnTable(x), lear(x), HandEmpty l stack(x, y): 手に持ったブロック x を y の上に積む前提条件 :Holding(x) lear(y) 削除リスト : Holding(x), lear(y) 追加リスト : HandEmpty, On(x,y), lear(x) l unstack(x, y): y の上に積まれたブロック x を手に持つ前提条件 : HandEmpty On(x,y) lear(x) 削除リスト : HandEmpty, On(x,y), lear(x) 追加リスト : Holding(x), lear(y) 4

5 例例 {lear(), lear(), On(, ), HandEmpty, OnTable(), OnTable()} 目標状態 G: {On(,), On(,)} {lear(), lear(), On(, ), HandEmpty, OnTable(), OnTable()} 目標状態 G: {On(,), On(,)} 予想 :unstack(,),putdown(),pickup(), stack(,),pickup(),stack(,) プラン à a1, a2, a3,,an プラン à a1, a2, a3,,an Step1 Step2 D:{On(,),On(,)} D は空ではないのでスキップ D:{On(,),On(,)} {lear(), lear(), On(, ), HandEmpty, OnTable(), OnTable()} 目標状態 G: {On(,),On(,)} Step3 差 D の中から副目標を一つ選択しそれを達成する動作規則 O を選択する D:{On(,),On(,)} 手段目標分析 D を実現する動作 :stack(,), stack(,) D を最も破壊しない動作 :unstack(,),unstack(,) I で最も実行できそうな動作 :pickup(),unstack(,) stack(,), を選ぶ Step4 再帰的に STRIPS(I, P) を呼ぶただし P は動作規則 O の前提条件式である stack(,) P:{Holding(),lear()} 新たなサブゴールこれが成立しないと stack(,) が実行できない STRIPS(I, P): 初期状態 I から新たなサブゴール P までのプランを作る 5

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

7 Step4(Step4(Step3)) 差 D の中から副目標を一つ選択しそれを達成する動作規則 O を選択する D:{lear()} Step4(Step4(Step4)) 再帰的に STRIPS(I, P) を呼ぶただし P は動作規則 O の前提条件式である手段目標分析 D を実現する動作 : unstack(,),unstack(,),stack(,),stack(,),putdown() D を最も破壊しない動作 :pickup(),stack(,),stack(,) I で最も実行できそうな動作 :pickup(),unstack(,) unstack(,) P:{HandEmpty,On(,),lear()} 新たなサブゴールこれが成立しないと unstack(,) が実行できない STRIPS(I, P): 初期状態 I から新たなサブゴール P までのプランを作る unstack(,) をまず試す ( 失敗したら次を試す ) Step4(Step4(Step4(Step1))) D:{ } Step4(Step4(Step4(Step2))) D は空なので終了 Step4(Step4(Step5) へ行く {lear(), lear(), On(, ), HandEmpty, OnTable(), OnTable()} {HandEmpty,On(,),lear()} Step4(Step4(Step5)) Step 4 で得た計画 (P を充足する状態に到達するための計画 ) の最後に O を追加する Step4(Step4(Step4))) で得た計画 = {} <- STRIPS(I,P) の返り値 O(Step4(Step4(Step3)) で得た計画 ) = unstack(,) Plan = {} + unstack(,) = {unstack(,)} Step4(Step4(Step6)) 状態 I に Step5 で得られた計画を適用しその結果得られた状態を Q とする {lear(), lear(), On(, ), HandEmpty, OnTable(), OnTable()} Plan = {unstack(,)} {lear(), OnTable(), OnTable(), Holding(), lear()} 7

8 Step4(Step4(Step7)) 再帰的に STRIPS(Q, G) を呼ぶ {lear(), OnTable(), OnTable(), Holding(), lear()} Step4(Step4(Step7(Step1))) D:{HandEmpty} この間のプランを見つける {Ontable(),lear(),HandEmpty} STRIPS(Q,G) と書いてあるので G:{on(,),on(,)} が目標になると一瞬思うかもしれないが Step4(Step4(Step1))) で呼ばれた STPRIS(I, G) の G はこの P であることに注意! 再帰呼び出しに慣れる! {lear(), OnTable(), OnTable(), Holding(), lear()} {Ontable(),lear(),HandEmpty} Step4(Step4(Step7(Step2))) Dは空ではないのでスキップ D:{HandEmpty} Step4(Step4(Step7(Step3))) 差 D の中から副目標を一つ選択しそれを達成する動作規則 O を選択する D:{HandEmpty} 手段目標分析 {lear(), OnTable(), Dを実現する動作 : OnTable(), Holding(), lear()} putdown(),putdown(),putdown(),stack(,),, stack(,) Dを最も破壊しない動作 : putdown(),putdown(),putdown(),stack(,),, stack(,) Iで最も実行できそうな動作 :putdown(), stack(,), stack(,) Putdown() をまず試す ( 失敗したら次を試す ) もし stack(,) を選ぶようなプログラムを書いてしまったら? Step4(Step4(Step7(Step4))) 再帰的に STRIPS(I, P) を呼ぶただし P は動作規則 O の前提条件式である Step4(Step4(Step7(Step4(Step1)))) putdown() P:{Holding()} 新たなサブゴールこれが成立しないと putdown() が実行できない D:{} STRIPS(I, P): 初期状態 I から新たなサブゴール P までのプランを作る {lear(), OnTable(), OnTable(), Holding(), lear()} {Holding()} 8

9 Step4(Step4(Step7(Step4(Step2)))) D は空なので終了 Step4(Step4(Step7(Step5))) へ行く Step4(Step4(Step7(Step5))) Step 4 で得た計画 (P を充足する状態に到達するための計画 ) の最後に O を追加する Step4(Step4(Step4))) で得た計画 = {} <- STRIPS(I,P) の返り値 O(Step4(Step4(Step3)) で得た計画 ) = putdown() Plan = {} + putdown() = {putdown()} Step4(Step4(Step7(Step6))) 状態 I に Step5 で得られた計画を適用しその結果得られた状態を Q とする中間状態 Q( 再帰的に呼ばれているので一つ上の Q が初期状態 ): {lear(), OnTable(), OnTable(), Holding(), lear()} Plan = {putdown()} 新 {lear(), OnTable(), OnTable(), lear(), Ontable(), HandEmpty,lear()} Step4(Step4(Step7(Step7))) 再帰的に STRIPS(Q, G) を呼ぶ新 {lear(), OnTable(), OnTable(), lear(), Ontable(), HandEmpty,lear()} この間のプランを見つける {Ontable(),lear(),HandEmpty} STRIPS(Q,G) と書いてあるので G:{on(,),on(,)} が目標になると一瞬思うかもしれないが Step4(Step4(Step1))) で呼ばれた STPRIS(I, G) の G はこの P であることに注意! 再帰呼び出しに慣れる! Step4(Step4(Step7(Step7(Step1)))) D:{} Step4(Step4(Step7(Step7(Step2)))) D は空なので終了 Step4(Step4(Step7(Step8))) へ行く新 {lear(), OnTable(), OnTable(), lear(), Ontable(), HandEmpty,lear()} {Ontable(),lear(), HandEmpty} 9

10 Step4(Step4(Step7(Step8))) Step5 で得られた計画の末尾に Step7 で得られた計画を付加する ( 実際には step4(step4(step7(step5)))) Step4(Step4(Step7(Step9))) Step8 で得られた計画を返却して終了する step4(step4(step7(step5)))) の計画 : Plan = {putdown()} step4(step4(step7(step7)))) の計画 : Plan = {} Plan = {putdown()} + {} = {putdown()} Plan = {putdown()} を Step4(Step4(Step7)) 計画として返り値を返す Step4(Step4(Step8)) Step5 で得られた計画の末尾に Step7 で得られた計画を付加する ( 実際には step4(step4(step5))) Step4(Step4(Step9)) Step8 で得られた計画を返却して終了する step4(step4(step5))) の計画 : Plan = {unstack(,)} step4(step4(step7))) の計画 : Plan = {putdown()} Plan = {unstack(,)} + {putdown()} + {} = {unstack(,), putdown()} Plan = {unstack(,), putdown()} を Step4(Step4) の計画として返り値を返す Step4(Step5) Step 4 で得た計画 (P を充足する状態に到達するための計画 ) の最後に O を追加する Step4(Step4)) で得た計画 : Plan = {unstack(,), putdown()} <- STRIPS(I,P) の返り値 O(Step4(Step3) で得た計画 ) = pickup() Plan = {unstack(,), putdown()} + pickup() = {unstack(,), putdown(), pickup()} Step4(Step6) 状態 I に Step5 で得られた計画を適用しその結果得られた状態を Q とする {lear(), lear(), On(, ), HandEmpty, OnTable(), OnTable()} Plan = {unstack(,), putdown(), pickup()} {lear(), OnTable(), OnTable(), lear(), Holding()} 10

11 再帰的に STRIPS(Q, G) を呼ぶ Step4(Step7) {lear(), OnTable(), OnTable(), lear(), Holding()} Step4(Step7(Step1)) D:{} {Holding(),lear()} この間のプランを見つける STRIPS(Q,G) と書いてあるので G:{on(,),on(,)} が目標になると一瞬思うかもしれないが Step4(Step4(Step1))) で呼ばれた STPRIS(I, G) の G はこの P であることに注意! 再帰呼び出しに慣れる! {lear(), OnTable(), OnTable(), lear(), Holding()} {Holding(),lear()} Step4(Step7(Step2)) D は空なので終了 Step4(Step8)) へ行く Step4(Step8) Step5 で得られた計画の末尾に Step7 で得られた計画を付加する ( 実際には step4(step5)) step4(step5) の計画 : Plan = {unstack(,), putdown(), pickup()} Step4(step7)) の計画 : Plan = {} Plan ={unstack(,), putdown(), pickup()}+ {} = {unstack(,), putdown(), pickup()} Step4(Step9) Step8 で得られた計画を返却して終了する Plan = {unstack(,), putdown(), pickup()} を Step4 の計画として返り値を返す Step5 Step 4 で得た計画 (P を充足する状態に到達するための計画 ) の最後に O を追加する Step4 で得た計画 : Plan = {unstack(,), putdown(), pickup()}<- STRIPS(I,P) の返り値 O(Step3 で得た計画 ) = stack(,) Plan = {unstack(,), putdown(), pickup()}+ stack(,) = {unstack(,), putdown(), pickup(),stack(,)} 11

12 Step6 状態 I に Step5 で得られた計画を適用しその結果得られた状態を Q とする {lear(), lear(), On(, ), HandEmpty, OnTable(), OnTable()} Plan = {unstack(,), putdown(), pickup(),stack(,)} { OnTable(), On(,), lear(), OnTable(), lear(), HandEmpty} 再帰的に STRIPS(Q, G) を呼ぶ Step7 { OnTable(), On(,),, lear(), OnTable(), lear(), HandEmpty} 目標状態 P: D:{On(,),On(,)} この間のプランを見つけるつづく 12

5th-ans.pptx

5th-ans.pptx STRIPS のアルゴリズム STRIPS(I,G) : I 初期状態のリスト G 目標状態のリスト Step1. Step2. Step3. 差 D の中から副目標を一つ選択しそれを達成する動作規則 O を選択する Step4. 再帰的に STRIPS(I, P) を呼ぶただし P は動作規則 O の前提条件式である Step5. Step 4 で得た計画 (P を充足する状態に到達するための計画