SigSai201311 Obashi Recent site activity jsaisigsai

(1)

RoboCup Rescue シミュレーションに対する距離概念を導入し

た平均探索情報量の提案

Proposal of the average search information that introduces the

concept of distance against RoboCup Rescue Simulation

尾橋大

^1∗

川村真之

¹

伊藤暢浩

¹

大原滝也

¹

堀江幸生

¹

Dai Obashi

¹

Masayuki Kawamura

¹

Nobuhiro Ito

¹

Tatsuya Ohara

¹

Sachio Horie

¹

1

愛知工業大学大学院経営情報科学研究科

1

AICHI INSTITUTE OF TECHNOLOGY Graduate School of Business Administration and

Computer Science

Abstract: By defining the complexity of the urban, to reveal the relevance of environment and agent in a multi-agent simulation. Further, it is intended to predict the activity of the agent results from the Relevance. In this paper, we use the urban maps as the urban road networks to illustrate the concept of navigability in networks and investigate how different network topologies influence the average amount of information that is needed to move from one node to another node in the network. Furthermore, we compare with the idea that added the concept of distance to the idea. Putting our purpose, we analyze representative maps used by RoboCup Rescue simulation and consider the relations of the agent strategy and each maps effectiveness of the disaster management by analyzing relevance with the map information and agents.

1 _はじめに

近年，世界各地で大規模な自然災害による被害が頻発しているため，地震災害に対しての警戒が高まっている．このような地震災害に対する取り組みの一つに災害救助シミュレーションとしての RoboCup Rescue シミュレーションがある．これは被災した仮想都市において，様々な種類の災害や災害救助部隊，市民の振る舞いをシミュレートするマルチエージェントシミュレータである．RoboCup Rescue におけるエージェントの活動評価は，シミュレーションの環境とエージェントの戦略に依存しているため，エージェントと環境との依存関係を調べる必要がある．

この問題に対し，瀬戸口の「道路ネットワークの複雑さと移動型エージェントシミュレーションとの依存関係について」[1] では道路が複雑になるほど移動難易度が高くなり，災害救助戦略の評価が悪くなると結論がでている．また，瀬戸口の研究に基づいた堀江らの

「平均探索情報量とマルチエージェントシミュレーションとの関連性についての考察」[2] では，都市の道路網の複雑さを数値化し，定量的に示す指標である平均探

∗_{連絡先：愛知工業大学}

愛知県豊田市八草町八千草 1247

TEL:(0565)48-8121 FAX:(0565)48-0277 E-mail: [email protected]

索情報量を用いて，都市の道路構造と災害救助の評価との依存関係の分析を行った．しかし，堀江らが研究で用いた平均探索情報量は災害救助にそのまま用いるには十分であるとはいえない．また，彼らの研究は実験数が少ないため，災害救助の評価と密接なかかわりがあると断言できなかった．

そこで本研究では，平均探索情報量を用いて，都市の道路網の複雑さと RoboCup Rescue シミュレーションにおける災害救助シミュレーションとの，より詳細な関係の分析をおこなう．また，平均探索情報量をもとに災害救助に適した，より詳細な都市道路ネットワークの定量化指標の提案をおこない，RoboCup Rescue シミュレーションとの依存関係の分析をおこなった．平均探索情報量は，Rosvall ら [3] によって提唱された，都市道路網の複雑さを数値化する指標である．この指標は道路に注目した解析をおこなうため，道路ネットワークをグラフへと変換する際に道路をノード，交差点をエッジとして表現する．これにより，通常のグラフ理論で表現される交差点をノード，道路をエッジとしたグラフとは異なり，道路から道路への結合にのみ注目したグラフが得られる．変換後のグラフでは道路が起点となるため，道路の「どの位置」から「どの位置」へ移動するのか，という情報が無い．そのため，

「距離」という情報を含まないグラフとなる．

(2)

災害救助を考える上で目的の場所へ素早く到達することは重要であり，目的地までの距離は短いほど早く目的地へ移動が可能となる．そのため，目的の場所へ早くたどり着くために目的地までの経路の距離情報は重要である．本研究では，この「距離」という情報を，重みという形で平均探索情報量に与えることによって， RoboCup Rescueシミュレーションにより適した指標の提案をおこなう．

