状況計算

状況計算は、動的領域の表現と推論のために設計された論理形式論である。 1963年にジョン・マッカーシーによって初めて導入された。 ^{[ 1 ] [ 2 ]}本稿で紹介する状況計算の主要バージョンは、レイ・ライターが1991年に導入したものに基づいている。続いて、マッカーシーの1986年バージョンと論理プログラミング定式化について述べる。

概要

状況計算は、変化するシナリオを一階述語論理式の集合として表現します。この計算の基本要素は次のとおりです。

• 世界情勢を説明する流暢な表現
• 世界で実行できるアクション
• 状況

ドメインは、次のようないくつかの式によって形式化されます。

• アクションの前提条件公理（アクションごとに1つ）
• 後継状態公理（各流暢性ごとに1つ）
• 様々な状況における世界を記述する公理
• 状況計算の基礎公理

実行例として、シンプルなロボットワールドをモデル化します。このワールドには、ロボット1台と複数の無生物オブジェクトが存在します。ワールドはグリッド状に配置されているため、座標点を用いて位置を指定できます。ロボットはワールド内を移動し、アイテムを拾ったり落としたりすることができます。アイテムによっては、ロボットが持ち上げられないほど重かったり、落とすと壊れてしまうものもあります。また、ロボットは保持している壊れたアイテムを修理する機能も備えています。 ${\displaystyle (x,y)}$

要素

状況計算の主な要素は、行為、流暢性、そして状況です。世界の記述には、通常、いくつかのオブジェクトも関与します。状況計算は、行為、状況、そしてオブジェクトの3つの種類を持つソートされたドメインに基づいています。オブジェクトには、行為や状況以外のすべてが含まれます。各種類の変数を使用できます。行為、状況、そしてオブジェクトはドメインの要素ですが、流暢性は述語または関数としてモデル化されます。

アクション

アクションはドメインの一種を形成します。アクション型の変数や、結果がアクション型となる関数を使用できます。アクションは定量化できます。ロボットの世界の例において、アクションの項として考えられるのは、ロボットが新しい場所へ移動する、あるいはロボットが物体oを拾い上げるといった動作です。アクションが実行可能であることを示すために、 特別な述語Poss が使用されます。 ${\displaystyle move(x,y)}$ ${\displaystyle (x,y)}$ ${\displaystyle pickup(o)}$

状況

状況計算では、動的な世界は、その世界内で行われる様々な行為の結果として、一連の状況を経て進行するものとしてモデル化されます。状況とは、行為の発生履歴を表します。ここで説明するライター版の状況計算では、状況は状態を表すものではありません。これは、「状況」という用語の文字通りの意味、そしてマッカーシーとヘイズによる元の定義とは相反するものです。この点は、ライターによって次のように要約されています。

状況とは、有限の行動の連続である。それだけだ。それは状態でもスナップショットでもなく、歴史なのだ。^{[ 3 ]}

何らかの動作が行われる前の状況は通常⁠ ⁠ ${\displaystyle S_{0}}$と表記され、初期状況と呼ばれます。動作の実行によって生じる新しい状況は、関数記号doを用いて表記されます（他の参考文献^{[ 4 ]}でもresultが使用されています）。この関数記号は、状況と動作を引数として持ち、結果として状況を持ちます。後者は、与えられた状況において与えられた動作を実行した結果生じる状況です。

状況は動作の連続であり、状態ではないという事実は、 が かつ の場合にのみ と等しいという公理によって強制されます。状況が状態である場合、この条件は意味をなしません。なぜなら、2つの異なる状態で実行された2つの異なる動作が同じ状態になる可能性があるからです。 ${\displaystyle do(a,s)}$ ${\displaystyle do(a',s')}$ ${\displaystyle a=a'}$ ${\displaystyle s=s'}$

