電気通信大学の山本教授らが「粘菌アルゴリズム」による避難経路探索手法を開発：「ダイクストラ法よりも優位性を確認」

電気通信大学の教授である山本佳世子氏らのグループは、粘菌アルゴリズムを用いて複数の避難場所への複数の避難経路を同時に導出する手法を開発した。ダイクストラ法で求めた経路と比べて、同手法が優位であることを確認した。

[＠IT]

　電気通信大学大学院情報理工学研究科の教授である山本佳世子氏と東京都産業技術研究センターの研究員である吉次なぎ氏らのグループは2019年12月17日、粘菌アルゴリズムを用いて複数の避難場所への複数の避難経路を同時に導出する手法を開発したと発表した。

　主要な経路探索手法の一つであるダイクストラ法によって導出した避難経路と比較して「追加計算不要で避難成功率の高い避難経路を導出できる」「複数の避難経路が得られる」「少ない計算時間でより効果的に避難経路を求められる」という3点について優位性を確認したとしている。

粘菌アルゴリズムで避難経路を算出

　粘菌アルゴリズムとは、真正粘菌（変形菌）の動作に着想を得たアルゴリズム。変形菌は、細胞体内に形成した輸送管を通して変形体（菌が移動する際の形態）の往復流動を行い、「輸送管ネットワーク」を動的に形成する。この性質によって、例えば「えさを採るとき」など目的の場所に移動する際に、最短経路をとれる。これを応用すると、迷路の解を得られるという。

　山本氏らのグループは、経路探索の対象となる道路網と、粘菌の輸送管ネットワークを関連付けした。道路は「リンク」、交差点は「ノード」、有効者（経路をたどる人）を「原形質」（細胞膜の内側の物質）とみなした。道路と粘菌アルゴリズムの各変数の関係については、通行可能性を「コンダクタンス」（流れやすさ）、道路長は「管長」、優先度は「流量」、始点と終点は「原形質の流出入点」と解釈した。これによって、原形質の流出入点を結ぶ輸送管の流量を求めることで、避難経路としての優先度を比較できる。

手法の概略（出典：電気通信大学）

　研究グループは開発した手法の妥当性を検証するために、東京都足立区のJR北千住駅周辺を対象とし、ダイクストラ法と比較した。JR北千住駅周辺は、河川に挟まれており、災害危険度が高いとされている。同地域の道路網は、国土地理院発行の数値地図から抽出した。

避難場所の収容人数や安全性を考慮した計算が可能

　避難経路を導出する条件は以下の通り。

1. 道路長のみを考慮して避難経路を1つ求める
2. 2つの避難場所へ向かう、それぞれの避難経路を求める
3. 優先度の高い順に，避難場所に向かう2つの避難経路を同時に求める
4. 途中の道路が通行不可能な場合でも、再計算なしで迂回（うかい）路を求める

計算結果（出典：電気通信大学）

　道路長のみを考慮して避難経路を1つ求めたときは、研究グループの手法で求めた避難経路とダイクストラ法による最短経路が一致した。

　避難終了地点を2つ設定し、1つの避難開始地点から、各避難終了地点までの優先度の最も高い避難経路を求めた場合、研究グループの手法で2つの避難経路を同時に導き出せた。これは、流出量比を任意に設定することで、避難場所の収容人数や安全性を考慮した計算が可能であることを意味する。

　避難開始地点と避難終了地点を1つずつ設定して、2つの避難経路を求めたときでも2つを同時に導けた。従って、追加計算なしに避難経路を任意の数だけ同時に求められる。さらに、途中の道路が通行不可能だと設定したときでも、再計算なしに迂回路を求められた。

　研究グループは、災害危険度や道路の勾配、傾斜、段差の有無といった情報を考慮して、通行可能性を表すコンダクタンスの値を変化させることで、精度を向上させることが可能だとしている。

　災害時には、複数の避難経路候補から定量的根拠に基づいて避難経路を選択することが重要だ。従来の経路検索アルゴリズムでは、始点と終点を結ぶ最短経路を求めることしかできず、複数の避難場所に向かう複数の避難経路の優先度を追加計算なしに定量的に比較することは不可能だった。