日本ソフトウェア科学会第 34 回大会 (2017 年度) 講演論文集

マルチエージェント継続協調巡回における分業の創発と変化に対する柔軟性の評価
杉山 歩未

Sea Vourchteang

早野 真史

菅原 俊治

近年の情報通信やセンサ技術の発達により，動的かつ大量に発生する情報やタスクを短時間で処理し，効率的な作業を実現することが望まれている．このような問題では単一のロボットや計算機では性能に限界があり，それらを複数組み合わせたシステムによって効率を向上させることが期待される．一般に，複数者での作業では分業を適切に行う
ことが効率化のために有効であるが，複雑かつ動的に変化する環境では適切な分担を事前にエージェントに割り当てることは困難である．そこで，エージェントが自律的にタスクの分担を決めることが期待されるが，複数の自律エー
ジェントがシステム全体の効率と通信コストのトレードオフを考慮しながら効率的な分業体制を創発するためのメカ
ニズムは明らかになっていない点が多い．本研究では，継続協調巡回問題を例に我々が提案した単純な交渉と自律的学習を組み合わせることで分業の創発を促進する手法に対し，分業創発の要因についての分析と本手法が異なる種類の環境の変化にどのように対応するかを調査し，自律エージェント群が変化に柔軟で持続的なシステムを構築するためのメカニズムについて考察を行う．結果から，本手法が複数の役割分担を自然に発生させ，それらの役割分担や異なる粒度の学習が混在することが効率的かつ柔軟な分業体制を創発させることを示唆した．

operative Patrolling Problem, CCPP) を定義し，複1 はじめに数の自律エージェントが効率的な分業体制を創発する

動的に発生するタスクや環境の変化に柔軟に対応

メカニズムと，そのようなボトムアップに作られた体

可能な自律エージェントによるシステムが多くの分野

制の，変化に対する柔軟性を評価する． [3] は近年ので期待されている．近年のロボットやセンサなどのデマルチロボットによる巡回アルゴリズムの比較をおバイスやネットワークの発達により，動的に発生する

こなっており，複数者による巡回問題に求められる拡多数のタスクやデータを，要求される時間内で処理す

張性や変化への柔軟性，通信の制約などの特徴から，るシステムが求められている．このような要求を解決

複数エージェント巡回問題で得られた知見が巡回問題するためには，ロボットやプログラムを制御する多数だけでなく，マルチロボットシステム全体で有効活用のエージェントが自律的に対応することが重要となできると主張している．既存の巡回問題に関連する研る．しかし，多数の自律エージェントによる作業にお究の多くは，予め決められた各ノードへの訪問要求

いて，エージェントが自己の効率の最大化を目指しなを満たしつつ，各ノードへの訪問間隔を最小化する

がらもエージェント間でも競合を回避しながらシステことを目的としたものが多かった．しかし，現実の多ム全体の効率を高い状態で持続させるメカニズムは，くの問題では，処理・検出すべきイベントは確率的にエージェント間の相互作用の複雑さから未だ明らかと発生し，その発生確率も動的に変化する場合も多い．

なっていない．