例のロボットの世界では、ロボットの最初のアクションが場所 に移動することである場合、最初のアクションは となり、結果として生じる状況は となります。次のアクションがボールを拾うことである場合、結果として生じる状況は となります。 や などの状況に関する用語は、実行されたアクションのシーケンスを示すものであり、実行の結果として生じる状態の説明ではありません。 ${\displaystyle (2,3)}$ ${\displaystyle move(2,3)}$ ${\displaystyle do(move(2,3),S_{0})}$ ${\displaystyle do(pickup(Ball),do(move(2,3),S_{0}))}$ ${\displaystyle do(move(2,3),S_{0})}$ ${\displaystyle do(pickup(Ball),do(move(2,3),S_{0}))}$

流暢な

真理値が変化する可能性のある文は、関係的フルエント（状況を最終引数として取る述語）によってモデル化されます。また、関数的フルエント（状況を最終引数として取り、状況依存の値を返す関数）も考えられます。フルエントは「世界の特性」と考えることができます。

この例では、このフルーエントは、ロボットが特定の状況において特定の物体を運んでいることを示すために使用できます。ロボットが最初に何も運んでいない場合、は偽ですが、は真です。ロボットの位置は、特定の状況におけるロボットの 位置を返す関数型フルーエントを使用してモデル化できます。 ${\displaystyle {\textit {isCarrying}}(o,s)}$ ${\displaystyle {\textit {isCarrying}}(Ball,S_{0})}$ ${\displaystyle {\textit {isCarrying}}(Ball,do(pickup(Ball),S_{0}))}$ ${\displaystyle location(s)}$ ${\displaystyle (x,y)}$

公式

動的な世界の記述は、アクションに関する式 (前提条件と結果)、世界の状態に関する式、および基礎公理という 3 種類の式を使用して、 第 2 階論理でエンコードされます。

行動の前提条件

特定の状況では、一部のアクションは実行できない場合があります。例えば、実際に運んでいるとき以外は、物体を下ろすことはできません。アクションの実行に関する制約は、 という形式のリテラルによってモデル化されます。ここで、aはアクション、s は状況、Possはアクションの実行可能性を表す特殊な二項述語です。この例では、物体を落とすことが、それを運んでいるときのみ可能であるという条件は、次のようにモデル化されます。 ${\displaystyle {\textit {Poss}}(a,s)}$

${\displaystyle {\textit {Poss}}(drop(o),s)\leftrightarrow {\textit {isCarrying}}(o,s)}$

より複雑な例として、次のモデルでは、ロボットは一度に 1 つの物体しか運ぶことができず、一部の物体はロボットが持ち上げるには重すぎる (述語heavyで示される) ことをモデル化しています。

${\displaystyle {\textit {Poss}}(pickup(o),s)\leftrightarrow (\forall z\ \neg {\textit {isCarrying}}(z,s))\wedge \neg heavy(o)}$

アクション効果

ある状況においてある行動が可能であるならば、その行動が流暢性に及ぼす影響を特定する必要があります。これは効果公理によって行われます。例えば、物体を拾うとロボットがそれを運ぶという事実は、次のようにモデル化できます。

${\displaystyle Poss(pickup(o),s)\rightarrow {\textit {isCarrying}}(o,do(pickup(o),s))}$

条件付き効果、つまり現在の状態に依存する効果を指定することも可能です。次のモデルは、一部のオブジェクトが壊れやすい（述語fragileで示される）こと、そしてそれらをドロップすると壊れる（流暢なbrokenで示される）ことを表わしています。

${\displaystyle Poss(drop(o),s)\wedge fragile(o)\rightarrow broken(o,do(drop(o),s))}$

この式はアクションの効果を正しく説明していますが、フレーム問題のため、アクションを論理的に正しく説明するには不十分です。

フレームの問題

上記の式は動作の効果について推論するのには適しているように見えますが、重大な弱点があります。それは、動作の非効果を導出するのに使用できないことです。例えば、ロボットが物体を拾った後、ロボットの位置は変化していないと推論することはできません。これには、いわゆるフレーム公理、つまり次のような式が必要です。

${\displaystyle Poss(pickup(o),s)\wedge location(s)=(x,y)\rightarrow location(do(pickup(o),s))=(x,y)}$

