JAIST Repository

JAIST Repository

https://dspace.jaist.ac.jp/

Title

る研究

Author(s)

Citation

Issue Date

Type

Text version

URL

Rights

Description

修 士 論 文

マルチエージェント系における 集団的戦略変更に関する研究

指導教官

東条 敏 教授

北陸先端科学技術大学院大学 情報科学研究科情報処理学専攻

吉田 憲世

2001年²月¹⁵日

Copyrightc 2001byken'seiyoshida

要 旨

複数のエージェントからなる集団が^,動的な環境の下で共通の目的を達成しようとする場 合^,個々のエージェントが直面している局所的問題の解決と^,集団全体が持つ大域的目標の 達成をうまく整合させる必要がある^.

このような状況下における解法の¹つとして^,エージェントに複数の戦略を持たせ^,環 境の変化にあわせてエージェントが採るべき戦略を選択する方式が挙げられる^.あるエー ジェントが^,集団にとって不利益を及ぼすような臨界状態を感知したとき^,このエージェン トは他のエージェントに戦略を変更して臨界状態を回避させるための通信を行う^.

この戦略変更の判断材料となる情報を送受信する方法として^,二つのアプローチが考え られる^.一つは大域的な通信を使って全てのエージェントに通信を行う方法で^,系を構成す るエージェントが全てが等しく情報を享受できるという長所を持つが^,長距離通信や通信 における情報分配による処理数の増大によって無視できない遅延を生み出すという短所を 同時に併せ持つ^. 逆に^,局所通信を使う方法は情報伝達に対する遅延は発生しないが^,情報 源から発生した情報が漸時拡散していくことから^,エージェントの戦略変更に利用できる 判断材料が空間上の位置によって異なる現象が起きてしまう^.

そこで^,本研究では局所通信系を使いつつも^,その短所を補う方式について提案を行う^. 具体的には^,緊急に必要ではなくても将来の戦略変更に利用できる可能性のある情報をあ らかじめ流布させておくことで^,実際にその情報が必要になったときに空間上の位置によっ て生じる受け取る情報量の格差を埋める方式の研究を行う^.

実際に「エネルギー補給問題」題材にして実験を行い^,提案モデルが実際に目的達成に 有用であることを示すことができた^.だが^,この提案モデルは平常時から通信を頻繁に行う ため^,通信コストの総計が高くなってしまうという課題が残ってしまう結果となった^.

目 次

1 はじめに ¹

2 研究に関するサーベイ ³

2.1 研究の背景 ^{. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3}

2.2 エネルギー補給問題と^{BlindHunger Dilemma . . . . . . . . . . . . . . . . 4}

2.3 BlindHunger Dilemmaの特徴 ^{. . . . . . . . . . . . . . . . . . . . . . . . . 6}

3 シミュレーションでの基本モデル ⁹ 3.1 系全体の設定 ^{. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9}

3.2 エージェントの戦略とアルゴリズム ^{. . . . . . . . . . . . . . . . . . . . . . 11}

3.2.1 通常型戦略 ^{. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13}

3.2.2 扇動者型戦略 ^{. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14}

3.2.3 移動型戦略 ^{. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17}

4 シミュレーションの結果と検証 ¹⁹ 4.1 各種パラメータについて ^{. . . . . . . . . . . . . . . . . . . . . . . . . . . . 19}

4.2 通信のコストに関する比較 ^{. . . . . . . . . . . . . . . . . . . . . . . . . . . 20}

4.3 待機時のエネルギー消費率に関する比較 ^{. . . . . . . . . . . . . . . . . . . 22}

4.4 提案モデルにおける情報の信頼度に関する比較^{. . . . . . . . . . . . . . . . 26}

4.5 提案モデルにおける通信の可否を制御する閾値に関する比較 ^{. . . . . . . . 29}

5 まとめ ³⁴

第

章 はじめに

複数のエージェントからなる集団が^,動的な環境変化の下で共通の目標を達成しようと する場合^,個々のエージェントが直面している局所的問題の解決と^,集団全体が持つ大域的 目標の達成をうまく整合させる必要がある^{1 .}

このような状況下における一つの解法として^,全てのエージェントに複数の戦略を持たせ ておき^,環境の変化に合わせてエージェントが取るべき戦略を選択する方法があげられる^. あるエージェントが^,集団全体に不利益を及ぼすであろう臨界状態を感知したとき^,この 臨界状態の発生を他のエージェントに知らせる方法が二通り挙げられる^.一つは臨界状態 を感知したエージェントが大域的な通信を用いて全てのエージェントに情報を知らせる方 法^.もう一つは局所的な通信を用いて情報をエージェント間で次々と伝播させる方法であ る^.前者の方法は^,一つの情報源から出された情報⁽集団全体の意志決定の材料⁾を全ての エージェントが平等に享受できる長所がある一方^,長距離通信や情報分配による処理数の 増大により情報伝達に対する無視できない遅延が生み出されるという短所を持つ^.逆に後 者の方法は^,情報伝達に対する遅延は発生しないが^,情報源からの情報が漸時拡散してして いくことから^,エージェントが戦略変更に利用できる材料が空間上の位置に応じて異なる ことになる^.

そこで^,本研究では局所通信であっても^,戦略変更のための情報をより効果的に伝播で きるモデルの提案を行う^.具体的には^,例え緊急に必要ではなくても^,将来の環境の変化に よって必要になってくる可能性のある情報をあらかじめ伝播させておくことで^,空間上の 位置によるエージェントの享受できる情報の格差を埋める研究を行う^.

1例えば^,危険な区域で仕事を行うエージェントが故障が発生するような危険が近付いたと感知した場合^, 集団全体の目標のために動き続けるメリットよりもエージェントの故障によって集団全体の数が減少する デメリットが大きい場合がある^.このとき危機に直面すると予測されるエージェントは一時的に作業を放棄 し^,危険をやり過ごす方がよいだろう^.

以下^,第²章では研究の背景に関するサーベイ^,第³章では自分の提案するモデルの説明^, 第⁴章ではこのモデルの検証を行う^.

第

章

研究に関するサーベイ

2.1

