人工知能5

人工知能
計画(3個の箱)
Lecture 12
3個の積み木
• ロボットアームが箱を積み替えるオペレータ
• 机αの上から箱を持ち上げる：PICKUP（x,α)
• 机αの上に箱を置く：上の逆＝PICKUP-1(x,α)
別に名前をつけても良い(例)PUTDOWN(x,α)
• 箱yの上に箱xを置く：PUTON(x,y)
箱のy上から箱xを持ち上げる： PUTON-1(x,y)
別に名前をつけても良い(例)TAKEOFF(x,y)
• 順序が大事：前提条件が満たされていなくて
は適用できないオペレータ
初期状態→（オペレータ）→目標状態
初期状態：
目標状態
ONTABLE(A),CLEAR(A)
ONTABLE(B),CLEAR(B)
ONTABLE(C),CLEAR(C)
EMPTY
ON(B,C), ON(A,B)
CLEAR(A), ONTABLE(C)
EMPTY
A
B
A
B
C
C
状態(state)の定義
•
•
•
•
•
箱xが机の上にある ONTABLE(x)
箱xが箱yの上にある ON(x,y)
箱ｘの上は何もない CLEAR (x)
ロボットアームは何も持っていないＥＭＰＴＹ
ロボットアームは箱xを持っている HOLD(x)
必要なoperatorsを定義する
•
•
•
•
PUTON(x,y)：xをyの上に置く
TAKEOFF（x,y)：yの上にあるxを掴む
PUTDOWN(x):xをテーブルの上に置く
PICKUP(x)：テーブルの上にあるxを掴む
各operatorに対するpc,D,Aで定義
• pc:Prerequisite condition前提条件
そのoperatorを適用できる条件
• D:削除delete状態リスト
そのoperatorを適用後に削除される状態
• A：追加add状態リスト
そのoperatorを適用後に追加される状態
各operatorの前提条件,削除/追加リスト
• PUTON(x,y)：xをyの上に載せる
前提条件：HOLD(x),CLEAR(y)：yの上が空きxを保持
削除リスト:HOLD(x),CLEAR(y)：ｙの上は詰まり,手は空
追加リスト：ON(x,y),CLEAR(x),EMPTY：yにｘが載り,上
は空、手は空
• TAKEOFF（x,y)：yの上からxを除去
前提条件： ON(x,y),CLEAR(x),EMPTY:ｘがｙに載り,そ
の上は空き,手は空
削除リスト: ON(x,y),CLEAR(x),EMPTY：
追加リスト：HOLD(x),CLEAR(y)：ｘを保持し、ｙの上は空
各operatorの前提条件,削除/追加リスト
• PUTDOWN(x):ｘをテーブルαに置く
P&D：HOLD(x)
A：ONTABLE(x),CLEAR(x),EMPTY
• PICKUP(x)：テーブルαにあるxを拾う
P&D： ONTABLE(x),CLEAR(x),EMPTY
A： HOLD(x)
オペレータ（operator)の定義
• PICKUP（x)：
<P&D>：ONTABLE(x),CLEAR(x),EMPTY
<A>： HOLD(x)
• PUTON(x):
<P&D>： HOLD(x)
<A>：ONTABLE(x),CLEAR(x),EMPTY
• PUTON(x,y)：
<P&D>： HOLD(x), CLEAR(y)
<A>：ON(x,y),CLEAR(x),EMPTY
• TAKEOFF(x,y)：
<P&D>： ON(x,y), CLEAR(x), EMPTY
<A>:
HOLD(x), CLEAR(y)
一般的な問題解決法
• 目標状態の状態記述のうちで、初期状態によって達
成されていない命題はどれかを探し
• それを一つ達成する
という操作を繰り返す。
命題Cを達成するには、 Cを追加リストとするオペ
レータOを求める。そのオペレータの前提条件が初
期条件によって満たされているかを調べ、満たされ
ていればOを適用。満たされていなければそれを満
たすのに必要な命題を達成することを目標にする
Local planning
function LocalPlanning(S,G)
1．LOOP1: if satisfy G exit (S);
2．Sによって満たされないGの命題をgoal-listに入
3．LOOP2: if empty(goal-list) return(fail);
4．C=first(goal-list); remove(C,goal-list);
Cを達成するオペレータを全て求めoplistに入
5．LOOP3：if empty (oplist) goto LOOP2
6．operator=first(oplist); remove(operator,oplist);
if not applicable(operator), goto LOOP3
7．Gからoperatorの追加リストを除き、前提条件を加えた状態をG1とする
8．G2= LocalPlanning(S,G1)
9．if G2=fail, goto LOOP3
10. S=operator(S)
11. Goto LOOP1
LOOP1の最初のタスク：
*
SG
1. SはGを満たさないので次へ行く
2. ON(B,C)とON(A,B)をgoal-listに入れる（LOOP2へ）
3. goal-listはEMPTYでない
4.T=ON(B,C) としてgoal-listから外す
Tを達成するオペレータを全て求め、oplistに入れる
>>PUTON(B,C)をoplistへ（LOOP3へ）
5. oplistはemptyではない
6. operator= PUTON(B,C),適用可能なら次へ→実は適用不可
理由はPUTON(B,C)を適用後CLEAR(B)が追加されるが
それはGにはないから. そこでgolalistの次の要素に行
く.ON(A,B)をgoal-listから外したうえでT=ON(A,B)を達成
するオペレータを全て求め、oplistに入れる
>>PUTON(A,B)をoplistへ（LOOP3へ）
5. oplistはemptyではない
6. operator= PUTON(A,B),今度は適用可能な
ので次へ
7. GからPUTON(A,B）の追加リストである
ON(A,B)とCLEAR(A)を除き、前提条件であ
るHOLD(A)とCLEAR(B)を加えた状態をG1
として LocalPlanning(S,G1）を解く
(LOOP1の次のタスク)
S→G1
G1= HOLD(A),CLEAR(B),ON(B,C),ONTABLE(C)
Loop１の次のタスク：
*
S G1
2． HOLD(A);ON(B,C)をgoal-listへ(Loop2へ）
3. goal-listは空ではないので次へ
4. HOLD(A)を達成するのに必要なオペレータを
oplistへ；これらはHOLD(A)を追加条件とする
TAKEOFF(A,x)またはPICKUP(A)である
6. operator= PICKUP(A);
remove(PICKUP(A),oplist);
7. HOLD(A) はG1から除かれ、代わりにG1に
PICKUP(A)の前提条件である
ONTABLE(A),CLEAR(A),EMPTYを入れてG2とし
LocalPlanning(S,G2)を解く G2= ON(B,C), CLEAR(B),
ONTABLE(C),ONTABLE(A),CLEAR(A),EMPTY
Loop１の次のタスク：
*
S → G2
G2= ON(B,C), CLEAR(B), ONTABLE(C),
ONTABLE(A), CLEAR(A), EMPTY
でSにないのは ON(B,C)なので
2． ON(B,C)をgoal-listへ(Loop2へ）
3. goal-listは空ではないので次へ
4. ON(B,C)を達成するのに必要なオペレータをoplistへ；
これらはON(B,C)を追加条件とするPUTON(B,C)
6. operator= PUTON(B,C);
remove(PUTON(B,C),oplist);
7. ON(B,C) をG1から外し代わりにPUTON(B,C)の前提
条件であるHOLD(B),CLEAR(C)を入れてG3とし
LocalPlanning(S,G3)を解く
Loop１の次のタスク：
*
S → G3
G3= HOLD(B),CLEAR(C), ONTABLE(C),ONTABLE(A),
CLEAR(A)
でSに無いのは HOLD(B)なので
2． HOLD(B)をgoal-listへ(Loop2へ）
3. goal-listは空ではないので次へ
4. HOLD(B)を達成するのに必要なオペレータをoplistへ；
これらはHOLD(B)を追加条件とするPICKUP(B)
6. operator= PICKUP(B); remove(PICKUP(B),oplist);
7. HOLD(B)をG3から外し代わりにPICKUP(B)の前提条
件であるONTABLE(B),CLEAR(B)を入れてG4とし
LocalPlanning(S,G4)を解くここでS=G4なので終了
副目標subgoalが複数命題となる場合
• 命題同士が独立とは
限らない
• もし干渉しあったらど
うするか？
１)並列にそれぞれの目
標を達成したあとで整
理
HOLD(A)
ON(A, B)
ON(B, C)
CLEAR(B) HOLD(B)
CLEAR(C)
A
例
A B
ON(A, B)  ON(B,C)
B
C
C
EMPTY
CLEAR(A)
ONTABLE (A)
EMPTY
CLEAR(B)
ONTABLE(B)
A
B
A
B
C
C
S
G
A
S
B
A
B
C
C
G
ON(A, B)
ON(B, C)
ONTABLE(C)
CLEAR(A)
ON(A, B)
を実現する
オペレータ
は適用可能.で
前提条件は
HOLD(A)
CLEAR(B)
ON(B, C)
を実現する
オペレータはG
にCLEAR(A)を
作るがこれはGに
含まれないので
適用不可
G1=HOLD(A),CLEAR(B),ON(B,C),ONTABLE(C)
S→G
A
B
A
B
C
S
C
G
A
B
A
B
S
C
C
G
ON(A, B)
ON(B, C)
ONTABLE(C)
CLEAR(A)
ON(A, B)
を実現する
オペレータ
は適用可能.で
前提条件は
HOLD(A)
CLEAR(B)
ON(B, C)
を実現する
オペレータはG
にCLEAR(A)を
作るがこれはGに
含まれないので
適用不可
G1=HOLD(A),CLEAR(B),ON(B,C),ONTABLE(C)
S → G1=HOLD(A),CLEAR(B),ON(B,C),ONTABLE(C)
A
B
A
B
C
C
S
G１
B
A
B
S
C
A
G2
C
HOLD(A)
G1 CLEAR(B)
ON(B,C)
ONTABLE(C)
HOLD(A)を実現する
オペレータは適用可能.
で,前提条件は
ONTABLE(A)
CLEAR(A), EMPTY
ON(B,C)
を実現する
オペレータはG
にEMPTYを
作るがこれはGに
含まれないので
適用不可
G2=ONTABLE(A),EMPTY,CLEAR(A), ON(B,C),CLEAR(B),
ONTABLE(C)
S→G2=ONTABLE(A),EMPTY,CLEAR(A), ON(B,C),CLEAR(B),
ONTABLE(C)
G3=HOLD(B),CLEAR(C),
CLEAR(A),CLEAR(B),
ONTABLE(C), ONTABLE(A)
B
A B
C
A
C
ON(B,C), EMPTY
CLEAR(A), CLEAR(B)
G2 ONTABLE(C)
ONTABLE(A)
ON(B,C)を実現するオペレータ
PUTON(B,C)は適用可能.で
前提条件はHOLD(B)とCLEAR(C)
追加条件はON(B,C)とEMPTY.
S→G3 =HOLD(B),CLEAR(C),CLEAR(A),CLEAR(B),
ONTABLE(C), ONTABLE(A)
• G3にあってSに無いのはHOLD(B)
• HOLD(B)を実現するオペレータはPICKUP(B)
またはTAKEOFF(B,x)
• PICKUP(B)は適用可能で前提条件は
ONTABLE(B),CLEAR(B),EMPTY
• 故に、G4= ONTABLE(B),CLEAR(B）,EMPTY,
CLEAR(C),CLEAR(A),CLEAR(B),ONTABLE(C),
ONTABLE(A)
となってS=G4で終了
A
B
C

Download Report