STRIPS

STRIPS (Stanford Research Institute Problem Solver)

STRIPSは、1971年にRichard FikesとNils Jonh Nilssonによって開発された自動計画に特化した人工知能のフレームワークです。このシステムは、状態から目標状態への遷移を計画するために、形式的な言語を利用します。ここでは、システムそのものではなく、その構成要素である形式言語について詳しく解説します。

STRIPSの構成要素

STRIPSのインスタンスは以下の要素で構成されています。

1. 初期状態 (Init)：計画が開始される前の状況を示します。
2. 目標状態 (Goal)：達成すべき最終的な状況を記述します。
3. 行動 (Actions)：状況を変化させる操作であり、オペレータとも呼ばれます。各行動には以下の情報が含まれます。
- 事前条件 (Preconditions)：その行動が実行されるために必要な条件。
- 効果/事後条件 (Effects/Postconditions)：行動の結果として満たされるべき条件。

STRIPSでは、インスタンスを形式的に記述するための手法がいくつかあり、命題論理、一階述語論理、グラフ理論に基づいたものなどがあります。

命題論理形式

STRIPSのインスタンスは、一般的に以下のように表されます:

\[ \langle O, I, G \rangle \]

ここで、

• - \(O\)はオペレータの集合を示し、各オペレータは以下の形式で定義されます:

\[ o = \langle pre(o), e^{+}(o), e^{-}(o) \rangle \]
- \(pre(o)\)：事前条件、\(e^{+}(o)\)：追加効果、\(e^{-}(o)\)：削除効果。

• - \(I\)は初期状態を示し、これは全ての初期時点で真となる命題変数の集合です。
• - \(G\)は目標条件で、ゴールに達した際に真となるべき命題論理式を表します。

一階述語論理形式

この形式では、アクションにパラメータの概念が追加され、より一般的な計画の実行に対応します。

グラフ理論形式

STRIPSのインスタンスは、ステートをノード、アクションをラベル、遷移をエッジとしてグラフ理論の問題として扱うことができます。このアプローチでは、状態の遷移が視覚的に表現されるため、計画の可視化と理解が容易になります。

自動計画のプロセス

自動計画システムは、定義された初期状態から目標状態へと導く計画を生成します。具体的には、命題の集合を利用して任意の状態を表現し、状態間の遷移を遷移関数としてモデル化します。行動が適用できる条件を満たす場合、状態の遷移が行われ、目標に近づきます。

計画は、\(strips\)インスタンスの形で記述され、各状態の遷移は再帰的に展開されます。

具体例：サルとバナナの問題

ある研究室にバナナがあり、サルがそれを取ろうとします。サルは箱を使ってバナナを取る必要があるため、以下のような行動が考えられます。

• - 行動

- _Move(X, Y)_
- _ClimbUp(Location)_
- _ClimbDown(Location)_
- _MoveBox(X, Y)_
- _TakeBananas(Location)_

各行動には事前条件と事後条件が設定されており、サルが成功裏にバナナを取るための計画を構築します。

計算複雑性

STRIPSにおいて、計画が存在するかを決定する問題はPSPACE完全です。より制約を加えた形では、この問題がNP完全であることも知られています。

結論

STRIPSは、非常に影響力のある自動計画手法であり、現在の人工知能研究においても広く利用されています。様々な形式における拡張が行われ、部分的な初期状態を使用する試みにも取り組まれています。

もう一度検索