研究の背景

前章で記述したように^,エージェントに対して通信を行う際に^,2通りのアプローチが考 えられる^.

環境の変化を察知したエージェントが残り全てのエージェントに対して通信を行なう方 法の場合^,長距離の通信^,情報分配のために遅延が発生するが^,この遅延は^,環境や系の設定 次第で無制限に大きくなりうるものである^.

そこで^,沼岡 ^[1] は^,局所通信を利用する方法で局所的な環境変化によって一部のエー ジェントが戦略を変更した場合に^,最終的に集団として新たに発生した戦略に移行するこ とが可能であるかを研究した^.空間中に共有の補給基地が一箇所にのみ置かれている状況 を考える^.エージェントの目的は^, 効率良くエネルギーの補給を行ない生存することである

1

. 最悪の場合^,全てのエージェントが同時にエネルギー補給を必要とし^,一箇所に集まっ てくる^.このとき^,エネルギーを求めて補給基地に群がるエージェントと^, 補給が終り補給 基地から離れようとするエージェントの間で衝突が起こる^.

この問題を ^{BlindHunger Dilemma}と呼ぶ^.沼岡は^,このとき^"扇動者^"と呼ばれる周囲 に戦略変更を促す通信を発信するモードをエージェントに組み込むことで混雑を回避し ている^.扇動者モードには^,エージェントが環境の変化によって集団全体に不利益を及ぼす ような臨界状態を感知したときに切り替わる^.このとき^,自身は環境の変化が及ぼす不利 益^{(BlindHunger Dilemma}で言うなら混雑⁾を回避する戦略型のみを採るようになり^,か つ周囲にも扇動者モードに切り替わったことを知らせる通信を行う^.これによって扇動者 モードが伝播していき^,集団全体⁽もしくは臨界状態と直接関係ある集団の一部⁾として臨

1沼岡は^,自律ロボットを考えた場合^,定期的なエネルギー補給は重要な問題である^,としている^.

図 ^2.1: エネルギー補給問題 界状態を回避する方向へ戦略変更がなされる^.

しかし^,この ^{Blind Hunger Dilemma}の問題設定はエージェントが¹ヶ所に集まりやす

く^,局所通信のデメリットが表れにくい問題設定である^.また^,マルチエージェントを分散 協調システムとして見た場合^,全てのエージェントが固まって動くという設定は現実でも 例の少ない特殊な状況を想定した問題設定のように思える^.

そこで^,本研究ではエージェントが戦略変更を促す際の通信の範囲を局所的なものにし^, かつエージェントが比較的ばらけた状態でもうまく戦略の変更を行なうことが可能な方式 の作成を目指す^.

2.2

エネルギー補給問題と

詳しい問題設定を行う前に^,ここでエネルギー補給問題と^{BlindHungerDilemma[2]}に 関してもう少し詳しい説明を行う^.

エネルギー補給基地があり^,そこでエネルギー補給口の数がそこに集まる可能性のある エージェントの数に比べて十分小さい状況を考える^.このような制約があるときに^,エー

図 ^{2.2: Blind Hunger Dilemma}

ジェントはどのように行動すればエージェント全体として効率よくエネルギーの補給を行 うことができるかという問題をエネルギー補給問題 ⁽図^2.1)という^.

補給基地からは常に何らかの刺激⁽匂いや光^,信号など⁾を発している^.この刺激は補給 基地から離れる程距離の²乗に反比例して弱くなっていく^.エージェントはこの刺激を参 照することにより^,エネルギー補給場所の方角⁽これは^,いわば嗅覚のようなもので正確な 距離までは分からない⁾を知覚することができる^.また^,エージェントの視界と通信距離も 限られたものとなる^.このような限られた制約の中で^,いかにしてエージェント全体として 効率よくエネルギーを補給することができるかが問題の焦点となる^.

エネルギーを消費したエージェントは早く補給基地に取り付きたいのだが^,全体のエー ジェントの動きを知ることはできない^.仮に多数のエージェントが一度にエネルギー補給 が必要となり補給基地に集まった場合^,補給口により早くたどり着いたエージェント以外 は^,補給基地周辺で凝集した形で^,順番を待つことになる^.

エージェントが補給基地周辺で十分に秩序だった行動がとれるように設計されているな らば^,列を作るなどして一定時間以内にエネルギーを必要としているエージェントが全て 補給を行うよう行動することができるだろう^. しかし^,エージェントが非常にプリミティ

ブな行動しかとれない場合^,補給を完了した一番内側のエージェントは周りを囲まれてし まい動きがとれなくなり^, 他のエージェントはそれら補給を完了したエージェントが補 給口から動けないため補給できないという状態に陥る⁽図^2.2).この状態を ^BlindHunger

Dilemmaと呼ぶ^.

そこで^,このような状態に陥らないように^,集団として自発的にできるだけ効果的にそ の状態を回避するような機構が必要となる^.2.1章で書いたように沼岡はエージェントに扇 動者というモードを組み込むことによってこの問題を回避する研究を行っている^.また^,戦 略変更とは観点が違うが^,エージェントに単純な行動習性のみを与え^,非線形ダイナミクス を用いることによって^,秩序だった行動が自己組織化されないか調べる研究も栗原^,岡田ら

[4]によって行われている^.

なお^,この問題は設定はエージェント同士が接触^,またはローカルな視覚と通信手段しか 使えないような状況において共同作業をする場面を想定したものである^.例えば^,未知の 世界の探索や複雑な環境では構造が単純で丈夫なロボットを多数協調させる方がリスク が小さい^.しかしながらうまく協調動作を行わないと目的を達成するすることはできない^. このような場合にロボット間で常に大域的な通信が行える可能性は保証できず^,集中制御 系を考えることは妥当ではない^.

2.3 Blind Hunger Dilemma

の特徴

本研究では前出の論文との比較を行えるという観点から^{, Blind Hunger Dilemma}に基 づいた実験を行なうことにした^.そこで^,実験を行うにあたって^, 問題の特徴を調べた^.

Blind Hunger Dilemma の設定から読みとれることは^,「多数のエージェントに対して

