〈一般研究課題〉 蟻の生態を利用した災害地における避難ナビ
ゲーション・システムの開発
助 成 研 究 者

大同大学

朝倉宏一

蟻の生態を利用した災害地における避難ナビゲーション・システムの開発
朝倉 宏一（大同大学）An Evacuation Guidance System for Disaster Areas
Based on Ant Colony Systems
Koichi Asakura(Daido University)

Abstract：
This paper proposes an evacuation guidance system for disturbed disaster areas based on ant
colony systems. In this system, evacuees with mobile devices record passed roads and passed time
while evacuating to a shelter. By collecting recorded information, condition of disaster areas,
particularly which roads are passable and can be used for safe evacuation, is recorded in an up-todate manner. For reassembling recorded information, we adapt a concept of pheromones in ant
colony systems. This paper focuses on communication methods for the evacuation guidance systemsince network infrastructure such as access points and base stations may be destroyed ormalfunctioning in disaster areas.

We present three types of communication methods: aninfrastructure method, an ad-hoc method, and a hybrid method. Then, their performances areanalyzed in simulation experiments. From the experimental results, we concluded that the ad-hocmethod is good enough to be an alternative to the infrastructure method when communication
infrastructure has malfunctioned. We also found that the results of the hybrid method werecomparable to the optimal results.
１．はじめに巨大地震などの災害発生時に避難所まで避難するための適切な経路を選択するためには，正しい－ 145 －地図情報が必要となる．現在，Google マップや Yahoo!地図などの地図サイトや，Maps With Meなどの地図アプリケーションが幅広く利用されているが，これらのシステムを災害時の避難に使用するのは必ずしも適切ではない．なぜなら，これらのシステムは基本的に災害などの発生していない通常状態の地図情報を提供しているのみであり，災害地での道路の使用可否などの最新の情報を手に入れることはできない．災害地では，建物の崩壊や道路自体の被害などにより通行できない道路が発生する．このとき，避難所までの最短の経路を使用することは，避難者にとって必ずしも最適であるとは言えない場合がある．
上記の問題に対して，本研究では，蟻の生態を利用して，現在通行可能な道路情報を収集し適切な避難経路を生成する災害地道路地図生成システムを開発する．蟻が移動中にフェロモンを撒きながら移動することで餌と巣の間の最短経路を自律分散的に形成することに着想を得て，避難者が避難行動中にどの経路を通過して避難所まで到達したかを携帯端末を用いて記録し，道路の通過時間や経過時間から，フェロモンの付加・蒸発モデルに基づき現時点で通行できる可能性が高い道路の情報を計算する．フォロモンのモデルを用いることで，多くの避難者が避難経路として使用した道路や最近使用された道路は，現在も使用可能である確率が高い道路だと計算できる．したがって，災害地の流動性にも対応可能な避難経路地図を作成でき，避難者に適切な避難経路を提示することができる．
2．災害地道路地図生成システム
災害地道路地図生成システムは，災害発生時に，避難者の避難誘導のための地図情報を提供するシステムである．本システムでは，避難者自身が災害地の道路状態の情報を収集するモバイル・センサの役割を担う．複数の避難者が避難行動中に収集した道路情報を蟻コロニー・システム（AntColony System）に基づき構成することで，情報の最新性も考慮した災害地道路地図を生成することができる．
2.1 蟻コロニー・システム
蟻は餌を発見し巣に戻るとき，地面にフェロモンを落としながら移動する．これにより，発見した餌と巣の間にフェロモンの軌跡が生成される．蟻は他の蟻などが残したフェロモンに沿って移動する傾向があるので，フェロモンの軌跡があることで容易に餌までたどり着くことができる．巣に帰るときは同様にフェロモンを落としながら移動するので，その結果多くの蟻が移動した経路には多量のフェロモンが残されることとなる．また，フェロモンは揮発性の物質であるので，餌がなくなり蟻がその経路にフェロモンを落とさなくなると，時間が経つにつれてフェロモンが蒸発し，その経路を選択する蟻が少なくなる．この機構により，蟻は餌と巣の間の最短経路を発見することができる．
蟻コロニー・システムは，上記のような蟻の習性に着想を得た群知能アルゴリズムの一種である[1,2]．ネットワーク経路の最短経路を求めたり，故障したルータを回避した経路を求めたりするためのアルゴリズムに利用されている．