道路から道路への距離を求める場合，移動主体が道路の「どの場所」にいるのか，道路上の「どの場所」が目的地なのかという問題がある．そこで，道路から道路へ移動する場合に始点と終点を定義することにより，道路から道路への距離を求める．「始点」は，移動を開始する道路から次の道路へ入る交差点であり，移動を開始する場合は始点を起点とする．「終点」は，目的の道路の全長の中心点であり，エージェントの移動目標道路上の終点を目的地とする．この始点と終点により，道路から道路への距離を求める．そして，より距離の短い経路ほど選択しやすくするために，経路の距離の逆数を平均探索情報量の経路の選択確率に重みとして与え，距離を考慮した平均情報探索量を定義する．

本研究では，以上の距離を考慮した平均探索情報量を用いて，都市の道路の複雑さと RobpCup Rescue シミュレーションにおける災害救助との関係の分析をおこなった．その結果，道路網が複雑な場合，RoboCupRes- cueシミュレーションにおける評価に影響を与える道路以外の要素も密に集まると考えられるため，災害救助が難しくなる．そのため，道路網の複雑さにより， RoboCupRescueシミュレーションにおける評価との間に依存関係があることはわかった．しかし，シミュレーションの結果は，用いるエージェントアルゴリズムにより変わる可能性があり，道路ネットワークだけでは，RoboCupRescue シミュレーションにおける評価を推測することは難しいと考えられる．

また，距離概念を導入した平均探索情報量により RoboCup Rescueシミュレーションにおける評価を推測することは，評価に影響を与える道路以外の要素による影響が無視できないことから，「道路網の複雑さ」と「道路以外で評価に影響を与える要素」を分析する必要があることがわかった．

2 RoboCup Rescue _{シミュレーシ}

ョンにおける評価

RoboCup Rescueシミュレーションは地震災害による火災や建物倒壊，道路閉塞が発生した被災都市において，災害救助隊が市民の救助および火災の消火をおこなうシミュレーションである．RobocupRescue におけるエージェントの活動評価は，そのエージェントに

よる消火活動や救助活動などにより，市民の死傷や火災といった都市の被害を次式（1）によって求まる都市価値 V によって評価する．ただし P は災害救助活動後に生存しているエージェントの数，S は災害救助活動後におけるすべてのエージェントの体力の合計，Sintは災害救助活動前におけるすべてのエージェントの体力の合計，B は災害発生に燃え残った建物の面積，Bint

は災害発生前におけるすべての建物の面積である．

V = (

P+ ^S Sint

) √ B Bint

(1) しかしエージェントの活動評価は環境に依存しており，環境である地図の変更によって，エージェントの活動評価が変化する．すなわち，エージェントの持つ純粋な能力の評価をおこなうためにはエージェントと地図の間に存在する関連性を明らかにする必要がある．

3 _{平均探索情報量}

3.1 _{平均探索情報量とは}

2章の背景に対して，堀江らは Rosvall らによって提唱された平均探索情報量 [3] をもとに，環境として与えられる都市の道路ネットワークに注目し，道路ネットワークを数値化てしエージェントの活動評価との依存関係の考察をおこなった．平均探索情報量はネットワークの複雑さを数値化し定量的に表すことののできる指標である．

Rosvallらはインターネットや細胞組織のようなネットワークにおける情報の伝播を説明するために，様々な構造をもつネットワークで，ある地点からある地点へ向かってどのように情報が伝わるかを考察した．まず，ネットワーク全体における情報伝達にかかるコスト（情報量）に着目し，都市道路ネットワークに適用した．都市の中で道路を歩く人が，ある場所から目的の場所を見つけるために実際の移動距離は必要ないと考え，道路ネットワーク上で目的の場所に移動する場合に距離，移動時間をゼロとし，必要な情報のみに着目した．その後，道路の結合だけを表すグラフを作成し，その複雑さを定義するために平均探索情報量「S」値を定義した．

3.2 平均探索情報量と道路ネットワーク

平均探索情報量では用いる道路ネットワークに以下の制約を与えている．

1. 任意の点において，自身と繋がる道路（自己ループ）は存在しない