資源を提供する少数の窓口があり^,この資源を巡って混雑が引き起こされる」というもの である^.そこで^,実験の環境と似た事例が現実の世界にないか調べることにした^.人工的な 世界よりも^,できるだけ現実の世界をモデルに近い設定を用いた方が^,現実世界への応用・

フィールドバックが可能だからである。

以下は^,自分で調べた^,同様の性質⁽多数のエージェントに対して資源を提供する少数の 窓口があり^,この資源を巡って混雑が引き起こされる⁾を持つシチュエーションの例である^.

自家用車とガソリンスタンド

人間と食料品店・コンビニエンスストア・レストラン等

動物と餌場・砂漠のオアシス等

人間と^ATM

フリーのエンジニア・ライター等とその仕事

これらの例題は体⁽機体⁾を動かすのに必ず必要になる資源を提供する類のものである^. 後者²つは貯金を引きおとしや給与の受け取りなど^,生活を行なうために必要になってく る金銭の受渡しを行なうものである^.このような全てのエージェントに対しての必需品を 取り扱う場面・業界では^,このような混雑が起こりやすいく^,また必需品の需要量もエー ジェントごとのばらつき⁽個体差⁾が少なく^,コンピュータ上に再現しやすいと考えられる^.

レンタルビデオ店

チケット売り場

また^,必需品を供給しているわけではないが^,このような娯楽・サービスを提供するとこ ろでも^,人気があったり希少価値があれば同様の混雑が出来てくると考えられる^.もっとも この場合^,提供する資源は満足度などのあいまいなものになると考えられるので^,パラメー タなどの設定が上記のものより難しいと考えられる^.

多数のユーザ・ジョブが少数のマシン・サーバにアクセスする

建築や工事等の資材とその補給

この²つは^,何か物事を進めるために必要になってくる類のものである^.これらは上記 の必需品の供給する場合と同じく^,供給される資源が無いと物事が先に進まなくなる性質 があるため混雑が予想される^.だが^,場面によって必要な資源の量にばらつきがあったり^, エージェント数自体が不定である場合があるなど^,コンピュータ上での再現は若干難しい ものと考えられる^.

