多重解像度補間メッシュに基づく経路探索手法

全文

(1)Vol.2017-AL-163 No.6 2017/5/12. 情報処理学会研究報告 IPSJ SIG Technical Report. 多重解像度補間メッシュに基づく経路探索手法永谷禎基†1 澤田賢治†2. 新誠一†1. 概要：大規模グラフにおける経路探索の高速化を目的として，ネットワークの持つ階層構造を利用した解法が研究されている．本論文では階層構造間のフラクタルに着目した高速経路探索手法を提案する．本論文はフラクタルとして 3D モーフィングのデータ構造に用いられている多重解像度補間メッシュを利用し，低解像度層からのトップダウン方式の探索アルゴリズムを与える．このとき探索する層が高解像度になるほど探索される経路数が増加し，計算時間に影響が出る．この課題に対して分枝限定法によって最短になり得ない経路を発見し、その経路は以降の探索を中止とする．これによって探索の効率化を図る．また実際のネットワークは必ずしもメッシュ構造をしていない．この課題に対しては，与えられたグラフより近似的にメッシュを生成する手法を提案することにより解決する．数値実験により提案探索アルゴリズムが問題の規模にかかわらず，安定した計算時間で探索できることを示す．また実際のネットワークより近似的に生成したメッシュ上での探索を行い，近似解が高速に求まることを示す．キーワード：最短経路，フラクタル，多重解像度. A Route Search Method Based on Multiresolution Interpolation Mesh YOSHIKI NAGATANI†1 KENJI SAWADA†2 SEIICHI SHIN†1 1. はじめに. いても安定した計算時間で実行できることを示す．多重解像度補間メッシュは三角形のメッシュによって表現された. 大規模グラフにおける経路探索は頂点や辺の数が多い. 補間メッシュを頂点，辺の追加によってより高解像度の補. ゆえに計算時間が長大になる．本研究では大規模グラフ上. 間メッシュを得たものである．多重解像度補間メッシュの. において高速に最短経路を探索するアルゴリズムを提案す. 特徴として異なる解像度のメッシュ間に自己相似関係が存. る．経路探索において特に階層的視点から取り組んでいる. 在することが挙げられる．本研究では多重解像度補間メッ. 研究例がいくつかある[1],[2],[3]．これらの研究では元のグ. シュを用いて，三角形の格子グラフを多重解像度表現する．. ラフを粗いグラフと細かいグラフというように階層表現し，. そして解像度と階層を対応付けした上で，低解像度である. 粗いグラフから Dijkstra 法などを用いて探索を行っている．. 上位層からトップダウンに探索を行う．図 1 に全体的な探. そして粗いグラフでの探索結果を基に細かいグラフで探索. 索の流れを示す．各階層では隣接ノードへ最大 1 回移動す. する領域を絞り込むことで余計な探索を減らし，高速化を. るというルールに基づき探索を行う．トップダウン探索を. 実現している．グラフの階層表現に関しては様々ある．文. 行った場合，探索する層が高解像度になるほど探索される. 献[1]では道路ネットワークに存在する高速道路，国道，生. 経路数が増加する．このままでは計算時間に影響が出る．. 活道路といった階層構造を利用し，完全な意味での最短で. そこで本研究では最適解が得られる見込みがない探索途中. はなくより人の直観にあった最適な経路探索アルゴリズム. の経路は判明時に以降の探索を中止することを考える．こ. を提案している．文献[2]においても同様に道路の階層構造. れを実現する手法として組み合わせ最適化の汎用アルゴリ. を利用した最短経路探索アルゴリズムを提案しているが，. ズムである分枝限定法を用いる．分枝限定法では“上限値”. 探索の高速化に重みを置いている．文献[3]ではコミュニテ. と“下限値”という値が必要である．上限値は「ルールに. ィ検出を利用して探索の高速化に適した階層化を行ってい. 従って探索した時の移動可能な最長移動距離」，また下限値. る．本研究では階層構造として，道川らの多重解像度補間. は「目的地に到達するために少なくとも必要な移動距離」. メッシュ[4]という 3D モーフィングに用いられているデー. とそれぞれ定義する．. タ構造を取り入れる．本論文では階層に多重解像度補間メッシュに基づいた最短経路の探索アルゴリズムを提案し，大規模グラフにお †1 電気通信大学情報理工学研究科 Graduate School of Informatics and Engineering, The University of Electro-Communications †2 電気通信大学 i-パワードエネルギー・システム研究センター Info-Powered Energy System Research Center, The University of Electro-Communications. ⓒ 2017 Information Processing Society of Japan. 1.

