人工知能5

人工知能
計画
Lecture 9
GPS
(general problem solver)
および
計画
最も簡単な問題:積み木
• ロボットアームが箱を積み替えるオペレータ
• 机の上から箱を持ち上げる：PICKUP（x)
• 机の上に箱を置く：上の逆＝PICKUP-1(x)
別に名前をつけても良い(例)PUTDOWN(x)
• 箱yの上に箱xを置く：PUTON(x,y)
箱のy上から箱xを持ち上げる： PUTON-1(x,y)
別に名前をつけても良い(例)TAKEOFF(x,y)
• 順序が大事：前提条件が満たされていなくて
は適用できないオペレータ
初期状態→（オペレータ）→目標状態
• 初期状態：
ONTABLE(A)
ONTABLE(C)
ON(B,C)
B
A
C
目標状態
ON(A,C)
A
C
B
一般的な問題解決法
• 目標状態の状態記述のうちで、初期状態によって達
成されていない命題はどれかを探し
• それを一つ達成する
という操作を繰り返す。
命題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
必要な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):ｘを下に置く
前提条件：HOLD(x)
削除リスト:HOLD(x)
追加リスト：ONTABLE(x),CLEAR(x),EMPTY
• PICKUP(x)：xを拾う
前提条件： ONTABLE(x),CLEAR(x),EMPTY
削除リスト: ONTABLE(x),CLEAR(x),EMPTY
追加リスト： HOLD(x)
最初のタスク：
*
SG
1. SはGを満たさない
2. ON(A,C)をgoal-listに入れる
3. goal-listはemptyでない
4.T=ON(A,C) としてgoal-listから外す
Tを達成するオペレータを全て求め、oplistに入れる
>>PUTON(A,C)をoplistへ
5. oplistはemptyではない
6. operator= PUTON(A,C)、適用可能でないLOOP3へ、oplist
が空ならLOOP2へ>>fail(????)
7. GからPUTON(A,C）の追加リストを除き、前提条件
HOLD(A);CLEAR(C)を加えた状態をG1として、
LocalPlanning(S,G1）を解く
次のタスク：
*
S G1
2． HOLD(A);CLEAR(C)をgoal-listへ
4. goal-listを達成するのに必要なオペレータをoplist
へ；これらはHOLD(A);CLEAR(C)を追加条件とす
るTAKEOFF(A,C)またはPICKUP(A)である
6. operator= PICKUP(A);
remove(PICKUP(A),oplist);
7. HOLD(A) はG1から除かれ、代わりにG1に
ONTABLE(A),CLEAR(A),EMPTYを入れて
LocalPlanning(S,G1)を解く
これを繰り返す
初期状態→（オペレータ）→目標状態
初期状態 S
ONTABLE(A)&&ON(B,C)
A
目標状態 G
ON(A,C)&&ONTABLE(C)
B
A
C
C
B
SからGへは直接行けない
ON(A,C)を実行するにはoperator PUTON(A,C)が必要
PUTON(A,C)の前提条件としてHOLD(A)&&CLEAR（C)が必要。
これらをsubgoal=G1とする。SからG1へは直接行けない。
HOLD(A)の実行にはoperator PICKUP(A)またはTAKEOFF(A,x)が必要。
CLEAR(C)の実行にはOPERATOR TAKEOFF(B,C)が必要。
PICKUP(A)の前提条件としてONTABLE(A)&&CLEAR(A)&&EMPTYが必要。
TAKEOFF(B,C)の前提条件としてON(B,C)&&EMPTY&&CLEAR(B)が必要。
これらは初期条件Sにより満たされているので実行可能。
ONTABLE（C）は最初からあるので、そのままいじらない
ON(A,C)
S → ON(A,C) goallistに
PUTON(A,C)
HOLD(A)＆CLEAR（C）
PICKUP(A)
TAKEOFF(A,x)
S → HOLD(A)＆CLEAR（C）
CLEAR(A)
ONTABLE(A)
EMPTY
CLEAR（C)
PUTDOWN(y)：y=B
CLEAR(A)
ON (A,x)
EMPTY
CLEAR（C)
S → CLEAR(A)＆
ONTABLE(A)＆
EMPTY&CLEAR(C）
PUTON(y,z)
HOLD(B)
CLEAR(A)
ONTABLE(A)
CLEAR(C）
CLEAR(C）が実現されないので
HOLD(y)
CLEAR(A)
ONTABLE(A)
CLEAR（C)
CLEAR(A)
Cの上に載っている物を下ろす
TAKEOFF(B,C)
S → HOLD(B)＆CLEAR（A)
＆ONTABLE(A)＆CLEAR(C）
EMPTY, CLEAR(A), ONTABLE(A), ON(B,C)
S → EMPTY & CLEAR(A)
&ONTABLE(A)&ON(B,C)

Download Report