プラニングとは？ - Ueda Lab. Homepage

17.プランニング(Planning)
1G01P069
飛田伸一
2004/5/17
1
プラニングとは？
エージェントに与えられた目標を達成するた
めの一連の行為(action)を自動生成する
こと。
 ロボットが積み木を積み上げる手順
 カメラの準備の仕方
 巡回セールスマン問題
 並列CPUの効率的なタスクの割り当て
2004/5/17
2
17.1 行為表現(Representing
actions)


Prologでプランニングするためには、当然
プログラムを書かなければならない。
故に、状態、行為をどうやってプログラムと
して表すかが問題となる。
2004/5/17
3
1
初期状態
ゴール
c
a
a
b
c
2
2004/5/17
b
3
4
1
2
3
4
4
行為に必要なもの
前提条件:
行為を可能にするのに満たさなければなら
ない状態の条件
追加リスト:
行為が実行された後に追加されるもののリ
スト
削除リスト:
行為が実行されたら消えるもののリスト
2004/5/17
5
Prologで表現する

状態



前提条件


adds( Action, AddRels)
削除リスト


can( Action, Cond)
追加リスト


on( Block, Object)
clear( Object)
delete( Action, DelRels)
行為

2004/5/17
move( Block, From, To)
6
Prologで表現する

初期状態


[clear(2), clear(4), clear(b), clear( c),
on(b,3), on(c,a)]
目標

2004/5/17
[ on( a, b), on( b, c)]
7
17.2 手段目標解析でプランを得
よう


17.1で状態と行為を表現することが出来た。
今度はそれらを使って実際にプランニング
を行ってみる。
手段目標解析を用いてプランの導出を行う
2004/5/17
8
手段目標解析(means-ends
analysis)