十分な時間があれば，既存のアルゴリズムによって最本研究では，継続協調巡回問題 (Continuous Co-

適なルートを再計算することで対応可能だが，持続的なシステムのためにはそのような動的な変化にもAyumi Sugiyama
Vourchteang Sea
MasashiHayanoToshiharu Sugawara, 早稲田大学基幹理工学研究科情報理工・情報通信専攻, Dept. of Information and Computer Science, Waseda University.

システムを停止させずに，自律的に対応することが望まれる．そこで，CCPP では既存の巡回問題の設定を拡張し，継続的な活動のために充電やサーバー

のメンテナンス等を考慮してエージェントが定期的と巡回問題と共通する要素が多くあり，複数の自律的に休止する必要のあるモデルを提案している．また，な行動主体による分業についての研究が行われている

現実のように通信範囲や通信間隔に制限を設け，その[6] [13] [5] [7]．しかし，これらの研究では各エサに割りような制約の元で自律的な複数のエージェントが効率

当てるエージェントの最適な比率が与えられており，的な巡回を継続するためのメカニズムを考察する．

どのようにそれぞれのエージェントが割り当てられる

本稿では，分業の創発を促進する我々の提案手法

かということに主眼を置いていた．

[14] [11] [10] [12] に対し，環境の急激な変化に対する追巡回問題においては分業を実現するために大きく分

従性を評価する追加的な実験を行い複数の自律エー

けて 2 つのアプローチがある．1 つは環境をいくつか

ジェントがそのような変化に効率よく対応するためののサブエリアに分割し，各サブエリアを一体もしくは要素を分析する． [12] では，途中でエージェントの一数体のエージェントに割り当てる領域分割手法 [1] [4]

部が停止するという変化に対する追従性の評価を行っであり，もう一方は環境を分割せずに，効率的な巡回た．結果から，提案手法によってエージェント間で主のための目標や経路を学習する手法 [8] [2] である．領域に担当する場所や巡回の方法などにおいて役割分担を分割によるアプローチは比較的簡単に競合の発生を防創発し，あらかじめ分業の割り当てを与えられていな

ぐことが可能であり，有用なアプローチである．しかいにも関わらず効率的な分業体制を構築し，その役割しながら，このような領域分割のアプローチではサブを柔軟に変化させることで変化に柔軟なシステムをエリアの分け方や各領域に割り当てる最適なエージェ

維持できることが分かった．しかし，エージェントのントの比率があらかじめ与えられており，領域が連続

停止はシステムの内部的な変化であったため，環境のしているゆえに環境の変化時に収束が遅く柔軟性に

イベント発生確率の急激な変化などの外部的な変化

欠けるといった課題がある．そこで我々は後者のアプに対しての考察は行われていなかった．既存の多くのローチに注目し， [14] では清掃問題を題材にいくつか

巡回問題に関する研究においても，このような二面的の目標決定戦略から最適な戦略を学習する Adaptiveな変化に対してシステムの継続性・柔軟性の点で深く

meta target decision strategy(AMTDS) を提案し，考察されたものは見受けられていない．本研究では，[11] ではエージェント間の交渉がなくとも環境のイベ

イベント発生確率が急激に変化するという追加的なント発生確率を学習することで間接的に他者のふる実験の結果から，これまでに得られていたエージェン

まいを考慮する AMTDS with learning of dirt accu-

トの停止という変化に対応するメカニズムとは別のmulation probability(AMTDS/LD) を提案した．まメカニズムによって，環境の急激な変化に適応していた， [10] では清掃問題から巡回問題にモデルを一般ることが明らかとなった．そして，本実験により得ら化して継続協調巡回問題として再定義し，責任をもれた結果とこれまでに得られていた知見との統合的つ範囲という概念をエージェントに導入し，非常に簡な分析を行い，異なる種類の変化にも柔軟に対応する

単な交渉手法によって互いのイベント発生確率に関ためのメカニズムについての考察を行った．

する情報を交換することで，分業創発をボトムアップに促進させる手法 (AMTDS with learning of event

2 関連研究probabilities and enhancing divisional cooperation,

複雑な問題を複数人で効率的に行うために分業を行

AMTDS/EDC) を提案した．

うことは，古くからその有用性が認識されている．産

しかし，これらの研究では効率性と通信時のコスト

業革命時に Adam Smith は分業について言及し，分にのみ着目しており， [3] が主張した巡回問題におけ業の利点として (1) 特定の作業への特化による熟練度

る課題である変化への柔軟性については考慮されていの向上 (2) 作業の変更に伴うコストの削減 (3) 各作業なかった．そこで我々は [12] でエージェントの一部がの効率化のための道具開発の促進の 3 点を述べてい停止するという内部的な変化に対して我々の提案手法

る [9]．また，採餌問題もエサをイベントととらえるがどのように対応できるかを調査し，提案手法によっ

て発生した役割をエージェントが自律的に変化させる

CCPP における巡回の目標は，環境内に残存することで，変化に対して効率の低下を防ぐ柔軟なシステ

イベント量を継続的になるべく小さく維持することムとなることを示した．しかし， [12] は創発されたである．そのため，本研究における巡回効率の評価指

役割分担が変化にどのように対応するかというメカ

標を時刻 ts から te 間の Dts ,te として以下のようにニズムの初期的な実験であり，もう一つの大きな変化定義するである外部的な環境の変化に対しての考察はされていなかった．そこで本研究では，追加的な実験として環境のイベント発生確率が急激に変化するという外部的な変化への対応を調査する．手法自体は，異なる
種類の変化に対する影響の違いに主眼をおくため [12]と同一のものを用いるが，結果から，異なる種類の変化に対しては異なるメカニズムがはたらいて変化への柔軟性を維持していることが分かった．本稿ではその違いを分析し，役割分担だけでなく異なる粒度の学習が共存していることで多様な変化への柔軟性をシ
ステムが有することを示す．

Lt (v),(2)v∈V t=ts +1

ここで，ts < te であり，s はエージェントが選択した目標決定戦略である．Dts ,te (s) の値が小さいほど作業効率が良いとする．また，もう一つの評価指標として Uts ,te (s) を以下のように定義する

Uts ,te (s) =maxv∈V,ts <t≤teLt (v).

(3)

Uts ,te (s) は環境内に蓄積した最大のイベント数を表す．実問題ではある一定以上の成果を保っているのであれば稼働台数を減らしたいなどのエネルギー消費を考慮したい場合も多くある．そこで，本モデルでは価も提案している．

3. 1 環境エージェントが巡回を行う環境を G = (V, E) ⊂ R2とし，G はあらかじめエージェントに与えられていると仮定する．マップ生成も重要な課題の一つであるが，これに関しては多くの有用な研究がなされており，それらを活用することを想定している．V = {v1 , . . . vm }をノードの集合とし，ノード v は座標 xv ，yv をもつ．

E はエッジの集合であり，エージェントはエッジで接続された隣接ノードへ移動が可能である．ただし，障害物 Ro ⊂ R がノード上に存在する場合，そのノー2ドへは移動できない．また，すべてのノードはイベ
ントの発生確率 p(v) (0 ≤ p(v) ≤ 1) をもち，高い値の p(v) ほど頻繁な訪問を要求する．時刻 t にノードv において，検出されずに残存しているイベントの数を Lt (v) と表す．Lt (v) は p(v) に基づいて毎 tick ご

3. 2 エージェント
エージェントの集合を A = {1, . . . , n} と定義する．
時刻 t におけるエージェント i の位置を vti ∈ V と表
現する．本研究では継続的な巡回活動を考慮するため，エージェントは有限容量のバッテリをもち，定期i
的に充電基地 vbaseに戻り充電する必要がある．詳しい制御方法は [14] を参照されたい．また，エージェン
トはノード v が最後に訪問され，イベントが処理された時刻 tvvisit を用いて，現在の時刻 t までの経過時
刻 Iti (v) を以下のように計算する

Iti (v) = t − tvvisit .

(4)

ここで，本稿ではエージェントは赤外線素子や GPS
機能を利用することで，自分と他者の位置を把握できると仮定した．実問題においては位置情報を完全に取得できない場合や位置情報にノイズが発生する場合は考えられるが，今回は分業の創発と変化への追従(1)

エージェントがノード v を訪問したとき，残存していたイベントは処理され Lt (v) = 0 となる．我々は離散時間 tick を導入し，イベントの発生やエージェン
トの移動は各 tick 内で行われる．

te∑ ∑その成果の指標となる最大蓄積イベント数による評

3 モデルとに以下の式で確率的に更新する
Lt−1 (v) + 1 (イベント発生時)
Lt (v) ←Lt−1 (v) (その他).

Dts ,te (s) =性に焦点を絞るため，このような仮定をおいた．この仮定により，本稿では経過時刻 Iti (v) は各エージェン
トにおいて他者が訪問した時刻を考慮した値となり，エージェント間で統一の値をもつ．しかし，Iti (v) は各エージェントが独立にもつ値のため，他者の位置が把握できない場合にも自然に拡張可能である．

セプトを簡単に述べる．

i

エージェントは各ノード v の重要度 p (v) を独立に学習・記録し，その集合 Pvi = {(v, p(v))|v ∈ V } をも
つ．学習の詳細については 4 節にて後述する．重要度は数値で表現でき，環境において設定されているイ

ランダム法 i は環境全体からランダムに目標を選択する．
貪欲法 i は推定優先度 ELit (v) の上位 Ng ノード
から目標を選択する．

ベントの発生確率 p(v) と異なり，各エージェントが訪問間隔優先法 i は環境全体から最後に訪問され独立にもつ，あるノードがどれだけ重要かという経験てからの間隔 Iti (v) の上位 Ni ノードから目標をに基づく知識を表す．また，エージェント i は学習し

決定する．

i

た各ノードの重要度 p (v) を用いて，時刻 t における戦略型目標決定法 i は近隣の巡回を優先するかのノード v の推定優先度 ELit (v) を次の式で定義する

閾値 EB を学習し，近隣の推定イベント蓄積数

ELit (v) = pi (v) × Iti (v).

(5)

が EB 以下になるまで近隣を優先して巡回する．

エージェントは戦略によっては推定優先度を基に訪問[11] では，エージェントが学習した各ノードの知

すべきノードを決定する．

識も利用して，これらの戦略から適切な戦略を学本モデルでは一般的な通信の制約を考慮した通信制

習 す る 手 法 と し て AMTDS/LD を 提 案 し て い る ．

御を想定した．エージェントは通信範囲 dcom (> 0) を

AMTDS/LD においてエージェント i は任意の戦略

有し，エージェント i がエージェント j と通信ができの集合 S = {s1 , . . . , sn } から最適と思われる戦略 s∗

るのはエージェント間のユークリッド距離 m(v i , v j )を学習しながら巡回を行う．各エージェントは p(v)を用いて，時刻 t において m(vti , vtj ) < dcom の時とす

を未知とし pi (v) の学習を行う．後述する本提案手法

る．また，過度な通信によるコストの増加を防ぐため，の AMTDS/EDC においても，同様の戦略学習を行i,ji は j と最後に通信をおこなった時刻 Tlast
を保持し，
i,j
i,j
i,j
最低通信間隔 Tlimit (> 0) を定義し，Tlimit ≥ t−Tlast

うが，AMTDS/LD では計算コストを考慮してエーのときは通信を行わないと仮定した．

による学習と間接的に環境から他者のふるまいを学

ジェント間の交渉は行っておらず，単一エージェント

習するのみとなっている．経路生成手法については今

4 提案手法回の主目的と外れるため [14] を参照されたい．

本研究とも密接に関わるため，ここで我々の提案
した自律的な学習と 1 対 1 間の交渉というミクロな4. 2 重要度の学習とエージェント間交渉

行動戦略からシステム全体のマクロな分業創発を促交渉においては公平性のための交渉と改善のため進させる AMTDS/EDC 手法 [12] について説明する．

の交渉を行う．公平性のための交渉では，責任をもつ本手法では，エージェントは複数の行動戦略から適切

タスク量の多いエージェントが少ないエージェントにだと思われる戦略を学習しながらも，その戦略の決

いくつかのノードの責任を委託するよう打診し，打診i

定に影響する環境に対する知識を表す p (v) も学習すi

されたエージェントは自分の方が少ないコストでそのる．さらに，経験から学習した p (v) に関する知識をノードを巡回できると考えられるのであれば責任の簡単な交渉手法によって他者と交換し，責任をもつ範一部を引き受ける．この仕事量の分配によって，両方囲の改善を試みる．

のエージェントが一部のノードへの集中と広範囲への探索を行えるようになる．改善のための交渉では，

4. 1 目標決定戦略

責任量の同等なエージェント同士が，互いにより少な

エージェントの巡回は (1) 戦略 s に従い目標ノード

いコストで巡回できるノードがあればその責任を交

vtar を決定．(2) vtar までの経路を生成．(3) 生成し換する．2 つの交渉手法において，エージェントは責た経路を通り vtar に到着．という流れを繰り返すこ

任の委譲を打診されたノードが，自分の方が少ないコとで行う．以下でエージェントがとりうる戦略のコンストで巡回できると思われる場合のみその打診を受諾する．たとえば，エージェント i の責任量が他者にiは Vselfから計算される 2 つの値のみを用いる．1 つ

比べて多い場合でも，他にその作業をより小さいコスは責任をもつノードの重要度の総和 pisum (≥ 0) であトで行えるエージェントがいない場合，交渉は成立しり，以下のように計算する∑ ipisum =
pt (v).

ない．経済学における比較優位の法則のように，ある
エージェントの責任量が大きくなるほど他のエージェ
ントがそのエージェントの仕事を代わることによるインセンティブは増加する．これにより，自分の現在の状況を考慮しつつ，単に 1 対 1 間で責任を分ける

iv∈Vself

重要度 pit (v) が高いノードは頻繁な訪問を求められる
ので，pisum は i が責任をもつ作業量を表現している．

2 つめは作業の重心 C i = (xic , yci ) であり，pi (v) の重に情報を交換することで，互いに多くのイベントのみを考慮して以下のように設定する∑ pi (v)∑ pi (v)
i
x
,
and
y
=
yv . (7)
xic =
v
c
pisum
pisum
i
i

回収を目指せるというインセンティブをもつ．また，

ここで，v = (xv , yv ) である．ノード vp からノード提案する交渉手法は他のオークションベースなどのvq への最短経路長を d(vp , vq ) とすると，d(vci , v) <交渉プロトコルと異なり，交渉はあくまで責任の委託

d(vcj , v) のとき，ノード v はエージェント i の作業のであり，あるノードをどちらのエージェントがどれく

中心にエージェント j よりも近く，訪問するために払らい担当するかは交渉によって完全には決められず，うコストが小さいことをあらわす．

各エージェントが自分の知識に基づき決定することに

4. 2. 2 公平性のための交渉注意されたい．

i
エージェントは他者と交渉を行い，各々の Vselfののではなくシステムの全体にとって利益となるよう

v∈Vselfv∈Vself

4. 2. 1 重要度の学習と責任をもつ範囲

要素の改善を試みる．この際，通信コストを考慮し，エージェント i はノード v に訪れたとき，Iti (v) をpisum と C i のみの比較によって交換する情報を決定i

用いて p (v) を次式で更新する．
1(1 − β)pi (v) + β i(Lt (v) > 0 のとき),
i
I
t (v)
p (v) ←
(1 − β)pi (v) (L (v) = 0 のとき),する．公平性のための交渉では，自分より少ない責任(6)行えるようにすることが狙いである．式 (8) の条件をt

ここで，α (0 < β ≤ 1) は学習率である．
i
また，エージェント i が責任をもつ範囲 Vselfをもつ他者に自分にとって重要でないタスクを任せる
ことで，自分は重要な作業に集中し相手は広く探索を満たす場合，担っている責任に差があると判断し公平(⊂ V )

を導入する．責任をもつとは，戦略 s による目標ノー性のための交渉を行う

1 + Tc < pisum /pjsum .

(8)i
でなく，Vselfに限定すTc (0 < Tc ≪ 1) は責任の差を判定する閾値であ

ることで巡回対象の選択と集中を行うことをあらわ

i,jる．この時，i は pi (v) の降順に集合 Vself= {v ∈

す．ただし，訪問間隔優先法とランダム法は環境内で

i,j
i
Vself
| d(C i , v) > d(C j , v)} を計算する．i は Vselfの見逃されているノードの探索が目的であるため，これpi (v) の小さい値から，eg (0 ≤ eg ) 個のノードを選択

iらの戦略では vtar
を V から選択する．エージェント

し，その pi (v) の値を j に次式によって渡す．

i
ド vtarの候補を環境全体の Viii は充電基地に戻った際，Vselfを更新する．Vselfのpj (v)←

pj (v) + pi (v) × δ

(9)

i
i
初期値は環境全体とし，Vself= V とする．Vselfのサpi (v)←pi (v) × δ.

(10)

i
i
イズを Nselfとし，この初期値も Nself= |V | となる．

δ(0 < δ < 1) は情報を受け渡す割合を表す．式 (9),充電基地に戻った際，i は P の要素を p (v) の降順(10) に示す pi (v) 値の受け渡しは，i が部分的に自分iiに並び替え，上位 Nselfのノードを Vself
として再定の責任を j に委託することを表す．eg は交渉時に情

i

i

i

義する．p (v) が同値のノードが複数あった場合はラ報を受け渡されるノードの数であり，pisum と pjsum のンダムに決定される．

比率から以下のように決定する．
⌋)
(
⌊ i
p
i
i
×
γ
, (11)
eg = min Nself− 1, Ngmax
, sum
pjsum

本研究では交渉にかかるコスト抑制のため，交渉に環境変化前表1

実験パラメータ

目標選択戦略

パラメータ

値

貪欲法

Ng

5

訪問間隔優先法

Ni

5

AMTDS/LD

α

0.1

β

0.05

ε

0.05

Ngmax

100

環境変化後

図1

AMTDS/EDC

実験環境

Ncmax

10

i
i
i
) は急激な変動≤ Nself
ここで，Ngmax(0 < Ngmax

Tc

0.05

を防ぐための上限であり，γ は受け渡すノード数を調γ10

整するパラメータである．情報の受け渡しが終わった

δ

0.5

dcom

5

Tlimit10800

i
i
後，エージェント i と j は Vselfのサイズ Nself
を次

通信の制約

式で更新する
i
Nself

←

i
Nself
− eg

(12)

j
Nself

←

j
min(|V |, Nself+ eg ).

(13)

5 評価実験
4. 3 改善のための交渉

5. 1 実験設定

もう 1 つの交渉は，責任をもつ作業量が均衡した提案手法により創発された分業と環境の変化へのときに，責任をもつノードを交換することで互いの責追従性の関係性を調査するためにシミュレーション

任を持つノードの改善を試みる交渉である．この交渉による評価実験を行った．ここでは， [12] で示された

では，お互いに相手の方がより少ないコストでできる

エージェントの停止という変化への対応と比較して，作業を交換することで，大きな変動を与えずに互いの異なる種類の変化，具体的には環境のイベント発生確

巡回コストを低下させ，効率を向上させることが狙い

率の急激な変化に対応するための要素を分析する．本である．式 (14) の条件を満たす場合に以下の改善の研究でエージェントが巡回を行う環境は，各ノードのための交渉を行う．

イベント発生確率 pi (v) に偏りがあり，障害物によっ

1 − Tc < pisum /pjsum < 1 + Tc .

(14)ていくつかの部屋 Room N (N = 0, . . . , 5) に分かれの大きい p (v) の大きい値から eg 個のノーている 101 × 101 の大きさのグリッド構造とした．そドの p (v) を式 (9), (10) に従い j に渡す．eg は次式の環境を図 1 に示す．各ノードの p(v) の値は図 1 にで決定する

示す色によって赤色部：10−3 ，オレンジ色部：10−4 ，i,ji は Vself
i

i

(

)

i
i
eg = min Nself− 1, Ncmax,(15)

その他：10−6 とし，障害物 Ro は黒色で表している．

i
ここで，Ncmax(> 0) は上限である．情報の受け渡し

また，本研究の目的のため，環境のイベント発生確iが終わった後，エージェントは Nself

を式 (12) に従率を途中で大きく変化させる．100 万ステップ時に図i
い更新する．交換する p (v) の値を考慮し，Ncmaxは1 に示す環境変化後のように，各部屋のイベント発生i
Ngmaxと比較して小さな値とする．式 (14) の条件を確率の特徴を時計回りに 1 部屋ずつずらし，200 万ス

満たすとき，上記の過程は i と j で双方向に発生する．

テップ時に元の状態に戻した． [12] では，イベント発i

生確率の変化の代わりに 100 万ステップ時にランダ
ムに 10 のエージェントを停止させ，200 万ステップ時に停止したエージェントを復帰させている．
エージェント数は 20 で，全エージェントの充電基

4500000AMTDS/LD

Cumulative existence duration of events D(s)AMTDS/EDC (提案手法)

AMTDS/EDC(proposed method)

5000000
3500000

AMTDS/LD

3000000
4000000
2500000

3000000
2000000

2000000
1500000

1000000
1000000
50000000

図20500000 1000000 1500000 2000000 2500000 3000000

05000001000000

1500000
Time (ticks)

2000000

2500000

Cumulative existence duration of events D(s)4500000

6000000
4000000

4000000

3500000

AMTDS/EDC (提案手法)
AMTDS/EDC(proposed method）

AMTDS/LD

3500000

3000000
3000000

2500000
2500000

2000000
2000000
1500000
1500000
1000000
1000000
5000005000000003000000

環境変化時の巡回効率 D(s) の推移

AMTDS/LD

4500000

4000000

図350000005000001000000

1000000

1500000

1500000
Time (ticks)

2000000

2000000

2500000

3000000

2500000

3000000

エージェント停止時の巡回効率 D(s) の推移
18

地は vbase = (0, 0) とした．全てのエージェントは充

ランダム法

16

貪欲法

訪問間隔優先法戦略型

14

電基地からスタートし，充電のために定期的に戻る

1210必要がある．エージェントのバッテリの設定は容量

86を 900，容量 0 からの満充電に 2700tick を要し，隣42

接ノードへの移動は 1 消費すると設定した．よって，

00

エージェントの巡回サイクルは最大 3600tick となり，5000001000000

1500000

2000000

2500000

3000000

評価指標の Dts ,te (s) も 3600tick ごとに集計した．全
てのエージェントは戦略として AMTDS/LD か提案

図4

イベント発生確率変化時の選択戦略の推移

手法の AMTDS/EDC のいずれかを用いる．ここで，(AMTDS/LD)

AMTDS/LD はエージェント間交渉は行わないが環18

境の学習のみによって間接的に他者のふるまいを学

ランダム法

16

貪欲法

訪問間隔優先法

戦略型

14

習するものであり，単一エージェントの学習フレーム

12
10

ワークに近い手法である．AMTDS/LD でもわずか8ながら主に訪問する場所の偏り，いわゆる分業が発生

6することが確認されているがその程度は小さいもの

2

4

0
0

であった．また，モデルおよび提案手法で述べたパラ

5000001000000

1500000

2000000

2500000

3000000

メータは表 1 のように設定した．本研究では [12] で得られたエージェントの停止に対する結果と，今回

図5

イベント発生確率変化時の選択戦略の推移

行う環境の急激な変化に対する結果を比較するため，
表 1 のパラメータは [12] で用いたものと同様の値を用いた．

(AMTDS/EDC)
18

ランダム法

16

貪欲法

訪問間隔優先法

戦略型

14
12

5. 2 結果と考察
環境変化時およびエージェント停止時の評価指標 D(s) の推移を図 2, 3 に示す．両方の変化に対して，提案手法である AMTDS/EDC は効率の悪化を

10
8
6
4
2
0
0

5000001000000

1500000

2000000

2500000

3000000

AMTDS/LD に比べて防いでおり，D(s) も早く低下させていることが見て取れる．詳細は [12] にて述
べているが，エージェント停止時に提案手法である

AMTDS/EDC が大きく効率低下を防いでいるのは，

図6

エージェント停止時の選択戦略の推移(AMTDS/LD)

直後に訪問間隔優先法が急激に増え，その後貪欲法と
18
ランダム法

16

貪欲法

訪問間隔優先法

戦略型

戦略型が増加している．今回比較した 2 つの変化に14

おいて最も異なる点は，エージェント停止時は残され12
10たエージェントにとって追加分のイベント発生領域が86増えるが，エージェントの台数は減っており考慮する

4

他者の数は減ったが，環境変化時にはこれまでに学習

2005000001000000

1500000

2000000

2500000

3000000

した各ノードのイベント発生確率の増減の修正と，新たに発生したイベントに対する他者のふるまいの変化

図7

エージェント停止時の選択戦略の推移(AMTDS/EDC)の両方に追従する必要がある点である．つまり，環境変化時の方が新たに学習し直す要素が多く，学習に時間がかかると考えられる．本実験では， [12] では見ら提案手法によって主に担当する範囲に大きな偏りが発れなかった戦略の素早い変更が AMTDS/LD および生するのと同時に何台かのエージェントは似たよう

AMTDS/EDC で起きている．これは，環境変化時な場所を巡回するいわゆるチームのような働きが創には各ノードの重要度の再学習に時間がかかるため，発されたこと，責任の量はほぼ同等ながら責任を持戦略という大きな方針が先に学習されることで，知識つ範囲にも偏りが生じ，一部のエージェントは特定のの活用を行う貪欲法や戦略型から，環境の探索を行う

範囲に集中してその場所を精度良く巡回するスペシャ

訪問間隔優先法への変更が促され，これにより変化に

リストのような役割を，別のエージェントは広範囲を対応したと考えられる．それに加え，AMTDS/EDC

巡回するゼネラリストのような役割を担うようになっでは訪問間隔優先法にて探索優位になった状態から，たことが要因である．これらの役割は提案手法の交渉[12] で述べたようにそれぞれが探索した新しい環境のによって決定的に定まるのではなく，エージェントが知識をより低コストで巡回できるエージェントに委

自律的に調整を行うことで変化時には役割を柔軟に変託しながら役割を柔軟に変化させることで，スペシャ

更させ，素早く変化に対応することが可能となった．

リストによる各ノードに対するイベント発生確率のしかし，本実験では [12] で得られた役割分担だけ学習が促進され，近領域を優先する―ある種の連続でなく，素早い戦略の転換によって変化に対応した領域の領域分割のような巡回をするー AMTDS/LD

ことがみてとれた．環境変化時の AMTDS/LD およ

よりも早く変化に対応できたと考えられる．つまり，び AMTDS/EDC によって各エージェントが選択し環境変化に対してはエージェントの停止時と異なり，ていた目標決定戦略を図 5,4 に，エージェント停止

大きな方針である戦略学習と各ノードに対するイベ

時の AMTDS/LD および AMTDS/EDC によって各ント発生確率の学習という小さな粒度の学習という 2エージェントが選択していた目標決定戦略を図 7,6 に種類の粒度の異なる学習が存在することで，変化に柔示す． [12] では AMTDS/LD では近領域を優先する

軟に対応しているということが分かった．

戦略型が優勢であったが AMTDS/EDC では各エー[12] において多様な役割が存在し，それを交渉にジェントが連続しないノードに対しても責任範囲を決よって決定するのではなく自律的に決めることで柔軟

定でき，その知識を利用することで近領域以外にも柔な役割の変更を可能とし，変化への柔軟性を向上して軟に巡回する貪欲法で高い効率をだせていた．しかいるという知見を得ていたが，本研究において異なる

し，図 6 と図 7 をみて分かるように，両手法におい環境の変化に対する実験を追加的に行いその差異をてエージェント停止時にも貪欲法か戦略型をほぼ全て比較することで，戦略学習という大きな行動決定のたのエージェントが選んでいた．ところが，図 4 と図 5めの方針の学習と，イベント発生確率の学習とそのをみると，AMTDS/LD では戦略型が優勢なことは再交渉という各戦略を遂行する際に参考とする情報変わらないが，環境変化時には両手法において変化のの学習という小さな粒度の学習をエージェントが行っ

ていることで，変化やエージェントによる変化の検知に応じて役割や方針を自律的かつ柔軟に変更することでシステムの効率性を維持しながら柔軟性をも向上させることを示唆している．

6 結論
本研究では，高度な自律性と持続可能性・複数エー
ジェントによる協調が求められる問題の 1 つとして

CCPP を定義した．既存研究における内部的な変化と異なる，外部的な変化を評価する追加的な実験を行い，異なる種類の環境変化への追従性を調査してその要因を分析することで，創発された分業がシステムの柔軟性向上に与える要因を考察した．具体的には，提案手法はエージェントの停止という変化にはボトムアップに発生した多様な役割分担を柔軟に変化させることで効率向上と変化への対応性の向上を実現するのに加え，環境のイベント発生確率の急激な変化という外部的な変化には，戦略の学習と戦略の内部で参照する情報の学習という異なる粒度の学習が混在することで，変化に対し迅速な対応をしつつ高い効率を発揮することを示した．提案手法ではこれらの異なる役
割分担や異なる粒度の学習をエージェントが自律的に行うことで，通常時の効率を損なうことなく，それぞれの変化に対応した役割や方針の変化を自律的に行い変化に柔軟なシステムを持続することを示唆した．
今後は， [3] が主張したように，この研究において得られた知見や手法を一般的なマルチロボット・マル
チエージェントシステムにおいて適用させ，一般性の高い手法の提案を試みる．また，結果から多様性を担保する自律的な決定が低コストの交渉ながらも効率と変化への柔軟性の向上をさせることが示唆されたが，これらの多様性とシステムの性能についてのより一
般的な理論の発見が求められる．
謝辞 本研究は JSPS 特別研究員奨励費 JP16J11980の助成を受けたものである。

参 考 文 献[ 1 ] Ahmadi, M. and Stone, P.: A Multi-Robot System for Continuous Area Sweeping Tasks, Proceedings of the 2006 IEEE International Conference on
Robotics and Automation, 2006, pp. 1724 – 1729.

[ 2 ] Cheng, K. and Dasgupta, P.:
Dynamic
Area Coverage using Faulty Multi-Agent Swarms,
Intelligent Agent Technology, 2007. IAT ’07.
IEEE/WIC/ACM International Conference on,
nov. 2007, pp. 17 –23.
[ 3 ] David, P. and Rui, R.: A Survey on Multi-robot
Patrolling Algorithms, Technological Innovation for
Sustainability: Second IFIP WG 5.5/SOCOLNET
Doctoral Conference on Computing, Electrical andIndustrial Systems, DoCEIS 2011, Costa de Caparica, Portugal, February 21-23, 2011. Proceedings, Camarinha-Matos, L. M.(ed.), Springer Berlin
Heidelberg, 2011, pp. 139–146.
[ 4 ] Elor, Y. and Bruckstein, A. M.: Multi-a(ge)nt
Graph Patrolling and Partitioning, Proceedingsof the 2009 IEEE/WIC/ACM International Joint
Conference on Web Intelligence and Intelligent
Agent Technologies, 2009, pp. 52–57.
[ 5 ] Ikemoto, Y., Miura, T., and Asama, H.: Adaptive Division of Labor Control for Robot Group,
Proceedings of the 2009 IEEE/RSJ International
Conference on Intelligent Robots and Systems, Oct2009, pp. 2409–2414.
[ 6 ] Jones, C. and Mataric, M. J.: Adaptive divisionof labor in large-scale minimalist multi-robot systems, Proceedings of the 2003 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2003), Vol. 2, Oct 2003, pp. 1969–1974
vol.2.
[ 7 ] Lee, W. and Kim, D.: Adaptive Division of Labor in Multi-Robot System with Minimum Task
Switching, Proceedings of the Fourteenth International Conference on the Synthesis and Simulationof Living Systems (ALIFE 14), Jul 2014, pp. 750–
756.
[ 8 ] Sampaio, P., Ramalho, G., and Tedesco, P.: The
Gravitational Strategy for the Timed Patrolling,
Tools with Artificial Intelligence (ICTAI), 2010
22nd IEEE International Conference on, 2010,
pp. 113–120.
[ 9 ] Smith, A.: An Inquiry into the Nature andCauses of the Wealth of Nations, History of Economic Thought Books, No. smith1776, McMaster
University Archive for the History of Economic
Thought, 1776.
[10] Sugiyama, A., Sea, V., and Sugawara, T.: Effective Task Allocation by Enhancing Divisional
Cooperation in Multi-Agent Continuous Patrolling
Tasks, 2016 IEEE 28th International Conferenceon Tools with Artificial Intelligence (ICTAI), Nov
2016, pp. 33–40.
[11] Sugiyama, A. and Sugawara, T.: Meta-strategy
for Cooperative Tasks with Learning of Environments in Multi-agent Continuous Tasks, Proceedingsof the 30th Annual ACM Symposium on Applied
Computing, 2015, pp. 494–500.
[12] Sugiyama, A. and Sugawara, T.: Improvementof Robustness to Environmental Changes by Au-

tonomous Divisional Cooperation in Multi-agent
Cooperative Patrol Problem, Springer International
Publishing, 2017, pp. 259–271.
[13] Suseki, K., Mizuguchi, T., Sugawara, K., andKosuge, K.: Proportion Regulation for Division ofLabor in Multi-Robot System, Proeedings of the2005 IEEE/RSJ International Conference on In-

telligent Robots and Systems, Aug 2005, pp. 2339–
2344.
[14] Yoneda, K., Sugiyama, A., Kato, C., and Sugawara, T.: Learning and relearning of target decision strategies in continuous coordinated cleaningtasks with shallow coordination, Web Intelligence,Vol. 13, No. 4(2015), pp. 279–294.