JP5681050B2 - 経路探索装置、経路探索方法及び経路探索プログラム - Google Patents

Description

本発明は、経路を探索する技術に関する。

現在では、例えば、カーナビゲーションシステムやネットワーク上の地図サービスにおいて、出発地から目的地までの２地点間の経路を求めて表示することが実現されている。このような２地点間の経路を求めることは古くから知られた技術であり、その技術の核となるのは、主に交差点に対応する点をノードとし、それらノード間で通行可能な道をリンクとし、各リンクにその距離（あるいは通過に必要な時間）をコストとして割り当て、ノードとリンクの接続状態を表すデータをグラフとみなしてグラフ理論を適用することである。例えば、２つのノード間の最短距離を求めるアルゴリズムとして、「ダイクストラ法」（非特許文献１）や「Ａ＊法」（非特許文献２）などの技術が知られている。非特許文献１，２の方法は、ノード間、すなわち交差点から交差点までの最短経路を求める技術であるが、その方法を拡張して任意の２地点間の最短経路を求めることも容易である。以下、簡単にその方法を説明する。

まず、図１２（ａ）に示すように、出発地Ｓと目的地Ｄの座標が指定される。

続いて、図１２（ｂ）に示すように、出発地Ｓから最も近傍となるリンク（この場合、Ｎ１−Ｎ３リンク）上の近傍点Ｓ’を求め、Ｎ１−Ｎ３リンクを分割してノードにＳ’を追加する。Ｓ’からＮ１への距離をＬ１、Ｓ’からＮ３への距離をＬ３とすると、Ｌ１：Ｌ３の比に応じて、Ｎ１−Ｎ３リンクのコストを分配して、Ｎ１−Ｓ’リンクとＳ’−Ｎ３リンクのコストとして割り当てる。同様に、目的地Ｄから近傍点Ｄ’を求めてノードＤ’を追加する。

そして、図１２（ｃ）に示すように、ノードＮ１，・・・，Ｎ９，Ｓ’，Ｄ’からなるグラフに対して、非特許文献１，２の方法を適用してノードＳ’−Ｄ’間の最短経路を求め、Ｓ−Ｓ’、Ｄ−Ｄ’を追加し、Ｓ−Ｄ間の最短経路とする。

人は、地図を見るだけで、暗黙のうちに経路を理解することが容易にできるが、計算機等で、上記のような経路探索を行うためには、整合性のとれたグラフ構造をなすノードとリンクのデータ（ネットワークデータ）が必要となり、しかも探索された経路上のリンクを地図画像に重畳して出力するためには、そのリンクの位置と、人が暗黙のうちに理解する経路の位置に大きなずれが生じていないことが必要条件となる。このため、カーナビや地図サービスにおいては、デジタル地図データの供給者によって、一元的に、必要なネットワークデータも作成されて供給されることが一般的である。特に、近年では、歩行者の利用も考慮し、歩行者専用通路を含むネットワークデータが整備され、供給されている。

Dijkstra, E. W. "A note on two problems in connexion with graphs.", Numerische Mathematik, 1(1959), S.269-271 Hart, P. E.; Nilsson, N. J.; Raphael, B., "A Formal Basis for the Heuristic Determination of Minimum Cost Paths", IEEE Transactions on Systems Science and Cybernetics, SSC4(2), 1968, p.100-107

しかしながら、デジタル地図データの供給者によるネットワークデータ作成では、屋内施設やビル構内などのネットワークデータは供給されない。あるいは供給されるとしても、特定のターミナル駅構内など、非常に限定された対象に限られる。これは、デジタル地図データの供給者は、航空写真などの情報をベースにデータ作成することが多く、屋内施設のデータを作成するための調査効率が悪いこと、屋内は通常私有地であり、調査のための所有者の許可を得る手続が個別に必要であることなどの理由がある。さらに、デジタル地図データの供給者により提供されるネットワークデータは、非常に規模が大きいために必要な整合性の確認などを経てから提供・市販されるため、実際にそのようなデータが利用可能になるまで、数ヶ月といったレベルの期間がかかる。屋外の例えば道路等は建設に相当な時間がかかるため、このようなレベルの更新期間であっても問題はないが、屋内、特に施設内の通路等は、簡易な改装で頻繁に変更されることがあり、すぐに経路探索結果に反映されることが期待され、数ヶ月レベルの更新期間では問題となる。

一方で、施設管理者自身が施設内のネットワークデータを用意することも可能である。この場合、通常、特に許可を改めて得る必要はなく、また施設管理者は多くの場合施設の図面等を保持していることや、そもそも施設内を熟知していることから、特別な調査も不要である。また、規模が限られているため、データの整合性の確認も容易であり、短期間で利用者に対して経路探索サービスを提供することも可能である。このため、施設内の改装等に伴う変化にも柔軟に対応できる。

しかしながら、当然、この場合は、経路探索が可能となる範囲は、その施設内に限定されてしまう。そのため、屋外の出発地から施設内の目的地までの経路探索、施設内の出発地から屋外の目的地への経路探索、あるいは、ある施設内の出発地から別の施設内の目的地への経路探索をすることができない。

本発明は、上記に鑑みてなされたものであり、施設内の地点を出発地、目的地として指定可能な経路探索を提供することを目的とする。

