17.プランニング(Planning) 1G01P069 飛田伸一 2004/5/17

プラニングとは？ エージェントに与えられた目標を達成するための一連の行為(action)を自動生成すること。 ロボットが積み木を積み上げる手順 カメラの準備の仕方 巡回セールスマン問題 並列CPUの効率的なタスクの割り当て 2004/5/17

17.1 行為表現(Representing actions) Prologでプランニングするためには、当然プログラムを書かなければならない。 故に、状態、行為をどうやってプログラムとして表すかが問題となる。 2004/5/17

初期状態 ゴール a c b a b c 1 2 3 4 1 2 3 4 2004/5/17

行為に必要なもの 前提条件: 行為を可能にするのに満たさなければならない状態の条件 追加リスト: 行為が実行された後に追加されるもののリスト 削除リスト: 行為が実行されたら消えるもののリスト 2004/5/17

Prologで表現する 状態 前提条件 追加リスト 削除リスト 行為 on( Block, Object) clear( Object) can( Action, Cond) 追加リスト adds( Action, AddRels) 削除リスト delete( Action, DelRels) 行為 move( Block, From, To) 2004/5/17

Prologで表現する 初期状態 [clear(2), clear(4), clear(b), clear( c), on(b,3), on(c,a)]　 目標 [ on( a, b), on( b, c)] 2004/5/17

17.2 手段目標解析でプランを得よう 17.1で状態と行為を表現することが出来た。今度はそれらを使って実際にプランニングを行ってみる。 手段目標解析を用いてプランの導出を行う 2004/5/17

手段目標解析(means-ends analysis) 初期状態とゴールの差を減少させるように，ゴールをサブゴールに分解して解いていく方法 2004/5/17

手段目標解析の例(1) ルールはfig17.2を参照のこと ①目標 on(a,b) これを満たす行為を見つける。 ②Move(a,From,b)　 この行為の前提条件を見つける。 ③[clear(a),clear(b),on(a,From)] clear(b)とon(a, 1)(Fromを1とする)は初期状態ですでにあるので、今度はclear(a)を新たな目標とする。 2004/5/17

手段目標解析の例(2) ④新たな目標 clear(a) これを満たす行為を見つける。 ⑤Move(Block,a,To) この行為の前提条件を見つける。 ⑥[clear(Block),clear(To),on(Block,a)] Block=c,To=2のとき初期状態を満たす。よって move(c,a,2)が出てくる。 つまりプランは[move(c,a,2),move(a,1,b)]となる 2004/5/17

補足 初期状態 [clear(2),clear(4),clear(b),clear( c),on(a,1),on(b,3),on(c,a)] 行為 Move(c,a,2) 前提条件: [clear( c),clear(2), on(c,a)] 追加リスト: [on(c,2),clear(a)] 削除リスト: [on(c,a),clear(2)] [clear(a),clear(b),clear( c),clear(4),on(a,1),on(b,3),on(c,2)] 2004/5/17

補足(2) [clear(a),clear(b),clear( c),clear(4),on(a,1),on(b,3),on(c,2)] 行為 move(a,1,b) 前提条件: [clear(a),clear(b),on(a,1)] 追加リスト: [on(a,b),clear(1)] 削除リスト: [on(a,1),clear(b)] [clear(a),clear( c),clear(1),clear(4),on(a,b),on(b,3),on(c,2)] 目標達成 2004/5/17

