スタンフォード研究所問題解決者

スタンフォード研究所問題解決器（STRIPS）は、1971年にSRIインターナショナルでリチャード・フィークスとニルス・ニルソンによって開発された自動プランナーです。^{[ 1 ]}後に、このプランナーへの入力の形式言語を指すのに同じ名前が使われるようになりました。この言語は、今日使用されている自動プランニング問題インスタンスを表現するためのほとんどの言語の基盤となっています。このような言語は、一般的にアクション言語として知られています。この記事では、プランナーではなく、言語のみを説明します。

STRIPSインスタンスは以下で構成されます。

• 初期状態。
• 目標状態の仕様 ― プランナーが達成しようとしている状況。
• 一連のアクション。各アクションには、以下の内容が含まれます。
  • 前提条件（行動を実行する前に確立しておかなければならないこと）。
  • 事後条件（行動が実行された後に確立されるもの）。

数学的には、STRIPSインスタンスは4つ組である。${\displaystyle \langle P、O、I、G\rangle }$それぞれの構成要素は、以下の意味を持つ。

1. ${\displaystyle P}$は条件の集合（すなわち、命題変数）である。
2. ${\displaystyle O}$は演算子（つまり、アクション）の集合であり、各演算子はそれ自体が四つ組である。${\displaystyle \langle \alpha ,\beta ,\gamma ,\delta \rangle }$各要素は条件の集合である。これらの4つの集合は、順に、アクションが実行されるために必要な条件、偽でなければならない条件、アクションによって真になる条件、および偽になる条件を指定する。
3. ${\displaystyle I}$は初期状態であり、初期状態で真である条件の集合として与えられる（その他の条件はすべて偽であると仮定する）。
4. ${\displaystyle G}$これは目標状態の仕様であり、ペアとして与えられます。${\displaystyle \langle N,M\rangle }$これらは、ある状態が目標状態とみなされるために、それぞれどの条件が真でどの条件が偽であるかを規定するものです。

このような計画インスタンスにおける計画とは、初期状態から実行可能であり、目標状態に到達する一連の演算子のことである。

形式的には、状態は条件の集合です。状態は、その状態において真となる条件の集合によって表されます。状態間の遷移は遷移関数によってモデル化されます。遷移関数とは、アクションの実行によって生じる新しい状態に状態をマッピングする関数です。状態は条件の集合によって表されるため、STRIPSインスタンスに関連する遷移関数は${\displaystyle \langle P、O、I、G\rangle }$関数です

${\displaystyle \operatorname {succ} :2^{P}\times O\rightarrow 2^{P},}$

どこ$2P$は、すべての部分集合の集合です。${\displaystyle P}$したがって、はすべての可能な状態の集合である。

遷移関数${\displaystyle \operatorname {succ} }$州のために${\displaystyle C\subseteq P}$は、アクションは常に実行可能であるが、前提条件が満たされていない場合は効果がないという単純化された仮定を用いて、次のように定義できる。

機能${\displaystyle \operatorname {succ} }$以下の再帰方程式により、一連の動作にも拡張できます。

${\displaystyle \operatorname {succ} (C,[\ ])=C}$

${\displaystyle \operatorname {succ} (C,[a_{1},a_{2},\ldots ,a_{n}])=\operatorname {succ} (\operatorname {succ} (C,a_{1}),[a_{2},\ldots ,a_{n}])}$

STRIPSインスタンスのプランとは、初期状態から順番にアクションを実行した結果得られる状態が目標条件を満たすような一連のアクションのことです。正式には、${\displaystyle [a_{1},a_{2},\ldots ,a_{n}]}$計画は${\displaystyle G=\langle N,M\rangle }$もし${\displaystyle F=\operatorname {succ} (I,[a_{1},a_{2},\ldots ,a_{n}])}$以下の2つの条件を満たす。

${\displaystyle N\subseteq F}$

${\displaystyle M\cap F=\varnothing }$