－ 146 －

r2

r2

r1

r1

(b) with ant colony systems(a) without ant colony systems
図 1 : 災害地地図の例

2.2 安全な避難地図の生成本研究で提案する災害地道路地図生成システムは，避難者の現在地から避難所までの避難経路を，蟻コロニー・システムのフェロモンの考え方に基づき提示するシステムである．避難者が避難行動中にある道路を移動したとき，システム内ではその道路にフェロモンが仮想的に落とされる．
多くの避難者が避難に使用した道路には多くのフェロモンが残されるので，フェロモンの濃度が高くなる．また，避難者が最近使用した道路はフェロモンがまだ蒸発していないので，同様にフェロモンの濃度が高くなる．したがって，道路に残されているフェロモンの濃度により，多くの避難者が最近使用した道路，すなわち「現在避難に使用できる安全な道路」を識別することができる．
災害地での避難誘導では状況の変化を考慮することが重要である．例えば，ある道路が建物の崩壊などにより途中で通行できなくなった場合を考える．それまでは避難者が使用しフェロモンの濃度が高かったとしても，通行不可能となればそれ以降フェロモンが落とされなくなる．そのため，フェロモンの蒸発によりその道路が避難経路の選択肢から除外されることとなる．
蟻コロニー・システムのフェロモンの考え方に基づいた災害地道路地図の例を図1に示す．図において，中央の丸が避難者の位置を，右下の四角が避難所の位置を表している．図1(a) では蟻コロ
ニー・システムを利用せず避難者が避難行動で使用した道路が太線で示されている．図1(b) では避難者が使用した道路がフェロモン量に基づき濃淡のある太線で表されている．最短経路を求める一
般的な誘導システムや，図1(a) のように他の避難者が使用したか否かの情報だけが得られる場合，避難所までの最短経路を考え，道路r1 を通る経路を選択する可能性が高い．このとき，もし道路r1まで到着したときに通行不可であることが判明した場合，避難者は再度経路を検索して大回りとなる避難経路を使用する必要が生じる．それに対し，図1(b) のようにフェロモン量が考慮されていると，道路r1 のフェロモン量が周辺の道路と比較して少なくなっていることが分かる．この場合，道路r1 は初期には通行可能であったが最近は通行不可となりフェロモンが蒸発しつつある状況，すなわち現在道路r1 は通行不可状態であると判断でき，道路r2 を経由する避難経路を最初から設定可能である．
このように，各避難者がフェロモン情報を収集・蓄積・分配することで，災害地の状況変化にも適応できる現時点で最適な避難経路を生成・提示することがでる．したがって，本研究で提案する
災害地道路地図生成システムを用いることで，避難者が安全に素早く避難所へ避難することが可能となる．

－ 147 －

3．通信方式
このような避難誘導システムを実現するためには，地図情報を共有するための通信方法の検討が重要である．なぜなら巨大地震などが発生した状況では，携帯電話の基地局などの通信インフラは故障したり正しく動作しない可能性があるからである．また，もし通信インフラが故障していなかったとしても，災害発生地の通信状況は不安定であり，正しく情報を共有できない可能性がある．このような状況で注目されている通信技術として，モバイル・アドホック・ネットワーク(Mobile Ad-hoc Network: MANET) がある[3,4]．モバイル・アドホック・ネットワークでは，中央集権的な基地局などの存在を前提とせず，各端末が自律分散的に動作して，通信経路を構築するルータの役目も担う．したがって，基地局やアクセス・ポイントなどの通信インフラが存在しない場所でもネットワークを構築できるので，災害発生時の通信システムとして注目されている[5,6]．
本研究では，以下の四種類の通信方式を設定し，災害地地図情報システムのための最適な通信方式を検討する．
（１） 避
 難者が避難中に取得した通行可能経路や通行不可能経路の情報（災害地情報）を即時的に収集し，即時的に全避難者に共有可能な「理想的通信システム」．
