(57)【特許請求の範囲】
【請求項１】
コンピュータープロセス（以後、エージェント（ａｇｅｎｔ）と称する）によって代表されるそれぞれのエンティティ（ｅｎｔｉｔｙ）を有する分散システムに於いて、複数の当該エンティティ間に於ける一つのアクティビティ（ａｃｔｉｖｉｔｙ）を確立する方法であって、当該複数のエンティティに対するそれぞれのエージェントは、当該分散システムにおいて実行可能な操作（ｏｐｅｒａｔｉｏｎ）を含む提案（ｐｒｏｐｏｓａｌｓ）を発生させ、次いで、当該発生された提案を当該複数のエンティティに対する他のエージェントに送信し、そして、当該複数のエンティティに対する他のエージェントから提案を受信すると共に当該受信した提案がそのエージェントにとって受入可能であるか受入不可能であるかを、木構造（ｔｒｅｅ−ｓｔｒｕｃｔｕｒｅ、以後目標序列（ｇｏａｌ  ｈｉｅｒａｒｃｈｙ）と言う）を調査する事によって決定する為に配置されており、且つ当該木構造に於けるそれぞれのノード部は、受入可能か、受入不可能か、或いはその何れにも決定できないと言う様にマークされているそれぞれの操作についての詳細を含んでいる様に構成されている当該方法に於いて、
当該方法は、
当該複数のエンティティを代表する複数のエージェント間で、当該複数のエンティティを代表する全てのエージェントが、当該アクティビティを確立する為のある特定の提案が、受け入れられるか、或いは如何なる同意にも到達出来なかったと言うことを決定するまで、幾つかの提案を交換し合う工程、及び当該複数のエンティティを代表する全てのエージェントが当該特定の提案が受け入れ可能であると決定する場合には、当該分散システムに於いて、当該アクティビティを確立する為に当該特定の提案に含まれる操作を実行する工程を含んでおり、
更に当該方法は、
当該一つのエージェントが、当該受信した提案が受け入れ可能でないと決定した後に、当該エージェントは、交換可能な提案(以後、逆提案と言う)を得るために、受信した当該提案が受け入れ不可能であると決定する為に使用されたノード部からスタートして、当該提案を受入可能か受入不可能かの何れにも決定できないノード部を見つける為に、当該枝部に沿って上昇する方向に調査し、その後、受入可能であるとマークされている操作についての詳細を含んでいるノード部を見つけるために他の枝部に沿って下降する方向に調査する事により、当該目標序列を調査する工程、及び
当該逆提案としての当該操作についての詳細を他のエージェントに送信する工程、
とを実行する事を特徴とする複数のエンティティ間に於ける一つのアクティビティを確立する方法。
【請求項２】
当該提案が、仲介的なコンピュータープロセス（以後、折衝者と称する）の使用を介して当該エージェント間で交換される請求項１の方法。
【請求項３】
当該提案が当該エージェント間で直接交換される請求項１の方法。
【請求項４】
当該エージェントの全てが同じ目標序列を利用する請求項１の方法。
【請求項５】
当該エージェントが異なる目標序列を利用する請求項１の方法。
【請求項６】
当該分散システムが通信ネットワークであり、そして当該アクティビティが通信ネットワーク内における２又はそれ以上のエンティティ間の通信を設定する工程を含んでいることを特徴とする請求項１記載の方法。
【請求項７】
分散システム内の複数のエンティティ間で、一つのアクティビティを確立する為の請求項１乃至６の何れかに記載されている分散システムであって、当該分散システムは、更に複数のエージェントのそれぞれを実行する為のコンピューター手段（４０）及び当該複数のエージェントのそれぞれに関する目標序列を記憶している記憶手段（４２）とを含んでおり、且つ当該コンピューター手段は、当該逆提案に関して当該目標序列を調査し且つ当該逆提案を他のエージェントに送信する様に構成されている事を特徴とする分散システム。
【発明の詳細な説明】
技術分野
本発明は、請求範囲第１項の前提部分に従った工程を含むエージェントにより代表される各々のエンティティ（ｅｎｔｉｔｙ）との分散システムにおける１又は複数の当該構成要素における活動を設立する方法に関する。分散システムは、自主的な独立した又はともに開発したシステム又は互いに相互に作用できるコンピュータプログラムのコレクションからなる。これらの分散システムの例は、通信ネットワーク、分散データベースシステム及びコンピュータ支持協調ワークである。本発明では、折衝メカニズムは、構成要素間の競合を解消するのに使用される。本発明によれば、分散システム例えば通信ネットワーク（例えば加入者、資源（ｒｅｓｏｕｒｃｅ）提供者、情報提供者）又は分散データベースシステムにおけるそれぞれのエンティティは、エージェントとして知られているコンピュータプロセスにより折衝において示される。エージェントの機能は、他のエージェントへの伝送のために分散システムにおいて或るアクティビティの効率の提案（ｐｒｏｐｏｓａｌ）を発生させ、他のエージェントから受け取られる提案が受け入れ可能かどうかを決定し、そしてもし必要ならば逆提案を発生させることである。それぞれのエージェントは、提案及び逆提案を発生させ、そして他のエージェントから受け取られる提案を受け入ることができるかどうかを決定するために目標序列（ｇｏａｌ  ｈｉｅｒａｒｃｈｙ）を使用する。
背景技術
通信ネットワークにおける競合
分散システム例えば通信ネットワークにおいて少なくとも３種の競合が生ずる。一つは、通信ネットワークにおける使用者が、それらの中で確立される特別な形の通信セッションに同意しないことである。例えば、パーティＡは、リストされていない番号を有するが、一方パーティＢは、任意の呼び出しを受け入れる前に呼び出しパーティの番号を知ることを望むことがある。パーティＡがパーティＢを呼び出すとき、競合が生ずる。この種類の競合は、それがいかに通信セッションが確立されるかについての不同意を含むという理由から、セッション競合と呼ばれる。セッション競合の他の例は、通信セッションへのパーティＡが第三のパーティＣを含むことを望むが、通信セッションへの第二のパーティＢが第三のパーティを含むことを望まない場合である。一般に、セッション競合は、通信を確立するかどうか又は通信の性質が何であるだろうかについての不同意を含む。
第二の種類の競合は、ネットワークの外部の資源の使用について生ずる。例えば、もし通信使用者Ａが家庭におりそして使用者ＢがＡの家庭を訪問しているならば、Ｂの家庭からＡの家庭へもたらされる呼び出しは、Ａへの呼び出しによる資源のそれらの使用で競合する。この種類の競合は、それが使用者のステーションでの装置を含むということから、ステーション競合と呼ばれる。
第三の種類の競合は、希少ネットワーク資源の使用を含む。例えば、会議の呼び出しは、マルチプルの資源から単一の信号へ信号を組み合わすブリッジと呼ばれる特別な装置を必要とする。もし余りに多くの会議の呼び出しが同時に企てられるならば、ネットワークは、それらに十分なブリッジを提供できないだろう。この種類の競合は、資源競合と呼ばれる。或るセッション競合及びステーション競合は、機能相互作用と呼ばれるものの結果として生ずる。機能競合は、通信ネットワークにおける一つの機能が、他の機能の予想された操作と干渉するとき、生ずる。
協調システム中の折衝
通信ネットワークで生ずる上記の競合は、どのアクティビティが行われているかについて分散システムが経験する競合のタイプの例である。これらの競合は、分散システムの個々の構成要素が異なる情報に基づいてそれらの決定を行うため、又はそれらが異なる目標を達成しようと試みるために、それらが互いに適合しない決定を下すので、発生する。競合を解消するために、分散システムの個々の構成要素は、互いに作用し、情報を交換し、そして恐らくそれら自身の目標を変え又は他のシステムの目標を変えようと試みる必要がある。生ずる相互作用は、折衝プロセスを構成する。或る折衝メカニズムでは、エンティティは、エージェントにより代表される。ここで使用されるとき、用語エージェントは、折衝において対応するエンティティを代表するコンピュータプロセスに関する。
概して、一つのエージェントは、それが達成しようと試みる目標、並びに受け入れ可能な目標を達成するための別のプランについての情報を他のエージェントに送る。この情報は、それから他のエージェントが、それについて受け入れ可能なものを取り出す提案のコレクションを形成する。或る折衝領域では、折衝の目的を形成する提案及び逆提案は、（数的）属性の固定されたセットにより表すことができる。これらの場合では、提案の評価及び逆提案の発生は、これらの属性の機能の比較的簡単な組み合わせにより実行できる。これらの領域の例は、新車の価格及び機能に関する折衝及び会合をスケジュールするための折衝である。折衝エージェントは、折衝の目的がこれらの属性の固定されたセットにより表すことのできない領域で使用される。これらの領域では、逆提案は、それが応答する提案に存在する同じ属性の異なる価を含むばかりか、全く異なる属性を含むことができる。潜在的に、逆提案における挿入のために選択される多くの属性が存在する。しかし、それらの或るもののみが、ヒトの観察者にとり関連する又は「意味がある」ように思われるだろう。折衝エージェントの使用を含む本発明の折衝方法は、ＤＡＩ（分散人工知能）における折衝のための現在の技術に以下のものをこれらの領域において加えるものである。
・提案を評価する方法（受け入れ可能性又は受け入れ不可能性を決める）
・受け取った提案が受け入れ不可能なとき何が「意味のある」逆提案であるかを決める方法
非常に種々の折衝プロセスが、分散人工知能に関して従来技術において開示されてきた。例えば、Ｓ．Ｃａｍｍａｒａｔａ、Ｄ．ＭａｃＡｒｔｈｕｒ及びＲ．Ｓｔｅｅｂ「Ｓｔｒａｔｅｇｉｅｓ  ｏｆ  Ｃｏｏｐｅｒａｔｉｏｎ  ｉｎ  Ｄｉｓｔｒｉｂｕｔｅｄ  Ｐｒｏｂｌｅｍ  Ｓｏｌｖｉｎｇ」Ｉｎ  Ｐｒｏｃｅｅｄｉｎｇｓ  ＩＪＣＡＩ−８３、７６７及び７７０ページ、Ｋａｒｌｓｒｕｈｅ、１９８３；Ｒ．Ｃｌａｒｋ、Ｃ．Ｇｒｏｓｓｎｅｒ及びＴ．Ｒａｄｈａｋｒｉｓｈｎａｎ「Ｃｏｎｓｅｎｓｕｓ：Ａ  Ｐｌａｎｎｉｎｇ  Ｐｒｏｔｏｃｏｌ  ｆｏｒ  Ｃｏｏｐｅｒａｔｉｎｇ  Ｅｘｐｅｒｔ  Ｓｙｓｔｅｍｓ」Ｉｎ  Ｐｒｏｃｅｅｄｉｎｇｓ  １１ｔｈ  Ｗｏｒｋｓｈｏｐ  ｏｎ  Ｄｉｓｔｒｉｂｕｔｅｄ  Ａｒｔｆｉｃｉａｌ  Ｉｎｔｅｌｌｉｇｅｎｃｅ、４３及び５８ページ、Ｇｌｅｎ  Ａｒｂｏｒ、ＭＩ、Ｆｅｂｒｕａｒｙ、１９９２；Ｓ．Ｅ．Ｃｏｎｒｙ、Ｋ．Ｋｕｗａｂａｒａ、Ｖ．Ｒ．Ｌｅｓｓｅｒ及びＲ．Ａ．Ｍｅｙｅｒ「Ｍｕｌｔｉｓｔａｇｅ  Ｎｅｇｏｔｉａｔｉｏｎ  ｆｏｒ  Ｄｉｓｔｒｉｂｕｔｅｄ  Ｃｏｎｓｔｒａｉｎｔ  Ｓａｔｉｓｆａｃｔｉｏｎ」ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｓｙｓｔｅｍｓ、Ｍａｎ  ａｎｄ  Ｃｙｂｅｒｎｅｔｉｃ、２１（６）：１４６２−１４７７、Ｎｏｖｅｍｂｅｒ／Ｄｅｃｅｍｂｅｒ  １９９１；Ｒ．Ｄａｖｉｓ及びＲ．Ｇ．Ｓｍｉｔｈ「Ｎｅｇｏｔｉａｔｉｏｎ  ａｓ  ａ  Ｍｅｔａｐｈｏｒ  ｆｏｒ  Ｄｉｓｔｒｉｂｕｔｅｄ  Ｐｒｏｂｌｅｍ  Ｓｏｌｖｉｎｇ」Ａｒｔｉｆｉｃｉａｌ  Ｉｎｔｅｌｌｉｇｅｎｃｅ、２０：６３  １０９、１９８３；Ｅ．ＩＩ．Ｄｕｒｆｅｅ及びＶ．Ｒ．Ｌｅｓｓｅｒ「Ｎｅｇｏｔｉａｔｉｏｎ  Ｔａｓｋ  Ｄｅｃｏｍｐｏｓｉｔｉｏｎ  ａｎｄ  Ａｌｌｏｃａｔｉｎｇ  Ｕｓｉｎｇ  Ｐａｒｔｉａｌ  Ｇｌｏｂａｌ  Ｐｌａｎｎｉｎｇ」１０章、２２９−２４３ページ、Ｐｉｔｍａｎ、ロンドン、１９８９；Ｓ．Ｋｒａｕｓ、Ｅ．Ｅｐｈｒａｔｉ及びＤ．Ｌｅｈｍａｎｎ「Ｎｅｇｏｔｉａｔｉｏｎ  ｉｎ  ａ  Ｎｏｎ−ｃｏｏｐｅｔａｔｉｖｅ  Ｅｎｖｉｒｏｎｍｅｎｔ」Ｊｏｕｒｎａｌ  ｏｆ  Ｅｘｐｅｒｉｍｅｎｔａｌ  ａｎｄ  Ｔｈｅｏｒｅｔｉｃａｌ  Ａｒｔｉｆｉｃｉａｌ  Ｉｎｔｅｌｌｉｇｅｎｃｅ、１：２５５−２８１、１９９１；Ａ．Ｓａｔｈｉ及びＭ．Ｓ．Ｆｏｘ「Ｃｏｎｓｔｒａｉｎｔ−ｄｉｒｅｃｔｅｄ  Ｎｅｇｏｔｉａｔｉｏｎ  ｏｆ  Ｒｅｓｏｕｒｃｅ  Ｒｅａｌ  ｌｏｃａｔｉｏｎ」Ｌ．Ｇａｓｓｅｒ及びＭ．Ｎ．ＩＩｕｈｎｓ編「Ｄｉｓｔｒｉｂｕｔｅｄ  Ａｒｔｉｆｉｃｉａｌ  Ｉｎｔｅｌｌｉｇｅｎｃｅ、ＩＩ巻」Ｒｅｓｅａｒｃｈ  Ｎｏｔｅｓ  ｉｎ  Ａｒｔｉｆｉｃｉａｌ  Ｉｎｔｅｌｌｉｇｅｎｃｅ、８章、１６３−１９３ページ、Ｐｉｔｍａｎ、ロンドン；Ｓ．Ｓｅｎ及びＥ．Ｈ．Ｄｕｒｆｅｅ「Ａ  Ｆｏｒｍａｌ  Ａｎａｌｙｓｉｓ  ｏｆ  Ｃｏｍｍｕｎｉｃａｔｉｏｎ  ａｎｄ  Ｃｏｍｍｉｔｍｅｎｔ  ｉｎ  Ｄｉｓｔｒｉｂｕｔｅｄ  Ｍｅｅｔｉｎｇ  Ｓｃｈｅｄｕｌｉｎｇ」Ｉｎ  Ｐｒｏｃｅｅｄｉｎｇｓ  １１ｔｈ  Ｗｏｒｋｓｈｏｐ  ｏｎ  Ｄｉｓｔｒｉｂｕｔｅｄ  Ａｒｔｉｆｉｃｉａｌ  Ｉｎｔｅｌｌｉｇｅｎｃｅ、３３３−３４４ペ−ジ、Ｇｌｅｎ  Ａｒｂｏｒ、ＭＩ、Ｆｅｂｒｕａｒｙ  １９９２；Ｋ．Ｐ．Ｓｙｃａｒａ「Ａｒｇｕｍｅｎｔａｔｉｏｎ：Ｐｌａｎｎｉｎｇ  Ｏｔｈｅｒ  Ａｇｅｎｔｓ’Ｐｌａｎｓ」Ｉｎ  Ｐｒｏｃｅｅｄｉｎｇｓ  ＩＪＣＡＩ−８９、５１７及び５２３ペ−ジ、Ｄｅｔｒｏｉｔ、ＭＩ、１９８９；Ｆ．ｖｏｎ  Ｍａｒｔｉａｌ「Ｃｏｏｒｄｉｎａｔｉｏｎ  ｂｙ  Ｎｅｇｏｔｉａｔｉｏｎ  Ｂａｓｅｄ  ｏｎ  ａ  Ｃｏｎｎｅｃｔｉｏｎ  ｏｆ  Ｄｉａｌｏｇｕｅ  Ｓｔａｔｅｓ  Ｗｉｔｈ  Ａｃｔｉｏｎｓ」Ｉｎ  Ｐｒｏｃｅｅｄｉｎｇｓ  １１ｔｈ  Ｗｏｒｋｓｈｏｐ  ｏｎ  Ｄｉｓｔｒｉｂｕｔｅｄ  Ａｒｔｉｆｉｃｉａｌ  Ｉｎｔｅｌｌｉｇｅｎｃｅ、２２７−２４６ペ−ジ、Ｇｌｅｎ  Ａｒｂｏｒ、ＭＩ、Ｆｅｂｒｕａｒｙ  １９９２；Ｒ．Ｗｅｉｈｍａｙｅｒ及びＲ．Ｂｒａｎｄａｕ「Ａ  Ｄｉｓｔｒｉｂｕｔｅｄ  ＡＩ  Ａｒｃｈｉｔｅｃｔｕｒｅ  ｆｏｒ  Ｃｕｓｔｏｍｅｒ  Ｎｅｔｗｏｒｋ  Ｃｏｎｔｒｏｌ」Ｉｎ  Ｐｒｏｃｅｅｄｉｎｇｓ  ＩＥＥＥ  Ｇｌｏｂａｌ  Ｔｅｌｅｃｏｍｍｕｎｉｃａｔｉｏｎｓ  Ｃｏｎｆｅｒｅｎｃｅ（ＧＬＯＢＥ−ＣＯＭ  ’９０）６５６及び６６２ペ−ジ、Ｓａｎ  Ｄｉｅｇｏ、ＣＡ、１９９２；Ｇ．Ｚｌｏｔｋｉｎ及びＪ．Ｓ．Ｒｏｓｅｎｓｃｈｅｉｎ「Ｃｏｏｐｅｒａｔｉｏｎ  ａｎｄ  Ｃｏｎｆｌｉｃｔ  Ｒｅｓｏｌｕｔｉｏｎ  Ｖｉａ  Ｎｅｇｏｔｉａｔｉｏｎ  Ａｍｏｎｇ  Ａｕｔｏｎｏｍｏｕｓ  Ａｇｅｎｔｓ  ｉｎ  Ｎｏｎ−ｃｏｏｐｅｒａｔｉｖｅ  Ｄｏｍａｉｎｓ」ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｓｙｓｔｅｍｓ、Ｍａｎ  ａｎｄ  Ｃｙｂｅｒｎｅｔｉｃ、２１（６）：１３１７−１３２４、Ｎｏｖｅｍｂｅｒ／Ｄｅｃｅｍｂｅｒ  １９９１参照。
折衝メカニズムの二三は、目標の序列表示並びにこれらの目標を達成するための別のやり方に基づく。目標の序列は、全ての関係のあるエージェントの目標を達成するが競合作業を含まないプランを見つけるのに使用される。Ｒ．Ｃｌａｒｋ、Ｃ．Ｇｒｏｓｓｎｅｒ及びＴ．Ｒａｄｈａｋｉｓｈｎａｎ「Ｃｏｎｓｅｎｓｕｓ：Ａ  Ｐｌａｎｎｉｎｇ  Ｐｒｏｔｏｃｏｌ  ｆｏｒ  Ｃｏｏｐｅｒａｔｉｎｇ  Ｅｘｐｅｒｔ  Ｓｙｓｔｅｍｓ」Ｉｎ  Ｐｒｏｃｅｅｄｉｎｇｓ  １１ｔｈ  Ｗｏｒｋｓｈｏｐ  ｏｎ  Ｄｉｓｔｒｉｂｕｔｅｄ  Ａｒｔｉｆｉｃｉａｌ  Ｉｎｔｅｌｌｉｇｅｎｃｅ、４３及び５８ペ−ジ、Ｇｌｅｎ  Ａｒｂｏｒ、ＭＩ、Ｆｅｂｒｕａｒｙ  １９９２における序列は、ノードが目標であるＡＮＤ／ＯＲ／ＸＯＲ木である。提案として目標の仕様
0003716995.tif 000002
を使用するよりも、特定の序列の全体が提案として使用される。このアプローチは、本発明におけるよりもエージェントの目標及びオプションに関するそれぞれの提案においてさらに情報を無条件に開示することを含む。しかし、プロトコールは、固定且つ制限された数の段階において妥協することに決定してしまうだろう。マルチステージ折衝プロトコール（Ｓ．Ｅ．Ｃｏｎｒｙ、Ｋ．Ｋｕｗａｂａｒａ、Ｖ．Ｒ．Ｌｅｓｓｅｒ及びＲ．Ａ．Ｍｅｙｅｒ「Ｍｕｌｔｉｓｔａｇｅ  Ｎｅｇｏｔｉａｔｉｏｎ  ｆｏｒ  Ｄｉｓｔｒｉｂｕｔｅｄ  Ｃｏｎｓｔｒａｉｎｔ  Ｓａｔｉｓｆａｃｔｉｏｎ」ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｓｙｓｔｅｍｓ、Ｍａｎ  ａｎｄ  Ｃｙｂｅｒｎｅｔｉｃ、２１（６）：１４６２−１４７７、Ｎｏｖｅｍｂｅｒ／Ｄｅｃｅｍｂｅｒ  １９９１参照）では、序列で組織化されるプランの断片のコレクションは、提案として使用される。提案を受け取る他のエージェントは、提案から好適なプランの断片を選択するか又はどんな受け入れ可能なプラン断片も提案に含まれなかったという通告を送るかの何れかを行う。序列は、他のエージェントの目標について考慮するのに使用されず、そして目標は、全てのエージェントにより共有されるグローバルな目標からどんな場合でも由来する。そのため、アプローチは、自律的なエージェントの環境よりも分散問題解決システムに一層適している。Ｋ．Ｐ．Ｓｙｃａｒａ「Ａｒｇｕｍｅｎｔａｔｉｏｎ：Ｐｌａｎｎｉｎｇ  Ｏｔｈｅｒ  Ａｇｅｎｔ’Ｐｌａｎｓ」Ｉｎ  Ｐｒｏｃｅｅｄｉｎｇｓ  ＩＪＣＡＩ−８９、５１７及び５２３ペ−ジ、Ｄｅｔｒｏｉｔ、ＭＩ、１９８９は、提案の他のエージェントの評価に影響を与えるためにどの同意を使用するかを決定するために序列を用いる。この序列は、目標を達成する別のやり方を表す。それは、関連のあるエージェントの目標を決定するのに使用されないか、又は提案の実際の評価を行うのに使用されない。Ｒ．Ｗｅｉｈｍａｙｅｒ及びＲ．Ｂｒａｎｄａｕ「Ａ  Ｄｉｓｔｒｉｂｕｔｅｄ  ＡＩ  Ａｒｃｈｉｔｅｃｔｕｒｅ  ｆｏｒ  Ｃｕｓｔｏｍｅｒ  Ｎｅｔｗｏｒｋ  Ｃｏｎｔｒｏｌ」Ｉｎ  Ｐｒｏｃｅｅｄｉｎｇｓ  ＩＥＥＥ  Ｇｌｏｂａｌ  Ｔｅｌｅｃｏｍｍｕｎｉｃａｔｉｏｎｓ  Ｃｏｎｆｅｒｅｎｃｅ（ＧＬＯＢＥ−ＣＯＭ  ’９０）６５６及び６６２ペ−ジ、Ｓａｎ  Ｄｉｅｇｏ、ＣＡ、１９９０で使用される序列は、抽象化の関係（代替）のみを表す木である。その上、この序列は、他のエージェントの目標について考えるのに使用されない。この序列は、エージェント自身の目標を達成する代替プランの表示として使用され、そして次の提案を生ずるのに使用できる。追加の情報（例えば代替のコスト又は或るレベルの抽象化の代替の利用可能性）は、エージェント間を通過してエージェントの序列を通ってサーチプロセスを指導し調整する。しかし、従来技術に記載された折衝方法は、二三の欠点を有する。特に、従来技術の折衝方法は、概して、目標を達成するための代替が受け入れできそしてどれができないかに関する多くの情報を交換するために、種々のエンティティについてエージェントを必要とする。或る応用例えば通信ネットワークでは、エージェントにとりどの代替が受け入れ��きそしてエージェントにとりどの代替が受け入れできないかに関する情報は、情報が方略的情報（エージェントにとり最も有利な同意を見いだすのに使用される）であるか、又はそれが占有情報（例えば加入者がむしろ専有を保持するポリシーに関する情報例えば呼び出しスクリーニングリスト）であるという理由の何れかのために、通常、制限される。さらに、従来技術の折衝技術は、（共働的交渉の分析及び分配される問題解決に関与する役割（Ｐｒｏｃ．Ｉｎｔ．Ｃｏｎｆ．Ｅｘｐａｒｔ  Ｓｙｓｔ．Ｅｔｃ．，１９９１，ｐ．８１−９４）受け取ったエージェントをして、受け取った提案を評価して、それらの受け入れ可能性又は受け入れ不可能性を決めさせ、そして受け取った提案が受け入れできないときには逆提案を発生させる、満足できる方法を提供しない。特に、従来技術の折衝技術は、伝送エージェントからの受け入れできない提案を受け取る受け取りエージェントをして、伝送エージェントの目標を推論しそして推論した目標を実現する伝送エージェントへ伝送しかえすための逆提案を発生させない。従来技術の折衝方法のこれらの短所を克服するのが本発明の目的である。
発明の概要
本発明は、上記目的を達成するため、基本的には以下に示す様な技術構成を採用するものである。即ち、コンピュータープロセス（以後、エージェント（ａｇｅｎｔ）と称する）によって代表されるそれぞれのエンティティ（ｅｎｔｉｔｙ）を有する分散システムに於いて、複数の当該エンティティ間に於ける一つのアクティビティ（ａｃｔｉｖｉｔｙ）を確立する方法であって、当該複数のエンティティに対するそれぞれのエージェントは、当該分散システムにおいて実行可能な操作（ｏｐｅｒａｔｉｏｎ）を含む提案（ｐｒｏｐｏｓａｌｓ）を発生させ、次いで、当該発生された提案を当該複数のエンティティに対する他のエージェントに送信し、そして、当該複数のエンティティに対する他のエージェントから提案を受信すると共に当該受信した提案がそのエージェントにとって受入可能であるか受入不可能であるかを、木構造（ｔｒｅｅ−ｓｔｒｕｃｔｕｒｅ、以後目標序列（ｇｏａｌ  ｈｉｅｒａｒｃｈｙ）と言う）を調査する事によって決定する為に配置されており、且つ当該木構造に於けるそれぞれのノード部は、受入可能か、受入不可能か、或いはその何れにも決定できないと言う様にマークされているそれぞれの操作についての詳細を含んでいる様に構成されている当該方法に於いて、当該方法は、当該複数のエンティティを代表する複数のエージェント間で、当該複数のエンティティを代表する全てのエージェントが、当該アクティビティを確立する為のある特定の提案が、受け入れられるか、或いは如何なる同意にも到達出来なかったと言うことを決定するまで、幾つかの提案を交換し合う工程、及び当該複数のエンティティを代表する全てのエージェントが当該特定の提案が受け入れ可能であると決定する場合には、当該分散システムに於いて、当該アクティビティを確立する為に当該特定の提案に含まれる操作を実行する工程を含んでおり、更に当該方法は、当該一つのエージェントが、当該受信した提案が受け入れ可能でないと決定した後に、当該エージェントは、互換可能な提案（以後、逆提案と言う）を得るために、受信した当該提案が受け入れ不可能であると決定する為に使用されたノード部からスタートして、当該提案を受入可能か受入不可能かの何れにも決定できないノード部を見つける為に、当該枝部に沿って上昇する方向に調査し、その後、受入可能であるとマークされている操作についての詳細を含んでいるノード部を見つけるために他の枝部に沿って下降する方向に調査する事により、当該目標序列を調査する工程、及び当該逆提案としての当該操作についての詳細を他のエージェントに送信する工程、とを実行する事を特徴とする複数のエンティティ間に於ける一つのアクティビティを確立する方法である。
本発明に於いて使用される当該エンティティとは、具体的には、例えば、通信ネットワークにあっては、加入者、資源提供者或いは情報提供者であり、又分散データベースシステムに有っては、ローカルデータベースである。
又、本発明に於ける分散システムとは、自主的に独立した又は共に開発したシステム或いは互いに相互に作用できるコンピュータプログラムの集合であり、その具体的な例としては、通信システムやデータベースシステム或いはコンピュータでサポートされた協調的ワーク等である。
一方、本発明に於いて使用されるエージェントとは、コンピュータプロセスを示すものであり、上記エンティティは、エージェントにより代表されるものである。
又、本発明に於ける当該エージェントによって代表されるエンティティは、当該分散システムに於いては互いに独立しており、マスター−スレーブの関係にはないが、相互に協調的関係にある。
更に、本発明に於けるアクティビティとは、一般的な言葉であり、より具体的には、通信ネットワークに於ける通信タイプであり、又分散データベースシステムに於いては取引のタイプ等である。
一方、本発明に於いて使用される目標序列（ｇｏａｌ  ｈｉｅｒａｒｃｈｙ）とは、ゴール階層とも言われており、それぞれのエージェントが有しているもので、記憶手段に記憶されている情報に関しての複数の枝部からなる木構造（ｔｒｅｅ−ｓｔｒｕｃｔｕｒｅ）を形成している。又、上記木構造のそれぞれのノード部は所定のタイプのアクティビティを確立するために特定の目標を達成する為特定の操作の仕様を含むものである。
尚、折衝者は、仲介的なコンピュータープロセスに該当する。
本発明によれば、分散システム中の種々のエンティティ例えばカスタマー、又はカスタマー前提（ｐｒｅｍｉｓｅｓ）装置、又は通信ネットワークのネットワーク資源は、それぞれエージェントにより表示される。通信ネットワークの場合では、構成要素を代表するエージェントは、対応するエンティティが含まれることを望みそして通信をエンティティ間の競合を避けるやり方で設定する通信のタイプを折衝する。折衝プロセスは、エージェントによる提案の交換を含む。提案は、通信ネットワークにより採用することのできる１種又はそれ以上の操作からなる。第一のエンティティを代表する第一のエージェントは、それにとって受け入れ可能な提案を発生させ、そして第二のエンティティを代表する第二のエージェントへ提案を伝送する。第二のエージェントは、受け取った提案がそれにとって受け入れ可能な提案であるかどうかを決め、そしてそうでなければ、第一のエージェントへ伝送され戻される逆提案を発生させる。プロセスは、提案が両方のエージェントにとり受け入れ可能かどうかを見いだすまでか、又は両方のエージェントにとり受け入れ可能な特別なタイプの通信セッションを実現するのに提案がないことを決定するまで、続けられる。もし提案が両方のエージェントにより受け入れ可能であることが分かるならば、提案に含まれる操作は、通信ネットワークにより実行される。
エージェントは、提案が受け入れ可能かどうかを決めるために目標序列を使用する。目標序列は、エージェントが通信ネットワークにどんな操作をそのエンティティを代理して行うように指示できそしてできないかを示す。目標序列は、どの提案及び逆提案をそれが発生させそして他のエージェントに伝送することを決め、そして他のエージェントから受け取った提案が受け入れ可能かどうかを決めるのにエージェントにより使用される。エージェントが他のエージェントから受け取った提案に同意できないとき、受け取ったエージェントは、目標序列を使用して提案の目標を推論し、そして目標を達成するために別の提案即ち操作の代替セットを見いだすように試みる。例えば、目標序列におけるルート目標（即ちルート操作）は、呼び出し（Ａ、Ｂ）であり、即ちＡとＢとの間に呼び出しを設けることであろう。ルート目標呼び出し（Ａ、Ｂ）に関する目標序列は、それによりルート目標呼び出し（Ａ、Ｂ）が実行できる異なる操作及び操作の組み合わせを含むだろう。目標呼び出し（Ａ、Ｂ）を実行するための一つの操作は、Ａ及びＢは、単純呼び出しにより接続される単純呼び出し（Ａ、Ｂ）である。呼び出し（Ａ、Ｂ）を実行するための他の操作は、呼び出しがＢに達するときＡに関する識別情報がＢへ提供される識別呼び出し（Ａ、Ｂ）である。目標序列の操作は、一つが頂部から底部へ移動するにつれ作用が次第に特殊化される木で整えられる。例えば、ルート親ノードは、呼び出し（Ａ、Ｂ）であることができる。ルート親ノードの子ノードは、単純呼び出し（Ａ、Ｂ）及び識別呼び出し（Ａ、Ｂ）であることができる。これらの子ノードは、ルート又は親ノードの目標を実行するための特殊化された操作を含む。異なるタイプの親ノード例えば識別呼び出し（Ａ、Ｂ）について、子即ち接続（Ａ、Ｂ）及び引き渡し情報（Ａ）は、組み合わされて親ノードの操作を形成する、操作即ちＡとＢとの接続及びＡからＢへの引き渡し情報を表す。
本発明によれば、各エージェントについて、目標序列における各ノードは、受け入れ可能か、受け入れ不可能か、又は未決定としてそのままにされる。目標序列のこのマーキングは、エージェントにより表さられるエンティティに関するポリシーに通常基づく。例えば、加入者の形のエンティティは、その家庭電話番号を秘密に保つポリシーを有することができる。従って、他の加入者への家庭電話番号の送信を必要とする目標序列における全ての操作は、受け入れ不可能とマークされる。エージェントは、提案及び逆提案を発生させそして他のエージェントから受け取る提案が受け入れできるかどうかを決定するためにノードマーキシングを使用する。例えば、エージェントが他のエージェントから提案を受け取り、そしてその提案が受け取りエージェントにとり受け入れ不可能であるとする。受け取りエージェントは、受け入れ不可能な提案の目標を推論するために、目標序列を移動させることができる。受け取りエージェントは、次に同じ目標を実行するのに受け入れできる他の操作又は操作のコレクションがあるかどうかを決める。そうであれば、それは逆提案として使用できる。或る場合例えば二つより多いエージェントが通信を設定するのに含まれるときには、本発明によれば、折衝が、折衝に含まれる種々のエージェントから提案を受け取りそして提案を提出する折衝物として知られているコンピュータプロセスにより行われる。
競合なしに通信ネットワークのような分散システムにおけるエンティティ間の通信を設定する本発明の折衝方法は、多数の顕著な利点を有する。第一に、エージェントは、それら自身又は他のエージェントの目標の変更に依存することよりも、全ての関係するエージェントの目標を達成する代替の操作又は操作のセットを見いだす。さらに、通信ネットワークのような分散システムにおける作業を設定する本発明の方法は、情報の開示に制限をもたらす。制限は、方略的情報（例えばどの提案がエージェントに受け入れ可能かを直接特定する情報）及び機密情報（例えば加入者がむしろプライベートに保つポリシーに関する情報）に適用する。
【図面の簡単な説明】
図１は、競合なしにエンティティ間に通信を設定するための本発明の折衝プロセスを利用する通信ネットワークを概略的に図示する。
図２、３Ａ及び３Ｂは、本発明に従って折衝プロセスにおいてエージェントにより利用される目標序列を図示する。
発明の詳細な説明
本発明の折衝方法の適用性
本発明の折衝方法を使用するために、基礎となるコンピュータシステムは、好ましくは或る基準を満たす。第一に、システムは、使用者の或るコレクションにアクセス可能であり、そして使用者は、かれらがシステムを使用することを達成することを試みる或る目標を有する。第二に、システムは、任意の使用者の代わりに要求できそしてもし要求者がそれを実行する権限を付与されているならば実行するだろう操作からなるインターフェースを提供する。第三に、操作は、或る使用者により「所有」され、それは、操作が、使用者が要求者に操作を実行する権限を付与したときのみ実行されうることを意味する。第四に、操作をプランに組み込むことができ、そしてこれらのプランは、使用者の目標を達成するのに使用される。このシステムの例は、ＡＩＮ（アドバンスドインテリジェントネットワーク）又はＩＮ（インテリジェントネットワーク）のスイッチを使用する通信ネットワークである。使用者は、カスタマー、サービスプロバイダ（例えば操作会社）及び資源プロバイダ（操作会社及び長距離通信業者）である。カスタマーの目標は、或るやり方で通信することである。サービスプロバイダ及び資源プロバイダの目標は、サービス又は資源を提供することにより金をもうけることである。操作は、ＡＩＮ（又はＩＮ）呼び出しモデルにより規定される。基本的呼び出しモデルにおけるそれぞれの状態遷移に対応する一つの操作そしてそれぞれのビルディング・ブロック（又はＳＩＢ）に対応する一つが存在する。操作は、組み合わされて、双方向及び多方向呼び出し及びボイス・メールを含む、異なる種類の呼び出しを設定できる。（基本的な呼び出しモデルの操作は、その呼び出しモデルに与えられるように組み合わされるべきである。）カスタマーがオフフックになるとき、彼又は彼女は、電話ネットワークを使用する目標を特定する。カスタマーによる次の作業は、目標の仕様をさらに精密にし、そのためカスタマーは、呼び出しを設定するか、又はスクリーニングリストを編集するか、又は或る他の作業を行うか試みることができる。本発明の方法が適用できる他の例は、分散データベースシステムである。使用者は、データベースの所有者、管理者、データベース書き入れ者、並びに高度の問い合わせ言語によりデータベースに問い合わせるか又は改訂する人を含む。操作は、標準のデータベース操作を含む。代表的な分散データベースでは、各ローカルデータベースの管理者は、そのデータベースのデータに関する全ての操作に権限を有する。データベース操作は、通常トランザクションに組み合わされる。折衝は、トランザクションが実行されるか又は何時それが実行されるかを決めるか、又は実行する代替のトランザクションを見いだすのに使用できる。
一般に、方法は、上記の基準を満足する全てのコンピュータシステムに適用できる。
Ａ．通信ネットワーク
図１は、本発明の折衝プロセスを実行するのに使用できるタイプの通信ネットワーク１０を概略的に説明する。ネットワーク１０は、幹線ライン１６により接続された中心オフィス１２及び１４からなる。中心オフィスは、実例としてＡＩＮ又はＩＮスイッチからなる。使用者Ａのカスタマー前提装置２０は、加入者ループ２４を経て中心オフィス１２へ接続される。使用者Ｂのカスタマー前提装置２２は、加入者ループ２６を経て中心オフィス１２へ接続される。同様に、使用者Ｃのカスタマー前提装置２８は、加入者ループ３０を経て中心オフィス１４へ接続される。一般に、使用者Ａ、Ｂ、Ｃのカスタマー前提装置２０、２２、２８は、電話ネットワークを経る情報の伝送又は受信のための電話、ファックスマシン、コンピュータ又は種々の他の装置である。ネットワーク１０を使用して、種々の異なるサービスが提供できる。種々のタイプの電話サービスが提供され、それらは、単純な点対点の音声接続、そして呼び出しパーティの電話番号又は他の識別情報が呼び出されたパーティのカスタマー前提装置に表示されるサービスのような一層特殊化され付加したサービスを含む。さらに、中心オフィスの一つにあるブリッジ（図示せず）を使用して、遠隔会議が複数の使用者（例えば使用者Ａ、Ｂ、Ｃ）の中に設定できる。通信ネットワーク１０で提供できるサービスの他の例は、情報検索である。例えば、使用者Ｃのカスタマー前提装置２８を、データベースマネージメントシステムとする。他の使用者（例えばＡ及びＢ）は、特定の情報を得るためにネットワーク１０を経てデータベースマネージメントシステムにアクセスできる。
本発明によれば、通信ネットワーク１０中の各エンティティ（例えばカスタマー前提装置２０、２２、２８、遠隔会議のためのブリッジなど）は、エージェントにより代表される。各エンティティを代表するエージェントは、コンピュータプロセスである。実例として、ネットワーク１０中の各構成要素と結合するエージェントは、中心オフィス１２へ接続するコンピュータ４０で実行される。コンピュータ４０で実行されるエージェントは、コンピュータ４０と結合するメモリー４２中に記憶される目標序列を利用する。目標序列は、以下に詳細に説明される。或る場合には、エンティティ（例えばカスタマー前提装置）がそれ自体コンピュータである場合、エンティティを示すエージェントは、中心オフィスと結合したコンピュータに存在するよりむしろそれ自体エンティティに存在する。或る場合では、或るエンティティに関するエージェントは、中心オフィスに位置し、そして他のエンティティに関するエージェントは、エンティティそれ自体で実行できる。
Ｂ．折衝プロセス
本発明による折衝プロセスは、詳細に考慮される。第一に、単純折衝プロセスの例が提供される。次に、折衝プロセスが本発明に従って自動化されるプロセスが論議される。
１）折衝プロセスの例
図１のネットワーク１０において、使用者Ａがリストされていない電話番号を有しそして使用者Ｂが呼び出し番号伝達サービスを有する場合を考える（即ち、使用者Ｂのカスタマー前提装置２２は、使用者Ｂをして呼び出しパーティの電話番号を知ろうとする）。従って、もし使用者Ａがネットワーク１０を経て使用者Ｂを呼び出そうと試みるならば、競合が生ずる。特に、リストされていない番号を有する使用者Ａが、彼の又は彼女の電話番号を一般に知らしめることを望まないために、使用者Ａのリストされていない番号機能は、使用者Ｂの呼び出し番号伝達機能と整合しないように見える。
この競合は、競合なしにＡとＢとの間に呼び出しを設定するやり方を見いだす使用者Ａのエージェントと使用者Ｂのエージェントとの間の折衝により解消できる。
それ故、使用者Ａと使用者Ｂとの間の呼び出しは、以下のように設定できる。使用者Ａは、ネットワーク１０を経てコンピュータ４０のそのエージェントへメッセージを送り、使用者Ａが使用者Ｂを呼び出すことを望んでいることを示す。使用者Ａに関するエージェントは、使用者Ｂに関するエージェントへ提案接続（Ａ、Ｂ）を通信し、それは又コンピュータ４０で実行する。この提案は、ＡとＢとの間で呼び出しを設定するための提案された操作からなる。使用者Ｂに関するエージェントは、提案接続（Ａ、Ｂ）を受け取り、そして提案が呼び出し番号を含まないのでそれが受け入れ不可能であることを決める。使用者Ｂに関するエージェントは、接続（Ａ、Ｂ）及び伝達番号の形の逆提案を発生させ、そしてこの提案をＡに関するエージェントへ伝送する。Ａに関するエージェントは、この提案を受け取り、そして追加の操作伝達番号を知らしめる。Ａのエージェントは、それがＢへＡのリストされていない電話番号を伝達する追加の操作を必要とするために、逆提案を受け入れることができないことを見いだす。Ａに関するエージェントは、次に逆提案接続（Ａ、Ｂ）、並びに操作伝達番号の代わりに操作伝達名を用いる伝達名を発生させる。この提案は、Ｂに関するエージェントへ伝送される。Ｂに関するエージェントは、次にこの提案を受け入れる。提案が、提案された呼び出しに含まれる全てのエンティティに関するエージェントに受け入れられるとき、提案は、コンピュータ４０からネットワーク１０へ伝送され、受け入れられた提案に含まれる操作は実行される。
ＡとＢとの間の上記の折衝は、以下の表に要約される。
0003716995.tif 000003
この例並びに同意が見いだされる事実は、重要な質問に対する答え次第で決まる。なぜ提案は次に合理的に交換されるか？なぜＡは、例えばさらに払うか又は呼び出しに第三のパーティを含むかを申し出る代わりに、Ｂの逆提案を受け取って名を提供することを申し出るのか（そのそれぞれは、他の状況では合理的な逆提案である）？
答えは以下の観察にある。概して、提案は、エージェントの最終の目標を示さないが単にエージェントの目標を達成する一つのやり方を示す。同様に、エージェントの目標を達成する代替のやり方が存在するかもしれない。同じ目標を達成するこれら代替のやり方は、折衝に関する余地を提供する。これらの代替のやり方を調べるために、受け入れられない提案を受け取るエージェントが、提案がどんな目標を達成しようとしており、そしてその目標から同じ目標を達成する代替の恐らく受け入れ可能なやり方を導き出そうとすることを認識する必要がある。もしエージェントが他のエージェントがどんな目標を達成しようと試みているかを明快に伝えられていないならば、エージェントは、それが有する情報即ち受け取った提案に基づいて目標について予測できることになる。前の例では、Ａは、番号伝達により呼び出しを設定するために提案を受け取った。この提案は、それ自体受け入れ不可能である。しかし、この例では、Ａは、Ｂの目標は実際にはＡの番号を受け取ることではなく、むしろ或る識別情報（例えば名）を受け取ることであったと推論した。この目標は、又他のやり方、例えば番号の代わりに名を送ることにより達成できる。名を送ることがＡにとり受け入れ可能であるため、この代替は、次に提案される。従って、提案に対する合理的な逆提案は、その提案と同じ目標を達成するものである。
２）目標序列を使用する折衝プロセスの自動化
本発明によれば、それによりエージェントが提案及び逆提案を発生させるプロセス並びにそれによりエージェントが他のエージェントから受け取られた提案が受け入れ可能か又は受け入れ不可能かを決めるプロセスは、自動化される。特に、エージェントは、目標序列を使用して、提案及び逆提案を発生させ、そして他のエージェントから受け取られた提案が受け入れ可能か又は受け入れ不可能かを決める。通信ネットワーク１０における種々のエンティティを含む多くの異なるタイプの呼び出し及び通信セッションに関する目標序列は、コンピュータ４０に取り付けられたメモリー４２に記憶される。
操作のコレクションは、システムにより提案される。操作のコレクションは、プランを形成する。プランが実行されるとき、それは目標を達成する。最も単純な目標は、単一のシステム操作を実行することである。これを達成するためのプランは、その一つの操作のみからなる。目標は、下記の抽象化及び複合化の関係により互いに関連している。抽象化及び複合化の関係のコレクションは、目標序列を規定する。
一度目標序列が規定されると、各目標を達成するためのプランのコレクションが見いだされる。これらのプランは、それらがいかに目標を達成するかを一層精密に特定しているので、仕様と呼ばれる。仕様は、目標のセットである。目標の一つの仕様は、まさに目標それ自体からなるセットである。他の仕様は、この仕様に以下の二つの操作の或る配列を適用することにより形成される。
・抽象化目標の特殊化（以下を参照）の一つにより仕様の任意の抽象化目標を置換する。
・複合化目標の下位目標の全てにより仕様の任意の複合化目標を置換する。
第二の種類の段階は、単一の目標の代わりに数種の目標を使用することにより仕様のサイズを拡大できる。
われわれは、又仕様の改良を規定する。第二の仕様は、もしそれが第一の仕様へ上記の二つの操作の或る配列を適用することにより得られるならば、第一を改良する。
使用者Ａがリストされていない番号を有しそして呼び出しＢが呼び出し番号伝達サービスを有する呼び出しタイプに関する目標序列は、図２に説明される。
図２の目標序列１００は、複数のノード１０２、１０４、１０６、１０８、１１０、１１２、１１４、１１６からなる。各ノードは、目標を表す。上記のように、用語目標は、通信ネットワークで採用できる一つ又はそれ以上の操作をここでは使用されるとき示す。目標序列１００のノード間の関係は、点線及び実線により示される。
点線により示される関係は、抽象化関係として知られている。抽象化関係は以下のように操作される。操作呼び出し（Ａ、Ｂ）からなるルートノード１０２を考える。ノード１０２は、点線１０１及び１０７によりノード１０２へ接続している二つの子ノード１０４及び１０８を有する。この場合、各子ノード１０４及び１０８は、ノード１０２の目標を実施する一つの特殊化されたやり方を表す。従って、ノード１０２呼び出し（Ａ、Ｂ）の目標は、ＢへのＡを識別する情報の無伝送を含むノード１０４の操作単純呼び出し（Ａ、Ｂ）により実施できる。ノード１０２の目標は、又ＢへＡに関する識別情報を伝送することを含むノード１０８の操作識別呼び出し（Ａ、Ｂ）により実施できる。一般に、点線１０１及び１０７によりノード１０２へ接続されるノード１０４及び１０８のそれぞれは、ノード１０２の特殊化と呼ばれる。ノード１０２は、次にノード１０４、１０８の抽象化と呼ばれる。
ノード１０８の目標は、複合化目標である。ノード１０８の目標及びその子ノード１１０及び１１２の間の関係は、複合化の一つである。ノード間のこれらの複合化関係は、実線例えば実線１０９及び１１１により示される。この場合、目標１０８は、複合化目標でありそして目標１１０及び１１２は、成分目標である。複合化目標（例えば目標１０８）は、もし全てのその成分目標（例えば目標１１０及び１１２）が実現されるならば、そのときに限って実現される。図２の目標序列で示されるように、識別呼び出し（Ａ、Ｂ）の成分目標は、ノード１１０の接続（Ａ、Ｂ）及びノード１１２の伝達情報（Ａ）である。ノード１１２の抽象化目標伝達情報（Ａ）は、ノード１１４の特殊化目標伝達番号（Ａ）又はノード１１６の特殊化目標伝達名（Ａ）により実現できる。図２で示されるタイプの序列は、プラン認識について記載されている（例えば、Ｈ．Ａ．Ｋａｕｔｚ「Ａ  ｆｏｒｍａｌ  ｔｈｅｏｒｙ  ｏｆ  ｐｌａｎ  ｒｅｃｏｇｎｉｔｉｏｎ  ａｎｄ  ｉｔｓ  ｉｍｐｌｅｍｅｎｔａｔｉｏｎ」Ｊ．Ｆ．Ａｌｌｅｎ、Ｈ．Ａ．Ｋａｕｔｚ、Ｒ．Ｎ．Ｐｅｌａｖｉｎ及びＪ．Ｄ．Ｔｅｎｅｎｂｅｒｇ編「Ｒｅａｓｏｎｉｎｇ  ａｂｏｕｔ  Ｐｌａｎｓ」２章、７０−１２５ペ−ジ、Ｍｏｒｇａｎ  Ｋａｕｆｍａｎｎ  Ｐｕｂｌｉｓｈｅｒｓ、Ｉｎｃ．Ｓａｎ  Ｍａｔｅｏ、ＣＡ  １９９１参照）。
本発明によれば、エージェントは、他のエージェントへの伝送のために提案及び逆提案を発生させそして他のエージェントにより発生された提案及び逆提案を受け取る。提案及び逆提案の全ては、上記のように目標の仕様を構成することにより形成される。エージェントは、又目標序列例えば図２の目標序列を使用して、提案が受け入れ可能か又は受け入れ不可能かを決める。
３）提案の受け入れ可能性
提案は、もしその対応するエンティティがそれに同意するならば、エージェントに受け入れられることができる。従って、目標序列の各目標（即ちノード）は、受け入れ可能、受け入れ不可能をマークするか、又はマークしない。目標がマークされないとき、それは未決定である。
４）提案の受け入れ可能性
提案は、もしそれが受け入れ可能な目標の仕様ならば、受け入れることができる。
提案は、もしそれが受け入れ不可能な目標の仕様であるならば、受け入れることができない。
受け入れ可能及び受け入れ不可能と目標を分類することは、もし仕様が受け入れ可能な目標及び受け入れ不可能な目標の両方の仕様でないならば、そしてもしそのときに限ってのみ整合している。
二つの追加のルールは、複合化目標の成分の受け入れ可能性又は不可能性から複合化目標の仕様の受け入れ可能性又は不可能性を演繹するのに使用できる。複合化目標ｇが、受け入れ可能か又は受け入れ不可能かに分類されないとする。ｈ１・・・ｈｎをその成分目標とし、Ｈｉをそれぞれのｉについてｈｉの受け入れ可能な仕様であるとする。ｉ＝１、・・・ｎ。次に、仕様Ｇ＝Ｕｎｉ＝１Ｈｉはｇの受け入れ可能な仕様である。さらに、もし仕様Ｈｉが受け入れ不可能であれば、Ｇ＝Ｕｎｉ＝１Ｈｉは、ｇの受け入れ不可能な仕様となる。これらのルールを目標に適用すると、明快に分類されなかった複合化目標が、もしその成分の一つが受け入れ不可能であるならば、受け入れ不可能であることを演繹できる。
各使用者は、上記のルールと整合して序列の目標をマークしなければならない。どんな仕様も受け入れ可能及び受け入れ不可能の両方であることを決められないことを確かめるために、我々は、可能な限り目標の分類を拡大する。我々は、目標の得られる分類を序列の完全なマーキングと呼ぶ。どんな目標も、完全なマーキングにおいて受け入れ可能及び受け入れ不可能の両方に分類されないならば、序列のマーキングは、矛盾のないもの、即ち全ての仕様が正に受け入れ可能、受け入れ不可能又は未決定の一つである。
我々は、以下のように分類を拡大する。
・最高のレベルのノードから出発し、序列をレベルダウンすることにより進み、もし抽象化目標が受け入れ可能であれば、全てのその子のマークは受け入れ可能であり、そしてもしそれが受け入れ不可能であれば、全てのその子のマークは受け入れ不可能である。
・最低のレベルのノードから出発し、序列をレベルアップすることにより進み、もし抽象化目標の子の全てが受け入れ可能であれば、それを受け入れ可能とマークし、もし未決定複合目標の子の全てが受け入れ可能であるならば、それを受け入れ可能とマークし、もし抽象化目標の子の全てが受け入れ不可能であれば、それを受け入れ不可能とマークし、そしてもし未決定の複合目標の任意の子が受け入れ不可能であれば、それを受け入れ不可能とマークする。
一度これらの段階が上記の順序で行われると、序列のマーキングは完全となる。使用者Ａに対する受け入れ可能及び受け入れ不可能の目標を示すマーキングを有する図２の目標序列は、図３Ａに示される。使用者Ｂに対する受け入れ可能及び受け入れ不可能の目標を示すマーキングを有する図２の目標序列は、図３Ｂに示される。（一般に、種々の異なるエンティティを含む多くの異なるタイプの通信セッションの目標序列は、特別なエンティティを代表する特別なエージェントへ異なるノードの受け入れ可能性及び受け入れ不可能性を示すマーキングとともに、図１のメモリー４２に記憶される）。
５）折衝プロセスにおける目標序列の使用
折衝プロセスは、エンティティ（例えば加入者）が目標を実現すべき結合されたエージェントへ通信するとき、開始される。例えば、加入者Ａは、それが目標呼び出し（Ａ、Ｂ）を実現することを望むそのエージェントへ通信することができる。この目標は、それ自体、Ａのエージェントにより使用されるように呼び出し（Ａ、Ｂ）に関する目標序列において受け入れ可能とマークできない（図３Ａ参照）。しかし、目標が受け入れ不可能でないとして、その目標の受け入れ可能な仕様が存在しなければならない。目標序列は、受け入れエージェントにより使用される目標序列で受け入れ可能とマークされる目標呼び出し（Ａ、Ｂ）の仕様を見つけるためにサーチされる。この場合、呼び出し（Ａ、Ｂ）の受け入れ可能な仕様は、単純呼び出し（Ａ、Ｂ）である。この仕様は、次にＢに関するエージェントへＡに関するエージェントにより最初の提案として伝送される。提案又は逆提案がエージェントにより受け取られるとき、受け取りエージェントは、提案又は逆提案が受け入れできるかどうかを決めなければならない。もし提案が、受け取りエージェントにより使用される目標序列で受け入れ可能とマークされる単一の目標を含むならば、受け取りエージェントは、それに同意できる。もし提案が、受け入れ可能とマークされた目標（即ちノード）の仕様ならば、提案は受け入れ可能である。
もし受け取り提案が、受け取りエージェントの目標序列に従って受け入れ不可能又は未決定であると決められるならば、逆提案は、発生させる必要がある。その場合、受け取り提案は未決定であり、逆提案は、目標序列を下降することにより受け取りエージェントによって発生させて、受け入れ可能である未決定目標の仕様を見いだすように試みる。もしこのような受け入れ可能な仕様が見いだされるならば、それは逆提案として伝送される。もし受け取り提案が、受け入れ不可能であると決められるならば、逆提案は、受け入れ不可能な提案により達成された任意の未決定目標が存在するかどうかを知るために、序列を上昇することにより受け取りエージェントによって発生させられる。次に、受け取りエージェントが、受け入れ可能な未決定抽象化目標の或る他の仕様が存在するかどうかを知るために、他のブランチに沿って序列を下降する。このような受け入れ可能な仕様は、次に逆提案を発生させるのに使用される。（注意、これは、正にビジネスでしばしば使用される「ウイン−ウイン（ｗｉｎ−ｗｉｎ）」折衝方略のタイプである。代表的なビジネス折衝において、第一のパーティが提案を作るとき、第二のパーティは、提案が受け入れ可能か又は受け入れ不可能かを決める。もし第二のパーティが、提案を受け入れることができないならば、彼／彼女は、しばしば、尋ねる。「あなたは、その提案を作るのになにを成し遂げようと試みるか、即ちなにがあなたの目標であるのか」。第一のパーティは、次に彼／彼女の目標を識別する。第二のパーティは、次に私は私に受け入れ可能であるあなたの目標を成し遂げる異なるやり方を有すると言うだろう。）
上記のＡとＢとの間の呼び出しの場合、受け入れ可能、受け入れ不可能及び未決定の提案及び逆提案の以下の例を考慮する。
１．Ａに関するエージェントは、目標呼び出し（Ａ、Ｂ）を実行する指令を対応するエンティティから受け取る。エージェントＡは、目標序列をサーチして、目標呼び出し（Ａ、Ｂ）を実施する受け入れ可能なやり方を見いだす。目標呼び出し（Ａ、Ｂ）は、Ａに関するエージェントにより使用される目標序列で未決定である。従って、Ａに関するエージェントは、下降することにより目標序列（図３Ａ）をサーチして、受け入れ可能な目標呼び出し（Ａ、Ｂ）の仕様を見いだす。図３Ａの目標序列の受け入れ可能な仕様は、接続（Ａ、Ｂ）である。接続（Ａ、Ｂ）の形の提案は、Ｂに関するエージェントへ伝送される。Ｂに関するエージェントは、提案接続（Ａ、Ｂ）を受け取り、そして提案が受け入れ不可能であると図３Ｂの目標序列から決める。逆提案を発生させるために、Ｂに関するエージェントは、図３Ｂの目標序列を上昇して、未決定である目標接続（Ａ、Ｂ）の抽象化を見いだす。未決定である抽象化は、呼び出し（Ａ、Ｂ）である。次に、Ｂに関するエージェントは、序列を下降して受け入れ可能な呼び出し（Ａ、Ｂ）の他の仕様を見いだす。受け入れ可能な仕様は、識別呼び出し（Ａ、Ｂ）である。この目標は、逆提案としてＡに関するエージェントへＢに関するエージェントから伝送される。
３．提案識別呼び出し（Ａ、Ｂ）は、Ａのエージェントにより受け取られる。Ａのエージェントは、その目標序列を調べ（図３Ａ）、そして提案識別呼び出し（Ａ、Ｂ）が未決定であることを注意する。Ａに関するエージェントは、次にその目標序列を下降して、受け入れ可能な識別呼び出し（Ａ、Ｂ）の仕様を見いだす。複合目標識別呼び出し（Ａ、Ｂ）の受け入れ可能な仕様は、接続（Ａ、Ｂ）及び伝達名（Ａ）である。（これは、それが複合目標のそれぞれの個々の成分の受け入れ可能な仕様からなるので、複合目標の受け入れ可能な仕様である。）この逆提案は、Ｂに関するエージェントへ伝送される。
４．Ｂに関するエージェントは、図３Ｂの目標序列を使用して、受け取る提案接続（Ａ、Ｂ）及び伝達名（Ａ）が受け入れ可能であることを決定する。Ａ及びＢに関するエージェントは、エンティティＡ及びＢ間の通信を確立するためのプランされた操作からなる提案について同意する。それ故、指令は、同意された提案を実行するために、中心オフィス１２（図１参照）へコンピュータ４０から伝送される。
提案及び逆提案の反復発生は、目標序列を経るサーチプロセスからなり、折衝を開始しそして全ての関係するエージェントに受け入れられるエージェントの初めの目標を達成する提案（即ちノード）を見いだす。全ての関係するエージェントに受け入れ可能な提案が見いだされるか、又はエージェントが同意に達することができないことを決めるかの何れかのとき、提案の交換は、終了する。
開始エージェントに受け入れられるそれぞれのそしてあらゆる提案が試みられるときどんな同意にも達することができない。即ち他の関係するエージェントへ伝送又はそれから受け取られそして同意に至らないことが決定される。
６）折衝者の使用
二つより多いエージェントが折衝セッションに含まれるときのような或る場合では、折衝者として知られているコンピュータプロセスの形の媒介者は、エージェントから提案を受け取り、そして提案をエージェントへ伝送するのに使用できる。本発明の説明的な態様では、折衝者が含まれるとき、折衝プロセスは、例示的に以下の要素を含む。
・目標序列
１．全てのエージェントは、同じ目標序列を有するが、異なるエージェントにとって異なるノードは、受け入れ可能又は受け入れ不可能などをマークできる。
２．目標序列の目標（即ちノード）の数は、有限である。
・折衝者
１．折衝者は、それが受け取る全ての提案を待ち行列に入れ、そして折衝が先ず終了するか又は或るエージェントが提案に対してノーと初めに答えない限り、それが受け取るあらゆる提案をＦＩＦＯ（先入れ先出し）の順序で開始エージェント及び全ての他の関係するエージェントへ送る。
２．もし折衝者が、それが開始エージェントからノーの応答を受け取る前に、それが受け取った全ての提案を送ったならば、それは、開始エージェントへ問い合わせを送るだろう。
３．以下の場合、折衝者は折衝を終了する。
（ａ）或る提案Ｐについて、開始エージェント及び全ての他の関係するエージェントが、彼らが提案Ｐを受諾すると折衝者へ伝えたとき。この場合、同意された解答は、通信ネットワークで実行される。
（ｂ）或る提案Ｐについて、開始エージェントが折衝者へノーと応答するとき。
４．折衝者は、一度だけエージェントへ提案を送る。
エージェント
１．エージェントが折衝者から提案を受け取るとき、それはイエスと応答するか（それは同意する）、ノーと応答するか又は逆提案を送ることができる。
２．開始エージェントが折衝者から問い合わせを受け取るとき、それはノーと応答するか、又は提案を送ることができる。
３．もし提案がそれにとって受け入れ可能であるならば、エージェントは、折衝者へ提案を送るだけに過ぎない。
４．もしエージェントにとって受け入れ可能であるそれぞれの提案Ｑに対して、それが折衝者からＱを受け取るか又はＱを折衝者へ送るかの何れかならば、エージェントは提案又は問い合わせに対してノーと応答する（これは、エージェントにとり受け入れ可能な全ての提案が、エージェントがノーと応答できる前に、エージェント又は或る他のエージェントにより提案されなければならなかったことを意味する）。
５．エージェントは、一度だけ折衝者へ提案を送る。
折衝者及びエージェントにより用いられる折衝アルゴリズムの詳細な記述は、付属の付録に記載されている。
簡単にいえば、分散システム例えば通信ネットワークの競合を解消する折衝プロセスが、開示されている。折衝プロセスでは、各エンティティは、エージェントにより表される。エージェントは、目標序列を使用して、他のエージェントへの伝送のために提案及び逆提案を発生させ、他のエージェントから受け取る提案の受け入れ可能性を決める。本発明の折衝プロセスは、エージェントにそれらの目標を変えるように要求することなくそしてエージェントに制限された情報を共用することを要求することなく、分散されたネットワーク（例えば通信ネットワークにおける通信）のエンティティ間の操作を設定するために、同意に至らしめる。受け取りエージェントが伝送エージェントから受け入れ不可能な提案を受け取るとき、受け取りエージェントは、伝送エージェントの目標を推論するために目標序列を使用することができることが本発明の折衝プロセスの特別な利点である。受け取りエージェントは、又目標序列を使用して、受け取りエージェントにとり受け入れ可能なそして又は伝送エージェントの推論された目標を満足させる代替提案を見つけるように試みる。上記の本発明を説明する態様では、折衝に含まれる全てのエージェントは、同じ目標序列を使用するが、異なる受け入れ可能性又は受け入れ不可能性のマーキングにより使用する。しかし、本発明の別の態様では、折衝に参加する異なるエージェントは、異なる目標序列を利用することができる。
最後に、本発明の上記の態様は、説明するだけのことを目的とする。本発明の多数の別の態様は、以下の請求の範囲の趣旨及び範囲から離れることなく、当業者により考案できる。
付録      折衝アルゴリズム
この付録は、折衝に関するアルゴリズムを概説する。折衝構成要素に関するエージェントに加えて、全ての提案及び逆提案が送られる折衝者プロセスも存在する。第一のセクションは、折衝者の操作を記述し、第二のセクションは、エージェントの操作を記述する。
折衝者
折衝者が最初の提案を受け取るとき、それは、種々のデータ構造をイニシャライズすることにより新しい折衝を開始する。データ構造は、以下の通りである。
・Ｈ−折衝者がエージェントへ送った全ての提案のセット。
・Ｑ−Ｐが試みられていない提案でありそしてＡが折衝者へそれを送ったエージェントであるペア＜Ｐ、Ａ＞の列。
・Ａ−折衝に含まれる全てのエージェントのセット。
データ構造をイニシャライズした後、折衝者は、どのエージェントが提案に権限を有することを要求されるかを決め、そして評価のためにそれらに提案を送る。提案Ｐについて、我々は、エージェントのこのセットをエージェント（Ｐ）と示す。
開始エージェントＡ１からの最初の提案Ｐ
・データ構造Ｈ、Ｑ及びＡをイニシャライズして空にする。
・＜Ｐ、Ａ１＞を列Ｑの終わりに加えそして折衝のラウンド（ｒｏｕｎｄ）を開始する。
折衝のラウンドは、評価のためにエージェントへ提案を送り、そして応答を集めることを含む。ラウンドの第一の段階では、折衝者は、提案を開始エージェントへ送って（もし提案が開始エージェントにより送られていなかったならば）、それが開始エージェントの目標を達成しそして開始エージェントにとり受け入れ可能かどうかを決める。もし開始エージェントが提案を受け入れるならば、折衝者は、次にそれの権限を有することを要求する他のエージェントへそれを送り、そしてそれらの応答を集める。折衝プロセスは、多くのこれらのラウンドからなる。提案Ｐを使用する折衝のラウンドは、折衝者の側の以下の操作により開始される。
ラウンドを開始
・もし列Ｑが空でないならば、Ｑの前部から提案＜Ｐ、Ａ＞を除く。
・（Ｐ∈Ｈ）及び（Ｑが空でない）の間繰り返す、Ｑの前部から提案＜Ｐ、Ａ＞を取り除く。（この段階は、提案が多くて一度送られることを保証する。）
・もしＰ∈Ｈならば、（Ｑは空に違いないので）折衝を不成功で終了する（どんな同意も見いだされなかった）。
・Ｐを履歴Ｈへ加える。
・もしＡがＡ１（開始エージェント）でないならば、ＰをＡ１に送りそしてその応答を待つ。
−もしＡ１が逆提案Ｑで応答するならば、＜Ｑ、Ａ１＞を列Ｑの最後に加え、そしてこのラウンドを終了する。
−もしＡ１が「ノー」と応答するならば、このラウンドを終了する。
（この段階は、開始エージェントが提案に同意したことを保証する。）
・（もし折衝者がこの段階に達するならば、Ａ＝Ａ１又はＡ１は、提案Ｐを受け入れた。）「エージェント」（Ｐ）の全てのエージェントをＡに加える。
・それぞれのＡ∈「エージェント」（Ｐ）について、変数「承認」［Ａ］及び「応答」［Ａ］を「偽り（ｆａｌｓｅ）」にセットする。
・提案を「エージェント」（Ｐ）のあらゆるエージェントへ送り、そして応答を集める。
折衝者が反応しなければならないことは、最初の提案（上記）の受け取り及び応答（イエス、ノー又は逆提案）の受け取りである。
エージェントＡからの応答
・「応答」［Ａ］を「真」にセットする。
・もし応答が「イエス」ならば、「承認」［Ａ］を「真」にセットする。
・もし応答が「ノー」ならば、「承認」［Ａ］を「偽り」にセットする。（開始エージェント以外のエージェントから「ノー」を受け取ることは、応答エージェントが全ての解答に含まれることができないことのみを意味する。しかし、異なるエージェントを含む解答が存在するだろう。）
・もし応答が逆提案
0003716995.tif 000004
でありそして＜Ｑ、Ｂ＞∈ＱであるようなエージェントＢが存在しないならば、＜Ｑ、Ａ＞を列Ｑの最後に加える。
・もしあらゆるエージェントＡ∈「エージェント」（Ｐ現在）にとり「応答」［Ａ］＝真ならば、
−あらゆるエージェントＡ∈「エージェント」（Ｐ現在）にとり「承認」［Ａ］＝真の場合、
・解答（Ｐ現在）により折衝を終了する。
・「エージェント」（Ｐ現在）の全てのエージェントへ「受け入れた」を送る。
・Ａ−「エージェント」（Ｐ現在）の全てのエージェントへ「行った」を送る。
−もし少なくとも一つのエージェントＡ∈「エージェント」（Ｐ）にとり「承認」［Ａ］＝「偽り」ならば、このラウンドを終了しそして折衝の新しいラウンドを開始する。
折衝者は、解答が見いだされるか又は逆提案の列が空になるまで、折衝を終了しない。折衝者は、或るエージェントが既に提案を拒絶しない限り、「エージェント」（Ｐ）のエージェントの全てにそれが受け取る全ての提案Ｐを送る。もしエージェントが「ノー」と応答するならば、もしそしてただもし現在の提案が受け入れ不可能でそしてそれが既に折衝者に全ての受け入れ可能な提案を送っていたに過ぎないならば、折衝者は、解答が見いだされていると保証するのに必要なように作業する。
エージェント
エージェントは、提案並びに折衝を終わらせるメッセージに応答しなければならない。開始エージェントは、その最初の目標を記憶し、そしてその目標の仕様でない全ての提案を拒絶しなければならない(その受け入れ可能性にかかわらず)。開始エージェントは、その最初の目標に等しい変数Ｇをセットする。全てのエージェントは、それらが送りそして受け取った提案の履歴Ｈを維持する。それらは、最初にＨ＝Φをセットする。開始エージェント及び他のエージェントは、以下のやり方で受け取った提案Ｐに応答するだろう。
開始エージェント
・ＰをＨへ加える。
・もしＰがＧの受け入れ可能な仕様ならば、「イエス」で応答する。
・もしＰが受け入れできないか又はＧの仕様でないならば、
0003716995.tif 000005
のようなＧの受け入れ可能な仕様Ｒが存在する場合、
・ＲをＨへ加える。
・Ｒと応答する。
0003716995.tif 000006
のようなＧの受け入れ可能な仕様Ｒが存在しない場合、「ノー」と応答する。
我々は、ここでは仕様をいかにピックするかを詳細に明らかにしない。
他のエージェント
・ＰをＨへ加える。
・もしＰが受け入れ可能ならば、「イエス」と応答する。
・もしＰが受け入れ不可能ならば、
−受け入れ可能な仕様
0003716995.tif 000007
が存在する場合、
・ＲをＨへ加える。
・Ｒと応答する。
−受け入れ可能な仕様
0003716995.tif 000008
が存在しない場合、「ノー」と応答する。
このやり方は、我々が非開始エージェントが送る提案の数を減らすことができるので、もし解答が存在するならば解答を見いだす保証を失うことなく、一層能率的である。アイディアは、非開始エージェントが、それらが開始エージェントの目標の仕様でない限り、仕様を提案しようと望まないことにある。非開始エージェントに達するあらゆる仕様が開始エージェントの目標を達成することに注意すべきである。従って、非開始エージェントは、開始エージェントの目標がなんであるかを仕様の配列から以下のように演繹できる。Ｉを現在までの折衝から推論される目標のセットとする。Ｉは、現在の提案がどの目標の仕様であるかを決め、そして目標のこのセットをＩの現在の値と交差させることにより反復して詳細にする。次に、我々は、エージェントが送る各提案が、Ｉにおける或る目標を達成することを要求することにより送られた提案の数を減少させる。これは、有効に提案のサーチスペースを減少させる。
全てのエージェント−メッセージ「受け入れた」又は「行った」の終了
・Ｈを空にセットする。
エージェントは、提案が受け入れ可能な場合のみ提案に同意し、そしてそれが受け入れ不可能な提案を受け取り、そして又目標Ｇを満足する全ての受け入れ可能な提案を受け取るか又は送るかの何れかでない限り、「ノー」と応答しないことに注意すべきである。
【図１】
0003716995.tif 000009
【図２】
0003716995.tif 000010
【図３Ａ】
0003716995.tif 000011
【図３Ｂ】
0003716995.tif 000012