フレーム公理を指定する必要性は、動的な世界を公理化する上での問題として長年認識されており、フレーム問題として知られています。一般に、このような公理は非常に多く存在するため、設計者が必要なフレーム公理を省略したり、世界の記述に変更が加えられた際に適切な公理をすべて修正し忘れたりする可能性が非常に高くなります。

後継国家公理

後継状態公理は、状況計算におけるフレーム問題を「解決」します。この解決策によれば、設計者は特定の流動性の値を変化させるすべての方法を効果公理として列挙する必要があります。流動性の値に影響を与える効果公理は、一般化された形で、正の効果公理と負の効果公理として記述できます。 ${\displaystyle F({\overrightarrow {x}},s)}$

${\displaystyle Poss(a,s)\wedge \gamma _{F}^{+}({\overrightarrow {x}},a,s)\rightarrow F({\overrightarrow {x}},do(a,s))}$

${\displaystyle Poss(a,s)\wedge \gamma _{F}^{-}({\overrightarrow {x}},a,s)\rightarrow \neg F({\overrightarrow {x}},do(a,s))}$

この式は、状況sにおける動作a が、後続の状況 s において流暢性Fを真にする条件を記述しています。同様に、この式は、状況sにおける動作a の実行が、後続の状況 s における流暢性Fを偽にする条件を記述しています。 ${\displaystyle \gamma _{F}^{+}}$ ${\displaystyle do(a,s)}$ ${\displaystyle \gamma _{F}^{-}}$

この公理のペアが、流暢なF が値を変更できるすべての方法を記述している場合、単一の公理として書き直すことができます。

${\displaystyle Poss(a,s)\rightarrow \left[F({\overrightarrow {x}},do(a,s))\leftrightarrow \gamma _{F}^{+}({\overrightarrow {x}},a,s)\vee \left(F({\overrightarrow {x}},s)\wedge \neg \gamma _{F}^{-}({\overrightarrow {x}},a,s)\right)\right]}$

言葉で言えば、この式は次のように述べています。「状況sでアクションaを実行できると仮定すると、流暢なF が結果の状況で真となるのは、 sでa を実行するとそれが真になる場合、またはそれが状況sで真であり、 sでa を実行してもそれが偽にならない場合のみです。」 ${\displaystyle do(a,s)}$

例として、上で紹介した流暢なブロークンの値は、次の後続状態公理によって与えられます。

${\displaystyle Poss(a,s)\rightarrow \left[broken(o,do(a,s))\leftrightarrow a=drop(o)\wedge fragile(o)\vee broken(o,s)\wedge a\neq repair(o)\right]}$

州

初期状態やその他の状況の特性は、式で記述するだけで指定できます。例えば、初期状態に関する事実は、（状態ではなく状況）に関する表明を行うことで形式化されます。以下の文は、初期状態においてロボットは何も運んでおらず、位置 にあり、壊れた物体は存在しないことをモデル化しています。 ${\displaystyle S_{0}}$ ${\displaystyle (0,0)}$

${\displaystyle \forall z\,\neg {\textit {isCarrying}}(z,S_{0})}$

${\displaystyle location(S_{0})=(0,0)\,}$

${\displaystyle \forall o\,\neg broken(o,S_{0})}$

基礎公理

状況計算の基礎公理は、状況が歴史であるという考えを、 によって形式化します。また、状況に関する第二階帰納法などの他の性質も含んでいます。 ${\displaystyle do(a,s)=do(a',s')\iff a=a'\land s=s'}$

回帰

回帰^{[ 5 ]}は、状況計算における帰結を証明するためのメカニズムである。^{[ 6 ]}これは、状況を含む式を、行為aと状況sを含む式で表し、状況sを含まない式で表すことに基づいている。この手順を繰り返すことで、初期状況S ₀のみを含む同等の式を得ることができる。この式から帰結を証明する方が、元の式から証明するよりも簡単であると考えられている。 ${\displaystyle do(a,s)}$ ${\displaystyle do(a,s)}$

ゴログ

GOLOGは状況計算に基づいた論理プログラミング言語である。 ^{[ 7 ] [ 8 ]}