これらの事例に共通していえることは^,(特に人間相手の時に⁾レジや^ATMなど列を作 る窓口が存在することである^.先ほど記述したように^,資源の供給を受ける際に列をつくる ことが最も効率が良いと思われるため^,特に人間相手の時は同様のシチュエーションが多 いと考えられる^.しかし^,人間も集中制御された存在ではなく^,視界も有限なので^,例えば補 給基地を店舗単位の大きなもので考えれば^,十分^{BlindHunger Dilemma}と同様の状況を 作り出すことが可能であると考えられる^.

しかし^,上記の例をそのままモデルとした場合でも^,地域差などでパラメータが変化する ので^,問題設定が非常に難しくなってしまうおそれがある^.加えて^,「自家用車とガソリン

スタンド」の例や「人間と食料品店・コンビニエンスストア・レストラン等」の例などは^, 本人の不注意でもない限りエネルギー切れることなど無いことから分かるように^,補給口 の数が十分用意されている^,問題に適さない^{(Blind Hunger Dilemma}自体が起こらない⁾ 例も多くある^. 実際に日本の都道府県別面積 ^[12] と全国の給油所^(SS)数^[13] をパラメー タとして実験してみたが^,特にエネルギー切れになるエージェントはでてこなかった

よって^,これらの事例からうまく特徴をつかみ^,抽象化することが大切だと思われる^. 以下に^,上記⁹つの問題に対して共通していると思われる性質を記述しておく^.

エネルギーを消費する時間に比べて^,補給する時間はごく僅かですむ

生物においても機械においても^,活動する時間に比べて補給のための時間はわずか で済む^.

移動時のエネルギー消費量に比べて^,待機時の消費量は少ない

生物の場合^,起きて活動している時と寝ている時とでは寝ている時の方がエネルギー 消費量は小さいし^,機械は電源^oにすると消費量を限りなく⁰に近くすることがで きる^.

エージェントは基本的に^,補給→離れる→活動する→補給に向かう^,という行動を繰 り返すことになる

単純に邪魔になるという理由の場合もあるが^,仕事などやらなければならないこと がある⁽人間^),その場に留まっていると危険である⁽自然界の動物⁾などの種々の理 由で^,補給を受けた後その場から離れないケースは非常に少ない^.また^,補給後に再び 補給に戻るのはエネルギーが非常に少なくなってからである^. エネルギーが少なく なってきたから徐々に補給基地との距離をつめるなどというケースはほとんどない^.

第

章

シミュレーションでの基本モデル

3.1

系全体の設定

3030マスのフィールドに¹⁶⁰体のエージェントと¹⁶個の補給口がある環境を考える^. 補給口¹個あたり¹⁰体のエージェントが補給に来るというのは^,問題設定の大前提である

「エネルギー補給口の数がそこに集まる可能性のあるエージェントの数に比べて十分小さ い状況」に当てはまる^.9マス内にエージェントが^1.6体という密度も局所通信系を扱うの であれば^,十分現実的な数字である^.

エージェントは^1step毎に縦横斜めの⁸方向に動くか^,その場に留まるかの⁹種類の行 動のうち¹つを選んで実行できる^.エージェントは動けば ^{0.5%/step ,}動かなければパラ メータ ^{Cstop%/step (Cstop 0:5)} のエネルギーを消費する^. 時刻 ^t での移動に関するエネ ルギーの消費量を ^{Cmove(t) ,}エネルギーの最大値を ^FULL とすると^,

C

move (t)=

8

<

:

FULL0:5%; when agent move

FULLC

stop

%; when agent don't move

(3.1)

となる^.仮に^,エージェントがたえず動きまわるなら^,エージェントは^200step弱に一度補 給を受けなければならないことになる^.移動時に対して^,待機時はエネルギーの消費量が小 さい^{. Cstop} の値はエージェントがどのようなものを想定するかで変わってくる^.例えば^, 動物や眠ったり機械が待機状態になったときは^,その消費エネルギーは極わずかとなる^.こ のような場合は ^Cstop は限りなく⁰に近くなる^.対して^,待機時もエージェントは何らかの 仕事をしていると考えるのが自然だとするならば ^Cstop の値は^0.5に近くなる^." 移動^"自 体に必要なエネルギー量と^,エージェントの仕事のエネルギー量の比が^2:3ならば移動時

消費量 ^0.5 に対して ^Cstop は^0.3になる^{1 .}

なお^,Cstop の大きさの変更が必要なシミュレーションを行うとき以外は^{Cstop =0:25}と 値を固定して実験を行うことにする^.これは^,人間の消費カロリー表^[14] において^,"散歩

(歩く^)"の消費カロリーと^"立ち仕事^"の消費カロリーがほぼ同等だったからである^. エー ジェントがロボットや機械であることを考えたとき^,この値はエージェントの用途や仕事の 内容によって如何様にも変動すると思われるので^,移動に必要なエネルギー消費量とエー ジェントが目的を達成するための仕事のエネルギー消費量を等価として単純化させても らった^.

また^,エージェントが通信を行った場合にも^,一回の通信毎に一定の値のエネルギーを消 費する^.この値も実験時にパラメータとして変動させているが^,パラメータを固定する場合 は単純化のため ^{Ccom =0:25}とさせてもらった^. 局所通信という設定なのでエージェント 同士の通信は^,発信元のエージェントの周囲⁸マスに存在するエージェントのみが受信で きるものとする^.

よって^,時刻 ^t でのエネルギーの値を^{E(t) ,}通信に関するエネルギー消費量のパラメー タを^{Ccom ,}時刻^t に ^n(t) 体のエージェントに対して通信を行ったとすると^,

E(t+1)=E(t) C

move

(t) (C

com

n(t)) (3.2)

となる^.

エージェントが感知できる事象は^"視界内にどのエージェントが存在するか^" と^"補給 口から発生する刺激の大小^"のみである^.前者はエージェントが接触しているか⁽通信でき るか⁾と^,視界内にどの程度の密度でエージェントが存在するかの判断に^,後者は補給口の 向きと補給口と近いか遠いか⁽いわば嗅覚のようなもので^,正確な距離は分からない⁾の判 断に使用する^.

補給基地の上下左右には補給口が設置されており^,エージェントはここに取り付くこと によって補給を受けることができる^.1体のエージェントが補給を終えるのに^1stepの時間 がかかる^.例えば^,自動車は給油無しでも何時間もかけて走行することができるのに^,給油 は⁽タンクの容量にもよるが⁾ものの¹⁰分弱ですんでしまったり^,電池式の機械の電池交 換がものの数分で終るように^,機械の稼働率を考えた場合約^200step弱に^1stepの補給行 動という値は現実的な値だと考えられる^{2 .}

1エージェントは移動時も変わらず何らかの活動をしており^,動く場合は^"移動^"+"仕事^"分の消費量^.立 ち止まっている場合は^"仕事^"分のみを消費すると考える^.

2エージェントが⁽現在の技術での⁾充電式のロボットだと仮定した場合などは^,この値は不自然かもしれ ない

研究の目的が^,"エージェントが¹箇所に集まらなくとも局所通信系で戦略の変更を行え る方式の提案^"なので^,16の補給口が全てフィールドの中央に集まっている場合と^,補給口 を⁴個ずつ⁴箇所に分散させてエージェントがフィールド上にまんべん無く存在する場合 の²パターンを比較して実験を行う^.

3.2

エージェントの戦略とアルゴリズム

本研究では^,比較のためにエージェントを³種類用意する^.

戦略を¹種類⁽通常型戦略⁾しか持たないもの

BlindHunger Dilemmaに直面しても戦略変更して事態を改善できないものである^.

通常型戦略は^,補給を終えた後に補給基地から離れるように行動し^,エージェントが 感知する刺激値を参照して^,補給基地からある程度離れたと判断してからランダム に動くようになる^.エネルギーがある閾値以下になったときに補給を受けるために補 給基地に向かう行動を行う^.

このエージェントは^,関数^flag1 と ^{flag2 (p12}参照⁾を^on にできない^.

沼岡が実験した^,通常型戦略の他に扇動者戦略を持ったもの

BlindHunger Dilemmaに直面したとき^,混雑の内側にいるエージェントから逃げ道

を開けてもらうために^,エネルギーが少ないエージェントであっても一時的に補給口 から離れる行動をとるように戦略変更を行う通信を発信する^.扇動者戦略自体が補 給口から離れる動きをするようにできており^,これが伝播することによって混雑が解 消される⁽図 ^??参照^).

このエージェントは ^{flag2 (p12}参照⁾を ^onにできない^.

本研究が提案するモデル

通常型^,扇動者の²つの戦略の他に^,混雑の外側で ^{Blind Hunger Dilemma}に直面し たエージェントが^,混雑を解消するためにすいている補給口を目指す³種類目の戦略 を有する^.この戦略を有効に活用するためには^,補給を終えたエージェントが視界の 中にどれだけのエージェントが存在するかを確認し^,すいていると判断すればその情 報を広めるための通信を行わなければならない^.

このタイプのエージェントが補給を終えたとき^,その時刻 ^t での補給口^SB(x;y)か ら見える視界内のエージェントの数^Num(x;y;t)がある閾値^Few以下の場合^,その

補給口を^"すいている補給口^"としてその座標を記憶しておき^,エージェント中に伝 播させていく^(p11参照^).ただし^, 補給口の混み具合は時間が経つ毎に変化するもの であるため^,時間が経つほどその情報は信頼できないものとなる^.そのため^,エージェ ントは^"すいている補給口の座標^"の情報だけでなく^,"残り何^step後までその情報 が信用できるか^" という基準⁽仮にこれを情報の信頼度呼ぶ⁾を同時に持たなければ ならない^.情報の信頼度 ^Trust(t) はすいている補給口を感知したときにパラメータ

Hold と同値になり^,以後^1step毎に¹ずつ減っていく^.

Trust(t)= 8

<

:

Hold; Num(x;y;t)Fewwhen supply energy

Trust(t 1) 1; other

(3.3)

エージェントは ^{Trust(t) > 0} かつ^{, E(t) > M} の間^{3 ,}すいている補給口の座標

SB(x;y) と ^Trust(t) の情報を伝播させていき^{, Trust(t) 0} になればその情報を 破棄する^.

この方式は通信の回数が増える性質上^,多少余分なエネルギーを使わなければなら ないが^,前もって戦略変更に必要な情報を広めておくことで^"効率良くエネルギーの 補給を行い^,できるだけ多くのエージェントを生き残らせる^"という目的に非常に有 効に作用すると思われる^.

戦略変更を行うべきかどうかの評価には^{, flag1(t) ,flag2(t)} という関数を用いる^.

flag

1

(t) は混雑の内側で^{, flag2(t)} は混雑の外側でそれぞれ ^{BlindHunger Dilemma}を 感知したときに¹となる関数で^,これらの致命的な状態を回避する戦略変更を行う条件と なっている^.flag1(t)は移動方向 ^D(t) の値が⁴以外⁽⁴はプログラム中で動かない^,もしく は動けないことを示す^.つまりエージェントが移動が可能⁾になったとき^,flag2(t) はエー ジェントの座標 ^A(x;y) が目的地⁽すいている補給口⁾の座標^SB(x;y) に近付いたときに

0になる^.

flag

1 (t)=

8

>

>

>

<

>

>

>

:

0; D(t)6=4

1; when agent can't leavesupply base

flag1(t 1); other

(3.4)

flag

2 (t)=

8

>

>

>

<

>

>

>

:

0; (jSB(x) A(x)j1)^(jSB(y) A(y)j1)

1; when agent can't approachsupply base

flag2(t 1); other

(3.5)

3通信にエネルギーが消耗されるため^,ある程度エネルギーに余裕がないと通信ができないようにするた め^{. M} はパラメータ⁽閾値^).

Usually strategy Instigator strategy

Movement strategy can’t approach

supply base (flag2(t) = on)

|SB(x)-A(x)| < 2 and

|SB(y)-S(y)| < 2 (flag2(t) = off)

can’t leave supply base (flag1(t) = on)

not(D(t) = 4) (flag1(t) = off)

図 ^3.1: 戦略変更条件

3.2.1

通常型戦略

通常型戦略では^,エネルギーが少なくなったら補給基地へ近付き^,補給を受けた後は補給 基地から離れ^,ある程度離れたと判断したときランダムに動くような戦略である^.

エージェントは^,まずエネルギーの残量 ^E(t) を調べ^,ある閾値 ^Hungry 以下だと空腹 状態⁽図^3.2の^{Hungry condition)}となり^,補給基地に近付こうとする^.空腹状態では^,エー ジェント自身が存在するマスを含む周囲⁹マスの刺激の値を大きい順にソートし^,各移動 方向への優先順位を決定する^.次に^,優先順位の高い順からそのマスが空いているか調べ^, 空いている中で一番優先順位の高いマスへ移動を行う^.このとき^,エージェントが現在のマ スより刺激値の大きいマスへ移動できず^,同じマスにとどまる行動をとった場合^,補給基地 の付近が混雑していると判断し^,flag2(t) の値を¹にする^.