（２） 通 信インフラがある程度利用可能である想定で，避難所に到着した避難者から災害地情報を収集し，他避難者に一定間隔で情報を提供する「インフラ利用型通信システム」．
（３） 通 信インフラが利用不可能である想定で，MANETのみにより災害地情報を共有する「MANET型通信システム」．
（４） インフラ利用型と MANET型の通信システムを組み合わせた「ハイブリッド型通信システム」．
この中で「理想的通信システム」は，すべての情報を即時的に手に入れることのできる，いわゆる神の視点を実現するものであり，現実的には実現できないが最適解を計算できる．したがって，次に続く三種類のシステムの性能評価のための理想解として利用する．
これらの通信方式に基づくシステムを実際に開発し，数百台規模の実験を実施することは不可能である．したがって，本研究では，コンピュータ上のエージェント・シミュレーションによりこれらの通信方式を比較し，最適な通信方式を検討することとする．
3.1 インフラ利用型通信システム
インフラ利用型通信システムでは，各避難者が避難所に到着したとき，避難所においてフェロモン情報を収集する．そして，収集したフェロモン情報に基づいて災害地道路地図を生成し，一定間隔で各避難者に送信する．
各移動端末で蓄積されるフェロモン情報は，通行した道路と通過した時間の組として表される．
<ri, ti>.
避難者が避難所に到着した時間をtnowとすると，フェロモン情報 <ri, ti> から計算される道路 ri の－ 148 －フェロモン量は以下の通りである．
p = max(0, α-β・(tnow - ti)).
ここで，α, βは定数であり，αはフェロモンの初期値，βは蒸発によるフェロモンの減少値を表している．
3.2 MANET型通信システム
MANET型通信システムでは，各端末が収集しているフェロモン情報を定期的に周辺の端末と交換することにより，フェロモン情報を蓄積し災害地道路地図を生成する．この場合，インフラ利用型通信システムのようにフェロモン情報が一箇所に蓄積され単一の地図が生成されるのではなく，各端末が持つフェロモン情報には偏りができ各端末固有の災害地道路地図が生成されることとなる．避難者が移動することにより，間接的に広範囲の端末とフェロモン情報を交換することができ，通信インフラが使用できない状態でもフェロモン情報をある程度拡散させることができる．
通信プロトコルは以下の通りである．
1.

端末は定期的にフェロモン要求 (PREQ) パケットを送信する．

2.

PREQ パケットを受信した隣接端末は，自身の持っているフェロモン情報を含んだフェロモン返信 (PREP) パケットを PREQ パケット送信者宛に送信する．

3.

PREP パケットを受信した端末は，自身のフェロモン情報から PREP パケットに含まれているフェロモン情報を削除したものを含んだフェロモン交換 (PEXG) パケットを PREP パケット送信者宛に送信する．

この通信プロトコルにより定期的に隣接端末とフェロモン情報を交換し，各自の持っているフェロモン情報より災害地道路地図を生成する．フェロモン量の計算アルゴリズムは 3.1 節と同様である．
3.3 ハイブリッド型通信システム
ハイブリッド型通信システムでは，上記二つの通信システムを同時に利用したシステムである．
すなわち，通信インフラを利用して避難所で収集されたフェロモン情報を定期的に受信しつつ，隣接端末間でMANETによりフェロモン情報を交換する．避難所で蓄積された大域的なフェロモン情報と，隣接端末間で交換した局所的なフェロモン情報を融合することにより，災害地道路地図を生成する．
4．評価実験
3章で述べた各通信システムの性能評価のために実施した評価実験について述べる．先に述べたように，実システムを開発して数百台規模の実験を実施することは不可能なので，コンピュータ上のエージェント・シミュレーションにより性能を確認する．そのため，災害地を模したシミュレー－ 149 －

図 2 : シミュレーション範囲

