特集
» 2020年01月15日 08時00分 公開

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

災害が発生した場合、現在の場所から一番早く到達できる避難番所はどこか? 自宅からでも迷ってしまう避難場所と移動経路を短時間に探してくれる技術に、新しく「粘菌アルゴリズム」が追加された。GIS(Geographic Information System)との組合せで複数経路を一度に探索可能なその新手法とは?

[土肥正弘,ドキュメント工房]

目次


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Copyright © ITmedia, Inc. All Rights Reserved.

会員登録(無料)

ホワイトペーパーや技術資料、導入事例など、IT導入の課題解決に役立つ資料を簡単に入手できます。