手段目標解析によるプランニングアルゴリズム 状態Stateの目標リストGoalsを解決して最終状態FinalStateまでもっていく。 もし、状態StateでGoalsが全て満たされていた場合、FinalState=Stateとなる。そうでなければ以下のステップを行う。 1.まだ解決していない目標Goalを目標リストGoalsの中から選ぶ。 2.今の状態にGoalを加えるような行為Actionを見つける。 3.Actionの前提条件であるConditionを解決することによってActionを可能にする。故に、Conditionが入っている状態MidState1を得る。 4.MidState1にActionを適用し、MidState2を得る。なお、MidState2ではGoalは真になっている。(後ろ向き推論） 5.MidState2でGoalsを解決することにより、FinalStateへもっていく 2004/5/17

Condition Goal Goals PrePlan Action PostPlan State MidState1 MidState2 FinalState 2004/5/17

17.3 目標保護(Protecting goals) 現在の手段目標プランニングの問題点を考える。 2004/5/17

問題がある例(1) 先の問題を解いてみる Plan( Start, [on(a,b),on(b,c)],Plan,_) すると Plan = [move(b,3,c),move(b,c,3),move(c,a,2),move(a,1,b),move(a,b,1),move(b,3,c),move(a,1,b)] が出てくる。 本来なら３ステップで良いはずなのに何故か７ステップのプランが出来た。 どういう推論でこのようなプランが出てきたのか？ 2004/5/17

問題がある例(1) move(b,3,c) 目標on(b,c)を達成する行為 move(b,c,3) 次の行為の条件であるclear( c)を作り出す行為 move(c,a,2) 行為move(a,1,b)の前提条件であるclear(a)を作る行為 move(a,1,b) 目標on(a,b)を達成する行為 move(a,b,1) 行為move(b,3,c)の前提条件であるclear(b)を作る行為 move(b,3,c) 目標on(b,c)を達成する行為(２回目) move(a,1,b) 目標on(a,b)を達成する行為(２回目) すでに達成した目標を壊すときがある。 ２回目はたまたまon(b,c)が達成された時にon(a,b)を達成できる状況にあった。 2004/5/17

問題がある例(2) どうするか？ Plan(Start,[clear(2),clear( 3)].Plan,_) を実行。 するとプランナーは無限に次のことを繰り返す。 move(b,3,2) 目標clear(3)を達成 move(b,2,3) 目標clear(2)を達成 目標を達成しようとするとすでに達成した目標を壊してしまう。 どうするか？ 2004/5/17

Protected Goals(目標保護) すでに達成した目標を保護すればよい 保護用の引数をひとつ導入 ProtectedGoals それに伴いPrologも変更 Plan(State, Goals, ProtectedGoals, Plan, FinalState) この方法を使って例(2)を解くと move(b,3,2) 目標clear(3)を達成 move(b,2,4) clear(3)を壊さないように目標clear(2)を達成 となる。本来はmove(b,3,4)だけで良いのでまだ最適でない。 2004/5/17

17.4 手続き解釈と幅優先(Procedural aspects and breadth-first regime) 今まで使ってきた探索法は深さ優先探索である。 幅優先探索も併用することにより、すこしプランを短くすることができる。 2004/5/17

幅優先探索実装 先に作ったプログラムにconc(Plan,_,_)を入れる。 plan( Start,[on(a,b),on(b,c)],Plan,_). 結果 move(c,a,2) move(b,3,a) move(b,a,c) move(a,1,b) この場合は最適解ではない。move(b,3,a)がいらない。 何故最適解にならないのか？ 2004/5/17

２つの疑問 プランナーはどのような推論をしたのか？ 何故プランナーは最適プランを見つけられないのか？ 2004/5/17

プランナーはどのような推論をしたのか？ 追ってみよう move(a,1,b) 目標on(a,b)を達成(前提条件はclear(a)) move(b,a,c) 前提条件clear(a)を導く。(前提条件はon(b,a)) move(b,3,a) 前提条件on(b,a)を導く。(前提条件はclear(a)) move(c,a,2) 前提条件clear(a)を導く。 プランナーはこの様な推論をした。 2004/5/17

何故プランナーは最適プランを見つけられないのか？ 先のような推論では最適プランは見つけられない。何故こんなことになっているのか？ さっきのプランニングでは目標がずっとon(a,b)だった。 目標on(b,c)が達成できたのは偶然である。 2004/5/17

手段目標プランニングでは不完全。 ほかの目標のことも考えよう 目標を追っている間はほかの目標のことは気にしないから 目標後退 2004/5/17

17.5 目標後退(Goal regression) 状態 S0: Goals0 状態 S: Goals A Goals0は次の特性を備えていなければならない 1.状態S0で行為Aは可能でなければならない。 　故にAの前提条件をGoals0が含んでなければならない 2.Goalsの目標Gについて次のどちらかが成り立つ ・行為AがGを加える ・GがGoals0の中にあり、行為AがGを消さない 与えられたGoalsとAを使いGoal0を決定することをAを通した Goalsの後退という。 2004/5/17

目標後退をプランニングに組み込む 初期状態StartStateから目標リストGoalsを達成するために ・さもなければ、Goalsの中から目標Gを、さらにGを加えるような行為Aを選び、そして、Aを使ってGoalsを退行することによってNewGoalsを得る。さらに、StartStateからNewGoalsを達成するようなプランを見つける。 2004/5/17

impossible 無理なものはimpossibleで定義する. impossible( on(X,X), _). 自分の上に自分は来ない impossible( on(X,Y), Goals) :- 同時に二箇所にいない member( clear(Y), Goals) ; member( on(X,Y1), Goals), Y1 \== Y member( on(X,Y1), Goals), X1 \== X. impossible( clear(X), Goals) :- 同じ場所に違うブロックは乗らない member( on(_,X), Goals). 2004/5/17

目標後退の効果 プログラムを実行してみる 目標後退の結果4ステップかかっていたのが3ステップになった。 2004/5/17

17.6 手段目標プランニングと最良優先探索を組合せる これまで探索には、深さ優先探索、幅優先探索、反復深化法などを使ってきた。 せっかく問題に特有な知識があるのだから、それを元に発見的な最良優先探索を使うと、素早いプランニングをしやすくなる。 2004/5/17

最良優先探索 評価関数とコストという概念を導入して、その時点でもっともコストが低くなりそうな方向に枝を伸ばしていく探索法 “良さそうな”方向へ探索していける 2004/5/17

プランナーへ最良優先探索を導入する 定義するもの (1)状態空間の節点間の後継関係 s(Node1,Node2,Cost) (2)関係による探索の目標節点 goal(Node) (3)関係による発見的関数 h(Node,HeuristicEstimate) (4)探索の開始節点 2004/5/17

状態空間とか Action Cost Node1 Node2 状態がノードとしてあり、それに対して操作。 2004/5/17

プランナーへ最良優先探索を導入する 状態空間の目標集合Goals1とGoals2および行為Aの間に次の関係が成り立つ AはGoals1のいくつかの目標を加える AはGoals1の目標を破壊することなく、しかも Goals2はAを通したGoals1の退行の結果である。 2004/5/17

プランナーへ最良優先探索を導入する このままだと目標リストしか出てこないので Goals -> Action としてプランをだすようにする 2004/5/17

17.7 Uninstantiated actionsと半順序プランニング 能率を良くするためほかのことも考えてみよう Uninstantiated actions and goals 半順序プランニング 2004/5/17

Uninstantiated actions and goals 変数を確定しないまま進めていく方法 2004/5/17

半順序プランニング プランの中で順番を一概に決められないものがあるプランニング(cf 全順序プランニング） 探索空間がプランをノードとするプラン探索空間 2004/5/17

例 a d b e b e a c f d c f 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 2004/5/17

半順序プランニング 上の例で以下の２つのプランは互いに独立である。 Plan1 = [move(b,a,c),move(a,1,b)] Plan2 = [move(e,d,f),move(d,8,e)] そこでプランを [move(b,a,c),move(a,1,b),move(e,d,f),move(d,8,e)] としようが [move(b,a,c),move(e,d,f),move(a,1,b),move(d,8,e)] としようがどちらでも同じである。 2004/5/17

START move(b,a,c) move(e,d,f) move(a,1,b) move(d,8,e) FINISH 2004/5/17

半順序プランニング プランステップ 因果リンク プラン中の個々の行為に付けられるインデックス集合。行為の名前みたいなもの プラン中で、プランステップSが、プランステップWの前提条件のPを追加する時、 　　と記述する。これを因果リンクという。 P S W 2004/5/17

半順序プランニング S W W S V S 順序制約 脅威ステップ 因果リンク　　　　　 に関して、ステップSとW以外で、Pを削除リストにもつステップV あるプランにおいて，VがSとWの間にあるとWが適用できない。それを避けるために、制約順序　　　　 or　　　　 が必要 S W P W S V S W V 2004/5/17

半順序プランニング 完全なプラン 無矛盾なプラン プラン中のすべてのステップの条件リストが、他のステップにより達成されるようなプラン 制約順序に矛盾のないプラン 2004/5/17

半順序プランニングのアルゴリズム 初期化 特別なステップSTARTとFINISHを作る 順序制約リストをORDERとする 空集合で初期化する Pをプランとし、 START 、FINISH 、およびORDERで初期化する 2004/5/17

半順序プランニングのアルゴリズム Pが完全・無矛盾なら完了、or Backtrack P中に、 なる因果リンクがあり、vがこの因果リンクに対する脅威ステップの場合 、 か　　　　　を付加し１へ さもなければ、P中に条件pが満たされないようなwがあるなら Pかオペレータ集合（前提条件、追加リスト、削除リストをあわせたもの）から、pを追加リストに持つようなステップsを探しPにsと　　　　　　　　と　　　　　　　　を追加する sがオペレータ集合から得られたなら、Pに　　　　　　　 　　　　　　　と　　　　　　 　　　　　を追加し１へ p W S V S W V p W S S W S FINISH START S 2004/5/17

半順序プランニング 半順序プランニングを使うと、fig17.2の例も簡単に解ける Uninstantiated actions and goalsと組み合わせる事によって複雑さの緩和ができる （制約） 2004/5/17

まとめ プランニングをPrologでとく場合、さまざまなテクニックがある。それらをうまく使い、良いプランナーをつくる事が大切である。 今日紹介したプランニングは古典的プランニングである。近年では即応プランニング(reactive planning)というものも出てきており、プランニングは着実に進歩している。 2004/5/17

参考文献(書籍) ・Ivan Bratko: "PROLOG Programming for Artificial Intelligence“ ・Prologプログラミング入門　安部憲広　共立出版 1985 　 -上の訳本 ・AIプログラミング　安部憲広・田中和明　近代科学社　1996 -訳本の続き ・人工知能の基礎　馬場口登・山田誠二　昭晃堂　1999 2004/5/17

参考文献(Internet) 人工知能論 http://bruch.sfc.keio.ac.jp/course/AI01/ai01-6/tsld001.htm 問題解決と学習 ～問題解決プログラムの作成と評価～　第２章 http://isl.educ.fukushima-u.ac.jp/~hitomi/soturon/soturon.html プランニング http://www.watanabe.nuie.nagoyau.ac.jp/member/sagawa/AI/chap3.ppt プランニング技術 http://www.jaist.ac.jp/~itota/Lecture/K415-4.ppt 半順序プランニングを調べるのに参照。 2004/5/17

大切なこと Prologに慣れておく Prologの用語をきちんと理解しておく 時間をきちんと取る 理解できなかったらどんどん聞く 2004/5/17

END 2004/5/17

おまけ 2004/5/17

Uninstantiated actions and goals move(b,a,c) move(c,a,1) move(c,a,2) can(move(Block,From,To),[clear(Block),clear(To),on(Block,From)]). move(Something,a,Somewhere) 前提条件 [clear(Something),clear(Somewhere),on(Something,a)] Something = c Somewhere = 2 move(c,a,c) これは駄目 2004/5/17

Uninstantiated actions and goals Can(move(Block,From,To),[clear(Block),clear(To),on(Block,From)]) :- Block(Block), Object(To), ･･･ move(Something,a,Somewhere) can(move(Something,a,somewhere),Condition) move(b,a,1) move(b,a,2) move(b,a,3) move(b,a,4) 2004/5/17

Uninstantiated actions and goals can(move(Block,From,To),[clear(Block),clear(To),on(Block,From),different(Block,To),different(From,To),different(Block,From)]). satisfied(State,[Goal | Goals]) :- holds(Goal),satisfied(Goals). holds(different(X,Y)) これは以下のように定義されている ・もしXとYがマッチしなければdifferent(X,Y)が保たれる ・もしXとYが文字通り一致するならば、この状態は偽となり、この先いくらプランを進めても常にプランは偽となる。その後、状態は関係impossibleとして目標を同じような方法で扱うことができる。 ・さもなければ、(XとYはマッチするが文字的には違う)その場での判断は出来ない。 あとでXとYとの関係を見る事にする。 2004/5/17

M1 = move(a,X,b) M2 = move(b,Y,c) M3 = move(U,a,V) Before(M3,M1) [M3,M1,M2] [M3,M2,M1] [M2,M3,M1] 2004/5/17