STRIPS
自動計画システムは、以上のような記述を入力として、初期状態から目標状態へと導く計画(すなわち一連の行動実行順序)を導出する。
形式的には状態は命題の集合であり、ある時点の状態はそのときに真である命題の集合で表される。状態間の遷移は遷移関数にモデル化でき、行動の実行によって発生する、ある状態から別の状態への写像とみなせる。状態は行動に対応するため、STRIPS のインスタンス ⟨ P , O , I , G ⟩ {\displaystyle \langle P,O,I,G\rangle } に関する遷移関数は次のように表される:
succ : 2 P × O → 2 P , {\displaystyle \operatorname {succ} :2^{P}\times O\rightarrow 2^{P},}
ここで、 2 P {\displaystyle 2^{P}} は P {\displaystyle P} の全部分集合の集合であり、システムがとりうる全状態の集合である。
STRIPS のインスタンスは以下の部分から構成される:
初期状態 (Init)
目標状態の記述 (Goal) - システムが到達しようとする状況
行動 (Actions) - 行動は状態に変化をもたらす操作なので、オペレータ(Operator)とも呼ばれる。各行動には以下の記述が含まれる: 事前条件 (Preconditions) - その行動を行うために満たされていなければならない条件 効果/事後条件 (Effects / Postconditions) - その行動を行うことで満足される条件
STRIPS インスタンスを形式的に記述する方法は複数あり、命題論理に立脚したもの、一階述語論理に基づいたもの、グラフ上の遷移に基づいたものなどがある。
研究室にサルがいるとする。このサルはバナナを食べたがっている。研究室には3つの場所 A、B、C がある。最初、サルは A にいる。C には箱が置いてある。B にはバナナが天井からつるしてある。つまり、サルは箱を使ってバナナを取らなければならない。