エージェントが空腹状態でない場合^,次に現在受けている刺激の量^F(t) を参照し^,ある 閾値 ^N 以上だと補給基地に近い場所にいると判断して^,刺激の小さい方向へ移動しよう とする⁽図^3.2の^{Escape mode).}この状態では^,上記とは逆にエージェント自身が存在する マスを含む周囲⁹マスの刺激の値を小さい順にソートして各移動方向への優先順位を決 定する^.周囲のすいているマスの中で最も優先順位の高いところへ移動を行う^.このとき^, エージェントが現在のマスより刺激値の大きいマスへ移動できず^,同じマスにとどまる行 動をとった場合^,補給基地の付近が混雑していると判断し^{, flag1(t)}を¹にする^.

Usually condition (moveing randomly)

Hungry condition (approaching supply base)

Escape mode

(pasting from the supply)

en(t) < H en(t) = FULL

(supplying energy) force(x,y) > N

force(x,y) < N

図 ^3.2: 通常型戦略の状態変更条件

上記の²つの状態に当てはまらない場合は^,ランダムに動く⁽図^3.2の^Usuallycondition).

図 ^3.3にこの戦略のフローチャートを示す^{. approachSB} はエージェントの周囲⁹マス を刺激の大きい順ソートして移動方向の優先順位を決め補給基地に近付こうとする行動^,

leaveSB はその逆順ソートで移動方向の優先度を決め補給基地から遠ざかろうとする行

動である^{. D(t)} は時刻 ^t で進んだ方向を示し^,0は左上^,1は上^,2は右上^,3は左^,4は中央⁽動 かず^),5は右^,6は左下^,7は下^,8は右下を示す^.また提案モデルの場合^,移動の後さらに通信 可能範囲にエージェントがいないか調べ^,伝えるべき情報があれば^(Trust(t)>0)通信を 行い情報を伝播させる行動をとる^.

3.2.2

扇動者型戦略

補給を終えた後^,その場から脱出できない状況を感知した^{(F(t)>N;D(t)=4)}ときに^, エージェントは扇動者戦略を採るようになる^.