上記の言語は実際にはSTRIPSの命題言語版です。実際には、条件は多くの場合、対象に関するものです。例えば、ロボットの位置は述語によってモデル化できる、といった具合です。${\displaystyle At}$、 そして${\displaystyle At(room1)}$これは、ロボットがRoom1にいることを意味します。この場合、アクションには自由変数を含めることができ、それらは暗黙的に存在量化されます。言い換えれば、アクションは、各自由変数を値に置き換えることによって得られるすべての可能な命題アクションを表します。

初期状態は、上記の言語では完全に既知であるとみなされます。${\displaystyle I}$これらはすべて偽であると仮定されています。しかし、初期状態が完全には分かっていない計画問題の自然な例が存在するため、これはしばしば制約的な仮定となります。部分的にしか分かっていない初期状態を扱うために、STRIPSの拡張版が開発されています。

サルは実験室のA地点にいます。C地点には箱があります。サルはB地点の天井からぶら下がっているバナナが欲しいのですが、バナナに届くには箱を動かしてその上に登る必要があります。

初期状態：A地点、レベル（低）、ボックスA地点（C地点）、バナナA地点（B地点） 目標状態：バナナを持っている

アクション: // XからYへ移動 _移動(X, Y)_ 前提条件：At(X)、Level(low) 事後条件: At(X) でもなく、At(Y) でもない // 箱の上に登る _登る(場所)_ 前提条件: At(Location)、BoxAt(Location)、Level(low) 事後条件：レベル(高)、レベル(低)ではない // 箱から降りる _降りる（場所）_ 前提条件: At(Location)、BoxAt(Location)、Level(high) 事後条件：レベル(低)、レベル(高)ではない // 猿と箱をXからYに移動させる _MoveBox(X, Y)_ 前提条件: At(X)、BoxAt(X)、Level(low) 事後条件: BoxAt(Y)、BoxAt(X)ではない、At(Y)、At(X)ではない バナナを取って _TakeBananas(場所)_ 前提条件: At(Location)、BananasAt(Location)、Level(high) 事後条件: バナナを持っている

命題STRIPSインスタンスに対してプランが存在するかどうかを判定することはPSPACE完全問題である。多項式時間でプランが存在するかどうかを判定したり、少なくともNP完全問題にするために、さまざまな制約を適用することができる。^{[ 2 ]}

サルとバナナの問題では、ロボットのサルは天井にあるバナナに到達するために一連の動作を実行する必要があります。単一の動作はゲームに小さな変化をもたらします。計画プロセスを簡素化するために、通常のルール記述では使用できない抽象的な動作を考案するのが理にかなっています。^{[ 3 ]}スーパーアクションは低レベルの動作で構成され、高レベルの目標に到達できます。利点は、計算複雑度が低く、ソルバーによってより長いタスクを計画できることです。

ドメインの新しいマクロ演算子を特定することは、遺伝的プログラミングで実現できます。^{[ 4 ]}アイデアは、ドメイン自体を計画するのではなく、前段階で、ドメインをはるかに速く解決できるヒューリスティックを作成することです。強化学習のコンテキストでは、マクロ演算子はオプションと呼ばれます。AI プランニング内の定義と同様に、アイデアは、時間的抽象化 (より長い期間にわたる) を提供し、より上位のレイヤーでゲームの状態を直接変更することです。^{[ 5 ]}

• 行動記述言語（ADL）
• 自動計画
• 階層型タスクネットワーク
• プランニングドメイン定義言語（PDDL）
• サスマン異常

• C. Bäckström および B. Nebel (1995). SAS+ プランニングの複雑性に関する結果. Computational Intelligence , 11:625-656.
• T. Bylander (1991). プランニングにおける複雑性の結果。第12回国際人工知能合同会議（IJCAI'91）議事録、274-279ページ。
• ラッセル、スチュアート・J.、ノーヴィグ、ピーター（2003）、『人工知能：現代的アプローチ』（第2 版）、アッパー・サドル・リバー、ニュージャージー州：プレンティス・ホール、ISBN 0-13-790395-2