第１の本発明に係る経路探索装置は、経路探索対象の２地点の入力を受け付けて、２地点間の経路を探索する経路探索装置であって、施設内の経路探索に用いるための、広域経路探索に用いる広域ネットワークデータに接続する前記施設の出入り口に対応し、緯度経度のデータが付与された外部接続ノードを有するローカルネットワークデータを施設毎に蓄積したローカルネットワークデータ蓄積手段と、施設内に経路探索対象の施設内地点が指定されたときに、当該施設内地点を含む前記ローカルネットワークデータを前記ローカルネットワークデータ蓄積手段から読み出して、当該施設内地点と前記施設の前記外部接続ノードそれぞれとの間の経路探索を行うローカル経路探索手段と、前記広域ネットワークデータ内に経路探索対象の広域地点が指定されたときに、当該広域地点の緯度経度のデータと前記外部接続ノードの緯度経度のデータを外部のサーバに送信して広域の経路探索結果を受信する広域経路探索手段と、同じ前記外部接続ノードを持つ前記ローカル経路探索手段の探索結果と前記広域経路探索手段の探索結果を統合して経路探索結果として出力する経路統合手段と、を有することを特徴とする。

上記経路探索装置において、経路探索対象の２地点として異なる第１、第２の施設内の施設内地点が指定された場合、前記ローカル経路探索手段は、前記第１、第２の施設内の施設内地点のそれぞれについて前記外部接続ノードそれぞれとの間の経路探索を行い、前記広域経路探索手段は、前記第１、第２の施設それぞれの前記外部接続ノード間の広域経路探索を行い、前記経路統合手段は、前記第１の施設についての経路探索の探索結果と前記広域経路探索手段の探索結果と前記第２の施設についての経路探索の探索結果を統合して経路探索結果として出力することを特徴とする。

上記経路探索装置において、前記広域経路探索手段は、前記第１、第２の施設の前記外部接続ノード間の経路が短くなると推定される前記外部接続ノードを抽出し、抽出した前記外部接続ノード間についてのみ広域経路探索を行うことを特徴とする。

上記経路探索装置において、前記施設毎に前記ローカルネットワークデータを受け付けて前記ローカルネットワークデータ蓄積手段に蓄積するローカルネットワークデータ登録手段を有することを特徴とする。

第２の本発明に係る経路探索方法は、施設内の経路探索に用いるための、広域経路探索に用いる広域ネットワークデータに接続する前記施設の出入り口に対応し、緯度経度のデータが付与された外部接続ノードを有するローカルネットワークデータを施設毎に蓄積したローカルネットワークデータ蓄積手段、ローカル経路探索手段、広域経路探索手段、及び経路統合手段を備えた経路探索装置によって実行される、経路探索対象の２地点の入力を受け付けて、２地点間の経路を探索する経路探索方法であって、前記ローカル経路探索手段による、施設内に経路探索対象の施設内地点が指定されたときに、当該施設内地点を含む前記ローカルネットワークデータを前記ローカルネットワークデータ蓄積手段から読み出して、当該施設内地点と前記施設の前記外部接続ノードそれぞれとの間の経路探索を行うステップと、前記広域経路探索手段による、前記広域ネットワークデータ内に経路探索対象の広域地点が指定されたときに、当該広域地点の緯度経度のデータと前記外部接続ノードの緯度経度のデータを外部のサーバに送信して広域の経路探索結果を受信するステップと、前記経路統合手段による、同じ前記外部接続ノードを持つ前記ローカル経路探索手段の探索結果と前記広域経路探索手段の探索結果を統合して経路探索結果として出力するステップと、を有することを特徴とする。

上記経路探索方法において、経路探索対象の２地点として異なる第１、第２の施設内の施設内地点が指定された場合、前記ローカル経路探索手段は、前記第１、第２の施設内の施設内地点のそれぞれについて前記外部接続ノードそれぞれとの間の経路探索を行い、前記広域経路探索手段は、前記第１、第２の施設それぞれの前記外部接続ノード間の広域経路探索を行い、前記経路統合手段は、前記第１の施設についての経路探索の探索結果と前記広域経路探索手段の探索結果と前記第２の施設についての経路探索の探索結果を統合して経路探索結果として出力することを特徴とする。

第３の本発明に係る経路探索プログラムは、上記経路探索装置としてコンピュータを動作させることを特徴とする。

本発明によれば、施設内の地点を出発地、目的地として指定可能な経路探索を提供することができる。

本実施の形態における経路探索装置の構成を示す機能ブロック図である。 ローカルネットワークデータのデータ構造を示す図である。 ローカルネットワークデータを具体的に説明する図である。 ローカルネットワークデータをＸＭＬ形式のデータとして表現した例を示す図である。 ローカルネットワークデータを表形式のデータとして表現した例を示す図である。 ローカルネットワークデータ登録部の構成例を示す図である。 ローカルネットワークデータの登録処理をするアプリケーションプログラムの画面例を示す図である。 出発地が屋外で目的地がローカルネットワークデータに属する場合の経路探索の処理の流れを示すフローチャートである。 目的地が屋外で出発地がローカルネットワークデータに属する場合の経路探索の処理の流れを示すフローチャートである。 出発地と目的地が互いに異なるローカルネットワークデータに属する場合の経路探索の処理の流れを示すフローチャートである。 本実施の形態における経路探索装置を含む全体構成図である。 グラフ構造を利用して２地点間の最短経路を求める方法を説明する図である。

以下、本発明の実施の形態について図面を用いて説明する。

図１は、本実施の形態における経路探索装置の構成を示す機能ブロック図である。同図に示す経路探索装置１００は、ローカルネットワークデータ登録部１１０、ローカルネットワークデータ蓄積部１２０、ローカル経路探索部１３０、広域経路探索部１４０、および統合経路探索部１５０を備える。経路探索装置１００が備える各部は、演算処理装置、記憶装置等を備えたコンピュータにより構成して、各部の処理がプログラムによって実行されるものとしてもよい。このプログラムは経路探索装置１００が備える記憶装置に記憶されており、磁気ディスク、光ディスク、半導体メモリ等の記録媒体に記録することも、ネットワークを通して提供することも可能である。以下、各部について説明する。

