No | 213521 | |
著者(漢字) | 桑原,和宏 | |
著者(英字) | ||
著者(カナ) | クワハラ,カズヒロ | |
標題(和) | マルチエージェントシステムにおける協調メカニズムの研究 | |
標題(洋) | ||
報告番号 | 213521 | |
報告番号 | 乙13521 | |
学位授与日 | 1997.09.18 | |
学位種別 | 論文博士 | |
学位種類 | 博士(工学) | |
学位記番号 | 第13521号 | |
研究科 | 工学系研究科 | |
専攻 | 電気工学専攻 | |
論文審査委員 | ||
内容要旨 | マルチエージェントシステムは自律的に動作するエージェントとよばれるプログラム群から構成されるシステムで,新しい分散システム構築のモデルとして注目を集めている.マルチエージェントシステムではエージェント間の協調をいかに実現するかが大きな課題となっている.本論文ではこのような背景のもとマルチエージェントシステムにおける協調メカニズムにおいて筆者が行なってきた以下の研究をまとめたものである. ・マルチステージネゴシエーションプロトコル ・市場モデルに基づく分散資源割当:均衡的アプローチ ・協調プロトコル記述言語Agen Talk 第1章において本研究の背景を概説するとともに本研究の目的を明確にする. 第2章ではマルチエージェントシステムにおける協調メカニズム研究状況の概要を述べ,本論文の位置付けを明確化する. 第3,4章ではエージェント間の協調を実現するためのプロトコル(協調プロトコル)の一例としてエージェント間にまたがる制約を満足した資源割当を実現するマルチステージネゴシエーションを取り上げる.まず,第3章においてマルチステージネゴシエーションで扱っている問題の定式化を与え,その中で複数のゴール間の競合を検出するための手法を提案する.さらに第4章でマルチステージネゴシエーションにおける探索戦略(3フェーズプロトコル)の評価を行なう. 第5章では市場モデルに基づく分散資源割当の試みを述べる.マルチステージネゴシエーションでは資源の割当をするかしないかを選択する問題を扱っていた.これに対し,マルチエージェントシステムの中に市場の構造を導入することによって,資源の量を扱えるようにする.それと同時にエージェント間の限られたメッセージの交換のみでエージェント間の協調を実現することを目指す.ここではその第一段階として均衡的アプローチと呼ぶ市場モデルに基づくアプローチを提案し,シミュレーション実験結果を中心に述べる. 第6章ではマルチエージェントシステムにおける種々の協調を実現するための"協調プロトコル"を記述するための言語Agen Talkを提案する.Agen Talkではプロトコル記述にオブジェクト指向言語に見られるような継承機能を導入し,プロトコルの段階的な定義を実現しているのが特徴である.さらにAgen Talkのアーキテクチャに基づいた協調プロトコルのメタレベル制御機構についても言及する. 第7章では結論と今後の課題について述べる.また,最後に付録としてAgen Talkの仕様概要を述べる. | |
審査要旨 | マルチエージェントシステムは自律的に動作するエージェントと呼ばれるプログラムモジュールの群から構成されるシステムであり、新しい分散システム構築のモデルとして重要になってきている。マルチエージェントシステムではエージェント間の協調をいかに実現するかが大きな課題である。本論文は、「マルチエージェントシステムにおける協調メカニズムの研究」と題し、このような協調メカニズムに関する ・マルチステージネゴシエーションプロトコル ・市場モデルに基づく均衡的アプローチによる分散資源割当て法 ・Agen Talkと称する協調プロトコル記述言語 の研究についてまとめたものである。 第1章「序論」では、本研究の背景と目的を記述している。 第2章「マルチエージェントシステムにおける協調メカニズムの研究状況」では、これまでの協調メカニズムの研究を要約し、本研究の位置付けを明確にしている。協調問題解決の領域では、結果共有、タスク共有、分散探索に分類して契約ネットプロトコル等について示し、交渉と均衡化に関する領域では、ゲーム理論手法の導入、市場モデルの応用についてまとめている。そして、これまでに開発されてきた協調プロトコル記述言語についてまとめている。 第3章「マルチステージネゴシエーションにおけるゴール間競合の検出」では、エージェント間にまたがる制約を満足する資源割当てを実現するためのマルチステージネゴシエーション(多段階交渉)の手法を示している。このマルチステージネゴシエーションは契約ネットワークの一種の拡張・一般化と考えることができ、契約ネットワークでは一回のタスク公示、入札、落札というメッセージの交換でタスクの割当てを行うのに対し、局所的な資源割当ての影響に関して交換した情報に基づき、必要に応じて資源割当てをやり直す。これにより適切な資源割当てが効果的に行えるようにする。まず、ここで扱う資源割当て問題を、システム全体の目標(グローバルゴール)と個々のエージェントの目標(サブゴール)を考慮に入れた探索空間として定式化し、続いてグローバルな目標間の競合関係、即ち、制約が強すぎて全ての制約を満足することができないという競合関係となる無効ゴール集合を,各エージェントがグローバルプランに関する情報をやりとりすることにより、効果的に計算する手法を示している。 第4章「マルチステージネゴシエーションにおける探索効率戦略の評価」では、第3章に続き、制約を満足する解を分散協調して効率的に探索する手法を示している。これは、非同期探索フェーズ、協調探索フェーズ、過制約解消フェーズからなる3フェーズプロトコルである。この枠組みを分散制約充足問題として見た時にどのように写像できるかを明らかにし、実際の通信網のデータを基にした例題を通じて、分散制約充足問題の基本的解法の一つである非同期バックトラックとの性能の定量的比較を行い、特に制約が弱い時に提案手法の有効性が大きいことを示している。 第5章「市場モデルに基づく分散資源割当て:均衡的アプローチ」では、第3、4章のマルチステージネゴシエーションでは資源を割当てるか否かの1/0問題を扱ったのに対し、売買の市場モデルを参照した資源の割当ての量を扱える分散資源割当て手法を提示している。エージェント間の限られたメッセージの交換のみでエージェント間の協調を実現することを目指し、各々の行動戦略を有する資源の売り手と買い手の存在下での均衡的アプローチと呼ぶ市場モデルに基づく手法を示している。ここではエージェント間で交換される情報は、売り手から買い手への価格情報の通知と、買い手から売り手への資源割当て要求に限定されている。通信ネットワークの資源割当て問題を例題としたシミュレーション実験を通じて、資源使用率の均等化を目標にした場合に各資源の使用率の分散が振動する現象が生じるが、感度係数の調整、価格情報の遅延に対する推定手法の導入による、振動を減少させる効果的方策を示している。 第6章「協調プロトコル記述言語Agen Talk」では、マルチエージェントシステムにおける種々の協調を実現する協調プロトコルを記述するための基礎言語となるAgen Talkと称するソフトウェア言語を提示している。Agen TalkはCommon Lisp上に実装されており、プロトコル記述にオブジェクト指向言語に見られるような継承機能を導入し、プロトコルの段階的定義を可能にしている。契約ネットプロトコル並びにそれを拡張したプロトコルをAgen Talkを用いて記述し、プロトコルの段階的定義機能について実証している。更に、Agen Talkで提案した枠組みにより協調プロトコルのメタレベル制御を実現することを示している。 第7章「結論」では、本研究の成果をまとめ、今後の課題について記している。また、付録Aには「Agen Talk仕様概要」を記載している。 以上を要するに、本論文は新しい分散システム構築のモデルとして重要になってきている、自律的に動作するエージェントと呼ばれるプログラムモジュールの群から構成されるマルチエージェントシステムの協調メカニズムに関し、マルチステージネゴシエーション(多段階交渉)の手法、売り手と買い手からなる市場モデルに基づく均衡的アプローチの手法、及び各種の協調メカニズム・プロトコルを実装するプラットフォームとなるAgen Talkと称する記述言語の考案、開発について記し、各手法の有効性を資源割当て問題等を例題として示しており、電子情報工学上貢献するところが少なくない。 よって、本論文は博士(工学)の学位請求論文として合格と認められる。 | |
UTokyo Repositoryリンク | http://hdl.handle.net/2261/51059 |