wssit2016 sig sai 1 Recent site activity jsaisigsai wssit2016 sig sai 1

すれ違い通信と耐故障経路探索アルゴリズムによる災害時避難法

について

On Evacuation Method in Disaster by Opportunistic

Communication and Fault-Tolerant Evacuation Route Finding

川上 拓真

泉 泰介

伊藤 暢浩

岩田 員典

Kawakami Takuma

Izumi Taisuke

Ito Nobuhiro

Iwata Kazunori

1

_{名古屋工業大学}

1

Nagoya Institute of Technology

2

_{愛知工業大学}

2

Aichi Institute of Technology

3

_愛知大学

3

Aichi University

Abstract: In this paper, we focus on exhibiting proper homecoming routes to persons difficult to come their homes or refuges after disasters. They cannot find out appropriate escape routes in the situation because of lack of information. We propose a new route planning algorithm that can select safe routes based on the A-star algorithm with opportunistic communication to solve this problem. In addition, we evaluate our algorithm on disaster situations through some experiments.

1 _はじめに

大規模な自然災害に対して，現在様々な取り組みが 行われている. 大都市での地震災害時の状況の 1 つの 例として，多くの市民が避難することにより，帰宅難 民が発生することが挙げられる. 帰宅難民が発生する 原因は様々であるが，原因の 1 つとしては災害時の周 辺の被災状況，安全な避難場所や避難経路，利用可能 な交通機関など，必要な情報が手に入らないことであ る. そのため，災害環境下での経路探索及び情報共有 手法は重要な問題と考えられ，様々な手法が提案され ている.

本論文では災害時の経路探索と通信による情報共有 の両方に着目した，すれちがい通信を利用した災害時 避難誘導システム [1] に注目した. しかし，災害時にお ける経路探索と情報共有を対象としているにもかかわ らず，経路探索としては経路上の故障を考慮していな い. そこで本論文では，既存の研究である故障を考慮 した期待値+A^⋆アルゴリズム [2] を，すれ違い通信環 境下の災害時の避難活動問題に適用し，その有効性を 確認する. また，既存の研究である故障を考慮した期待 値+A^⋆アルゴリズムは計算時間が非常に長いため，よ

∗連絡先： 名古屋工業大学

       愛知県名古屋市昭和区御器所町        E-mail: t.kawakami.832@nitech.jp

り高速で，かつ，避難時間や故障衝突回数に関してほ ぼ同程度の質が達成可能な，故障を考慮した経路探索 法を提案し，その有効性を確認する．

2 災害時避難問題とアプローチ

本章では，研究の対象とする災害時避難問題とすれ ちがい通信を利用した災害時避難誘導システム [1] の解 説を行う．

2.1 _{災害時避難問題}

本論文では災害として，都市直下型地震を主に取り 扱う．災害時は震災による一次被害と併せて様々な二 次被害が想定される．以下にその一例を示す．

• 建物の倒壊

• 道路の液状化などによる道路の通行障害

• 大勢の被災者の集中によるひどい混雑（輻輳）

• 建物や電気系統の破損による火災及び延焼

• 避難者の負傷や地形の変化による避難行動の複 雑化

• 通信システムの障害による情報伝達手段の喪失 これらの被害はそれぞれが相互に作用するといわれて いる．例えば道路に通行障害が起きたために普段利便 性の高い道路が利用できず，避難者が何度も経路を変 更しなければならなくなる等である．このような環境 での被災者の避難活動時に起こる問題を災害時避難問 題という．

2.2 すれ違い通信を利用した災害時避難誘

導システム

すれちがい通信を利用した災害時避難誘導システム [1]について紹介する．このシステムはスマートフォン のような携帯電話にインストールされているアプリケー ションを介して実行され，通信インフラの崩壊により ウェブサービスが完全に停止してしまった大都市にお ける，予期しない大規模災害時において機能すること を目的とする．また，スマートフォン同士の通信，つ まりスマートフォンによる局所的な通信は可能である とする．この際の避難誘導アプリケーションの誘導手 順は次の通りである．