ローカルネットワークデータ登録部１１０は、施設管理者から、その施設管理者が管理する施設内における経路を探索するためのローカルネットワークデータを入力する。ローカルネットワークデータの詳細については後述する。

ローカルネットワークデータ蓄積部１２０は、ローカルネットワークデータ登録部１１０が入力したローカルネットワークデータを施設毎に蓄積する。

ローカル経路探索部１３０は、同一のローカルネットワークデータ上に存在する出発地と目的地が指定されたときに、ローカルネットワークデータ蓄積部１２０からローカルネットワークデータを取得して、そのローカルネットワークデータに基づいて出発地と目的地間の経路探索を行う。ローカルネットワークデータ上での出発地、目的地は、ローカルネットワークデータを特定する情報と、そのローカルネットワークデータの図面データを特定する情報と、その図面データ上での、例えば図面データの右上を原点としてピクセル単位で表される座標値で指定する。

広域経路探索部１４０は、緯度経度により指定された２地点間の経路探索を行う。広域経路探索は、デジタル地図データ供給者により提供されたネットワークデータに対して、非特許文献１，２の技術を用いる。あるいは、広域経路探索部１４０は、広域経路探索の機能を提供しているネットワーク上のサーバを利用して、出発地と目的地の緯度経度を指定して検索要求を送信し、経路探索結果を受信するものでもよい。

統合経路探索部１５０は、ローカル経路探索部１３０、広域経路探索部１４０の経路探索結果を統合し、施設内の経路を含む最適な経路探索結果を出力する。

次に、ローカルネットワークデータについて説明する。

図２は、ローカルネットワークデータのデータ構造を示す図である。ローカルネットワークデータは、背景図面（フロア図等）となる画像データ、画像データに対応して設定されたノード、同一画像データ内のノード間を結ぶ図面内リンクを有する図面データと、図面データ間のノードを結ぶ図面間リンクと、施設の出入り口に相当し、緯度経度のデータが付与された外部接続ノードとを有する。１つの施設に対して１つのローカルネットワークデータが存在する。

図３に、ローカルネットワークデータの具体例を示す。同図に示すローカルネットワークデータは、３フロアで構成されるショッピングモールについてのローカルネットワークデータである。このローカルネットワークデータは、ショッピングモールの１Ｆ，２Ｆ，３Ｆの各階に対応する３つの図面データがある。各図面データは、各階のフロアマップに相当する画像データを有し、画像データに対応付けて黒丸で示されたノードが設定されている。ノードは、画像データの座標値（例えばピクセル単位で表される値）で設定される。同じフロアで移動可能な通路に相当するノード間には図面内リンクが設定される。また、フロアをまたがるエレベータ、エスカレータ、階段などの通路には、図面間リンクが設定される。図３に示す例では、エレベータに対応して図面間リンクが設定されている。１Ｆのノードのうち、外部への出入り口に相当する白丸のノードが外部接続ノードとして指定されている。なお、２Ｆから直接外部のペデストリアンデッキへ出入りできる場合なども考えられるので、外部接続ノードは必ずしも１Ｆに相当する図面データ内にあるとは限らない。

画像データとして、図面ごとに決められた一定の縮尺に基づくほぼ正確な図面の画像データを用いることで、経路の正確な距離を座標値と縮尺から計算できる。図面内リンクについては、図面上の座標値を元に算出された距離にその縮尺の逆数をかけることで実際の距離が算出できる。図面間リンクについては、それぞれのリンクに対し、その移動の負担あるいは所要時間を元に、通常の徒歩での移動の何ｍの移動に相当するのが妥当か、という値を指定しておく。例えば、１Ｆから２Ｆまでエレベータにより移動することは、所要時間を考慮すると、３０ｍの距離を歩くことに相当する、というような数値である。これにより、図面内リンク、図面間リンクともに、リンクコストとして「徒歩で移動することに相当する距離」という値が付与されることになる。

図４は、ローカルネットワークデータをＸＭＬ形式のデータとして表現した例を示す図である。同図に示す例では、network タグで囲まれた部分がローカルネットワークデータを示している。map タグで囲まれた部分が図面データを示し、図４の例では３つの図面データが存在する。図面データ中の image, node, link の要素がそれぞれ画像データ、ノード、図面内リンクを示している。また、extlink, entry の要素はそれぞれ図面間リンク、外部接続ノードを示している。ネットワークデータをＸＭＬ形式のデータで表現した場合、ローカルネットワークデータ蓄積部１２０として、ハードディスクなどのファイル単位で読み書き可能な記憶装置を備えた計算機を用い、ローカルネットワークデータごとに１つのファイルとして記憶装置の特定のディレクトリ上に蓄積する入出力プログラムにより構成することができる。

また、別の表現方法としては、図５に示すように、表形式のデータとしてローカルネットワークデータを表現することができる。図５（ａ）は画像データのテーブル例を示し、図５（ｂ）はノードのテーブル例を示し、図５（ｃ）は図面内リンクのテーブル例を示し、図５（ｄ）は図面間リンクのテーブル例を示し、図５（ｅ）は外部接続ノードのテーブル例を示す。ネットワークデータを表形式のデータで表現した場合、データベースマネージメントシステム（ＤＢＭＳ）を用いてテーブルを定義してローカルネットワークデータ蓄積部１２０を構成することができる。

次に、ローカルネットワークデータの登録について説明する。

