(57)【特許請求の範囲】
【請求項１】
複数のコンピュータがタスクを遂行するための異なるオプションとなるアクションの相対的な複雑性を評価してコラボレーションさせるコンピュータ実行可能な方法であって、該方法は、コンピュータに対し、
前記タスクを、該タスクの前記コンピュータによって実行される作業の単位であるアクションを指定する順序集合データ構造として、Ａをマルチセットの要素とし、Ｍを順序集合Ｓ内における要素Ａの順序シーケンスを指定する順序関係としてＳ＝（Ａ
，Ｍ）として定義し、前記マルチセットの要素Ａの２つの要素ａｉおよびａｊについて、順序関係Ｍの下に集合Ａ内においてａｉがａｊより前に順序付けされるように、個々のアクションが遂行されるべき順序を指定する順序情報として定義する機能手段と、
前記タスクの前記アクションを遂行するために利用可能な、前記アクションを遂行するための詳細を規定するレシピを、前記アクションに関する前記レシピのサブアクションを指定する順序集合データ構造、および前記サブアクションが遂行されるべき順序を指定する順序情報からなるレシピ・ツリーとしてストアする機能手段と、
前記タスクの前記アクションに関する異なるレシピを使用して前記タスクを遂行することに関連付けされる複雑性の測度を、利用可能なレシピによって指定されるアクションの複雑性の測度に基づいて決定する機能手段であって、前記指定されるアクションの前記複雑性の測度が前記アクションを遂行するために利用可能なレシピの複雑性の測度によって定義され、レシピに関する複雑性の測度が前記レシピの前記サブアクションの複雑性の測度によって定義される機能手段と、
前記レシピによって指定されない基本アクションに関する予め決定済みの複雑性の測度を決定する機能手段と、
別のエージェントによって遂行される請負アクションに関する指定の複雑性の測度を決定する機能手段と、
定義済みタスクをプライマリ・エージェントに、前記プライマリ・エージェントおよび１ないしは複数の請負エージェントのうちの少なくとも１つによる実行のために、付与する機能手段と、
前記複数のコンピュータのうちの１つがアクションを遂行するためのレシピを有していない場合、当該アクションを遂行することのできる他のコンピュータを探し、前記定義済みタスクを、前記タスクについて複雑性のグローバルな測度が最小であると決定された一連のアクションとして実行させることによって遂行する機能手段と、
を実現する方法。
【請求項２】
請求項１に記載の方法をコンピュータに実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、アクションならびにレシピ（ｒｅｃｉｐｅｓ）のコラボレーティブ・プランニングに関する。
【背景技術】
【０００２】
問題解決のための複数のエージェントのコラボレーションは、アクティブ・リサーチの分野である。ここでは、コラボレーションを、複数のエージェントが共有する目的を達成するべく試みる、特別なタイプの調和された活動のこととする。これらのエージェントは、互いに共同して作業し、共有する目的を満たすために必要なタスクもしくは活動を遂行する。
【０００３】
コラボレーティブな行動は、本質において多分に相互依存的であり、言い換えるとその種の行動は、個別の行為の総和を超えるものとなり得る。コラボレーションは、エージェントが相互に掛かり合って合意済みの結果を達成するという意味において、インタラクションおよび単純な調整のいずれからも区別される。コラボレーションは、その後に続いて追加されるのではなく、多分に、生得的に設計されなければならないシステム機構である。
【０００４】
コラボレーションにおいて複数のエージェントが共同して作業し、特定のタスクを達成するとき、これらのエージェントは、それらのタスクを遂行するプランを作成し、最終的にこれらのエージェントは、そのプランを実行する。ソフトウエア・エージェントの関与が期待されるコラボレーティブなタスクは、特定の特質を有する。これらの特質は、次のようにリストすることができる、（ｉ）限定的なリソース（たとえば、時間的制約を含む）、（ｉｉ）アクションの複数レベルの分解、（ｉｉｉ）グループ活動および個別活動の組み合わせ、（ｉｖ）各エージェントの分担に関する部分的な知識、および（ｖ）エージェント間の調整ならびに交渉の必要性。
【０００５】
コラボレーティブなタスク、および全体プロセスにおけるプランニングの重要性の性質を理解するために、次のようなシナリオを考える。あるコンピュータのネットワークが科学計算に使用されている。ネットワーク管理者（ＮＡ）は、このネットワーク内のプロセッサならびにディスクの使用を分析してクラスタの再アレンジを行い、それによってこのネットワークからより良好なパフォーマンスを引き出す必要がある。各ノードには、開いている単一のメンテナンス・ポートがあり、それにおいて、システムの使用に関するクエリを行うことができる。制約は、１つのノードについて、任意の時点で１つのクエリだけが実行できることとする。
【０００６】
この場合においてＮＡは、２つのメンテナンス・エージェント（つまり、ソフトウエア・エージェント）を使用し、それらのエージェントに対し、共同して作業を行い、ネットワーク内の各種のノードにおけるＣＰＵ使用およびディスク使用をレポートすることを命令する。便宜上、以下の例の中で使用されているソフトウエア・エージェントをジャックおよびジルとする。
【０００７】
ジャックおよびジルは共同して、ジャックがネットワークからＣＰＵ使用統計を収集すること、ジルがネットワークからディスク使用統計を収集すること、およびジャックおよびジルが共同してＮＡへ提出する最終レポートを準備することを決定する。これら３つのサブアクション（つまり、（ｉ）ＣＰＵ統計の収集、（ｉｉ）ディスク使用統計の収集、（ｉｉｉ）最終レポートの準備）は、ＮＡによって指定されたアクションを実行するためのハイ・レベルのレシピを構成する。
【０００８】
同じタスクから別のレシピを導くことも可能である。その種の代替レシピとしては、ノードのセットを２つに分けること、およびそれぞれのエージェントが、それぞれのエージェントに付託されたノードのサブセットについてＣＰＵならびにディスク両方のクエリを扱うこと、およびその後それらの結果を結合して提出することが挙げられる。
【０００９】
レシピが確立され、同意されると、ジャックおよびジルは、それぞれ独自の個別プランを作り上げなければならない。ジャックのプランはＣＰＵ統計を収集するためのものであり、ジルのプランはディスク使用統計を収集するためのものである。ジャックおよびジルが互いのプランの完全な詳細を知る必要はないが、それぞれのプランの間において衝突が生じることを避ける必要がある。たとえば、ジャックおよびジルは、両者の旅程が衝突しないように、ノードを訪問するための互いの旅程について交渉しなければならない。したがって、エージェントがそれぞれの個別プランを開発するとき、各エージェントは、ほかのエージェントのプランとの潜在的な衝突を監視し、必要に応じて潜在的に衝突するエージェントと調整を行わなければならない。さらにジャックおよびジルは、第３のアクション、すなわち最終レポートの準備のための共有プランを持つ必要がある。
【００１０】
上に概説したこれらレシピ内の３つのアクションの各々は、そのレシピがさらに分解を必要とするという意味において複合的である。すなわちジャックは、ノードを訪問すること、およびメンテナンス・ポート上において特定のコマンドを実行することを伴う傾向のあるＣＰＵ使用統計のためのレシピを開発しなければならない。同様にジルは、ディスク使用統計を集計するためのレシピを開発しなければならない。その後ジャックおよびジルは、共同して遂行することになるレポートの準備のためのプランを開発し、交渉し、かつ同意しなければならない。このレシピは、それぞれのエージェントが各ノードについて収集したデータをデータベース内へプッシュすること、およびその後、データベース・マネジメント・システムによって提供されるルーチンを使用してこのデータからレポートをフォーマットすることを指定できる。
【００１１】
それに代えて、ジャックおよびジルがレポートの記述ならびにフォーマットにおけるスペシャリストでないことから、ジャックおよびジルは、レポートをフォーマットするアクションを別のエージェント、すなわち便宜上ここで「レポータエージェント（Ｒｅｐｏｒｔｅｒ  Ａｇｅｎｔ）」と呼んでいるエージェントへ請負に出す決定を行うこともできる。「レポータエージェント」は、データベースからデータをフェッチすること（当然ではあるが、ジャックおよびジルが関連する統計をデータベースの異なるテーブル内へプッシュした後）、およびワード・プロセッシング・アプリケーションを使用して適切にフォーマットされたレポートを準備することを請け負う。
【００１２】
このほかにもエージェント‐ベースのコラボレーティブ・プランニング・タスクの各種の具体的な例が存在する。上記の例およびそのほかのこの種の例から、いくつかの重要なポイントを引き出すことができる。第１に、プランはレシピそのものではないということである。レシピは、アクションをどのように遂行するかを指定するにすぎない。したがって、プランニングの間に考慮されなければならない事項としては、（ｉ）エージェントは、そのアクションを遂行するつもりがあるか否か、（ｉｉ）そのエージェントは、そのアクションを遂行する能力があるか否か、（ｉｉｉ）そのエージェントは、そのように信じているか否か、（ｉｖ）そのエージェントは、特定のアクションを請負に出すことを決定しているか否か、（ｖ）そのエージェントの持つ掛かり合いはグループの成功へ向かっているか否か、および（ｖｉ）エージェント間の相互掛かり合いに起因して結果的にもたらされる手段‐目標推論が含まれる。
【００１３】
第２に、各エージェントは自律エンティティである。各エージェントは、特定のレシピ・ライブラリを有し、そのエージェントが遂行できるアクション、および不作為によって、そのエージェントが遂行できないアクションを承知している。中央コントロールまたは調整オーソリティはなく、したがってコラボレーティブなタスクの遂行に要求される機能は、完全に分散されている。
【００１４】
コラボレーティブ・プランニングの形式化は、主としてコラボレーティブな活動に関係するエージェントの『メンタル状態』のモデリングに関係する。これらのメンタル状態の仕様は、エージェントに関する個別ならびに共有のプランを構成する。コラボレーティブ・プランニングの原理の形式化の努力についても、実行能力、グループ活動内のメンバに要求される信頼および意志といったメンタルな態度、個別ならびに共有のプランの仕様を指定することが含まれる。集合論および１次ロジックを使用してプランの形式モデルおよびエージェントのそのほかのメンタル状態を示すことができる。
【００１５】
次に示すリストは、個別ならびにグループのプランの主要コンポーネントを列挙している。これらの原理およびコンポーネントは、形式化の間にモデリングされたエンティティである。
【００１６】
あるアクションのための個別プランを有するためには次のことが必要になる。
（ｉ）レシピの知識、
（ｉｉ）サブアクションを遂行する能力、および
（ｉｉｉ）そのサブアクションを行う意志。
【００１７】
あるアクションのためのグループ・プランを有するためには次のことが必要になる。
（ｉ）レシピの相互信頼、
（ｉｉ）サブアクションのための個別またはグループ・プラン、
（ｉｉｉ）グループがアクションを遂行するという意志、および
（ｉｖ）コラボレーションのメンバが成功するという意志。
【００１８】
上記のプラン（個別またはグループ）の要素をモデリングする形式化は、各種の実際的な応用のためのマルチ‐エージェント・システムを構築する理論的な基礎を提供する。またモデリングは、コラボレーティブ・プランニングの分野における主要な結果の確認ならびに検証の補助となる。
【発明の開示】
【発明が解決しようとする課題】
【００１９】
コラボレーティブ・プランニングにおけるアクションならびに使用されるレシピの複雑性について紹介し、形式化した。現存するコラボレーティブ・プランニングの理論に対する拡張を提供する。呈示したその種の形式化に関連付けされる具体化の問題についても扱う。呈示の形式化は、レシピの選択、アクションの遂行、レシピの交換、およびそのほかのマルチ‐エージェント環境におけるコラボレーティブ・タスクの実行との関係で知的な決定を行うための基礎として使用することができる。
【課題を解決するための手段】
【００２０】
レシピおよびアクションの概念は、集合論を使用して定義される。レシピならびにアクションの複雑性についても定義される。その種の形式化の具体化に求められるデータ構造およびアルゴリズムも取り扱う。この形式化の使用ならびに重要性、および関連付けされる具体化の構造についても検討する。取り扱われる個々の問題を次に示す。
・レシピならびにアクションの複雑性の相互に再帰的な定義、
・請負の場合への定義の拡張、および
・形式化を具体化するためのデータ構造ならびにアルゴリズム。
【００２１】
レシピならびにアクションの複雑性の概念を導入することは、タスクの困難性の測定を提供し、それに基づいて、特定のレシピならびに請負先の使用に関する決定を行うことができる。
【００２２】
さらに、この種の複雑性の測定は、そのほかの、コラボレーティブ・プランニングの各種側面の定量化に関する概念を呈示するための基礎となり得る。たとえば、あるエージェントが特定の複雑性より低いアクションの実行に成功している場合に、そのエージェントの複雑性を扱う能力を測定できる。
【発明を実施するための最良の形態】
【００２３】
ここで説明するテクニックは、コラボレーティブ・プランニングに多様な結果をもたらす。それらには、以下の能力が含まれる。
１．  レシピの形式主義の拡張、
２．  アクションの遂行における代替選択肢の複雑性の測定、
３．  アクションを遂行する複雑性の形式化、
４．  レシピを使用する複雑性の形式化、
５．  開発された形式化を具体化するためのデータ構造ならびにアルゴリズムの開発。
【００２４】
これらの開発は、以下と密接な関係を有する。
１．  交渉の間にレシピに関する同意に到達し、レシピの相互信頼を確立すること、
２．  利用可能な異なる請負オプションの間において決定を行うこと、
３．  利用可能なコラボレーションのオプションの間において決定を行うこと、
４．  時間的な期間にわたってレシピ（もしくはレシピを使用するエージェント）の成功または失敗を示す新しい測定基準を開発すること、
５．  レシピの交換のための基礎を提供すること、したがってエージェントの個別のレシピ・ライブラリの有用性を高めること。
【００２５】
定義および表記
以下の説明においては、「順序集合」のコンセプトが、関連付けされた補助演算とともに導入されている。「順序集合」のコンセプトは、アクションならびにアクションに関するレシピの概念を定義するために使用される。これらの定義および表記は、以下の説明の中で使用されている。
【００２６】
「順序集合（ＳｅｑｕｅｎｃｅｄＳｅｔ）」
「順序集合」は、順序対（Ａ，Ｍ）として定義され、それにおいてＡは要素のマルチセットであり、Ｍは、ＡからＡの要素のシーケンスを指定する自然数の有限サブセットへのマッピングである。
【００２７】
「順序集合」の定義を、次の式（１）に示す。
【００２８】
【数１】
0004608288.tif 000002
【００２９】
ただし、Ｎｋ＝｛１，２，３，．．．，ｋ｝とする。
【００３０】
上記の式（１）の「順序集合」の定義を用いて、記号、
【００３１】
【数２】
0004608288.tif 000003
【００３２】
によって表される順序関係を次の式（２）に定義する。なお、本文中ではこの記号をＯＤＲとして表す。
【００３３】
【数３】
0004608288.tif 000004
【００３４】
上記の式（２）は、関係ａｉ  ＯＤＲ  ａｊが、関係Ｍの下において集合Ａ内の要素ａｊの前に要素ａｉが順序付けされることを含意している旨を確立する。
【００３５】
ｓｕｃｃｅｓｓｏｒ演算子およびｐｒｅｄｅｃｅｓｓｏｒ演算子を式（３）に定義するが、それにおいて記号、
【００３６】
【数４】
0004608288.tif 000005
【００３７】
は『存在しない』を表し、本文中ではこの記号をｎｏｔ∃として表す。
【００３８】
【数５】
0004608288.tif 000006
【００３９】
ここでは、簡潔のために次の「順序集合」Ｓ＝（Ａ，Ｍ）に関する式（４）の中に示されている表記を使用する。
【００４０】
【数６】
0004608288.tif 000007
【００４１】
ただし、各ａｋ∈Ａ、かつ｜Ａ｜＝ｉである。
【００４２】
順序関係Ｍは、要素が書き込まれる順序で捕捉される。下付き文字が使用されている場合には、ｉ＜ｊは、ａｉ  ＯＤＲ  ａｊを含意する。
【００４３】
ヌル「順序集合」を次のように定義する。Ｓ＝（Ａ，Ｍ）を「順序集合」とする。Ａ＝φかつＭ＝φであれば、「順序集合」Ｓはヌルであると言い、Ｓ＝φとして表す。
【００４４】
ここで、「順序集合」に関する２つの演算子を定義する。これらの定義済み演算子は、続くアクションおよびレシピの複雑性の定義の中で使用される。
【００４５】
「順序集合」に関する和演算ｉｎｖΩ
Ｓ１およびＳ２を、次の式（４）で定義される２つの「順序集合」とする。
【００４６】
【数７】
0004608288.tif 000008
【００４７】
「順序集合」に関する和演算は、本文中においてはｉｎｖΩとして表している記号、
【００４８】
【数８】
0004608288.tif 000009
【００４９】
によって表され、その定義を次の式（５）に示す。
【００５０】
【数９】
0004608288.tif 000010
【００５１】
上記の式（５）において、Ｍは、次のように定義される。
【００５２】
【数１０】
0004608288.tif 000011
【００５３】
さらに、次の式（６）に定義される関係も適用する。
【００５４】
【数１１】
0004608288.tif 000012
【００５５】
「順序集合」に関する和演算は可換でない。したがって、Ｓ１  ｉｎｖΩ  Ｓ２≠Ｓ２  ｉｎｖΩ  Ｓ１である。
【００５６】
「順序集合」に関する演算λの下における選択演算ｃｉｒＣ
ここで、Ｓ１およびＳ２を、次の式（７）によって定義される２つの「順序集合」とする。
【００５７】
【数１２】
0004608288.tif 000013
【００５８】
また、λをＡおよびＢの要素について演算可能な任意のバイナリ演算とする。その場合に、本文中においてはｃｉｒＣとして表している記号、
【００５９】
【数１３】
0004608288.tif 000014
【００６０】
によって表される選択演算は、次の表１に示されている擬似コード演算によって定義される。
【００６１】
【表１】
0004608288.tif 000015
【００６２】
Ｓ１＝（Ａ，Ｍ１）かつＳ２＝（Ｂ，Ｍ２）であり、Ａ⊂ＮかつＢ⊂Ｎ（ただし、Ｎは自然数の集合）であるとき、加算（＋）演算の下における演算ｃｉｒＣを次の記号で表し、本文中ではそれをｓｑ＋として表す。
【００６３】
【数１４】
0004608288.tif 000016
【００６４】
次の式（８）に、２つの「順序集合」［５，２，３］および［１，２］についての一例を示す。
【００６５】
【数１５】
0004608288.tif 000017
【００６６】
アクション
アクション∝は、エージェントによって実行される作業の単位である。述語ｂａｓｉｃ．ｌｅｖｅｌ（∝）は、あるエージェントによって追加の詳細なしに∝の遂行が可能である場合に真となる。述語ｂａｓｉｃ．ｌｅｖｅｌ（∝）が偽の場合、つまり‐ｂａｓｉｃ．ｌｅｖｅｌ（∝）が成立する場合には、アクション∝は、暗に複体を意味し、複数のステップからなる。このことはまた、アクション∝が、そのアクションをどのように遂行するかについての詳細を、サブアクションの集合の形で必要としていることを意味する。このサブアクションの集合がレシピと呼ばれる。
【００６７】
エージェントＧは、基本レベルのアクション∝の遂行について、可能または不能のいずれかとなる。このことは、述語Ｅｘｅｃ（∝）の真偽によって示される。アクションが複体である場合には、どのようにそのアクションが遂行されるべきかを指定するレシピをエージェントＧが有していることもあれば、エージェントＧがまったくレシピを有していないこともある。関数ｒｅｃｉｐｅｓ（∝）は、「順序集合」Ｒ∝を返す。次の表２は、「順序集合」Ｒ∝に関係する各種の結果を表している。
【００６８】
【表２】
0004608288.tif 000018
【００６９】
これは、ここで使用している表記に従って、Ｒ∝＝［ｒ１∝，ｒ２∝，．．．，ｒｉ∝］として表すことができる。
【００７０】
エージェントＧがアクション∝を実行するために保持しているレシピの集合が順序付けされる必要がない場合でも、この作業の中では、この種のセットが「順序集合」として表される。このアプローチは、アクションの遂行の複雑性がどのように取り扱われるか、また利用可能な各種の代替レシピの中からどのように選択するかという観点から採用されている。したがって、レシピの選択肢が指定されなければならないことから、任意のアクションに関するレシピは順序付けされなければならない。
【００７１】
最後に、異なる基本レベルのアクションの実行には、異なるコストが伴う。これは、あるエージェントにとって基本レベルのアクションが詳細をまったく必要としないとしても、１つ基本レベルのアクションが別の基本レベルのアクションより相当に複雑（たとえば、処理時間およびメモリに関して）となる可能性はある。関数ｃｏｓｔ（∝）は、そのエージェントによって基本レベルのアクションαが遂行されるコストを示す整数の測度を提供する。
【００７２】
レシピ
前述したように、レシピは、アクションをどのように遂行するかについての詳細である。レシピは、メイン・アクションを成し遂げるために遂行されるサブアクションからなる。サブアクションが特定の順序に従って遂行されることから、レシピは、「順序集合」として定義されなければならない。
【００７３】
したがって、アクション∝のためのレシピｒ∝は、「順序集合」ｒ∝＝（β，δ）であり、それにおいてβはサブアクションの集合、δは順序関係である。ここで使用している表記を用いると、レシピｒ∝は、レシピｒ∝＝［β１，β２，．．．，βｋ］として表すことができる。この中に規定されている順序付け演算子ＯＤＲの定義から、βｉ  ＯＤＲ  βｊは、∝を実行するために、サブアクションβｊの前にサブアクションβｉが行われる必要があることを含意する。これらの、∝に関するレシピ内のサブアクションのそれぞれは、基本または複体のいずれにもなり得る。したがって、これらのサブアクションもまた、それぞれ独自のレシピを有することがある（そのサブアクションが複体の場合）。
【００７４】
以上の説明から、それぞれのアクションは、エージェントが保持しているレシピの「順序集合」に関連付けされ、それぞれのレシピは、サブアクションの「順序集合」に関連付けされる。
【００７５】
図１は、あるエージェントに関するレシピとアクションの間の関係を表している。適用されるべきレシピに関連して行われることになる選択が存在する。
【００７６】
レシピ・ツリーはすべての利用可能な選択肢を捕捉するという意味において、図１は完全なレシピ・ツリーである。この完全なレシピ・ツリー内の各ノードはアクションである。各ノードは、レシピのリストを含んでいる。ノードは、２つの部分を有する。上側半分は、そのノードが表すアクションを含む。下側半分は、そのアクションのために利用可能なレシピのリストを含む。これらのレシピのそれぞれからリンクのセットがサブアクションへ向かって広がっている。第１レベル（∝）１１０は第２レベル（β１〜β８）１２０をもたらし、それもまた第３レベル（χ１〜χ１４）１３０をもたらす。
【００７７】
レシピを成し遂げるために、それに従って遂行されるべきサブアクションが存在する。このレシピから広がる子も順序付けされており、その順序は左から右へ向かっている。最左翼の子は、最初に遂行される必要のあるサブアクションであり、以下その順に従う。このようにして、完全なレシピ・ツリーは、ルート・アクションの各段階において可能なすべての選択肢を捕捉している。各ノードにおいては、レシピに関する選択肢が存在するか、あるいはレシピがまったく存在しない。あるアクションについて、まったくレシピが存在しないとき、考えられるケースは２つある。
【００７８】
アクション∝が基本レベルのアクションであれば、そのアクションについてレシピを指定する必要がない。エージェントは、追加の詳細なしに最初のインスタンスにおいてそのアクションを実行することができる。しかしながら完全性のため、基本レベルのアクション∝に関して定義されるレシピｒ∝は、ヌル「順序集合」とする。つまり、ｒ∝＝φになる。すでに示したヌル「順序集合」の定義によれば、これは、レシピの集合がヌルであり、順序関係もまたヌルであることを意味する。この形式化における厳格さは、後に述べるように、追加のコンセプトならびに表記の好都合な定義を可能にする。
【００７９】
アクションが基本でなく（これは、レシピの必要があることを含意している）、しかもエージェントが、そのレシピ・ライブラリの中にそのアクションに関するレシピを有していない場合には、その「順序集合」ｒｅｃｉｐｅｓ（∝）はヌル「順序集合」になる。したがって、この場合においては、Ｒ∝＝φとなる。このように、ｒｅｃｉｐｅｓ（∝）＝［φ］であるか否か、あるいはｒｅｃｉｐｅｓ（∝）＝φであるか否かによって２つのケースを区別することができる。最初の選択肢は、ｂａｓｉｃ．ｌｅｖｅｌ（∝）の場合は常に真になり、２番目の選択肢は、レシピの知識がないことを表す。
【００８０】
「順序集合」Ｒ∝＝ｒｅｃｉｐｅｓ（∝）は、特定のエージェントによって保持されているレシピを与える。別のエージェントが、同一のアクションの遂行のために異なるレシピを有することはあり得る。同じことが、サブアクションの実行のために必要となることのあるレシピについても当てはまる。
【００８１】
アクションとレシピの複雑性
アクションに関する複雑性の測度は、そのアクションの遂行がどの程度複雑であるかを示す。それぞれの段階におけるレシピに関して選択肢が存在することから、１つのアクションに関連付けされたいくつかの複雑性（そのアクションに関するレシピのすべての複雑性の測度の和）が存在し、各インスタンスは、選択された選択肢の特定の集合を表す。
【００８２】
レシピの複雑性の測度は、意図されたアクションをそのレシピに従って実行する上でそのアクションがどの程度複雑であるかを示す。これは、そのアクションが内包しているサブアクションの複雑性の総計である。アクションならびにレシピの複雑性の測度の定義が、本質的にこの方法で掛かり合うことから、複雑性の測度は、次に述べるようにして相互に再帰的に定義される。
【００８３】
複雑性の基本的な定義
アクションならびにレシピの複雑性の相互に再帰的な定義は、次のように与えられる。アクションの複雑性の定義はレシピの複雑性を使用し、レシピの複雑性の定義はアクションの複雑性の定義を使用する。以下の説明および例においては、これが不完全あるいは無効な定義ではない。
【００８４】
次に示す、Ｃｘ（∝）によって表されるアクション∝の複雑性の定義は、式（９）のとおりである。
【００８５】
【数１６】
0004608288.tif 000019
【００８６】
Ｃｘ（ｒａ）によって表されるレシピｒａの複雑性の形式的な定義は、次の式（１０）のように示される。
【００８７】
【数１７】
0004608288.tif 000020
【００８８】
上記の定義に含まれている記号、
【００８９】
【数１８】
0004608288.tif 000021
【００９０】
は、前述したように、エクスクルーシブ‐オア演算子を表す。アクションの複雑性の定義は、エージェントがそのアクションに関するレシピを含んでいる場合には、そのアクションの複雑性がそれらの複雑性の和（前述のとおり）になるというものである。そのエージェントが、そのアクションに関するレシピをまったく含んでいない場合には、そのアクションの複雑性は無限になる（基本レベルのアクションは、ヌルのレシピを含んでおり、したがって基本レベルのアクションの複雑性は、無限とはならない）。
【００９１】
このレシピの複雑性の定義は、レシピがヌル「順序集合」である（これは実際に、そのレシピの応じるアクションが基本レベルのアクションであることを意味する）場合に、その複雑性が１つの要素を有する「順序集合」であるとして定義され、それがｃｏｓｔ（α）に等しい。しかしながら、レシピがヌル「順序集合」でない場合は、そのレシピがサブアクションのリストを含み、その場合には、そのアクションの複雑性が、それらのサブアクションが遂行される順序に従ってサブアクションのすべての複雑性に対して行われるｓｑ＋によって表される加算の下における選択演算ｃｉｒＣの結果になる。
【００９２】
例
図１に与えられているアクションαの複雑性の計算例を、次の式（１１）を使用して説明する。図１のすべての基本レベルのアクションに関するｃｏｓｔ（ａｃｔｉｏｎ）関数（ａｃｔｉｏｎはアクションを示す値）は、１の値をもたらすと仮定されている。すなわち、この特定の例におけるすべての基本レベルのアクションを遂行するコストは、同一と見なされ、それが１単位である。
【００９３】
【数１９】
0004608288.tif 000022
【００９４】
上記の式（１１）の右辺の各項は、以下の式（１２）、（１３）、および（１４）を使用して計算される。
【００９５】
【数２０】
0004608288.tif 000023
【００９６】
【数２１】
0004608288.tif 000024
【００９７】
【数２２】
0004608288.tif 000025
【００９８】
上記の式（１２）〜（１４）を使用し、次の式（１５）によって表される結果を得る。
【００９９】
【数２３】
0004608288.tif 000026
【０１００】
この式（１５）の結果は、各段階において利用可能な異なるレシピに起因して、６とおりの方法でこのアクションの遂行が可能であることを意味している。これらの選択肢のそれぞれに関する、このアクションを遂行する複雑性もまた決定されている。ここでは、はじめの３つの選択肢が、このアクションの遂行に１２単位の複雑性を要し、残り３つの選択肢が１３単位の複雑性を要する。
【０１０１】
請負の場合
前述の定義においては、エージェントがアクションに関するレシピを有していない場合に、そのアクションを遂行する複雑性が無限になると定義されている。しかしながら、コラボレーティブ・タスクにおいては、エージェントが特定のアクションについて別のエージェントへ請負に出すことが可能なため、この規則を緩和することができる。
【０１０２】
その種の、エージェントがアクションを遂行するためのレシピを有していない場合には、それらのアクションを遂行することのできるエージェントを探すことができる。アクションの請負先となるエージェントは、そのタスクを遂行する複雑性の測度の提供が可能である必要があり、それによって、請負元エージェントが、全体的な複雑性に対するそのアクションの寄与を考慮可能となる必要がある。アクションならびにレシピの複雑性の定義においてこれらの側面をサポートするため、次に追加の関数を定義する。
【０１０３】
関数ｃｏｎｔｒａｃｔｏｒｓ（∝）は、「順序集合」Ｇ∝を返す。Ｇ∝＝ｃｏｎｔｒａｃｔｏｒｓ（∝）は、「順序集合」である。すなわち、Ｇ∝＝（Ｇ，Ｍ）であり、それにおいてＧ∝＝｛ｇ１∝，ｇ２∝，．．．，ｇｍ∝｝である。この場合において『ｍ』は、エージェントＧが実行に関してアクション∝を請負に出すことのできるエージェントの総数であり、Ｍは、集合Ｇ内のエージェントの順序を示す関係である。
【０１０４】
この関係は、先に示した表記と矛盾なくＧ∝＝｛ｇ１∝，ｇ２∝，．．．，ｇｍ∝｝として表すことができる。
【０１０５】
もう１つの関数、すなわちＣＣｘ（ｇ，α）と呼ばれる関数も定義されている。この関数は、要素を１つだけ含む「順序集合」を返す。この要素は、エージェント「ｇ」によって返されるとおりの、アクション∝を遂行するための複雑性の測度（数値）である。つまりこの関数は、別のエージェントとの通信を開始すること、この別のエージェントへ、請負に出されるアクションについての情報を与えること、およびそのアクションを遂行する複雑性についての情報を獲得することを内包する。
【０１０６】
これは、エージェント「ｇ」が返す単一の数値になるが、この数値は、ほかの利用可能な選択肢との組み合わせが可能であることから、「順序集合」として計算される。また、ここで注意する必要があるが、エージェントは、アクションおよびそのサブアクションについて選択するための異なるレシピを有することができるが、アクションを請け負うエージェント「ｇ」は、複雑性として単一の数値だけを提供する。これは、レシピならびにそのほかの選択肢の決定がエージェント「ｇ」によって内部的になされ、そのエージェントが、最良可能（最小の複雑性、様々なファクタを考慮）測度だけを請負元エージェントへ返すことによる。
【０１０７】
この種の複雑性を、ここではブラック‐ボックスの複雑性と呼んでいる。この用語は、『ｇ』にとって内部的に利用可能な選択肢について、またそこで行われる決定について請負元エージェントが知らないことから用いられている。しかしながら請負元エージェントは、そのエージェント自体が遂行するアクションについて、利用可能な選択肢および行うべき決定という意味において熟知している。したがってその種の複雑性を、ここではホワイト‐ボックスの複雑性と呼んでいる。
【０１０８】
請負を考慮し、かつ関数ｃｏｎｔｒａｃｔｏｒｓ（∝）およびＣＣｘ（ｇ，α）を使用すると、アクションならびにレシピの複雑性の定義を次のように拡張することができる。
【０１０９】
Ｃｘ（∝）によって表されるアクション∝の複雑性の形式的定義は、次の式（１６）のとおりとなる。
【０１１０】
【数２４】
0004608288.tif 000027
【０１１１】
Ｃｘ（ｒ∝）によって表されるアクション∝に関するレシピｒ∝の複雑性の形式的定義は、次の式（１７）のとおりとなる。
【０１１２】
【数２５】
0004608288.tif 000028
【０１１３】
請負先が存在する場合には、その請負先がそのアクションに関して呈示した複雑性を考慮に入れる。この請負の概念の導入によって、アクションの複雑性の定義だけが変更される。レシピの複雑性の定義は変更されない。
【０１１４】
アクションの複雑性の定義においては、相互に排他的なケースが４つ存在する。第１のケースは、そのアクションを遂行するためのエージェントを伴うレシピの存在を参照し、かつアクションを請負に出すためのエージェントの存在も参照する。第２のケースは、エージェントに伴うレシピの存在を参照し、かつ請負のためのエージェントの不在を参照する。第３のケースは、請負のためのエージェントの存在を参照するが、そのエージェントに伴うレシピの不在を参照しない。第４のケースは、エージェントならびにレシピの両方の不在を参照する。
【０１１５】
これらのうち、最後のケースのみ、アクションの複雑性が無限になる。そこでこの後は、エージェントがアクションを行うレシピを有している場合であっても、選択肢が請負オプションを含む。これは、エージェントが、このデータを用いて、より情報の豊富な決定を行い得ることによる。たとえば、エージェント自体がアクション（そのエージェントがそれに関するレシピを有している）を遂行する複雑性が、そのアクションを請負に出したときの複雑性よりはるかに大きい場合には、そのアクションを請負に出す決定を行うことができる。
【０１１６】
具体化
アクションならびにレシピの複雑性を決定するための前述した形式化は、相互再帰を使用する。現存のプログラミング言語には、相互再帰を具体化に利用できる直接的なテクニックが存在する。したがって、Ｃ、Ｃ＋＋、あるいはＪａｖａ（Ｒ）といった様々なコンピュータ言語により定義を直接具体化することができる。しかしながら、相互再帰の場合には、関数呼び出しスタックが急速に蓄積される。
【０１１７】
したがって、アクションに関して完全なレシピ・ツリーを構成することは最適ソリューションではない、完全なレシピ・ツリーは、エージェントがそのエージェントのアクションのライブラリ内に保持している各アクションについて構成されるべきである。この概括は、タスクが時間を要することを含意する。つまり、メモリならびにプロセッシング時間の両方の消費に関するその含意から、単純な具体化は特に効率的でないことになる。
【０１１８】
そこで、アクションならびにレシピの複雑性を決定する上で相互再帰を必要としない、より効率的に方法を実現するために使用することのできるデータ構造およびアルゴリズムについて述べる。これを目的として反復テクニックを使用する。さらに、エージェントのライブラリ内におけるアクションならびにレシピの複雑性が計算された後は、増分方法を確立して、そのエージェントのライブラリ内のレシピならびにアクションに対する追加／削除があった場合に複雑性の値を更新することができる。相互再帰は、定義の間は容易性ならびに優雅さを提供するが、このアプローチの具体化は、具体化の間に大量の複雑性を追加する。そのため具体化の間は、反復テクニックが好ましい。
【０１１９】
提示および保存
図２は、各エージェントを包含するツリー配列を表している。各エージェントは、３つの重要な配列を保持する、すなわち、（ｉ）アクション配列２１０、（ｉｉ）レシピ配列２２０、および（ｉｉｉ）請負先配列２３０である。それぞれの配列は、単純に順序付きリストとする。これらの配列２１０〜２３０の間の関係が示されている。これらの関係は、データ・ポイントとして構造化される。
【０１２０】
アクション配列２１０内のすべてのアクションは、レシピ配列２２０内のゼロもしくはそれを超える数のレシピへリンクされている。これらは、このエージェントが、そのアクションを実行するために使用することのできるレシピである。これは、前述の形式化において使用されたｒｅｃｉｐｅｓ（）関数に対応する。それぞれのアクションは、このエージェントがアクションを請負に出すことのできる請負先配列２３０のリストに対してもポイントしている。配列内に維持されているこれらのポインタのリストは、すべて順序付きであり、したがって、「順序集合」データ構造が使用される。
【０１２１】
レシピ配列２２０は、このエージェントが任意の時点において承知しているすべてのレシピを保持している。この配列内の各レシピは、アクションのリストをポイントする。これは、そのレシピが応じているアクションを実行するために遂行を必要とするアクションのリストである。特定のレシピを、１を超える数のアクションのために使用することができる。これにおいても、この配列内の各レシピによってポイントされるアクション配列２１０の集合が順序付けされている。したがって、「順序集合」データ構造が使用される。
【０１２２】
各種の配列の間のリンクを表すために使用されているポインタは双方向である。したがって、あるアクションが、いくつかの使用することのできるレシピを有している場合には、それらのレシピのそれぞれが逆向きにアクションを、すなわちそのアクションのためのレシピとなるアクションをポイントする。同じことがレシピ内に指定されているアクションについても当てはまる。
【０１２３】
各アクション、レシピ、および請負先は、いくつかの属性を有するオブジェクトとしてモデリングすることが可能であり、公に使用可能な関数のリストを提供する。アクションならびにレシピの複雑性に関する具体化を説明するために必要となる属性および関数について次に述べる。
【０１２４】
・配列は、［ｉｎｄｅｘ］表記を使用してインデクスされる（ｉｎｄｅｘはインデクスを示す値）。たとえば、アクション配列のｉ番目のアクションへアクセスする場合には、ａｃｔｉｏｎｓ［ｉ］と記述する。この表記は、「順序集合」に関して前述したものと同じである。
・ａｃｔｉｏｎ．ｂａｓｉｃＬｅｖｅｌ（）関数は、ブール値を返す。この関数は、そのエージェントについてそのアクションが基本レベルのとき真を返す。関数が複体（エージェントが１ステップでアクションを遂行することが不可能であり、したがって、レシピもしくは請負先を必要とすることを意味する）である場合には、この関数が偽を返す。
・ａｃｔｉｏｎ．ｃｏｍｐｌｅｘｉｔｙは、「順序集合」に関して複雑性の値をストアするために使用される属性である。同じことがｒｅｃｉｐｅｓ．ｃｏｍｐｌｅｘｉｔｙに当てはまる。
・ｌｅｎｇｔｈ（ａｒｒａｙ）は、「配列」内の要素の数を返す（ａｒｒａｙは「配列」を示す値）。
・ａｃｔｉｏｎ．ａｃｔｉｏｎＯｆ（）関数は、「アクション」がサブアクションとしてリストされているレシピの配列を返す。
・ａｃｔｉｏｎ．ｒｅｃｉｐｅｓ（）関数は、「アクション」を実行するためにエージェントが保持しているレシピの配列を返す。
・ａｃｔｉｏｎ．ｃｏｎｔｒａｃｔｏｒｓ（）関数は、エージェントが請負に出すことを承知している「アクション」の請負先の配列を返す。
・ｒｅｃｉｐｅ．ａｃｔｉｏｎｓ（）関数は、「レシピ」に従って遂行される必要のあるアクションの配列を返す。
・ｒｅｃｉｐｅ．ｒｅｃｉｐｅＦｏｒ（）関数は、「レシピ」の使用が可能なアクションの配列を返す。
・ａｃｔｉｏｎ．ｕｐｄａｔｅＲｅｑｕｉｒｅｄは、ブール属性であり、複雑性の値の更新がさらに必要であるか否かを示すために使用される。同じことがｒｅｃｉｐｅ．ｕｐｄａｔｅＲｅｑｕｉｒｅｄについても当てはまる。
【０１２５】
アルゴリズム
次に、上記のデータの表現ならびに構造を用いて、アクションならびにレシピの複雑性の計算を、相互再帰に頼ることなく反復方法で行うアルゴリズムについて概説する。このアルゴリズムの擬似コード・リスティングが、図３および図４の２つの部分に示されている。このアルゴリズムを使用する利点について以下に述べる。
【０１２６】
図３および図４に示されているアルゴリズムのコードの多くには、Ｃに類似のシンタクスが使用されている。図５は、このアルゴリズムによって行われるステップを概説したフローチャートである。すべてのアクションならびにレシピの複雑性の測度は、ステップ５０５において無限大に初期化される。このアルゴリズムは、まずステップ５１０において、コスト・ファクタを用いてすべての基本レベルのアクションの複雑性を更新する。
【０１２７】
続いてこのアルゴリズムは、ステップ５１５へ進み、請負に出すことのできるアクションの複雑性を更新する。このアルゴリズムの要点は、すべての複雑性の値が解決されるまでアクションおよびレシピの配列上で連続的に反復が行われるという点である。最初の数回の反復のトレースは、次のようになる。
【０１２８】
複雑性の値を用いて基本レベルのアクションならびに請負アクションが更新されると、レシピ配列に関する反復が行われる。この反復の間はステップ５２０において、基本アクションだけを使用するレシピ、もしくは請負アクションだけを使用するレシピ（エージェントが作業を行わせることができるのであれば、その種のレシピがいくつか存在するはずである）が、それぞれの複雑性の値を用いて更新される。これは、それらのレシピを使用するアクションの複雑性の値における追加の更新をトリガする。その結果、ステップ５２５において、そのアクション配列に対する反復が行われる。このとき、より多くのアクションが解決済みとなることから、レシピのいくつかの処理が可能になる。したがってステップ５２５においては、新たな反復がこのレシピ配列に対して行われる。
【０１２９】
このプロセスが、ステップ５３０において可能なすべてのアクションならびにレシピの複雑性が解決されるまで繰り返される。これらの複雑性の値は、定義に従えば正しい無限として残されたまま解決されることがあり得ない。このエージェントの保持しているアクションならびにレシピの現在の集合について複雑性に関する計算が完了した後は、ライブラリに対する新しい追加もしくは削除が増分方法で扱われる。つまり、新しいアクションが追加されると、対応するレシピのｕｐｄａｔｅＲｅｑｕｉｒｅｄフィールドがステップ５３５において変更される。ｗｈｉｌｅループ（ｗｈｉｌｅ（！ｂｏｔｈＤｏｎｅ））が再び実行されて、新しい複雑性の値を用いたライブラリの更新が行われる。このようにして、最小必要計算だけが行われる。
【０１３０】
これらの反復の間に使用される演算は、上記の『定義および表記』のタイトルを付したサブセクションに定義されている「順序集合」の演算である。このプロシージャは、相互再帰を介した直接の具体化の場合には完全に正当とならないが、必要とされる計算だけを行う。したがって、冗長な計算はまったく行われない。また、ツリーの構築もなく、計算がインラインで実行され、そのため必要なメモリ要件が軽減される。
【０１３１】
コンピュータ・ハードウエアおよびソフトウエア
図６は、ここで説明したようなタスクを行うための各種のオプションの相対的な複雑性を評価するためのテクニックの具体化に使用することのできるコンピュータ・システム６００を示した概略図である。コンピュータ・システム６００上にインストールされた適切なオペレーティング・システムの下にコンピュータ・ソフトウエアが実行されて、ここで説明したテクニックの遂行を援助する。このコンピュータ・ソフトウエアは、任意の適切なコンピュータ・プログラミング言語を使用してプログラムされ、特定のステップを達成するための多様なソフトウエア・コード手段を包含しているものと考えることができる。
【０１３２】
コンピュータ・システム６００のコンポーネントには、コンピュータ６２０、キーボード６１０ならびにマウス６１５、およびビデオ・ディスプレイ６９０が含まれる。コンピュータ６２０は、プロセッサ６４０、メモリ６５０、入力／出力（Ｉ／Ｏ）インターフェース６６０、６６５、ビデオ・インターフェース６４５、およびストレージ・デバイス６５５を含んでいる。
【０１３３】
プロセッサ６４０は、中央処理ユニット（ＣＰＵ）であり、オペレーティング・システムならびにオペレーティング・システムの下に実行されるコンピュータ・ソフトウエアを実行する。メモリ６５０は、部分的にはロジック・エレメントとして機能するランダム・アクセス・メモリ（ＲＡＭ）、および読み出し専用メモリ（ＲＯＭ）を含み、プロセッサ６４０の管理の下に使用される。
【０１３４】
ビデオ・インターフェース６４５は、ビデオ・ディスプレイ６９０へ接続され、ビデオ・ディスプレイ６９０上に表示するためのビデオ信号を提供する。コンピュータ６２０を操作するユーザ入力は、キーボード６１０ならびにマウス６１５から提供される。ストレージ・デバイス６５５は、ディスク・ドライブもしくはそのほかの任意の適切なストレージ・メディアを含むことができる。
【０１３５】
コンピュータ６２０内のそれぞれのコンポーネントは、データ・バス、アドレス・バス、およびコントロール・バスを含む内部バス６３０へ接続されており、コンピュータ６２０のコンポーネントが内部バス６３０を介して互いに通信することを可能にする。
【０１３６】
コンピュータ・システム６００は、入力／出力（Ｉ／Ｏ）インターフェース６６５を介し、インターネット６８０として表されているネットワークへの通信チャンネル６８５を使用して、１ないしは複数の、ほかの類似のコンピュータへ接続することができる。
【０１３７】
コンピュータ・ソフトウエアは、ポータブル・ストレージ・メディア上に記録されることもあり、その場合にコンピュータ・ソフトウエア・プログラムは、コンピュータ・システム６００によってストレージ・デバイス６５５からアクセスされる。それに代えてコンピュータ・ソフトウエアを、コンピュータ６２０によってインターネット６８０から直接的にアクセスされるようにすることも可能である。いずれの場合でもユーザは、キーボード６１０ならびにマウス６１５を使用してコンピュータ・システム６００とインタラクションを行い、コンピュータ６２０上において実行されているプログラム済みのコンピュータ・ソフトウエアを操作することができる。
【０１３８】
このほかの構成もしくはタイプのコンピュータ・システムについても、ここで述べたテクニックの具体化に等しく使用することができる。上記のコンピュータ・システム６００は、ここで説明したテクニックの具体化に適したタイプのシステムの一例として述べられているに過ぎない。
【０１３９】
結論
本発明は、コンピュータ科学において、一例を挙げればネットワークされたコンピュータ・システムの管理ならびに使用において一般的な応用を有する。ここで述べたテクニックならびに構成については、当業者が認識されるように、各種の変更および修正が可能である。
【図面の簡単な説明】
【０１４０】
【図１】任意のアクションαに関するレシピ・ツリーを示した概略図である。
【図２】エージェントに関するアクション、レシピ、および請負先のライブラリを示した概略図である。
【図３】アクションならびにレシピの複雑性の反復計算に使用されるアルゴリズム・コードの最初の部分を示した説明図である。
【図４】アクションならびにレシピの複雑性の反復計算に使用されるアルゴリズム・コードの２番目の部分を示した説明図である。
【図５】アクションならびにレシピの複雑性の反復計算に使用される図３および図４のアルゴリズム・コードを使用して示した、アルゴリズムを要約するフローチャートである。
【図６】図１〜５を参照して説明したテクニックを実施する上で適したコンピュータ・システムを示した概略図である。
【符号の説明】
【０１４１】
１１０  第１レベル（∝）
１２０  第２レベル（β１〜β８）
１３０  第３レベル（χ１〜χ１４）
２１０  アクション配列
２２０  レシピ配列
２３０  請負先配列
６００  コンピュータ・システム
６１０  キーボード
６１５  マウス
６２０  コンピュータ
６３０  内部バス
６４０  プロセッサ
６４５  ビデオ・インターフェース
６５０  メモリ
６５５  ストレージ・デバイス
６６０  入力／出力（Ｉ／Ｏ）インターフェース
６６５  入力／出力（Ｉ／Ｏ）インターフェース
６８０  インターネット
６８５  通信チャンネル
６９０  ビデオ・ディスプレイ
【図１】
0004608288.tif 000029
【図２】
0004608288.tif 000030
【図３】
0004608288.tif 000031
【図４】
0004608288.tif 000032
【図５】
0004608288.tif 000033
【図６】
0004608288.tif 000034