• 大規模災害が起こった直後，各避難者は携帯電話 からアプリケーションを起動

• アプリケーションは最寄りの避難所と，現在地か ら避難所にたどり着くための最短経路に基づいた 避難経路を提案

• 避難者はアプリケーションからの避難経路に従い 避難

• 避難者は避難途中で災害による火災や建物倒壊に より通行不能となった道路に遭遇した場合，その 位置情報をアプリケーションに記録（避難者によ る被災地情報収集）

• 避難者同士が出会った場合，アプリケーションは すれちがい通信を行い，互いのもっている通行不 能道路の情報を自動的に共有（避難者同士による 被災地情報共有）

• もし，位置情報による記録結果または，すれちが い通信の結果から避難経路上に通行不能道路があ れば，アプリケーションは自動的に避難経路を再 計算し，提示

すれ違い通信を利用した災害時避難誘導システムに おいては，初期に地図と周辺の避難所に関する情報を 既に保持していることを仮定している．これは，平常 時から定期的に周囲の地図と周辺の避難所の情報を端 末に保持しておくようにすることで，可能である．

2.3 _諸定義

グラフ

本論文では地図上の道路の構造をグラフと考える．地 図上の道路の経路探索がおこなわれる重み付きグラフ Gを以下のように定義する．

• G = (V，E，C，B)

V はノード (node) の集合であり，E はノードとノード をつなぐ辺 (edge) の集合である．|V | = n，|E| = m と すると，V と E を以下のように表現できる．

• V = {1，2，．．．，n}

• E = {e1, e2, ..., em}

また，ノード i，j 間の辺を e_i，jとも表現する．この とき，任意のノード i，j ∈ V について e_i，j と e_j，iを 同一視し，また ei，jはただ 1 つに定まるとする．また， 辺にコストを与える関数 C を以下のように定義する．

• C : E → R^>0

ここで，コストとは辺 ei，j上で輻輳等が発生しない状態 での移動時間であり，辺 e_i，jに与えられたコスト ce_i，j

は c_i，jと略記する．

経路

辺 ei,j に対して，vertex(ei,j) = {i, j}と書くとき， 辺 e1, e2, ..., ek ∈ E(k ≥ 1)の各 i = {1, 2, ..., k − 1} に 関して，ei̸= ei+1かつ vertex(ei) ∩ vertex(ei+1) ̸= ∅ のとき，(e1, e2, ..., ek)を経路と呼ぶ．

また経路 (e1, e2, ..., ek)に対し，k ≥ 2 のとき，i ∈ vertex(e1) かつ j ∈ vertex(ek)かつ i ̸∈ vertex(e2) かつ j ̸∈ vertex(e_k−1)のとき，経路 (e1, e2, ..., ek)は ノード i からノード j への経路と呼ぶ．k = 1 ならば vertex(e1) = {i, j}のとき e1を頂点 i から j への経路 という．

故障発生率

辺に故障発生率を与える関数 B を以下のように定義 する．

• B : E → R>0

ここで，辺 e_i，j に与えられた故障発生率 Be_i，j は b_i，j と略記する．本論文で扱う経路故障は，シミュレーショ ン開始時に各辺に与えられた故障発生率に基づいて発 生する．以降，経路故障が発生した辺を故障辺と呼ぶ． ノード上では故障は発生しない．また，故障発生率並 びに故障辺はシミュレーション開始時点で決定され，シ ミュレーション中に増減する事はない．

最短経路

ノード i からノード j までの最短経路を以下のよう に定義する．

• ノード i からノード j までの全ての経路の中で， 経路内の辺のコストの総和が最小になる経路 また，最短経路のコストを最短コストと呼ぶ． 

迂回経路

迂回経路とは，最短経路上のある辺が故障により通 行不可能であると仮定した時の (次善の) 最短経路であ る．頂点 i から j への経路を pathi,j，頂点 i から j へ の経路集合を P ath(i, j) とし，既知である故障により 通行不能である辺を fail，そのような辺の集合を F ail とする．頂点 i から j への故障のある辺を通らない経 路の集合 Alt は次のように記述する．