ローカルネットワークデータの登録は、施設管理者により作成された図４に示すようなＸＭＬ形式のデータを入力することで行う。具体的には、Ｗｅｂサーバとして機能する計算機上に、ＸＭＬファイルと画像データをアップロードできるＷｅｂページを設け、そのページを通じて施設管理者よりＸＭＬファイルと画像データを受信し、ローカルネットワークデータ蓄積部１２０に蓄積する。ローカルネットワークデータ蓄積部１２０では、ローカルネットワークデータをＸＭＬ形式のデータで蓄積する場合は、入力したＸＭＬファイルをそのまま蓄積すればよく、ローカルネットワークデータを表形式のデータで蓄積する場合は、入力したＸＭＬファイルを解析して表形式のデータに変換し、ＤＢＭＳの登録機能により蓄積する。なお、偽の施設管理者からのアップロードを避けるための認証、ローカルネットワークデータＩＤのチェック、蓄積済みデータに対する上書き確認、書き込みエラー等に対する警告表示などの処理も行うが、ここでは通常行われる処理についての説明は省略する。

別のローカルネットワークデータの登録方法として、施設管理者がディスプレイに表示された画像データを見ながらマウス等のポインティングデバイスを操作することで、その施設のローカルネットワークデータを登録できるアプリケーションを利用する方法もある。例えば、図６に示すように、ローカルネットワークデータ登録部１１０を、サーバ１１２とネットワーク１１３を介して接続された端末１１１Ａ，１１１Ｂで構成し、端末１１１Ａ，１１１Ｂ上でアプリケーションプログラムを動作させてローカルネットワークデータを入力する。この場合、各端末１１１Ａ，１１１Ｂで作成されたＸＭＬ形式のデータをサーバ１１２が受信してローカルネットワークデータ蓄積部１２０に登録する。

図７に、端末１１１Ａ，１１１Ｂで動作するアプリケーションプログラムの画面例を示して、ローカルネットワークデータの登録処理を説明する。

アプリケーションプログラムを起動し、施設、すなわちローカルネットワークデータを識別するＩＤを指定すると、図７（ａ）に示す初期画面となる。図７（ａ）の左側の「１Ｆ」「２Ｆ」のアイコンは１Ｆ、２Ｆフロアに相当する図面データが登録されていることを示す。

図７（ａ）のＭａｐ作成ボタンをクリックすると、図７（ｂ）に示す新規図面登録画面に遷移する。図７（ｂ）で、例えば「３Ｆ」などのＩＤを入力して３Ｆフロア図に相当する画像ファイルを選択し、アップロードボタンをクリックすると「３Ｆ」の図面データが追加されて、図７（ａ）の画面（ただし、左側に「３Ｆ」が追加表示された状態）に戻る。画像ファイルの選択は、選択ボタンをクリックして表示されるダイアログを用いて行う。

図７（ａ）の画面で左側の「１Ｆ」等のアイコンをクリックすると、図７（ｃ）に示す図面データ編集画面に遷移する。図面データ編集画面では、選択した図面データのフロア図（画像データ）が表示され、フロア図を見ながら、ノードの作成、削除、リンクの作成、削除などの編集を行うことができる。図面データを選択した状態で、図７（ｃ）の選択Ｍａｐ削除ボタンをクリックすると、選択した図面データが削除される。

図７（ｃ）のノード作成ボタンをクリックし、画面の右側に表示されたフロア画像上の任意の点をクリックすると新規のノードがその位置に作成される。フロア画像上のノードをクリックして選択し、ノード削除ボタンをクリックすると選択したノードが削除される。また、ノードをクリックしてドラッグすると、ノードの位置を変更できる。なお、ノードの削除、移動に伴い、そのノードに設定されているリンクも削除、移動する。

ノードを２つ選択した状態で、選択ノード間にリンク作成ボタンをクリックすると選択したノード間にリンクが作成される。リンクあるいは両端の２つのノードを選択した状態で、リンク削除ボタンをクリックすると選択したリンクが削除される。

ノードを１つ選択した状態で、選択ノードから別Ｍａｐノードへのリンク作成ボタンをクリックすると、図７（ｄ）に示すもう一方のノードを指定するための図面間リンク選択画面に遷移する。図７（ｄ）では、「２Ｆ」の図面データを選択し、２Ｆフロアに設定されたノードを指定しようとしている。図面間リンクのもう一方のノードが指定されると図７（ｃ）の画面に遷移する。

また、ノードを１つ選択した状態で、選択ノードを外部接続指定ボタンをクリックすると、図７（ｅ）に示す緯度経度の入力を受け付ける外部接続情報指定画面に遷移する。緯度経度を数値入力するのは難しいため、地図指定ボタンをクリックすると、図７（ｆ）に示す地図画面に遷移し、表示された地図上をクリックすることで、クリックした位置の緯度経度を求めて、図７（ｅ）の緯度経度入力欄に数値が入力される。決定ボタンをクリックすると外部接続ノードの情報が付与されて図７（ｃ）の画面に遷移する。なお、地図から緯度経度を求める際には、外部地図サービスサイトと連携してもよい。

図面データの入力が終了した場合は、図７（ｃ）の完了ボタンをクリックすることで、それまでに編集されたデータがＸＭＬ形式のデータに変換されてサーバ１１２に送信される。

