kou Recent site activity jsaisigsai

危険回避を考慮した ^Hyperstar アルゴリズムによる経路探索の

輻輳低減について

Lowering the congestion of risk-avoding paths using Hyperstar

algorithms

黄 浦

泉 泰介

伊藤 暢浩

岩田 員典

HUANG PU

TISUKE IZUMI

NOBUHIRO ITO

KAZUNORI IWATA

1

_{名古屋工業大学}

1

Nagoya Institute of Technology

2

_{愛知工業大学}

2

Aichi Institute of Technology

1

_愛知大学

Aichi University

Abstract: 災害時の危険回避を考慮した経路探索は重要な課題である．既存研究では，唯一の最短 経路を求めるため，災害時に大人数が避難する場合には，輻輳が生じる可能性が高い．そこで本論文 は輻輳を低減するために，複数の最適経路を探索できる HyperStar アルゴリズムと既存手法を融合 する方法を提案した．エージェントの総合移動時間コストについて，災害救助シミュレーションを用 いて，既存手法と改善手法を比較し，その有効性を確認した

1 _はじめに

近年, 世界各地で大規模な地震災害が頻発している. 特に,2011 年 3 月 11 日に発生した東北地方太平洋地震 では, 東北から関東にかけて大きな被害を引き起こした ことは記憶に新しい.

このような大規模な自然災害に対として，現在さま ざまな取り組みが行なわれている. その取り組みにはさ まざまな研究課題が含まれており, その中のひとつに災 害環境下の経路探索問題がある. 特に被災者を安全な 場所まで, できる限り短時間で安全に避難させるための 経路探索は重要な課題である. 東京, 大阪などの大都市 部における大規模災害では, 特に大量の人が一度に避難 をすることが考えられ, これらの人々をできるだけ安全 に避難場所まで短時間で誘導しなければならない．

経路探索問題の既存研究として,A^∗アルゴリズム [1], ダイクストラ法 [3] と AdaptiveA^∗アルゴリズム [2] な どが知られている．これらのアルゴリズムはグラフネッ トワーク上の 2 つのノード間の最短経路を探索するア ルゴリズムである. これらの既存アルゴリズムは, 基本 的にはただ 1 つの最短経路を探し, 経路計算時間を短く することを重視している. しかし, 災害救助活動や避難

∗連絡先： 名古屋工業大学大学院 情報工学専攻       〒 466-8555 愛知県名古屋市昭和区御器所町        E-mail: hiper.hp@hotmail.com

のための経路探索では, 道路に障害が発生する可能性 があり, 道路が全て使えるとは限らない. すなわち, 環境

（道路情報）に関する事前知識が正確でなくなっている ことを想定しなければならない. 一方で, 平常時での周 辺環境調査等により災害時における環境変化について ある程度の予想が可能であると仮定することは妥当で あると考えられる. よって, 災害時における移動計画に おいては, これらの不確実性と予想可能性を考慮して経 路選択をすることが望ましい. また, 計算時間そのもの よりも, 目的地へ到達するまでの時間を短くすることが 重要となる. そのため, 移動時間に比例する総移動コス トも重要となる.

社本ら [4] は, 確率的な障害が発生することを想定し, より効率よく目的地まで移動するために, 道路にどれ くらいの確率で障害が発生するかを示す「障害発生率」 と, 最短経路群に障害があったときの代替経路である

「迂回経路」を利用することを考慮した災害救助に向け る新しい評価関数を A^∗アルゴリズムに導入した. 具体 的には，既存の A^∗アルゴリズムの評価関数の代わり に, 障害による経路の封鎖確率, および迂回経路への切 り替え容易性を考慮した新しい評価関数を提案した. し かし, この方法は, 大量の人が同時に移動することを考 慮していないため, 最適な 1 つ経路探索を提供するた め, この経路に従って大量の人が移動すると深刻な輻輳

状態が, 被災地において生じることが考えられる. 本論文では, その輻輳をできる限り低減するため, 最 適経路群を利用して避難者を分散することにより, 輻輳 を減少することを考える.