まず^,自分の座標の刺激より値の大きい方向⁽つまり補給口より遠ざかる方向⁾ のエー ジェントに同じ扇動者型戦略を採るように^(flag1(t)=1にパラメータを変えるように⁾戦 略変更を促す通信を行う^.その後^,扇動者自身は補給口から遠ざかろうとする行動⁽通常型 戦略の ^{escape mode} と同じ行動⁾をとる^.このときエージェントの移動方向が ^{D(t) 6=4 ,} つまり移動が可能であったときに混雑が解消されたと判断して ^flag1(t)=0 となる^.

図 ^3.3: 通常型戦略のアルゴリズム

図 ^3.4: 扇動者型戦略のアルゴリズム

(a) (b)

(c) (d)

図 ^3.5: 扇動者が混雑を解消する様子

図^3.4にこの戦略のフローチャートを示す^. communicate1(0;1;2;3;5;6;7;8)は^,方向⁰

〜^3,5〜⁸にいるエージェントのうち^,刺激値が自分の座標より高い方向にいるものにのみ 通信を行う関数である^.

実際にこのエージェントが混雑を解消するのは^,補給口に取り付くエージェントの²層 目^,3層目のエージェントにこの扇動者戦略が伝染していき^,外側から脱出口が開く形にな ると思われる^.

図^3.5 はこの様子を示している^.図中^,太線の○で示した補給済エージェントが戦略変更 のための通信を外側のエージェントに向かって発信している^(a).通信を受信したエージェ ントはそれぞれ外側へ脱出しようと移動を開始したり^,さらに扇動者になって外側への脱 出口を開けようと通信を開始する^(b).そうして開けられた脱出口を補給済エージェント が通過し^,開いた空間へまだ補給を終えていないエージェントが入り込む^(c)(d).

図 ^3.6: 移動型戦略のアルゴリズム

3.2.3

移動型戦略

補給をしようと補給基地に近付こうとして混雑を感知し^,かつ^,今取り付こうとしてい る補給口以外に現在すいているであろう補給口の位置を知っている場合^,エージェントは この戦略を採るようになる^.

エージェントは^,まず現在値と目的地の差から目的地へ到着するための方向を計算し^,優 先順位をソートする^.もし^,移動方向に邪魔なエージェントなどの障害物が存在するような ら^,右手法⁴ を用いて迂回するようにする^.さらに^,エージェントが通信を行う余裕がある

(E(t)> M)と判断した場合^,すいている補給口をの位置を教える通信も行う^. そして^,目

的地の近くについたとき^{((jSB(x) A(x)j1)^(jSB(y) A(y)j1)),}もしくは情報の 信頼度が無くなったとき^(Trust(t)<0)に ^flag2(t)=0となって通常型戦略に戻る^.

図 ^3.6 にこの戦略のフローチャートを示す^. movetothedestination は^,目的地に移動す るための方向を計算し^,右手法で障害物を迂回するよう移動方向を計算する関数である^.

この移動型戦略は^,エージェントが空腹状態^{(E(t) < H)}になってから現れる戦略であ るが^,もし空腹状態になる閾値 ^Hungry よりも通信を行う余裕があると判断する閾値 ^M の方が小さい場合^,この戦略に切り替わる瞬間は^,外側から混雑を解消する⁽戦略変更を促

4右側の壁に沿って移動する手法

図 ^3.7: パラメータ ^Hungry<M の場合の移動型戦略に切り替わる瞬間 す⁾扇動者になりうる⁽図 ^3.7).

もしこれが実現すれば^,"あるエージェントが集団全体に不利益を及ぼすであろう臨界状 態を感知したとき^,この臨界状態の発生をできるだけ早く他のエージェントに知らせる^"

というエージェントの戦略変更に関する研究の目的と^,"緊急に必要ではなくても^,将来の 環境の変化によって必要になってくる可能性のある情報をあらかじめ伝播させておくこと で^,局所通信系であっても空間上の位置によるエージェントの享受できる情報の格差を埋

める^"という本研究の目的とをうまく両立させることができると考えられる^.

第

章

シミュレーションの結果と検証

4.1

各種パラメータについて

ここで各種パラメータについて設定しておく^.比較実験においてパラメータの変更を行 うとき以外はこの値を守ることとする^.

まず^,エージェントの稼働率を考えると^,すぐに空腹状態になって補給に向かうのは効 率がいいとは言えない^.一方でなかなか補給に向かわないように設計するとエネルギーが 切れるエージェントが続出してしまう^.エージェントが動かないときのエネルギー消費量

C

stop を ^{0:25(%), 1}回の通信のエネルギー消費量 ^Ccom を ^0:25(%)としたとき^,補給口¹⁶ 個を全て中央に集めた場合⁽以後これを^{World 1}と呼ぶ⁾は 空腹状態となる閾値^Hungry が^20(%)で^,補給口を⁴箇所に⁴個ずつ分散させた場合⁽以後これを^{World 2}と呼ぶ⁾では

Hungry=15(%)で比較可能で^,かつエネルギー切れのエージェントが少なめの結果が得

られた^.よって^,これらの値でシミュレーションするのが現実世界でもフィールドバックし やすいと考えられるので^,このパラメータで実験を行う^.

前出の^{Cstop =0:25(%)(}移動時の半分⁾という値は^,移動時は^"移動^"と^"仕事^"に^,待機 時は^"仕事^"にのみエネルギーを使っていると考えたとき^,"移動^"の消費エネルギーと^"仕 事^"の消費エネルギーを等価に設定したため^{. Ccom =0:25(%)}も^"通信^"と^"仕事^"のエネ ルギー消費量を等価とした^.人間のカロリー消費量^[14] が大体この値になっているので参 考とさせてもらった^.これらのパラメータはエージェントをどんな機械⁽もしくは生物⁾と 想定するかで変わってくるものなので単純化させてもらった^.

提案モデルで新しく得られた^"すいている補給口^"の情報を何^step保持するかを決める

Hold の値は上記パラメータのとき ²⁰ 前後で最も良い数値が出たので ^{Hold = 20(step)} を使った^.

"すいている補給口^"の情報をやりとりする通信を行う余力⁽エネルギー⁾ があるかどう かを判断する閾値 ^M は空腹と同時に状態が切り替わるという設定が自然だと感じたので

Hungry と同じ値を使った^.

エージェントの視界は周囲¹マスのみで^,補給が終った後^,視界内に⁽自分を含め⁾²体以 下のエージェントしかいなかった場合に^,エージェントはその補給口を^"すいている^"と認 識する^.

以下の実験結果は^,10000step の実験を ¹⁰⁰ 回試行した結果である^.

4.2

通信のコストに関する比較

まず始めに^,提案モデルがうまく働くのか¹ 調べる意味も含めて^,1回の通信にかかるコ スト^Ccom を変化させて性能を比較してみた^.

はじめに^,16ヶ所の補給口を全て中央に固めたフィールドにて実験を行った⁽表^4.1,図

4.1).その結果^,扇動者モデルと比べて^,通信の機会が多くなったことによってエネルギー