ション・システムを開発した[7]．
実験では，災害地として本学周辺の東西 2000m，南北 1500m の範囲を用いた．シミュレーショ
ンの適用範囲を図2に示す．実験の簡単化のため，本学の位置である図中の黒丸の交差点を避難所として設定した．シミュレーション・システム上の避難者エージェントは各自の災害地道路地図を参照しながら避難所へ移動する．災害地の状況の流動性を考慮するため，シミュレーション開始後5分ごとに地図上の 1% の道路をランダムに選択し，通行不可になるように設定した．
避難者エージェントの数は 500 とし，実験開始時に地図の道路上にランダムに配置される．避難者エージェントのうち 100 エージェントがシミュレーション開始時に即座に避難行動を開始す
る．残りの 400 エージェントはシミュレーション開始時は停止しており，ポアソン分布に従い5秒に1エージェントの割合で避難行動を開始することとした．
シミュレーション実験では，時間の経過と共に何名の避難者が避難所に避難できたかを集計した．3章で述べた各通信システムに対してそれぞれ 10回の実験を実施し，平均値を求めた．
4.1 実験結果
実験結果を図3に示す．グラフの横軸はシミュレーション開始からの経過時間を表しており，単位は「分」である．縦軸は避難所に避難できたエージェントの累積数を表している．“Infra”がインフラ利用型通信システムを，“Ad-hoc”が MANET型通信システムを，“Hybrid”がハイブリッド型通信システムを，それぞれ表している．また，最適解を表す理想的通信システムの結果は“Ideal”の点線で表されている．実験結果より，以下のことが検証できる．
1.

インフラ利用型通信システムの方が，MANET型通信システムよりもよい結果が得られている．しかし，後者は前者の約 90% の性能に達しており，実験開始後約40分までは結果にほとんど差が生じていない．したがって，通信インフラが使用できない状況では，MANET型通信システムで効果的な避難誘導が期待できる．

－ 150 －

InfraAd-hocHybridIdeal

500400300200

10002.

03060
図 3 : 実験結果

90120ハイブリッド型通信システムを用いた場合，一番よい結果が得られている．これはインフラ使用型通信システムと MANET型通信システムから，大域的・局所的な情報を得られるからである．インフラ使用型通信システムで得られた大域的な情報を MANET型通信システムで即時的に共有することで，避難者の避難行動を支援することができる．

3.

ハイブリッド型通信システムは，理想的な結果と比較して，約90〜95% の性能となっている．
したがって，災害地道路地図生成システムにおいて，ハイブリッド型通信システムは最適であると結論づけることができる．

5．おわりに
本研究では，災害地道路地図共有システムのための通信方式について検討した．インフラ利用型通信システム，MANET型通信システム，ハイブリッド型通信システムの三種類を検討し，エージェント・シミュレーションによって性能を評価した．その結果，通信インフラが使用できないよ
うな状況であっても，MANET型通信システムにより効果的な避難誘導が期待できることを確認した．また，通信インフラが使用できる状況であれば，MANETも利用したハイブリッド型通信システムにより，理想的な状況とほぼ同じ性能を得られることを確認した．
今後の課題としては，通信頻度の検討が挙げられる．携帯端末は基本的にバッテリー駆動であり，電池の容量は有限である．特に災害時には，携帯端末のバッテリーはできるだけ消費しないよ1

うにすることが重要である．ハイブリッド型通信システムにより理想的な結果は得られたが，その反面通信負荷が高くなり，バッテリーの消費も激しくなる．したがって，携帯端末間の情報共有のための通信頻度を削減するためのプロトコルの開発や，フェロモン情報を交換するときのデータ量の削減を検討する必要がある．
参考文献
1.	M. Dorigo and T. Stutzle:“Ant Colony Optimization”, Bradford Company, P.305 (2004).

－ 151 －2.	C. Blum:“Ant Colony Optimization: Introduction and Recent Trends”, Physics of Life Reviews,
Vol. 2, No. 4, pp. 353-373 (2005).
3.	C-K. Toh:“Ad Hoc Mobile Wireless Networks: Protocols and Systems”, Prentice Hall, P.324(2001).
4.	C.S.R. Murthy and B.S. Manoj:“Ad Hoc Wireless Networks: Architectures and Protocols”,
Prentice Hall, P.857 (2004).
5.	S.F. Midkiff and C.W. Bostian:“Rapidly-deployable Broadband Wireless Networks for Disasterand Emergency Response”, the 1st IEEE Workshop on Disaster Recovery Networks (2002).
6.	A. Meissner, T. Luckenbach, T. Risse, T. Kirste and H. Kirchner:“Design Challenges for an
Integrated Disaster Management Communication and Information System”, the 1 st IEEE
Workshop on Disaster Recovery Networks (2002).
7.	K. Asakura and T. Watanabe:“A Simulation System of Disaster Areas for Evaluating
Communication Systems”, the 2 nd International Symposium on Intelligent Decision
Technologies, pp. 495-506 (2010).

－ 152 －