最適経路群を探索するアルゴリズムの既存研究とし て,k-最短経路アルゴリズム [5] と HyperStar アルゴリ ズム [6] などが知られている. それらは, 最短経路を含 め, 候補最短経路も探索するアルゴリズムである. 2009 年に Bell らによって提案された HyperStar アルゴリ ズムは複数の経路を 1 回の計算で探索でき, 経路群の探 索時間を大幅に削減した. 本論文では, 社本らが提案し た評価関数を HyperStar アルゴリズムに融合して, 確 率的障害が発生する環境下で，大量の人が一度に避難 する場合に起こりやすい輻輳を低減することを目的と した, 新しい HyperStar アルゴリズムを提案した. ま た, エージェントシミュレーション上で, 社本らが提案 した評価関数を HyperStar アルゴリズムとエージェン トの総合移動時間コストの方を比較して, 提案したアル ゴリズムの有効性について評価した.

2 諸定義

ここでは災害救助向けの経路探索問題に通用するデー タ構造などの定義をおこなう．

グラフ

経路探索がおこなわれる重み付きグラフ G を以 下のように定義する．

• G = (V, E, C)

ここで V はノードの集合であり，E はノードと ノードをつなぐ辺の集合である．今，ノードの数 と辺の数をそれぞれ |V | = n，|E| = m とすると， V と E を次のように表現できる．

• V = {1, 2, . . . , n}

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

また，特にノード i，j 間の辺を ei,jと表現する ことにする．このとき，任意のノード i, j ∈ V に ついて ei,jと ej,iを同一視し，また ei,jはただ 1 つに定まるとする．

また辺にコストを与える関数 C を以下のように 定義する．

• C : E → R+

ここで，コストとは辺 ei,j上に輻輳無い状態の移 動時間であり. 辺 ei,jに与えられたコスト ce_i,jは ci,jと略記する．

輻輳コスト

ノード i の隣接点 j までの辺 ei,j(道路) 上に, 混 雑の状況になって通れない場合に, その通れない 状態から通れる状態まで掛かる時間を輻輳コスト と呼ぶ.

また, 辺に輻輳コストを与える関数 D を以下のよ うに定義する．

• D : E → R+

 ここで, 辺 ei,jに与えられた輻輳コスト De_i,j

は di,jと略記する． 経路