の減少が速くなり^,頻繁に補給基地は向かわなければならなくなるが^,"集団全体に不利益 をもたらす臨界状態を回避するのに役に立つ情報を事前に広めておくことで^,局所通信系 であっても情報空間上の位置における戦略変更の判断に使える情報の格差を埋める^"とい う当初の目的はひとまず達成できたと考えられる^.

エージェントが¹ヶ所に集まりやすい設定であるせいか^,通信コストが上がるにつれて^, 必要以上の通信が仇になってかえってエネルギー切れが起こりやすくなったようだが^,通 信のコストが移動や作業に使うエネルギー量を越えてもある程度までは扇動者モデルよ りもよい結果を残した^.

表^4.2,図^4.2は^,同じ実験を補給口が分散された状態で行ったものである^.補給口が分散 されたため^,混雑はある程度解消される設定ではあるが^,局所通信系では情報の伝達がやり にくい状況であるとも考えられる^.

結果は^{, World 1} で実験したものよりもよいものであった^.Ccom の数値を上げていって も^,かなり上昇させるまでは扇動者モデルより死亡エージェント数が少なく^,Hungryと ^M のパラメータは ^{World 1} よりも生存に不利なのだが ^{Ccom 0:6} までは補給の回数^,エー ジェントの死亡数ともによい結果を示した^{2 .} この結果は^,環境の設定的に単純に混雑が解

1仮に通信のコストが⁰でも沼岡の扇動者モデルより効率が悪いようならば^,わざわざ通信回数を増やし てまで改良した意味がなくなってしまう

2

World 1の ^{Ccom 0:8} の平均補給回数の減少はあまりにも多くのエージェントがエネルギー切れに なった結果なので^,一概に比較できないと思われる

com

無通信モデル 平均補給回数 ^{3.260 3.260 3.260 3.260 3.260 3.260} 平均死亡数 ^{144.00 144.00 144.00 144.00 144.00 144.00} 扇動者モデル 平均補給回数 ^{44.979 42.576 40.420 38.687 36.181 38.703} 平均死亡数 ^{27.25 36.09 42.50 49.59 57.01 50.37} 提案モデル 平均補給回数 ^{52.806 66.064 79.810 66.064 102.525 89.070} 平均死亡数 ^{4.17 6.90 9.07 6.90 18.06 17.82}

C

com

= 0.6% 0.7% 0.8% 0.9% 1.0%

無通信モデル 平均補給回数 ^{3.260 3.260 3.260 3.260 3.260} 平均死亡数 ^{144.00 144.00 144.00 144.00 144.00} 扇動者モデル 平均補給回数 ^{31.863 33.119 25.977 26.811 20.242} 平均死亡数 ^{71.54 68.80 90.44 90.88 112.92} 提案モデル 平均補給回数 ^{108.146 83.913 68.964 43.008 25.225} 平均死亡数 ^{47.02 87.54 110.35 135.73 144.74} パラメータ：^{Hungry=20(%);M =20(%);Cstop=0:25(%);Hold=20(step)}

表 ^{4.1: World 1}での通信コストの比較による各モデルの性能の比較

0 20 40 60 80 100 120 140 160

0 0.2 0.4 0.6 0.8 1

Dead agent

C_com(%)

"model_1"

"model_2"

"model_3"

図 ^{4.1: World 1}での通信コストの比較による各モデルの性能の比較

消された結果だけではなく^,補給基地の混み具合に偏りが現れた場面で他の補給基地に移 動する場面が実際に見られたので^,情報のやり取りもうまく機能しているものと思われる^. 補給口の混雑の差というのは^,World1のようなエージェントが¹ヶ所に集まるような環 境では起こりにくいと考えられる^.その点では^"すいている補給口の情報^"というものは

World2の方が有効に活用できると思われる^.そして^,シミュレーションの結果で実際によ

い結果を出しているということは^,その情報をエージェントが¹ヶ所に集まらない⁽分散し た⁾場面でも局所通信系でうまく情報のやり取りを行うことができていることを示してい ると思われる^.

4.3

待機時のエネルギー消費率に関する比較

次に^,エージェントが待機時のときに消費するエネルギー量 ^Cstop のパラメータを変更 して比較する実験を行った^.

この ^Cstop の値の変動はエージェントにどんなものを想定するかに関わってくるパラ メータである^.このシミュレーションではエージェントのエネルギー補給時の行動のみを

com

無通信モデル 平均補給回数 ^{6.082 6.082 6.082 6.082 6.082 6.082} 平均死亡数 ^{144.99 144.99 144.99 144.99 144.99 144.99} 扇動者モデル 平均補給回数 ^{50.314 49.707 48.765 47.700 47.354 45.739} 平均死亡数 ^{8.11 10.21 13.53 17.21 18.43 23.36} 提案モデル 平均補給回数 ^{51.384 76.906 76.535 100.637 121.517 137.437} 平均死亡数 ^{2.61 3.83 3.49 5.28 8.28 13.77}

C

com

= 1.2% 1.4% 1.6% 1.8% 2.0%

無通信モデル 平均補給回数 ^{6.082 6.082 6.082 6.082 6.082} 平均死亡数 ^{144.99 144.99 144.99 144.99 144.99} 扇動者モデル 平均補給回数 ^{45.622 44.523 43.403 43.512 42.585} 平均死亡数 ^{23.62 27.91 32.66 30.77 34.37} 提案モデル 平均補給回数 ^{150.221 139.086 122.590 102.093 85.764} 平均死亡数 ^{31.76 50.85 70.05 85.96 96.69} パラメータ：^{Hungry=15(%);M =15(%);Cstop=0:25(%);Hold=20(step)}

表 ^{4.2: World 2}での通信コストの比較による各モデルの性能の比較

0 20 40 60 80 100 120 140 160

0 0.5 1 1.5 2

Dead agent

C_com(%)

"model_1"

"model_2"

"model_3"

図 ^{4.2: World 2}での通信コストの比較による各モデルの性能の比較