初期状態とゴールの差を減少させるように，
ゴールをサブゴールに分解して解いていく
方法
2004/5/17
9
手段目標解析の例(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
10
手段目標解析の例(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
11
補足
初期状態
[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
12
補足(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
13
手段目標解析によるプランニン
グアルゴリズム
状態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
14
Condition
PrePlan
State
2004/5/17
Goal
Action
MidState1
Goals
PostPlan
MidState2
FinalState
15
17.3 目標保護(Protecting
goals)

現在の手段目標プランニングの問題点を
考える。
2004/5/17
16
問題がある例(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),m
ove(a,b,1),move(b,3,c),move(a,1,b)]
が出てくる。
本来なら３ステップで良いはずなのに何故か７ステップのプ
ランが出来た。
どういう推論でこのようなプランが出てきたのか？

2004/5/17
17
問題がある例(1)
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)
目標on(b,c)を達成する行為
次の行為の条件であるclear( c)を作り出す行為
行為move(a,1,b)の前提条件であるclear(a)を作る行為
目標on(a,b)を達成する行為
行為move(b,3,c)の前提条件であるclear(b)を作る行為
目標on(b,c)を達成する行為(２回目)
目標on(a,b)を達成する行為(２回目)
すでに達成した目標を壊すときがある。
２回目はたまたまon(b,c)が達成された時にon(a,b)を達成できる状況に
あった。
2004/5/17
18
問題がある例(2)
Plan(Start,[clear(2),clear( 3)].Plan,_)
を実行。
するとプランナーは無限に次のことを繰り返す。
move(b,3,2) 目標clear(3)を達成
move(b,2,3) 目標clear(2)を達成
move(b,3,2) 目標clear(3)を達成
move(b,2,3) 目標clear(2)を達成
目標を達成しようとするとすでに達成した目標を壊してしま
う。
どうするか？
2004/5/17
19
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
20
17.4 手続き解釈と幅優先(Procedural
aspects and breadth-first regime)


今まで使ってきた探索法は深さ優先探索
である。
幅優先探索も併用することにより、すこしプ
ランを短くすることができる。
2004/5/17
21
幅優先探索実装

先に作ったプログラムに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
22
２つの疑問


プランナーはどのような推論をしたのか？
何故プランナーは最適プランを見つけられ
ないのか？
2004/5/17
23
プランナーはどのような推論をし
たのか？

追ってみよう
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
24
何故プランナーは最適プランを
見つけられないのか？



先のような推論では最適プランは見つけら
れない。何故こんなことになっているの
か？
さっきのプランニングでは目標がずっと
on(a,b)だった。
目標on(b,c)が達成できたのは偶然である。
2004/5/17
25

手段目標プランニングでは不完全。


目標を追っている間はほかの目標のことは気
にしないから
ほかの目標のことも考えよう

2004/5/17
目標後退
26
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
27
目標後退をプランニングに組み
込む
初期状態StartStateから目標リストGoalsを達成す
るために
・もし、StartStateでGoalsが満たされていたら、空
のプランで十分である。
・さもなければ、Goalsの中から目標Gを、さらにGを
加えるような行為Aを選び、そして、Aを使って
Goalsを退行することによってNewGoalsを得る。
さらに、StartStateからNewGoalsを達成するよう
なプランを見つける。
2004/5/17
28
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
同じ場所に違うブロックは乗らない
29
目標後退の効果


プログラムを実行してみる
目標後退の結果4ステップかかっていたの
が3ステップになった。
2004/5/17
30
17.6 手段目標プランニングと最
良優先探索を組合せる


これまで探索には、深さ優先探索、幅優先
探索、反復深化法などを使ってきた。
せっかく問題に特有な知識があるのだから、
それを元に発見的な最良優先探索を使う
と、素早いプランニングをしやすくなる。
2004/5/17
31
最良優先探索


評価関数とコストという概念を導入して、そ
の時点でもっともコストが低くなりそうな方
向に枝を伸ばしていく探索法
“良さそうな”方向へ探索していける
2004/5/17
32
プランナーへ最良優先探索を導
入する
定義するもの
(1)状態空間の節点間の後継関係
s(Node1,Node2,Cost)
(2)関係による探索の目標節点
goal(Node)
(3)関係による発見的関数
h(Node,HeuristicEstimate)
(4)探索の開始節点
2004/5/17
33
状態空間とか
Action
Cost
Node1
Node2
状態がノードとしてあり、それに対して操作。
2004/5/17
34
プランナーへ最良優先探索を導
入する
状態空間の目標集合Goals1とGoals2および
行為Aの間に次の関係が成り立つ
 AはGoals1のいくつかの目標を加える


AはGoals1の目標を破壊することなく、し
かも
Goals2はAを通したGoals1の退行の結果
である。
2004/5/17
35
プランナーへ最良優先探索を導
入する
このままだと目標リストしか出てこないので
Goals -> Action
としてプランをだすようにする
2004/5/17
36
17.7 Uninstantiated actionsと
半順序プランニング

能率を良くするためほかのことも考えてみ
よう


2004/5/17
Uninstantiated actions and goals
半順序プランニング
37
Uninstantiated actions and
goals

変数を確定しないまま進めていく方法
2004/5/17
38
半順序プランニング


プランの中で順番を一概に決められないも
のがあるプランニング(cf 全順序プランニ
ング）
探索空間がプランをノードとするプラン探
索空間
2004/5/17
39
例
a
d
e
b
e
f
d
c
f
7
8
b
a
c
1
2
3
2004/5/17
4
5
6
1
2
3
4
5
6
7
8
40
半順序プランニング
上の例で以下の２つのプランは互いに独立である。
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
41
START
move(b,a,c
)
move(e,d,f
)
move(a,1,b
)
move(d,8,e
)
FINISH
2004/5/17
42
半順序プランニング

プランステップ


プラン中の個々の行為に付けられるインデックス集合。
行為の名前みたいなもの
因果リンク

プラン中で、プランステップSが、プランステップWの前
提条件のPを追加する時、
S
P
W
と記述する。これを因果リンクという。
2004/5/17
43
半順序プランニング

順序制約

プランステップSは、プランステップWよりも先に実行さ
れる必要があるという制約
S

脅威ステップ


2004/5/17
W
P
W に関して、ステップSとW以
因果リンク S
外で、Pを削除リストにもつステップV
あるプランにおいて，VがSとWの間にあるとWが適用
できない。それを避けるために、制約順序
V S
or
が必要
W
V
44
半順序プランニング

完全なプラン


プラン中のすべてのステップの条件リストが、
他のステップにより達成されるようなプラン
無矛盾なプラン

2004/5/17
制約順序に矛盾のないプラン
45
半順序プランニングのアルゴリズム

初期化

特別なステップSTARTとFINISHを作る



順序制約リストをORDERとする


2004/5/17
STARTは、追加リストに初期状態を持つ
FINISHは、条件リストにゴールを持つ
空集合で初期化する
Pをプランとし、 START 、FINISH 、および
ORDERで初期化する
46
半順序プランニングのアルゴリズム
Pが完全・無矛盾なら完了、or Backtrack
P中に、S p W なる因果リンクがあり、vがこの
因果リンクに対する脅威ステップの場合、V
S
か W V を付加し１へ
さもなければ、P中に条件pが満たされないよう
なwがあるなら
1.
2.
3.
1.
2.
2004/5/17
Pかオペレータ集合（前提条件、追加リスト、削除リ
ストをあわせたもの）から、pを追加リストに持つよう
なステップsを探しPにsと S p W と S
W
を追加する
sがオペレータ集合から得られたなら、Pに
S を追加し１へ
FINISH
START
S
と
47
半順序プランニング
半順序プランニングを使うと、fig17.2の例
も簡単に解ける
 Uninstantiated actions and goalsと組み
合わせる事によって複雑さの緩和ができる
（制約）

2004/5/17
48
まとめ


プランニングをPrologでとく場合、さまざま
なテクニックがある。それらをうまく使い、
良いプランナーをつくる事が大切である。
今日紹介したプランニングは古典的プラン
ニングである。近年では即応プランニング
(reactive planning)というものも出てきて
おり、プランニングは着実に進歩している。
2004/5/17
49
参考文献(書籍)
・Ivan Bratko: "PROLOG Programming for Artificial
Intelligence“
・Prologプログラミング入門安部憲広共立出版 1985
-上の訳本
・AIプログラミング安部憲広・田中和明近代科学社
1996
-訳本の続き
・人工知能の基礎馬場口登・山田誠二昭晃堂 1999
2004/5/17
50
参考文献(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/chap
3.ppt

プランニング技術
http://www.jaist.ac.jp/~itota/Lecture/K415-4.ppt
半順序プランニングを調べるのに参照。

2004/5/17
51
大切なこと




Prologに慣れておく
Prologの用語をきちんと理解しておく
時間をきちんと取る
理解できなかったらどんどん聞く
2004/5/17
52
END
2004/5/17
53
おまけ
2004/5/17
54
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(Blo
ck,From)]).
move(Something,a,Somewhere)
前提条件
[clear(Something),clear(Somewhere),on(Something,a)]
Something = c
Somewhere = 2
move(c,a,c) これは駄目
2004/5/17
55
Uninstantiated actions and
goals
Can(move(Block,From,To),[clear(Block),clear(To),on(Blo
ck,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
56
Uninstantiated actions and
goals
can(move(Block,From,To),[clear(Block),clear(To),on(Block,From),dif
ferent(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
57
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
58

Download Report