• Alt(i, j) = {alti,j|alti,j ∈ P ath(i, j), ∀f ail ̸∈ alti,j}

ノード i 及び j に関して，alti,j ∈ Alt(i, j)かつ ∀alt^′_i,j ∈ Alt(i, j) で C(alti,j) ≤ C(alt^′_i,j)であるとき，alti,jを ノード i から j への迂回経路と呼ぶ．またこのときの C(alti,j)を迂回経路コストと呼ぶ．

迂回経路を選択した場合の移動コスト

最短経路が (e1,2, e2,3, e3,4, ..., e_n−1,n)で表され，辺 (i, i + 1)(1 ≤ i ≤ n − 1)で故障が発生して迂回経路を 選択しなければならない場合のノード 1 からノード n までの移動コスト Calt(1, i, n)は次のようになる．

• Calt(1, i, n) =^∑i−1_j=1(cj,j+1) + C(alti,n)

迂回経路を選択しなければならない確率

最短経路が (e1,2, e2,3, e3,4, ..., e_n−1,n)で表される場 合，辺 (i, i + 1)(1 ≤ i < n) で故障が発生して迂回経路 を選択しなければならない確率 Palt(i, i + 1)は次のよ うになる．

• Palt(i, i + 1) = (1 − b1,2) ∗ (1 − b2,3) ∗ . . . ∗ (1 − b_i−1,i) ∗ (bi,i+1)

エージェント

本論文では，避難対象者をエージェント化して実験 を行う．探索を開始するノード (開始ノード) から目的 地となるノード (目的地ノード，避難所) へ移動する対 象をエージェントと呼ぶ．目的地ノード（避難所）は マップ上で 1ヶ所である．また，エージェントは同一グ ラフ上に複数存在し得る．各エージェントの能力及び 動作を以下のように定義する．

• 各エージェントは ID を持ち，それぞれ識別可能

• エージェントは与えられたグラフに従って移動先 ノードを決定

• 複数のエージェントが同一環境に存在する場合， 全エージェントは同時に動作可能

• エージェントは，初期状態で故障情報を除いた， グラフに関する情報を取得保持可能

• エージェントの通信は通信範囲内に存在するエー ジェントと通信可能

• エージェント同士は独立して移動し，発見した故 障に関する通信が可能

• エージェントは移動しながら通信が可能

• エージェントの移動速度は毎秒 1.1m

• エージェントは故障辺に接続しているノードが視 認範囲内に到達するまで，経路故障を取得不可能

• エージェントは経路故障が発生後，ランダムな位 置に配置され，避難所に移動が完了したら停止

3 _{関連・先行研究紹介}

ダイクストラアルゴリズム

ダイクストラアルゴリズムとは，スタートノードか らの距離が最小になるノードを順次探索し，スタート からの距離を格納していくアルゴリズムである．全て のノードに対してスタートからの距離を格納した場合， もしくは決められたゴールノードの探索が完了した時 点でアルゴリズムは終了する．

A

アルゴリズム

A^⋆アルゴリズムは目標指向探索の一種であり，node potentialとして各ノードから目的地ノードへの最短コ ストの推定値を使用して経路探索を行う．ダイクストラ 法などのアルゴリズムと比較すると，目的地ノードに

近いと推定されるノードを優先して探索するため，全 探索をせず短い計算時間で探索することができる．A^⋆ アルゴリズムでは次に探索するノードを選択する際に， 開始ノードから候補となるノードを経由して目的地ノー ドへ至る最短コストの推定値を求め，推定値が最小に なるノードを経路として選択することで経路探索を進 める．候補となるノード i を経由した場合の移動コス トは式 1 で求める．

fˆ(i) = g(i) + ˆh(i) (1) ここで，g(i) は開始ノードからノード i までの最短 コストを，h(i) はノード p から目的地ノードまでの最 短コストを意味する．探索がノード i まで進んでいる ため，g(i) は開始ノードから i までに経由した辺のコ ストから求めることができる．ˆh の値は距離の推定値 を用いる．既存手法では主にユークリッド距離やマン ハッタン距離が用いられる．