(3)

2. 対となる任意の点同士の間には複数の道路は存在しない

3. 任意の 2 点において，一方から他方への経路は必ず存在する

これらの制約に従い，道路ネットワークのグラフへの変換を行う．しかし，RoboCup Rescue シミュレーションにおいては現実の道路網をもとに作成されることが多いため，これらの制約に従わない場合が存在する．以下に本研究での制約に従わない道路ネットワークの扱いについて述べる．

自身と繋がる道路が存在する場合

自身と繋がる道路が存在する場合，平均探索情報量を求めることができない．そのため，本研究では自身へと繋がる道路は存在しないものとし，存在する場合はその道路を削除する．

対となる任意の点同士の間に複数の道路が存在する場合現実の道路ネットワークにおいては，中央分離帯に区切られた並走した道路が存在する．並走した道路が存在する場合，平均探索情報量を求めることができないため，本研究では並走する道路を 1つの道路として扱う．

任意の 2 点において経路が存在しない場合

任意の 2 点間において経路が存在せず到達不可能な地点が存在する場合，平均探索情報量を求めることができない．また，到達不可能な地点が存在する場合，平均探索情報量での扱いは 2 通り考えられる．

1. その地点への経路の情報量は 0 である（到達できない）

2. 到達不可能な地点がある地図データを除外する

1の方法を採用することは平均探索情報量において複雑さを表す「S」値が変化してしまう可能性がある．そのため，本研究では 2 の方法を採用し，到達不可能な地点が存在する地図データは使用しないものとする．

3.3 道路間の結合を表すグラフへの変換

平均探索情報量は，都市の景観分析で用いられるスペースシンタックス理論をもとに道路ネットワークを道路同士の結合を表すグラフへの変換をおこなう．スペースシンタックス理論は，空間解析の手法の一つであるが，解析対象とする空間を特に指定していない．そ

のため，平均探索情報量ではこの解析対象を都市の道路ネットワークと考える．

道路間の結合を表すグラフへの変換は，道路ネットワークにおける「道路」をノード，「交差点」をエッジとみなし変換を行う．変換例を図 1 に示す．

図 1: 道路ネットワークから道路結合を表すグラフへの変換

図?? の左図は道路 1,2,3,4,5 から構成される道路ネットワークとなっている．この道路ネットワークにおいて道路間の結合のみに着目した解析をおこなうために，より単純なグラフへの変換を行ったのが右図である．変換後のグラフでは道路間の結合のみに注目したため，距離や移動時間をゼロと仮定されている．そのため，グラフの変換により目的の場所への「距離」という情報が取り除かれている．

3.4 _{平均探索情報量の定義}

起点となる道路 s から終点となる道路 t に到達する確率 P [p(s, t)] は式（2）で表される．_k¹

s ^{は出発点での}

確率，_k¹

j−1は s から t へ移動する途中の各ノード j における確率を表しており，kiはノード i の次数，kjはノード j の次数である．

P[p(s, t)] = ¹ ks

∏

j∈p(s,t)

1

kj− 1 ⁽²⁾ 起点となる道路 s から終点となる道路 t に到達する遠回りしない複数の経路が存在する合計確率から求められる経路の情報量は，次式（3）で表される．ここで，

「遠回りしない」とは，起点となる道路 s から終点となる道路 t に到達する経路の中で，エッジの数がもっとも少ないことを意味する．

S(s → t) = − log₂





∑

p(s,t)

P[p(s, t)]



 (3) すべての起点とすべての終点についての S(s → t) の和を，自身の点を含まない始点終点の数 N(N − 1) で割ったものが S 値であり，式（4）式で表される．

S= ¹ N(N − 1)

N

∑

s6=t

S(s → t) (4)

(4)

3.5 平均探索情報量を災害救助に用いる場

合の問題点

災害救助では，目的地まで素早く到達することが重要であり，より短い距離で目的地まで移動することが必要となる．そのため，目的地までの「距離」という概念は災害救助を考える上で切り離すことはできない．そのため，目的地までの「距離」の概念が存在しない平均探索情報量は災害救助に適した指標ではない．

