STRIPS（Stanford Research Institute Problem Solver）とは、1971年、Richard Fikes と Nils Nilsson が開発した自動計画に関する人工知能の一種。後にそのシステムの入力に使う形式言語も同じ名前で呼ばれるようになった。自動計画用の言語としては最も広く利用されている。本項目では、システムではなく言語に関して解説する。STRIPS のインスタンスは以下の部分から構成される:数学的には、STRIPS のインスタンスは formula_1 で表される。各要素の意味は次の通り:自動計画システムは、以上のような記述を入力として、初期状態から目標状態へと導く計画（すなわち一連の行動実行順序）を導出する。形式的には状態は条件の集合であり、ある時点の状態はそのときに真である条件の集合で表される。状態間の遷移は遷移関数にモデル化でき、行動の実行によって発生する、ある状態から別の状態への写像とみなせる。状態は行動に対応するため、STRIPS のインスタンス formula_1 に関する遷移関数は次のように表される:ここで、formula_9 は formula_2 の全部分集合の集合であり、システムがとりうる全状態の集合である。仮定を単純化して、行動はいつでも実行できるが、事前条件が適合していない場合にはその効果が発揮されない（状態が変化しない）と仮定すると、遷移関数は以下のように定義できる:関数 formula_11 は以下のように再帰的に行動の列に展開できる:STRIPS のインスタンスの計画は、初期状態から目標状態へと遷移させる一連の行動の並びである。形式的には、formula_12 が以下の2つの条件を満たす場合、formula_13 が計画となる。これまで説明した言語は、提案段階の STRIPS である。実際には、条件は物体（オブジェクト）に関するものであることが多い。例えば、ロボットの位置をモデル化する際に述語 formula_14 を使い、formula_15 なら、ロボットが Room1 にいるという意味を表す。この場合、行動には自由変項があり、それが暗黙のうちに存在量化される。すなわち、ある行動は各自由変項を特定の値と置換することによって得られる全ての可能な命題的行動を表している。これまでの説明では、初期状態は必ず全て判明しているとみなしていた。つまり、formula_5 に含まれない条件は全て偽であるとされた。この条件は限定的すぎることが多く、具体的に条件を設定しようとすると、初期状態が完全にはわからないことが多い。STRIPS を拡張して部分的な初期状態を扱えるようにする試みがなされてきた。他にも様々な拡張がなされている。研究室にサルがいるとする。このサルはバナナを食べたがっている。研究室には3つの場所 A、B、C がある。最初、サルは A にいる。C には箱が置いてある。B にはバナナが天井からつるしてある。つまり、サルは箱を使ってバナナを取らなければならない。STRIPS の問題に計画が存在するかどうかの決定問題はPSPACE完全である。様々な制限を加えることで、問題をNP完全にすることができる。

出典:wikipedia