以上のような端末１１１Ａ，１１１Ｂで動作するアプリケーションプログラムは、ＧＵＩを持つ計算機システムの標準的な機能を組み合わせることで実施できる。あるいは、ＨＴＭＬ５と一般にはＪＡＶＡＳＣＲＩＰＴ（登録商標）と呼ばれるＥＣＭＡｓｃｒｉｐｔの規定に準拠したブラウザを利用することも可能である。実際、ＨＴＭＬで構成可能なボタン等の画面上の部品に加えて、ＨＴＭＬ５で規定されるＳＶＧ（Ｓｃａｌａｂｌｅ Ｖｅｃｔｏｒ Ｇｒａｐｈｉｃｓ）では、画像、線分、多角形、円等の図形をオブジェクトとして表現することが可能であり、それらのオブジェクトは、適切なＪａｖａｓｃｒｉｐｔによるプログラムを通じて、利用者のポインティングデバイスの操作に応じた新規作成、移動、変更、削除等の処理を行うことができる。

次に、経路検索処理について説明する。

経路検索処理は、利用者から出発地と目的地を入力して開始される。各地点が施設内の場合は、その施設に対応するネットワークデータと図面データとその図面データ上の座標値を入力し、各地点が屋外の場合は、屋外であることを示すデータとその地点の緯度経度を入力する。以下に、いくつかの入力方法の具体例を説明する。

第１の入力方法は、利用者がＩＤや数値を直接入力する方法である。ローカルネットワークデータを識別するローカルネットワークデータＩＤ、図面データを識別する図面データＩＤ、図面データ内の座標値を示す数値の入力を促す画面を利用者に対して提示し、利用者がキーボードを用いて入力する。なお、屋外の地点を指定する場合は、ローカルネットワークデータＩＤとして予め定められた屋外を示すキーワード（例えば「ｇｌｏｂａｌ」）を入力し、座標値として緯度経度の数値を入力する。この場合、図面データＩＤは任意とする。

第２の入力方法は、利用者がポインティングデバイスを用いて各地点を指定する方法である。ローカルネットワークデータ蓄積部１２０が蓄積しているローカルネットワークデータの一覧を取得し、その一覧から利用者がポインティングデバイスの操作により１つを選択する。続いて、選択されたローカルネットワークデータの図面データ一覧をローカルネットワークデータ蓄積部１２０から取得し、その一覧から利用者がポインティングデバイスの操作により１つを選択する。そして、選択された図面データの画像データを表示し、その画像上の一点を利用者がポインティングデバイスにより指定することで位置を入力する。なお、屋外の地点を指定するために、ローカルネットワークデータの一覧に対して屋外を示す項目（例えば「ｇｌｏｂａｌ」）を追加しておく。利用者が屋外の地点を指定する場合は、ローカルネットワークデータの一覧から「ｇｌｏｂａｌ」を選択し、外部地図サービスサイトを利用して地図上の一点を指定し、緯度経度を入力する。

第３の入力方法は、各ＩＤ、座標値を予めコード化しておく方法である。予め施設内の店舗などの位置に関するローカルネットワークデータ、図面データ、座標値を調べておき、決められたフォーマットでコード化しておく。コード化の具体例としては、「図面上のＸ座標値，図面上のＹ座標値＠図面データＩＤ＠ローカルネットワークデータＩＤ」、「urn:ローカルネットワークデータＩＤ／図面データＩＤ？図面上のＸ座標値，図面上のＹ座標値」などが考えられる。

所定の地点の情報をコード化したデータを店舗等のＷｅｂサイト上にＨＴＭＬにより記述されたページ内にハイパーリンクの形式として埋め込んでおくと、目的地を指定する際に有効である。利用者は、店舗等の検索を行った後、このハイパーリンクをクリックすることによって、その店舗を目的地として指定できる。

また、ある地点の情報をコード化したデータを携帯端末によって読み取り可能な媒体に書き込み、その媒体をコード化した地点に設置しておくと、現在位置を出発地として指定する際に有効である。具体的には、２次元バーコードとしてコード化し、そのバーコードを印刷した表示板を設置し、携帯端末でバーコードを読み取り現在位置を取得する方法、ＩＣタグにコード化したデータを書き込み、近接無線の読取装置を備えた携帯端末をＩＣタグにかざしてデータを読み取り現在位置を取得する方法、数ｍ程度の出力範囲を持った無線発信装置を設置してコード化されたデータを常時発信しておき、無線データを受信可能な携帯端末によりデータを受信して現在位置を取得する方法などがある。また全ての設置地点におけるコード化されたデータを一意に識別できる設置地点ＩＤを付与してデータベースサーバで管理し、設置地点ＩＤを上記の方法で印刷、書き込み、発信しておき、携帯端末で設置地点ＩＤを取得し、データベースサーバにアクセスしてコード化されたデータに変換してもよい。

なお、出発地と目的地それぞれの入力で異なる入力方法を用いてもよい。例えば、目的地は検索された店舗に対するハイパーリンクにより入力し、出発地は２次元バーコードにより入力する。また、屋外の地点を指定する場合は、ＧＰＳを備えた携帯端末により緯度経度を取得してもよい。その際には、ローカルネットワークデータＩＤとして屋外を示すキーワードを用いる。

出発地と目的地が入力されると経路検索処理が開始される。

経路検索処理では、出発地と目的地が属するネットワークデータについて検査し、（１）出発地も目的地も屋外の場合、（２）出発地と目的地が同じローカルネットワークデータに属する場合、（３）出発地が屋外で目的地がローカルネットワークデータに属する場合、（４）目的地が屋外で出発地がローカルネットワークデータに属する場合、（５）出発地と目的地が互いに異なるローカルネットワークデータに属する場合、の５パターンに分類して経路検索処理を行う。

（１）出発地も目的地も屋外の場合は、緯度経度で指定された２地点間の従来の経路探索になるので、広域経路探索部１４０により経路探索を行う。

