JP2015194438A - 地図データ構造、経路探索装置、および経路探索方法 - Google Patents

Abstract

【課題】位置特定のための効率および正確性に優れた地図データ構造、経路探索装置、および経路探索方法の提供を目的とする。
【解決手段】経路探索処理に用いられる地図データ構造であって、
探索領域１を複数の領域３に分割した領域情報２と、
各領域３毎に設定される適宜の座標系により記述された領域３内の位置情報４と、
各領域３内における他の領域３への少なくとも１つ以上の移動点５の移動点情報１１と、
２つの領域内の相対する移動点を対にした領域接続情報６と、
を有し、
探索領域１内に設定された出発点７から目的点８までの経路を位置情報４および領域接続情報６を利用して特定する処理に用いられる地図データ構造を採用する。
【選択図】図３

Description

本発明は地図データ構造、経路探索装置、および経路探索方法に関するものである。

経路探索処理は、従来、例えば特許文献１に示すように、緯度、経度による位置情報をもつノードの多数を探索領域内に設定し、このノード間を通路としてのリンクで結びつけた上で、出発地としての特定のノードから目的地としての他の特定のノードまでに至る適数のリンクを介した経路を探索してなされる。地下街や建物内部を探索領域とするこの従来例においては、ノードは、地下通路の交差点や階段の乗り降り口の中央位置などに設定され、リンクには、地下街等の階層の情報が属性情報として、また、通路や階段の距離、所要時間といったものがコストデータとして設定される。
さらに、地下街等の上記ノードに応じた位置に、当該位置の緯度、経度、および階層を送信する位置情報送信ユニットを設置しておき、利用者の所持する携帯端末で受信することにより、ＧＰＳ衛星信号の受信できないような地下街等においても利用者の現在位置が特定され、これを利用することで経路案内が利用者にリアルタイムでなされる。

特開２００６-１７６４７号公報

しかしながら上述した従来例は、緯度、経度のみでは位置が十分に特定できず、また、このような緯度、経度をリアルタイムで把握するためのＧＰＳ衛星信号も受信できないような地下街等において、これらをベースにしてさらに階層の情報をも付加することで位置を特定しているために、位置特定のための効率が非常に悪い、また、ノードや通路としてのリンクが代表的な位置や線で設定されているため、探査領域の実際の形状に即して自在に位置を特定して行う経路探索ができないという欠点がある。

本発明は以上の欠点を解消すべくなされたものであって、位置特定のための効率に優れ、探査領域の形状に即した経路探索を可能とする地図データ構造の提供を目的とする。また、本発明の他の目的は、位置特定のための効率に優れた経路探索装置および経路探索方法の提供にある。

本発明によれば、上記目的は、
経路探索処理に用いられる地図データ構造であって、
探索領域１を複数の領域に分割した領域情報２と、
各領域３毎に設定される適宜の座標系により記述された領域３内の位置情報４と、
各領域３内における他の領域３への少なくとも１つ以上の移動点５の移動点情報１１と、
２つの領域３、３内の相対する移動点５を対にした領域接続情報６と、
を有し、
探索領域１内に設定された出発点７から目的点８までの経路を位置情報４および領域接続情報６を利用して特定する処理に用いられる地図データ構造を提供することにより達成される。

本発明によれば、探索領域１は領域情報２により複数の領域３に分割され、各領域３では、位置情報４が各領域３毎に設定される適宜の座標系により記述されるとともに、他の領域３への１つ以上の移動点５が設定され、また、２つの領域３、３内で対をなす移動点５、５が設定され、領域接続情報６として記述される。出発点７、目的点８、および移動点５は、それぞれが属する領域３に設定された座標系に従う位置情報４により当該領域３内の位置が特定され、領域３、３間の相対位置は、対をなす移動点５、５をあたかもワープゾーンのように機能させることで特定される。

すなわち、本発明は、各領域３内に他の領域３内のものと対をなす移動点５、５を設定して領域３、３間を接続することにより、接続の際に必要な接続対象同士の等質性、すなわち座標系の一致といったものを移動点５の対において担保して領域３に関する位置情報４の定義の自由度を確保し、また、接続を移動点５の対、すなわち相対的な関係に限ることによって、接続媒体自体への位置情報４等の定義をも不必要にしたものである。これにより、探索領域１について、領域３毎に座標系の異なる位置情報４を一体化させた経路探索用のデータベースを構築することも可能になり、例えば、記述方法の異なる位置情報４が設定された領域３、３間を跨いで経路探索することも可能になる。一方、上述したような従来の経路探索処理は、上述の等質性を担保するためにノードの全てに対して共通の座標系における座標値を設定し、また、同一のノードに一端が繋がれたリンクの複数から個別のリンクを選択、識別するに止まる。

