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

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

[＠IT]

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

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

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

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

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

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

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

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

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

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