STRIPS 拡張

ウィキペディア

STRIPS

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/10/29 06:26 UTC 版)

拡張

これまで説明した言語は、提案段階の STRIPS である。実際には、条件は物体（オブジェクト）に関するものであることが多い。例えば、ロボットの位置をモデル化する際に述語 $At$ を使い、$At(room1)$ なら、ロボットが Room1 にいるという意味を表す。この場合、行動には自由変項があり、それが暗黙のうちに存在量化される。すなわち、ある行動は各自由変項を特定の値と置換することによって得られる全ての可能な命題的行動を表している。

これまでの説明では、初期状態は必ず全て判明しているとみなしていた。つまり、$I$ に含まれない条件は全て偽であるとされた。この条件は限定的すぎることが多く、具体的に条件を設定しようとすると、初期状態が完全にはわからないことが多い。STRIPS を拡張して部分的な初期状態を扱えるようにする試みがなされてきた。他にも様々な拡張がなされている。

STRIPSの問題例

研究室にサルがいるとする。このサルはバナナを食べたがっている。研究室には3つの場所 A、B、C がある。最初、サルは A にいる。C には箱が置いてある。B にはバナナが天井からつるしてある。つまり、サルは箱を使ってバナナを取らなければならない。

Initial state: At(A), Level(low), BoxAt(C), BananasAt(B)
Goal state:    Have(Bananas)

Actions:
               // move from X to Y
               _Move(X, Y)_
               Preconditions:  At(X), Level(low)
               Postconditions: not At(X), At(Y)
               
               // climb up on the box
               _ClimbUp(Location)_
               Preconditions:  At(Location), BoxAt(Location), Level(low)
               Postconditions: Level(high), not Level(low)
               
               // climb down from the box
               _ClimbDown(Location)_
               Preconditions:  At(Location), BoxAt(Location), Level(high)
               Postconditions: Level(low), not Level(high)
               
               // move monkey and box from X to Y
               _MoveBox(X, Y)_
               Preconditions:  At(X), BoxAt(X), Level(low)
               Postconditions: BoxAt(Y), not BoxAt(X), At(Y), not At(X)
               
               // take the bananas
               _TakeBananas(Location)_
               Preconditions:  At(Location), BananasAt(Location), Level(high)
               Postconditions: Have(bananas)

計算複雑性

STRIPS の問題に計画が存在するかどうかの決定問題はPSPACE完全である。様々な制限を加えることで、問題をNP完全にすることができる。