また、上述のように探索領域１を複数の領域３、３、・・に分割するに際し、領域３、３間に適宜の重合領域を残せば、この重合領域を移動点５の配置スペースに活用することで領域３、３間の移動を探索領域１上においては実質的に移動がなかったものと扱うことも可能になり、より現実空間に感覚的に近づけることができる。すなわち、移動点５の対を探索領域１内の重合領域において、現実空間上における同一地点を各領域３、３で示すものとして利用すれば、領域接続情報６を位置情報４とは全く無関係に機能させることができる。一方、上述の従来例のように探索領域１が階層状などの場合、各階を領域３に設定してエスカレータの登り降り口を移動点５、５にしても足り、この場合、領域接続情報６にエスカレータの距離などをコストに関する属性情報として設定したり、エスカレータの上り下りの向きに応じた移動方向の制限に関する属性情報を設定したりすることも可能である。
以上の領域３の形状は、人が移動する床面などの２次元空間として、また、立体形な３次元空間として実際の形状に即して記述できるほか、実際の形状をモデル化することにより点状や線状の空間としても記述することが可能である。また、移動点５の形状も、点状に限定されず、線状あるいは面状の２次元空間として構成することも可能である。

本発明の上述した高い拡張性により、領域３を点状および線状で、移動点を線状でモデル化することによって、上述した従来例におけるようにノードやリンクと同様の設定を行うことで経路探索に利用することができるが、むしろ、本発明は、このように予めノード等を設定せずに、例えば可視グラフ法を適用して各領域３内および領域３間の間で経路探索をする際に有効である。このように可視グラフ法などのいわゆるロードマップ法を利用する場合は、領域３の形状や位置座標を実際の形状に即して正確に記述することで、例えば、災害時などに、経路案内対象者の現在位置を詳細に特定して、状況に即した経路探索案内をする際に活用することも可能になるし、展示場などでブースのレイアウト変更がなされても、可視グラフ法で使用する障害物の設定を変更することで容易に対応することができる。

したがって本発明によれば、領域３毎に位置情報４の座標系を自由に設定することが可能になるために、無理に位置情報４の座標系を共通化させることによる位置特定のための効率の低下を防止でき、かかる効率を向上させることができる。

また、上述した位置特定のための効率の向上は、
探索領域１内に設定された出発点７から目的点８までの経路を探索する経路探索装置であって、
探索領域１を複数の領域３に分割した領域情報２、各領域３毎に設定される適宜の座標系により記述された領域３内の位置情報４、各領域３内における他の領域３への少なくとも１つ以上の移動点５の移動点情報１１、および対をなす移動点５、５の領域接続情報６を格納する記憶手段９と、
出発点７から目的点８までの経路を探索する経路探索手段１０と、
を有し、
前記経路探索手段１０は、位置情報４を利用して各領域３内での経路を特定するとともに、領域接続情報６を利用して領域３、３間の接続状態を特定して出発点７から目的点８までを経路探索する経路探索装置を提供することにより達成することができる。

さらに、上述した位置特定のための効率の向上は、
探索領域１内に設定された出発点７から目的点８までの経路をユーザの要求に応じて探索領域データベース１２に基づいて探索する経路探索方法であって、
前記探索領域データベース１２は、
探索領域１を複数の領域３に分割した領域情報２と、
各領域３毎に設定される適宜の座標系により記述された領域３内の位置情報４と、
各領域３内における他の領域３への少なくとも１つ以上の移動点５の移動点情報１１と、
２つの領域内の相対する移動点５を対にした領域接続情報６とを含み、
位置情報４を利用して各領域３内での経路を特定するとともに、領域接続情報６を利用して領域３、３間の接続状態を特定して出発点７から目的点８までを経路探索する経路探索方法を提供することにより達成することができる。

以上の説明から明らかなように、本発明によれば、位置特定のための効率を高めることができ、経路案内システムをより簡易に構成することや、実際の探索領域の形状に即した経路探索を提供することで、経路案内の利便性を高めることが可能になる。