状況計算のオリジナルバージョン

マッカーシーとヘイズによる初期の状況計算と現在用いられている状況計算の主な違いは、状況の解釈にあります。現代の状況計算では、状況とは一連の行動です。当初、状況は「ある瞬間における宇宙の完全な状態」と定義されていました。そのような状況を完全に記述することは不可能であることは当初から明らかでした。状況に関するいくつかの記述を与え、そこから帰結を導き出すという考え方でした。これは、状態が既知の事実の集合、つまり宇宙の 不完全な記述である可能性があるとされる、流暢計算のアプローチとも異なります。

状況計算のオリジナル版では、フルーエントは具体化されていません。言い換えれば、変化する可能性のある条件は、関数ではなく述語によって表現されます。実際には、マッカーシーとヘイズは、フルーエントを状況に依存する関数として定義しましたが、その後、常に述語を使用してフルーエントを表現しました。たとえば、状況sにおいて場所xに雨が降っているという事実は、リテラル によって表現されます。マッカーシーによる状況計算の 1986 年版では、機能的なフルーエントが使用されています。たとえば、状況sにおけるオブジェクトxの位置は、の値によって表現されます。ここで、位置は関数です。このような関数に関するステートメントは、等式を使用して与えることができます。は、オブジェクトxの位置が2 つの状況sとで同じであることを意味します。 ${\displaystyle raining(x,s)}$ ${\displaystyle location(x,s)}$ ${\displaystyle location(x,s)=location(x,s')}$ ${\displaystyle s'}$

アクションの実行は関数resultによって表されます。つまり、状況sにおけるアクションaの実行は状況 となります。アクションの効果は、状況sにおける流暢性と状況 における流暢性を関連付ける式によって表されます。例えば、ドアを開けるというアクションの結果、ドアが施錠されていない場合はドアが開くことは、次のように表されます。 ${\displaystyle {\textit {result}}(a,s)}$ ${\displaystyle {\textit {result}}(a,s)}$

${\displaystyle \neg locked(door,s)\rightarrow open(door,{\textit {result}}(opens,s))}$

述語「locked」と「open」は、それぞれドアが施錠されている状態と開いている状態を表します。これらの状態は変化する可能性があるため、状況引数を持つ述語で表されます。式は、ある状況においてドアが施錠されていない場合、定数「opening」で表される動作「opening」を実行した後にドアが開いていることを示します。

これらの式は、妥当と考えられるすべてのことを導き出すのに十分ではありません。実際、異なる状況における流暢性は、それらが行為の前提条件と結果である場合にのみ関連しています。流暢性が行為の影響を受けない場合、それが変化しなかったと推論する方法はありません。例えば、上記の式は、が から従うということを意味しません。これは予想される結果（ドアを開けても施錠されない）です。慣性が成り立つためには、フレーム公理と呼ばれる式が必要です。これらの式は、行為の非結果をすべて規定します。 ${\displaystyle \neg locked(door,{\textit {result}}(opens,s))}$ ${\displaystyle \neg locked(door,s)}$

${\displaystyle \neg locked(door,s)\rightarrow \neg locked(door,{\textit {result}}(opens,s))}$

状況計算の最初の定式化では、後に⁠ ⁠ ${\displaystyle S_{0}}$と表記される初期状況は明示的に特定されていません。状況が世界の記述であるとみなされる場合、初期状況は必要ありません。たとえば、ドアは閉じられているが鍵がかかっておらず、ドアを開けるという動作が実行されるというシナリオを表すことは、定数s を初期状況を意味するものとし、それについて述語（たとえば、）を作成することによって形式化されます。変化後にドアが開いていることは、式が含意されることで反映されます。代わりに初期状況は、現代の状況計算のように、状況が動作の履歴であるとみなされる場合に必要になります。これは、初期状況が動作の空のシーケンスを表すためです。 ${\displaystyle \neg locked(door,s)}$ ${\displaystyle open(door,{\textit {result}}(opens,s))}$

1986 年にマッカーシーによって導入された状況計算のバージョンは、関数の流暢性 (たとえば、状況sにおけるxの位置を表す項) の使用と、フレーム公理の代わりにサーカムスクリプションを使用する試みによって、元のバージョンと異なります。 ${\displaystyle location(x,s)}$

論理プログラムとしての状況計算

状況計算を論理プログラムとして記述することも可能です (例: Kowalski 1979、Apt and Bezem 1990、Shanahan 1997)。

${\displaystyle {\textit {Holds}}(f,do(a,s))\leftarrow {\textit {Poss}}(a,s)\wedge {\textit {Initiates}}(a,f,s)}$

${\displaystyle {\textit {Holds}}(f,do(a,s))\leftarrow {\textit {Poss}}(a,s)\wedge {\textit {Holds}}(f,s)\wedge \neg {\textit {Terminates}}(a,f,s)}$

ここで、Holdsはメタ述語であり、変数fはfluents の範囲を持ちます。述語Poss、Initiates、Terminates はそれぞれ述語Poss、、に対応します。左矢印 ← は同値 ↔ の半分です。残りの半分はプログラムの完了に暗黙的に含まれており、否定は否定として失敗として解釈されます。帰納法の公理も暗黙的であり、プログラムの特性を証明するためにのみ必要です。論理プログラムを実行するために通常使用されるメカニズムである SLD 解決のような後方推論は、回帰を暗黙的に実装します。 ${\displaystyle \gamma _{F}^{+}({\overrightarrow {x}},a,s)}$ ${\displaystyle \gamma _{F}^{-}({\overrightarrow {x}},a,s)}$

参照

• フレームの問題
• イベント計算

参考文献

1. マッカーシー、ジョン (1963). 「状況、行動、因果律」(PDF) .スタンフォード大学技術報告書. 2020年3月21日時点のオリジナル(PDF)からアーカイブ。
2. 「状況計算」 Engati . 2025年11月17日閲覧。
3. 「ECSTER討論会への寄稿」。
4. 「物語の組み合わせ、ジョン・マッカーシー他 (1998)」（PDF）。
5. リチャード・ウォルディンガー「複数の目標を同時に達成する」『人工知能入門』250-271ページ、モーガン・カウフマン、1981年。
6. Reiter, R., 1991. 「状況計算におけるフレーム問題：単純な解（場合によっては）と目標回帰の完全性の結果」『計算の人工数学理論』3.
7. Lakemeyer, Gerhard. 「状況計算とGolog：チュートリアル」（PDF）www.hybrid-reasoning.org . 2014年7月16日閲覧。
8. 「GOLOGに関する出版物」 。 2014年7月16日閲覧。

• J. マッカーシーとP. ヘイズ (1969).人工知能の観点から見たいくつかの哲学的問題. B. メルツァーとD. ミチー編,機械知能, 4:463–502. エディンバラ大学出版局, 1969.
• R. Kowalski (1979). 問題解決の論理 - Elsevier North Holland.
• KR AptとM. Bezem (1990). 非巡回プログラム. 第7回国際論理プログラミング会議. MIT Press. エルサレム, イスラエル.
• R. ライター (1991). 状況計算におけるフレーム問題：単純な解（場合によっては）と目標回帰の完全性の結果．ウラジミール・リフシッツ編著『人工知能と計算の数学的理論：ジョン・マッカーシー記念論文集』 359-380ページ，サンディエゴ，カリフォルニア州，米国．Academic Press Professional, Inc. 1991．
• M. シャナハン(1997). 『フレーム問題の解決：慣性の常識法則の数学的考察』MIT 出版.
• H. Levesque, F. Pirri, R. Reiter (1998).状況計算の基礎.人工知能に関する電子取引, 2(3–4):159-178.
• F. ピリとR. ライター (1999). 状況計算のメタ理論へのいくつかの貢献. ACMジャーナル, 46(3):325–361. doi : 10.1145/316542.316545
• R.ライター（2001）『知識の実践：動的システムの仕様定義と実装のための論理的基礎』MIT出版。

「 https://en.wikipedia.org/w/index.php?title=Situation_calculus&oldid=1322648864」より取得