期待値+A

アルゴリズム

期待値+A^⋆アルゴリズムは，社本らによって提案さ れた，障害発生を考慮した経路探索アルゴリズムであ る．このアルゴリズムは災害時に建物の倒壊や道路の 液状化などの要因で経路の障害が発生する状況を想定 し，障害の迂回に要する移動コストを軽減することに 焦点を当てたアルゴリズムである，アルゴリズムでは 全ての辺の障害発生率が予め得られる仮定のもと，障 害発生率と要する迂回経路長の期待値を計算し，それ を A^⋆アルゴリズムの候補ノードから目的地ノードまで のコストの推定値として使用したアルゴリズムである．

目的地ノードまでの経路が ei,i+1, ei+1,i+2, . . .で表さ れる場合，推定値 ˆh(i) の計算方法は以下のようになる．

1. ノード p から目的地ノードまでの最短コストを計 算する (障害を考慮せず行う)．

2. 最短コストで目的地へ到達できる確率を計算する． 3. 1.と 2. で得られた値を乗算する．

4. ノード j において辺 ej,j+1が通れない場合の迂 回経路を使用した移動コストと，その迂回経路を 使用する確率を計算し，乗算する．

5. 4.の結果を経路内の全ての辺について求め，総和 を求める．

6. 3.および 5. で得られた値を加算した結果が推定 値 ˆh(i) となる．

4 提案手法

4.1 _{提案手法の詳細}

期待値+A^∗アルゴリズムは 3 章で述べたとおり，推 定値 ˆh(p) の評価方法を算出するためには，迂回経路 alti,n，および Calt(p, i, n)を計算する必要がある. グラ フの条件を変更して迂回路の経路探索をしなければな らないので，スマートフォンなどのアプリ上でのスタン ドアローンな計算では，計算時間が非常にかかると予 想される. そのため，迂回経路のコストを Calt(p, i, n) をノード i とノード n のユークリッド距離に代替した手 法を提案する，具体的にはノード p から目的地までの 最短経路が (ep,p+1, ep+1,p+2, . . . , e_n−1,n)である場合， 推定値 ˆh(p) の評価方法は以下のようになる.

1. ノード p から目的地ノードまでの最短コストを計 算する.(既存アルゴリズム同様に故障を考慮せず 行う)

2. 1.で求めた最短コストとなる経路上の各ノード iにおいて辺 ei,i+1が通れないと仮定したとき， ノード i とノード n のユークリッド距離 を計算 する.

3. 2.を基に ∑ⁿ⁻¹_i=p{Palt(i, i + 1) ∗ (ノード i とノー ド n のユークリッド距離)} を計算する.

4. 2.と 3. の結果を加算した結果を推定値 ˆh(p) とし 代入する.

つまり，Calt(p, i, n)を ノード i とノード n のユーク リッド距離 にすることによって計算時間を短縮する.

4.2 _{提案手法の動作例}

期待値+A^∗アルゴリズムの動作例でも使用した図 1 に示すグラフにおいて，ノード v1からノード G への 最短経路探索を提案手法によって探索する例を述べる. ノードの近くに記載されている座標はそのノードの位 置であり，辺の近くに記載されている赤数字は辺のコ スト，黒数字は辺の故障率である.

アルゴリズムは以下の流れに沿って行われる. 1. ノード v1に隣接しているノード v2について ˆh(p)

を計算する. ノード v2からノード G への最短経 路 (ev2,v3, ev3,v6, ev6,G)である.

(a) 最短経路のコスト:2 +√3 = 3.732 (b) (迂回経路を選択しなければならない確率×

ユークリッド距離) の合計: = (ev2,v3が故障 している確率 ∗ v2と v3のユークリッド距離 ) + (v3までたどり着いて ev3,v4が故障してい

図 1: 入力グラフのイメージ

る確率∗v3と G のユークリッド距離)+(v6ま でたどり着いて ev6,Cが故障している確率∗v6

と G のユークリッド距離) = 0.01 ×√13 + 0.99×0.01×√10+0.99×0.99×0.02×√3 = 0.101

