STRIPS
出典: フリー百科事典『ウィキペディア（Wikipedia）』
STRIPS（Stanford Research Institute Problem Solver）とは、1971年、Richard Fikes と Nils Nilsson が開発した自動計画に関する人工知能の一種。後にそのシステムの入力に使う形式言語も同じ名前で呼ばれるようになった。自動計画用の言語としては最も広く利用されている。本項目では、システムではなく言語に関して解説する。
目次 |
[編集] 定義
STRIPS のインスタンスは以下の部分から構成される:
- 初期状態
- 目標状態の記述 - システムが到達しようとする状況
- 行動群。各行動には以下の記述が含まれる:
- 事前条件（その行動を行う前に満足されていなければならない条件）
- 事後条件（その行動を行うことで満足される条件）
数学的には、STRIPS のインスタンスは <math>\langle P,O,I,G \rangle</math> で表される。各要素の意味は次の通り:
- <math>P</math> は「条件」群（つまり、命題的変数群）
- <math>O</math> は「演算子」群（つまり、行動群）。各演算子は <math>\langle \alpha, \beta, \gamma, \delta \rangle</math> で表され、それぞれが条件群となっている（左から、行動選択前に真でなければならない条件群、同じく偽でなければならない条件群、行動実行後に真となる条件群、同じく偽となる条件群）。
- <math>I</math> は初期状態であり、最初に真となっている条件群である（他の条件は全て偽）。
- <math>G</math> は目標状態の記述であり、<math>\langle N,M \rangle</math> で表される（最終的に真となるべき条件と偽となるべき条件）。
自動計画システムは、以上のような記述を入力として、初期状態から目標状態へと導く計画（すなわち一連の行動実行順序）を導出する。
形式的には状態は条件の集合であり、ある時点の状態はそのときに真である条件の集合で表される。状態間の遷移は遷移関数にモデル化でき、行動の実行によって発生する、ある状態から別の状態への写像とみなせる。状態は行動に対応するため、STRIPS のインスタンス <math>\langle P,O,I,G \rangle</math> に関する遷移関数は次のように表される:
- <math>\operatorname{succ}: 2^P \times A \rightarrow 2^P,</math>
ここで、<math>2^P</math> は <math>P</math> の全部分集合の集合であり、システムがとりうる全状態の集合である。
仮定を単純化して、行動はいつでも実行できるが、事前条件が適合していない場合にはその効果が発揮されない（状態が変化しない）と仮定すると、遷移関数は以下のように定義できる:
| <math>\operatorname{succ}(C,\langle \alpha,\beta,\gamma,\delta \rangle)</math> | = <math>P \backslash \delta \cup \gamma</math> | if <math>\alpha \subseteq C</math> and <math>\beta \cap C = \varnothing</math> |
| = <math>P</math> | otherwise |
関数 <math>\operatorname{succ}</math> は以下のように再帰的に行動の列に展開できる:
- <math>\operatorname{succ}(C,[]) = C</math>
- <math>\operatorname{succ}(C,[a_1,a_2,\ldots,a_n])=\operatorname{succ}(\operatorname{succ}(C,a_1),[a_2,\ldots,a_n])</math>
STRIPS のインスタンスの計画は、初期状態から目標状態へと遷移させる一連の行動の並びである。形式的には、<math>F=\operatorname{succ}(I,[a_1,a_2,\ldots,a_n])</math> が以下の2つの条件を満たす場合、<math>[a_1,a_2,\ldots,a_n]</math> が計画となる。
- <math>N \subseteq F</math>
- <math>M \cap F = \varnothing</math>
[編集] 拡張
これまで説明した言語は、提案段階の STRIPS である。実際には、条件は物体（オブジェクト）に関するものであることが多い。例えば、ロボットの位置をモデル化する際に述語 <math>At</math> を使い、<math>At(room1)</math> なら、ロボットが Room1 にいるという意味を表す。この場合、行動には自由変項があり、それが暗黙のうちに存在量化される。すなわち、ある行動は各自由変項を特定の値と置換することによって得られる全ての可能な命題的行動を表している。
これまでの説明では、初期状態は必ず全て判明しているとみなしていた。つまり、<math>I</math> に含まれない条件は全て偽であるとされた。この条件は限定的すぎることが多く、具体的に条件を設定しようとすると、初期状態が完全にはわからないことが多い。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(X, Y)_
//move from X to Y
Preconditions: At(X), Level(low)
Postconditions: not At(X), At(Y)
_ClimbUp(Location)_
//climb up on the box
Preconditions: At(Location), BoxAt(Location), Level(low)
Postconditions: Level(high), not Level(low)
_ClimbDown(Location)_
//climb down from the box
Preconditions: At(Location), BoxAt(Location), Level(high)
Postconditions: Level(low), not Level(high)
_MoveBox(X, Y)_
//move the box from X to Y
Preconditions: At(X), BoxAt(X), Level(low)
Postconditions: BoxAt(Y), not BoxAt(X)
_TakeBananas(Location)_
//take the bananas
Preconditions: At(Location), BananasAt(Location), Level(high)
Postcondition: Have(bananas)
[編集] 計算複雑性
STRIPS の問題に計画が存在するかどうかの決定問題はPSPACE完全である。様々な制限を加えることで、問題をNP完全にすることができる。
[編集] 参考文献
- C. Bäckström and B. Nebel (1995). Complexity results for SAS+ planning. Computational Intelligence, 11:625-656.
- T. Bylander (1991). Complexity results for planning. In Proceedings of the Twelfth International Joint Conference on Artificial Intelligence (IJCAI'91), pages 274-279.
- R. Fikes and N. Nilsson (1971). STRIPS: a new approach to the application of theorem proving to problem solving. Artificial Intelligence, 2:189-208.
- S. Russell and P. Norvig (1999). Artificial Intelligence - a modern approach. Prentice Hall.
