(57)【要約】【解決手段】  選択された実世界環境におけるオブジェクトを表すためにソフトウェア・エージェントを使用するマルチエージェント・システムについて説明する。各エージェントは、特定の特徴を有する構造を有し、他のエージェントが需要エージェントに適した特徴を有する場合に他のエージェントとの関係を確立することができる。マルチエージェント・システムは、新しいイベントがシステムに参入したときに関係を確立するか、あるいは既存の関係を修正しかつシステムの総合的な値を最適化する自己組織化する補償をオファーするように、エージェント間で自律的に動的交渉を実行する。
2006505019.tif 000002
【特許請求の範囲】
【請求項１】
仮想環境で交渉するように適応されたエージェントであって、
実行可能プログラムとして実現され、エージェントの交渉特徴を決定する１組の特性を含むエージェント記述子と、
実行可能プログラムとして実現され、仮想環境から情報を受け取る少なくとも１つのセンサと、環境と連係する少なくとも１つのアクチュエータと、少なくとも１つのセンサから受け取った情報に基づいて意志決定プロセスを実行するために所定の期間能動状態で動作可能な決定エンジンとを含むエージェント本体とを含み、
決定エンジンが、交渉特徴に依存して別のエージェントと関係を確立し、確立された関係の質を表す値を決定するように動作可能なエージェント。
【請求項２】
前記特性の少なくともいくつかが、エネルギーの性質を定義する１組の属性と関連付けられる請求項１に記載のエージェント。
【請求項３】
前記特性の少なくともいくつかがそれぞれ、１組のシナリオを参照し、各シナリオが、エージェントの実行の挙動を制御する一連のコマンドを含む請求項１または２に記載のエージェント。
【請求項４】
前記決定エンジンが、前記１組のシナリオから、エージェントの交渉特徴とエージェントが作成した既存の確立済み関係の質とに従って少なくとも１つのセンサから受け取った情報に基づいて最も適切と考えられるシナリオを選択するように動作可能な請求項３に記載のエージェント。
【請求項５】
仮想環境が、需要と資源を含む実環境を表し、前記エージェントが、実需要に割り当てられた需要エージェントである請求項１から４のいずれか１項に記載のエージェント。
【請求項６】
仮想環境が、需要と資源を含む実環境を表し、前記エージェントが、実資源に割り当てられた資源エージェントである請求項１から５のいずれか１項に記載のエージェント。
【請求項７】
エージェント本体が、仮想環境の現在の状態を表すデータを保持するシーン・メモリを含む請求項１から６のいずれか１項に記載のエージェント。
【請求項８】
前記シナリオのうちの１つが、決定エンジンに、前記値を改善する補償を提示することによって１対のエージェント間に確立された関係を乱させるように構成された請求項３または４に記載のエージェント。
【請求項９】
エージェント本体が、エージェントの性質に関する知識を保持するオントロジ・メモリを含む請求項１から８のいずれか１項に記載のエージェント。
【請求項１０】
前記エージェント本体が、前記シナリオを保持するコマンド・メモリを含む請求項３に記載のエージェント。
【請求項１１】
少なくとも１つのセンサが、アクセス可能なデータベース・フィールドを読み出す手段を含む請求項１から１０のいずれか１項に記載のエージェント。
【請求項１２】
少なくとも１つのセンサが、メッセージを受け取るメールボックス機構を含む請求項１から１１のいずれか１項に記載のエージェント。
【請求項１３】
少なくとも１つのアクチュエータが、データベースにアクセスして中のデータ・フィールドを更新する手段を含む請求項１から１２のいずれか１項に記載のエージェント。
【請求項１４】
アクチュエータが、メッセージをディスパッチする手段を含む請求項１から１３のいずれか１項に記載のエージェント。
【請求項１５】
エージェント本体が、前記所定の期間を制御するタイマを含む請求項１から１４のいずれか１項に記載のエージェント。
【請求項１６】
請求項１から１５のいずれか１項にそれぞれ記載された複数のエージェントを含む仮想環境を作成することによって実環境をシミュレートする方法であって、
前記エージェントの少なくともいくつかに、エージェントの能動状態を所定の期間呼び出す段階と、
各能動エージェントに、エージェントの交渉特徴に従って少なくとも１つのセンサから受け取った情報に基づいて意志決定プロセスを実施して、別のエージェントと関係を確立できるかどうかを判定する段階と、
前記所定の期間の後で、エージェントの受動状態を呼び出す段階とを含み、前記エージェントが、自由の状態または対にされた状態を有し、対にされたエージェントが、確立した関係の質を判定する値を保持する方法。
【請求項１７】
仮想環境で交渉するように適応されたエージェントを実現するためにコンピュータを操作する方法であって、
エージェントの交渉能力を決定する１組の特性を含むエージェント記述子を定義する第１のプログラムを実行する段階と、
仮想環境から情報を受け取る少なくとも１つのセンサと、環境と連係する少なくとも１つのアクチュエータとを提供することにより、エージェント本体を準備する段階と、前記少なくとも１つのセンサと関連付けられた決定エンジンを実現する第２のプログラムを実行する段階とを含み、
前記決定エンジンが、エージェントの交渉特徴に従って少なくとも１つのセンサから受け取った情報に基づいて決定を行うために所定の時間能動状態で動作可能であり、決定エンジンが、交渉特徴に依存して別のエージェントとの関係を確立し、確立した関係の質を表す値を決定するように動作可能な方法。
【請求項１８】
前記特性の少なくともいくつかが参照する１組のシナリオをコマンド・メモリにロードする段階を含み、各シナリオが異なる組のコマンドを含む請求項１７に記載の方法。
【請求項１９】
前記意志決定プロセスが、１組のシナリオから最も適切なシナリオを選択する請求項１８に記載の方法。
【請求項２０】
エージェントによるアクセスに関して仮想環境の現行シーンをシーン・メモリにまとめる段階を含む請求項１７に記載の方法。
【請求項２１】
新しいイベントが出現したときに現行シーンが変更され、前記イベントが重要な場合に意志決定プロセスが別のシナリオを選択する請求項２０に記載の方法。
【請求項２２】
前記新しいイベントが、新しいエージェントである請求項２１に記載の方法。
【請求項２３】
前記新しいイベントが、シーンにおける既存のエージェントからのメッセージである請求項２１に記載の方法。
【請求項２４】
新しいイベントがシーンに参入しかつ前記イベントが重要でない場合に、意志決定プロセスが、現在のシナリオを実行し続ける請求項２１に記載の方法。
【請求項２５】
需要と資源を管理するためにコンピュータ・システムを操作する方法であって、
資源と需要の現在の状態を表すシーンを生成する段階と、
資源を表す第１組の資源エージェントと需要を表す第２組の需要エージェントとを含む複数のエージェントを、実行可能プログラムとしてインスタンス化する段階であって、各エージェントが、別のエージェントとメッセージを交換するように動作可能であり、かつシーンからの情報と前記他のエージェントからのメッセージとに基づいて意志決定プロセスを実行し、前記他のエージェントとの関係を実現し、前記関係と関係値を関連付ける決定エンジンを含む段階と、
前記関係値を関係の基準値と比較して、関係が満足なものかどうかを決定する段階とを含む方法。
【請求項２６】
実世界を表す仮想世界として構成されたコンピュータ・システムであって、
実行可能プログラムとして実現され、実世界における需要を表す１組の特性をそれぞれ含む第１組の需要エージェントと、
実行可能プログラムとして実現され、実世界における資源を表す１組の特性をそれぞれ含む第２組の資源エージェントとを含み、
需要エージェントと資源エージェントが、メッセージを交換することによって交渉するように動作可能であり、前記メッセージは、決定エンジンが所定の基準に基づいて関係を確立できるように各エージェントの需要と資源に対応する前記組の特性を含み、
新しい需要または資源がシステムに参入したときに、新しい需要または資源を表すエージェントが、確立済み関係の質を表す値を改善する補償をオファーすることによって１対のエージェント間の確立済み関係を乱すことができるコンピュータ・システム。
【請求項２７】
マルチエージェント・システムにおけるエージェントの特徴およびそのエージェント間の関係に関する知識を記憶するオントロジ・メモリを有し、エージェントが、そのオントロジ・メモリを参照して、交渉すべき適切なエージェントのリストを見つけることができる請求項１から２６のいずれか１項に記載のエージェント。
【請求項２８】
前記オントロジ・メモリが、マルチエージェント・システム内のすべてのエージェントがアクセス可能な共通知識と、前記エージェントだけがアクセスできる専用知識とを含む請求項２７に記載のエージェント。
【請求項２９】
エージェントの前記特徴が、特性、属性、および値を含む請求項２７に記載のエージェント。
【請求項３０】
前記オントロジ・メモリが、エージェントに特定のアプリケーションの知識だけを吹き込むことができるようにドメイン固有である請求項２７から２９のいずれか１項に記載のエージェント。
【請求項３１】
前記アプリケーションが、ロジスティックス・アプリケーションである請求項３０に記載のエージェント。
【請求項３２】
複数のプログラムを実行するためのプロセッサを含むコンピュータ・システムであって、各プログラムが、仮想環境で交渉するエージェントと、複数のエージェント定義データを記憶するメモリを表し、各エージェント定義データがオントロジを有し、前記オントロジが、
エージェントの性質を定義する１組の特性と、
エージェントによる交渉に使用される特徴を定義する１組の属性と、
様々な意志決定プロセスを実施するためにエージェントによって実行可能な１組のシナリオと、
エージェントによって確立された関係の質を定義する値を保持する関係質記憶機構とを含むコンピュータ・システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、仮想環境の管理に関し、詳細には、ソフトウェア・エージェントおよびそのようなエージェントを実行するコンピュータ・システムに関するがこれらに限定されない。また、本発明は、実環境をシミュレートし、シミュレートした仮装環境を使用して需要と資源を管理する方法に関する。
【背景技術】
【０００２】
実環境のコンピュータ・シミュレーションは、現代世界において重要性が高まってきている。伝統的に人間の制御下に置かれていた多くのシステムが、コンピュータによって実行される自動制御の恩恵を受けるようになった。このことは、例えば工業生産ラインや航空機のオートパイロット機能などのほとんどの分野において明らかである。現代の計算処理プラットフォームによって提供される出力の処理能力や一貫性が高いため、システムをコンピュータ制御下に置く傾向が大きくなった。自律的挙動のレベルは、人間の介入に依存せず、システムの感知知能によってのみ制御される。
【０００３】
システムのいわゆる「知能的」な制御を強化するために、多くの場合、人工知能やファジー論理、ニューラル・ネットワークなどの計算処理概念が使用される。特に、いわゆる「エージェント」の発達が増大した。エージェントとは、本明細書に示したように、他のエージェントと自律的かつ知能的に交信することができるソフトウェア・オブジェクトである。
システムの重要な要素を識別し、次にそのような重要な要素を表す同じ特性と属性を有する特殊化したエージェントを作り出すことによって、システムをモデル化することができる。
【０００４】
資源割り当ての問題は、システム内のすべての資源と資源のすべての需要が予め分かっている場合はによく理解されており、既存の技術を使用して解決することができる。しかしながら、実際の市場の状態は、かなり乱れが大きく、多くの場合、資源の需要が頻繁かつ予測不能に変化しやすい。資源の割り当ては、動的である。そのような条件下では、資源を割り当てるアルゴリズムは、頻繁かつ急速な再割り当てに対応できなければならない。従来のプログラムは、そのような状態に対処することができない。
マルチエージェント・システムは、頻繁に変化する需要に対して資源を動的に割り当てかつ割り当てなおす有効な方法を提供する。
【０００５】
本発明の１つの目的は、システム内の資源の動的割り当てを可能にするモデリング技術およびそれに関連した構成要素を提供することである。
【発明の開示】
【課題を解決するための手段】
【０００６】
本発明の第１の態様によれば、仮想環境で交渉するように適応されたエージェントが提供され、このエージェントは、実行可能プログラムとして実現され、エージェントの交渉特徴を決定する１組の特性を含むエージェント記述子と、実行可能プログラムとして実現され、仮想環境から情報を受け取る少なくとも１つのセンサと、環境と連係する少なくとも１つのアクチュエータと、少なくとも１つのセンサから受け取った情報に基づいて意志決定プロセスを実行するために所定の期間能動状態で動作可能な決定エンジンとを含むエージェント本体とを含み、決定エンジンが、交渉特徴に依存して別のエージェントとの関係を確立し、確立した関係の質を表す値を決定するように動作可能である。
【０００７】
本発明の第２の態様によれば、前述のような複数のエージェントを含む仮想環境を作成することによって実環境をシミュレートする方法が提供され、この方法は、前記エージェントの少なくともいくつかに、所定の期間エージェントの能動状態を呼び出す段階と、各アクティブ・エージェントに、エージェントの交渉特徴に従って少なくとも１つのセンサから受け取った情報に基づいて意志決定プロセスを実施して、別のエージェントと関係を確立できるかどうかを判定する段階と、前記所定の期間の後で、エージェントの受動状態を呼び出す段階とを含み、前記エージェントが、自由の状態または対にされた状態を有し、対にされたエージェントが、確立した関係の質を決定する値を保持する。
【０００８】
本発明のさらに他の態様によれば、仮想環境で交渉するように適応されたエージェントを実現するためにコンピュータを操作する方法が提供され、この方法は、エージェントの交渉能力を決定する１組の特性を含むエージェント記述子を定義する第１のプログラムを実行する段階と、仮想環境から情報を受け取る少なくとも１つのセンサと、環境と連係する少なくとも１つのアクチュエータとを提供することによってエージェント本体を準備する段階と、前記少なくとも１つのセンサと関連付けられた決定エンジンを実現する第２のプログラムを実行する段階とを含み、前記決定エンジンが、エージェントの交渉特徴に従って少なくとも１つのセンサから受け取った情報に基づいて意志決定プロセスを実行するために所定の期間能動状態で動作可能であり、決定エンジンが、交渉特徴に依存して別のエージェントとの関係を確立し、確立した関係の質を表す値を決定するように動作可能である。
【０００９】
本発明のさらに他の態様によれば、需要と資源を管理するためにコンピュータ・システムを操作する方法が提供され、資源と需要の現在の状態を表すシーンを生成する段階と、実行可能プログラムとして、資源を表す第１組の資源エージェントと、需要を表す第２組の需要エージェントとを含む複数のエージェントをインスタンス化する段階とを含み、各エージェントが、別のエージェントとメッセージを交換するように動作可能であり、シーンからの情報と前記他のエージェントからのメッセージに基づいて意志決定プロセスを実行して、前記他のエージェントとの関係を実現しかつ前記関係と関係値を関連付ける決定エンジンを含み、さらに、その関係値を関係の基準値と比較して関係が満足かどうかを判定する段階を含む。
【００１０】
本発明のもう１つの態様によれば、実世界を表す仮想世界として構成されたコンピュータ・システムが提供され、システムは、実行可能プログラムとして実現され、実世界における需要を表す１組の特性をそれぞれ含む第１組の需要エージェントと、実行可能プログラムとして実現され、実世界における資源を表す１組の特性をそれぞれ含む第２組の資源エージェントとを含み、需要エージェントと資源エージェントが、メッセージを交換することによって交渉するように動作可能であり、前記メッセージが、各エージェントの需要と資源に対応する前記組の特性を含み、それにより決定エンジンが、所定の基準に基づいて関係を確立することができ、新しい需要または資源がシステムに参入したとき、新しい需要または資源を表すエージェントは、確立済み関係の質を表す値を改善する補償をオファーすることによって、１対のエージェント間の確立済み関係を乱すことができる。
【００１１】
本発明のさらにもう１つの態様によれば、複数のプログラムを実行するプロセッサを含むコンピュータ・システムが提供され、各プログラムは、仮想環境で交渉するエージェントと、複数のエージェント定義データを記憶するメモリとを表し、各エージェント定義データが、エージェントの性質を定義する１組の特性と、エージェントによる交渉のために使用される特徴を定義する１組の属性と、様々な意志決定プロセスを実施するためにエージェントによって実行可能な１組のシナリオと、エージェントによって確立された関係の質を定義する値を保持する関係質記憶機構とを含むオントロジを有する。
【００１２】
本発明をさらによく理解し、本発明をどのように実施できるかを示すために、次に、例として添付図面を参照する。
【発明を実施するための最良の形態】
【００１３】
本発明の好ましい実施形態を説明する前に、基本のとなる概念を簡単に説明する。仮想世界は、その名前が示唆する通り、実システムをシミュレートする試みにおいて作成される人工的なシステムである。本発明の状況における仮想世界は、要求に対する資源割り当てが行われるシステムである。そのような仮想世界は、実世界システムの様々な構成要素を識別し、次に特定の特性と属性を有するソフトウェア・オブジェクトを使用してその挙動を模倣することによって作成される。
そのようなソフトウェア・オブジェクトは、「エージェント」と呼ばれ、他のオブジェクトから受け取った情報を解釈して仮想世界を構築することができる。この種の仮想世界におけるエージェントを各需要と各資源に割り当てることができる。エージェントは、入力に基づいて、知識ベースの決定を行い、この決定は、次に仮想世界の他の要素に出力される。
【００１４】
ユーザがシステムを制御しその結果を利用できるように、この入力と出力が実世界すなわち物理世界との橋渡しをすることを理解されよう。実世界との橋渡しは、コンピュータ・システムの既知の任意の入出力装置の形をとることができる。
互いに関係を確立することができる特性と属性を有するエージェントを使用して仮想世界を作成することができる。仮想世界におけるエージェントは、他のどのエージェントとも関係を確立しない、いわゆる「フリー」エージェントでよい。この事例において、フリー・エージェントは、自分自身と他のエージェントとを突き合わせることによって他のエージェントと関係を確立しようとし、識別可能な特徴を使用することによって潜在的なパートナとして識別する。そのような突き合わせプロセスは、ネゴシエーションと呼ばれる。エージェント間の関係は、ネゴシエーションに対してすべてのエージェントが合意した場合だけ確立され、提案された関係が既定の基準を満たす場合だけ合意が認められる。この基準は、特定の特性、属性、値など、エージェント間のいくつかの特徴の一致でよい。これについて、以下で詳細に考察する。
【００１５】
システムを調べて一致を見つけるフリー・エージェントは、「能動（アクティブ）」状態になる。適切な一致が見つからない場合、エージェントは、「受動（パッシブ）」状態に切り換わり、仮想世界の状態の変化を待つ。ある瞬間での仮想世界の状態を「シーン」と呼ぶ。他のエージェントとの間に既に関係を確立しているエージェントは、受動状態に切り換わることがあり、これは、仮想世界の状態に変化があった場合に再び能動状態になることがあるためである。新しい「イベント」、すなわち新しいエージェントの生成を引き起こす新しい需要または資源の到着によって、「シーン」の変化が起こることがある。エージェントは、互いおよび仮想世界と「メッセージ」によって交信する。
【００１６】
エージェントは、「不満足」な関係においても「満足」な関係においても「自由」である。これらの用語の意味は、後で考察する。仮想世界の状態に変化があったとき、あるいは初期設定時、プロセスは、最初にフリー・エージェントが能動化され、次に不満足エージェントが能動化され、最後に満足エージェントが能動化されるシーケンスに従う。突き合わせのために、各エージェントは、突き合わせようとしている特性または属性の極小値と最大値を保持している。特徴を突き合わせようとしているエージェントは、必要な特定の特徴に優先順位を付けることができる。エージェントは、エージェント間に確立されている関係に関して特徴の各最大値が一致した場合に「満足」したと表現される。さらに、エージェントは、一致が、要求された特徴の値が最小値よりも大きいかまたはそれと等しいエージェントに対するものである場合に、「不満足」な関係を確立することができる。エージェントに要求された特徴の値が最小値よりも小さい場合は、エージェントとの関係は確立されない。したがって、不満足なエージェント間に関係が存在することがあるが、エージェントの不満足状態は、確立された関係を再検討する強い理由であり、そのようなエージェントは、次に、すべてのフリー・エージェントの適切な一致が確認された後で順番に検討される。最後に、満足なエージェントが、そのリンクを再検討するために能動化され、実現可能な場合には、総合システム値が大きくなるようにリンクが再び確立される。
【００１７】
エージェントの最大値は、例えば平均市場価格などのほとんど達成可能であると予想される総合平均システム値を反映するように設定することができる。しかしながら、平均システム値を容易に達成可能な値よりも高く設定して、既存の関係を破る補償を使用して、エージェント・ペアの自律的突き合わせ活動によってその値を達成できるかどうかを確認することができる。エージェント間に確立された関係を破るために、それらのエージェントに補償がオファーされる。補償は、再交渉された関係が、破られた関係よりも満足できる関係になる場合だけ受け入れられる。この結果、すべてのエージェントの活動に基づく集合的な値である総合システム値が上昇する。この総合システム値は、例えば、システムにとって最も重要と考えられる「売上総利益率」（すなわち、お金）や他の何らかの量である。しかしながら、総合システム値が、「ユーザの満足状態」や「時間」などの観点で測られることもあることを理解されたい。
【００１８】
不満足な関係が、あまり不満足でなくなるか満足になる可能性があることに注意されたい。また、補償のオファーによって最大値よりも高く一致させることによって、関係がより満足なものになる。
この実施形態は、エージェントの突き合わせ機能を使用することによって、時間が許す限りあるいはシステムに新しいイベントが参入するまで、総合システム値を常に最適化する効果を有する。最初にフリー・エージェント、次に不満足なエージェント、最後に満足なエージェントを突き合わせようとする線形ネゴシエーション・ストラテジは、強力な実行プラットフォーム上で実行された場合は特に効率的であり、エージェントは、システムを最適化する作業をし続けることができる。しかしながら、ほとんどの実システムの動的性質のために、多くの場合、新しいイベントごとにエージェント活動期間を制限しなければならない。
【００１９】
図１は、資源（灰色で表したＲ）エージェントと需要（白で表したＤ）エージェントからなる仮想世界の１つのシーンを示す。関係の確立に関心をもつ７つのエージェント１００、１０２、１０４、１０６、１０８、１１０、および１１２が示されている。需要エージェント１００は、資源エージェント１０２と関係を既に確立している。この関係は、実線１０１によって示したように確立されている。笑顔は、両方のエージェントが満足していることを示す。需要エージェント１０６から資源エージェント１０４および１０８に、２つの点線１０５、１０７がそれぞれ延びている。点線は、これらのエージェントがネゴシエーション中であるが、有効な関係がまだ確立されていないことを示す。笑顔は、エージェントが、提案された関係にその時点で満足していることを示す。第３に、資源エージェント１１０が、需要エージェント１１２との関係を確立しようとしている。この関係は、関係がまだ確立されないことを示す点線１１１で示されている。さらに、悲しい顔は、エージェント１１０と１１２が良好な一致を見ておらず、現時点でより良い関係がないことを示す。
【００２０】
需要エージェントと資源エージェントのどちらが能動的でもよいことに注意されたい。すなわち、関係１１１の場合、資源エージェント１１０は、交渉を開始しており、これは、図１の他の関係１０７、１０１、１０５と大きく異なることを理解されたい。これは、多くの場合、特に買手市場において好まし戦略であり、これは、実際に図１のシーンに当てはまる。すなわち、需要エージェント（買手）１００、１０６、１１２よりも資源エージェント（売手）１０２、１０４、１０８、１１０が多く、これは、突き合わせプロセスで検討される買手が少ないことを意味している。
【００２１】
関係が一旦確立されると、そのような関係は、双方の合意によってしか破棄することができない。したがって、図１において、システムに新しい需要が参入した場合は、前に割り当てられていた資源エージェントを新しい需要エージェントと突き合わせることが最適か検討されることがある。しかしながら、この場合、すべてのエージェントが合意することが必要になり、既存の関係を修正するために、元の需要エージェントに補償をオファーする必要がある。
ここで、自己組織化の原理についてより詳しく考察する。自己組織化システムにおける動的資源割り当てに関して、ｎ個の資源をｍ個の需要に割り当てるタスクが与えられたマルチエージェント・システムを検討する。好ましい実施形態において、各資源は、ｆ個の１組の特徴によって特徴づけられており、通貨単位（ミュー）で表された値を有する。各需要は、ｇ個の１組の特徴によって特徴づけられており、やはりミューで表された購買力を有する。一般に、需要は、システムに１つづつ到達し、到達時間とその特徴は予測不可能である。資源は、一定の場合もあり時間と共に変化する場合もある。
【００２２】
動的資源割り当てを実施するアルゴリズムの基本的な例は、以下の段階を含む。 
１．需要がシステムに到達したときに、エージェントが需要に割り当てられる。割り当てられた需要エージェントは、その特徴をメッセージで、特定数の通貨単位で支払うことができる特定の特徴を有する資源を要求しているすべてのフリー・エージェントに送る。
２．要求された特徴を有するかまたはそのような特徴の少なくともいくつかを有する資源を有するすべてのフリー資源エージェントが、需要エージェントにオファーする。
３．次に、需要エージェントは、そのオファーから最も適切な資源エージェントを（特徴に基づいて）選択し、一致が確立される。
４．適切なフリー資源エージェントがない場合、需要エージェントは、確立済みの関係と関連した不満足な各需要エージェントと再交渉するか、あるいは既に確立済みの関係を修正するために満足な各需要エージェントに補償をオファーすることによって、前に割り当てられている資源エージェントから適切な資源を獲得しようとする。
５．次に、補償のオファーが行われた需要エージェントは、そのオファーを検討する。需要エージェントは、その補償によって、改善された一致基準すなわち最大値に近い（あるいは、それよりも高い）基準を有する別の適切な資源を取得できる場合だけ、そのオファーを受け入れる。補償のオファーを受け入れた場合、これは、システム全体を有効に再編成する効果を有し、元の需要エージェントと資源エージェントの間に前に確立済みの関係が修正され、新しい需要エージェントと開放された資源エージェントの間に新しい関係が確立される。
６．プロセス段階１〜５は、すべての資源が需要にリンクされ、確立済みの関係を改善できなくなるか、あるいは割り当てに使用できる時間期間が終了するまで繰り返される。すなわち、以上のプロセスは、限られた時間期間内で最適な資源割り当てが達成されるまで繰り返される。
【００２３】
ある瞬間において、エージェント間の関係が満たされておりシステムが平衡状態にあるシーンが存在する可能性のある状況を検討する。しかしながら、後になって、システムに新しいイベントが入力される。そのようなイベントは新しい注文でよく、そこで、この注文のために需要エージェントが作成され、システムは、自律的にエージェント間の既存の関係を修正しかつ／または新しい関係を確立して、最終結果は、総合システム値を高める。マルチエージェント・システムにおいて関係を自律的に再交渉するこの機能は、「自己組織化」として知られる。マルチエージェント・システムは、ある瞬間において平衡状態にあるシステムを有し、資源と需要が適切に一致している。次に、新しい需要などのイベントがシステムを乱した場合、システムは、自己組織化を実行することにより資源を動的に割り当て、その後でシステムは再び平衡状態になるが、このとき、既存の関係を有するエージェントに補償をオファーすることにより総合システム値を最適化する影響によって関係が修正されていることがある。
【００２４】
資源の動的割り当ては、資源を割り当てる必要がある場合、またはそのような資源のための需要が、割り当てプロセスにおいて予測不能に変化する場合である。動的資源割り当ての例は、以下の通りである。
・生産ロジスティクス。これは、例えば組立ロボット、コンベヤ、金属加工機械などの生産設備に材料または部品を割り当てることに関係する。ロジスティックス・アプリケーションは、部品を時間と空間で指定することを必要とする高い複雑さを有することがあり（後を参照）、あるいは製品仕様に頻繁な変更が行われる可能性がある。
・電子商取引。これは、顧客または供給業者が割り当てプロセスに予測不能に参入したり参入をやめたりするときの顧客要求（需要）への品物またはサービスの割り当てに関係する。
・スタッフ・スケジューリング。これは、きわめて動的な市場で作業する業務スタップへのタスクの割り当てに関連する。
【００２５】
次に、最初の２つのアプリケーションについて、詳細に説明する。
図２は、１つの実施形態による仮想世界シーンの論理的アーキテクチャを示し、ここで、どの仮想世界シーンも、二重にリンクされたリストによって定義されている。このような論理的アーキテクチャは、そのようなシーンの様々な要素を実行するためにプロセッサによって使用される。リスト２５２および２５４によって定義された第１のシーン２５０を検討し、ここで、第１のパネル・リスト２５２が、シーンで使用されているエージェント記述子１〜Ｎのリストであり、第２のパネル・リスト２５４が、シーンにおけるエージェント間の関係１〜Ｍのリストである。また、関係２６４、２６８、２７０は、関係のリストの状況を含む。したがって、図２は、第１のエージェント２５８と第２のエージェント２６０の間に第１の関係２６４があり、その関係が、確立された接続であり、一方、複数の他のエージェント間に第２の関係２６８があるが、その状況は、ネゴシエーションが適切なエージェント間で続いているが、確立された関係にまだ到達していない予約段階にあることを示している。
【００２６】
これらの二重にリンクされたリスト２５２、２５４の結果として、プロセッサが、すべてのエージェント２５８、２６０、２６２、または関係２６４、２６８、２７０からその隣りに進むことができる。この実施形態の論理的アーキテクチャは、これらのリストが互いに参照することを可能にし、それにより、エージェントは、自分の関係を見つけることができ、またその関係を確立した他のエージェントも見つけることができる。この実施形態において、プロセッサがシステム・ディスパッチャへの実行キューの探索時間を短縮するために、エージェント・パネル２５２と関係・パネル２５４は、能動的エージェント、受動的エージェント、満足エージェント、および不満足エージェントのパネルに分けられる。システム・ディスパッチャは、エージェント動作のクロック・サイクルを生成し、仮想世界シーンのオブジェクトの実行を制御する役割を持つ。
【００２７】
図３に示したような飛行船貨物輸送システムの特定のロジスティックス・アプリケーションを検討する。ロジスティックス・アプリケーションの場合、それぞれの範囲の立地と経路の縮小マップを必要とするスペースや時間などの追加の要素を検討し、また資源を需要にいつ割り当てるべきかを検討しなければならないことがある。図３は、飛行船に積み降ろしするためのサイト１２０、１２２、１２４、１２６、１２８、１３０、１３２のネットワークが存在する飛行船貨物仮想世界のロジスティックス・マップを示し、各サイトは、大文字Ａ〜Ｆで示されており、中央サイトは、文字０で示されている。また、これらのサイト間の経路は、それぞれの寸法ｄ１、ｄ２、およびｄ３で示されており、この場合、ｄ１＝５００ｋｍ、ｄ２＝２５０ｋｍ、およびｄ３＝１５０ｋｍである。サイト間で貨物を輸送するために２つの飛行船が使用される。エージェントは、これらの各飛行船の割り当てられ、本明細書では、それぞれ「Ａ１」と「Ａ２」と呼ばれる。 
図４は、本明細書において「Ｏ１」と呼ばれる新しい注文が割り当てられたエージェントと、エージェントＡ１およびＡ２との間で行われるネゴシエーションを示す。
【００２８】
エージェントＡ１で表された飛行船は、１００トンの貨物船積載力を有し、１０ｋｍ／時間で移動し、７ミュー／ｋｍの比較的高い運転経費を有する。エージェントＡ２で表された飛行船は、１０トンの貨物船積載力を有し、１５ｋｍ／時間で移動し、３ミュー／ｋｍの運転経費を有する。
状況１： 
９月１５日に、システムは、サイトＡからサイトＤ（距離５００ｋｍ）に５トンの貨物を輸送する１５０００ミューの注文を受け取る。貨物がサイトＤに到達する期限は、９月２０日である。Ａ１は、フリーでありかつサイトＥに配置されており、Ａ２は、現在、前に受け入れた注文をサイトＣに輸送している。作業の計画を立てるために、第１の注文エージェントＯ１が作成され、注文に割り当てられる。エージェントＯ１は、必要な貨物輸送の詳細を有する要求をＡ１とＡ２の両方に送る。その要求を検討した後で、各飛行船は、そのオファーをＯ１に送る。
【００２９】
Ａ１は、輸送をすぐに開始する用意ができている。注文を受けるために、飛行船は、サイトＥからサイトＡまで（３００ｋｍ）を移動しなければならない。このコストは、（３００＋５００）×７＝５６００ミューであり、実行に必要な時間は、（３００＋５００）／１０＝８０時間、すなわち約３．５日である。したがって、Ａ１は、９月２０日の期限を守ることができる。Ａ２は、まずその現在の輸送タスクを完了し、次にサイトＡに移動して、新しい注文Ｏ１の実行を請け負う。Ａ２が現在サイトＯにある場合、Ａ２は、経路Ｏ−Ｃ−Ｏ−Ａ（７５０ｋｍ）をカバーし、次にＡからＤ（５５０ｋｍ）に移動して注文Ａ１を完了しなければならない。実行するために必要な時間は、（２５０＋２５０＋２５０＋５００）／１５＝８３．３時間であり、すなわち、やはり約３．５日であり、したがってこの場合も期限に間に合う。コストは、（２５０＋２５０＋２５０＋５００）／１５＝４５００ミューになる。
【００３０】
Ａ１とＡ２は両方とも、５トンの貨物を処理することができ、両方のエージェントは、９月２０日の期限を守ることができる。したがって、検討すべき基準は、コストの高いエージェントはどちらかということである。結果は、４５００ミューでＡ２が最も安価であり、その結果利幅が１５，０００−４５００＝１１，５００の大きく、それに対してＡ１では、利幅は、わずか１５，０００−５６００＝１０，４００ミューである。
図４は、エージェント間のネゴシエーションを示し、線１４１は、Ｏ１からＡ１に送られる問合せを示す。線１４６は、Ａ１からの応答（オファー）を示す。線１４８は、Ａ２に送られる問合せを示す。線１５０は、Ａ２の予約と、エージェントＯ１とＡ２の間に確立された関係を示す。
状況２： 
次に、１時間後に、貨物の新しい注文をシステムが受け入れられ、本明細書において「Ｏ２」と呼ぶ新しい注文エージェントに割り当てる事例を検討する。すなわち、２０，０００ミューのために８トンの貨物をポイントＣからポイントＢ（１５０ｋｍ）に輸送しなければならない。期限は、９月１７日である。Ａ１は（５００＋１５０）／１０＝６５時間、すなわち約３日を必要とし、したがって９月１７日（２日後）の要求期限を守ることができないので、Ａ１は期限を守ることができないため、この注文を実行できるのはＡ２だけである。これと対照的に、Ａ２は、この注文を完了するのに（２５０＋１５０）／１５＝２３．３時間、すなわち約１日しか必要としない。
しかしながら、Ａ２は、前の状況１においてＯ１によって既に予約されている。
【００３１】
したがって、エージェントＯ２からエージェントＡ２への問合せの結果、以下のネゴシエーションが行われる。
・Ａ２は、Ｏ２を受け入れそれに応じて無指定の補償をオファーするために、前に確立済みの関係から開放される許可を要求するメッセージをＯ１に送る。
・Ｏ１は、Ａ１およびＡ２と再び連絡をとって要求の受け入れを試み、期限に間に合うが費用の高い選択肢（１０４００ミュー対１１５００ミュー）として前に拒否された状況１と同じオファーをＡ１から受け取る。
・Ｏ１は、差すなわち１１００ミューを補償することをＡ２に依頼する。
・エージェントＯ２は、Ａ２によって渡される補償の要求を検討する。Ｏ２が、Ａ２との関係を確立する場合、Ｏ２の利益は、２００００−（２５０＋１５０）＊３＝１８９５０ミューになる。したがって、Ｏ１に１１００ミューが支払われる補償は、Ａ２が契約１８９５０ミューから得ることを期待する利益の点から受け入れ可能である。
【００３２】
図５は、システムの全体的な結果が改善されるシステムの自己組織化のネゴシエーションを示す。線１５４は、Ｏ２からＡ２に問合せを示す。線１５６は、Ａ２からＯ１への再予約のための提案を示す。線１５８は、Ｏ１からＡ１への問合せを示す。線１６０は、Ａ１からＯ１への肯定応答を示す。線１６２は、Ａ２を再予約するためにＯ１によって与えられる許可を示す。
線１６４は、Ａ２からＯ２に送られるオファーＯ１の補償を示す。
要するに、Ａ２が再予約され、Ａ１がＯ１との関係を確立し、これにより、Ａ２は、システムの総合値を改善する関係をＯ２と確立することができる。
【００３３】
次に、電子商取引を含む第２のアプリケーションについて説明する。
自分の倉庫と自動車を納品する輸送手段を有するドイツとブラジルの販売業者の国際的ネットワークを使用してインターネット・ポータル上で自動車を販売する例を検討されたい。エージェントが、注文、販売業者、倉庫、輸送ユニット、輸送スロット、輸送負荷、および自動車にそれぞれ割り当てられる。これらのエージェントは、既存の電子商取引システムの場合と同じように自動車を販売できるだけでなく、動的に変化する環境で自己組織化することもでき、それによりすべての顧客の要求を満たしながら総合システム値が高まる。より詳細に後で説明するように、エージェントは、確立済みの関係（すなわち、契約）の取り消しあるいは買手と売手の許可による確立済みの関係の修正を実行することによって自律的に活動できるのに十分な知能を有する。
【００３４】
図６は、電子商取引アプリケーションを示す。第１の注文２１２は、ブラジルにいる第１の顧客からの、価格５００００ミューの赤いメルセデス・キャブリオレ２０２の注文である。自動車は、既に支払いが完了しており、現在顧客の家から３００メートルにあり、ブラジルの販売業者２１４からトラックによって配達されている。第１の顧客は、この自動車を既に１ヶ月間待っている。
ドイツ内の第２の顧客が、急に全く同じ自動車を持ちたくなり、第２の注文２１０を出す。ドイツ内の販売業者２０４、２０６、２０８は、その倉庫２０４、２０６、２０８に第２の顧客の要求と一致するこの自動車のモデルを見つけることができない。そこで、マルチエージェント・システムは、赤いメルセデス２０２を第２の顧客に納品するために、第１の顧客に、拒否することが困難な代替オファーを生成することを試みる。
【００３５】
これを達成するために、第２の注文エージェント２１０は、自動車エージェント２０２（すなわち、赤いメルセデス）に、補償が指定されておらず顧客を変更することを勧めるオファーと共にメッセージを送る。次に、自動車エージェント２０２は、第１の注文エージェント２１２に、顧客を変更する許可を求めるメッセージを送る。これに応じて、第１の注文エージェント２１２は、それ自体と自動車の所有者の利益を考慮する状況を検討する。まず、第１の注文エージェント２１２は、ブラジルの販売業者２１４に問い合わせて、同じ特徴を持つ新しい自動車をどれだけ早く納品できるかを調べる。新しい自動車が１か月以内に納品できると仮定すると、これにより、第１の顧客の待機期間は２倍になる。比例補償の単純なシナリオ戦略（後を参照）に従って、注文１エージェントは、自動車の納期が２倍になる補償として、５０％の割引を第２の注文エージェント２１０に求める。契約の許可を得るために、第１の注文エージェント２１２は、第１の顧客と、例えばその顧客のＷＡＰ電話に電話して連絡を取り、もう１ヶ月待つ契約と引き換えに５０％割引をオファーする。第１の顧客が、もう１ヶ月待つことに合意した場合、第１の注文エージェント２１２は、最初の赤い自動車２０２の予約を取り消し、新しい自動車２２０を予約する。次に、第２の注文エージェント２１０は、自動車の最初の価格と補償の金額を加えたもの、すなわち５０，０００＋２５，０００＝７５，０００ミューと等しい価格で自動車２０２を予約する。
【００３６】
次に、第２の注文エージェント２１０は、自動車をドイツに２週間以内に送り返すために航空会社と交渉しなければならない。航空会社が合意したと仮定すると、すべてのフライトが完全に予約済みの場合でも、大きな貨物積載量を表す他のエージェントと、補償と引き換えにその輸送スロットをあきらめるネゴシエーションを行うことができる。したがって、空輸の補償が合計で４０００ミューになると仮定すると、自動車の総コストは、５０，０００＋２５，０００＋４，０００＝７９，０００ミューになる。
この価格は、ドイツ内の第２の顧客にオファーされ、この顧客は、ネゴシエーション・レポートを受け取り、必要に応じて決定木（注文の緊急度を考慮する）を参照する。次に、第２の顧客は、このオファーを受け入れるかまたは拒否することができる。その顧客が受け入れた場合は、第１の顧客の家に自動車を納品しているトラック運転者が、空港に経路を変更し、自動車を指定されたドイツ行きのフライトに載せる。顧客が拒否した場合は、達成された関係がすべて取り消され、最初に確立された関係に戻され、すなわち、自動車は、計画通り第１の顧客の家に納品される。
【００３７】
補償が受け入れられ、両方の注文が首尾良く実行された場合、エージェントは、取り引きの各関係者（すなわち、顧客１、顧客２、航空会社など）の需要を満たすことによって追加の利益を得る。したがって、自己組織化プロセスによって、本発明は、市場関係者間の関係に関する動的変更を達成することができる。
電子商取引アプリケーションの十分な利益を得るために、理想的には、固定された価格や固定された引渡条件があってはならず、あらゆるものが顧客の要求に依存しなければならないことを理解されたい。
【００３８】
前に例示し考察したような自己組織化を実行する可能性を実現するために、特定のエージェント・アーキテクチャについて説明する。図７は、エージェント記述子４とエージェント本体６の２つの主要部分を有する基本的なエージェント・アーキテクチャを示す。エージェント記述子４は、エージェント２の１組の特性８、１０、１２あるいは他のエージェントとの関係を含む。エージェントの特性は、エージェントの性質を決定する。エージェント特性は、様々なシナリオ１４を参照することができる。各シナリオは、エージェントのコマンド・メモリ１４部分にあるあらかじめプログラムされた手順として実現することができる（図８を参照）。エージェントは、最適の結果を生成するのがどのシナリオになりそうかを選択することができる。シナリオは、他のエージェントと望ましい関係を確立するように情報を提供したり、突き合わせのための特性の適性を確認する値を計算したりすることができる。
【００３９】
各特性１０は、突き合わせのために１組の属性１６を参照することもできる。例えば、電子商取引アプリケーションにおける自動車エージェント２０２は、特性「色」と、この特性に割り当てられた属性「赤」を有する。エージェント２は、読み取ることができる特定の部分を有し、例えば、エージェント記述子４を「公開」することができる。図７に示した例では、他のエージェントが、いわゆる「視覚センサ」を有する場合にこの特性を読み取ることができるように、特性８が公開される。エージェント記述子４の他の部分、例えば特性１０および１２は、公開されていなくてもよく、要求があるときだけエージェントによって公開されてもよい。
【００４０】
視覚センサは、エージェント記述子４の公開データ・フィールドを読み取るために、エージェントによって使用される機構である。一般に、感知機構は、エージェント本体に組み込まれたソフトウェア手順とデータ構造からなるか、あるいは、システム内のどこか他の場所に保持された基本クラスから必要に応じてビジョン・センサ機構をエージェントに移すことができる。また、ビジョン・センサ機構は、エージェント記述子の特定の公開部分だけを読み取ることができるように、視覚を規制するフィルタを有することができる。
図８は、エージェント本体６の構成要素を示す。エージェント本体は、センサ２０、アクチュエータ２２、シーン・メモリ２４、意志決定機械２６、オントロジ・メモリ２８、事実メモリ３０、およびコマンド・メモリ１４を有する。センサ要素２０の例には、タイマ、ビジョン・センサ、メールボックス機構などが含まれる。これらのいくつかは、他のエージェントと対話し、いくつかは、実世界と対話する。アクチュエータ２２は、ＷＡＰ電話、電子メール、エージェントのデータ・ベースにアクセスする手段などを含むことができる。したがって、これらによって、確立された関係を現実の物質界で実現することができる。オントロジ・メモリ２８は、エージェントが所有する知識ベースである。オントロジについては後でより詳細に考察するが、オントロジは、「汎用」知識ベースまたは「ドメイン固有」知識ベースの２つのカテゴリに分けることができる知識ベースとして広義に考えることができる。ほとんどのエージェントは、汎用知識ベースによってかなり適切に動作することができるが、特定のアプリケーションでは、例えば自動車生産アプリケーションでは、多数のドメイン固有知識ベースを使用するほど効率的であることが分かった。エージェントが周囲の仮想世界の概念を有するように、センサ２０を使用してシーン・メモリ２４を構成することができる。意志決定機械２６は、エージェント本体の核であり、他の要素のほとんどとつながっている。意志決定機械２６は、自分自身の知識を使用して、受け取った入力に基づいて決定を行い、出力するために必要な手順を実施する。決定に至る際に、意志決定機械２６は、特定の状況に好ましいアクション・シナリオ１４を選択することができる。特定のアプリケーションでは、シーン・メモリ２４を必要とする可能性があるが、ほとんどの単純なアプリケーション（例えば、電子メール・アプリケーション）では、エージェントは、ネットワークの汎用オントロジ・メモリ２８しか必要としない。
【００４１】
各エージェントの動作は、例えばこの実施形態では３００ピコ秒のクロック・サイクルに基づく。このクロック・サイクルは、システム・ディスパッチャ（図示せず）によってすべてのエージェントに割り当てられる。システム・ディスパッチャは、固有でかつ独立のソフトウェア・オブジェクトと見なすことができ、これは、エージェントの活動を組織化するためにプロセッサ上で実行される。システム・ディスパッチャは、仮想世界において他のエージェントに特定の情報を提供することができる。例えば、エージェントが、仮想ビジョン・センサを持ちたい場合は、需要エージェントに適切なソフトウェアを送る要求をシステム・ディスパッチャに行うことができる。
【００４２】
図９は、エージェント動作サイクルのステップを説明するフローチャートを示す。ステップＳ４０は、エージェントがシステム・ディスパッチャからクロック・エッジを受け取ったときのエージェント動作サイクルの開始を示す。シーンにおける活動状態のエージェントはすべて、各クロック・サイクルで並列に動作することによって同期して動作する。ステップＳ４４で、各エージェントは、そのシーンにおいて重要なイベントが発生したかどうかを判定する。この判定は、入力センサによる影響を受け、図９では、メールボックス入力センサＳ４２を有する単純なエージェントを示す。各エージェントは、ステップＳ６０からクロック・サイクルが終了したかどうかの確認を行い、Ｓ４２でメールボックスから入力を受け取る。シーンに新しいイベントがある場合は、ステップＳ４６で、現行シナリオが遅延され、ステップＳ４８で、エージェント・オントロジ２８に基づいて新しいシナリオを選択する。すなわち、エージェントは、オントロジに基づいて、新しいイベントを処理するために、最も適した他のシナリオを実行するように決定することができる。ステップＳ４４でシーンに新しいイベントがない場合、エージェントはＳ５４に進み、そこで、現行シナリオの次のコマンドを選択する。また、ステップＳ５０の終わりで、新しいシナリオを実行した後、エージェントは、Ｓ５４に進む。ステップＳ５６で、現行シナリオの次のコマンドが実行され、電子メール・アクチュエータ機構２２に出力される。ステップＳ６０で、エージェントは、クロック・サイクルが終了したかどうかを確認する。終了していない場合、アルゴリズムはステップＳ４４に戻り、そこで、エージェントは、シーンに何か他の重要なイベントが参入したかどうかを確認する。クロックが終了した場合、ステップＳ６２は、エージェント動作サイクルの終わりに達したことを規定する。
【００４３】
説明したように、図９のエージェントの実施形態は、唯一の入力センサとしてメールボックスを有し、唯一のアクチュエータとして電子メールを有する。そのような単純なエージェントでは、シーン・メモリ２４を有する必要はなく、むしろ汎用エージェント・オントロジ２８で十分な可能性が高い。しかしながら、もっと複雑なアプリケーションの場合、例えば前に説明したロジスティックスの例では、オントロジ・メモリ２８の他にシーン・メモリ２４が必要になる。シーン・メモリを使用しない場合、そのようなエージェントは、仮想世界に他にエージェントがいくつ存在し、どの種類のエージェントがあるか分からなくなる。
【００４４】
仮想意志決定機械２６は、エージェント本体のコア要素であり、他の要素と直接的または間接的につながる。意志決定機械２６は、各エージェントが、その記述子を比較することによって、１組のそのようなシナリオから特定のシナリオを選択することを可能にする。シナリオ記述子は、完全シナリオの概要を提供するソフトウェア・コードの短縮部分である。意志決定機械２６は、オントロジおよび／またはシーン・メモリを使用するシステムの現在状況を考慮し、そこで、必要な基準を最も効率的に満たす特定のシナリオが最終的に選択される。選択されたシナリオは、次に、複数のコマンドとして実時間で活動化され実行される。したがって、例として、１つのシナリオは突き合わせアルゴリズムであり、別のシナリオは、補償をオファーすることなどである。
【００４５】
オントロジ・メモリ２８は、知識ベースであり、以下に関する知識が記憶されている。
１．オブジェクト 
２．関係 
３．特性 
４．シナリオ
５．属性
メタオントロジは、すべての知識ベースの記述であり、オントロジの全体構造を記述する。図１０は、エージェント・オントロジの基本要素が相互接続されている様子を示す。より具体的には、メタオントロジは、ノードとして図１０の四角いボックスに示された基本要素と、解釈のために実際のシナリオ１４と共に矢印で示されたものの間の様々な関係とを有するセマンティック・ネットワークである。これらの要素と関係は、マルチエージェント・システムを実行するために必要なすべての知識を含む。メタオントロジを使用すると、どのドメイン知識も要素とシナリオのネットワークとして構成することができる。例えば、前に説明したロジスティックスおよび電子商取引アプリケーションにおいて、オントロジは、注文された製品の仕様、製品のタイプ、その製造に必要な時間、必要な部品、倉庫に部品を保管する条件とコストなどを含む。
【００４６】
オントロジ・メモリの特定の部分は、すべてのエージェントに共通の知識を含む。例えば、生産時間とコストを含む部品のカタログを含むオントロジは、共通知識である。この共通知識は、システム・ディスパッチャなどのシステムに共通の要素内にあってもよく、あるいは、この知識は、各エージェントのオントロジ・メモリ２８に入れられてもよい。各エージェントが、専用オントロジ・メモリを含むので、このメモリに対する個別のアクセスを提供することができ、このメモリにアクセスしようとするエージェントの衝突を防ぐ。
【００４７】
例として、図１１に自動車エージェントの一般化したオントロジを示した電子商取引アプリケーションを検討されたい。自動車エージェント７０は、モデル７２、価格７６、および色７４の３つの特性を有するように示されている。また、自動車７０は、関係７８および８０からなる。関係７８は、車体８２、エンジン８４、および自動車フレーム８６である自動車７０の特性からなる。自動車は、また、高級モデル８８、標準モデル９０、およびスポーツ・モデル９２の特性のうちの１つの特性でよいモデル範囲からなる関係８０を有する。価格特性７６は、１組の割引計算操作シナリオ１４を含むように示されている。次に、エージェントは、必要な割引計算によって必要なシナリオを選択することができる。価格特性７６は、例えばＵＳ＄１０，０００からＵＳ＄２５，０００までの、例えば見込み客が受け入れるであろう価格範囲を提供する価格属性９４を含む。
【００４８】
図１１に示したオントロジのためにエージェントが選択できる様々な割引シナリオ１４があることが理解されたい。例えば、この電子商取引アプリケーションでは、比例割引戦略が選択され、自動車の納期を２倍にする補償として自動車価格を半分にする割引がオファーされた。しかしながら、例えば、それまでに自動車を購入した回数による「常得意」割引、１つの注文で購入する自動車の数による「大量販売」割引、顧客が代金を前払いするが納期の遅れを受け入れることができる「納期遅延購入」割引、または自動車価格が競合相手の価格に匹敵するかまたはそれより低い「競合価格」割引などの割引シナリオも可能である。
【００４９】
アクション・シナリオ１４は、それぞれのシナリオに記憶される意志決定規則を含むこともできる。例えば、シナリオが、収益性の評価またはユーザによって定義された評価基準規則に基づく資源割り当ての規則を含むことができる。
仮想意志決定機械２６は、エージェント・アーキテクチャのコア要素である（図７を参照）。機械２６は、好ましい実施形態において、１組の手順およびデータ構造として実現される。手順は、基本データ構造およびエージェントに要求されたアクションを操作するために作成される。それは、例えば、エージェント間の情報交換の組織化、供給と需要の変遷パターンに関する情報の収集、エージェント間の接続の検索、最良接続の選択、決定およびシナリオの実行、状況が変化した場合の再検討である。
【００５０】
前に説明したように、各エージェントは、その特性とそれらの属性のリストによって示される。各エージェントは、属性を有する特性を持つことができ、各属性が値を持つことができる。あるいは、特性も値を持つことができる。したがって、図１１の例において、ＣＡＲエージェント７０は、１０，０００ドル〜２５，０００ドルの属性「価格範囲」９４を有する「価格」特性７６を有し、特定の自動車では、平均自動車の価格は１５０００ドルである。したがって、エージェントは、＜特性１＝属性１＞，＜特性２＝値１＞，．．．などのデータ構造を有することができる。エージェントの特性、属性、および値について知るために、エージェントは、あるエージェントが別のエージェントに、そのエージェントが特性１を有するかどうか、他のエージェントが特性１に割り当てられた属性１を有するかどうかなどを尋ねるようなメッセージを交換することができる。
【００５１】
いくつかの特性を、それらの特性が他のエージェントから見えるように「公開」することができる。これにより、必要とされる要求メッセージの数とシナリオ・ロジックの複雑さが減少する。意志決定は、エージェントの特性および属性を「洞察」または「推論」することによってメッセージから、あるいはエージェント・オントロジから収集した情報に基づいて実行される。エージェント・オントロジは、一般に、総合的な仮想世界モデルに関する知識を含み、シナリオにより様々な状況におけるエージェント挙動を制御する。
意志決定するための代表的なデータ構造は、受け取った提案に関する情報とオファーのテーブルである。図１２に、ロジスティックス・アプリケーションにおける需要エージェントのそのようなテーブルの例を示す。この単純な例では、製品クラス、コスト、および納期の３つの特性だけを示す。
【００５２】
図１２のテーブルの構造は、エージェントに定義された特性の数によって異なる。仮想意志決定機械は、テーブルの作成／削除、フィールドの定義または消去、フィールドによるオファーのソート、パターンを使用した文字列の探索などの基本的なテーブル操作を実行することができる。
最も重要なステップは、最良のオファーを選択することである。この手順は、きわめて複雑なことがある。最も単純なケースは、需要と供給間に完全一致があるときであり、したがってこの実施形態では、両方の資源エージェントが、需要エージェントから要求されたすべての特性を含むとき、すなわち、製品クラス、価格および納期がすべて一致するときである。さらに複雑なケースは、合意メトリクスによって評価されたときに需要と供給が互いに近いとき、すなわち部分的に一致するときである。部分的（不満足）な一致は、特性のうちの１つが一致したときであり、例えば、資源エージェントが同じ製品クラスを有するがコストと納期を満足させることができない場合である。
【００５３】
好ましい実施形態において、需要特性と資源特性を突き合わせるために、需要エージェントは、エージェント特性とその値を突き合わせるために必要な基準を示す要求を送る。例えば、要求メッセージは、「特性Ａ１が値Ｚ１で重要度Ｂ２１、特性Ａ２が値Ｚ２で重要度Ｂ２を有するＡクラスの資源があるか」などである。この照会は、１組のエージェントに向けられてもよく、すべてのエージェントに同報通信されてもよい。次に、資源エージェントは、オントロジ・メモリ内の対応する資源の特性とその属性を確認し、応答する。それらの特性と属性が、要求で示されたものと一致しない場合でも、部分的一致の候補として資源をオファーすることができる。
【００５４】
優先順位に基づいて需要と資源の特性を突き合わせるには、以下のような２つの方法がある。
１．最も優先度の高い特性から始める特性の順次突き合わせ。最初の需要エージェントが、資源エージェントに、メッセージ「こちらはクラスＮの需要エージェントです。名前Ｓ１を持つクラスＮの資源エージェントがある場合は、そちらの値を指定してください」を送ります。この応答を受け取った後、需要エージェントは、「特性値」データ構造テーブルを作成する。そのテーブルから１つまたは複数の適切なオファーを選択し、そのエージェントに、質問「特性Ｓ２がありますか。ある場合は、その値は何ですか」を送る。この突き合わせ実行方法は、エージェントが、重要な方の特性から重要でない方の特性に進み、部分的一致戦略を適用し（すなわち、重要度の小さい特性に注意を払わない）、比較演算の数を減らし、非公開の特性値を隠したままにし、交渉戦略または市場状況に従って（例えば、競合相手の数が変化した場合）、アクセス可能性を変化させる。
２．媒介者による平行突き合わせ。需要エージェントは、公開および非公開の特性を媒介者に開示し、媒介者は、指標を計算し、それをエージェントに戻す。エージェントは、他のエージェントの特性の正確な値を知らないが、指標によって示されたその類似度または相違度は知っている。
【００５５】
図１３は、エージェント間のネゴシエーションのステップの実施形態を示す。ステップＳ３００で、関係を確立するシナリオが実行され、ステップＳ３０２で、需要エージェントが、そのオントロジ・メモリ２８から、適切なリエージェントのリストを読み取る。次に、需要エージェントは、ステップ３０６で、すべての適切な資源エージェントに要求メッセージＳ３０８を送る。ステップＳ３０６は、仮想世界シーンＳ３０４に何か変化がある場合に実行されることもある。ステップＳ３１０で、需要エージェントは、資源エージェントＳ３１２からの応答を待つ。次に、ステップＳ３１４で、図１２に示したような意志決定テーブルがまとめられる。ステップＳ３１６で、最良のオファーを選択することができ、ステップＳ３１８で、選択された資源エージェントＳ３２０との関係を確立するための要求メッセージが送られる。ステップＳ３２２で、需要エージェントは、資源エージェントＳ３２４からの応答メッセージを待つ。Ｓ３２６で応答が否定の場合は、ネゴシエーション手順はステップＳ３１８に戻り、需要エージェントが、次に最良の資源エージェントに提案を行なう。Ｓ３２８で応答が肯定の場合は、関係が確立される。最後に、ステップＳ３００で、関係が確立された後、需要エージェントは、Ｓ３０４でシーンに変化があるまで受動モードに切り換わる。
【００５６】
図１４に、意志決定機械によって使用されるデータ構造のさらに他の実施形態を示す。図１４は、エージェントに市場の現在の指示を示し、各製品ごとに、エージェントと市場における製品の現在需要との間のネゴシエーションの履歴に基づいて現在の平均価格が計算される。次に、エージェントは、製品の平均価格が現在上昇しているか低下しているか決定することができる。例えば、市場が低下している場合、資源エージェントは市場が回復するまで待った方がよい可能性がある。
本発明によるマルチエージェント・システムが、図１５に示したクライアント−サーバ・ベースの実施形態を使用して実現できることを理解されたい。より具体的には、エージェントの処理と実行は、サーバによって行われ、クライアント端末は、世界中にいるユーザがシステムに情報を入出力できるようにするユーザ・インタフェースとして動作する。したがって、人間ユーザは、情報を入力したりシステムから情報を受け取ったりすることができ、例えば、自動車セールスマンは、経験から、ある特性を有する自動車の平均市場価格に関する知識を得る。次に、自動車セールスマンは、この情報をシステムに入力することができる。クライアント端末は、入力された情報を処理のためにサーバに送り、その結果、システム内の各関連エージェントのオントロジがこの知識によって更新され、その知識を突き合わせに使用することができる。
【図面の簡単な説明】
【００５７】
【図１】仮想世界シーンの例を示す図である。
【図２】１つの実施形態による仮想世界シーンの論理的アーキテクチャを示す図である。
【図３】航空貨物輸送の例のロジスティックス・マップを示す図である。
【図４】航空貨物の例の第１の状況におけるエージェント間のネゴシエーションを示す図である。
【図５】航空貨物の例の第２の状況における自己組織化のためのネゴシエーションを示す図である。
【図６】電子商取引アプリケーションを示す図である。
【図７】本発明の好ましい実施形態による基本的なエージェント・アーキテクチャを示す図である。
【図８】本発明の実施形態によるエージェント本体の構成要素を示す図である。
【図９】エージェント動作サイクルのステップのフローチャートを示す図である。
【図１０】エージェントのメタオントロジの例を示す図である。
【図１１】電子商取引アプリケーションの自動車エージェントのオントロジの例を示す図である。
【図１２】本発明の実施形態による意志決定機械によって使用されるデータ構造のテーブルを示す図である。
【図１３】本発明の実施形態によるエージェント間のネゴシエーションのステップを示す図である。
【図１４】意志決定機械に使用されるデータ構造の代替実施形態を示す図である。
【図１５】本発明を実現するクライアント−サーバ実施形態を示す図である。
【符号の説明】
【００５８】
１４  アクション・シナリオ
２０  センサ
２２  アクチュエータ機構
２４  シーン
２６  決定機械
２８  オントロジ
３０  事実メモリ
【図１】
2006505019.tif 000003
【図２】
2006505019.tif 000004
【図３】
2006505019.tif 000005
【図４】
2006505019.tif 000006
【図５】
2006505019.tif 000007
【図６】
2006505019.tif 000008
【図７】
2006505019.tif 000009
【図８】
2006505019.tif 000010
【図９】
2006505019.tif 000011
【図１０】
2006505019.tif 000012
【図１１】
2006505019.tif 000013
【図１２】
2006505019.tif 000014
【図１３】
2006505019.tif 000015
【図１４】
2006505019.tif 000016
【図１５】
2006505019.tif 000017
【国際調査報告】
2006505019.tif 000018
2006505019.tif 000019
2006505019.tif 000020
2006505019.tif 000021