STRIPS

ＳＴＲＩＰＳ
STRIPSのアルゴリズムをブロック
ワールドに適用してみる。
ブロックワールド
A
C
A
B
B
C
I: {Clear(B), Clear(C), On(C, A),
HandEmpty,
OnTable(A), OnTable(B)}
G: {On(B, C), On(A, B)}
資料(３)
分散人工知能
2
動作規則
1. pickup(x): テーブル上のブロックxを手に持つ。
前提条件：OnTable(x)∧Clear(x)∧HandEmpty
削除リスト： OnTable(x), Clear(x), HandEmpty
追加リスト：Holding(x)
2. putdown(x): 手に持ったブロック x をテーブル上に置く。
前提条件： Holding(x)
削除リスト： Holding(x)
追加リスト：OnTable(x), Clear(x), HandEmpty
3. stack(x, y): 手に持ったブロック x を y の上に積む。
前提条件：Holding(x) ∧Clear(y)
削除リスト： Holding(x), Clear(y)
追加リスト： HandEmpty, On(x,y), Clear(x)
4. unstack(x, y): y の上に積まれたブロック x を手に持つ。
前提条件： HandEmpty ∧ On(x,y)∧Clear(x)
削除リスト： HandEmpty, On(x,y), Clear(x)
追加リスト： Holding(x), Clear(y)
資料(３)
分散人工知能
3
STRIPS(I, G)
1. 状態I と状態G の差D を計算する。ここで、D は
状態G を表すリテラルの中で、状態I で真でな
いリテラルの集合である。
2. 差Ｄが空ならば、空の計画を返却し終了する。
3. 差Ｄの中から副目標を一つ選択し、それを達成
する動作規則Ｏを選択する。
4. 再帰的に STRIPS(I, P) を呼ぶ。ただし、P は動
作規則O の前提条件式である。
5. Step 4 で得た計画（P を充足する状態に到達す
るための計画）の最後にO を追加する。
資料(３)
分散人工知能
4
STRIPS(I, G)
6. 状態I に、Step５で得られた計画を適用し、
その結果得られた状態をQ とする。
７．再帰的にSTRIPS(Q, G) を呼ぶ。
８．Step５で得られた計画の末尾にStep7で
得られた計画を付加する。
９．Step8で得られた計画を返却して終了す
る。
資料(３)
分散人工知能
5
Step-1
1. 状態I と状態G の差D を計算する。ここで、D は状態G
を表すリテラルの中で、状態I で真でないリテラルの
集合である。
I: {Clear(B), Clear(C), On(C, A), HandEmpty,
OnTable(A), OnTable(B)}
G: {On(A, B ), On(B, C)}
D: {On(A, B), On(B, C)}
資料(３)
分散人工知能
6
Step-2
2. 差Ｄが空ならば、空の計画を返却し終了する。
D ￢= Φ
資料(３)
分散人工知能
7
Step-3
副目標 On(A, B) が達成できなけ
れば、次に選択される副目標
（後戻り点）
3. 差Ｄの中から副目標を一つ選択し、それを達成する動作
規則Ｏを選択する。
I: {Clear(B), Clear(C), On(C, A), HandEmpty, OnTable(A), OnTable(B)}
D: {On(A, B), On(B, C)}
手段・目標解析:目標状態と現在の状態の差を小さくするため
１．目標に含まれるリテラルの中で、動作の実行により、真となるリテラルの数が最大の動
作規則（差D を最も減少させる動作規則）
stack(A, B), stack(B, C)
２．目標に含まれるリテラルの中で、動作の実行により、偽となるリテラルの数が最小の動
作規則（差D を最も増大させない動作規則）
unstack(A, B), unstack(B, C)
３．動作の前提状態に含まれるリテラルの中で、現状態で偽であるリテラルの数が最小の
動作規則（実行できる可能性が最も高い動作規則）
pickup(B), unstack(C, A)
資料(３)
分散人工知能
8
Step-4(Step-1,2)
4. 再帰的に STRIPS(I, P) を呼ぶ。ただし、P は動作規則O
の前提条件式である。
I: {Clear(B), Clear(C), On(C, A), HandEmpty,
OnTable(A), OnTable(B)}
O: stack(A, B)
P: {Holding(A), Clear(B)}
Step-4(Step-1)
D: {Holding(A)}
Step-4(Step-2)
D ￢= Φ
資料(３)
分散人工知能
9
Step-4(Step-3)
I: {Clear(B), Clear(C), On(C, A), HandEmpty, OnTable(A), OnTable(B)}
D: {Holding(A)}
手段・目標解析:目標状態と現在の状態の差を小さくするため
１．目標に含まれるリテラルの中で、動作の実行により、真となるリテラルの数が最大の動
作規則（差D を最も減少させる動作規則）
pickup(A), unstack(A, B), unstack(A, C)
２．目標に含まれるリテラルの中で、動作の実行により、偽となるリテラルの数が最小の動
作規則（差D を最も増大させない動作規則）
putdown(A), stack(A, B), stack(A, C)
３．動作の前提状態に含まれるリテラルの中で、現状態で偽であるリテラルの数が最小の
動作規則（実行できる可能性が最も高い動作規則）
pickup(B), unstack(C, A)
資料(３)
分散人工知能
10
Step-4(Step-4)
I: {Clear(B), Clear(C), On(C, A), HandEmpty,
OnTable(A), OnTable(B)}
O: pickup(A)
P: {OnTable(A), Clear(A), HandEmpty}
Step-4(Step-4(Step-1))
D: {Clear(A)}
Step-4(Step-4(Step-2))
D ￢= Φ
資料(３)
分散人工知能
11
Step-4(Step-4(Step-3))
I: {Clear(B), Clear(C), On(C, A), HandEmpty, OnTable(A), OnTable(B)}
D: {Clear(A)}
手段・目標解析:目標状態と現在の状態の差を小さくするため
１．目標に含まれるリテラルの中で、動作の実行により、真となるリテラルの数が最大の動
作規則（差D を最も減少させる動作規則）
unstack(C, A), unstack(B, A), stack(A, B), stack(A, C), putdown(A)
２．目標に含まれるリテラルの中で、動作の実行により、偽となるリテラルの数が最小の動
作規則（差D を最も増大させない動作規則）
pickup(A), stack(B, A), stack(C, A)
３．動作の前提状態に含まれるリテラルの中で、現状態で偽であるリテラルの数が最小の
動作規則（実行できる可能性が最も高い動作規則）
pickup(B), unstack(C, A)
資料(３)
分散人工知能
12
Step-4(Step-4(Step-4))
I: {Clear(B), Clear(C), On(C, A), HandEmpty,
OnTable(A), OnTable(B)}
O: unstack(C, A)
P: {HandEmpty, On(C, A), Clear(C),}
Step-4(Step-4(Step-4(step-1)))
D: {}
Step-4(Step-4(Step-4(step-2)))
D=Φ
資料(３)
Step-4(Step-4(Step-5))
分散人工知能
13
Step-4(Step-4(Step-5,6))
5. Step 4 で得た計画（P を充足する状態に到達するための計画）
の最後にO を追加する。
Plan ={} + unstack(C, A)
6. 状態I に、Step５で得られた計画を適用し、その結果得られた状態
をQ とする。
I: {Clear(B), Clear(C), On(C, A), HandEmpty,
OnTable(A), OnTable(B)}
O: unstack(C, A)
Q: {Clear(B), OnTable(A), OnTable(B), Holdind(C), Clear(A)}
資料(３)
分散人工知能
14
Step-4(Step-4(Step-7))
７．再帰的にSTRIPS(Q, G) を呼ぶ。
Q: {Clear(B), OnTable(A), OnTable(B), Holdind(C), Clear(A)}
G: {OnTable(A), Clear(A), HandEmpty}
資料(３)
分散人工知能
15
Step-4(Step-4(Step-8,9))
８．Step５で得られた計画の末尾にStep7で得られた計画を付加する。
９．Step8で得られた計画を返却して終了する。
資料(３)
分散人工知能
16

Download Report