経路案内システムのハードウェア構成図である。 経路探索用のデータベースを示す図で、（ａ）は領域データベースの構造を説明する図、（ｂ）は移動点データベースの構造を説明する図、（ｃ）は領域接続情報データベースの構造を説明する図、（ｄ）は目的点データベースの構造を説明する図である。 探索領域を模式的に示す図で、（ａ）は目的のデパートまでの経路を緯度、経度座標系上において示す図、（ｂ）はデパートの内部を複数の領域に分割し、当該建物に固有の座標系に従って表した図である。 デパート内部の各領域を模式的に示す図で、（ａ）はデパートの２階における目的点までの経路を可視グラフ法により求めるときの図、（ｂ）はこの経路を案内するときの画面構成の一例を示す図である。 ユーザの携帯端末における経路案内画面を示す図で、（ａ）はユーザの居る建物１階を示すもの、（ｂ）は目的点のある建物２階を示すもの、（ｃ）はユーザの居る場所から目的点までの経路全体を示すものである。 経路探索サーバのフローチャートを示す図である。 経路探索サーバのフローチャートを示す図である。 探索領域の分割の変形例を示す図で、（ａ）はエレベータ空間を上下方向の線状の領域として設定した探索領域の一部であって建物に固有の座標系上にあるものの全体を捉えた模式図、（ｂ）は領域データベースの構造を説明する図、（ｃ）は移動点データベースの構造を説明する図、（ｄ）は領域接続情報データベースの構造を説明する図である。 領域や移動点の態様の自由度を説明するための図で、（ａ）は領域を地下街の交差点や通路において点状や線状に設定したときを示す図、（ｂ）は領域を前庭や道路脇の歩道を区画して面状に、移動点を線状に設定したときを示す図である。 領域や移動点の態様の自由度を説明するための図で、（ａ）は移動点が点状であるときを示す図、（ｂ）は移動点が線状であるときを示す図、（ｃ）は移動点が面状であるときを示す図である。

図１ないし図７に本発明を適用した経路案内システムを示す。この経路案内システムは、図１に示すように、経路探索装置としての経路探索サーバＡとクライアント端末とをネットワーク２１を介して相互に交信可能に接続して構成される。上記ネットワーク２１にはこの実施の形態においてインターネットが利用される。

上記経路探索サーバＡは、図１に示すように、適宜の経路探索エンジンを活用して構成される経路探索手段１０と、この経路探索手段１０による経路探索対象としての探索領域１の地理的情報を蓄積する探索領域データベース１２（記憶手段９）とを有する。上記探索領域１に、この実施の形態においては緯度、経度座標系が適用される屋外区域と、建物固有の座標系が適用される屋内区域の双方を含むこの実施の形態において、上述の地理的情報は、座標系の異同に加え、屋内区域の階層に従って探索領域１を分割した領域３毎に蓄積される。

上記探索領域１は、この実施の形態においては具体的には、ある特定の市の中心街２２である屋外区域と、この中心街２２に建てられている３階建てのデパート２３の内部である屋内区域とで構成されており、上述の地理的情報は、上記中心街２２における道路等を含む屋外地理環境と、上記デパート２３内における通路等を含む各階毎の地理環境に分かれて蓄積される。また、領域３、３間を接続するために、各領域３内には他の領域３内に設定されるものと対をなす移動点５が設定され、一方の移動点５が他方の移動点５に位置的に繋がるものとして扱われる
図３は以上の探索領域１を模式的に示したものであり、図３（ａ）は屋外領域３、すなわち中心街２２を、図３（ｂ）は屋内領域３、すなわちデパート２３を表しており、デパート２３の出入り口や各階を繋ぐエスカレータ、エレベータの乗降口が移動点５として設定される。

以上の探索領域１の地理的情報および移動点５を経路探索に利用可能に蓄積するために、上述した探索領域データベース１２は、図１に示すように、各領域３の領域情報２や座標系等を蓄積する領域データベース（領域情報２）と、各移動点５のそれぞれの領域３内における位置情報４等を蓄積する移動点データベース（移動点情報１１）と、一対の移動点５、５間の接続情報を蓄積する領域接続情報データベース（領域接続情報７）とを有する。上記領域データベース２は、図２（ａ）に示すように、各領域３のＩＤ、空間種別、当該領域３の領域種別、名称、関連情報、座標系、および空間属性を相互に関連づけて蓄積する。ここで空間属性とは、各領域３の位置および形状に関する情報を座標系に基づいて特定するものであり、領域３が面により構成されるこの実施の形態においては、領域３内における道路や通路などの通行可能、言い換えれば経路として選択可能な面空間を座標値に基づいて特定するものである。なお、上述した建物固有の座標系には、図４（ａ）に示すように、デパート２３の平面視における矩形形状を構成する直交２辺を座標軸Ｘ、Ｙとし、階層をＺ軸の値に対応付けた直交座標を採用している。

