Mobile agent
ネットワークにおけるノルムの収束
Norm emergence through Influence-based aggregative learning in
Mobile agent network
大塚 知亮
1∗菅原 俊治
1,2Otsuka Tomoaki
1Sugawara Toshiharu
1,21
早稲田大学基幹理工学部情報理工学科
1
School of Computer Science and Engineering, Waseda University.
2
早稲田大学大学院情報理工・情報通信専攻
2
Department of Computer Science and Engineering
Abstract: Social norm have often been used to promote cooperation and coordination and to avoid unnecessary conflicts in multiagent systems. Furthermore, interaction between agents is ususally based on social network topology, that is, how individuals are connected. Thus, many studies are dedicated to the emergence of norms in these complex networks, but few of them focused on dynamically changing networks. This paper extends our previous study, influence-based aggregative learning (IAL), which is framework to facilitate the emergence of social norms in static complex network, to apply to changing networks. Then, we experimentally indicate that the norm can emerge in the networks of agents by the extended IAL.
1
はじめに
社会規範（ノルム）とは実社会のいたるところで観 察でき, ノルムにしたがうことで集団における競合を減 らし円滑な社会活動の指針となっている. 例えば, 道の どちら側を歩くかや, チップを払う際の金額, 車の運転 における道の譲り方などにも広義のノルムが存在する. マルチエージェントシステム (MAS) においてもエー ジェントが協調行動を獲得し, それがシステム全般に伝 搬することでノルムが発生し, 頑健なシステムの構築 を促進できる. このようなノルムはルールとしてシス テムの設計時に規定する方法もあるが, 問題設定, 環境, エージェントの能力, 相互関係などに依存する. そのた めそれぞれに適した設計をすることは難しい. また, 環 境の変化や周囲の状況を集めこれらを集中的に管理す る方法もあるが, エージェントのインタラクションは組 み合わせ問題であり, システム全体とエージェントの状 況を考慮して管理することは大規模な環境では困難で ある. そこで, エージェントは個々の環境で周辺のエージェ ントとのインタラクションからノルムを獲得できるこ とが望ましい. そのため, 各エージェントが協調行動を 獲得し, それらがシステム全体に伝搬するメカニズム ∗連絡先：早稲田大学基幹理工学部情報理工学科 〒 169-8555 東京都新宿区大久保 3-4-1 E-mail: [email protected]@suou.waseda.jp が MAS で注目されている. また伝搬は個々のつなが りを経ることから, 実社会の関係を表現するネットワー クの特徴を模した環境を再現することも研究されてい る. 例えば, 実社会のネットワークにはスモールワール ド性, クラスタ性, スケールフリー性といった性質が確 認されている. 以上の観点からエージェントが構成するネットワーク 上で, 主に協調ゲームを用いたノルムの獲得・学習に関す る研究が多くある (例えば [1][2][3]). しかし, CNN, BA などのうちある種のネットワークでは学習結果として ノルムが十分に伝搬せず, 得られた行動の整合性が低く なることがある. 他方, [4] で多様な複雑ネットワークで ノルム収束の成功率の高い influence-based aggregative learning (IAL)手法を提案している. しかし, 実社会の ネットワークは各種の条件によって絶えず変化してお り, こうした時間とともに変化するネットワーク上で のノルム収束は確認していない. また [5] では, 変化す るネットワーク [6] 上でのノルムの収束を議論している が, 最後通牒ゲームを対象とした利益分配に着目してお り, 本研究の目的とは異なる. そこで, 本研究では隣接エージェント間のみのインタ ラクションから系全体のノルムを収束させた [4] の IAL 手法を Mobile agent による時間経過とともに変化する ネットワーク（以下 Mobile agent ネットワークもしく は MA ネットワーク）[6] へと適用し, そのネットワーク 人工知能学会研究会資料 SIG-KBS-B503-01上でのノルムの収束について調査する. また, MA ネッ トワークにおけるパラメータを変化させることで, その 特徴についても調査する. 本論文の構成は以下の通りである. 次節で関連研究 を述べ, 第 3 節では実験の準備として協調ゲーム, MA ネットワークについて述べる. 第 4 節では IAL 手法を MAネットワークへ適用する手法を提案する. 第 5 節で は生成された MA ネットワークの特徴を調べた後, 提 案手法の評価実験を行い, 協調が促進されることを示 す. 最後に, 第 6 節で結論と今後の課題を述べる.
2
関連研究
ノルムの収束や実社会のネットワーク構造の研究は 数多くある. 例えば [7] ではノルムを考慮したシステム やエージェントがノルムに従うかを選択できるシステ ム, normative multiagent system の定義を紹介してい る. 文献 [1][3] では人間が意思決定をする際に周囲の 人の意見を元に集約するプロセスを模倣したフレーム ワークを提案し, ノルムの収束について調査している. しかしノルム収束の成功率も全てのネットワークにお いて高いとは言えない. [4]では [1] を拡張した IAL という手法を提案し, 周 囲のエージェントへの影響力を定義し, これらを集約・ 伝搬させることで多くの複雑ネットワークでノルムの 収束に成功している. また, [8] では周囲と協調しない 行動をしたエージェントを罰する仕組みを導入し, 非協 調エージェントを罰しなかったエージェントを更に周 囲のエージェントが罰するメタノルムを導入した. ここ ではハブエージェントによる影響について考察・改善 し, 実社会のネットワークの特性を再現したネットワー クでのノルムの収束を調査している. しかし, これらの 研究は静的なネットワーク上でのインタラクションを 想定しおり, ネットワーク構造の時間変化は考慮してい ない. 時間経過によるネットワーク構造の変化を考慮した 研究も存在する [5][9][10][11]. 例えば, 時間とともに変 化する実社会のネットワークを模倣する研究として [6] （MA ネットワーク）がある. ここではエージェントを 粒子に見立てて自由運動のシミュレーションを行い, そ の衝突から得られるネットワークと性的関係のネット ワークや小学生の友人関係のネットワークとの類似を 調査している. この変化する MA ネットワークをベー スに [5] ではノルム収束法を提案しているが対象が最後 通牒ゲームでありその目的は本論文と異なる. 一方 [12] では複数のエージェントでマップ上の資源 収集をするシミュレーションを行い, エージェント同士 で競合をさける戦略を獲得することを目指し, そうした 戦略の選択におけるノルムの発生を調査している. エー ジェントのインタラクションの範囲が限られているた め, エージェントのネットワークは動的と言えるが, 実 験の手法に依存する部分が多い.3
準備
3.1
協調ゲーム
本研究で対象とする協調ゲームは 2 人ゲームで, 2 種 類の戦略 S ={L, R} と図 1 の利得行列で定義する. 先 行研究 [1][4] にもとづき, どちらかの戦略を 90% 以上 のエージェントが選択したときノルムが収束した状態 とする. L R L 1, 1 -1, -1 R -1, -1 1, 1 図 1: 協調ゲームの利得行列3.2
MA
ネットワーク
MAネットワークは, 集団の中で人が知り合い関係の ネットワークを構築する様子を模倣したモデルである. MAネットワークではエージェントを直径 d の小さい 粒子に見立て, N 体のエージェントを一辺の長さ L の 正方形の空間に放ち, 初期速度 v0でランダムな方向に 直線運動させる. 壁に衝突した場合は反射する. もし 粒子同士が衝突すると, 対応するエージェント同士がリ ンクを獲得する. さらに, 衝突した 2 つのエージェント の速度を以下に述べる方法で更新（加速）し, ランダム な方向に向きを変えて再び運動を続ける. 3.2.1 最大クラスタ MAネットワークによって構築されたネットワーク のある瞬間のスナップショットにおいて, 連結した最大 クラスタを G とする. このクラスタ G を時間経過とと もに変化するネットワークとみなす. このクラスタは 実社会における集団を表現しており, このネットワーク のエージェントとのながりの変化が, 集団における関係 の変化を意味する. 3.2.2 制限時間と速度 それぞれのエージェントには生存時間 T T L と, 経過 時間 (以下年齢とも呼ぶ）を記録する変数 Ageiがある. 時間経過とともに Ageiは増加し, それが T T L に達す るとそのエージェントは消滅し, 同時に新しいエージェントを投入する. これにより実社会における集団のメン バーの離脱や参加を表現する. リンク数 kiのエージェ ント i の速度 vi(ki)は, 初期速度 v0, 定数 ¯V から以下 のように決定し, 衝突時に次数の変化ごとに更新する. vi(ki) = ¯V kαi + v0 (1) ここで α は次数と速度を制御する変数である. 速度が 大きいほど衝突しやすいため, α によってリンクの獲得 しやすさを調整している. 3.2.3 準安定状態 MAネットワークは一定期間変化を続けると最大ク ラスタ G の平均速度V と平均次数 K が安定する準安 定状態 (quasi-stationary state, 以降 QSS) に達し, そ の時間はおおよそ T T L の 2 倍程度である [6]. ノルム の収束を検証する実験は [5] にならい, QSS に達したと 考えられる 2· T T L 経過時間後のネットワークを利用 する. このモデルでは知人関係を表すため, MA ネット ワークは無向グラフとなる. 集団において, 友人を作 りやすい人は次々と友人を作り人見知りな人は時間が たってもそれほど友人を作らないという性質を衝突後 のエージェントの速度を更新することで表現している. また, 集団からの離脱・参加をエージェントに寿命を導 入することで表現している.
4
提案手法
4.1
動的ネットワーク上の IAL
本節では, IAL[4] を MA ネットワークへ拡張した IAL 手法を提案する. まず QSS に達した MA ネットワーク Gを構築する. ネットワーク G における各ノードは常 にあるエージェントに対応し, G を時間経過とともに変 化させ, T 秒ごとに 1 回 IAL 手法を導入した協調ゲー ムを行い, そのノルムの収束を調べる. エージェントに 設定された Ageiが T T L に達するとそのエージェント は消去され, それまで獲得したリンクを全て破棄し, 代 わりに新しいエージェントを追加する. ネットワーク の変化により G にリンクが形成された場合は, 新しい 相手エージェントの Q 値をランダムに決定する. MA ネットワークでは実験中に各エージェントの次数が変 化するが, 影響力の更新により次数の変化を考慮してい る. IAL を用いた協調ゲームの流れを以下に示す. 1. 各エージェント i はその隣接エージェント j に対 し, それぞれの Q 値を利用して戦略を決定する. 2. 隣接するエージェントへの戦略 sijとそれぞれの 隣接エージェントの影響力 wjを積算し, 4.3 節で のべる方法により自分の戦略を決定する. 3. 2で決定した戦略を元に隣接エージェントと協調 ゲームを行う. 4. 3の結果を利用し隣接エージェントへの Q 値を更 新し, 利得 r を得る. 5. 4で得た利得を利用し自分の影響力を更新し, 隣 接エージェントに伝える. 上記の流れを 1 ゲームとし, これを繰り返す. なお, ス テップ 2, 5 で求める影響力の計算法については次節で 述べる.4.2
影響力
IAL[4]は, 相互に協調している近隣のコミュニティの 影響力を考慮して自分の戦略を決定する集約型学習手 法である. IAL では周囲のエージェントへの戦略を Q 値により決定し, さらに周囲のエージェントの影響力に 基づいて自分の最終的な戦略を決定する. それを用い てエージェント i は隣接する各エージェント j∈ Niと 協調ゲームを行い利得 ri jを得る. その利得から各隣接 エージェントに対する戦略 sijを更新する. また, 利得 の平均値を ri =∑j∈N ir i j/|Ni| とする. エージェント iの影響力の初期値は次数によって wi= kiとし, 以降, 各エージェントとの協調ゲームの終了毎に以下の式で 更新する. wi= (1− β)wi+ βC(si, sj)rjwj (2) ここで 0 ≤ β ≤ 1 は影響力の学習率を表し, C(si, sj) は協調ゲームによる利得を表した符号関数であり 3.1 節の協調ゲームの利得に従い以下のように定義する. C(si, sj) = { +1 if si= sj −1 otherwise (3)4.3
影響力を考慮したアンサンブル法
影響力を考慮したアンサンブル法によりエージェン ト i は, 戦略 s に対し以下の優先度 pi(s)が最大となる 戦略を自分の戦略 siとする. pi(s) = ∑ j∈Ni δ(si, sij)wj (4) ここで関数 δ は任意の戦略 s1, s2 について δ(s1, s2) = { 1 if s1 = s2 0 otherwise (5) となるデルタ関数である.表 1: MA ネットワークのパラメータ パラメータ 値 エージェントの数 N 2000 環境のサイズ L 5000 速度の更新式における α 1.5 初期速度 v0 1 速度の定数 ¯v 1 エージェントの直径 d 2 エージェントの生存時間 T T L 70000∼100000 表 2: QSS に達した時点でのノード数, 平均次数, 頂点 間距離, 冪指数 TTL ノード数 平均次数⟨k⟩ 頂点間距離 冪指数 70000 25.1 1.88 3.13 2.61 80000 74.1 1.95 5.24 2.58 90000 214.1 2.01 8.14 2.75 100000 579.6 2.18 8.27 2.56
5
実験
5.1
実験環境と MA ネットワークの性質
MAネットワークを構築し, ノルムの収束を評価す る. 実験で設定したパラメータを表 1 に示す. なおネッ トワーク構築のデータは 50 回の試行の平均である. 本 研究では MA ネットワークの構築のための粒子衝突の シミュレーションを離散時間で行い, その間隔を 0.05 秒とした. また生存時間 T T L の変化によるネットワー クの変化を調べるために, QSS に達した時点でのノー ド数, 平均次数, 頂点間距離, 冪指数を表 2 に, この時 の累積次数分布の平均を図 2 に示す. T T L が 90000 及 び 100000 の時のネットワークのサンプルを図 3, 4 に 示す. T T Lの増加にともないノード数も増え, 頂点間距離 が長くなる. 一方で平均次数はノード数の増加にあま り影響を受けない. また図 2 より MA ネットワークは スケールフリー性を有することがわかる. その冪指数 は 2 から 3 程度であり実社会のネットワークとおおよ そ同じ [13] ものとなった. 図 2: QSS に達した時点の次数分布（両対数） 図 3: T T L = 90000 の MA ネットワークのサンプル 図 4: T T L = 100000 の MA ネットワークのサンプル5.2
静的 MA ネットワーク上のノルム獲得
の成功率
実験 1 では MA ネットワークを構築し, QSS に達し た時点で変化を止め, その状態のネットワーク上で IAL によるノルムの収束を調査した. 前述の通り, 90% の エージェントが同一の行動戦略を選択したときノルム の獲得に成功したとする. IAL に関連する実験パラメー タを表 3 に示す. なお IAL による以降のデータは 100 回の試行の平均値である. 実験 1 で T T L を変化させ, 表 3: IAL 手法のパラメータ パラメータ 値 Q学習の学習率α 0.1 影響力の学習率β 0.1 学習戦略 ε-greedy ε 0.01図 5: QSS 直後のネットワーク上の協調率の推移 図 6: QSS から 150000 秒間の IAL による協調率の推移 表 4: 静的な MA ネットワーク上のノルムの成功率 TTL 成功率(%) 70000 98.1 80000 93.7 90000 83.1 100000 92.1 IALによる 5000 回のゲームの結果を図 5 に, 5000 ゲー ム後のノルムの収束成功率を表 4 に示す. 図 3 を見ると T T L が 70000 から 90000 までは T T L の増加にともない協調率が上昇が緩やかになった. 一 方で T T L が 100000 のときは 90000 のときよりも上昇 が早くなり, 80000 と同程度の成功率となった. 表 4 か ら 5000 ゲーム後の成功率も高くなったことが分かる.
5.3
動的 MA ネットワーク上のノルム獲得
の成功率
実験 2 では実験 1 のネットワークから時間とともに 構造を変化させつつ, IAL によるノルムの推移を調査す る. QSS から 150000 秒間 MA ネットワークを変化さ 表 5: QSS から 50000 秒後, 1500000 秒後のノルムの収 束率 TTL 成功率(%) QSSから50000秒後 QSSから150000秒後 70000 91.6 98.7 80000 93.6 99.8 90000 98.0 100 100000 97.8 100 せ, 10 秒ごとのネットワーク上で IAL による協調ゲー ムを 1 回行った. 協調率の変化を図 6 に示す. 図 6 を見ると T T L の増加にともない, 協調率が上昇 し, 収束までの時間も短くなった. 表 5 の 50000 秒後に おいては T T L によらずノルムの収束性効率は 90%を 超え, 更に 150000 秒後ではほぼ 100%に近づき, IAL に よって高い確率でノルムが収束した.5.4
考察
静的な MA ネットワークでは T T L の増加にともな いノルムの収束までの時間が長くなるが, 更に大きく すると再び収束までの時間が短くなる. これは図 3, 4 が示すように, T T L が 90000 の時ではネットワークが 密につながっている部分とそれらをつなぐ次数の低い ノードが存在しする. そのため次数の低いノードを境 として局所的なノルムが発生している. 一方で T T L が 100000と大きいとネットワークの全体の密度も高くな り, 局所的なノルムが発生しにくくなった. 動的な MA ネットワークでは, T T L が小さい時には Gのエージェント数が小さく, 図 6 における協調率の 変動が大きいことからエージェントの入れ替わりが激 しくノルムの収束は遅くなったと考えられる. 表 4, 5 において 5000 回の協調ゲーム時点のノルムの収束成功 率を比較すると, T T L = 90000 と T T L = 100000 では ネットワークを動的に変化させたほうが成功率が高い. これは静的なネットワークでは, T T L の増加に連れて ネットワークの構造が複雑になり, 局所的なノルムが 発生し, 全体が 1 つのノルムに収束することを難しく したが, ネットワークの構造が動的に変化する場合は, その変動により局所的なノルムが崩壊することがあり, 結果的に全体にノルムが伝搬したと考えられる.6
結論と今後の課題
本研究では, IAL 手法を動的に変化するネットワー ク, MA ネットワークに適用し QSS に達した時点での 静的な MA ネットワークと時間経過とともに変化する MAネットワークの両方で協調ゲームによりノルムを 高い確率で収束させられることを示した. 今後の研究では, 協調率が低減した時点でのネットワークの状態を 調査する必要がある. また T T L を大きくすると一定の 大きさからノルムの収束が促進されたことを検証する ためにネットワークの中心性やハブとなるエージェン トの動作を調査する必要がある. これらは同様の環境におけるノルムの収束を調査す る上での参考になるだけでなく, １つのノルムに収束 したモデルでの世代交代や競合ノルムの伝搬を時間経 過とともに検証することにも役立つ. これを利用して, 競合するノルムの時間経過による伝搬や別々のノルム を効率的に収束させる方法を導入したり, ネットワーク を動的に変化させながら異なる種類のノルムに収束し たクラスタを衝突させた場合や戦略を変更しないエー ジェントを混ぜることによる収束への影響を調査する ことも考えられる.
参考文献
[1] Chao Yu, Minjie Zhang, Fenghui Ren, and Xudong Luo. Emergence of Social Norms Through Collective Learning in Networked Agent Societies. In Proc. of Int. Conf. on Autonomous
Agents and Multiagent Systems, AAMAS ’13, pp.
475–482, 2013.
[2] Onkur Sen and Sandip Sen. Effects of Social Network Topology and Options on Norm Emer-gence. Coordination, Organizations, Institutions
and Norms in Agent Systems V, Vol. LNCS6069,
pp. 211–222, 2010.
[3] Chao Yu, Hongtao Lv, Honglin Bao, and Yapeng Li. Emergence of Social Norms through Collec-tive Learning and Information Diffusion in Com-plex Relationship Networks. Int. Joint Agents
Workshop and Symposium (IJAWS2015), 2015.
[4] Ryosuke Shibusawa and Toshiharu Sugawara. Norm Emergence via Influential Weight Propa-gation in Complex Networks. In 2014 European
Network Intelligence Conf., ENIC 2014, pp. 30–
37, IEEE Xplore, 2014.
[5] Bastin Tony Roy Savarimuthu, Stephen Crane-field, Martin K. Purvis, and Maryam A. Purvis. Norm emergence in agent societies formed by dy-namically changing networks. Web Intelligence
and Agent Systems, Vol. 7, No. 3, pp. 223–232,
2009.
[6] Marta C. Gonz´alez, Pedro G. Lind, and Hans J. Herrmann. System of Mobile Agents to Model
Social Networks. Physical Review Letters,
Vol. 96, No. 8, pp. 088702+, 2006.
[7] Guido Boella, Leendert W. N. van der Torre, and Harko Verhagen. Introduction to Normative Multiagent Systems. Computational &
Mathe-matical Organization Theory, Vol. 12, No. 2, pp.
71–79, 2006.
[8] Jeroen Keppens Michael Luck Samhar Mah-moud, Nathan Griffiths. Norm emergence: Over-coming hub effects in scale free networks. Proc.
of 14th Int. Workshop on Coordination, Organ-isations, Institutions and Norms (COIN 2012),
pp. 136–150, 2012.
[9] Marta C. Gonz´alez, Pedro G. Lind, and Hans J. Herrmann. System of Mobile Agents to Model Social Networks. Physical Review Letters,
Vol. 96, No. 8, pp. 088702+, 2006.
[10] Jukka-Pekka Onnela, Samuel Arbesman, Marta C. Gonz´alez, Albert-L´aszl´o Barab´asi, and Nicholas A. Christakis. Geographic Constraints on Social Network Groups. PLoS ONE, Vol. 6, No. 4, p. e16939, 2011.
[11] Pu Wang, Marta C. Gonz´alez, Cesar A. Hidalgo R., and Albert-L´aszl´a Barab´asi. Understanding the spreading patterns of mobile phone viruses.
CoRR, 2009.
[12] Adam Walker and Michael Wooldridge. Under-standing the Emergence of Conventions in Multi-Agent Systems. In Proc. of the 1st Int. Conf. on
Multiagent Systems, pp. 384–389, 1995.
[13] 増田直紀, 今野紀雄. 複雑ネットワークの科学. 産 業図書, 2005.
