「粘菌アルゴリズム」とは？　避難経路を粘菌から学ぶスゴ技

「粘菌アルゴリズム」は、組み合わせ最適化問題を高速化する日本発の最新アルゴリズム

　大地震などで緊急避難が必要なとき、最も早く避難場所や施設に到着できる経路を探すのは死活問題。地域ごとに大抵は複数ある指定避難場所のうち、最も早くたどり着けるのはどこか、また安全に効率的に移動できる経路はどれなのかは、自宅からでも難しい判断になる場合が多いだろう。見知らぬ外出先・旅行先ならなおさらだ。

　発見した最適避難経路をたどってはみたものの、途中で道路が危険な状態になっていた時、次善の経路を探るのに最初と同じ手間がかかるのでは困る。また、大抵の避難場所は高台にあることもあり、複数の道路が複雑に交わっていたり、最短ではあっても道幅が細かったり、こう配が厳しかったりと、移動の難易度が高い場合も多いだろう。

　最適な避難経路を論理的に求めることを追求すると、このように意外なほどさまざまな要素を考慮に入れて計算しなくてはならなくなる。最適な避難経路探索は、身近ながらなかなかに複雑な組合せ最適化問題なのだ。

　このような組合せ最適化問題に対して短時間で最適解を見いだすアルゴリズムはこれまで各種開発されてきた。なかでも最も一般的に用いられている手法にダイクストラ法があるが、その手法を上回るパフォーマンスで、最適な避難経路を、優先順を付けて一度に複数経路をレコメンド可能な新しい避難経路探索方法が、日本の若い研究者の手でこのほど開発された。ベースとしたアルゴリズムは、粘菌（細胞性粘菌ではない狭義の粘菌＝真正粘菌変形体）の生態研究から生まれた「粘菌アルゴリズム」だという。これは一体どんなものか。

経路探索能力の数理モデル化は2006年

　「粘菌には迷路を最短ルートで解く能力がある」ことを世界で初めて発見したのは、中垣俊之氏（現北海道大学教授、発見当時理化学研究所所属、2000年に論文発表）らの研究チームだった。

　粘菌の中でも真正粘菌変形体（以下、単に粘菌と呼ぶ）は、いわば裸の（細胞膜のない）原形質のかたまりという姿ながら、アメーバのように形を変えて、触手のように管を伸ばしてそこにいる微生物を捕食したり、光を嫌い、光が当たる部分を縮めたりと、変幻自在に自分の体を変形させることができる。神経組織を持たない原生生物なのに、環境に合わせて原形質が高速に流動・移動して、個体が生存しやすいように形を変える特性に、中垣氏らは注目した。

　実験では、迷路に粘菌を閉じ込め、入口と出口に餌をおいた。最初は迷路全体に粘菌が広がるが、やがて栄養がとれない枝道からは姿を消し、だんだんと入口と出口を結ぶ1本の最短経路内に収束していった。ひも状になった粘菌の姿は、そのまま迷路の解だった。この実験から、頭脳も神経もない粘菌に、最適経路探索能力があることが実証されたのだ。

　これを発端に、粘菌の形態形成の仕方を数理的なモデルとする取り組みが行われ、2006年には形態形成システムの一部を再現可能な数理的モデルが中垣氏らのチームによって構築されるに至った。これが「粘菌アルゴリズム」と呼ばれるものだ。

「粘菌アルゴリズム」を用いた避難経路探索で災害対応力を強化

　この粘菌アルゴリズムを、避難経路探索に応用することに取り組んだのは、地方独立行政法人東京都立産業技術研究センターの吉次なぎ氏と阿部真也氏だ。避難経路情報のベースになるGISの応用に造詣の深い電気通信大学の山本佳世子教授の協力を得て、約2年前に共同研究が開始された。

　吉次氏は「この研究は東京都の防災プランに基づくもので、災害対応力をソフト面から強化する目的で実施しています。同プランでは、安全・迅速・円滑な避難の実現を目指すとしており、そのために不可欠な最適避難経路探索を効率的に行うために粘菌アルゴリズムに注目しました」と語る。

　複数の避難経路候補から定量的根拠に基づいて避難経路を選択するアルゴリズムには、前述のダイクストラ法を含め幾つかの効率的な既存のアルゴリズムがある。しかし既存のアルゴリズムでは、2つのノード間の最適経路を1つ求めることはできても、その経路が被災などで利用できない場合の迂回（うかい）経路を求めるには追加計算が必要になり、計算コストがかかる。

　「粘菌アルゴリズムを用いる場合には、最適経路や迂回経路を含む避難経路を必要な数だけ、同時に導出できるのが利点。避難経路の災害危険度などの指標を加味したデータを用いることで、候補となる経路のそれぞれに避難に適している度合いを数値化して付与できます」（吉次氏）

　つまり、ただ1回の計算処理で、複数の避難経路を導き出したうえ、避難に適している順でランキングして提示するという。被災者がこの情報を入手できていれば、ランキング上位の避難経路から順に試していくことができる。選んだ経路が通行不能になっていたら、下位ランクの経路に向かえばよい。

「粘菌アルゴリズム」による避難経路探索の実証

