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 のままでは応用が効かない 任意の行動系列 ( 行動の順番 ) を生成するプログラムの作り方の理論には成っていない プランニングアルゴリズム ロボットやエージェントが 与えられた目標を達成するために必要な行為 (c.on) の系列を自動的に生成する際のアルゴリズム プランニングアルゴリズム プランニングアルゴリズム ロボットやエージェントが 与えられた目標を達成するために必要な行為 (c.on) の系列を自動的に生成する際のアルゴリズム 行為の系列が生成されたら 実世界で実行される 例 :SHRDLU 1

プランニングアルゴリズム ロボットやエージェントが 与えられた目標を達成するために必要な行為 (c.on) の系列を自動的に生成する際のアルゴリズム 初期状態からゴールを実現する行動プランを生成 ゴール :Pickup 3 (pick up a big red block.) プラン Pickup 4 初期状態からゴールを実現する行動プランを生成 4 3 2 1 初期状態 5 7 6 8 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

初期状態と目標状態 動作規則 {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

動作の適用 動作の実行によって変更されていない事実 ( リテラル ) は不変のまま保たれる 動作規則に 変化するリテラルのみを記述する 記述の無い物は変化しない 削除リスト 追加リストの順に状態に適用する 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

例 例 {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

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

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

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

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

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

再帰的に 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

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