また、上記移動点データベース１１は、図２（ｂ）に示すように、各移動点５のＩＤ、空間種別、当該移動点５の移動点種別、所属領域、および空間属性を相互に関連づけて蓄積する。移動点５が点状であるこの実施の形態において、空間属性は点空間を示す単一の座標値で構成される。

さらに、上記領域接続情報データベース７は、図２（ｃ）に示すように、領域３、３間を接続する一対の移動点５、５の組合せの各々に関し、そのＩＤ、組み合わせる一対の移動点５、５のそれぞれのＩＤ、これらの各々が属する領域３のＩＤ、移動種別、移動制限、移動適性、およびコスト属性を相互に関連づけて蓄積する。ここで移動制限とは、接続の有向性を示すものであり、具体的には移動点５、５の対が上りエスカレータの両端の乗降箇所に設定されたときに、当該移動点５、５間では下り方向への移動ができないことを示すためのものである。また、移動適性とは、この実施の形態において段差の有無などといったようにユーザの身体的状況によっては移動の可否に関わるような情報を示すものであるが、移動時の快適性などを示すものにすることも可能である。さらに、コスト属性は、この実施の形態においては、移動に要する予想時間を示すものであるが、例えば距離などに置き換えることも可能である。

以上に加え、上述した探索領域データベース１２には、図２（ｄ）に示すように、経路探索時の目的地候補としての目的点８と、その位置情報４とを関連づけて蓄積する目的点データベース２７も形成される。上記位置情報４は目的点８の属する領域３に適用される座標系に従って特定される。上記目的点データベース２７においては、各目的点８のＩＤ、空間種別、当該目的点８の目的地種別、名称、所属領域、および座標系などが相互に関連付けられる。

以上の経路探索サーバＡは、上述した経路探索手段１０にバスライン２８を介して接続される制御部２９と、上述のネットワーク２１に接続される入出力部３０とを有し、入出力部３０を介してクライアント端末Ｂからの経路探索要求を受信すると、この要求に応じた経路探索処理が制御部２９による制御のもと経路探索手段１０により実行される。なお、経路探索手段１０による上述した探索領域データベース１２へのアクセスは、バスライン２８に接続されるデータベースアクセス部３１によりトランザクション管理等がなされる。

上記経路探索手段１０による経路探索は、この実施の形態においては可視グラフ法を利用し、出発地としての出発点７から目的点８に至るまでの領域３と移動点５の移動順序を特定してなされる。各領域３内においては、この実施の形態においては上述した空間属性に基づいて出発点７、目的点８、および移動点５の間で可視グラフ法により領域内最短経路が探索され、この領域内最短経路の座標値に基づく経路長に応じてコストが算出される。図４（ａ）は可視グラフ法による経路探索を説明するもので、３２はエレベータ、３３はエスカレータ、点線で示す３４は各売り場のショーケース等であり、３５はエレベータの乗降口から靴売り場までの可視グラフにより得られる最短経路である。なお、コストの算出は、移動に要する基準時間を予め単位経路長に応じて設定しておくことにより、基準時間に経路長を乗算することでなされる。また、領域内最短経路は、上述のように可視グラフを用いる以外に、例えばボロノイ図を活用するなど適宜の手法によることが可能である。

出発点７から目的点８までに至る経路は、以上の領域内最短経路のコストと、接続情報データベース２６に蓄積される移動点５、５間のコスト属性とを合計して得られる総コストを基準にして、ダイクストラ法により出発点７から目的点８に至るまでの最小コストによる領域３、移動点５の経由順番を求めることによりなされる。なお、経路探索アルゴリズムは、このようにダイクストラ法を用いる以外に、例えばベルマン-フォード法を用いるなど適宜の手法によることが可能である。