問題にしているが^,マルチエージェント系がある目的を達成するために作られるものと考 えると^,待機時も何らかの仕事を行っていると考えるのが妥当だろう^.そこで例えばエー ジェントは自動車で補給基地にはガソリンを補給に来ると想定すれば^,自動車の停止中の 仕事⁽というには弊害があるが⁾はすぐに発進できるようにアイドリング状態でいること ぐらいなので^,さして ^Cstop の数値は高くないものと思われる^.また^,エージェントが調査 用のロボットか何かで^,停止中も周囲を監視して難しい計算を行っていると想定すれば^,待 機時でも多くのエネルギーが消費されていると考えられる^.

今回の実験ではエネルギー補給問題のみに焦点を当てているので^,Cstop の値がエージェ ントが移動しているときのエネルギー消費量^(1step毎に保有エネルギー最大値の^0.5%)を 上回る場面は想定しないことにする^{3 .}

表^4.3,図^4.3は補給口がフィールドの中央に収集している状態でこの実験を行った結果 である^.この結果を見ると^{, Cstop} の値が増加することによって加速度的に結果が悪くなっ ていくのがわかる^.

3移動しているときよりも^,エネルギー補給の順番待ちの方がエネルギーのコストがかかるというのは不 自然であるため

stop

無通信モデル 平均補給回数 ^{11.989 3.079 2.678 3.823 4.987 6.363} 平均死亡数 ^{7.54 139.68 144.02 144.01 144.00 144.00} 扇動者モデル 平均補給回数 ^{50.157 50.750 48.818 24.654 3.137 1.739} 平均死亡数 ^{1.59 3.94 14.30 94.59 156.32 158.21} 提案モデル 平均補給回数 ^{90.424 89.910 86.717 79.107 31.781 8.474} 平均死亡数 ^{1.61 3.88 9.32 22.21 111.89 149.60} パラメータ：^{Hungry=20(%);M =20(%);Ccom=0:25(%);Hold=20(step)} 表 ^{4.3: World 1} での待機状態でのエネルギー消費率の比較による各モデルの性能の比較

0 20 40 60 80 100 120 140 160

0 0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45 0.5

Dead agent

C_stop(%)

"model_1"

"model_2"

"model_3"

図 ^{4.3: World 1} での待機状態でのエネルギー消費率の比較による各モデルの性能の比較

stop

無通信モデル 平均補給回数 ^{40.231 26.466 7.833 41.192 4.299 5.38} 平均死亡数 ^{13.71 84.91 142.99 148.52 147.04 146.14} 扇動者モデル 平均補給回数 ^{47.783 48.870 49.517 40.231 44.848 35.209} 平均死亡数 ^{3.51 6.08 7.92 15.85 34.45 76.22} 提案モデル 平均補給回数 ^{81.873 83.102 83.614 81.308 70.049 57.501} 平均死亡数 ^{0.60 0.86 2.10 7.02 24.10 48.47} パラメータ：^{Hungry=15(%);M =15(%);Ccom=0:25(%);Hold=20(step)} 表 ^{4.4: World 2} での待機状態でのエネルギー消費率の比較による各モデルの性能の比較

表^{4.4 ,}図^4.4 は同じ実験を補給口が分散した状態で行った結果である^.ここでも ^World

1 と比べればやや緩やかではあるが^,同じく ^Cstop が大きくなるにつれて死亡エージェン ト数の傾きが大きくなっている^.

以上の結果を見ると^,エージェントの移動時のエネルギー消費量と比べて^,待機時のエネ ルギー消費量が増えても^,さして影響が無いことが分かった^.

ただしこの結果よって^,通信コストさえそれなりに低く押えられるならば^,エージェント が待機状態のとき何も活動をしていないものであっても^,何か活動をしているものであっ ても^,どちらの場合でも本研究の提案モデルは扇動者モデルよりもよい働きを示すことが わかった^.

4.4

提案モデルにおける情報の信頼度に関する比較

マルチエージェント系は^,エージェントが相互作用しあっているので^,1体のエージェン トにしてみれば^,さまざまなエージェントが影響しあっているその環境は動的なものある^. そのような状況で情報を広めるにあたって^,その情報をどれだけ保持しているかというの は重要な話である^.

この実験で言えば^,どの補給口がすいているかという事象が動的なものであり^, その情 報は時間が経つにつれて信頼できなくなる^.当然^,そのような情報を長時間保持しているの は無駄であると思われる^.しかし^,この研究の目的が^,「集団全体に不利益をもたらすある 臨界状態⁽この実験で言えば補給基地の混雑⁾を回避するのに訳に立つ情報を^"前もって^"

0 20 40 60 80 100 120 140 160

0 0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45 0.5

Dead agent

C_stop(%)

"model_1"

"model_2"

"model_3"

図 ^{4.4: World 2} での待機状態でのエネルギー消費率の比較による各モデルの性能の比較 広めておくことで局所通信系であっても情報空間上の位置関係によって生まれる情報の格 差を取り消し^,うまく戦略変更を促す」というものであるため^,すぐに破棄しすぎるとうま く情報を利用することができなくなってしまう^.

そこで^,ここでは情報をどれだけ保持するか^,その期間を決めるパラメータ^Holdを変更 し^,比較する実験を行う^.

エージェントはすいている補給口を見付けたときに^,その情報を ^Hold の値と同じ^step 保持し^,通信で周囲に広めることとなる^.1stepごとにその情報を保持する期限が減ってい き^,その値がそのままその情報の信頼度となる^.エージェントが情報を発信するときは^,こ の信頼度も同時に発信され^,何^step前の情報かが受け手にも分かるようになる^.エージェ ントがある情報を保持しているときに別のエージェントから情報が送られて来たときは^, より新しい方⁽信頼度の高い方⁾を覚えることにする^.

このパラメータは本研究で提案する提案モデルにのみ存在するパラメータなので^,他の モデルとの比較は行わない^.ただし^{, Hold=0}はすいた場所の情報を持たないということ なので^,扇動者モデルと同義となる^.

表 ^{4.5 ,}表 ^4.6は^,それぞれ補給基地が中央に集中的に存在する環境と^,補給基地を⁴ヶ