表題番号：2007A-853 日付：2010/10/18
研究課題スケーラブルな交渉アルゴリズムのための特性解析の研究
研究者所属（当時） 資格 氏名
（代表者） 理工学術院 教授 菅原　俊治
研究成果概要
　　インターネットを活用した自動取引や各種グリッド、ＣＰＵを内包するセンサーによるユビキタス・センサーネットワーク、広域分散システムの資源割当てなど、大量の計算機上で自律的に動作するソフトウェアが効率の面で互いに影響し合う状況で、効果的な動作を実現するためには、適切なタスク割当てが必要である。本研究では、大規模なマルチエージェントシステムに向けて、スケーラビリティを考慮した交渉プロトコル (タスク・資源割当てプロトコル）を提案することを目的とする。
　　これまで交渉プロトコルの研究は、非常に空いたシステムで小規模なものを想定している。これを大規模なものに適用した場合、明らかにスケーラビリティに問題があるが、それ以前に、大規模に適用したときの性能の性質や各エージェントの振舞いの特性も分かっていない。本特定課題研究の目的は、代表的な交渉プロトコルである契約ネット(CNP)を対象に、相互に干渉する有限な能力や容量(たとえばCPU資源の割当てや予算が限定された電子商取引など)を対象とした交渉に着目し、特に、多数のエージェントが介在する環境での個々の振舞いと、系全体の効率およびそれらの特性について解析する。
　　本研究期間では、CNPの広報戦略と落札戦略に着目しそれらの戦略の差と全体の効率の関係をシミュレーションにより求めた。本実験では、広報の範囲を狭めると能力の高いエージェントにタスクの通知が行かず、全体の効率が落ちる懸念があった。しかし、大規模なシステムでは、むしろ広報範囲を狭めた方が全体としての平均効率が上がることが分かった。
　　また、落札戦略についても、常に一番高い値を入札したものではなく、ある程度の揺らぎを加え、２番手、3番手のエージェントを選択しタスクを割り当てる戦略が全体の効率を著しく上げることが分かった。この揺らぎの度合いとシステムの負荷には大きな関連性があり、これらをうまく調整することで、システム全体の潜在能力を引き出す交渉プロトコルへの手がかりが分かってきた。