さらに、上述した経路探索サーバＡは経路探索手段１０による探索結果に基づいてクライアント端末Ｂに対して案内情報を送信するために、このような案内情報を生成する案内用データ生成手段３６と、この案内用データ生成手段３６による案内情報の生成に用いるデータを格納する案内用データ格納手段３７を有する。上記案内用データ格納手段３７には、地図データや建物等のポリゴンデータなどが格納されており、案内用データ生成手段３６は、クライアント端末Ｂの表示画面である図５（ａ）ないし（ｃ）に示すように、地図データ上に経路を示す矢印や、出発点７、目的点８などを示す目印を重ねた案内用データを生成する。なお、上記案内用データ作成手段３６は、屋内区域においては図４（ｂ）に示すように、図４（ａ）に示す可視グラフにより得られた経路をＸ、Ｙ座標軸に平行な線分を組み合わせた折れ線に変換して経路を見やすくもする。また、図５（ａ）において３８は経路探索サーバＡに経路探索を要求する際のプルダウンメニューからなる入力欄、図５（ｂ）において３９は同様にプルダウンメニューからなる表示項目の選択欄であり、図５（ｃ）は上述したような最短経路ではなく、探索された全ての経路を案内表示した状態を示す。

一方、上述したクライアント端末Ｂは、この実施の形態においてはいわゆるスマートフォンであり、表示手段４０がタッチ画面として入力手段をも兼ねたものである。このクライアント端末Ｂは、制御部４１にバスライン４２を介して接続される経路探索要求生成手段４３を有し、ユーザによるタッチ画面への操作を通じて経路探索命令が入力されると、制御部２９は経路探索要求生成手段４３に経路探索要求を生成させ、入出力部４４を介して上述した経路探索サーバＡに送信させる。

また、上記クライアント端末Ｂは位置情報取得手段４５を有し、制御部４１は、上述のように経路探索命令が入力されると、位置情報取得手段４５に当該スマートフォンＢの現在位置情報を取得させる。現在位置情報は屋外においてはＧＮＳＳ（Ｇｌｏｂａｌ Ｎａｖｉｇａｔｉｏｎ Ｓａｔｅｌｌｉｔｅ Ｓｙｓｔｅｍ）の衛星信号の受信により、屋内である上述したデパート２３内においては、デパート２３固有の上述した直交座標系に基づく座標情報を記録してデパート２３内の各所に設置されたＲＦＩＤタグ等の位置情報発信装置からの座標情報の受信により特定される。以上のようにして得られた現在位置情報は、上述した経路探索要求に出発点７として含められ、このためユーザは、目的点８を入力することでクライアント端末Ｂに経路探索を命令することが可能である。なお、経路探索要求生成手段４３は、以上のように目的点８の入力をユーザに求め、この結果入力された目的点８と位置情報取得手段４５により取得された出発点７との間の経路の探索要求コマンドを経路探索サーバＡに送信するものであり、このような機能を実現する経路探索用アプリケーションソフトをスマートフォンＢにインストールすることにより形成される。

以上の経路案内システムによる経路案内処理の一例を以下に説明する。この例は、スマートフォンＢを所持して中心街２２のデパート２３前の広場に居るユーザが、デパート２３内にあるのではないかと考えている靴売り場を経路案内によって目指すものである。まず最初に、ユーザはスマートフォンＢを操作して経路案内用アプリケーションソフトを起動した後、デパート２３の名称を入力する。経路案内用アプリケーションソフトの起動に伴い、位置情報取得手段４５はＧＮＳＳの衛星信号を受信して現在位置を特定し、経路探索要求生成手段４３は、起動後にユーザにより入力されたデパート２３の名称を目的点８、位置情報取得手段４５により得られた現在位置を出発点７とする経路探索要求を生成し、これをインターネット２１を通じて経路探索サーバＡに送信する。

図６に示すように、経路探索サーバＡは、経路探索要求を受信すると（Ｓ-１）、先ず、目的点８を目的点データベース２７を検索して特定した上で、経路探索要求に含まれている出発点７と目的点８が同じ座標系を持っているか否かを判定し（Ｓ-２）、座標系が違う場合にはクライアント端末Ｂに目的点８の修正を促すアドバイスを返信して（Ｓ-３）経路案内処理を終了する。座標系の異同判定は、例えば目的点データベース２７に格納される座標系を参照してすることが可能である。

一方、座標系が同じ場合には、次に、出発点７と目的点８が同じ領域３内であるか否かを判定する（Ｓ-４）。この判定も、例えば目的点データベース２７の所属領域を参照してすることが可能である。この例のようにいずれも屋外区域であるとき、すなわち同じ領域３内であるときには、領域データベース２内の屋外に応じた領域３の空間属性を利用して可視グラフ法等により経路を探索する（Ｓ-５）。このような経路探索処理に加え、上述した座標系や領域３の判定処理についても全て経路探索手段１０によりなされる。