(2) Vol.2017-AL-163 No.6 2017/5/12. 情報処理学会研究報告 IPSJ SIG Technical Report. Add new edges. Add new nodes. Start Goal. st. 1 layer nd. 2 layer. 図2. th. 4 layer st ~ 1 layer 図1 Figure 1. nd. ~ 4 layer. ~ 3 layer. メッシュの高解像度化. Figure 2. th. rd. ~ 2 layer. (c). (b). (a). rd. 3 layer. Addition of Nodes and Edges.. 上記の操作を行ったら，次に生成された各 3 頂点 ∈. を結ぶ辺. 提案アルゴリズムによる探索. ,. Route Search with the Proposed Method.. また実際のネットワークは必ずしもメッシュ構造しているわけではないため，本研究では与えられたグラフから. ∪. ,. ,. としてグラフ. 2（c））．辺の重みは. ，. ，. ，. をに加える．（図. と同様に. /2とする．以上の操作によって 1 つの三角形. メッシュを生成する手法も併せて提案する．なおメッシュ. を含むグラフから 4 つの三角形を含むグラフが生成される．. 生成には湊らの「Graphillion」[5]を用いた．. 生成された各三角形に対して同様の操作を繰り返し行うこ. 数値実験において提案アルゴリズムが大規模グラフに. とによって含まれる三角形の個数は 4 倍に増加し，解像度. おいても安定した計算速度で動作することを示す．また首. も高くなる．図 3 は異なる解像度のメッシュを縦方向に並. 都圏の鉄道ネットワークからメッシュを生成し，提案アル. べたものである．一番上から順に第 1 層，第 2 層，第３層，. ゴリズムによって高速に探索できることを示す．. 第４層である．各階層間は自己相似関係を有する．. 2. 本研究でのメッシュ多重解像度補間メッシュは道川ら[4]によって提案されており，3D モーフィングを実現する補間メッシュを多重解像度表現したものである．1 つの三角形の面を 4 つの三角. Low-resolution st. ). nd. ). rd. ). th. ). 1 layer (. Self-similar. 形の面に分割することでより高解像度の立体メッシュが得られる．本研究ではこの部分を用い，図 2 のように頂点お. 2 layer (. よび辺の追加によって 1 つの三角形を含むグラフから 4 つの三角形を含むグラフを生成する．この操作を繰り返すことによって得られるグラフはより高解像度になる．ここで. 3 layer (. は低解像度のグラフから順に第 1 層，第 2 層と呼んでいく．以下ではメッシュを無向グラフとして頂点，辺の追加操作を記述する． 1層のグラフを生成す. ここでは第層のグラフから第. る手順を示す．ここで示す手順は第層の各三角形に対してなされる．まず図 2(a)のような第層の三角形のグラフ ,. を与える．辺の重みは. 重みは共通の値. て着目する．辺の端点を. ,. ∖. （ ,. ，. ∈. ,. ∈ ,. Figure 3. Relation between Resolution and Layer.. 3. 提案アルゴリズム提案するアルゴリズムは与えられた三角形のメッシュ. につい. 上における 2 点間の経路上の重みが最小となる経路を探索. ）と. するものである．即ち，取り扱う問題は最下位層のグラフにおける最短経路の探索問題である．提案アルゴリズムの. を除去（. 探索は多重解像度化されたメッシュにおいて低解像度層か. ∪. らトップダウンに実行される．各階層では「隣接ノードへ. に追加する. 最大 1 回移動するという」ルールに基づき探索を行う．図. ，. を. としてグラフ. 4 は一連の探索手順を示した例である．図の例では始点を. （図 2（b））．. 辺の重みは. High-resolution 図 3 解像度と階層の関係. ）する．さらに次の式(1)，(2)を満. および辺 ∪. の各辺. より辺. おき，辺集合たす頂点. 1層のグラフは. とする．生成する第. とする．ここでグラフ. ,. と表記し，各辺の. 4 layer (. ,. (1). 第 0 層目に置いている．一方終点は各層の同位置に置いて. ,. (2). いる．図 4 (a)でまず第 1 層目の探索を行っている．隣接ノ. /2とする．各辺に対して. ードへ最大 1 回移動可能というルールが設けてあるので 0 回移動のノード. ⓒ 2017 Information Processing Society of Japan. _. と 1 回移動のノード. _. ，. _. までの経. 2.

(3) Vol.2017-AL-163 No.6 2017/5/12. 情報処理学会研究報告 IPSJ SIG Technical Report 路が得られる．得られた経路は探索木（Search Tree）として. Step.1 頂点を葉とする木を探索木とする．. 保存する．続いて第 2 層目の探索である（図 4 (b)）．第 1 層. Step.2 木の葉に格納されている各頂点に対して，. とする．上で. 目までの探索で得られた経路から，引き続き探索を行う．. 隣接する頂点へ移動し，得られた経路を探索木に保. 探索木で言うと各葉より続けて探索を進めるということで. 存する．また移動せずその場にとどまる経路も含め. ある．図からわかるように，探索する階層が 1 増えるごと. る．得られた各経路の上限値（. に探索木の深さも 1 増える．. をそれぞれ計算する．. ），下限値（. Step.3 得られた各経路について. _ _. Step.4 残った各経路中の. Search tree. 最大値. _. Goal. となった経路を. 探索木より削除する．. Start. _. ）. について最大のものを発見し，. よりも. が大きい経路は探索木よ. り削除する． _. Step.5. なら. が最小の経路を 1 つ出力して終了，. なら. 1として Step.2 へ移動する．. 入力パラメータのうち最下位層のグラフ _. _. _. と始点，終点. は「最短経路問題」として与えられるものであり，その他のパラメータは提案アルゴリズムにおいて必要なものであることに注意していただきたい．. (a). Step.3 及び Step.4 では 2 つの条件による枝刈りが実行さ. _. _. れる．以下では分枝限定法を用いるうえで必要となる上限値及び下限値についてさらに説明をする．. _. 3.1 上限値と下限値. _ _. ここでの上限値. _. _. _. _. _. _. _. は「ルールの下で探索終了層. 探索したときの取りうる最長距離」と定義する．. _. までは計. 算時点における探索した移動量と現在の階層より下での. _. ′との和. 探索で取り得る最大移動量. ′で得られる．. ′の計算方法はあらかじめアルゴリズムによって得 _. _. _. _. _. _. _. _. _. (b) 図4. る．しかしすべての経路を列挙しようとするとその数は階層が進むにつれ指数関数的に増加する．ここでは各階層の. 得られる探索木. （頂点の添え字は（ノード番号）_（階層）を表す） Figure 4. られるすべての経路を列挙するというのが 1 つの方法であ. が. これに従って探索を進めたときの探索経路数は指数関. 1階層の辺の重み. 辺の重みが等しく，第階層と第. Search Tree.. /. 計算する．各階層での探索は最大 1 回隣接ノードへ移動す. 数的に増大し，探索時間に影響を与える．そこで本研究で. るというルールがあるので，. は探索経路数を削減することを考える．ここでは分枝限定. 項数. 法を用いることで最適解が得られる“見込みがない”探索. 階層を表す．. は初項. 2. りと呼ぶ．枝刈りはある階層を探索したらその時点で探索中の経路について評価し，実行される．そして残った経路は引き続き次の階層で探索が行われる．つまり上で述べた. 2. “見込みがない”とはそれ以上探索を続けても最適解が得. 1 2 1 1 2 1 1 2 2 1. (3). られないという意味である．枝刈りする経路の条件はここ. これにより第層探索終了時の上限値. では 2 つ存在する．二つの条件によって終点まで到達不可. 算される．. 能な経路と，最適解になり得ない経路が枝刈りされる．ア. 2. ルゴリズムの全体的な流れは以下のとおりである．ラフ. ,. ，探索終了層. ,⋯,. ，グ. /2 ，公比1/2，. なる等比級数の和として表される．は現在の. 途中の経路を発見し，以降の探索を中止する．これを枝刈. （入力）始点，終点，探索開始層. ，. 1/2の関係にあることを用いて数式的に. 一方下限値. 1 2. は次のように計. 1 2. (4). は終点に到達するまでに少なくとも必要. な距離と定義する．. はユークリッド距離を用いて算出. （出力）最短経路. する．そこで各階層のグラフが 2 次元ユークリッド空間上. （手順）. に定義されているとする．第層探索終了時の下限値. ⓒ 2017 Information Processing Society of Japan. は. 3.

(4) Vol.2017-AL-163 No.6 2017/5/12. 情報処理学会研究報告 IPSJ SIG Technical Report 探索した距離と探索し終えた地点から終点までのユー ,. クリッド距離. を用いて. 図 5 に探索結果を示す．階層間にまたがった経路が提案アルゴリズムによって探索された経路，各階層の経路が. ,. (5). Dijkstra 法による経路である．提案アルゴリズムと Dijkstra. と計算する．. 法による最短距離は同じ値であった．2 つのアルゴリズム. 3.2 枝刈り条件. について，計算時間の推移を図 6 に示す．どの. に対して. も提案アルゴリズムの計算時間の方が速い．3. 8の. 上限値及び下限値は各階層で探索を終えたときにそれぞれの経路に対して計算する．そしてそれらの値に基づい. 範囲では計算時間の差はおおよそ一定であり，約 0.005 秒. て枝刈りをするが，その条件としては上で述べたように 2. である．しかし. つ存在する．. 9では約 0.01 秒，. 1 つめの枝刈り条件は各経路の上限値. 10では約 0.02 秒の差が生じている．. 提案アルゴリズムは. が上昇しても安定した計算時間で. の場合である．上限値及び下限値の定. 実行されている．図 7 は各階層のグラフにおけるノード数. となった場合はそれ以上探索を行っても. を示す．図 7 からわかるように階層が 7 を過ぎてから急. について義より. と下限値. が 8 を超えると，その差は増加する．. そもそも終点に到達不可能である． Start. 1 つめの条件によって枝刈りをしたあと，さらに残った経路を 2 つめの条件によって枝刈りする．2 つめの枝刈り条件は残った経路の各. のうちの最大値. よりも. が大きい場合である．この条件によって最小値を取り得ない経路が枝刈りされる．ただし枝刈り後に残った経路. Proposed method Goal. st. 1 layer. が探索を続けて終点に到達できる保証や最適解を取りうる保証はないことに注意していただきたい．例えば辺が切れている場合がもしあれば終点に到達不可能なことがあるだ. nd. 2 layer. ろう． rd. 3 layer. 4. 提案手法の計算速度性能提案したアルゴリズムの性能について特に計算速度の観点から検証をする．比較として Dijkstra 法でもメッシュ. th. 4 layer. 上での探索を行い計算時間の比較を行う．実行環境を表 1 に示す．表1 Table 1. Experiment Enviroment.. プロセッサ. Intel(R) Core(TM) i7-4900 3.60GHz. メモリ. 8GB. OS. Windows 7 Professional SP1. th. 6 layer 図5. 探索結果（第 6 層まで）. Figure 5. Matlab R2016A. プログラム. Dijkstra method. th. 5 layer. 実験環境. Results of Searching.. 環境 Dijkstra 法. Matlab コマンド ”shortestpath”. 実験では第 3 層から第 10 層の同一 2 点間で最短経路を探索した．そして階層と提案アルゴリズムの計算時間の関係について調査した．一方比較となる Dijkstra 法でも各階層で同一地点間の探索を行い，階層と計算時間の関係について調査した．実験の条件を表 2 に示す．表2 Table 2. 実験条件. Experiment Condition.. 探索開始層. 1. 探索終了層. 3∼10. グラフの詳細. 各階層における辺の重みは均一，階層間の重みの関係は 8（ただし. /. 2，. は第層の辺の重み）. ⓒ 2017 Information Processing Society of Japan. 図6 Figure 6. 計算時間の推移 Calculation Time.. 4.

(5) Vol.2017-AL-163 No.6 2017/5/12. 情報処理学会研究報告 IPSJ SIG Technical Report. 図 8 は首都圏の鉄道ネットワークaよりメッシュを生成する手順を示したものである．上段が生成したメッシュであり，第 1 層目まで生成した状態，即ち Step.1 が終わった状態である．生成アルゴリズムではメッシュの各辺上に頂点を追加し，さらにその頂点間を結ぶ経路を列挙，選択してメッシュの辺としている．この操作を各三角形に対して繰り返すことでさらに深い階層を生成していく．首都圏の鉄道ネットワークより生成したメッシュ上で最短経路を探索した．表 3 のように始点と終点を指定した．図 9 は提案アルゴリズムによる探索結果である．計算時間図7 Figure 7. は 0.018 秒であり，経路長は 111.6km であった．比較とし各階層の頂点数. Number of each layer’s nodes.. て生成元の鉄道ネットワーク上で同点間の最短経路を Dijkstra 法で探索した．結果は計算時間が 0.028 秒，経路長. 激に頂点数が増加している．このことよりグラフの規模が. は 100.6km となった．厳密解との誤差は約 10%に収めなが. 大きいほど提案アルゴリズムは有効であることがわかる. ら，計算時間は約 35％削減された．図 10 及び図に提案手. 5. 実ネットワークからのメッシュ生成. 法と Dijkstra 法によって出力された最短経路を示す．. ここまでで三角形メッシュ上における最短経路探索手法を提案した．もちろんすべてのネットワークがメッシュ構造を有しているわけではない．そこで本研究では与えら. Dijkstra 法によって出力された経路はメッシュ上に存在しなかった．生成するメッシュによって得られる最適解が決まってくるようである．. れた重み付きグラフよりメッシュを生成する手法を併せて. Add new edges. Add new nodes. 提案する．ここでの生成手法は与えられたグラフからメッシュを構成する辺及び頂点を選択するものである．ここでは探索問題として鉄道ネットワークにおける最短経路問題を用意し，メッシュ生成したうえで探索アルゴリズムを適用する．以下にメッシュの生成手順を示す．（入力）生成元のグラフ，生成する階層数（出力）各階層のグラフ. ，. ，･･･，図8. （手順） Step.1 グラフ中の最長閉路を 1 つ取り出す．閉路中の 3 頂点をグラフの頂点，それらを結ぶ各経路をの辺とする． 1とする．また閉路長の 1/3 をとする． Step.2 1，とする．グラフ中の三角形閉路注をすべて取り出す． Step.3 ある 1 つの三角形閉路に対して三角形の各辺に対応する生成元グラフ中の経路から，頂点を選択して三角形の辺上に追加する．選択基準は分断されてできる 2 辺の重みができるだけ等しくなることである． Step.4 Step.3 によってできた各 3 頂点間を結ぶ経路を生成元グラフから列挙，選択してグラフの辺とする．選択基準は経路長が /2 に最も近いものである． Step.5 Step.2 で取り出したすべての三角形に対して Step.3， 4 の操作を行ったら Step.6 へ，そうでなければ Step.3 へ移動する． Step.6 なら生成終了，なら Step.2 へ移動する．注:グラフ中の 3 辺によって構成される閉路を指す．. メッシュの生成手順（第 2 層目の生成） Figure 8. Process of mesh generation.. 表3 Table 3. 実験条件と結果. Conditions and Result of Experiment.. 始点. 頂点 1. 終点. 頂点 26. 始点に対応する駅名. 取手. 終点に対応する駅名. 小山. 階層数. 4. 提案アルゴリズムにより出. 111.6km. 力された最短距離路線図上での実際の最短距. 100.6km. 離また始点終点の組み合わせによっては解を発見できない場合も存在した．主な原因として上限値，下限値が正しく推定できていないということが挙げられる．今回は各辺. なお Step.4 の経路の列挙には湊らの「Graphillion」[5]を用. の重みが一定と仮定して計算を行ったが，実際には重み一. いた．. 定ではない．メッシュ生成手順 Step.4 の基準距離と実際に. a 駅データ.jp（https://www.ekidata.jp/）より取得した．. ⓒ 2017 Information Processing Society of Japan. 5.

(6) Vol.2017-AL-163 No.6 2017/5/12. 情報処理学会研究報告 IPSJ SIG Technical Report 生成されたメッシュの重みとの誤差は表 4 のようになった．特に下位層側でばらつきや誤差が目立つ．これらを踏まえ，上限値，下限値の計算方法やメッシュの生成方法を改善する必要がある．また別の原因として，そもそもトップダウン探索のみでは終点に到達できない始点終点の組み合わせがあるということも挙げられる．終点に到達できないとわかったときにボトムアップ探索もできるようなアルゴリズムを考える必要がある．表4. メッシュの重み誤差. Table 4 階層. 基準距離 /2. Errors of weights. 標準偏差. 平均値. 最大誤差. 図 11. Δ. 1. 339.1. 339.1. 0.7810. 0.9000. 2. 169.6. 170.4. 2.876. 7.950. 3. 87.78. 91.02. 22.50. 74.03. 4. 42.39. 47.84. 20.55. 119.4. Figure 11. Dijkstra 法による最短経路. A Shortest Path with the Dijkstra Method. 6. まとめと今後多重解像度補間メッシュ上での最短経路探索アルゴリズムを提案した．提案手法では探索，分枝限定法による枝刈りという手順を階層ごとに行い，最短経路を探索した．実験結果より提案探索アルゴリズムは大規模な問題であっ. Start. ても計算時間が指数関数的に増大しないことを確認した． Goal. また与えられたグラフより多重解像度補間メッシュを生成する手法を提案した．多重解像度補間メッシュの生成については経路探索をする上で問題があり，生成手法の改善が必要である．現段階ではまだどのようなメッシュ構造ならどの程度の精度をもって最短経路を出力できるのかといった点が十分に考察できていない．今後としてはこの点について解明し，そのうえでメッシュ生成アルゴリズムの改善が必要である．またボトムアップ探索を含めたアルゴリズムについ. The source network 図9. ても考えている．これによってトップダウン探索だけでは得られない経路も得られると期待できる．. 提案アルゴリズムによる最短経路（太線）. Figure 9. A Shortest Path with the Proposed Method.. 参考文献 [1]. [2]. [3]. [4]. [5]. 図 10. 提案アルゴリズムによる最短経路（太線，. 丹羽寿男，吉田雄二，福村晃夫:“道路網の階層的表現にもとづく経路探索アルゴリズムと地図情報システムへの応用”，情報処理学会論文誌，Vol.31，No.5，1990． Jiang Gangwu, Wang Jing, Chen Bo: “The Shortest Path Algorithm Based on Hierarchical Road Network”, 2006 6th International Conference on ITS Telecommunications Proceedings, 2006. Q. Song and X. Wang: "Efficient Routing on Large Road Networks Using Hierarchical Communities," IEEE Transactions on Intelligent Transportation Systems, vol. 12, no. 1, pp. 132-140, March 2011. 道川隆士，金井崇，藤田将洋，千代倉弘明．多重解像度補間メッシュ．グラフィクスと CAD / Visual Computing 合同シンポジウム，論文集．pp.139-144，2001． Takeru Inoue, Hiroaki Iwashita, Jun Kawahara, and Shin-ichi Minato: "Graphillion: Software Library Designed for Very Large Sets of Labeled Graphs," International Journal on Software Tools for Technology Transfer, Springe. 真上から見た状態） Figure 10. A Shortest Path with the Proposed Method (Top View).. ⓒ 2017 Information Processing Society of Japan. 6.

(7)