そこで本研究では平均探索情報量へ「距離」の概念を導入し，RoboCup Rescue シミュレーションの評価に適した指標を定義し，RoboCup Rescue エージェントとの関連性の分析をおこなうことにする．

4 距離概念を導入した平均探索情報

量

4.1 _{道路同士の距離の算出}

平均探索情報量における経路の選択確率を，始点から終点までの距離によって重みづけをおこなう．「始点」とは経路同士が始めに繋がる交差点をさし，「終点」とは到着目的である道路の長さの中間点を指す．例を図 2に示す．道路 1,2,3 が存在し，道路 1 から道路 3 までの道路 2 を経由した距離は，始点と終点間で示された距離となる．

図 2: 道路同士の距離の算出法

4.2 閉路となる道路について

4.1節で述べた距離概念の算出法を用いるにあたり閉路となる道路を展開する必要がある．展開例を図 3 に示す．

図 3 左図では，道路 1 が閉路となっている．閉路となっている道路は任意の場所から閉路を展開し，1 本の直線な道路として処理をおこなう．図 3 右図は展開処理をおこなった例である．

図 3: 閉路の展開例

4.3 距離概念を導入した平均探索情報量の

定義

起点となる道路 s から終点となる道路 t までの距離を ds→tとし，距離重み D[p(s, t)] を式（5）で表す．

D[p(s, t)] = ¹ ds→t

(5) 式（5）求められた重みを，式（2）の選択確率に与え，得られる経路の情報量 Sd(s → t) を式（6）に表す．

Sd(s → t) = − log₂





∑

p(s,t)

P[p(s, t)] ∗ D[p(s, t)]



 (6) すべての起点とすべての終点について Sd(s → t) の和を，自身の点を含まない始点終点の数 N(N − 1) で割った値を Sd 値と定義し，式（7）に表す．

Sd= ¹ N(N − 1)

N

∑

s6=t

Sd(s → t) (7)

5 _{分析内容・結果・考察}

5.1 _分析内容

本研究での RoboCup Rescue シミュレーションの設定は，瀬戸口らの実験に基づき以下のように設定する．エージェントアルゴリズム

動作するエージェントアルゴリズムによって道路網の複雑さの指標と災害救助エージェントの評価との依存関係が変化することが考えられる．よって本研究では RoboCup2007 において MRL チームの開発したエージェントアルゴリズム（以下 MRL）と，NAITO-Rescue チームによって開発されたエージェントアルゴリズム（以下 NAITO）の 2 種類を用いて実験を行う．

(5)

災害救助エージェントの評価方法

RoboCup Rescueシミュレーションにおける評価とは，災害救助エージェントの災害救助活動により，震災時における都市の被害をどの程度抑えることができたかを 2 節で述べた都市価値に基づいて評価することである．しかし都市価値は地図上に存在するエージェント数により値が大きく異なるため，異なる地図におけるエージェントの評価を比較することができない．

そこで本実験では，シミュレーション開始時の都市価値に対するシミュレーション終了時の都市価値の割合を都市価値維持率として定義し，都市価値維持率を用いて評価を行う．シミュレーション開始時の都市価値を Vini，シミュレーション終了時の都市価値を Vendとするとき，都市価値維持率は次式（8）で数値化される．

Vrate= ^V^end Vini

(8) 地図データ

名古屋市の千種区・北区・中川区・天白区のうち，東海・東南海連動地震の震度予測が公開されている地域 [4] から 18 の地域を選択する．公開されている震度予測地図の一部を図 4 に示す．

図 4: 中川区の震度予測地図

5.2 _{分析結果・考察}

都市価値維持率を従属変数，Sd 値を説明変数とした回帰分析及び，S 値を説明変数とした回帰分析との比較をおこなった．得られた相関係数と自由度調整済み

決定係数を表 1 に示す．また，相関の強弱の基準として参考文献 [5] をもとに表 2 に示す基準を用いる．

表 1: 回帰分析結果

相関係数自由度調整済み決定係数 MRL S値 −0.7726 05717

Sd値 −0.7870 0.5955 NAITO S値 −0.6057 0.3272 Sd値 −0.6186 0.3441

表 2: 相関の強弱の基準相関係数 (絶対値) |r| 相関の強弱