以上のようにして経路探索が終わったら、案内用データ格納手段３７に格納されたデータを利用して案内用データ生成手段３６により案内用データが生成される（Ｓ-６）。案内用データは、案内用データ格納手段３７に格納される中心街２２の地図に対し、経路探索手段１０により探索された経路を緯度、経度座標値を参考にして重ね合わせることで生成することができる。中心街２２の地図として立体地図が用意されるこの実施の形態において、案内用データ格納手段３７にはデパート２３の建物高さが付与されたポリゴンデータも格納される。

以上のようにして生成された案内用データは、経路探索サーバＡからユーザのスマートフォンＢに送信され（Ｓ-７）、この案内用データに基づいてユーザはスマートフォンＢの表示画面に図３（ａ）に示すような案内用地図の画像データを表示させることができる。したがってユーザは、目的の靴売り場があると考えているデパート２３までこの案内用地図により案内されて移動することができる。なお、目的点データベース２７におけるデパート２３の空間属性は、その出入口の座標のみとされており、これによりユーザはデパート２３の出入り口まで案内される。

また、この実施の形態において、上記デパート２３は屋内測位を用いたデパート内案内サービスを提供しており、所定間隔で屋内測位の座標情報を発信する座標情報発信装置が設置される。この座標情報発信装置はデパート２３の出入り口近傍にも配置されており、このためユーザが出入り口からデパート２３内に入ると、座標情報発信装置からの座標情報のスマートフォンＢによる受信によりそのデパート内における位置を特定することができる。なお、デパート２３内に固有の座標系は、デパート２３の設計図等を利用することであまり手間なく設定することが可能である。

したがってユーザがデパート２３の出入り口近傍でスマートフォンＢを操作して靴売り場への経路探索を求めると、経路探索要求生成手段４３は、靴売り場を目的点８、デパート２３の入り口近傍の屋内測位に基づく座標情報を出発点７とする経路探索要求を生成し、経路探索サーバＡに送信する。これを受信した（Ｓ-１）経路探索サーバＡは、出発点７と目的点８がいずれも建物固有の座標系を持っていることを確認した上で（Ｓ-２）、さらに出発点７と目的点８が同一の領域３内、すなわちデパート２３の同じ階にあるかを判定する（Ｓ-４）。

この実施の形態において靴売り場は１階とは領域３の異なる２階にあり、したがって経路探索手段１０による経路探索は、デパート２３の１階の出入り口近傍から２階の靴売り場までを対象にしてなされる。経路探索は、まず最初に、出発点７や目的点８のそれぞれが属する領域３、すなわち１階や２階において、その階の全ての移動点５に対する出発点７等からの経路を対象にしてなされる（Ｓ-８）。各階における移動点５の抽出は、移動点データベース１１における所属領域を利用してすることが可能であり、また、各階における経路探索は、上述同様、各階の空間属性を利用して可視グラフ法によりなされる。この経路探索の際には、デパート２３の固有座標系を利用して出発点７等から各移動点５までの全ての経路のコストも算出される。

次いで、上述のように各階で抽出した移動点５同士において、両者が直接接続されているものがあるか否かを判別する（Ｓ-９）。この判定は領域接続情報データベース７を参照してすることができる。図３（ｂ）に示すように１階と２階がエレベータとエスカレータの両者で直接的に接続されているこの実施の形態において、上述の判定ではこれらエレベータ等の移動点５の対が抽出され、したがって経路探索手段１０は、これらの移動点５を利用して１階から２階に移動するという経路候補を見付けることができる。このようにして経路候補が決まったら、領域接続情報データベース７を参照してエレベータ等の移動制限を確認し（Ｓ-１０）、また、エレベータ等のそれぞれのコストを取得して、先に求めていた出発点７等とこれらの移動点５との間の経路に応じたコストと足し合わせて総コストを算出した上で、総コストの値に基づいて経路候補から最短経路を決定する（Ｓ-１１）。この後、この最短経路に従って案内用データ生成手段３６が案内用データを生成し（Ｓ-６）、ユーザのスマートフォンＢに送信する（Ｓ-７）。

