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

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

意味

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

初期状態。
目標状態の指定 - 計画者が達成しようとしている状況。
一連のアクション。各アクションには、以下の内容が含まれます。
- 前提条件（アクションを実行する前に確立する必要があるもの）
- 事後条件（アクションの実行後に確立されるもの）。

数学的には、STRIPS インスタンスは 4 つの要素から成り、各要素は次の意味を持ちます。 $\langle P、O、I、G\rangle$

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

このような計画インスタンスの計画は、初期状態から実行でき、目標状態に至る一連の演算子です。

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

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

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

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

$\operatorname {succ} (C,\langle \alpha ,\beta ,\gamma ,\delta \rangle )$	＝ $(C\backslash \delta )\cup \gamma$	もしそして $\alpha \subseteq C$ $\beta \cap C=\varnothing$
	＝ $C$	さもないと

この関数は、次の再帰方程式によってアクションのシーケンスに拡張できます。 $\operatorname {succ}$

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

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

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

N\subseteq F

M\cap F=\varnothing

拡張機能

上記の言語は、実際にはSTRIPSの命題版です。実際には、条件は多くの場合オブジェクトに関するものです。例えば、ロボットの位置は述語によってモデル化でき、はロボットがRoom1にいることを意味します。この場合、アクションは自由変数を持つことができ、これらは暗黙的に存在量化されます。言い換えれば、アクションは、各自由変数を値に置き換えることで得られるすべての可能な命題アクションを表します。 $で$ $部屋1で$

上述の言語では、初期状態は完全に既知であるとみなされます。つまり、条件に該当しない条件はすべて偽とみなされます。これはしばしば限定的な仮定であり、初期状態が完全には既知でないプランニング問題の例が自然に存在するためです。部分的に既知な初期状態を扱うために、STRIPSの拡張が開発されています。 $I$

STRIPS問題の例

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

初期状態: At(A)、Level(low)、BoxAt(C)、BananasAt(B)目標状態: バナナを持っている

アクション: // XからYへ移動 _移動(X, Y)_ 前提条件: At(X)、レベル(低) 事後条件: At(X)、At(Y) ではない  // 箱の上に登る _ClimbUp(場所)_ 前提条件: At(場所)、BoxAt(場所)、Level(低) 事後条件: Level(high)、Not Level(low)  // 箱から降りる _ClimbDown(場所)_ 前提条件: At(場所)、BoxAt(場所)、Level(高) 事後条件: Level(low)、Not Level(high)  // サルとボックスをXからYに移動する _MoveBox(X, Y)_ 前提条件: At(X)、BoxAt(X)、Level(low) 事後条件: BoxAt(Y)、BoxAt(X) ではない、At(Y)、At(X) ではない  // バナナを取る _TakeBananas(場所)_ 前提条件: At(場所)、バナナAt(場所)、レベル(高) 事後条件: バナナを持っている

複雑

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

マクロ演算子

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

ドメインに対する新しいマクロ演算子の特定は、遺伝的プログラミングによって実現できます。^[4]その考え方は、ドメイン自体を計画するのではなく、その前段階で、ドメインをより速く解決するためのヒューリスティックを作成するというものです。強化学習の文脈では、マクロ演算子はオプションと呼ばれます。AI計画における定義と同様に、その考え方は、時間的抽象化（より長い期間にわたる）を提供し、ゲームの状態を上位層で直接変更することです。^[5]

参照

参考文献

^ Richard E. Fikes, Nils J. Nilsson (1971年冬). 「STRIPS：定理証明を問題解決に応用する新しいアプローチ」(PDF) .人工知能. 2 ( 3–4 ): 189– 208. CiteSeerX 10.1.1.78.8292 . doi :10.1016/0004-3702(71)90010-5. S2CID 8623866.
^ Tom Bylander (1994年9月). 「命題STRIPSプランニングの計算複雑性」.人工知能. 69 ( 1–2 ): 165–204 . CiteSeerX 10.1.1.23.199 . doi :10.1016/0004-3702(94)90081-7.
^ Haslum, Patrik (2007). 「計画問題における偶発的な複雑性の低減」 . 第20回国際人工知能合同会議議事録. pp. 1898– 1903.
^ Schmid, Ute (1999).反復マクロ演算子の再考：プログラム合成をプランニング学習に適用する（技術レポート）. カーネギーメロン大学コンピュータサイエンス学部. doi : 10.21236/ada363524 .
^ Sutton, Richard S.、Precup, Doina、Singh, Satinder (1999). 「MDPとセミMDPの間：強化学習における時間的抽象化の枠組み」人工知能誌、112 ( 1–2 ). エルゼビア: 181–211 . doi : 10.1016/s0004-3702(99)00052-1 .{{cite journal}}: CS1 maint: 複数の名前: 著者リスト (リンク)

さらに読む

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

[1] Richard E. Fikes, Nils J. Nilsson (1971年冬). 「STRIPS：定理証明を問題解決に応用する新しいアプローチ」(PDF) .人工知能. 2 ( 3–4 ): 189– 208. CiteSeerX 10.1.1.78.8292 . doi :10.1016/0004-3702(71)90010-5. S2CID 8623866.

[2] Tom Bylander (1994年9月). 「命題STRIPSプランニングの計算複雑性」.人工知能. 69 ( 1–2 ): 165–204 . CiteSeerX 10.1.1.23.199 . doi :10.1016/0004-3702(94)90081-7.

[3] Haslum, Patrik (2007). 「計画問題における偶発的な複雑性の低減」 . 第20回国際人工知能合同会議議事録. pp. 1898– 1903.

[4] Schmid, Ute (1999).反復マクロ演算子の再考：プログラム合成をプランニング学習に適用する（技術レポート）. カーネギーメロン大学コンピュータサイエンス学部. doi : 10.21236/ada363524 .

[5] Sutton, Richard S.、Precup, Doina、Singh, Satinder (1999). 「MDPとセミMDPの間：強化学習における時間的抽象化の枠組み」人工知能誌、112 ( 1–2 ). エルゼビア: 181–211 . doi : 10.1016/s0004-3702(99)00052-1 .{{cite journal}}: CS1 maint: 複数の名前: 著者リスト (リンク)