Notice: Undefined variable: fterm_desc_sub in /mnt/www/biblio_conv.php on line 353
経路探索装置、経路探索方法及び経路探索プログラム
説明

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

【課題】施設内の地点を出発地、目的地として指定可能な経路探索を提供する。
【解決手段】施設内の経路を探索するためのローカルネットワークデータを蓄積し、施設の出入り口に相当するノードに緯度経度を付与しておき、経路探索の際に、出発地、目的地それぞれが属するネットワークデータが異なる場合は、それぞれのネットワークデータにより外部接続ノードを経由した経路探索を行い、その経路探索結果をつなぎ合わせる。これにより、施設内を含む最適な経路探索を行うことができる。

【発明の詳細な説明】
【技術分野】
【0001】
本発明は、経路を探索する技術に関する。
【背景技術】
【0002】
現在では、例えば、カーナビゲーションシステムやネットワーク上の地図サービスにおいて、出発地から目的地までの2地点間の経路を求めて表示することが実現されている。このような2地点間の経路を求めることは古くから知られた技術であり、その技術の核となるのは、主に交差点に対応する点をノードとし、それらノード間で通行可能な道をリンクとし、各リンクにその距離(あるいは通過に必要な時間)をコストとして割り当て、ノードとリンクの接続状態を表すデータをグラフとみなしてグラフ理論を適用することである。例えば、2つのノード間の最短距離を求めるアルゴリズムとして、「ダイクストラ法」(非特許文献1)や「A*法」(非特許文献2)などの技術が知られている。非特許文献1,2の方法は、ノード間、すなわち交差点から交差点までの最短経路を求める技術であるが、その方法を拡張して任意の2地点間の最短経路を求めることも容易である。以下、簡単にその方法を説明する。
【0003】
まず、図12(a)に示すように、出発地Sと目的地Dの座標が指定される。
【0004】
続いて、図12(b)に示すように、出発地Sから最も近傍となるリンク(この場合、N1−N3リンク)上の近傍点S’を求め、N1−N3リンクを分割してノードにS’を追加する。S’からN1への距離をL1、S’からN3への距離をL3とすると、L1:L3の比に応じて、N1−N3リンクのコストを分配して、N1−S’リンクとS’−N3リンクのコストとして割り当てる。同様に、目的地Dから近傍点D’を求めてノードD’を追加する。
【0005】
そして、図12(c)に示すように、ノードN1,・・・,N9,S’,D’からなるグラフに対して、非特許文献1,2の方法を適用してノードS’−D’間の最短経路を求め、S−S’、D−D’を追加し、S−D間の最短経路とする。
【0006】
人は、地図を見るだけで、暗黙のうちに経路を理解することが容易にできるが、計算機等で、上記のような経路探索を行うためには、整合性のとれたグラフ構造をなすノードとリンクのデータ(ネットワークデータ)が必要となり、しかも探索された経路上のリンクを地図画像に重畳して出力するためには、そのリンクの位置と、人が暗黙のうちに理解する経路の位置に大きなずれが生じていないことが必要条件となる。このため、カーナビや地図サービスにおいては、デジタル地図データの供給者によって、一元的に、必要なネットワークデータも作成されて供給されることが一般的である。特に、近年では、歩行者の利用も考慮し、歩行者専用通路を含むネットワークデータが整備され、供給されている。
【先行技術文献】
【非特許文献】
【0007】
【非特許文献1】Dijkstra, E. W. "A note on two problems in connexion with graphs.", Numerische Mathematik, 1(1959), S.269-271
【非特許文献2】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
【発明の概要】
【発明が解決しようとする課題】
【0008】
しかしながら、デジタル地図データの供給者によるネットワークデータ作成では、屋内施設やビル構内などのネットワークデータは供給されない。あるいは供給されるとしても、特定のターミナル駅構内など、非常に限定された対象に限られる。これは、デジタル地図データの供給者は、航空写真などの情報をベースにデータ作成することが多く、屋内施設のデータを作成するための調査効率が悪いこと、屋内は通常私有地であり、調査のための所有者の許可を得る手続が個別に必要であることなどの理由がある。さらに、デジタル地図データの供給者により提供されるネットワークデータは、非常に規模が大きいために必要な整合性の確認などを経てから提供・市販されるため、実際にそのようなデータが利用可能になるまで、数ヶ月といったレベルの期間がかかる。屋外の例えば道路等は建設に相当な時間がかかるため、このようなレベルの更新期間であっても問題はないが、屋内、特に施設内の通路等は、簡易な改装で頻繁に変更されることがあり、すぐに経路探索結果に反映されることが期待され、数ヶ月レベルの更新期間では問題となる。
【0009】
一方で、施設管理者自身が施設内のネットワークデータを用意することも可能である。この場合、通常、特に許可を改めて得る必要はなく、また施設管理者は多くの場合施設の図面等を保持していることや、そもそも施設内を熟知していることから、特別な調査も不要である。また、規模が限られているため、データの整合性の確認も容易であり、短期間で利用者に対して経路探索サービスを提供することも可能である。このため、施設内の改装等に伴う変化にも柔軟に対応できる。
【0010】
しかしながら、当然、この場合は、経路探索が可能となる範囲は、その施設内に限定されてしまう。そのため、屋外の出発地から施設内の目的地までの経路探索、施設内の出発地から屋外の目的地への経路探索、あるいは、ある施設内の出発地から別の施設内の目的地への経路探索をすることができない。
【0011】
本発明は、上記に鑑みてなされたものであり、施設内の地点を出発地、目的地として指定可能な経路探索を提供することを目的とする。
【課題を解決するための手段】
【0012】
第1の本発明に係る経路探索装置は、経路探索対象の2地点の入力を受け付けて、2地点間の経路を探索する経路探索装置であって、施設内の経路探索に用いるための、広域経路探索に用いる広域ネットワークデータに接続する前記施設の出入り口に対応した外部接続ノードを有するローカルネットワークデータを施設毎に蓄積したローカルネットワークデータ蓄積手段と、施設内に経路探索対象の施設内地点が指定されたときに、当該施設内地点を含む前記ローカルネットワークデータを前記ローカルネットワークデータ蓄積手段から読み出して、当該施設内地点と前記施設の前記外部接続ノードそれぞれとの間の経路探索を行うローカル経路探索手段と、前記広域ネットワークデータ内に経路探索対象の広域地点が指定されたときに、当該広域地点と前記外部接続ノードとの間の広域経路探索を行う広域経路探索手段と、同じ前記外部接続ノードを持つ前記ローカル経路探索手段の探索結果と前記広域探索手段の探索結果を統合して経路探索結果として出力する経路統合手段と、を有することを特徴とする。
【0013】
上記経路探索装置において、経路探索対象の2地点として異なる第1、第2の施設内の施設内地点が指定された場合、前記ローカル経路探索手段は、前記第1、第2の施設内の施設内地点のそれぞれについて前記外部接続ノードそれぞれとの間の経路探索を行い、前記広域探索手段は、前記第1、第2の施設それぞれの前記外部接続ノード間の広域経路探索を行い、前記経路統合手段は、前記第1の施設についての経路探索の探索結果と前記広域探索手段の探索結果と前記第2の施設についての経路探索の探索結果を統合して経路探索結果として出力することを特徴とする。
【0014】
上記経路探索装置において、前記広域探索手段は、前記第1、第2の施設の前記外部接続ノード間の経路が短くなると推定される前記外部接続ノードを抽出し、抽出した前記外部接続ノード間についてのみ広域経路探索を行うことを特徴とする。
【0015】
上記経路探索装置において、前記施設毎に前記ローカルネットワークデータを受け付けて前記ローカルネットワークデータ蓄積手段に蓄積するローカルネットワークデータ登録手段を有することを特徴とする。
【0016】
第2の本発明に係る経路探索方法は、経路探索対象の2地点の入力を受け付けて、2地点間の経路を探索する経路探索方法であって、ローカル経路探索手段による、施設内に経路探索対象の施設内地点が指定されたときに、施設内の経路探索に用いるための、広域経路探索に用いる広域ネットワークデータに接続する前記施設の出入り口に対応した外部接続ノードを有するローカルネットワークデータを施設毎に蓄積したローカルネットワークデータ蓄積手段から当該施設内地点を含む前記ローカルネットワークデータを読み出して、当該施設内地点と前記施設の前記外部接続ノードそれぞれとの間の経路探索を行うステップと、広域経路探索手段による、前記広域ネットワークデータ内に経路探索対象の広域地点が指定されたときに、当該広域地点と前記外部接続ノードとの間の広域経路探索を行うステップと、経路統合手段による、同じ前記外部接続ノードを持つ前記ローカル経路探索手段の探索結果と前記広域探索手段の探索結果を統合して経路探索結果として出力するステップと、を有することを特徴とする。
【0017】
上記経路探索方法において、経路探索対象の2地点として異なる第1、第2の施設内の施設内地点が指定された場合、前記ローカル経路探索手段は、前記第1、第2の施設内の施設内地点のそれぞれについて前記外部接続ノードそれぞれとの間の経路探索を行い、前記広域探索手段は、前記第1、第2の施設それぞれの前記外部接続ノード間の広域経路探索を行い、前記経路統合手段は、前記第1の施設についての経路探索の探索結果と前記広域探索手段の探索結果と前記第2の施設についての経路探索の探索結果を統合して経路探索結果として出力することを特徴とする。
【0018】
第3の本発明に係る経路探索プログラムは、上記経路探索装置としてコンピュータを動作させることを特徴とする。
【発明の効果】
【0019】
本発明によれば、施設内の地点を出発地、目的地として指定可能な経路探索を提供することができる。
【図面の簡単な説明】
【0020】
【図1】本実施の形態における経路探索装置の構成を示す機能ブロック図である。
【図2】ローカルネットワークデータのデータ構造を示す図である。
【図3】ローカルネットワークデータを具体的に説明する図である。
【図4】ローカルネットワークデータをXML形式のデータとして表現した例を示す図である。
【図5】ローカルネットワークデータを表形式のデータとして表現した例を示す図である。
【図6】ローカルネットワークデータ登録部の構成例を示す図である。
【図7】ローカルネットワークデータの登録処理をするアプリケーションプログラムの画面例を示す図である。
【図8】出発地が屋外で目的地がローカルネットワークデータに属する場合の経路探索の処理の流れを示すフローチャートである。
【図9】目的地が屋外で出発地がローカルネットワークデータに属する場合の経路探索の処理の流れを示すフローチャートである。
【図10】出発地と目的地が互いに異なるローカルネットワークデータに属する場合の経路探索の処理の流れを示すフローチャートである。
【図11】本実施の形態における経路探索装置を含む全体構成図である。
【図12】グラフ構造を利用して2地点間の最短経路を求める方法を説明する図である。
【発明を実施するための形態】
【0021】
以下、本発明の実施の形態について図面を用いて説明する。
【0022】
図1は、本実施の形態における経路探索装置の構成を示す機能ブロック図である。同図に示す経路探索装置100は、ローカルネットワークデータ登録部110、ローカルネットワークデータ蓄積部120、ローカル経路探索部130、広域経路探索部140、および統合経路探索部150を備える。経路探索装置100が備える各部は、演算処理装置、記憶装置等を備えたコンピュータにより構成して、各部の処理がプログラムによって実行されるものとしてもよい。このプログラムは経路探索装置100が備える記憶装置に記憶されており、磁気ディスク、光ディスク、半導体メモリ等の記録媒体に記録することも、ネットワークを通して提供することも可能である。以下、各部について説明する。
【0023】
ローカルネットワークデータ登録部110は、施設管理者から、その施設管理者が管理する施設内における経路を探索するためのローカルネットワークデータを入力する。ローカルネットワークデータの詳細については後述する。
【0024】
ローカルネットワークデータ蓄積部120は、ローカルネットワークデータ登録部110が入力したローカルネットワークデータを施設毎に蓄積する。
【0025】
ローカル経路探索部130は、同一のローカルネットワークデータ上に存在する出発地と目的地が指定されたときに、ローカルネットワークデータ蓄積部120からローカルネットワークデータを取得して、そのローカルネットワークデータに基づいて出発地と目的地間の経路探索を行う。ローカルネットワークデータ上での出発地、目的地は、ローカルネットワークデータを特定する情報と、そのローカルネットワークデータの図面データを特定する情報と、その図面データ上での、例えば図面データの右上を原点としてピクセル単位で表される座標値で指定する。
【0026】
広域経路探索部140は、緯度経度により指定された2地点間の経路探索を行う。広域経路探索は、デジタル地図データ供給者により提供されたネットワークデータに対して、非特許文献1,2の技術を用いる。あるいは、広域経路探索部140は、広域経路探索の機能を提供しているネットワーク上のサーバを利用して、出発地と目的地の緯度経度を指定して検索要求を送信し、経路探索結果を受信するものでもよい。
【0027】
統合経路探索部150は、ローカル経路探索部130、広域経路探索部140の経路探索結果を統合し、施設内の経路を含む最適な経路探索結果を出力する。
【0028】
次に、ローカルネットワークデータについて説明する。
【0029】
図2は、ローカルネットワークデータのデータ構造を示す図である。ローカルネットワークデータは、背景図面(フロア図等)となる画像データ、画像データに対応して設定されたノード、同一画像データ内のノード間を結ぶ図面内リンクを有する図面データと、図面データ間のノードを結ぶ図面間リンクと、施設の出入り口に相当し、緯度経度のデータが付与された外部接続ノードとを有する。1つの施設に対して1つのローカルネットワークデータが存在する。
【0030】
図3に、ローカルネットワークデータの具体例を示す。同図に示すローカルネットワークデータは、3フロアで構成されるショッピングモールについてのローカルネットワークデータである。このローカルネットワークデータは、ショッピングモールの1F,2F,3Fの各階に対応する3つの図面データがある。各図面データは、各階のフロアマップに相当する画像データを有し、画像データに対応付けて黒丸で示されたノードが設定されている。ノードは、画像データの座標値(例えばピクセル単位で表される値)で設定される。同じフロアで移動可能な通路に相当するノード間には図面内リンクが設定される。また、フロアをまたがるエレベータ、エスカレータ、階段などの通路には、図面間リンクが設定される。図3に示す例では、エレベータに対応して図面間リンクが設定されている。1Fのノードのうち、外部への出入り口に相当する白丸のノードが外部接続ノードとして指定されている。なお、2Fから直接外部のペデストリアンデッキへ出入りできる場合なども考えられるので、外部接続ノードは必ずしも1Fに相当する図面データ内にあるとは限らない。
【0031】
画像データとして、図面ごとに決められた一定の縮尺に基づくほぼ正確な図面の画像データを用いることで、経路の正確な距離を座標値と縮尺から計算できる。図面内リンクについては、図面上の座標値を元に算出された距離にその縮尺の逆数をかけることで実際の距離が算出できる。図面間リンクについては、それぞれのリンクに対し、その移動の負担あるいは所要時間を元に、通常の徒歩での移動の何mの移動に相当するのが妥当か、という値を指定しておく。例えば、1Fから2Fまでエレベータにより移動することは、所要時間を考慮すると、30mの距離を歩くことに相当する、というような数値である。これにより、図面内リンク、図面間リンクともに、リンクコストとして「徒歩で移動することに相当する距離」という値が付与されることになる。
【0032】
図4は、ローカルネットワークデータをXML形式のデータとして表現した例を示す図である。同図に示す例では、network タグで囲まれた部分がローカルネットワークデータを示している。map タグで囲まれた部分が図面データを示し、図4の例では3つの図面データが存在する。図面データ中の image, node, link の要素がそれぞれ画像データ、ノード、図面内リンクを示している。また、extlink, entry の要素はそれぞれ図面間リンク、外部接続ノードを示している。ネットワークデータをXML形式のデータで表現した場合、ローカルネットワークデータ蓄積部120として、ハードディスクなどのファイル単位で読み書き可能な記憶装置を備えた計算機を用い、ローカルネットワークデータごとに1つのファイルとして記憶装置の特定のディレクトリ上に蓄積する入出力プログラムにより構成することができる。
【0033】
また、別の表現方法としては、図5に示すように、表形式のデータとしてローカルネットワークデータを表現することができる。図5(a)は画像データのテーブル例を示し、図5(b)はノードのテーブル例を示し、図5(c)は図面内リンクのテーブル例を示し、図5(d)は図面間リンクのテーブル例を示し、図5(e)は外部接続ノードのテーブル例を示す。ネットワークデータを表形式のデータで表現した場合、データベースマネージメントシステム(DBMS)を用いてテーブルを定義してローカルネットワークデータ蓄積部120を構成することができる。
【0034】
次に、ローカルネットワークデータの登録について説明する。
【0035】
ローカルネットワークデータの登録は、施設管理者により作成された図4に示すようなXML形式のデータを入力することで行う。具体的には、Webサーバとして機能する計算機上に、XMLファイルと画像データをアップロードできるWebページを設け、そのページを通じて施設管理者よりXMLファイルと画像データを受信し、ローカルネットワークデータ蓄積部120に蓄積する。ローカルネットワークデータ蓄積部120では、ローカルネットワークデータをXML形式のデータで蓄積する場合は、入力したXMLファイルをそのまま蓄積すればよく、ローカルネットワークデータを表形式のデータで蓄積する場合は、入力したXMLファイルを解析して表形式のデータに変換し、DBMSの登録機能により蓄積する。なお、偽の施設管理者からのアップロードを避けるための認証、ローカルネットワークデータIDのチェック、蓄積済みデータに対する上書き確認、書き込みエラー等に対する警告表示などの処理も行うが、ここでは通常行われる処理についての説明は省略する。
【0036】
別のローカルネットワークデータの登録方法として、施設管理者がディスプレイに表示された画像データを見ながらマウス等のポインティングデバイスを操作することで、その施設のローカルネットワークデータを登録できるアプリケーションを利用する方法もある。例えば、図6に示すように、ローカルネットワークデータ登録部110を、サーバ112とネットワーク113を介して接続された端末111A,111Bで構成し、端末111A,111B上でアプリケーションプログラムを動作させてローカルネットワークデータを入力する。この場合、各端末111A,111Bで作成されたXML形式のデータをサーバ112が受信してローカルネットワークデータ蓄積部120に登録する。
【0037】
図7に、端末111A,111Bで動作するアプリケーションプログラムの画面例を示して、ローカルネットワークデータの登録処理を説明する。
【0038】
アプリケーションプログラムを起動し、施設、すなわちローカルネットワークデータを識別するIDを指定すると、図7(a)に示す初期画面となる。図7(a)の左側の「1F」「2F」のアイコンは1F、2Fフロアに相当する図面データが登録されていることを示す。
【0039】
図7(a)のMap作成ボタンをクリックすると、図7(b)に示す新規図面登録画面に遷移する。図7(b)で、例えば「3F」などのIDを入力して3Fフロア図に相当する画像ファイルを選択し、アップロードボタンをクリックすると「3F」の図面データが追加されて、図7(a)の画面(ただし、左側に「3F」が追加表示された状態)に戻る。画像ファイルの選択は、選択ボタンをクリックして表示されるダイアログを用いて行う。
【0040】
図7(a)の画面で左側の「1F」等のアイコンをクリックすると、図7(c)に示す図面データ編集画面に遷移する。図面データ編集画面では、選択した図面データのフロア図(画像データ)が表示され、フロア図を見ながら、ノードの作成、削除、リンクの作成、削除などの編集を行うことができる。図面データを選択した状態で、図7(c)の選択Map削除ボタンをクリックすると、選択した図面データが削除される。
【0041】
図7(c)のノード作成ボタンをクリックし、画面の右側に表示されたフロア画像上の任意の点をクリックすると新規のノードがその位置に作成される。フロア画像上のノードをクリックして選択し、ノード削除ボタンをクリックすると選択したノードが削除される。また、ノードをクリックしてドラッグすると、ノードの位置を変更できる。なお、ノードの削除、移動に伴い、そのノードに設定されているリンクも削除、移動する。
【0042】
ノードを2つ選択した状態で、選択ノード間にリンク作成ボタンをクリックすると選択したノード間にリンクが作成される。リンクあるいは両端の2つのノードを選択した状態で、リンク削除ボタンをクリックすると選択したリンクが削除される。
【0043】
ノードを1つ選択した状態で、選択ノードから別Mapノードへのリンク作成ボタンをクリックすると、図7(d)に示すもう一方のノードを指定するための図面間リンク選択画面に遷移する。図7(d)では、「2F」の図面データを選択し、2Fフロアに設定されたノードを指定しようとしている。図面間リンクのもう一方のノードが指定されると図7(c)の画面に遷移する。
【0044】
また、ノードを1つ選択した状態で、選択ノードを外部接続指定ボタンをクリックすると、図7(e)に示す緯度経度の入力を受け付ける外部接続情報指定画面に遷移する。緯度経度を数値入力するのは難しいため、地図指定ボタンをクリックすると、図7(f)に示す地図画面に遷移し、表示された地図上をクリックすることで、クリックした位置の緯度経度を求めて、図7(e)の緯度経度入力欄に数値が入力される。決定ボタンをクリックすると外部接続ノードの情報が付与されて図7(c)の画面に遷移する。なお、地図から緯度経度を求める際には、外部地図サービスサイトと連携してもよい。
【0045】
図面データの入力が終了した場合は、図7(c)の完了ボタンをクリックすることで、それまでに編集されたデータがXML形式のデータに変換されてサーバ112に送信される。
【0046】
以上のような端末111A,111Bで動作するアプリケーションプログラムは、GUIを持つ計算機システムの標準的な機能を組み合わせることで実施できる。あるいは、HTML5と一般にはJavascriptと呼ばれるECMAscriptの規定に準拠したブラウザを利用することも可能である。実際、HTMLで構成可能なボタン等の画面上の部品に加えて、HTML5で規定されるSVG(Scalable Vector Graphics)では、画像、線分、多角形、円等の図形をオブジェクトとして表現することが可能であり、それらのオブジェクトは、適切なJavascriptによるプログラムを通じて、利用者のポインティングデバイスの操作に応じた新規作成、移動、変更、削除等の処理を行うことができる。
【0047】
次に、経路検索処理について説明する。
【0048】
経路検索処理は、利用者から出発地と目的地を入力して開始される。各地点が施設内の場合は、その施設に対応するネットワークデータと図面データとその図面データ上の座標値を入力し、各地点が屋外の場合は、屋外であることを示すデータとその地点の緯度経度を入力する。以下に、いくつかの入力方法の具体例を説明する。
【0049】
第1の入力方法は、利用者がIDや数値を直接入力する方法である。ローカルネットワークデータを識別するローカルネットワークデータID、図面データを識別する図面データID、図面データ内の座標値を示す数値の入力を促す画面を利用者に対して提示し、利用者がキーボードを用いて入力する。なお、屋外の地点を指定する場合は、ローカルネットワークデータIDとして予め定められた屋外を示すキーワード(例えば「global」)を入力し、座標値として緯度経度の数値を入力する。この場合、図面データIDは任意とする。
【0050】
第2の入力方法は、利用者がポインティングデバイスを用いて各地点を指定する方法である。ローカルネットワークデータ蓄積部120が蓄積しているローカルネットワークデータの一覧を取得し、その一覧から利用者がポインティングデバイスの操作により1つを選択する。続いて、選択されたローカルネットワークデータの図面データ一覧をローカルネットワークデータ蓄積部120から取得し、その一覧から利用者がポインティングデバイスの操作により1つを選択する。そして、選択された図面データの画像データを表示し、その画像上の一点を利用者がポインティングデバイスにより指定することで位置を入力する。なお、屋外の地点を指定するために、ローカルネットワークデータの一覧に対して屋外を示す項目(例えば「global」)を追加しておく。利用者が屋外の地点を指定する場合は、ローカルネットワークデータの一覧から「global」を選択し、外部地図サービスサイトを利用して地図上の一点を指定し、緯度経度を入力する。
【0051】
第3の入力方法は、各ID、座標値を予めコード化しておく方法である。予め施設内の店舗などの位置に関するローカルネットワークデータ、図面データ、座標値を調べておき、決められたフォーマットでコード化しておく。コード化の具体例としては、「図面上のX座標値,図面上のY座標値@図面データID@ローカルネットワークデータID」、「urn:ローカルネットワークデータID/図面データID?図面上のX座標値,図面上のY座標値」などが考えられる。
【0052】
所定の地点の情報をコード化したデータを店舗等のWebサイト上にHTMLにより記述されたページ内にハイパーリンクの形式として埋め込んでおくと、目的地を指定する際に有効である。利用者は、店舗等の検索を行った後、このハイパーリンクをクリックすることによって、その店舗を目的地として指定できる。
【0053】
また、ある地点の情報をコード化したデータを携帯端末によって読み取り可能な媒体に書き込み、その媒体をコード化した地点に設置しておくと、現在位置を出発地として指定する際に有効である。具体的には、2次元バーコードとしてコード化し、そのバーコードを印刷した表示板を設置し、携帯端末でバーコードを読み取り現在位置を取得する方法、ICタグにコード化したデータを書き込み、近接無線の読取装置を備えた携帯端末をICタグにかざしてデータを読み取り現在位置を取得する方法、数m程度の出力範囲を持った無線発信装置を設置してコード化されたデータを常時発信しておき、無線データを受信可能な携帯端末によりデータを受信して現在位置を取得する方法などがある。また全ての設置地点におけるコード化されたデータを一意に識別できる設置地点IDを付与してデータベースサーバで管理し、設置地点IDを上記の方法で印刷、書き込み、発信しておき、携帯端末で設置地点IDを取得し、データベースサーバにアクセスしてコード化されたデータに変換してもよい。
【0054】
なお、出発地と目的地それぞれの入力で異なる入力方法を用いてもよい。例えば、目的地は検索された店舗に対するハイパーリンクにより入力し、出発地は2次元バーコードにより入力する。また、屋外の地点を指定する場合は、GPSを備えた携帯端末により緯度経度を取得してもよい。その際には、ローカルネットワークデータIDとして屋外を示すキーワードを用いる。
【0055】
出発地と目的地が入力されると経路検索処理が開始される。
【0056】
経路検索処理では、出発地と目的地が属するネットワークデータについて検査し、(1)出発地も目的地も屋外の場合、(2)出発地と目的地が同じローカルネットワークデータに属する場合、(3)出発地が屋外で目的地がローカルネットワークデータに属する場合、(4)目的地が屋外で出発地がローカルネットワークデータに属する場合、(5)出発地と目的地が互いに異なるローカルネットワークデータに属する場合、の5パターンに分類して経路検索処理を行う。
【0057】
(1)出発地も目的地も屋外の場合は、緯度経度で指定された2地点間の従来の経路探索になるので、広域経路探索部140により経路探索を行う。
【0058】
(2)出発地と目的地が同じローカルネットワークデータに属する場合は、ローカル経路探索部130により経路探索を行う。
【0059】
(3)出発地が屋外で目的地がローカルネットワークデータに属する場合は、目的地のローカルネットワークデータの外部接続ノードを取得し、ローカル経路探索部130が各外部接続ノードから目的地までの経路探索を行い、広域経路探索部140が出発地から各外部接続ノードまでの経路探索を行う。そして、統合経路探索部150がそれぞれの経路探索結果の距離(リンクコスト)の和が最も小さくなる経路を経路探索結果とする。図8に示すフローチャートを用いて説明する。
【0060】
まず、目的地Dのローカルネットワークデータの外部接続ノードDent[1],Dent[2],・・・,Dent[n]を取得する(ステップS11)。
【0061】
ローカル経路探索部130が、外部接続ノードDent[1],Dent[2],・・・,Dent[n]それぞれについて、目的地Dとの間の経路を探索し、経路Plocal[k]と距離Qlocal[k](k=1,2,・・・,n)を取得する(ステップS12)。
【0062】
広域経路探索部140が、外部接続ノードDent[1],Dent[2],・・・,Dent[n]それぞれについて、出発地Sとの間の経路を探索し、経路Pglobal[k]と距離Qglobal[k](k=1,2,・・・,n)を取得する(ステップS13)。広域経路探索部140は、出発地Sの緯度経度と外部接続ノードDent[1],Dent[2],・・・,Dent[n]の緯度経度を用いて経路探索を行う。
【0063】
そして、統合経路探索部150が、外部接続ノードDent[1],Dent[2],・・・,Dent[n]それぞれについて、経路探索結果の距離を結合する(ステップS14)。結合結果Q[k](k=1,2,・・・,n)は、Q[k]=Qglobal[k]+Qlocal[k]で求める。
【0064】
Q[1],Q[2],・・・,Q[n]から最小となるQ[k1]を選択し(ステップS15)、経路Pglobal[k1]と経路Plocal[k1]を経路探索結果として出力する(ステップS16)。
【0065】
これにより、出発地から目的地までの経路が重畳された屋外の地図と施設内の図面を含む複数枚の図面が出力結果として表示される。
【0066】
(4)目的地が屋外で出発地がローカルネットワークデータに属する場合は、上記(3)の場合の目的地と出発地を入れ替えて同様の処理を行う。図9に、目的地が屋外で出発地がローカルネットワークデータに属する場合の経路探索処理のフローチャートを示す。図8のフローチャートとほぼ同じ処理内容であるのでここでの説明は省略する。
【0067】
(5)出発地と目的地が互いに異なるローカルネットワークデータに属する場合は、出発地、目的地のローカルネットワークデータの外部接続ノードを取得し、ローカル経路探索部130が出発地、目的地それぞれについて各外部接続ノードまでの経路探索を行い、広域経路探索部140が出発地、目的地それぞれの各外部接続ノード間の経路探索を行う。そして、統合経路探索部150がそれぞれの経路探索結果の距離(リンクコスト)の和が最も小さくなる経路を経路探索結果とする。図10に示すフローチャートを用いて説明する。
【0068】
出発地Sのローカルネットワークデータの外部接続ノードSent[1],Sent[2],・・・,Sent[m]と、目的地Dのローカルネットワークデータの外部接続ノードDent[1],Dent[2],・・・,Dent[n]を取得する(ステップS31,S32)。
【0069】
ローカル経路探索部130が、出発地の外部接続ノードSent[1],Sent[2],・・・,Sent[m]それぞれについて、出発地Sとの間の経路を探索し、経路Plocal0[j]と距離Qlocal0[j](j=1,2,・・・,m)を取得する(ステップS33)。
【0070】
ローカル経路探索部130が、目的地の外部接続ノードDent[1],Dent[2],・・・,Dent[n]それぞれについて、目的地Dとの間の経路を探索し、経路Plocal1[k]と距離Qlocal1[k](k=1,2,・・・,n)を取得する(ステップS34)。
【0071】
広域経路探索部140が、出発地の外部接続ノードSent[1],Sent[2],・・・,Sent[m]それぞれと目的地の外部接続ノードDent[1],Dent[2],・・・,Dent[n]それぞれと間の経路(m×n通り)を探索し、経路Pglobal[j,k]と距離Qglobal[j,k](j=1,2,・・・,m,k=1,2,・・・,n)を取得する(ステップS35)。
【0072】
そして、統合経路探索部150が、経路探索結果の距離を結合する(ステップS36)。結合結果Q[j,k](j=1,2,・・・,m,k=1,2,・・・,n)は、Q[j,k]=Qglobal[j,k]+Qlocal0[j]+Qlocal1[k]で求める。
【0073】
Q[1,1],Q[1,2],・・・,Q[m,n]から最小となるQ[j1,k1]を選択し(ステップS37)、経路Plocal0[j1]と経路Pglobal[j1,k1]と経路Plocal1[k1]を経路探索結果として出力する(ステップS38)。
【0074】
広域経路探索部140が、出発地の外部接続ノードと目的地の外部接続ノードの全ての組み合わせについて経路探索を行うと、m×n回の広域経路探索処理が必要となる。一般に広域経路探索処理は計算処理量が大きい。そこで最短(リンクコスト和最小)でない可能性を許容し、ある程度候補を減らした場合は計算処理量の削減が見込まれる。
【0075】
広域経路探索処理の回数を減らす方法としては、例えば、広域経路探索処理を行う前に、出発地の外部接続ノードと目的地の外部接続ノードの各点間の直線距離を単純に算出し、その直線距離を昇順にソートした場合のNmax番目以下の組み合わせに対してのみ、広域経路探索処理を行う。Nmax<m×nとすることで、広域経路探索処理の回数を減らすことができる。
【0076】
別の方法としては、目的地の外部接続ノードの経度緯度の平均を求めて代表目的地点とし、出発地の外部接続ノードと代表目的地点との間の広域経路探索処理を行い、距離の短いものからm0個を選択して出発地の外部接続ノードの候補とする。同様に、代表出発地点を求めて代表出発地点と目的地の外部接続ノードとの間の広域経路探索処理を行い、距離の短いものからn0個を選択して目的地の外部接続ノードの候補とする。そして、m0個の出発地の外部接続ノードの候補とn0個の目的地の外部接続ノードの候補と間で広域経路探索処理を行う。このようにして候補を絞ることで、広域経路探索処理の回数をm0×n0+m+n回とすることができる。m0,n0をm,nに比べて十分小さくすることで、広域経路探索処理の回数を減らすことができる。
【0077】
次に、経路探索結果の出力形態について説明する。
【0078】
本実施の形態では、経路探索結果として、出発地と目的地間の距離、あるいは探索に利用された所要時間等のリンクコストの和と、出発地から目的地までの経路が背景地図画面に重畳された画像データが出力される。図11(a)に示すように、経路探索装置100から出力された画像データは、Webサーバ210による配信機能を利用してネットワーク200に接続されたPCや携帯端末などの利用者端末220上に表示される。
【0079】
また、図11(b)に示すように、経路探索結果として、探索された経路を示す経路線分列データを出力し、Webサーバ210が地図サーバ230から背景図面画像データを受信して経路線分列データと重畳し、利用者端末220からの拡大・縮小・スクロール操作を実現してもよい。このようなWebアプリは、利用者端末220における操作によって決められる表示したい領域のパラメータをHTTPリクエストに合わせて受け取り、そのパラメータによって指定された領域の地図データ(屋外経路の場合)、背景図面画像データ(施設内経路の場合)の必要領域を切り出し、経路探索結果の経路線分列データのうち当該領域にかかるデータのみを取り出して図面に重畳させ、その結果をHTTPレスポンスとして利用者端末220に返信する。
【0080】
施設内の背景図面画像データとして正確な図面でなく、デフォルメされたフロア図を用いてもよい。この場合、画像データから図面内リンクの正確な実距離を計算することはできないので、図面内リンクによっては実際の距離とは異なる値がリンクコストとして与えられる。そのため、探索された経路が必ずしも最短ではない可能性もある。しかしながら、必ずしも最短経路を求めるのではなく、実用上問題ない範囲で経路探索を行うのであれば、デフォルメされた画像データを用いた探索結果でも十分である。むしろ、デフォルメにより、より理解しやすいフロア図となり、人が暗黙に理解する通路と整合がとれた経路探索結果を表示できる。また、施設管理者にとっては、必ずしも実測に基づく正確な図面の画像データを用意する必要がなくなる。
【0081】
以上説明したように、本実施の形態によれば、施設内の経路を探索するためのローカルネットワークデータを蓄積し、施設の出入り口に相当するノードに緯度経度を付与しておき、経路探索の際に、出発地、目的地それぞれが属するネットワークデータが異なる場合は、それぞれのネットワークデータにより外部接続ノードを経由した経路探索を行い、その経路探索結果をつなぎ合わせることで、施設内を含む最適な経路探索を行うことができる。
【0082】
また、本実施の形態によれば、ローカルネットワークデータが屋外のネットワークデータに接続する外部接続ノードの情報を有し、ローカルネットワークデータ蓄積部120が施設毎にローカルネットワークデータを蓄積しておき、ローカルネットワークデータを登録するローカルネットワークデータ登録部110を備えることで、施設管理者が他の施設とはまったく独立して自身が管理する施設に関するローカルネットワークデータを登録することが可能となり、ローカルネットワークデータの整合性については個々の施設についてのみ行えばよい。その結果、各施設管理者により柔軟にローカルネットワークデータの更新ができ、利用者は常に最新のローカルネットワークデータに基づく経路探索が期待できる。
【符号の説明】
【0083】
100…経路探索装置
110…ローカルネットワークデータ登録部
111A,111B…端末
112…サーバ
113…ネットワーク
120…ローカルネットワークデータ蓄積部
130…ローカル経路探索部
140…広域経路探索部
150…統合経路探索部
200…ネットワーク
210…Webサーバ
220…利用者端末
230…地図サーバ

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

【図1】
image rotate

【図2】
image rotate

【図3】
image rotate

【図4】
image rotate

【図5】
image rotate

【図6】
image rotate

【図7】
image rotate

【図8】
image rotate

【図9】
image rotate

【図10】
image rotate

【図11】
image rotate

【図12】
image rotate


【公開番号】特開2013−11451(P2013−11451A)
【公開日】平成25年1月17日(2013.1.17)
【国際特許分類】
【出願番号】特願2011−142803(P2011−142803)
【出願日】平成23年6月28日(2011.6.28)
【出願人】(000004226)日本電信電話株式会社 (13,992)
【Fターム(参考)】