STRIPS

STRIPS（Stanford Research Institute Problem Solver）とは、1971年、とが開発した自動計画に関する人工知能の一種。後にそのシステムの入力に使う形式言語も同じ名前で呼ばれるようになった。自動計画用の言語としては最も広く利用されている。本項目では、システムではなく言語に関して解説する。
定義.
STRIPS のインスタンスは以下の部分から構成される:
STRIPS インスタンスを形式的に記述する方法は複数あり、命題論理に立脚したもの、一階述語論理に基づいたもの、グラフ上の遷移に基づいたものなどがある。
命題論理形式の定義.
STRIPS のインスタンスは formula_1 で表され、それぞれの意味は以下である:
表記は論文によって様々で、これにformula_9(Propositions - 命題論理変数) またはformula_10 (Variables - 命題変数から)を追加するもの、
formula_2の代わりにformula_12(Actions)、
formula_7のかわりにformula_14(0番目の状態(state))、formula_8の代わりにformula_16(終わりとなる状態の集合), formula_17のかわりにformula_18が使われる場合もある。
オペレータはコストformula_19を含んで定義される場合もあり、コストのないものは通常すべてのアクションに対してコスト1が仮定される。
一階述語論理形式の定義.
一階述語論理形式の定義では、命題論理形式のアクション集合にパラメータの概念を導入する。
ここでアクションは formula_20 で表され、
formula_21はformula_22で修飾される。
グラフ理論形式の定義.
グラフ理論形式の定義では、 STRIPS インスタンスをグラフ探索アルゴリズムで解かれるグラフ探索問題と同一視する。
ここでインスタンスは formula_23 で表される。ここで、
formula_24は状態集合でありグラフのノード集合と同一視され、formula_25はアクションを指すラベル、formula_26は状態遷移（Transition)でありグラフのエッジに相当する。
自動計画.
自動計画システムは、以上のような記述を入力として、初期状態から目標状態へと導く計画（すなわち一連の行動実行順序）を導出する。
形式的には状態は命題の集合であり、ある時点の状態はそのときに真である命題の集合で表される。状態間の遷移は遷移関数にモデル化でき、行動の実行によって発生する、ある状態から別の状態への写像とみなせる。状態は行動に対応するため、STRIPS のインスタンス formula_27 に関する遷移関数は次のように表される:
ここで、formula_28 は formula_9 の全部分集合の集合であり、システムがとりうる全状態の集合である。
あるアクション formula_30 が状態formula_31に適用できる条件は、 formula_32である。これが満たされている場合、アクションを適用できて、
その結果状態formula_31は以下のような状態formula_34に遷移する:
ここで、formula_35の適用の順番は重要であり、これは同じ命題がformula_36、formula_37の両方に含まれた場合には追加効果が優先するという動作を決定する。
関数 formula_38 は以下のように再帰的に行動の列に展開できる:
STRIPS のインスタンスの計画は、初期状態から目標状態へと遷移させる一連の行動の並びである。形式的には、formula_39 がformula_40を満たす場合、プランformula_41 がこのインスタンスの解となる。
拡張.
これまで説明した言語は、提案段階の STRIPS である。実際には、条件は物体（オブジェクト）に関するものであることが多い。例えば、ロボットの位置をモデル化する際に述語 formula_42 を使い、formula_43 なら、ロボットが Room1 にいるという意味を表す。この場合、行動には自由変項があり、それが暗黙のうちに存在量化される。すなわち、ある行動は各自由変項を特定の値と置換することによって得られる全ての可能な命題的行動を表している。
これまでの説明では、初期状態は必ず全て判明しているとみなしていた。つまり、formula_7 に含まれない条件は全て偽であるとされた。この条件は限定的すぎることが多く、具体的に条件を設定しようとすると、初期状態が完全にはわからないことが多い。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完全にすることができる。