辺 ei,jに対して，vertex(ei,j) = {i, j}と書くと き，辺 e1, e2, ..., ek ∈ E(k ≥ 1)の各 i = {1, 2, ..., k− 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 への経路という． 移動コスト

経路 (e1,2,e2,3,...,ei,j) 上に, 移動する時に, かか る総合時間は移動コストと呼ぶ. 総合時間は経路 内の各道路のコストと各道路の輻輳コストの和で ある. 但し, 各道路に輻輳が発生するかどうかを 判断して．発生しない道路の輻輳コストを 0 とす る. 具体的に以下のように示す：

• c1,2+d1,2+c2,3+d2,3+...+c_(k−1),k+d_(k−1),k ,1 ≤ k ≤ n

道路容量

各道路に輻輳を発生するかどうかを判断するた め, 各道路に容量を定義する. また, 辺に容量を与 える関数 K を以下のように定義する.

•   K : E → R+

ここで, 辺 ei,jに与えられた道路容量 Ke_i,jは ki,j

と略記する．また, 本論文では, ノード i の隣接 点 j までの道路を道路容量の 1.5 倍の移動体が通 行しようとしたとき, 輻輳が発生する [8]. 本論文 で扱う道路の容量はシミュレーション開始時点で 決定され, シミュレーション中に増減することは ない.

最短経路及び最適経路 (群)

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

• ノード i からノード j までの全ての経路の 中で，経路の輻輳時間無し移動コストが最 小のもの．また，輻輳時間ありの移動コス トが最小のものが最適経路であり，最適経 路で組合わせた経路群は最適経路群である． また，最短経路のコストを最短コストと呼ぶ． エージェント

探索を開始するノード (開始ノード) から目的地 となるノード (目的地ノード) へ移動する対象を エージェントと呼ぶ．

エージェント分配率

最適経路群の各辺 ei,jに特定な分配率を与える. 各エージェントはこの分配率に従って移動する. 辺に分配率を与える関数 P を以下のように定義 する．

• P : E → R+

ここで, 辺 ei,jに与えられた分配率 Pei,jは pi,jと 略記する．

障害情報

辺に問題が発生し，エージェントが通過できない 状態を，辺に障害が有るという．また各辺の障害 の有無に関する情報を障害情報と呼ぶ． 迂回経路

最短経路上のある辺が障害により通行不可能であ ると仮定したときの (次善の）最短経路を迂回経 路と呼ぶ．

頂点 i から j への経路を pi,j，頂点 i から j への 経路集合を P ath(i, j) とし，既知である障害によ り通行不能である辺を f，そのような辺の集合を Fとする．頂点 i から j への障害のある辺を通ら ない経路の集合 D は次のように記述できる．

• D(i, j) = {di,j|di,j∈ P ath(i, j), ∀f ̸∈ di,j} ノード i 及び j に関して，d ∈ D(i, j) かつ ∀d^′ ∈ D(i, j) で C(d) ≤ C(d^′)であるとき，d をノー ド i から j への迂回経路と呼ぶ．またこのときの C(d)を迂回経路コストと呼ぶ．

3 関連研究

3.1 A

_{アルゴリズム}

A^∗アルゴリズム [1] では，開始ノードから目的地ノー ドへ至る最短コストの推定値に基づいて経路探索を進 める．

ここでで最短コストの推定値について説明をおこな う．探索経路上にあるノードを v とする．開始ノード からノード v を通り，目的地ノードまで至る経路の最 短コスト f(v) は，以下のように表わされる．

f (v) = g(v) + h(v)

ここで，g(v) と h(v) は以下のような意味である．

• g(v):開始ノードからノード v までの最短コスト

• h(v):ノード v から目的地ノードまでの最短コスト 探索がノード v まで進んだ場合を考えると，開始ノー ドからノード v までの最短コスト g(v) は求められてい るが，h(v) は探索を進めていかなければ求めることが できない．そこで h(v) には推定値として ˆh(v) を用い て，開始ノードからノード v を通り目的地ノードへ至 る最短コストの推定値を以下のように表す．

f (v) = g(v) + ˆˆ h(v)

A^∗アルゴリズムでは，現在経路探索が進んでいるノー ドから次の経路となるノードを選択するときに，候補 となるノードについて ˆf の値を求め， ˆfの値が最小に なるノードを経路として選択することで経路探索を進 める．代表的な ˆh の値としては，目的地までのユーク リッド距離などがある．

これにより，経路の全探索をせずに短い計算時間で 目的地ノードまでの最適経路を探索することができる． しかし，障害が発生することを考慮していない．その ため，地震災害等で道路に障害が発生した場合，総移 動コストが大きくなってしまう．

3.2 確率障害を考慮した A

アルゴリズム

既存の A^∗アルゴリズムとその関連研究では入力グラ フに移動障害が発生することを考慮していない場合が 多い. そこで, 推定値 h の計算を改良して, 確率的な障害 発生を考慮して A^∗アルゴリズムの改良をおこなった. このアルゴリズムでは与えられる地図であるグラフに 災害発生によって通行が出来なくなる確率（以下，障 害確率と呼ぶ）を追加し, その障害確率と迂回経路への 切り替えの容易性を考慮した期待値 h´ を利用する . こ の手法によって効果的に障害を回避することで目的地 までの移動コストに関して, 建物の倒壊や液状化現象な どが起きにくい地域では,A^∗アルゴリズムとあまり変

わらない結果が得られた. そして, 建物の倒壊や液状化 現象などが起きやすい地域では,A^∗アルゴリズムより も優れた結果を得た. 本論文では便宜上, 確率的な障害 発生を考慮したこのアルゴリズムを障害 A^∗アルゴリ ズムと呼ぶ. また, 詳細については次章で説明する.

3.3 HyperStar _{アルゴリズム}

HyperStarアルゴリズムは,SpiessandF lorida アル ゴリズム [7] に基づいて最適経路群を 1 回の計算で探 索するアルゴリズムである.SpiessandF lorida アルゴ リズムは, 鉄道の駅での待ち時間の不確実性を考慮した 複数の乗車戦略を計算するものである. すなわち, 頻度 べース (時刻表) で運行されている公共交通機関におけ る目的地に乗り場を共有している複数の路線を用いて 到達することが可能な場合, それらの路線から魅力的な 路線集合 (attractiveset) を選択するアルゴリズムであ る.SpeissandF lorida アルゴリズムは以下の仮定の基 で目的地まで到着する期待所要時間が最小となる路線 集合を魅力的な路線集合とする.

1. 路線は頻度ベースに基づいて運行されているため 乗客に期待待ち時間が発生する

2. 乗客はランダムに出発駅に到着し, 最初に到着し た路線に乗車する

そして,HyperStar アルゴリズムは, 鉄道交通機関と交 通網の違いを考慮して, 頻度べース (時刻表) を交通網 上の渋滞とみなし及び魅力的な路線集合を最適経路群 HyperP athとみなした. また, アルゴリズムの計算時 間を高速化するために,A^∗アルゴリズムと同じように, 推定値を利用して最適経路群 HyperP ath を探索する. 詳細なアルゴリズム手順は次章で説明する.

3.4 _{関連研究との相違点}

本章では, 経路探索と経路群探索の既存手法について 説明した. 既存の経路探索アルゴリズムでは計算時間の 短縮を目的としており, 経路障害の回避を考慮したもの はほとんどない. また, 障害を考慮していても輻輳は考 慮していない. また, 輻輳を考慮し経路群を求めるアル ゴリズムでは障害の発生については考えていない．そ こで, 次章では確率的に発生する障害を回避し, 輻輳を 考慮することで最終目的地までの総移動コストを減少 するアルゴリズムを提案する.

4 _問題設定

本論文では，経路探索がおこなわれる重み付きグラ フ G^′を以下のように定義する．

• G^′ = (V, E, C, K, D, P, B)

V, E, C, K, D, P は諸定義と同じものである．

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

• B : E→ R⁺

ここで，辺 ei,jに与えられた障害発生率は bi,jとする． 本論文で扱う経路障害はシミュレーション開始時に,「障 害発生率」に基づいて各辺に発生する. これ以降, 経路 障害が発生した辺を障害辺と呼ぶ. また, 経路障害はシ ミュレーション開始時点で決定され, シミュレーション 中に増減することはない. 分配率 pe_i,jはシミュレーショ ン開始時には, 各辺で 0 とする. シミュレーションが開 始され, 経路探索アルゴリズムが終了した時点で, 各辺 に設定される. なお, 再探索した際には再設定される.

本論文では，経路探索をおこなうエージェントの動 作を以下のように定義する．

• エージェントは，与えられたアルゴリズムにした がって，移動先ノードを決定する．

• エージェントは，障害辺に接続しているノードに 到達するまで，経路障害を発見できない．

• 初期状態では，エージェントはグラフおよび障害 発生率の情報を持つが経路障害の情報は持たない．

4.1 障害 A

アルゴリズム

 基本は,A^∗アルゴリズムと同じである. ただし,A^∗ アルゴリズムの推定値 h(ここではノード p の推定値は h(p))を評価する手法を改良している. ここでは, ノー ド p から目的地までの最短経路は (e1,2, e2,3, ..., ei,j)と する. 具体的な評価手法は以下のようになる.

1. ノード p から目的地までの最短コストを計算する． 2. 最短コストで目的地へ到達できる確率を計算する. 3. 最短経路が (1，2，3，．．．，k) で表される場合，各 ノード i において (i，i + 1) が通れないと仮定し た場合の最短コスト（迂回経路長）を計算する． 4. 3を基に b_1，2×ノード 1 の迂回経路長 +(1−b_1，2)

× b_2，3×ノード 2 の迂回経路長 +(1−b_1，2)× (1− b_2，3)× b_3，4×ノード 3 の迂回経路長 +．．．を計 算する．

5. (1と 2 の積) と 4 の和を h^′(p)とする．

4.2 HyperStar _{アルゴリズム}

Bellらは公共交通機関の特性と交通ネットワークを 融合した HyperStar アルゴリズムを提案した．このア ルゴリズムでは電車などの待ち時間を交通ネットワー クの渋滞時間とみなし A^∗アルゴリズムの推定値を用 いることで，輻輳時間コストを減少できる最適経路群 を提案している．アルゴリズムの流れは以下に示す．

まず，アルゴリズムに関するいくつかのパラメータ を説明する：

• f_i，j:辺 ei，jのサービス頻率．サービス頻率とは輻 輳コストを基にした利用可能性を意味する．fi= 1/d_i，j，d_i，j=0の時，f_i，jは無限大とする．

• fi:ノード i のサービス頻率．初期値は 0 とする．

• β:グラフ内の辺 e_i，jに対して，もしノード i まで 期待最小移動コスト Ui= ∞かつ fi= 0ならば， β← 1，それ以外 β ← fi× Uiとする．

開始する際に，開始ノード r とし，目的ノードは s を する．アルゴリズムを開始する際，処理ノードを j，目 的ノード s とする．

1. 処理ノード j から隣接している各ノードの目的 ノードまでの推定値 ˆh を計算する．

2. 処理ノード j に入る各辺を openList に入れる． 3. openList中の辺 ei，jに対して，推定値 ˆhi+ Uj+ c_i，j が最小の辺を候補辺 e^′_i，j とし，点 i を候補 ノードとする．

4. ステップ 3 において，もし辺 e^′_i，j が Ui ≥ ˆhi+ Uj+ c_i，jを満たすなら，β の値を定める．満た さない場合はステップ 8 に行く．

5. 式 Ui← (β +f_i，j× (Uj+c_i，j))/(fi+f_i，j)と式 fi

← fi + f_i，jにより，Uiと fiを更新し，辺 e^′_i，jは 集合 H に入れ，openList から辺 e^′_i，jを削除する． 6. もし openList が空になるか，ˆhi+ Uj+ c_i，j > Ur

ならば，次のステップに入る．満たさない場合は またステップ 2 に戻って処理を繰り返す． 7. 集合 E の中の辺 e_a，bを ˆha+Ub+c_a，bの値の大き

い順に順位つけて，もし辺 e_a，bは集合 H の中の 辺であれば，pa，b← (fa，b/fb)Yb，Ya← Ya+ pa，b

として，辺 e_a，bの選択率 ˆp_a，bを計算する，そう ではなければ，ˆp_a，bは 0 にする．

8. 集合 H の中の辺 e_t，lに対して，分配率 p_t，lが 0 ではない経路で組合わせた経路集合を最適経路群 HyperP athとして出力する．

4.3 _{既存研究との相違点}

障害 A^∗では，現実のように避難人数が多数になる 場合は，1 つ最短経路に従って全員が避難するため，輻 輳が発生する可能性が高い．一方，HyperStar アルゴ リズムは最適経路群を利用して避難者を分散する手法 はそのまま災害救助に適用しても経路群の中に通行で きない経路が含まれる可能性が高い．

そこで，本論文では危険回避を考慮した経路探索手 法に HyperStar アルゴリズムを適用する．

4.4 _適用方法

基本は HyperStar アルゴリズムだが，HyperStar アルゴリズムと違うところを以下に示す．

• HyperStarアルゴリズムに用いた推定値 ˆh を確 率的な障害を考慮した A^∗アルゴリズムで提案し た評価関数 h^′(p)を使う．

• HyperStarアルゴリズムに用いた輻輳無し移動 コスト c_i，jを，式 ˆc_i，j = (1 − b_i，j)× c_i，jによ り変更する．

• HyperStarアルゴリズムで得られる最適経路集 合 HyperP ath 中の辺の選択確率をエージェント の分配率 p_i，jとして利用する．

4.5 _動作例

提案手法の動作例を Fig.1 を使って説明する．経路 探索の開始ノードはノード 8, 目的地はノード 7 である． また，ここでは各辺の移動コスト, 道路容量および輻輳 コストを全て 1 としており，各辺の左側に書かれてい る数字はその辺の障害発生率である.

図 1: 動作例

1. ノード 7 に入る辺 (3,7),(0,7) について A^∗アル ゴリズムの推定値の計算方法により h^′(v)を求 め,h^′(v) + u7+ ˆcv,7の値を求める. ここでは, 辺 (3,7)は 3.02+1+0 =4.02, 辺 (0,7) は 4.19 である. そして, ２つとも openList に入れて openList 中 に最も小さい辺 (3,7) を選択する. ノード 3 の u3

を更新する, ここでは 2 である. そして,f3も更新 する, ここでは 1 である. 辺 (3,7) を H 集合に入 れる.

2. 次は, ノード 3 に入る辺 (6,3) と (4,3) について h^′(v) + u3+ ˆcv,3を計算し, ステップ 1 と同じよう に, 辺 (6,3) と辺 (4,3) を openList に入れて open- Listの中に最も小さい辺 (4,3) を選択し,u4と f4

を更新し, 辺 (4,3) を H 集合に入れる.

3. ステップ 1 とステップ 2 のように操作を繰り返し て, 辺 (9,10) は h^′(9) + u10+ ˆc9,10 > u8ので, 経 路選択を終了する

4. グラフの各辺 (i,j) に対して,h^′(i) + uj+ ˆci,jの値 により大きい順に順位をつけて, もし辺 (i,j) は H 集合の中におるならば, ステップ 5 に入る 5. 式 p_i，j← (f_i，j/fj)Yj，Yi← Yi+ p_i，j により, 辺

(i,j)の分配率を計算する

6. 分配率が 0 ではない辺を最適経路群 (HyperP ath) として出力する, 計算より得られた経路群の図は Fig.2に示す

図 2: 出力した経路群

5 実験

5.1 実験シミュレーションと理論値

本論文で障害 A*アルゴリズムと提案手法をシミュ レーションによって比較する. シミュレーションの流れ を以下に示す.

1. サーバエージェントは経路探索アルゴリズムを利 用して, 最適経路 (最適経路群) を計算する. そし て, 避難エージェントに最適経路を送信する 2. 避難エージェント達は最適経路を受け取り, 最適

経路に従って同時に移動を開始する

3. 避難エージェントはこれから移動しようとする辺 に障害を発見した場合，それをサーバエージェン トに送信する，障害を発見しなかった場合は 6 に いく

4. サーバーエージェントは避難エージェントから障 害に関する情報が届いた場合に, 迂回経路を計算 する. 迂回経路は, 避難エージェントの現在点を 開始ノードとおき, 障害が起きた経路の末端を目 的ノードとし,Dijkstra アルゴリズムにより計算 する. そして, 避難エージェントに迂回経路を送信 する

5. 避難エージェントは迂回経路に従って, 災害が起 きた経路を迂回し, また, もとの経路に戻って移動 を続ける

6. 各辺に移動する予定のエージェント数を計算し て, 輻輳が発生する条件を満たすかどうかを確認 する. 輻輳の発生が確認できた場合は, 辺のコス トに輻輳コストを加えた値がその辺に対する移動 コストとなる

7. 全避難エージェントが目的ノードにたどり着いた ら, 全避難エージェントの移動コストの和を総合 移動コストとする．総合移動コストを出力する そして, シミュレーションの中に, 最初から全ての障害情 報を持っている状態で計算した最短経路において輻輳 発生しないと仮定した際の総合コストを理論値と呼ぶ.

5.2 _実験環境

実験には 1 台の計算機を使用した．計算機の実験環境 は表 1 の通りである．また，プログラム言語には C++ を使用し，コンパイラには Visual Stdio 2010 を使用 した．

表 1: 実験環境 OS Windos7

CPU Intel(R) Core(TM) i5-2430M CPU 2.40GHz 2.40GHz Memory 4.00GB

5.3 確認実験

5.3.1 確認実験内容

提案手法が障害 A^∗アルゴリズムに比べて，総移動 コストが小さくなるかどうかを簡単な入力グラフで確 認する. 確認実験に使用した入力グラフを Fig.3 に示し. また, 提案手法は経路選択際, 障害 A^∗とどのように違 うを確認するため, グラフのパラメータを改造した. 詳 細は以下の通りである.

• 各辺の di,jは 4 とする. 但し, 提案手法と障害 A^∗ は輻輳回避に関する比較のため, ノード 17 とノー ド 12 及びノード 12 とノード 7 の間 di,jは 10 と する.

• 各辺の道路容量 ki,jは 4 とする.

全エージェントの開始ノードは 20 と目的地ノードは 4,また, 開始するタイミングも同一ものとする．実験は 100回を行う.

図 3: 確認実験用地図 5.3.2 確認実験結果

エージェントの総合移動コストの平均・標準偏差お よび平均衝突回数を表 2 のように示す.

5.3.3 確認実験結果の考察

確認実験の結果により, 提案手法の方が総移動コス トを低減できることがわかる. この環境下では, 単一の

表 2: 確認実験の平均・標準偏差と平均衝突回数 平均値 標準偏差 平均衝突回数 障害 A^∗ 397.12 27.11 0.16 提案手法 243.72 30.82 0.21

最短経路を用いると, 各辺にほぼ輻輳が発生する. した がって, 障害 A^∗アルゴリズムでは各辺の輻輳コストを 考慮してないために, 移動コストが低いが輻輳コストが 高い辺 (12,17) 及び (12,7) を選択してしまう. 一方, 提 案手法は輻輳コストを考慮した上に, 障害発生確率が低 いリンクを選択するため, 輻輳及び障害を回避ことがで きた. その結果, エージェントの総移動コストを低減す ることができた. そこで, 次節から実際の地図データか ら生成したグラフでも, 効果があるかどうかを確認する.

5.4 _応用実験

応用例として，実際の地図データから生成したグラ フでも効果があるかどうか確認する．本論文では，国 土地理院の発行している 2003 年度版地図データから入 力グラフ G′ = (V, E, F, B) を生成した. ここでは,V は 交差点の集合.E は交差点を繋ぐ道路の集合,F は交差 点と交差点の距離の集合,B は道路の障害発生率とした. また, 道路の障害発生率は名古屋市が発行している「あ なたの街の地震マップ」の液状化危険度を基に設定し た. 各応用実験の詳細を表に示す. また, 各道路の輻輳コ スト及び道路容量は道路の距離, 道路の平均流量および 道路の幅などいろいろな要素と関係があるが, 本論文で 扱う問題の設定を正確に定義できる資料の入手が困難 であるため，輻輳コストを単純化して扱うことにする. 次節に, その単純化の詳細を述べる. また, 本論文では, 道路の移動時間は道路の距離と比例するものとする. 扱 うシミュレータ上の避難エージェントの平均移動速度 vは定数 v = 1m/s とする. すなわち, 各道路のコスト

=(道路の距離/平均移動速度) とする. また, 全エージェ ントで開始ノードと目的地ノードは同一とし, 開始する タイミングも同じものとする.

5.4.1 応用実験の説明

本論文で扱うシミュレーションは道路の輻輳コスト を単純化したので, 現実の場合にできる限り近づけため に, 入手可能な各道路のコスト ci,j を基づいて各道路の 輻輳コストを式 di,j = 1.5× ci,j− r(rは 0 から 10 ま で乱整数) を用いて計算し, 輻輳コストが定数として実 験を行う. 具体的に以下のように定める：

• ci,jは 200 より長い場合は,ki,jは 10 とする.

• ci,jは 100 と 200 の間の場合は,ki,jは 7 とする.

• ci,jは 50 と 100 の間の場合は,ki,jは 5 とする.

• ci,jは 10 と 50 の間の場合は,ki,jは 4 とする.

• ci,jは 0 と 10 の間の場合は,ki,jは 2 とする. 各応用実験地図は名古屋市昭和区と名古屋市中村区 を使用した．各実験の開始ノードと目的ノードをラン ダム的に選択し, 各 100 回を行う. 各応用実験の詳細は 表 3 に示す.

表 3: 各応用実験の設定

地図 開始ノード 目的ノード 応用実験 1 昭和区 100 1000 応用実験 2 中村区 10 1500

5.4.2 応用実験結果 1

エージェントの総合移動コストの平均・標準偏差お よび平均衝突回数を表 4 のように示す.

表 4: 確認実験の平均・標準偏差と平均衝突回数 平均値 標準偏差 平均衝突回数 障害 A^∗ 35,000.55 199.28 2.46 提案手法 30,584.45 147.12 3.34 理論値 24,970.00 - 0

5.4.3 応用実験結果 2

エージェントの総合移動コストの平均・標準偏差お よび平均衝突回数を表 5 のように示す.

表 5: 確認実験の平均・標準偏差と平均衝突回数 平均値 標準偏差 平均衝突回数 障害 A^∗ 39,267.64 345.41 3.52 提案手法 31,501.86 321.19 4.90 理論値 28,140.00 - 0

5.5 応用実験の考察

応用実験の結果より，提案手法の総移動コストが A^∗ アルゴリズムの総移動コストより小さくなることがわ かった．障害 A^∗ は 1 つの最短経路を計算するため， エージェントは輻輳状態になることが多い，一方，提 案手法は最適経路群により，避難エージェントを分散 したため，輻輳状態になることが少ないことがわかっ た．また，提案手法は平均衝突回数について障害 A^∗ア ルゴリズムよりやや多いが，障害発生率が相対的に高 いところを避けられることも分かった. すなわち, 障害 A^∗アルゴリズムと同じように危険回避を考慮して経路 群を生成し，途中で障害と遭遇する可能性が減少して いるといえる．従って，提案手法は確率的な障害の下 で，有効であると考えられる．

6 今後の課題

6.1 他の経路群を探索する手法との比較

本論文で扱った最適経路群を探索するアルゴリズム は HyperStar アルゴリズムだけであるが, 他の経路群 も利用できる可能性がある. したがって, 他の経路群を 使う方法との比較などが必要となる．

6.2 現実に近い輻輳コストの導入

本論文で扱った輻輳コストは単純化したが, 現実の輻 輳コストはもっと複雑である. エージェントの移動速度 や, 道路の幅や, 及び平均交通量などと関係があるので ,それらを観慮したその輻輳コストをより現実に近い条 件で実験することが必要であると考えられ.

参考文献

[1] P.E.Hart,N.J.Nilsson,B.Raphael: A formal basis for the heuristic determination of minimum cost paths, Systems Science and Cybernetics,Vol. 4, No. 2, pp. 100–107 (1986)

[2] S.Koenig,M.Likhachev: A new principle for in- cremental heuristic search:Theoretical results, Proceedings of the International Conference on Automated Planning and Scheduling,pp. 410–413 (2006)

[3] E.W.Dijkstra: A note on two problems in connexion with graphs, Numerische Mathe- matik,pp. 269–271 (1959)

[4] 名古屋工業大学大学院 情報工学専攻 社本 峻: 確率 的な障害の下でマルチエージェント経路探索手法 について, 名古屋工業大学大学院 修士論文 (2013) [5] Eppstein: Finding the k-shortest paths, SIAM Journal of Computing,Vol. 28, No. 2.pp. 652–673 (1998)

[6] Michael G．H．Bell: Hyperstar:A multi-path As- tar algorithm for risk averse vehicle navigation, Transportation Research,Part B, No. 43.pp. 97– 107 (2009)

[7] Spiess H.,Florian M.: Optimal strategies: a new assignment model for transit networks, Transportation Research,Part B,Vol. 2,.pp. 83– 102 (1989)

[8] HuaPu Lu: Theory and Method in Transporta- tion Planning, Second Edition(1998)