大規模マルチエージェントネットワーク
この分野のキーワード
マルチエージェントシステム, ゲーム理論, シミュレーション, 創発, 複雑ネットワーク
エージェント
エージェントとはユーザの代理として行動することが可能なソフトウェアを指します. しかし,エージェントは単なるプログラムとは異なります. エージェントは自らが周囲の環境を知覚し,思考して意思決定を行なうことで,自律的に行動する点で知的であるといえます.
例えば,近年発売され話題になった掃除ロボットは,部屋の大きさを測り,障害物や階段などの段差を避け,部屋の中をくまなく掃除し,バッテリーが少なくなると自分で充電しにスタンドへ戻ります.
また,ウェブ検索エンジンはウェブ上の文書をサーバに日々収集することで実現しています. ウェブには何十億とも言われる多くの文書が存在し,日々追加や変更,さらには削除されたりします. このような膨大な量の文書を効率よく探索するため,様々な手法によってウェブクローラは最適化されています.
このように,人間の手を直接介すること無く,自律的にしかも賢く行動する知的エージェントが必要とされています.
マルチエージェントシステム
マルチエージェントシステムとは,複数のエージェントによって構成されたシステムのことを指します.
複数のエージェントを用いることによって,ある目的を達成することや状況のシミュレーション,モデル化などを行ないます.
マルチエージェントシステムでは,各々のエージェントは異なる特徴を有します. 各エージェントが個性を有する(目的に対して利己的であるとも表現できます)ことでエージェント間の相互作用が生まれ,全体として複雑な状況が生じます.
大規模エージェントシステムにおけるシミュレーション
大規模マルチエージェントネットワークでは,個々のエージェントは利己的に行動します. このため,各エージェントの目的が一致すれば,他のエージェントと協調する可能性もありますが,利害関係が存在するような状況ではエージェント間で競争状態に陥ることが多くなります. つまり,ネットワーク全体の利益を考えた場合には,個々のエージェントが利己的では非常に効率が悪いケースが多くなってしまいます. では,ネットワーク全体の利益を最大にするには,各エージェントは周囲のエージェンに対してどの様に振る舞えば良いのでしょうか.
一つの解決策は,ゲーム理論の枠組みを導入することです. ゲーム理論は,ある設定された状況における個々人の意思決定,取るべき戦略を探る方法論です. 経済学や心理学,社会学などでも用いられています. 囚人のジレンマゲームがよく知られており,これを拡張した空間囚人のジレンマゲームを用いた研究も多くなされています.
大沢研究室では,より大規模なマルチエージェントシステムの研究を行っています. 特に,エージェントに社会特性を導入する事でネットワークの安定性や効率性を探っています. これは,P2Pネットワークやネットワークゲームなどにおいて分散計算資源の効率的運用に役立つ基礎研究です.
囚人のジレンマゲーム
囚人のジレンマゲームは,ゲーム理論においてよく知られる代表的なモデルです.
このモデルの設定は,次のようなものです.
まだ証拠不十分な事件の共犯者(囚人A, B)に対して,取り調べで各々の囚人に
A \ B | 黙秘 | 自白 |
---|---|---|
黙秘 | A: 1年 B: 1年 |
A: 5年 B: 0年 |
自白 | A: 0年 B: 5年 |
A: 3年 B: 3年 |
- 2人とも黙秘すれば,どちらも懲役1年の刑.
- 2人とも自白すれば,どちらも懲役3年の刑.
- どちらかが自白し,一方が黙秘すれば,自白した囚人は無罪放免,黙秘した囚人は懲役5年の刑.
と言い渡します. さて,囚人A, Bはどのような行動を取るべきでしょうか.
囚人Aの立場に立って考えてみましょう. 相手の行動を予想してみます.
- 囚人Bが黙秘した場合.
囚人Aは黙秘すれば懲役1年,自白すれば無罪放免です. - 囚人Bは自白した場合.
囚人Aは黙秘すれば懲役5年,自白すれば懲役3年です.
このように,いずれの場合を考えても,囚人Aは自白するのが良いということになります.
さて,本当に自白するのが最良の手なのでしょうか.表をもう一度良く見てみましょう.
囚人A, Bともに自白するとどちらも懲役3年の刑になります.
しかし,どちらも黙秘すれば,懲役1年の刑で済みます.
では,やはり黙秘するのが最善なのでしょうか.この場合,自分が黙秘すれば相手が自白した場合に懲役5年の刑となってしまいます.
つまり,個人の利益を優先させると全体として最良にならず,全体の利益を追求すると個人的に損を被る可能性があると言え,この事こそがジレンマなのです.
研究紹介
社会性を考慮した大規模エージェントネットワークのダイナミクスに関する考察
ネットワークが大規模な場合,全体の状態を参照して意思決定を行なうことは非現実的です. できる限り,ネットワークの局所的な情報を用いることで,意思決定を行なうことが望ましいでしょう.
人間社会を考えると,全体の詳細な情報が無くても(あなたは世界中の人物の個人情報を知っていますか?),個々人がそれぞれ相手の社会的地位などを考慮して意思決定を行ない行動する事で円滑な社会活動を成立させていると考えられます. このように,社会性の概念は様々な利害関係を持った人々が集まる人類社会のネットワークを効率的なものにしています.
そこで,利害が対立するマルチエージェントシステムにおいても,エージェントに社会性を取り入れることによって,局所的な情報のみを用いた効率の良いネットワークの構築が可能となります.
社会モデルにはいくつかのモデルがありますが,SGD(Synthetic Group Dynamics)モデルは,社会心理学の考えをもとにした社会モデルで,マルチエージェント環境でエージェントのインタラクションに応じて,自身のインタラクションの頻度を調節する事ができるモデルです.
実験では空間囚人のジレンマゲームを用いています. 空間囚人のジレンマゲームは各ステップで自身にリンクしている各エージェントと囚人のジレンマゲームを行います. 本研究では空間囚人のジレンマゲームに対して,リンク変更時に価値関数を用いたリンク先の選好を導入しています.
選好の基準には,社会モデルであるSGDモデルやランダムに相手を選ぶモデルなど4種類のモデルを用いました. その結果,選好基準を持たないモデルよりも,選好基準を持つモデルの方がネットワーク全体として良いパフォーマンスを示すことが確認できました. またネットワーク全体が裏切りあうケースは,社会性を導入したSGDモデルが非常に低い値を示すことも確認されました.
菊池浩彰, 大沢英一
社会性を考慮した大規模エージェントネットワークのダイナミクスに関する考察
合同エージェントワークショップ&シンポジウム(JAWS-2007)講演論文集, 2007