日本ソフトウェア科学会ニューズレター
博士論文紹介欄

大沢 英一 博士の学位論文紹介


論文名: マルチエージェント環境における協調スキーマに関する研究
取得時期: 1996年3月6日
著者名: 大沢 英一
連絡先:
公立はこだて未来大学システム情報科学部情報アーキテクチャ学科
〒041-8655 北海道函館市亀田中野町116-2
Tel: 0138-34-6127, Fax: 0138-34-6301
E-mail: osawa@fun.ac.jp
大学と専攻:慶應義塾大学大学院 理工学研究科 計算機科学専攻
学位の名称: 博士 (工学)
主査の氏名: 所 真理雄 教授
概要

独立もしくは共通の目標を持つ複数のエージェントが存在する環境をマルチエージェント環境と呼ぶ.そのような環境においては,各エージェントの独立な目標(もしくはプラン)間や,共通の目標を達成するために各エージェントが持つ部分目標(もしくはプラン)間にさまざまな利害関係が生じ得る.そのような状況に置かれた複数のエージェントは,相互の利益のために必要な情報を交換し,相互の要求を局所的に評価し,最終的には相互の利害を考慮した合意を形成することが好ましい.なぜなら,合意は,目標の変更,行為の整合,そして共同などを含み,結果として大局的な協調動作となり得るからである.

マルチエージェント環境においては,あるエージェントが単独では達成できない目標を持つ場合がある.この場合,そのエージェントは他のエージェントに何らかのタスク(例えば,部分目標の達成など)を依頼して共同する必要が生じる.共同とは共通の目標を達成するためにそれに関与する複数のエージェントが各々の受け持つ部分目標やプランに関して整合をとることをさす.しかしながら,マルチエージェント環境においては,(1)エージェントの生成・消滅は動的である,(2)各エージェントの世界に関する知識や技能が部分的である,(3)エージェント間の信念が不整合な場合がある,などの理由により,共同の可能性を常に網羅的に把握しておくことは非常に困難でコストの高いタスクとなる.

また,共通目標を達成するために協調する場合は,各エージェントにおける適切な局所プランの生成と,それらの局所プランの大域的整合が要求される.特に,各エージェントのプラン生成と実行に対する問題空間の動特性が高い場合には,環境の特性に応じて,プランの生成と実行の小さなサイクルを繰り返す即応的な協調プランニングが要求される.なぜならば,そのような環境においては,生成に長い時間を要する複雑なプランを対象にすると,それを実行しようとした段階においては,既に状況が変化していてプランの適用条件が成立しなくなり実行不可能であったり,そのプランがもはや有効ではない,などの状況が生じる可能性が高くなるからである.すなわち,動的特性が高い環境においては,エージェント間の相互作用の形態が固定した組織(以下,固定組織と呼ぶことがある)では,共通目標の達成が効率良く行なえない場合が生じる.

本論文では,以上の二つの問題(マルチエージェント環境における共同に関与する諸問題と動的な環境における固定組織の問題) を解決するための協調スキーマを提案する.まず,最初の問題に対しては,共同の必要が生じた時点で,エージェントの機会に応じて組織を構成すること(機会主導型共同プランスキーマと呼ぶ)を提案し,各エージェントに合理性(効用を最大化する特性)を仮定した上で,その過程全体を定式化する.機会主導型共同プランスキーマでは,部分的で相互に不整合な信念を有する可能性のある複数のエージェントが,機会に応じて共同の可能性を推定し,整合的に共同プランを生成する.その過程では,(1)最良個別プランの生成,(2)共同における障害の除去,そして,(3)各エージェントの共同から得る効用の均等化,などが考慮される.

二番目の問題に対しては,動的組織再編(問題空間の変化に応じて,動的に組織形態を変更する)による協調プランニングと,それを実現するためのメタレベル整合戦略を提案する.メタレベル整合戦略では,(1) 共通目標への接近度合の変化量,(2)エージェント間で共有される知識量,そして,(3)協調組織におけるエージェントの意思決定の自由度,の3つを考慮する.メタレベル整合戦略では,現在の組織スキーマによる協調プランニングで,ある定数ステップ以上の間,共通目標への距離が改良されない場合,その組織スキーマは有効でないこと推定し,次に有効と思われる組織へと変更する.

機会主導型共同プランスキーマでは,エージェントに合理性を仮定することにより,エージェント相互に不確定な情報の下でも必要以上の通信を行なわずに,効率のよい,そして適切な共同プランを機会に応じて生成することが可能となった.合理性は,各エージェントに対して自己の行為に対する選択基準を与えるだけでなく,共同における他のエージェントの行為選択に関する良い予測を与える根拠ともなるため,非常に重要な性質であることが示された.メタレベル整合戦略に基づく動的再編組織においては,環境の特性に応じて適応的に組織を再編することにより,比較的通信コストの高い状況において,より効率良く共通目標を達成することが可能となった.この場合,メタレベル整合戦略の計算コストが,最も計算コストの高い組織の計算コストから次に計算コスト高い組織のそれを引いた値以下に抑えることができ,かつ,最も計算コストの高い組織の移動速度が,共通目標の変化速度よりも速ければ,その動的再編組織は共通目標を達成することが可能であることが示された.


Last update: December 24, 2004
大沢 英一 (osawa@fun.ac.jp)