マルチエージェント協働環境における
利己的なエージェントの進化
Evolution of Self-interested Agents in Collaborative Environments
下地竜起 坂間千秋
Ryuki Shimoji Chiaki Sakama
和歌山大学システム工学研究科
Graduate School of Systems Engineering, Wakayama University
Abstract: In this study, we consider an environment in which multiple agents share information and cooperatively search objects. We then observe the evolution of self-interested agents who do not act cooperatively or even act dishonestly to increase their own profits. Experiment results show that such self-interested agents get high profits when a large number of cooperative agents exist.
1．はじめに
マルチエージェント協調探索の一つとして、複数 の自律的に行動するエージェントが協調して環境内 の目標物を探索する問題がある。これはロボットに よる地雷探査に代表されるような広範囲に点在する 目標物を効率的に回収する問題である。このような 問題においては、エージェントがコミュニケーショ ンを通じで情報を共有することで効率的に探索を行 うことが可能になる[1,2]。一方でこうした協働環境 では、各エージェントが協調的に振る舞うことが前 提とされているが、人間社会においてはこうした前 提は一般に成り立たず、集団の中には自己中心的に 振る舞う人間が存在するのが常である。従って、人 間社会のモデル化を目指すマルチエージェントシス テムの研究でも、自己中心的に振る舞うエージェン トの存在が集団に与える影響や、利己的なエージェ ントが発現するプロセスを観察することは人間社会 におけるダイナミズムを理解する上で重要である。 これまでにも、集団の中で自らの利益を最大化する ために嘘をつくエージェントの研究[3]や、相手を騙 す能力を持つロボットの研究[4,5]、あるいは資源が 限られた状況下でエージェントが非協力的に振る舞 うようになるプロセスをシミュレーション実験した 研究[6]などが行われている。 本研究ではマルチエージェント協調探索問題にお いて、非協力的なエージェントの存在が集団に与え る影響を調べると共に、繰り返しゲームにおいて非 協力的で自己中心的なエージェントが発現するプロ セスをシミュレーション実験した。以下では、2 章 で協調探索問題の説明を行い、3 章で異なる戦略を 持つエージェントについて述べる。4 章でシミュレ ーション実験とその結果について報告し、5 章でま とめと今後の課題について述べる。2．マルチエージェント協調探索問題
本研究で考えるマルチエージェント協調探索問題 は、複数のエージェントがフィールド上を移動しな がらランダムに配置された目標物を回収するという ものである。またエージェントは自身が発見した回 収物の位置情報を他のエージェントに対して発信す ることができ、これによって各エージェントは協力 して回収作業に当たることができる。エージェント と環境の設定は以下の通りである。 フィールドは非トーラス状のセル空間で正 方形をしている。サイズは実験目的によって 変化させる。 フィールドは二次元座標空間であり、その中 に存在する全てのエージェントおよび物体 は二次元座標を用いてその位置を管理する。 エージェントの初期配置はランダムである。 エージェントは 1 ステップにつき上下左右い ずれかに 1 セル移動するか、その場で待機す るかを選択できる。 エージェントは自身の 5 回の移動で到達でき る範囲と等しい広さの視界を持つ。 回収目標物は複数個が 1 セットとなってフィ ールド内にランダムに配置されている。1 セ ット当たりの個数と配置数は実験内容に応 人工知能学会研究会資料 SIG-ALST-B402-05じて数値を変化させる。 エージェントは回収物と同じセルに進入、滞 在することで、移動とは別に 1 ステップにつ き 1 個の回収物を回収する。 エージェントは視界内に回収目標物を発見 するとその座標まで移動する。また回収目標 物の個数と座標情報を他のエージェントに 対して発信することができる。情報はタイム ラグ無く全てのエージェントに伝わり、発信 者の ID が付与されている。 視界内に回収目標物が無い場合は、他のエー ジェントから発信された情報と自身が過去 に発見して既に視界から外れている回収目 標物の中から、最も近くにあるものを目指し て移動する。 視界内にも過去の記憶にも他のエージェン トからの発信情報にも回収目標物が存在し ない場合、エージェントはランダムに移動す る。 エージェントは自身の手でより多くの目標 物を回収することを目指す。
3．エージェントの戦略
エージェントが取りうる戦略として以下の四つを 考える。3.1 協力的(cooperative)
この戦略を取るエージェントは自身が発見した回 収物の位置情報を正しく他のエージェントに対して 発信し、かつ他のエージェントから受け取った情報 を全て信用して利用する。この戦略が全てのエージ ェントの基本となる。3.2 懐疑的(skeptical)
この戦略を取るエージェントは自身が発見した回 収物の情報を正しく他のエージェントに対して発信 するが、他のエージェントから受け取った情報につ いては一切信用しない。この戦略は他のエージェン トから受け取った有益な情報を利用することはでき ないが、偽情報を受け取った場合の不利益を被るこ とも無いため、嘘をつくエージェントに対する対抗 策としての役割が期待される。3.3 フリーライダー(free rider)
この戦略を取るエージェントは自身が発見した回 収物の情報を一切発信しないが、他のエージェント から受け取った情報については利用する。この戦略 を使用するエージェントは他のエージェントに対し て一切の協力的な行動を取らないが、他のエージェ ントが行った協力的な行動を利用して自己の利益を 増加させる。3.4 嘘つき(liar)
この戦略を取るエージェントは自身が発見した回 収物の情報を一切発信せず、代わりに自身の現在位 置から 30 セル以上離れており、かつ回収物が存在し ないことを過去に自分で確認している地点に対して、 回収物が存在するという偽情報を 5 ステップにわた り発信する。また他のエージェントから受け取った 情報については利用する。フリーライダーに嘘の情 報を発信する機能を付与した戦略で、自身が発見し た回収目標物から他のエージェントを遠ざけるため に偽情報を利用する。4．実験
以上の設定の下でコンピュータ上で実験を行った。 なお、実験は 100 回の試行を行い、その平均値を用 いて性能を比較している。4.1 非繰り返しゲーム
まずは本実験環境における利己的な戦略の影響を 調べるため、繰り返しゲームではない単体のゲーム を用いて調査を行った。なおこの実験ではフィール ドのサイズを 50×50 としている。4.1.1 エージェント数による影響
エージェントの人口密度による各戦略の有効度の 変化を調査するため、4 種類のエージェントの数を 各 3 体、各 10 体、各 20 体の 3 パターンに変化させ て回収数を比較した。回収目標物の配置は 100 個を 1 セットとして 10 セットをランダムに配置している。 なおエージェントの戦略は「協力的、懐疑的、フリ ーライダー」の組み合わせと「協力的、懐疑的、嘘 つき」の組み合わせの 2 種類について実験を行って いる。 実験結果は以下の表 1, 2 の通りである。なお協力 的な戦略の平均回収数を 100%とした場合の各戦略 における回収量の比率をパーセンテージで表現して いる。 表 1 エージェント数による各戦略の比較(1) 協力的 懐疑的 フリーライダー 各 3 人 100 42 114 各 10 人 100 50 116 各 20 人 100 54 107表 2 エージェント数による各戦略の比較(2) 協力的 懐疑的 嘘つき 各 3 人 100 42 112 各 10 人 100 57 102 各 20 人 100 58 96 表 1, 2 より、人口密度が上昇するほどフリーライダ ーと嘘つきの回収率が低下することが観察される。 これは、人口密度が大きくなるほど自分が発見した 回収目標物を一人占めできる確率が下がるためだと 考えられる。また懐疑的な戦略は、人数によらず協 力的なエージェントと比較して回収効率で大きく劣 ることが分かる。これは嘘によって被る被害よりも、 他のエージェントが発信した情報を利用することに よる利益の方が大きいことを示している。
4.1.2 回収目標物の配置による影響
次に回収目標物の配置を変化させて各戦略の回収 数を比較した。エージェントの人数と戦略は協力的、 懐疑的、フリーライダーを各 3 人ずつとした場合と、 協力的、懐疑的、嘘つきを各 3 人ずつとした場合を 考えた。また、配置は 10 個を 10 セット、100 個を 10 セット、500 個を 10 セット、2 個を 50 セット、 20 個を 50 セット、100 個を 50 セットの 6 パターン について調査した。実験結果は以下の表 3,4 の通り である。 表 3 回収目標物の配置による各戦略の比較(1) 協力的 懐疑的 フリーライダー 10×10 100 69 111 10×100 100 42 114 10×500 100 46 112 50×2 100 65 102 50×20 100 63 109 50×100 100 63 108 表 4 回収目標物の配置による各戦略の比較(2) 協力的 懐疑的 嘘つき 10×10 100 45 118 10×100 100 42 112 10×500 100 48 103 50×2 100 57 104 50×20 100 54 99 50×100 100 62 101 表 3, 4 より、フリーライダー、嘘つき共に回収目標 物が一ヶ所に集まっている状況より、広く分散して いる場合の方が回収効率が低下することが分かる。 これは少量ずつ広く分散するほど、フリーライダー や嘘つきが一人占めできる回収目標物の量が減るか らであると考えられる。4.1.3 戦略毎の比率による影響
ここまでの実験ではエージェント毎の人数比率は 一定であったが、嘘つき戦略に関しては協力的な戦 略のエージェント数が多く、嘘つき戦略を取るエー ジェント数が少ないほど有効であると考えられる。 そこで協力的なエージェント 6 人に対して嘘をつく エージェント 3 人で実験した結果を表 5 に、協力的 なエージェント 8 人に対して嘘をつくエージェント 1 人で実験した結果を表 6 に記す。回収物の配置は それぞれ 10 個を 10 セット、100 個を 10 セット、500 個を 10 セットの場合を比較している。 表 5 協力的 6 人、嘘つき 3 人の場合 協力的 嘘つき 10×10 100 110 10×100 100 109 10×500 100 106 表 6 協力的 8 人、嘘つき 1 人の場合 協力的 嘘つき 10×10 100 146 10×100 100 132 10×500 100 117 表 5, 6 より、懐疑的なエージェントの人数を減らし て協力的なエージェントを増やしても嘘つきの効率 は向上しないが、嘘つきの人数を減らすとその効率 は大きく向上することが分かる。またその場合、回 収目標物の個数が少ないほど回収効率が上昇するこ とも分かる。これは嘘をつく人数が減ることにより 嘘つきエージェント自身が他の嘘つきエージェント に騙されることが無くなるためであると考えられる。 また回収目標物の数が少ないほど回収効率が向上す るのは、嘘で他のエージェントを遠隔地へと誘導し ている間に、嘘つきエージェントが回収目標物を一 人占めできる確率が上がるためだと考えられる。4.1.4 戦略比率の変化による回収時間の変化
嘘つきやフリーライダーといった戦略は仲間に対 して負担を強いるため、全体として見た場合の回収 効率が悪化するのではないかと考えられる。そこで 戦略の比率を変化させることで回収終了までの時間がどのように変化するのかを調査した。 戦略の比率は「協力的、懐疑的、フリーライダー を各 3 人ずつ(C×3, S×3, F×3)」「協力的、懐疑的、 嘘つきを各 3 人ずつ(C×3, S×3, L×3)」「協力的を 9 人(C×9)」「懐疑的を 9 人(S×9)」「嘘つきを 9 人(L ×9)」の各場合を用いた。また回収目標物の数につ いても 10 個を 10 セット、100 個を 10 セット、500 個を 10 セット、20 個を 50 セットの場合について比 較した。実験結果は表 7 の通りである。 表 7 戦略比率の変化による回収時間の変化 10×10 100×10 500×10 20×50 C×3 S×3 F×3 76,502 103,250 154,390 115,820 C×3 S×3 L×3 20,135 44,231 93,270 40,511 C×9 59,134 135,481 169,351 168,104 S×9 83,871 104,300 184,055 117,610 L×9 43,979 32,806 89,135 39,080 表 7 より、直観に反し嘘つきを含む組み合わせの方 が終了までに掛かるステップ数が小さくなる傾向が 観察された。これは１つの目標物を回収するのにか かる時間よりも探索にかかる時間の方が大きいため だと考えられる。そのため回収を手伝うためにエー ジェントが探索を切り上げて一ヶ所に集まることは、 結果的に回収終了までのステップ数の増加を招いて いるのではないかと考えられる。
4.2 繰り返しゲーム
継続した状況の中でエージェントが自己の利益を 最大化するために自身の戦略をどのように変化させ るのかを観察するために、繰り返しゲームを行った。 エージェントは各戦略 12 人ずつ計 48 人を配置する。 これらは 10 ゲームを終える毎に世代交代を行い、自 身の戦略を変化させる。この時選択される戦略は 10 ゲームにおける得点を利用したルーレット選択を採 用し、各戦略の平均点数に比例した確率で次世代の 戦略を決定する。また 1%の確率で突然変異を起こし、 前ゲームでの点数に関係なく戦略が選ばれる。これ を 100 世代分繰り返し、世代交代による戦略の変化 を観察した。 なお非繰り返しゲームにおける実験結果よりエー ジェントと回収目標物の密度が各戦略の有効性に影 響を及ぼすことが分かっているためエージェントの 人数に合わせてフィールドのサイズを 100×100 に、 回収物の量を 100 個×40 セットとしてこれらの密度 が一定になるよう調整を行っている。実験結果は 図 1 の通りである。 図 1 繰り返しゲームによる戦略の変化(1) 次に第一世代の戦略比率が及ぼす影響を確認する ために協力的と懐疑的のエージェントをそれぞれ 20 人ずつ、フリーライダーと嘘つきのエージェント を 4 人ずつ計 48 人を初期エージェントとして同様の 実験を行った。実験結果は図 2 の通りである。 図 2 繰り返しゲームによる戦略の変化(2) 更に第一世代を協力的と懐疑的 24 人ずつ計 48 人 とし、フリーライダーと嘘つきを排除した状態での 実験を行いその結果を観察した。実験結果は図 3 の 通りである。図 3 繰り返しゲームによる戦略の変化(3) 世代毎にバラつきは存在するが、どの実験も嘘つ きとフリーライダーの数がおおよそ同数で最も多く、 その次に協力的、そして懐疑的なエージェントが最 も少なくなるという共通した結果となった。これは おおよそ非繰り返しゲームにおける点数比率に近い 人数比で安定している。特に実験 3 では突然変異に よって生まれたフリーライダーと嘘つきが急速にそ の数を増やし、最終的に安定した比率へと至ること が分かる。この結果は嘘つきやフリーライダーの有 用性が協力的なエージェントの個体数に影響を受け ていることによることが原因であると考えられる。 非繰り返しゲームにおいて嘘つきの人数が増えるほ ど嘘つきの有用性は低下したことから、人数が増え ると得点差は狭まり、次世代における人数比が縮小 すると予想される。そのため図のように一定範囲で 人数比が保たれるのではないかと考えられる。
5 結論
マルチエージェント協調探索問題において、フリ ーライダーや嘘つきといった自己中心的で不誠実に 振る舞うエージェントが一定の利益を上げることが 実験により確認された。またどれほどの利益が得ら れるのかについては周囲のエージェント数や種類、 回収物の配置に左右され、人口密度が小さく、かつ 回収物が少ない場所に集中的に配置されている場合 に嘘の効率が向上すると分かった。そのため人口密 度が高く、回収物が広く分散したような環境では不 誠実な行為は大きな利益には繋がらないため、その ような行為の発生は抑えられると考えられる。 また不誠実なエージェントの有効性は協力的なエ ージェントによって支えられているため、無制限に 不誠実なエージェントが増加することもないことが 観察された。もし不誠実なエージェントが大きく増 えたならばその有用性は低下し、協力的なエージェ ントとの差は無くなるため嘘をつくメリットがなく なると考えられる。 なお今回の実験では考慮しなかったが、他のエー ジェントとの信頼関係や嘘をつくための労力、嘘が 発覚した場合のペナルティなどを評価値として組み 込んだ場合、不誠実な戦略の有用性は低下すると予 想される。そのため不誠実な行為がそれらの不利益 を超えるだけの十分な利益へと繋がらない場合、嘘 をつくことは合理的な行動ではなくなるかもしれな い。これらについては、今後実験を継続して確認し ていく予定である。参考文献
[１] Polycarpou, M. M., Yanli, Y., and Passino, K. M.: "Cooperative control of distributed multi-agent systems." IEEE Control Systems Magazine (2001)
[２] 北村泰彦, 寺西憲一, 辰巳昭治: "マルチエージェン ト実時間探索における組織化とその評価", 人工知能 学会誌, Vol. 11, No. 3, pp. 470-477 (1996)
[３] Zlotkin, G., Rosenschein, J. S., and Ram, G.: "Negotiation and Task Sharing Among Autonomous Agents in Cooperative Domains", Proc. IJCAI-89, pp.912-917 (1989)
[４] Wagner, A. R.: "Robot Deception: Recognizing when a Robot Should Deceive", Proc. IEEE International Symposium on Computational Intelligence in Robotics and Automation, pp. 46-54 (2009)
[５] Shim, J. and Arkin, R. C.: “Biologically-inspired deceptive behavior for a robot,” Proc. 12th International Conference on Simulation of Adaptive Behavior, pp. 401-411 (2012)
[６] Yamada, N. and Sakama, C.: “Evolution of self-interested agents: an experimental study”, Proc. 7th Multi-Disciplinary International Workshop on Artificial Intelligence (MIWAI), Lecture Notes in AI, vol. 8271, Springer, pp. 329-340 (2013)
