プロジェクト名

マルチエージェントプロジェクト

メンバー

中野

目的

集団における行動シミュレーション

サブテーマ

頑健な制約解消／提携構造形成問題

キーワード

制約最適化，分散制約最適化問題，ロバストな提携構造

概要

マルチエージェントシステムは，例えば人間社会やセンサネットワークなどのシミュレーションに用いられている． マルチエージェントシステムの研究分野の一つに「提携構造形成(CSG)問題」が存在する． CSG とは，システム全体の利益が最大化するようなチーム("提携"と呼ぶ)をエージェント同士で形成することを目的としている． エージェントの集合を複数のチームに分割したものを"提携構造"と呼ぶ．

CSG に関連した研究は，問題フレームワークの提案や，求解アルゴリズムの提案など，既に数多く存在している． しかしながら，エージェントが離脱することを想定した研究は少ない． エージェントが，事故または病気などの突発的な理由によって提携から離脱することは，自然なことであり，充分に起こり得る． 提携構造を形成する時点で，予めエージェントの離脱を想定しておくことは，自然な考え方である． 本プロジェクトでは，エージェントの離脱に頑健な提携構造を形成するための研究をしている．

既存研究の中に，CSG の新しい形態の一つとして，提携構造の頑健性に着目したロバストな提携構造形成(RCSG)問題がある． RCSG におけるロバストな提携構造とは，提携構造内の任意のエージェントが離脱しても，システム全体の利益が最大のままである提携構造を指す． RCSG の問題設定では，全ての提携構造に対して，任意のエージェントの離脱を考慮する必要があるため，高速に求解することは難しい． 本プロジェクトでは，RCSG の考えを基に，提携解消を考慮した提携構造形成(LAP-CSG)問題を定式化した． LAP-CSG は RCSG における提携構造のロバスト性に関する制約を緩和した問題である． LAP-CSG におけるロバストな提携構造とは，提携構造内の任意のエージェントが離脱しても，負の提携が発生しない提携構造を指す． LAP-CSG を求解することにより，突発的なエージェントの離脱に頑健な提携構造を得ることができる． すなわち，LAP-CSG により高品質かつロバストな解が CSG と同程度の時間で得られる.