　この手法の実証実験では、GISデータとして国土地理院が提供する東京都内の数値地図を用いた。数値地図には、地図情報、数値標高データなどの多様な属性情報が含まれている。その中からひとまず、道路の長さ、道路中心線のデータ、両端の緯度経度、5段階の道路の太さ情報に絞って計算に使うデータとした。吉次氏によれば「本当は道路の中心線に加えて歩行者経路のデータや道路の標高、災害危険度を示す各種のデータもあると良い。現時点ではまだデータが整備されていない部分がある」とのこと。

　数値地図から道路ネットワークデータを抽出し、道路の両端や交差点を「ノード」とみなし、それぞれの座標をつなぐ線（＝道路）を「リンク」とした。まずノードのリストとリンクのリストを作成する。次にノードリストから任意のノードを選び、それらノードを結ぶ経路のリンクの優先度を計算する。この優先度の計算に粘菌アルゴリズムを利用する。

　以降では、粘菌アルゴリズムによる優先度計算のアプローチがどういったものか、避難経路導出までの手続きの概要と実証実験の結果、今後の適用分野の展望を見ていく。

　粘菌アルゴリズムは「管（粘菌の伸びる足のような「輸送管」）の方程式と呼ばれる3つの数式を、圧力・流量・コンダクタンス（抵抗の逆数）のパラメータを変えながら繰り返し計算していくというものだ。圧力は避難する人の数、流量は通行できる人の数、コンダクタンスは通行可能性と言い換えることができる。

　この計算を最後まで、正確な優先度の値まで繰り返すには時間がかかりそうだが、実用的には優先順位が分かれば事足りる。優先度の大小は、ごく短時間で結果が出て逆転はしない（収束する）ため、それ以上の計算は必要なくなる。ノード間の経路それぞれに、経路に含まれる幾つかの道路の優先度の平均値をとれば、経路それぞれの優先度が比較できるようになる。その結果をGIS地図上にプロットすれば、どの経路をたどればよいかが一目で分かるようになるわけだ。また、もしも選んだ経路が通行不能になったら、次にとるべき経路も迷わずに選択できることになる。

図1　粘菌アルゴリズムによる避難経路導出の手順（東京都立産業技術研究センター）

実験では次のケースが試行された。

ケース1

（1） 避難開始地点が1つ、避難終了地点が1つの場合に、優先度の最も高い避難経路を1つ導出

ケース2

（2） 避難開始地点が1つ、避難終了地点が2つの場合に、それぞれの避難終了地点への最も優先度が高い避難経路を各1つずつ導出

ケース3

（3） 避難開始地点が1つ、避難終了地点が1つの場合に、優先度が高い順に2つの避難経路を導出

ケース4

（4） （1） において、途中の道路かが通行不可能であると仮定し,再計算なしで迂回路を導出

• （1）では、ダイクストラ法で求めた最短経路と一致する結果が出た。
• （2）では2つの避難場所に向かう2つの避難経路を同時に導出できた。避難場所では収容可能人数に差があるので、収容可能人数をパラメータとして入れることでより安全な避難場所選択と経路選択が可能になる。
• （3）では優先順位の高い順に2つの避難経路を同時に導出できた。追加計算の必要なく、任意の数の避難経路を導出可能だ。
• （4）では、途中の道路が通行不能でも再計算なしに迂回路を導出できた。

　まとめると、粘菌アルゴリズムを用いた避難経路探索では、他の経路探索アルゴリズムと違い、複数の避難場所への複数経路を追加計算なしで導出し、優先度も確認できる。また、全ての道路の優先度を計算しているため、一部の道路が通行不能になった場合でも、再計算せずに迂回路を見いだせる。

量子コンピュータ不要？　普通のPCで組み合わせ最適化問題を高速化、将来の物流革命にも

　昨今の量子アニーリング技術への期待の高まりに見られるように、組合せ最適化問題の効率的な解答を求めるニーズは強い。産業界では同技術がなかなか納得のいく結果を出せずにいるように見られている一方、避難経路という具体的で身近な応用問題に「粘菌」の生態研究から発展したアルゴリズムが良好な結果を出しているのは対照的だ。しかも利用するのは決して特殊で高価なマシンではなく、一般的なサーバーやPCだ。

　今回紹介した技術の現実的な応用イメージとしては、スマートフォンなどに自宅や会社付近の避難場所に関するデータを基にした優先順つきの推奨経路を記録させておき、いざというときに参照して避難するという方法だろう。ただし道路の優先度を計算するのに処理パワーが必要になることと、GISデータが必要なことから、計算とデータ抽出や組み合わせを行う処理はクラウド上のサーバに任せ、ユーザー端末ではその結果に基づいた推奨経路表示を行うようにするのが現実的なようだ。

　前述したように道路関連データの整備や、災害危険度データの追加も、経路の優先度を正確にするために重要になろう。さらに、リアルタイムに道路状況がアップデートされて優先順が最新・最適になるようだと理想的だ。研究チームではすでにスマホ対応アプリ開発に向かっており、実用化されるのはそう遠いことではなさそうだ。

　また、従来、経路探索アルゴリズムは鉄道路線経路案内のサービスや、コンピュータネットワークのルーティング、ゲームなどでのキャラクターのインタラクティブな移動、物流ルートの最適化などに使われてきた。将来的にはこうした領域への粘菌アルゴリズム応用も期待できそうだ。

（参考論文）吉次なぎ、阿部真也、山本佳世子：粘菌アルゴリズムを用いた避難経路導出手法の提案、情報処理学会論文誌、Vol.60、No.12、pp.2325-2329（2019）

Copyright © ITmedia, Inc. All Rights Reserved.