なお、以上のように経路候補が少数の場合には、図５（ｃ）に示すように、全ての経路候補をユーザに送信して経路案内としても足りる。また、以上においては２階に目的点８があったが、例えば３階にある場合には、出発点７と目的点８との間の経路がダイクストラ法を用いて求められる（Ｓ-１２）。この場合、例えば出発点７等の存在しない２階の全ての移動点５間の経路候補を可視グラフ法により特定してそれぞれのコストを求め、各階における経路候補をリンク、移動点５をノードして扱うことで既存の経路案内処理における場合と同様にダイクストラ法を活用して経路を求めることができる。

上述のように経路探索サーバＡから送信された案内用データがスマートフォンＢに受信され、ユーザの操作により案内用地図を表示画面に表示すれば、案内サービスが完了する。このように案内経路が１階と２階の場合には、図５に示すように、案内用地図は各階毎の個別の画像ファイルとして構成したり、さらに１階と２階の画像ファイルを複合したものと組み合わせるとわかりやすくなる。この場合、各画像ファイルを経路探索サーバＡからスマートフォンＢに送信しておき、ユーザのスマートフォンＢへの操作に応じて表示制御手段４６により順次画像ファイルを切り替え表示すればよい。

また、案内サービスを受けた後の移動途中にユーザが案内通りに移動できているか不安になったときには、再度その時点で経路探索サーバＡに経路探索要求をすれば、当該時点でのユーザの位置を正確に基準にして改めて経路案内を受けることができる。さらに、デパート２３の売り場のレイアウトが変更になったときには、領域データベース２と目的点データベース２７の空間属性を変更するだけで、簡単にレイアウト変更を探索領域データベース１２に反映させることができる。

なお、以上においては屋外領域３と屋内領域３の経路探索、経路案内を個別に順次行う場合を示したが、例えば目的点データベース２７において靴売り場にデパート２３の名称等を関連づけておけば、経路探索サーバＡが靴売り場を目的点８として受信したときに、靴売り場に関連づけられたデパート２３の名称を抽出し、このデパート２３までの屋外領域３の経路と、デパート２３内における出入り口から靴売り場までの経路とを一括して探索、案内することも可能である。

図８に本発明の変形例を示す。なお、以下の全ての説明においては、上述した実施の形態と同一の要素ついては同一の符号を付して説明を省略する。この変形例においてデパート２３には、図８に示すように、各階に止まるエレベータ３２Ａと、１階と３階を直通運転する高速運転エレベータ３２Ｂの２機が設置されており、各エレベータ３２Ａ、３２Ｂの鉛直方向に伸びる線状の移動範囲が領域データベース２に格納され、各階の乗降口近傍に一対の移動点５、５が設定される。

また、領域データベース２には、各エレベータ３２Ａ、３２Ｂの移動速度に応じたコストも設定されており、経路探索の際にはこのコスト、およびエレベータ３２Ａ、３２Ｂの停止階に応じた移動点５を利用することで最短経路を算出することができる。

なお、以上においては探索領域１を屋内、屋外や階層で分割し、エレベータの移動区域で分割する場合を示したり、このような領域３として面空間、線空間を設定する場合を示したり、さらには、各移動点５を点空間にした上で、移動点５の対に関し、その実質的な地理上の相対位置として一定の距離を隔てて設定する場合を示したが、探索領域１を適宜の単位で複数の領域３に分割し、領域３、３同士を移動点５を媒介にして一対一接続することができれば適宜の態様を採用することが可能である。例えば、図９（ａ）に示すように、屋外区域において道路４７を線状の部分と、交差点とにそれぞれ分けて捉え、これらを線空間と点空間で領域３に分割して各々の地理的情報を領域データベース２に蓄積することも可能である。なお、図９において移動点５’は道路に面した建物４８の出入口に設定したものである。

また、図９（ｂ）に示すように、道路４７から歩道４９や横断歩道５０を抽出し、これらをそれぞれ面空間として領域データベース２に分けて蓄積したり、歩道４９と横断歩道５０のそれぞれの境界をなす線状の区域に線状の移動点５を設定することも可能である。この場合、対をなす線状の移動点５は地理的に重合する位置をとる。