（２）出発地と目的地が同じローカルネットワークデータに属する場合は、ローカル経路探索部１３０により経路探索を行う。

（３）出発地が屋外で目的地がローカルネットワークデータに属する場合は、目的地のローカルネットワークデータの外部接続ノードを取得し、ローカル経路探索部１３０が各外部接続ノードから目的地までの経路探索を行い、広域経路探索部１４０が出発地から各外部接続ノードまでの経路探索を行う。そして、統合経路探索部１５０がそれぞれの経路探索結果の距離（リンクコスト）の和が最も小さくなる経路を経路探索結果とする。図８に示すフローチャートを用いて説明する。

まず、目的地Ｄのローカルネットワークデータの外部接続ノードＤｅｎｔ［１］，Ｄｅｎｔ［２］，・・・，Ｄｅｎｔ［ｎ］を取得する（ステップＳ１１）。

ローカル経路探索部１３０が、外部接続ノードＤｅｎｔ［１］，Ｄｅｎｔ［２］，・・・，Ｄｅｎｔ［ｎ］それぞれについて、目的地Ｄとの間の経路を探索し、経路Ｐｌｏｃａｌ［ｋ］と距離Ｑｌｏｃａｌ［ｋ］（ｋ＝１，２，・・・，ｎ）を取得する（ステップＳ１２）。

広域経路探索部１４０が、外部接続ノードＤｅｎｔ［１］，Ｄｅｎｔ［２］，・・・，Ｄｅｎｔ［ｎ］それぞれについて、出発地Ｓとの間の経路を探索し、経路Ｐｇｌｏｂａｌ［ｋ］と距離Ｑｇｌｏｂａｌ［ｋ］（ｋ＝１，２，・・・，ｎ）を取得する（ステップＳ１３）。広域経路探索部１４０は、出発地Ｓの緯度経度と外部接続ノードＤｅｎｔ［１］，Ｄｅｎｔ［２］，・・・，Ｄｅｎｔ［ｎ］の緯度経度を用いて経路探索を行う。

そして、統合経路探索部１５０が、外部接続ノードＤｅｎｔ［１］，Ｄｅｎｔ［２］，・・・，Ｄｅｎｔ［ｎ］それぞれについて、経路探索結果の距離を結合する（ステップＳ１４）。結合結果Ｑ［ｋ］（ｋ＝１，２，・・・，ｎ）は、Ｑ［ｋ］＝Ｑｇｌｏｂａｌ［ｋ］＋Ｑｌｏｃａｌ［ｋ］で求める。

Ｑ［１］，Ｑ［２］，・・・，Ｑ［ｎ］から最小となるＱ［ｋ１］を選択し（ステップＳ１５）、経路Ｐｇｌｏｂａｌ［ｋ１］と経路Ｐｌｏｃａｌ［ｋ１］を経路探索結果として出力する（ステップＳ１６）。

これにより、出発地から目的地までの経路が重畳された屋外の地図と施設内の図面を含む複数枚の図面が出力結果として表示される。

（４）目的地が屋外で出発地がローカルネットワークデータに属する場合は、上記（３）の場合の目的地と出発地を入れ替えて同様の処理を行う。図９に、目的地が屋外で出発地がローカルネットワークデータに属する場合の経路探索処理のフローチャートを示す。図８のフローチャートとほぼ同じ処理内容であるのでここでの説明は省略する。

（５）出発地と目的地が互いに異なるローカルネットワークデータに属する場合は、出発地、目的地のローカルネットワークデータの外部接続ノードを取得し、ローカル経路探索部１３０が出発地、目的地それぞれについて各外部接続ノードまでの経路探索を行い、広域経路探索部１４０が出発地、目的地それぞれの各外部接続ノード間の経路探索を行う。そして、統合経路探索部１５０がそれぞれの経路探索結果の距離（リンクコスト）の和が最も小さくなる経路を経路探索結果とする。図１０に示すフローチャートを用いて説明する。

出発地Ｓのローカルネットワークデータの外部接続ノードＳｅｎｔ［１］，Ｓｅｎｔ［２］，・・・，Ｓｅｎｔ［ｍ］と、目的地Ｄのローカルネットワークデータの外部接続ノードＤｅｎｔ［１］，Ｄｅｎｔ［２］，・・・，Ｄｅｎｔ［ｎ］を取得する（ステップＳ３１，Ｓ３２）。

ローカル経路探索部１３０が、出発地の外部接続ノードＳｅｎｔ［１］，Ｓｅｎｔ［２］，・・・，Ｓｅｎｔ［ｍ］それぞれについて、出発地Ｓとの間の経路を探索し、経路Ｐｌｏｃａｌ０［ｊ］と距離Ｑｌｏｃａｌ０［ｊ］（ｊ＝１，２，・・・，ｍ）を取得する（ステップＳ３３）。

ローカル経路探索部１３０が、目的地の外部接続ノードＤｅｎｔ［１］，Ｄｅｎｔ［２］，・・・，Ｄｅｎｔ［ｎ］それぞれについて、目的地Ｄとの間の経路を探索し、経路Ｐｌｏｃａｌ１［ｋ］と距離Ｑｌｏｃａｌ１［ｋ］（ｋ＝１，２，・・・，ｎ）を取得する（ステップＳ３４）。