(c) ˆh(p) = 3.83 + 0.10 = 3.83

2. 同様に，ノード v4について ˆh(p) を計算する. こ こでは 3.81 となる.

3. ノード v2, v4の ˆf(p)を計算する.

(a) ノード v2の ˆf(p) = g(p)+ˆh(p) = 1+3.83 = 4.83

(b) ノード v4の ˆf(p) = g(p)+ˆh(p) = 1+3.81 = 4.81

4. ノード v1に隣接しているノードの中で， ˆf(p)の 値が一番小さいノードを選択する. ここではノー ド v4を選択する.

5. ノード v4に隣接しているノードの中でまだ探索 していない v8について ˆf(p)を計算する. 今回は v4に隣接しているノードはひとつなのでノード v8を選択する.

6. ノード v8に隣接しているノードの中でまだ探索 していない v5, v9, v10について ˆf(p)を計算する. 7. ここではノード v10へ選択する.

8. ノード v10に隣接しているノード G は目的地な ので，ノード G を選択する.

9. 目的地まで探索したので，アルゴリズムを終了 する.

迂回経路のコストをユークリッド距離にすることによっ て，計算量を減らしている. 上記の動作例のノード v2

について ˆh(p) を求めるための 1(b) の式で迂回路の探 索計算をユークリッド距離に 3 回置き換えている. ま た，ノード v1からノードノード G までの経路を求め るまで，10 回置き換えている. そのため，置き換えた 回数分だけ迂回経路の探索をしなくてもいいため，計 算量が減り，計算時間が減ることが期待できる.

5 _実験

5.1 実験目的

本論文では，期待値+A^∗アルゴリズムと提案手法の 結果を比較し，避難時間，故障衝突回数について，ど の程度維持できたか，また，計算時間をどれだけ削減 できたかを実験で検証する．さらにすれちがい通信環 境での有効性を実験により検証する．

性能評価の為に，ダイクストラ，期待値+A^⋆，提案 手法，理論値としての故障が全て既知の場合と比較し て以下の要素を評価する．

• 避難時間

避難所までに避難するためにかかった時間である．

• 故障衝突回数

探索結果にしたがって移動中に故障のある辺に衝 突し，経路の再計算をする必要が生じた回数の累 計である．

• 通信による経路再探索回数

探索結果にしたがって移動中に通信によって故障 情報が更新され，故障のある辺を経路として選択 しており，経路の再計算をする必要が生じた回数 の累計である．

5.2 _実験環境

実験には THE ONE simulator を災害時避難問題用 に改良した．また使用した計算機の環境は表 1 の通り である．

表 1: 実験環境

OS Ubuntu 14.04

CPU Intel(R) Core(TM)i7-4770 CPU @3.40GHz

Memory 16.00GB

5.3 _{実験条件と内容}

実験条件

実験の条件は表 2 の通りとなる．マップは，グリッド 状マップ (図 2) で実験する．通信による故障情報の共 有の有効性も確認するため，通信のあり，通信のなし で実験する．

実験内容

シミュレーションは次のように行われる．シミュレー ション開始直後にマップを模したグラフの辺が故障率 b に従って，故障する．故障率 b はシミュレーションごと に 0 ≤ b < 1 の範囲でランダムに設定されている．そ の後，避難する人々を模したエージェントがマップ上 にランダムで配置される．避難所は 1 箇所のみで，シ ミュレーションごとにマップ上のランダムな箇所配置 される．エージェントは配置されたところから避難所 に避難する．避難後のエージェントは停止する．

図 2: グリッド状マップのイメージ図

表 2: 実験条件 エージェント数 100 エージェントの移動速度 1.1m/s

通信範囲 50m

視覚範囲 50m

試行回数 100

道路故障率 0 ≤ b < 1

5.4 _実験結果

5.5 グリッド状マップ