|r| ≥ 0.7 強い相関がある 0.7 > |r| ≥ 0.4 中程度の相関がある 0.4 > |r| ≥ 0.2 弱い相関がある

0.2 > |r| ほとんど相関がない

ここで，回帰直線の精度を判定するにあたり，本研究では決定係数を用いた．決定係数による回帰直線の精度の基準として，参考文献 [6] をもとに表 3 を用い，決定係数が高ければ（本研究では 0.5 以上），回帰式は従属変数の推測に使えると判断することとする [6]．

表 3: 決定係数による回帰直線の精度の基準決定係数 R² 回帰直線の精度

R²≥ 0.8 精度よい 0.8 > R²≥ 0.5 精度ややよい

0.5 > R² 精度よくない

5.2.1 都市価値維持率との依存関係

距離概念を導入した平均探索情報量と都市価値維持率の相関関係は MRL で強い負の相関，NAITO でやや強い負の相関があり，距離概念を導入した平均探索情報量が高い地図データほど都市価値維持率が低くなることがわかる．よって，本設定のもとでおこなう RoboCup Rescueシミュレーションでは距離概念を導入した平均探索情報量ほど災害救助エージェントは災害救助活動をおこなうことが難しいと考えられる．

また，MRL の決定係数が 0.5955 であり回帰直線の精度がよいことから，距離概念を導入した平均探索情

(6)

報量から都市価値維持率の推測が可能であると考えられる．対して NAITO の決定係数は 0.03441 であり，回帰直線の精度がよくないため，都市価値維持率の推測は難しいと考えられる．この決定係数の差はエージェントアルゴリズムの違いが大きく影響を及ぼしている．そのため，距離概念を導入した平均探索情報量からだけでは都市価値維持率を推測可能なエージェントと推測の難しいエージェントが存在すると考えられる．

5.2.2 平均探索情報量との比較

都市価値維持率との依存関係は，平均探索情報量より距離概念を導入した平均探索情報量の方がどちらのエージェントアルゴリズムでも強くなっている．この結果から，RoboCup Rescue シミュレーションを考える上で「距離」の概念は取り除くことができない情報の一つであり，距離概念を導入した平均探索情報量は平均探索情報量より RoboCup Rescue シミュレーションの評価に適した指標であると考えられる．

6 _{まとめと今後の課題}

本研究では，災害救助を考える上で取り除くことのできない「距離」の概念を平均情報探索量に導入し，災害救助エージェントと都市構造の依存関係の分析を行った．そして，平均探索情報量と距離概念を導入した平均探索情報量との結果を比較することで本実験で定義した距離概念を導入した平均探索情報量の検討をおこなった．その結果，距離概念を導入した平均探索情報量が高い地図データほど都市価値維持率が低くなる傾向があることがわかった．また，エージェントアルゴリズムによって道路ネットワークが都市価値維持率に与える影響の大きさが異なると考えられた．

今後の課題として，地図情報とシミュレーション結果との関係は建物情報や発火点，使用するエージェントアルゴリズムなど道路ネットワーク以外の環境により大きく変わる可能性があるため，道路ネットワーク以外の要素と都市価値維持率との依存関係についての検証が必要である．また，本研究では 18 の地域と 2 つのエージェントアルゴリズムを用いて分析を行ったが，より詳細な依存関係を求めるためにも，より多くのエージェントアルゴリズムや災害状況，地図データを用いての分析が必要である．

参考文献

[1] 瀬戸口陽一．”道路ネットワークの複雑さと移動型エージェントシミュレーションとの依存関係について ”，2007.

[2] 堀江幸生，伊藤暢浩，幸塚義之，園田純．”平均探索情報量とマルチエージェントシミュレーションとの関連性についての考察 ”，2010．

[3] M. Rosvall, A. Gronlund, P. Minnhagen, and K. Snep-pen,“Searchability of networks”. Physical Review E72, 046117,2005.

[4] 名古屋市公式ウェブサイト， http://www.city.nagoya.jp/

[5] 菅民郎．”らくらく図解統計分析教室 ”, Ohmsha. [6] 田中敏．”実践心理データ解析’ ”, 新曜社,1996.