広域経路探索部１４０が、出発地の外部接続ノードＳｅｎｔ［１］，Ｓｅｎｔ［２］，・・・，Ｓｅｎｔ［ｍ］それぞれと目的地の外部接続ノードＤｅｎｔ［１］，Ｄｅｎｔ［２］，・・・，Ｄｅｎｔ［ｎ］それぞれと間の経路（ｍ×ｎ通り）を探索し、経路Ｐｇｌｏｂａｌ［ｊ，ｋ］と距離Ｑｇｌｏｂａｌ［ｊ，ｋ］（ｊ＝１，２，・・・，ｍ，ｋ＝１，２，・・・，ｎ）を取得する（ステップＳ３５）。

そして、統合経路探索部１５０が、経路探索結果の距離を結合する（ステップＳ３６）。結合結果Ｑ［ｊ，ｋ］（ｊ＝１，２，・・・，ｍ，ｋ＝１，２，・・・，ｎ）は、Ｑ［ｊ，ｋ］＝Ｑｇｌｏｂａｌ［ｊ，ｋ］＋Ｑｌｏｃａｌ０［ｊ］＋Ｑｌｏｃａｌ１［ｋ］で求める。

Ｑ［１，１］，Ｑ［１，２］，・・・，Ｑ［ｍ，ｎ］から最小となるＱ［ｊ１，ｋ１］を選択し（ステップＳ３７）、経路Ｐｌｏｃａｌ０［ｊ１］と経路Ｐｇｌｏｂａｌ［ｊ１，ｋ１］と経路Ｐｌｏｃａｌ１［ｋ１］を経路探索結果として出力する（ステップＳ３８）。

広域経路探索部１４０が、出発地の外部接続ノードと目的地の外部接続ノードの全ての組み合わせについて経路探索を行うと、ｍ×ｎ回の広域経路探索処理が必要となる。一般に広域経路探索処理は計算処理量が大きい。そこで最短（リンクコスト和最小）でない可能性を許容し、ある程度候補を減らした場合は計算処理量の削減が見込まれる。

広域経路探索処理の回数を減らす方法としては、例えば、広域経路探索処理を行う前に、出発地の外部接続ノードと目的地の外部接続ノードの各点間の直線距離を単純に算出し、その直線距離を昇順にソートした場合のＮ_ｍａｘ番目以下の組み合わせに対してのみ、広域経路探索処理を行う。Ｎ_ｍａｘ＜ｍ×ｎとすることで、広域経路探索処理の回数を減らすことができる。

別の方法としては、目的地の外部接続ノードの経度緯度の平均を求めて代表目的地点とし、出発地の外部接続ノードと代表目的地点との間の広域経路探索処理を行い、距離の短いものからｍ０個を選択して出発地の外部接続ノードの候補とする。同様に、代表出発地点を求めて代表出発地点と目的地の外部接続ノードとの間の広域経路探索処理を行い、距離の短いものからｎ０個を選択して目的地の外部接続ノードの候補とする。そして、ｍ０個の出発地の外部接続ノードの候補とｎ０個の目的地の外部接続ノードの候補と間で広域経路探索処理を行う。このようにして候補を絞ることで、広域経路探索処理の回数をｍ０×ｎ０＋ｍ＋ｎ回とすることができる。ｍ０，ｎ０をｍ，ｎに比べて十分小さくすることで、広域経路探索処理の回数を減らすことができる。

次に、経路探索結果の出力形態について説明する。

本実施の形態では、経路探索結果として、出発地と目的地間の距離、あるいは探索に利用された所要時間等のリンクコストの和と、出発地から目的地までの経路が背景地図画面に重畳された画像データが出力される。図１１（ａ）に示すように、経路探索装置１００から出力された画像データは、Ｗｅｂサーバ２１０による配信機能を利用してネットワーク２００に接続されたＰＣや携帯端末などの利用者端末２２０上に表示される。

また、図１１（ｂ）に示すように、経路探索結果として、探索された経路を示す経路線分列データを出力し、Ｗｅｂサーバ２１０が地図サーバ２３０から背景図面画像データを受信して経路線分列データと重畳し、利用者端末２２０からの拡大・縮小・スクロール操作を実現してもよい。このようなＷｅｂアプリは、利用者端末２２０における操作によって決められる表示したい領域のパラメータをＨＴＴＰリクエストに合わせて受け取り、そのパラメータによって指定された領域の地図データ（屋外経路の場合）、背景図面画像データ（施設内経路の場合）の必要領域を切り出し、経路探索結果の経路線分列データのうち当該領域にかかるデータのみを取り出して図面に重畳させ、その結果をＨＴＴＰレスポンスとして利用者端末２２０に返信する。

施設内の背景図面画像データとして正確な図面でなく、デフォルメされたフロア図を用いてもよい。この場合、画像データから図面内リンクの正確な実距離を計算することはできないので、図面内リンクによっては実際の距離とは異なる値がリンクコストとして与えられる。そのため、探索された経路が必ずしも最短ではない可能性もある。しかしながら、必ずしも最短経路を求めるのではなく、実用上問題ない範囲で経路探索を行うのであれば、デフォルメされた画像データを用いた探索結果でも十分である。むしろ、デフォルメにより、より理解しやすいフロア図となり、人が暗黙に理解する通路と整合がとれた経路探索結果を表示できる。また、施設管理者にとっては、必ずしも実測に基づく正確な図面の画像データを用意する必要がなくなる。

以上説明したように、本実施の形態によれば、施設内の経路を探索するためのローカルネットワークデータを蓄積し、施設の出入り口に相当するノードに緯度経度を付与しておき、経路探索の際に、出発地、目的地それぞれが属するネットワークデータが異なる場合は、それぞれのネットワークデータにより外部接続ノードを経由した経路探索を行い、その経路探索結果をつなぎ合わせることで、施設内を含む最適な経路探索を行うことができる。