さらに、移動点５は、当該移動点５の属する領域３よりも空間の次数が低ければ領域３内に内包することが可能であり、その対は、相互の空間次数が同じであることで良好に接続できる。したがって図１０に示すように、領域３を３次元空間とした場合には、移動点５をノード、エッジ、フェイスのいずれかに設定することができ、例えば、上述したデパート２３について、その内部構造を示す３次元仮想空間がデータ化されているような場合には、これをそのまま探索領域データベース１２に活用し、出入口を表す仮想空間領域に図１０の（ａ）ないし（ｃ）のいずれかに示す移動点５を設定して経路探索に活用することも可能である。このように本特許の地図データ構造は、探索領域１内の各領域３におけるデータ整備状況の密や疎の状況によらず、複数の領域３、３、・・のデータベースをまたがる検索を実現できるモデルであり、複数の領域３、３を繋ぐための出入口情報である移動点５と領域接続情報７を作成することで容易に実現する。これにより、例えば、屋内施設の内部構造を示す高密度の３次元空間と屋外の近傍を示す中程度の２次元空間、交通要所間の移動手段を示す粗い２次元あるいは１次元空間などのデータの質や内容の異なる空間を組み合わせることが自在であり、経路案内の詳細度を求める要求に合わせて、メリハリのあるデータ活用や重要地域からの先行整備等、効果的かつ効率的な利用や整備を可能にする。

なお、上述した実施の形態等においては、健常者が経路探索をする場合を示したが、車いす利用者が経路探索する場合には、経路探索要求時に段差なしといった条件や、車いす使用を条件として付加し、接続情報データベース２６における移動適性を参照してこれらの条件を満たす経路を算出することも可能である。また、このような条件に代えてエレベータ利用を条件として付加し、領域データベース２の領域種別を参照して条件を満たす経路に絞り込むことも可能である。

１ 探索領域
２ 領域情報
３ 領域
４ 位置情報
５ 移動点
６ 領域接続情報
７ 出発点
８ 目的点
９ 記憶手段
１０ 経路探索手段
１１ 移動点情報
１２ 探索領域データベース

Claims (7)

1. 経路探索処理に用いられる地図データ構造であって、
   探索領域を複数の領域に分割した領域情報と、
   各領域毎に設定される適宜の座標系により記述された領域内の位置情報と、
   各領域内における他の領域への少なくとも１つ以上の移動点の移動点情報と、
   ２つの領域内の相対する移動点を対にした領域接続情報と、
   を有し、
   探索領域内に設定された出発点から目的点までの経路を位置情報および領域接続情報を利用して特定する処理に用いられる地図データ構造。
2. 前記領域接続情報は、移動可能方向に関する制限が属性情報として設定可能に構成され、
   目的点までの経路が属性情報に従って特定される請求項１記載の地図データ構造。
3. 前記領域情報が３次元空間、２次元空間、一次元空間、あるいは点空間のいずれかにより構成されるとともに、移動点が２次元空間、１次元空間、あるいは点空間のいずれかにより構成される請求項１または２記載の地図データ構造。
4. 探索領域内に設定された出発点から目的点までの経路を探索する経路探索装置であって、
   探索領域を複数の領域に分割した領域情報、各領域毎に設定される適宜の座標系により記述された領域内の位置情報、および各領域内における他の領域への少なくとも１つ以上の移動点の移動点情報、および対をなす移動点の領域接続情報を格納する記憶手段と、
   出発点から目的点までの経路を探索する経路探索手段と、
   を有し、
   前記経路探索手段は、位置情報を利用して各領域内での経路を特定するとともに、領域接続情報を利用して領域間の接続状態を特定して出発点から目的点までを経路探索する経路探索装置。
5. 探索領域内に設定された出発点から目的点までの経路をユーザの要求に応じて探索領域データベースに基づいて探索する経路探索方法であって、
   前記探索領域データベースは、
   探索領域を複数の領域に分割した領域情報と、
   各領域毎に設定される適宜の座標系により記述された領域内の位置情報と、
   各領域内における他の領域への少なくとも１つ以上の移動点の移動点情報と、
   ２つの領域内の相対する移動点を対にした領域接続情報とを含み、
   位置情報を利用して各領域内での経路を特定するとともに、領域接続情報を利用して領域間の接続状態を特定して出発点から目的点までを経路探索する経路探索方法。
6. 位置情報を利用して各領域内でのコストを演算し、
   探索により出発点から目的点までに至る複数の経路が見付かった場合に最小コストの経路を抽出する請求項５記載の経路探索方法。
7. ユーザから経路探索要求時に取得する位置情報を出発点として設定し、経路探索する請求項５または６に記載の経路探索方法。

Images