グリッド状の 10x10 のマップでのシミュレーション 結果を示す．表 3 に避難時間と通信による経路再探索 回数と故障衝突回数，図 3 と図 4 は避難時間の累積度 数分布，図 5 と図 6 は避難時間の箱ひげ図，表 4 と図 7は総シミュレーション時間を示す．

避難時間の累積度数分布 (図 3 と図 4) は，横軸が避 難できた時間（秒），その時間までに縦軸が避難できた エージェント数，赤線 (Dijkstra) がダイクストラ，緑線

（A-star）が期待値+A^⋆，青線 (Euclidean) が提案手法， 紫線 (Theoretical) が理論値を示す．総シミュレーショ ン時間の棒グラフ (図 7) は，Dijkstra-com は通信あり のダイクストラ，A-star-com は通信ありの期待値+A^⋆， Euclidean-comは通信ありの提案手法，Dijkstra は通信 なしのダイクストラ，A-star は通信なしの期待値+A^⋆， Euclideanは通信なしの提案手法，Theoretical は理論 値の総シミュレーション時間を示す．

表 3: グリッド状マップ

避難時間

通信あり 平均 標準偏差 中央値 最大値 最小値

ダイクストラ 3985.13 3172.15 3208.0 24561.0 3.0 期待値+A^⋆ 4112.23 3933.03 3103.0 33418.0 3.0 提案手法 3751.34 2883.35 3114.0 21401.0 3.0

通信なし 平均 標準偏差 中央値 最大値 最小値

ダイクストラ 5105.33 4759.28 3581.0 28331.0 3.0 期待値+A^⋆ 5154.26 5111.79 3565.0 36884.0 3.0 提案手法 4837.65 4821.53 3402.0 39418.0 3.0 理論値 2423.05 1249.18 2317.0 7675.0 3.0

通信による経路再探索回数

通信あり 平均 標準偏差 中央値 最大値 最小値

ダイクストラ 3.04 3.68 2 28 0

期待値+A^⋆ 2.83 3.53 2 24 0

提案手法 2.61 3.03 2 21 0

故障衝突回数

通信あり 平均 標準偏差 中央値 最大値 最小値

ダイクストラ 0.96 1.59 0 27 0

期待値+A^⋆ 0.85 1.46 0 22 0

提案手法 0.82 1.39 0 23 0

通信なし 平均 標準偏差 中央値 最大値 最小値

ダイクストラ 5.10 5.68 3 32 0

期待値+A^⋆ 4.77 5.63 3 37 0

提案手法 4.52 5.43 3 40 0

図 3: 避難時間の累積度数分布 通信あり グリッド状 マップ

図 4: 避難時間の累積度数分布 通信なし グリッド状 マップ

表 4: 総シミュレーション時間 グリッド状マップ 通信あり 時間（秒）

ダイクストラ 2239.49 期待値+A^⋆ 3962.06 提案手法 744.86 通信なし 時間（秒） ダイクストラ 388.30

期待値+A^⋆ 5046.56 提案手法 369.19

理論値 97.65

図 5: 避難時間の箱ひげ図 通信あり グリッド状マップ

図 6: 避難時間の箱ひげ図 通信なし グリッド状マップ

結果の考察

まず避難時間及び故障衝突回数について考察する．表 3より，通信ありのときの提案手法は期待値+A^⋆より， 平均避難時間は約 350 秒早く避難できた．また，図 3 か らも，5000 秒から 10000 秒にかけて避難したエージェ ントの数が期待値+A^⋆より提案手法のほうが多い事が わかった．図 5 からも 75%のエージェントは期待値+A^⋆ より提案手法のほうが早く避難できた事がわかった． また表 3 及び図 4 より，通信なしでも，次のように 通信ありと同様な結果が得られた．避難時間について は期待値+A^⋆より，提案手法のほうが約 300 秒早く， 5000秒から 15000 秒にかけて避難したエージェント数 も期待値+A^⋆より提案手法のほうが多かった．また図 6からも 75%のエージェントは期待値+A^⋆より提案手 法のほうが早く避難できた．