また、本実施の形態によれば、ローカルネットワークデータが屋外のネットワークデータに接続する外部接続ノードの情報を有し、ローカルネットワークデータ蓄積部１２０が施設毎にローカルネットワークデータを蓄積しておき、ローカルネットワークデータを登録するローカルネットワークデータ登録部１１０を備えることで、施設管理者が他の施設とはまったく独立して自身が管理する施設に関するローカルネットワークデータを登録することが可能となり、ローカルネットワークデータの整合性については個々の施設についてのみ行えばよい。その結果、各施設管理者により柔軟にローカルネットワークデータの更新ができ、利用者は常に最新のローカルネットワークデータに基づく経路探索が期待できる。

１００…経路探索装置
１１０…ローカルネットワークデータ登録部
１１１Ａ，１１１Ｂ…端末
１１２…サーバ
１１３…ネットワーク
１２０…ローカルネットワークデータ蓄積部
１３０…ローカル経路探索部
１４０…広域経路探索部
１５０…統合経路探索部
２００…ネットワーク
２１０…Ｗｅｂサーバ
２２０…利用者端末
２３０…地図サーバ

Claims (7)

1. 経路探索対象の２地点の入力を受け付けて、２地点間の経路を探索する経路探索装置であって、
   施設内の経路探索に用いるための、広域経路探索に用いる広域ネットワークデータに接続する前記施設の出入り口に対応し、緯度経度のデータが付与された外部接続ノードを有するローカルネットワークデータを施設毎に蓄積したローカルネットワークデータ蓄積手段と、
   施設内に経路探索対象の施設内地点が指定されたときに、当該施設内地点を含む前記ローカルネットワークデータを前記ローカルネットワークデータ蓄積手段から読み出して、当該施設内地点と前記施設の前記外部接続ノードそれぞれとの間の経路探索を行うローカル経路探索手段と、
   前記広域ネットワークデータ内に経路探索対象の広域地点が指定されたときに、当該広域地点の緯度経度のデータと前記外部接続ノードの緯度経度のデータを外部のサーバに送信して広域の経路探索結果を受信する広域経路探索手段と、
   同じ前記外部接続ノードを持つ前記ローカル経路探索手段の探索結果と前記広域経路探索手段の探索結果を統合して経路探索結果として出力する経路統合手段と、
   を有することを特徴とする経路探索装置。
2. 経路探索対象の２地点として異なる第１、第２の施設内の施設内地点が指定された場合、
   前記ローカル経路探索手段は、前記第１、第２の施設内の施設内地点のそれぞれについて前記外部接続ノードそれぞれとの間の経路探索を行い、
   前記広域経路探索手段は、前記第１、第２の施設それぞれの前記外部接続ノード間の広域経路探索を行い、
   前記経路統合手段は、前記第１の施設についての経路探索の探索結果と前記広域経路探索手段の探索結果と前記第２の施設についての経路探索の探索結果を統合して経路探索結果として出力すること
   を特徴とする請求項１記載の経路探索装置。
3. 前記広域経路探索手段は、前記第１、第２の施設の前記外部接続ノード間の経路が短くなると推定される前記外部接続ノードを抽出し、抽出した前記外部接続ノード間についてのみ広域経路探索を行うことを特徴とする請求項２記載の経路探索装置。
4. 前記施設毎に前記ローカルネットワークデータを受け付けて前記ローカルネットワークデータ蓄積手段に蓄積するローカルネットワークデータ登録手段を有することを特徴とする請求項１乃至３のいずれかに記載の経路探索装置。
5. 施設内の経路探索に用いるための、広域経路探索に用いる広域ネットワークデータに接続する前記施設の出入り口に対応し、緯度経度のデータが付与された外部接続ノードを有するローカルネットワークデータを施設毎に蓄積したローカルネットワークデータ蓄積手段、ローカル経路探索手段、広域経路探索手段、及び経路統合手段を備えた経路探索装置によって実行される、経路探索対象の２地点の入力を受け付けて、２地点間の経路を探索する経路探索方法であって、
   前記ローカル経路探索手段による、施設内に経路探索対象の施設内地点が指定されたときに、当該施設内地点を含む前記ローカルネットワークデータを前記ローカルネットワークデータ蓄積手段から読み出して、当該施設内地点と前記施設の前記外部接続ノードそれぞれとの間の経路探索を行うステップと、
   前記広域経路探索手段による、前記広域ネットワークデータ内に経路探索対象の広域地点が指定されたときに、当該広域地点の緯度経度のデータと前記外部接続ノードの緯度経度のデータを外部のサーバに送信して広域の経路探索結果を受信するステップと、
   前記経路統合手段による、同じ前記外部接続ノードを持つ前記ローカル経路探索手段の探索結果と前記広域経路探索手段の探索結果を統合して経路探索結果として出力するステップと、
   を有することを特徴とする経路探索方法。
6. 経路探索対象の２地点として異なる第１、第２の施設内の施設内地点が指定された場合、
   前記ローカル経路探索手段は、前記第１、第２の施設内の施設内地点のそれぞれについて前記外部接続ノードそれぞれとの間の経路探索を行い、
   前記広域経路探索手段は、前記第１、第２の施設それぞれの前記外部接続ノード間の広域経路探索を行い、
   前記経路統合手段は、前記第１の施設についての経路探索の探索結果と前記広域経路探索手段の探索結果と前記第２の施設についての経路探索の探索結果を統合して経路探索結果として出力すること
   を特徴とする請求項５記載の経路探索方法。
7. 請求項１乃至４のいずれかに記載の経路探索装置としてコンピュータを動作させることを特徴とする経路探索プログラム。

Images