トップ :: G 物理学 :: G06 計算;計数




【発明の名称】 推論装置、システム及び方法並びに推論用ソフトウェアを記録した記録媒体
【発明者】 【氏名】川村 隆浩

【氏名】長野 伸一
【要約】 【課題】メンタルモデルを利用したマルチエージェントのインタラクションプロトコルにおいて、一連のプロトコルを単位に事前条件や事後条件を付加することで、少ない負担で効率的かつ安定して推論を行う技術を提供する。

【解決手段】信念及び知識データベース１は、エージェントの内部状態を保持する。欲求リスト４には、エージェントの達成したい目標を設定される。プラン・ライブラリ２は、エージェントの活動を実現し、事前条件と、行動と、事後条件と、を含むプランを複数保持する。意思リスト５は、実行するために選択されたプランを保持する。推論部３は、エージェントの前記内部状態に基いて、プラン・ライブラリ２に格納された前記プランの中から次の行動を選択及び実行する。
【特許請求の範囲】
【請求項１】 一又は二以上のエージェントを活動させエージェント間の協調により推論を行う推論装置において、エージェントの内部状態を保持するための手段と、エージェントの活動を実現し、事前条件と、行動と、事後条件と、を含むプランを複数保持するための手段と、エージェントの前記内部状態に基いて、前記プランの中から次の行動を選択及び実行するための推論手段と、を備え、前記プランは、一連のアクションを含むプロトコルに対して、自エージェントの内部状態又は他エージェントの内部状態のうち少なくとも一方について記述した事前条件及び事後条件のうち少なくとも一方を付加したことを特徴とする推論装置。
【請求項２】 請求項１記載の推論装置が複数、通信手段で相互に接続されたことを特徴とする推論システム。
【請求項３】 前記推論手段は、いずれかのエージェントで不具合が発生した時に、その不具合に関係していた処理のみを選択的に再実行するように構成されたことを特徴とする請求項１に記載の推論装置。
【請求項４】 前記推論手段は、不具合のあったエージェントの信念を事前条件又は事後条件が参照しているプランと、事前条件又は事後条件が、不具合のあったエージェントの信念と依存関係のある自エージェントの信念を参照している前記自エージェントのプランと、を再実行するように構成されたことを特徴とする請求項３に記載の推論装置。
【請求項５】 一又は二以上の推論装置上でそれぞれ一又は二以上のエージェントを活動させエージェント間の協調により推論を行う推論方法において、エージェントの内部状態を保持するためのステップと、エージェントの活動を実現し、事前条件と、行動と、事後条件と、を含むプランを予め複数格納しておくステップと、エージェントの前記内部状態に基いて、前記プランの中から次の行動を選択及び実行するための推論ステップと、を含み、前記プランは、一連のアクションを含むプロトコルに対して、自エージェントの内部状態又は他エージェントの内部状態のうち少なくとも一方について記述した事前条件及び事後条件のうち少なくとも一方を付加したことを特徴とする推論方法。
【請求項６】 前記推論ステップは、いずれかのエージェントで不具合が発生した時に、その不具合に関係していた処理のみを選択的に再実行することを特徴とする請求項５に記載の推論方法。
【請求項７】 前記推論ステップは、不具合のあったエージェントの信念を事前条件又は事後条件が参照しているプランと、事前条件又は事後条件が、不具合のあったエージェントの信念と依存関係のある自エージェントの信念を参照している前記自エージェントのプランと、を再実行することを特徴とする請求項６に記載の推論方法。
【請求項８】 コンピュータを制御することにより、推論装置上でそれぞれ一又は二以上のエージェントを活動させエージェント間の協調により推論を行う推論用ソフトウェアを記録した記録媒体において、そのソフトウェアは前記コンピュータに、エージェントの内部状態を保持させ、エージェントの活動を実現し、事前条件と、行動と、事後条件と、を含むプランを予め複数格納させ、エージェントの前記内部状態に基いて、前記プランの中から次の行動を選択及び実行させ、前記プランは、一連のアクションを含むプロトコルに対して、自エージェントの内部状態又は他エージェントの内部状態のうち少なくとも一方について記述した事前条件及び事後条件のうち少なくとも一方を付加したことを特徴とする推論用ソフトウェアを記録した記録媒体。
【発明の詳細な説明】【０００１】
【発明の属する技術分野】この発明は、メンタルモデルを利用したマルチエージェントのインタラクションプロトコルに関するもので、特に、一連のプロトコルを単位に事前条件や事後条件を付加することで、少ない負担で効率的かつ安定して推論を行うようにしたものである。
【０００２】
【従来の技術】近年、情報処理技術の進展に伴い、エージェントを単位として情報処理システムを構築するエージェント指向技術が提案されている。このエージェントは自律性を持つソフトウェア上の実体であり、複数のエージェントの協力で処理を行うマルチエージェントの技術も提案されている。このようなマルチエージェントにおいて、複数のエージェント間での協力を実現する技術的アプローチは、メンタルモデルアプローチとプロトコルアプローチに大別できる。
【０００３】このうちメンタルモデルアプローチは、各エージェントについてその信念等の心的状態を表すメンタルモデル（ＢＤＩとも呼ぶ）を適用し心的状態に適合するルールを実行させるもので、プロトコルアプローチは、所定のプロトコルによりエージェント間で交渉を行わせるものである。なお、交渉などエージェント間の通信を行う形式としては、ＡＣＬ(Agent Communication Language)メッセージなどが知られている。
【０００４】また、マルチエージェント研究において、個々のエージェントのメンタルモデルを考慮し、ＡＣＬメッセージのセマンティクス（Semantics：意味）と合わせて、エージェントが次の行動を決定する手法に関する研究は数多い（例えば参考文献：T. Labrou, T. Finin, Y. Peng, Agent Communication Languages: TheCurrent Landscape, Intelligent Systems, IEEE, March/April pp.45--52, 1999.を参照）。
【０００５】
【発明が解決しようとする課題】しかしながら、メンタルモデルアプローチとプロトコルアプローチの組合せにも次のような問題点が存在した。まず、一般にＢＤＩを表現するために用いられる様相論理(Modal Logic)は、実世界における全ての事象を表現することは困難であることが知られており、このため適切な実装は困難であった。
【０００６】しかも、事象は刻々と変わるためにエージェントはリアクティブに行動することを求められるが、実行時に逐次現在の心的状態に適合するルールを多数のなかから見つけだし、評価しながら行動するのでは効率化は困難であった。また、非決定的なルールの存在も問題となり、過度の非決定性はシステムの安定性を損なう。更に、様々な種類のオークションなど複雑な交渉プロトコルをメンタルモデルによるルールに分解し、それらのルールを適用していった結果としてエージェントにプロトコルと同じ動作をさせるようにすること、つまり、プロトコルをプラニングによって生成するのはかなり煩雑な作業となり、システム開発や保守の負担増大という問題もあった。加えて、多くのソフトウェア設計者はメンタルモデルに不馴れであり、ＢＤＩに基づくシステム設計はハードルが高いとも予想される。
【０００７】そのため、現在まで多くのマルチエージェントシステムは、決められた順序でＡＣＬメッセージを交換するように記述したインタラクションプロトコル（Interaction Protocol）をサポートするのみである（参考文献：F. Bellifemine, A.Poggi, G. Rimassa, JADE - A FIPA-compliant agent framework, The Practical Application of Intelligent Agents and Multi-Agents(PAAM99), 1999.）。しかし、実行時にメンタルモデルを考慮しないのであれば、ＡＣＬという高度でかつ冗長な言語を使う必要性は少なく、プロトコル設計時にＡＣＬのセマンティクスを考慮することにもあまり意味はない。
【０００８】そこで、近年、これらメンタルモデルアプローチとプロトコルアプローチの中間的なアプローチに関する研究が様々な形で進められているが（参考文献：J. Pitt, A. Mamdami, A protocol-based semantics for an agent communication language, Proceedings of the Sixteenth International Joint Conference onArtificial Intelligence(IJCAI99), pp.486--491 1999.）、それら従来技術も、上記のようなさまざまな問題、例えば、ルール数が多いことによる低い処理効率、ルールの過度の非決定性、プランニングの煩雑さ、開発や保守の負担増大、といった課題を解決するための具体的かつ効果的な技術を提供するものではなかった。
【０００９】本発明は、上記のような従来技術の問題点を解決するため意に提案されたもので、その目的は、メンタルモデルを利用したマルチエージェントのインタラクションプロトコルにおいて、一連のプロトコルを単位に事前条件や事後条件を付加することで、少ない負担で効率的かつ安定して推論を行う技術すなわち推論装置、システム及び方法並びに推論用ソフトウェアを記録した記録媒体を提供することである。また、本発明の他の目的は、いずれかのエージェントで不都合が発生した場合のロールバック範囲を信念の参照関係に基づいて限定することで処理を効率化する推論の技術を提供することである。
【００１０】
【課題を解決するための手段】上記の目的を達成するため、請求項１の発明は、一又は二以上のエージェントを活動させエージェント間の協調により推論を行う推論装置において、エージェントの内部状態を保持するための手段と、エージェントの活動を実現し、事前条件と、行動と、事後条件と、を含むプランを複数保持するための手段と、エージェントの前記内部状態に基いて、前記プランの中から次の行動を選択及び実行するための推論手段と、を備え、前記プランは、一連のアクションを含むプロトコルに対して、自エージェントの内部状態又は他エージェントの内部状態のうち少なくとも一方について記述した事前条件及び事後条件のうち少なくとも一方を付加したことを特徴とする。
【００１１】請求項５の発明は、請求項１の発明を方法という見方からとらえたもので、一又は二以上の推論装置上でそれぞれ一又は二以上のエージェントを活動させエージェント間の協調により推論を行う推論方法において、エージェントの内部状態を保持するためのステップと、エージェントの活動を実現し、事前条件と、行動と、事後条件と、を含むプランを予め複数格納しておくステップと、エージェントの前記内部状態に基いて、前記プランの中から次の行動を選択及び実行するための推論ステップと、を含み、前記プランは、一連のアクションを含むプロトコルに対して、自エージェントの内部状態又は他エージェントの内部状態のうち少なくとも一方について記述した事前条件及び事後条件のうち少なくとも一方を付加したことを特徴とする。
【００１２】請求項８の発明は、請求項１，５の発明を、コンピュータのソフトウェアを記録した機械可読型記録媒体という見方から捉えたもので、コンピュータを制御することにより、推論装置上でそれぞれ一又は二以上のエージェントを活動させエージェント間の協調により推論を行う推論用ソフトウェアを記録した記録媒体において、そのソフトウェアは前記コンピュータに、エージェントの内部状態を保持させ、エージェントの活動を実現し、事前条件と、行動と、事後条件と、を含むプランを予め複数格納させ、エージェントの前記内部状態に基いて、前記プランの中から次の行動を選択及び実行させ、前記プランは、一連のアクションを含むプロトコルに対して、自エージェントの内部状態又は他エージェントの内部状態のうち少なくとも一方について記述した事前条件及び事後条件のうち少なくとも一方を付加したことを特徴とする。
【００１３】請求項２の推論システムは、請求項１記載の推論装置が複数、通信手段で相互に接続されたことを特徴とする。
【００１４】これらの態様では、メンタルモデルを利用したインタラクションプロトコルの記述形式とそれを基く推論手法を用いることで、まず、メンタルモデルアプローチに比べて、ルールの単位が１アクションから、一連のアクションを含むプロトコル（サブプロトコルと呼ぶ）になることでル−ル数が減少し、実行時効率が向上する。また、信念等の内部状態に基く条件分岐がアクション単位よりも大きな単位であるプロトコル単位となるので、過度の非決定性を減少させることにも役立つ。更に、このアプローチはオークションなどの高度に設計されたプロトコルを、既に立てられているプランと見なして組み合わせていく手法(Planning fromSecond principles)であるともいえるため、従来のようにプロトコルをプランニングによって生成する場合と比べ、プラニングの煩雑さを回避できる。
【００１５】一方、この態様では、メンタルモデルを利用したインタラクションプロトコルの記述形式とそれに基く推論手法を用いることで、プロトコルアプローチに比べて、サブプロトコル単位で宣言的に記述することができる。このため、全ての処理を１つの連続した手続きとして記述する場合に比べて、開発者はサブプロトコル間の接続関係を陽に指定する必要がなくなり、作業負担が軽減されシステムの信頼性も向上する。また、保守は各ルールが正しいかどうかだけによってなされるので、プログラム全体を通してのデバッグより容易である。
【００１６】請求項３の発明は、請求項１に記載の推論装置において、前記推論手段は、いずれかのエージェントで不具合が発生した時に、その不具合に関係していた処理のみを選択的に再実行するように構成されたことを特徴とする。
【００１７】請求項６の発明は、請求項３の発明を方法という見方からとらえたもので、請求項５に記載の推論方法において、前記推論ステップは、いずれかのエージェントで不具合が発生した時に、その不具合に関係していた処理のみを選択的に再実行することを特徴とする。
【００１８】請求項４の発明は、請求項３に記載の推論装置において、前記推論手段は、不具合のあったエージェントの信念を事前条件又は事後条件が参照しているプランと、事前条件又は事後条件が、不具合のあったエージェントの信念と依存関係のある自エージェントの信念を参照している前記自エージェントのプランと、を再実行するように構成されたことを特徴とする。
【００１９】請求項７の発明は、請求項４の発明を方法という見方からとらえたもので、請求項６に記載の推論方法において、前記推論ステップは、不具合のあったエージェントの信念を事前条件又は事後条件が参照しているプランと、事前条件又は事後条件が、不具合のあったエージェントの信念と依存関係のある自エージェントの信念を参照している前記自エージェントのプランと、を再実行することを特徴とする。
【００２０】これらの態様では、プロトコルアプローチに対するメリットとして、メンタルモデルに基づく推論機能を用いることにより、あるエージェントで物理的あるいは論理的な原因からロールバックが発生した際に、全てのエージェントが一斉にロールバックしそれまでの全ての処理を再実行するのではなく、不具合の発生したエージェントに関する信念や知識を有するエージェントのみが自らの信念を再確認する。これにより、必要な部分だけが再実行されるので不具合からの立ち直りが早くなると共に、関係のないエージェントは処理を継続できるというメリットがあり、推論が効率化及び安定化される。
【００２１】
【発明の実施の形態】次に、本発明の実施の形態（以下「実施形態」と呼ぶ）について図面を参照して具体的に説明する。なお、本実施形態は、典型的にはコンピュータをソフトウェアで制御することで実現される。この場合のソフトウェアは、コンピュータのハードウェアを物理的に活用することで本発明の作用効果を実現するもので、また、従来技術との共通部分には従来技術も適用される。
【００２２】但し、この場合のハードウェアやソフトウェアの種類や構成、ソフトウェアで処理する範囲などは各種変更可能であり、例えばこのようなソフトウェアを記録したハードディスクドライブ・ディスクパック・ＣＤ−ＲＯＭなどの記録媒体は単独でも本発明の一態様である。このため、以下の説明では、本発明及び実施形態の各機能を実現する仮想的回路ブロックを用いる。
【００２３】〔１．構成〕本実施形態は、図１（全体構成図）に示すように、複数の推論装置Ｒが、通信手段であるＥｔｈｅｒｎｅｔ（登録商標）等の通信路Ｎにより相互に接続された推論システム（エージェントシステムとも呼ぶ）であり、各推論装置Ｒは、推論を行う推論部３と、デバイスドライバなどを用いた入力制御部１１及び出力制御部１２と、ネットワークカードなどの入出力部１３と、を備えている。これら各推論装置Ｒは、推論装置３や後述する各部の働きによりそれぞれ１つのエージェントを活動させ、それら各エージェントが通信路Ｎを介して相互に協調することで全体としての推論を行うものである。すなわち、エージェントは、推論部３が中心となって実行される一連の情報処理単位である。
【００２４】また、図２（推論装置Ｒの機能ブロック図）に示すように、各推論装置Ｒは、信念及び知識データベース１と、プラン・ライブラリ２と、推論部３と、欲求リスト４と、意思リスト５と、を備えている。このうち、信念及び知識データベース（Brief and Knowledge DB）１は、エージェントの内部状態を保持するための手段であり、そのエージェントにとっての事実や推論規則、公理を格納している。すなわち、有益と思われる公理(Axiom)の多くは事前に登録されている。なお、本エージェントシステムでは、ＡＯＰ（参考文献：Y. Shoham, An Overview of Agent-Oriented Programming, Software Agents, The MIT Press, pp.271--290, 1997.）に基づき、エージェントの内部変数は信念、知識として扱われている。また、図２に示す欲求リスト（Desires List）４は、エージェントの達成したい目標（「欲求」と呼ぶ）を設定するための記憶領域である。
【００２５】また、プラン・ライブラリ（Plan Library）２は、エージェントの活動を実現し、事前条件と、行動と、事後条件と、を含むプランを複数保持するための手段であり、具体的には、インタラクションプロトコルにメンタルルールを付加したものであるプランを格納している。すなわち、各プランは、一連のアクションを含むプロトコルに対して、自エージェントの内部状態や他エージェントの内部状態について記述した事前条件や事後条件を付加したものである。他にも、プラン・ライブラリ２の内容には、各エージェントに固有のローカルアクションプランが含まれる。また、意思リスト（Intention List）５は、実行するために選択されたプラン（意思と呼ぶ）を保持する記憶領域である。
【００２６】また、推論部（Reasoning System）３は、エージェントの前記内部状態に基いて、プラン・ライブラリ２に格納された前記プランの中から次の行動を選択及び実行するための推論手段であり、具体的には、プラン・ライブラリ２からのプランの選択、意思リスト５内の意思の実行、信念及び知識データベース１や欲求リスト４の更新を受け持つ。また、推論部３への情報入力はセンサ等の入力装置から行われ、推論部３からの情報出力はアクチュエータ等の出力装置から行われる。
【００２７】また、この推論部３は、いずれかのエージェントで不具合が発生した時に、その不具合に関係していた処理のみを選択的に再実行するように構成されている。具体的には、推論部３は、（１）不具合のあったエージェントの信念を事前条件又は事後条件が参照しているプランと、（２）事前条件又は事後条件が、不具合のあったエージェントの信念と依存関係のある自エージェントの信念を参照している前記自エージェントのプランと、を再実行するように構成されている。
【００２８】〔２．作用〕上記のように構成された本実施形態は、以下のように作用する。
〔２−１．基本的推論手順〕まず、各推論装置Ｒによる推論において、推論部３で実行される処理手順の概略を示す。すなわち、推論は、次のようなサイクルの繰り返しによって実現される。まず、ある目標と信念、知識の組み合わせがきっかけとなり、プラン・ライブラリ２からプランが選択され、意思リスト５に置かれる。次に、そのプランが実行されることによってエージェントが行動し、その結果エージェントの周りの環境（他エージェントを含む）が変化し、新しい信念、知識、目標が、信念及び知識データベース１、欲求リスト４、意思リスト５に設定される。このように追加された信念、知識は前向きに推論され、その含意の帰結が追加される。そして、再度プラン・ライブラリ２から新たなプランが選択される。推論は、以上のような過程の繰り返しによって実現される。
【００２９】〔２−２．プランの記述形式と具体例〕
〔２−２−１．プランの記述形式〕また、本実施形態におけるプランは次のような形式（メンタルルール付きインタラクションプロトコルと呼ぶ）で記述される。まず、一般にメンタルモデルアプローチでは、各発話行為を単位として行為実行の前提となる心的状態の条件(Precondtion、以下Precondとも表す)と行為実行後の心的状態(Postcodition、以下Postcondとも表す)が定義されている。
【００３０】それに対して、メンタルルール付きインタラクションプロトコルとは、ある問題解決に至るプロトコルのビルディングブロック（構成単位ブロック）となるサブプロトコルに対して、心的状態を条件とするルールを付加したものである。この場合、エージェントは、現在のメンタルモデルに基づいて推論を行い、実行すべきサブプロトコルを決定する。言い換えれば、本実施形態におけるメンタルルール付きインタラクションプロトコルは、インタラクションプロトコルをサブプロトコル単位で宣言的に記述することを許すものである。このような本実施形態におけるメンタルルール付きインタラクションプロトコルの記述形式の例を次に示す。
【数１】Precond: プロトコル実行の前提となる心的状態×<action> 従来は発話行為単位で定義されている。
○<subprotocol> ある一連の行為（プロトコル）単位で定義する。
Postcond: プロトコル実行後の心的状態【００３１】〔２−２−２．プランの例〕ここでは、Precondition(s)とPostcondition(s)のセットを用いてメンタルルールを表す。すなわち、Preconditionはサブプロトコルを実行する前提となるエージェントの心的状態であり、Postconditionはサブプロトコルの終了時のエージェント心的状態を表す。また、Postconditionはサブプロトコルの終り方によって複数存在し得る。また、これらは以下の述語を用いて表現される。
【数２】信念BEL BEL(A,P)：エージェントＡにとってＰは真である。ここで、ＰはエージェントＡの内部形式で表される対象であり、対象は、述語を持っても持たなくてもよい。
【数３】知識KNOW KNOW(A,S)：エージェントＡは命題Ｓの成立を知っている。
【数４】目標WANT WANT(A,S)：エージェントＡは命題Ｓ（あるいは行為）の成立を望んでいる。
【数５】意図INT INT(A,S)：エージェントＡは行為Ｓ（あるいはＳを達成するに至る一連の行為）を実行する意図を持っている。
【００３２】更に、ここで以下の述語を導入する。
【数６】行為Proc PROC(A,M)：エージェントＡはメッセージＭを処理する。
【数７】行為DO DO(A,ACT)：エージェントＡは行為ＡＣＴを実行する。
【００３３】上記述語のより詳細なセマンティクス（意味）定義は、一般的公知例を自由に用いればよい（詳しくは参考文献：FIPA Specification, http://www.fipa.org,2000.を参照）。また、述語の変数（エージェント名や対象）は実行時にバインドされる。サブプロトコル自体の実行手順は各エージェントの内部形式で書かれ、例えばサブプロトコルのＡＵＭＬ表記を用いることも可能である。ここでＡＵＭＬ表記とは、ソフトウェア分析設計用記述言語ＵＭＬを、エージェントの記述用に拡張した表記法である。
【００３４】また、プロトコルの開始側をInitiator、相手側をParticipantとするとき、プロトコルの例として、情報通知(Inform)プロトコル、情報要求(Query-Inform)プロトコル、情報委託(Request-Inform)プロトコルが挙げられる。ここで、情報通知(Inform)プロトコルは、図３に示すように、開始側(Initiator)から相手側(Participant)へ情報を通知するプロトコルである。
【００３５】また、情報要求(Query-Inform)プロトコルは、図４に示すように、InitiatorからParticipantへの情報要求に対し、その場で、Participantから理解不能通知(not-understood)、失敗通知(failure)又は情報通知(inform)を返すプロトコルである。また、情報委託(Request-Inform)プロトコルは、図５に示すように、InitiatorからParticipantへの情報委託(request)に対し、Participantからその場では理解不能通知(not-understood)又は同意通知(agree)を返し、同意の場合はその後Participantから失敗通知(failure)又は情報通知(inform)を返すプロトコルである。
【００３６】例えば、InitiatorをエージェントＡ、ParticipantをエージェントＢとしたときのInformプロトコルに対するエージェントＡ，ＢのPrecond, Postcondを以下に示す。
【数８】Precond(A):BEL(A,X) ∧ KNOW(A,WANT(B,KNOW(B,SB))Postcond(A):KNOW(A,KNOW(B,BEL(A,X))但し、SBはBEL(B,X)または¬BEL(B,X)のいずれかを表す。
【数９】Precond(B):INT(B,KNOW(B,SB))Postcond(B):KNOW(B,SA)但し、SAはBEL(A,X)または¬BEL(A,X)のいずれかを表す。
【００３７】また、Query-Informプロトコルに対するエージェントＡ，ＢのPrecond, Postcondを以下に示す。
【数１０】Precond(A):WANT(A,KNOW(A,SA)) ∧ KNOW(A,INT(B,Proc(B,M)))Postcond(A): informが返された場合KNOW(A,SB)Postcond(A): not-understoodが返された場合KNOW(A,¬Proc(B,M))Postcond(A): failureが返された場合KNOW(A,Proc(B,M)) ∧ ¬KNOW(A,SB)但し、Ｍはquery-if(A,B,X)を表す。
【数１１】Precond(B):INT(B,Proc(B,M))Postcond(B): informを返す場合KNOW(B,KNOW(A,SB))Postcond(B): not-understoodを返す場合KNOW(B,KNOW(A,¬Proc(B,M)))Postcond(B): failureを返す場合KNOW(B,KNOW(A,Proc(B,M))) ∧ KNOW(B,¬KNOW(A,SB))【００３８】また、Request-Informプロトコルに対するエージェントＡ，ＢのPrecond, Postcondを以下に示す。
【数１２】Precond(A):WANT(A,Do(B,ACT)) ∧ KNOW(A,INT(B,Proc(B,M)))Postcond(A): informが返された場合KNOW(A,Done(B,ACT))【００３９】また、Request-Informプロトコルでは、要求した行為の結果を返すことを暗に意図している場合がある。例えば、informメッセージにて結果Ｒが返される場合は以下のように表される。
【数１３】KNOW(A,B(B,R))Postcond(A): not-understoodが返された場合KNOW(A,¬Proc(B,M))Postcond(A): failureが返された場合KNOW(A,Proc(B,M)) ∧ ¬KNOW(A,Done(B,ACT))但し、Mはrequest(A,B,ACT)を表す。
【数１４】Precond(B):INT(B,Proc(B,M))Postcond(B): informを返す場合KNOW(B,KNOW(A,Done(B,ACT)))あるいは、【数１５】KNOW(B,KNOW(A,BEL(B,R))) ∧ BEL(B,R)Postcond(B): not-understoodを返す場合KNOW(B,KNOW(A,¬Proc(B,M)))Postcond(B): failureを返す場合KNOW(B,KNOW(A,Proc(B,M))) ∧ KNOW(B,¬KNOW(A,Done(B,ACT)))【００４０】これらのPrecond, PostcondはＫＱＭＬセマンティクスの組み合わせから導出したものである。ここで、ＫＱＭＬセマンティクスとは、ＡＣＬと同様なエージェント間通信言語として、従来より広く使用されているＫＱＭＬの意味定義である。
【００４１】なお、エージェントのプランには、他のエージェントと協力するためのメンタルルール付きインタラクションプロトコルの他に、そのエージェント固有の処理を表すローカルアクションプランも含まれる。
【００４２】〔２−３．ロールバック時の推論手順〕上記のようなメンタルルール付きプロトコルから選択されるプランにおいて、いずれかのエージェントの不具合に基くロールバック時に、不具合のあったエージェントに関係する処理のみを再実行するための推論手順を以下に説明する。
【００４３】〔２−３−１．推論手順の概要〕まず、メンタルルール付きプロトコルを用いて推論する方法を示す。一般に、複数エージェントがインタラクションを行っているシステムにおいて物理的あるいは論理的な原因からあるエージェントがハングアップしてしまった場合、他のエージェントはなんらかの方法でそのことを知り、全エージェントが初めから処理をやり直す必要がある。あるいは、各エージェントが同期したタイミングでディスクなどに保存してあった状態を呼び出し、その時点から全エージェントが処理を再実行する方法（ロールバック）が用いられる。しかしながら、大規模なマルチエージェントシステムを想定した場合、ある１つのエージェントにおける不具合によって全エージェントが一様にロールバックを強いられることはパフォーマンス的に望ましくない。
【００４４】そこで、ロールバックが必要とされた際に単純再実行ではなく、本実施形態では、不具合のあったエージェントに関係する処理（サブプロトコル）のみを再実行する。このための概念的な動作は、各サブプロトコルに付けられたメンタルルールを参照し、不具合のあったエージェントの信念を実行の前提としていたり、結果としてそのエージェントの信念に影響を与えているルールのみを再実行し、そうでないルールは再実行を行わない、というものである。
【００４５】つまり、この処理は、単にメッセージの宛先で判断するのではなく、内容的に相手を考慮しているものを選択しているもので、いわば、相手に対する信念再確認処理、すなわち信念及び知識データベース１のアップデートと位置付けられる。このために、各エージェントは全状態が保存される所定のロールバック点から次のロールバック点までの間に実行したプランの履歴を逐次保持する。
【００４６】〔２−３−２．具体的な推論手順〕そして、上記のような信念再確認処理の目的は、不具合のあったエージェントＡは現在までの状態を失ってしまうことから、保存されている状態から処理を再実行して不具合発生時直前までの状態を作り直すこと、および、他のエージェントにおけるエージェントＡと関係のある状態を上記再実行にあわせて更新することである。そこで、大まかにはエージェントＡとの直接的なインタラクションは全て再実行する、および、エージェントＡの信念と依存関係のある信念を用いているプランを再実行する必要がある。そこで、プランを再実行する必要のある場合として以下の２つのパターンが挙げられる。
【００４７】〔２−３−２−１．メンタルルール(PrecondおよびPostcond)において相手の信念を参照している場合〕あるプランを実行する際に参照した信念BEL、知識KNOW、目標WANT、意図INTのエージェント名に不具合のあったエージェントが発見された場合は、そのプランを再実行する。このような場合を仮に直接参照と呼ぶものとする。
【００４８】〔２−３−２−２．メンタルルールにおいて相手の信念と依存関係のある自己の信念を参照している場合〕この場合、信念及び知識データベース１に含まれる各エージェントに固有の推論規則には相手（または自己）の信念から自分の信念を推論する規則が存在している。このような場合を仮に間接参照と呼ぶものとする。例えば、以下の推論規則では、【数１６】KNOW(A,BEL(B,X))→BEL(A,X)エージェントＡとエージェントＢは互いに信頼関係があることを前提として、エージェントＡはエージェントＢにとっての事実は（疑わずに）信じることを意味している。そこで、あるプランを実行する際に参照した自己の信念、知識などが他エージェントの信念、知識から推論されたものでないかどうかを判断するため、信念及び知識データベース１を用いて後向きに推論していき、不具合のあったエージェントの信念が発見された場合は、そのプランを再実行する。
【００４９】同様に、プラン・ライブラリ２に含まれる各エージェントに固有のローカルアクションプランには自己（または相手）の信念からある行為を経て他の信念を獲得するプランが存在する。例えば、以下のローカルアクションプランでは、【数１７】Precond: BEL(A,X)<DO(A,"Y=f(X)")>Postcond: BEL(A,Y)エージェントＡは変数Ｘからある計算過程を経て変数Ｙを得ている。ここで、上述した推論規則と組み合わせるとBEL(A,Y)はKNOW(A,BEL(B,X))に帰着し、エージェントＢの信念に依存していることが分かる。このように、ローカルアクションプランにおいても不具合のあったエージェントの信念が発見された場合は、そのプランを再実行する。
【００５０】上記以外の全てのプランに関しては、不具合のあったエージェントと関係しないと判断し、再実行は行わない。
【００５１】〔２−３−３．再実行の手順〕…図６〜８以下では、プランを再実行する必要がある上記２つの場合に関して、推論過程を順を追って説明する。以下では、エージェントＡ，Ｂ，Ｃにおいてメンタルルール付きプロトコルを用いて、インタラクションを実行している状況を想定する。但し、各エージェントは特定の時点で状態（信念及び知識データベース１、意思リスト５、欲求リスト４などを含むスナップショット）を保存し、マシンが落ちる（正常な動作が続行不能となること）などの不具合が発生した場合は自動的にその時点に戻って処理を継続できるものとする。
【００５２】〔２−３−３−１．直接参照の場合〕…図６例えば、あるエージェントにおいてロールバックが発生した場合、そのエージェントは他のエージェントに対して、ロールバックの発生を通知する。そして、以前に保存した状態に戻って処理を再実行する。一方、ロールバックを通知された他のエージェントは、現在の状態を上の再実行にあわせて更新する。
【００５３】例えば、図６において、エージェントＢはquery-informプロトコルの実行中、ないしは実行後だが状態保存はされていない時にマシンと共に落ちたとする。そこでエージェントＢはロールバック点（この例では初期状態）に戻る。そこで、エージェントＢは他エージェントへロールバックの発生をマルチキャストする。
【００５４】ここで、エージェントＢは初期状態としてINT(B,Proc(B,M))およびBEL(B,X)が与えられているものとすると、その後、エージェントＢでは初めに実行した時と同様にquery-informプロトコルのプランのPrecondが適合し、このプランが実行プランとして選択され、具体的にはquery-ifメッセージの受信待ちとなる。
【００５５】一方で、エージェントＡはエージェントＢからのロールバック通知を受信して、ロールバックの必要性を認識する。このときはまだ、エージェントＡは現在の状態を失ってはおらず、また、以前に状態を保存した後に実行したプランのリストを保持している。ここでは保持しているのは、図６で破線の楕円で示すquery-informプロトコルのプランとする。エージェントＡはこのプランのPrecondおよびPostcondを参照し、このプランがエージェントＢの信念を用いていることを発見する（KNOW(A,INT(B,Proc(B,M)))やKNOW(A,BEL(B,X))など）。そこで、直接参照に該当すると判断し、プランの再実行を決定し、具体的にはquery-ifメッセージを送信する。
【００５６】以上がもっとも簡単な信念再確認処理であり、これによりエージェントＢの状態は不具合発生前の状態（ここでは、KNOW(B,KNOW(A,BEL(B,X)))）まで再現される。また、同時にエージェントＡの状態はエージェントＢにあわせて更新される。
【００５７】〔２−３−３−２．間接参照の場合〕…図７例えば、あるエージェントにおいてロールバックが発生した場合、他のエージェントは互いの信念間の依存関係を判断するために、信念及び知識データベース１に含まれる推論規則とプラン・ライブラリ２に含まれるローカルアクションプランのPrecondとPostcondのセットを交換しあう。エージェントがこれらを交換するタイミングは、エージェントシステムが静的な場合、すなわちメンバーが固定で実行時の動的プラン変更なしの場合は、実行前に実行する。また、動的な場合、すなわち実行時にメンバーが決定し、プランの変更ありの場合は、ロールバックが発生が通知された時点で行う。
【００５８】この場合、図７に示すように、エージェントＢは直接参照に該当する場合と同様に、query-informプロトコルにおいてメッセージ待ち状態となる。一方で、エージェントＡのプランリストには、query-informプロトコルのプランの他に、ローカルアクションプランPrecond: BEL(A,X) <DO(A,"Y=f(X)")> Postcond: BEL(A,Y)、informプロトコルのプランが残されている。
【００５９】そこで、エージェントＡはまず上記１に該当する場合と同様にquery-informプロトコルのプランを実行する。次に、ローカルアクションプランを取り出してそのPrecond, Postcondを参照する。ここでは、Precond: BEL(A,X)に関して信念及び知識データベース１を用いて後向きに推論し、推論規則KNOW(A,BEL(B,X))→BEL(A,X)から、このプランがエージェントＢの信念を前提としていることを発見する。そこで、間接参照に該当すると判断し、プランの再実行を行う。
【００６０】更に、informプロトコルのプランを取り出してそのPrecond, Postcondを調べる。このとき、エージェントＡはinformプロトコルのPrecondにB(A,Y)を発見し、上の推論規則とローカルアクションプランから、このプランもエージェントＢの信念を前提としていることを発見する。そこで、同様に間接参照に該当すると判断して、プランの再実行を行う（具体的にはinformメッセージを送信する）。
【００６１】更に、エージェントＣは直接的にはエージェントＢとは会話していないが、informプロトコルのPostcond: KNOW(C,BEL(A,Y))にエージェントＡの信念を発見することができる。そこで、事前に交換したエージェントＡの推論規則を用いて後向きに推論すると、上と同様にエージェントＢの信念が発見されることから、このプランの再実行が必要と判断する。ここでは具体的にはinformメッセージの受信待ちとなる。
【００６２】以上がエージェントの信念間に依存関係がある場合の信念再確認処理であり、これによりエージェントＡのみならずＣの状態もエージェントＢにあわせて更新される。
【００６３】〔２−３−３−３．フローチャート〕以上のような再実行の処理手順は図８のようなフローチャートとしてまとめて示すことができる。この手順では、あるエージェントで不具合が発生すると（ステップ１）、ロールバックにより保存されている状態へ戻るが、保存されている状態がなければ初期状態へ戻る（ステップ２）。続いて、不具合の発生を他のエージェントに通知し（ステップ３）、再実行を開始し（ステップ４）正常処理へ移行する。不具合の発生通知はロールバック通知とも呼ぶ。
【００６４】ロールバック通知を受けた他のエージェントでは、推論規則とローカルアクションプランのPrecond, Postcondのセットを他のエージェントと交換し（ステップ６）、実行したプランのリストにプランが存在すれば（ステップ７）、実行したプランのリストから実行順に１つのプランを取り出し（ステップ８）、プランの再実行の必要性を判断する（ステップ９）。このときは、各プランのPrecond,Postcondをチェックし、（１）直接参照すなわち不具合のあった相手の信念を参照しているか、（２）間接参照すなわち不具合のあった相手の信念と依存関係のある自己の信念を参照している、のいずれかに該当するかどうかを判断する。この間接参照の判断では、自己及び他エージェントの推論規則とローカルアクションプランのPrecond, Postcondを用いて、自己の信念から後ろ向きに推論していき、不具合のあった相手の信念が含意されるかどうかを判断する。
【００６５】以上のような判断の結果、再実行が必要と判断されたプランについて再実行が行われ（ステップ１０）、ステップ７からステップ１０の処理を、実行したプランのリストにプランが存在しなくなるまで（ステップ７）繰り返したうえ、正常処理へ移行する。
【００６６】〔３．効果〕以上説明したように、本実施形態では、メンタルモデルを利用したインタラクションプロトコルの記述形式とそれを基く推論手法を用いることで、まず、メンタルモデルアプローチに比べて、ルールの単位が１アクションから、一連のアクションを含むサブプロトコルになることでル−ル数が減少し、実行時効率が向上する。また、信念等の内部状態に基く条件分岐がアクション単位よりも大きな単位であるサブプロトコル単位となるので、過度の非決定性を減少させることにも役立つ。更に、このアプローチはオークションなどの高度に設計されたプロトコルを、既に立てられているプランと見なして組み合わせていく手法(Planning from Second principles)であるともいえるため、従来のようにプロトコルをプランニングによって生成する場合と比べ、プラニングの煩雑さを回避できる。
【００６７】一方、この実施形態では、メンタルモデルを利用したインタラクションプロトコルの記述形式とそれに基く推論手法を用いることで、プロトコルアプローチに比べて、サブプロトコル単位で宣言的に記述することができる。このため、全ての処理を１つの連続した手続きとして記述する場合に比べて、開発者はサブプロトコル間の接続関係を陽に指定する必要がなくなり、作業負担が軽減されシステムの信頼性も向上する。また、保守は各ルールが正しいかどうかだけによってなされるので、プログラム全体を通してのデバッグより容易である。
【００６８】また、本実施形態では、プロトコルアプローチに対するメリットとして、メンタルモデルに基づく推論機能を用いることにより、あるエージェントで物理的あるいは論理的な原因からロールバックが発生した際に、全てのエージェントが一斉にロールバックしそれまでの全ての処理を再実行するのではなく、不具合の発生したエージェントに関する信念や知識を有するエージェントのみが自らの信念を再確認する。これにより、必要な部分だけが再実行されるので不具合からの立ち直りが早くなると共に、関係のないエージェントは処理を継続できるというメリットがあり、推論が効率化及び安定化される。
【００６９】〔４．他の実施形態〕なお、本発明は、上記実施形態に限定されるものではなく、次に例示するような他の実施形態も含むものである。
【００７０】〔４−１．依存関係の判断について〕エージェント間の信念の依存関係を判断する方法は上述した以外にも考えられる。例えば、サブプロトコル内において自己の信念を相手に伝えるためのメッセージ（例えば、informメッセージ）に、この信念が元来、誰の信念であるかをコメントとして付加して送信することで、信念の依存関係を表す推論規則自体を互いに交換することなく、不具合のあったエージェントとの依存関係を見つけることができる。
【００７１】〔４−２．再実行に関するコミュニケーションについて〕また、上記実施形態においてエージェントは合理的に信念、知識を更新することを前提としており、サブプロトコル実行に必要な心的状態の条件はPrecondに、実行後の変化はPostcondに全て定義されているものとする。したがって、サブプロトコルを実行する両エージェントの信念や知識は必ず他方のエージェントの信念や知識に影響を与えるため、再実行の有無は明示的なコミュニケーションを行わなくとも両エージェントは同じ判断を得ることができるとしている。しかし、両エージェント間で何らかの明示的なコミュニケーションに基づいてプランの再実行を決定してもよい。
【００７２】〔４−３．信念、知識の棄却について〕不具合の発生した例えばエージェントＢの再実行時には、以前のプランのPrecondが満たされなくなり再実行されないプランもでてくる。つまり、処理の流れ自体が変更される場合である。この場合、他のエージェントは、以前に実行したプランが与えた状態（信念及び知識データベース１など）への影響を棄却(Retract)しなくてはならない。そこで、処理の流れが変更されてしまうことが分かった場合、これらのエージェントはこのプラン以降の全プランを対象にPostcondを参照して対象となる信念、知識を棄却する。そして、以降の処理は通常どおり実行する。この場合、つまり、処理の流れが変更される直前にロールバックしたことになる。
【００７３】このような棄却(Retract)にはいくつかの手法が存在するが、例えば以下のようなプランの場合、【数１８】Precond: BEL(A,X) <action> Postcond: BEL(A,Y)信念及び知識データベース１からBEL(A,Y)を消去してしまえばよい。
【００７４】但し、以下のようなプランの場合は、【数１９】Precond: BEL(A,X) <DO(A,"X=X+1")> Postcond: BEL(A,X)BEL(A,X)自体を消去することはできない。そこで、PrecondとPostcondに同じ信念がでてくるものに関しては、実行時に以前の信念(BEL(A,X))を保存しておき、その状態に戻すものとする。
【００７５】〔４−４．時間の概念の導入〕更に、時間の概念を導入することも可能である。本来はあるエージェントＡで不具合が起きた場合でも、エージェントＡに関する全ての信念を更新する必要はなく、実行の度に変更される可能性のある信念（たとえば、時間や実行回数に依存しているもの）のみを更新すればよい。
【００７６】
【発明の効果】以上説明したように、本発明によれば、メンタルモデルを利用したマルチエージェントのインタラクションプロトコルにおいて、一連のプロトコルを単位に事前条件や事後条件を付加することで、少ない負担で効率的かつ安定して推論を行う技術すなわち推論装置及び方法を提供することが可能となる。
【出願人】 【識別番号】０００００３０７８
【氏名又は名称】株式会社東芝
【出願日】 平成１２年９月２９日（２０００．９．２９）
【代理人】 【識別番号】１０００８１９６１
【弁理士】
【氏名又は名称】木内 光春
【公開番号】 特開２００２−１０８６１３（Ｐ２００２−１０８６１３Ａ）
【公開日】 平成１４年４月１２日（２００２．４．１２）
【出願番号】 特願２０００−２９８９４２（Ｐ２０００−２９８９４２）