図 7: 総シミュレーション時間 グリッド状マップ

次にすれちがい通信環境での有効性について述べる． 表 3 より，通信なしより通信ありのほうが平均時間約 1000秒早く避難できる．特に提案手法の最大避難時間 は約 18000 秒くらい避難時間を抑えることができる． これは，故障した経路と遭遇し引き返すといった動作 の時に，故障した経路情報を保持していないエージェ ントが通信によって故障した経路情報を得ることがで きるためである．したがって，本手法はすれちがい通 信環境で有効であると考えられる．

次に通信による経路再探索回数について述べる．表 3より提案手法の再探索回数が一番少なかった．これ が先に述べた避難時間に影響したと考えられる．また， どの経路探索手法においても通信なしより通信ありの ほうが故障衝突回数を 4 回くらい少ない．これは，通信 による経路故障情報の共有による影響だと考えられる．

最後に計算時間について述べる．表 4 より，期待値 +A^⋆より提案手法のほうが，通信ありの時は 3200 秒， 通信無しの時は 4700 秒くらい，総シミュレーション時 間が短いので，提案手法によって，計算時間が改善さ れていると考えられ，本手法の有効性を確認できた． 以上により，提案方式は期待値+A^⋆アルゴリズムと 比べて，避難時間，障害衝突回数はほぼ同じかよりよ い結果を示しており，本手法の有効性は確認できる．し かし，本研究のアプローチは本質的に衝突回避を改善 しているわけではない．したがって，実験回数が 100 回 と少ないことに起因していると考えられる．さらには 計算時間を大幅に抑えることができている．したがっ て，提案手法はスマートフォンなどの小型の端末でも 短い時間で安全な経路を提案すると期待できる．また， 通信による故障情報に共有が「なし」より「あり」の ほうが早く避難できる．これは，故障した経路と遭遇 し引き返すといった動作の時に，故障した経路情報を

保持していないエージェントが通信によって故障情報 を得ることができるためである．また，通信によって 故障情報を得ることにより，故障衝突回数を少なくし ている．

6 まとめと今後の課題

6.1 _まとめ

本研究では，期待値+A^⋆アルゴリズムと比べて，計 算時間を抑え，経路故障を回避するような経路探索手 法を提案した．提案手法は期待値+A^⋆アルゴリズムと 比べて，経路探索にかかる計算時間を抑えることがで きるだけでなく，避難時間，故障衝突回数はほとんど同 じかより良い結果が出ていることを確認した．ダイクス トラよりも故障を考慮した経路探索である期待値+A^⋆ アルゴリズムと提案手法のほうが故障衝突回数を抑え る事ができた．また，どの結果も通信ありと通信なし では通信ありのほうが早く避難することができた．こ れは通信によって有効な道路故障情報が得られるから である．

6.2 _{今後の課題}

今後の課題として次のことが述べられる．

避難方法の選択：幾つかの避難方法について検討し，避 難行動を採るエージェントの現在地から避難所までの 地形の特徴や避難経路の特徴により，最適な避難方法 を選択するようにする．

通信の効率化：他の DTN ルーティングを適用し，効率 よく経路故障情報を共有できる通信方法を提案する． ユークリッド距離と迂回路の関係：マップの特徴ごとに 提案手法のユークリッド距離が期待値+A^⋆アルゴリズ ムの迂回路の距離とどのくらい近似できているか，ど のような関係があるかを調べる．また，迂回路の近似 をユークリッド距離から算出できるようにする． 避難行動以外の行動をするエージェントの配置：実際 の災害の環境では，災害救助隊や情報通信端末の設置 などで，避難行動以外の行動を取る通信端末を持った エージェントが存在することも想定される．そのよう な環境での有効性を確認する．

参考文献

[1] 藤原明広，他，すれちがい通信を利用した災害時 避難誘導法， 電子情報通信学会論文誌 B， 96， 6， 580–588， 2013.

[2] 社本 峻，他， 災害時の経路探索手法に関する一 考察， 人工知能学会「社会における AI 研究会」， 2013.