JP5771024B2 - 経路探索装置 - Google Patents

Description

本発明は、多階層構造を有する建造物内の経路を探索し、案内するための経路探索装置に関するものである。

現在、屋外についてモバイル端末を用いた歩行者ナビゲーションが実用化されている。また、屋内の駅構内や地下街、ビル等の建造物内に出発地や目的地、経由地を設定して経路探索を行なう歩行者ナビゲーションの研究も進んでいる。
屋内の建造物は多階層構造となる場合が多く、屋外のネットワークデータとは異なる構造を有する必要がある。例えば、屋内の建造物内のネットワークデータは階段やエレベータ等の他階層へ接続するノードが必要である。また、階層毎に案内をする場合はその階層ごとのネットワークデータが必要である。そして、高層商業ビルなどの多階層構造を有する建造物のネットワークデータはその階層分だけネットワークデータが必要になるため、ネットワークデータの容量は必然的に大きくなるものであった。その結果、容量やＣＰＵの性能に制限のあるモバイル端末にとって、このようなネットワークデータは大きな負担となるものであった。
この問題を解決する技術として、高さ方向の複数の階数に対応するネットワークデータを地図圧縮部により一平面状に投影することで圧縮する技術が開示されている（例えば、特許文献１参照）。この技術は、各階層のネットワークデータを投影し、空間上の類似点を利用して一平面状のネットワークデータを生成させ、ネットワークデータが存在する階数をフラグで管理するので、空間上で類似する階層が多数ある場合はデータ量を削減することができるものである。

特開２００８−８３１１２号公報

しかしながら、特許文献１に記載の技術はネットワークデータの容量は削減するものの、経路探索の効率が悪化する場合がある。具体的には、特許文献１は形状が異なるネットワークデータの各階層を一平面上に投影することにより生成した一平面状のネットワークデータがいずれの階層にも対応可能とするために細分化されている。この細分化された一平面状のネットワークデータに基づいて各階層のネットワークデータを生成するので、たとえ各階層が単純な構造のネットワークデータで構成されたものであっても、生成された階層ごとのネットワークデータは本来不要なノードを含んだ複雑な構造となってしまう場合がある。このようなネットワークデータを用いた経路探索を行なう場合には、経路探索はノードごとに通過の可否を判定する処理を実施するものであることから、本来不要なノードを用いた経路探索を行うこととなるので、経路探索効率が低下するのである。

本発明は、多階層構造の建造物内の経路探索において、経路探索効率を維持しつつネットワークデータの容量を削減する経路探索装置の提供を目的とする。

上記課題を解決するために、本発明は、多層階構造を有する建造物内を含む地図上の経路探索を行う経路探索装置であって、前記建造物の各階層の通路網の内で鉛直方向に見て一致する所定の通路網を表現した標準ネットワークデータと、前記建造物の各階層の通路網と前記標準ネットワークデータにより表現された通路網との差分を表現した差分ネットワークデータとを含む地図データを記憶する記憶部と、前記地図上に出発地と目的地とを設定する地点設定部と、前記記憶部から前記標準ネットワークデータと所望の階層の前記差分ネットワークデータとを読み出し、当該所望の階層の前記通路網を再現して前記出発地から前記目的地に至る経路探索を行う経路探索部と、を備えることを特徴とする。
なお、上述した特徴は、本発明の特徴のすべてを列挙したものではなく、これらを要部とする構成（または方法）もまた発明となり得る。

本発明の経路探索装置によれば、鉛直方向に見て一致する所定の通路網を表現した標準ネットワークデータと差分ネットワークデータとを用いて通路網を生成することにより経路探索を行うことから、各階層のネットワークデータには本来不要なノードを含まないことによって経路探索効率を維持しつつ、多階層構造の建造物のネットワークデータの容量を削減することができる。

ナビゲーションシステムの全体構成を示す図である。 地図データのデータ構造を示す図である。 経路案内処理の全体のフローチャートを示す図である。 地点設定処理のフローチャートを示す図である。 経路探索処理のフローチャートを示す図である。 指定階層のノードデータ群生成処理のフローチャートを示す図である。 経路案内処理のフローチャートを示す図である。 （ａ）は建造物内の各階層のネットワークデータを示す図であり、（ｂ）は建造物内のネットワークデータ全体を鉛直方向に見た図である。 （ａ）および（ｂ）は標準ネットワークデータを示す図である。 差分ネットワークデータを示す図である。 （ａ）は実施例１の建造物内のネットワークデータを説明する図であり、（ｂ）は実施例２のネットワークデータを説明する図である。 実施例２のノードデータのデータ構造を示す図である。 実施例２の経路案内処理のフローチャートを示す図である。 実施例３の建造物内の各階層のネットワークデータを示す図である。 実施例３の経路探索処理のフローチャートを示す図である。

以下、本発明を具体化した実施形態を説明する。

＜実施例１＞
図１に示すように、ナビゲーションシステム１は、携帯端末１０およびこの携帯端末１０と情報ネットワークを通じて接続される経路案内装置２０を備える。携帯端末１０は、無線通信部１１、現在位置検出部１２、画像表示部１３、入力部１４および装置本体を備える携帯電話であり、歩行者用ナビゲーション端末として利用される。経路案内装置２０はデータ通信部２１、計算機２２、記憶部２３を備える配信サーバである。なお、計算機２２には地点設定部３０、経路探索部３１、経路案内部３２を備えている。また、記憶部２３は地図表示用データ４０とネットワークデータ４１と含む地図データが記憶されている。

携帯端末１０を構成する無線通信部１１は、送信機、受信機およびアンテナからなるトランシーバである。また、現在位置検出部１２は、ＧＰＳ衛星からの電波に基づいて現在位置を検出するＧＰＳ受信器と、ＧＰＳ衛星からの電波を受信しにくい地下街内等では現在位置を検出するために設置された無線局からの近距離の無線電波の受信に基づいて現在位置を求めて現在位置のデータを出力する近距離無線位置検出器とからなる。また、画像表示部１３は、液晶ディスプレイ等であって画像表示面に通信メニュー画面や地図画像等の画像を表示するデバイスである。入力部１４は、画像表示部１３の表面がタッチパネルの機能を有しており、ユーザの指定により、目的地、表示したい地図のエリア、縮尺、施設の階層等を指定することができる。

経路案内装置２０を構成するデータ通信部２１は、光ファイバーによりインターネットＷと接続する機能を備えており、インターネットＷから無線通信を介して携帯端末１０の無線通信部１１と接続される。また、計算機２２は、コンピュータプログラムや処理条件等が予め記憶されているＲＯＭやＲＡＭ等の内部記憶装置、およびこのコンピュータプログラムを実行するＣＰＵ等からなる大型のコンピュータである。そして、記憶部２３は、フラッシュメモリ、ハードディスク、ＤＶＤまたはブルーレイディスク等の外部記憶装置であり、地図データを記憶している。

地点設定部３０は、データ通信部２１からの信号を受け付け、記憶部２３に記憶された地図データを参照して出発地、目的地等の地点を設定し、経路探索部３１へ出力する機能を有する。

経路探索部３１は、地点設定部３０からの出発地や目的地の情報を受け付け、地図データを参照して経路探索に必要な階層のネットワークデータの集合であるネットワークデータ群を生成する機能と、この生成されたネットワークデータ群を使用して目的地までの経路を探索する機能と、探索した経路のデータを経路案内部３２へ出力する機能とを有する。

経路案内部３２は、経路探索部３１からの経路のデータを受け付け、地図データを参照してこの経路の案内情報を生成し、データ通信部２１へ出力する機能を有する。

記憶部２３に記憶されている地図データは、行政界図、道路図および施設図等を生成するためのポリラインやポリゴンのデータ等の地図表示用データ４０と、歩行者用の通路の接続状態をノードおよびリンクで表現するネットワークデータ４１とを含む地図データである。

本発明におけるネットワークデータは、高さ方向に階層の異なる複数の階層を有する多階層構造の施設について各階層の通路網を表現した建造物内のネットワークデータを含んでいる。そして、この建造物内のネットワークデータは各階層の通路網の内で鉛直方向に見て一致する所定の通路網を表現した標準ネットワークデータと、この標準ネットワークデータにより表現された通路網との差分を表現した差分ネットワークデータとに区別される。

多階層構造を持つ建造物の各階層は、鉛直方向に見て通路が共通している場合が多い。このように共通する通路で構成するように生成された通路網が標準ネットワークデータである。標準ネットワークデータは、建造物内のネットワークデータにおいて鉛直方向から見て数多く一致するネットワークデータで構成されることが望ましい。標準ネットワークデータは後述するように一致するノードを共通化するので、一致する数が多いほど建造物のネットワークデータの容量が削減される。

差分ネットワークデータは、標準ネットワークデータに対して鉛直方向に見て一致しないデータであり、各階層単位に設定されている。建造物内のネットワークデータは、差分ネットワークデータが最も少なくなる構成となるのが望ましい。差分ネットワークデータを少なくすることで、建造物内のネットワークデータの容量をより多く削減できる効果がある。なお、差分ネットワークデータが無いと表現される階層のネットワークデータは、標準ネットワークデータと同じ構成となる。

差分ネットワークデータは、属性情報に「追加」と記載されている追加型ネットワークデータと、属性情報に「削除」と記載されている削除型ネットワークデータと、属性情報に「変更」と記載されている変更型ネットワークデータとがある。追加型ネットワークデータは、注目する一つの階層においてその階層には存在し、かつ標準ネットワークデータには存在しないネットワークデータである。削除型ネットワークデータは、標準ネットワークデータには存在し、かつ注目する一つの階層においてその階層には存在しないネットワークデータである。変更型ネットワークデータは、鉛直方向に見て標準ネットワークデータと一致するものの接続関係などの属性が異なっているネットワークデータである。
なお、変更型ネットワークデータは削除型ネットワークデータと追加型ネットワークデータとを用いて表すこともできる。すなわち、標準ネットワークデータの一部の属性を変更する場合、対象となる標準ネットワークデータを削除型ネットワークデータにより削除する処理、および追加型ネットワークデータにより変更された属性のネットワークデータを追加する処理の両方を実行することにしても良い。

たとえば、高さ方向に異なる６階層を有する多階層構造の建造物のネットワークデータの例について、図８を用いて説明する。図８（ａ）に示す建造物内の各階層のネットワークデータを鉛直方向に見た場合、図８（ｂ）に示すようにノードＮ１〜Ｎ８を含むネットワークデータで表すことができる。標準ネットワークデータにするか否かを判断するための閾値を３に設定したとき、この鉛直方向に見たネットワークデータのうち、鉛直方向に見て一致するノードが閾値以上となるノードはノードＮ１〜Ｎ６である。したがって、この建造物の標準ネットワークデータのノードは、図９に示すように、ノードＮ１〜Ｎ６で構成することができる。なお、本実施例においては、これらのノード間を結ぶリンクについても鉛直方向に見て閾値以上一致するものについて標準ネットワークデータに加えている。具体的には、図９に示すように、ノードＮ１〜Ｎ６間のリンクＬ１〜Ｌ７を構成に加えている。

また、図８で示した建造物の各階層の差分ネットワークデータについて、図１０を用いて説明する。１Ｆから６Ｆまでの各階層は図９で示した標準ネットワークデータに対して鉛直方向に見たときに一致しないデータで表現される。１Ｆの階層において、標準ネットワークデータに存在するノードＮ２、Ｎ５は１Ｆの階層には存在しないデータである。この場合、１Fの階層の差分ネットワークデータは削除型ネットワークデータのノード(以下、削除型ノードという)であるノードＮ２、Ｎ５で構成される。また、ノードＮ１、Ｎ３についてはノードＮ２への接続情報、ノードＮ６、Ｎ４についてはノードＮ５への接続情報がそれぞれ変更型ネットワークデータのノード（以下、変更型ノードという）により変更される。なお、図８に示す建造物においては、標準ネットワークデータに対応するリンクを設定していない。

また、２Ｆ〜４Ｆの階層は差分情報がないため図１０に示す例では「差分なし」と表現している。この場合、２Ｆ〜４Ｆの階層単位のネットワークデータは標準ネットワークデータと同じ構成となる。また、５Ｆの階層において、標準ネットワークデータには存在しないノードＮ７、Ｎ８は５Ｆの階層には存在するデータである。したがって、５Ｆの階層の差分ネットワークデータは、追加型ネットワークデータのノード（以下、追加型ノードという）であるノードＮ７、Ｎ８で構成される。また、ノードＮ２、Ｎ５についてはノード７への接続情報、ノードＮ３、Ｎ４についてはノードＮ８への接続情報がそれぞれ変更型ノードにより変更される。

また、さらに６Ｆの階層において、標準ネットワークデータには存在しないノードＮ７、Ｎ８は６Ｆの階層には存在するデータである。また、標準ネットワークデータには存在するノードＮ３は６Ｆの階層には存在しないデータである。したがって、６Ｆの階層の差分ネットワークデータは、追加型ノードＮ７、Ｎ８、削除型ノードＮ３で構成される。また、ノードＮ２についてはノードＮ７、Ｎ３への接続情報、ノードＮ５についてはノードＮ７への接続情報、ノードＮ４についてはノードＮ８への接続情報がそれぞれ変更型ノードにより変更される。

なお、本発明の地図データは標準ネットワークデータを１つの建造物に対して複数のパターンで用意することを可能な構造にしている。１つの建造物に対して複数のパターンを用意した場合は、各階層に任意に選択された１つのパターンの標準ネットワークデータを対応させる。標準ネットワークデータのパターンを複数設定すると、差分ネットワークデータは建造物の各階層の通路網と任意に選択された１つの標準ネットワークデータとの差分となるので、建造物全体として鉛直方向に見て通路が共通する傾向が複数あるようなときには、差分ネットワークデータの数が少なくなってネットワークデータの容量が削減される場合がある。

本実施例の地図データは、図２に示すように、地図表示用データ４０とネットワークデータ４１とで構成される。
地図表示用データ４０は、高さ方向に異なる複数の階層を有する施設について各階層の画像を表示するための階層単位表示用データを有している。本実施例の階層単位表示用データは、施設ＩＤ、施設名称、階層ＩＤをデータとして含んでいる。

ネットワークデータ４１は、建造物の各階層のデータを表す階層単位データ、通路同士を接続する点を規定するノードデータおよび２つのノード同士を結ぶ線を規定するリンクデータを含んでいる。階層単位データには、階層ＩＤ、標準パターン情報、差分情報等をデータとして含んでいる。階層ＩＤにはこの建造物の各階層を識別するＩＤが格納されている。標準パターン情報には、標準パターンＩＤ、ノードＩＤ、リンクＩＤが格納されている。標準パターンＩＤには標準ネットワークデータのパターンを規定する番号が格納されている。標準パターン情報に格納されるノードＩＤおよびリンクＩＤは標準ネットワークデータを構成するノードデータおよびリンクデータに対応している。

差分情報は標準パターンＩＤに対応する標準ネットワークデータに対して、差分ネットワークデータが有るか無いかの情報が格納されている。差分情報が「無し」となっている場合は、この階層のネットワークデータは標準ネットワークデータと同じ構成となる。一方、差分情報が「有り」となっている場合は、追加型ネットワークデータのＩＤを表す追加型ノード（リンク）ＩＤ、削除型ネットワークデータのＩＤを表す削除型ノード（リンク）ＩＤまたは変更型ネットワークデータのＩＤを表す変更型ノード（リンク）ＩＤが格納されている。なお、変更型ノード（リンク）には変更対象となるノード（リンク）の属性データを変更するための変更情報が含まれている。

ネットワークデータ４１のノードの情報であるノードデータには、ノードＩＤ、施設ＩＤ、接続ノード情報、座標情報、階層遷移情報等をデータとして含んでいる。接続ノード情報には、接続ノードＩＤ、この接続ノードに至るコスト情報および接続リンクＩＤを含んでいる。階層遷移情報は異なる階層へ接続する情報であり、対象となるノードから階層遷移することができるノードがある場合、そのノードの数だけ作成される。階層遷移情報は対象となるノードが位置する階層を表す階層IDと、その接続先の接続ノードＩＤ、接続リンクＩＤ、接続先階層ＩＤおよびコスト情報とを含んでいる。階層遷移情報はたとえば、階段やエレベータを表現した情報である。

ネットワークデータ４１のリンクの情報であるリンクデータには、リンクＩＤ、施設ＩＤ、接続ノードＩD、座標情報、階層遷移フラグ等をデータとして含んでいる。

本実施例のナビゲーションシステム１の処理について図３〜図７を用いて説明する。本実施例は、現在位置である出発地から目的地へ至る経路を設定し、ネットワークデータのうちノードデータの接続関係を用いて経路探索を行う例である。リンクデータは、経路探索の後に経路を表示させるときに用いるものとした。なお、出発地と目的地とは一建造物内で設定するものとした。さらに、本実施例では標準ネットワークデータに対応するノードおよびリンクをそれぞれ標準ノードおよび標準リンクとし、差分ネットワークデータに対応するノードおよびリンクをそれぞれ差分ノードおよび差分リンクとした。

まず、地点設定部３０は、入力部１４による出発地および目的地の入力に応じてネットワークデータを参照し、出発地に対応する階層および探索開始ノードと目的地に対応する階層および探索終了ノードとを特定する処理（地点設定処理）を実行する（ステップＳ１００）。次に、経路探索部３１はステップＳ１００により設定された探索開始ノードから探索終了ノードまでの経路探索を行なう処理（経路探索処理）を実行する（ステップＳ２００）。次に、経路案内部３２はステップＳ２００により探索された経路データとリンクデータを用いて経路案内を行う処理（経路案内処理）を実行する（ステップＳ３００）。以上、本発明のメインフローの各処理を説明した。以下、各処理の詳細について説明を行う。

（地点設定処理）
ステップS１００の地点設定処理について、図４を用いて以下に詳細な説明を行う。
まず、携帯端末１０側でユーザが入力部１４のタッチパネルを操作することにより目的地を指定する。目的地の指定は目的地が位置する階層の指定およびこの指定された階層における位置の指定により行なわれる。また、携帯端末１０は、現在位置検出部１２により現在位置を検出することにより出発地を指定する。出発地の指定は現在位置の位置する階層の指定および当該階層における位置の指定により行なわれる。ユーザの指定を受け付けると、指定された目的地のデータと出発地のデータとを無線通信部１１によりインターネットＷを介して配信サーバへ送信する処理を実行する（ステップＳ１１１）。

ステップＳ１１１が終了すると、配信サーバ側で、データ通信部２１が目的地のデータと出発地のデータを受信して計算機２２の地点設定部３０へ出力する処理を実行する。続けて、地点設定部３０は、記憶部２３に記憶されたネットワークデータ４１を参照し、地図上に出発地点としての探索開始ノードおよび目的地点としての探索終了ノードを決定する処理を実行する（ステップＳ１１２）。本実施例においては、地点設定部３０は、出発地指定位置から最近傍のノードを探索開始ノード、目的地の指定位置から最近傍のノードを探索終了ノードとして設定する。地点設定部３０により決定された地図上の探索開始ノードおよび探索終了ノードの情報は経路探索部３１へ出力され、経路探索処理（ステップＳ２００）へと移行する。

（経路探索処理）
ステップＳ２００の経路探索処理について、図５を用いて以下に詳細な説明を行う。
まず、経路探索部３１は、出発地および目的地の階層の標準ノードを記憶部２３のネットワークデータ４１から取得する（ステップＳ２１１）。具体的には、経路探索部３１は、出発地のデータに対応する階層における階層IDに対応する標準パターン情報を参照し、標準パターンＩＤにより規定される標準ノードを取得する。

ステップＳ２１１が終了すると、経路探索部３１は、出発地のデータに対応する階層に存在する差分ノードをネットワークデータ４１から取得し、ステップＳ２１１で取得した標準ノードに適用して経路探索に必要なノードデータの集合であるノードデータ群を生成する処理を実行する（ステップＳ２１２）。この処理の詳細な説明は後述するものとする。

ステップＳ２１２が終了すると、経路探索部３１は、探索開始ノードの接続ノード情報を参照し、ダイクストラ法により到達可能と判断された全ノードから最も低いコストとなるノードを確定する処理を実行する（ステップＳ２１３）。

ステップＳ２１３が終了すると、経路探索部３１は、確定したノードである確定ノードが探索終了ノードであるか否かを判定する処理を実施する（ステップＳ２１４）。本実施例の場合、直近のステップＳ２１３によって確定した確定ノードのノードＩＤおよび当該確定ノードが位置する階層と探索終了ノードのノードＩＤおよび探索終了ノードが位置する階層とを比べて判定を行なう。経路探索部３１は、ステップＳ２１４において、当該確定ノードが探索終了ノードであると判定した場合は（ステップＳ２１４：Ｙｅｓ）、経路探索処理を終了する。そして経路探索部３１は探索開始ノードから探索終了ノードまでに確定したノードのうち最もコストが低くなる経路を構成するノードを経路案内処理（ステップＳ３００）へ出力する。

一方、ステップＳ２１４において、当該確定ノードが探索終了ノードではないと判定した場合は（ステップＳ２１４：Ｎｏ）、経路探索部３１は当該確定ノードに階層遷移情報があるか否かを判定する（ステップＳ２１５）。なお、確定ノードが対応するノードデータには複数の階層遷移情報を含んでいるものがある。そのため、具体的には、経路探索部３１は、当該確定ノードの階層遷移情報において当該確定ノードが位置する階層の階層ＩＤと同じ階層ＩＤに対応する階層遷移情報がある場合は、階層遷移情報があると判定する。ステップＳ２１５において、階層遷移情報が無い場合は（ステップＳ２１５：Ｎｏ）、経路探索部３１は異なる階層へ探索を進めることが無いと判断してステップＳ２１３へ移行し、当該確定ノードの接続ノード情報を参照して次に進むノードを探索する。

一方、ステップＳ２１５において当該確定ノードに階層遷移情報が有ると判定した場合は（ステップＳ２１５：Ｙｅｓ）、経路探索部３１は接続先階層ＩＤを参照し、当該確定ノードの接続先の階層がノードデータ群を生成しているか否かの判定をおこなう（ステップＳ２１６）。ステップＳ２１６において、接続先の階層のノードデータ群を生成済みであると判定された場合は（ステップＳ２１６：Ｙｅｓ）、経路探索部３１はステップＳ２１３へ移行する。

ステップＳ２１６において、接続先の階層のノードデータ群を生成済みでないと判定された場合は（ステップＳ２１６：Ｎｏ）、経路探索部３１はステップＳ２１２へ移行して接続先の階層のノードデータ群を生成する処理を行なう。

（ノードデータ群生成処理）
ステップＳ２１２のノードデータ群生成処理について図６を用いて以下に詳細に説明する。
まず、経路探索部３１は、ネットワークデータ４１における階層単位データの差分情報を参照し、対応する階層に差分ノードが存在するか否かを判定する（ステップＳ４１１）。ステップＳ４１１において、差分情報が無いと判定された場合は（ステップＳ４１１：Ｎｏ）、経路探索部３１は対応する階層のノードデータ群生成処理を終了する。

一方、ステップＳ４１１において、差分情報が有ると判定された場合は（ステップＳ４１１：Ｙｅｓ）、経路探索部３１は対応する階層の差分ノードをネットワークデータ４１から取得する（ステップＳ４１２）。具体的には、経路探索部３１はネットワークデータ４１における階層単位データの差分情報を参照し、差分対象となる追加型ノード、削除型ノードおよび変更型ノードのうち対応するノードを記憶部２３から抽出する。

ステップＳ４１２が終了すると、経路探索部３１は、ステップＳ４１２で取得した差分ノードをステップＳ２１１で取得した標準ノードと合成する処理を実行する（ステップＳ４１３）。差分ノードには、上述の通り追加型ノード、削除型ノードおよび変更型ノードがある。経路探索部３１は、経路探索部３１は、例えば、追加型ノードについては標準ノードからなるノードデータ群に追加する処理、変更型ノードについては標準ノードのうちの特定のノードに接続する他のノードとの接続関係等を変更する処理、削除型ノードについては標準ノードデータからなるノードデータ群のうち特定のノードを削除する処理を実行する。このようにして、経路探索部３１は対応する階層のノードデータ群を生成する。生成されたノードデータ群は、各階層に存在するノードデータだけで構成されているため、不必要なノードデータが存在しない。したがって、以上のようなデータ構造とすることで、経路探索部３１は経路探索の効率を維持できる効果がある。

（経路案内処理）
ステップＳ３００の経路案内処理について、図７を用いて以下で詳細に説明する。
まず、経路案内部３２は、経路探索部３１が出力したノード同士を接続するリンクデータを記憶部２３のネットワークデータ４１から抽出する処理を実行する（ステップＳ３１１）。経路案内部３２は、経路探索部３１が出力したノードの接続リンクＩＤを参照してリンクデータを抽出する。
たとえば、図８の５Ｆの階層において経路探索部３１が出力したノードがノードＮ６→ノードＮ５→ノードＮ７→ノードＮ８であった場合、本実施例においては、経路案内部３２は図１１（ａ）に示すように標準ネットワークデータのリンクＬ５、差分ネットワークデータのリンクＬ８、Ｌ９をネットワークデータ４１から抽出する。なお、リンクＬ８、９はともに追加型ネットワークデータである。このうちリンクＬ８については、鉛直方向に見て標準ネットワークデータのリンクＬ７と一部が一致しているので、標準ネットワークデータのリンクＬ７を削除する処理と差分ネットワークデータのリンクＬ８を追加する処理の両方を実行することによりノードＮ５→ノードＮ７に対応するリンクＬ８として抽出される。

ステップＳ３１１が終了すると、経路案内部３２は抽出したリンクデータと表示用地図データとから経路案内データを生成する処理を実行する（ステップＳ３１２）。経路案内部３２は、ステップＳ３１１で抽出したリンクデータを接続して表示するように処理した経路表現データに、この経路表現データに対応する階層単位表示用データを抽出して重ねることで、経路案内データを生成する。

ステップＳ３１２が終了すると、経路案内部３２は生成した経路案内データをデータ通信部２１へ出力し、配信サーバ２０からインターネットＷを介して携帯端末１０の無線通信部１１へ送信する。携帯端末１０は経路案内データを無線通信部１１から表示部１３へ送信し、液晶ディスプレイ等に表示させる（ステップＳ３１３）。

＜実施例２＞
実施例２では、ノードデータの接続ノード情報において対応するリンクの情報の形態が実施例１と異なる。なお、地点設定処理Ｓ１００および経路探索処理Ｓ２００については実施例１と同じである。

実施例２におけるノードデータは、図１２に示すように、接続ノード情報に実施例１における接続リンクＩＤの代わりに採用リンクＩＤが記憶される。採用リンクとは、接続対象となるノードとの間のリンクとして採用する標準リンクを示す。また、接続ノード情報には、接続ノードＩＤやコスト情報の他、鉛直方向に見て採用リンクが接続対象のノードの位置を通過するリンクデータであることと、採用リンクが接続対象のノードの位置を通過するリンクデータであるときに接続対象のノードの採用リンク上における相対位置とを示す相対位置情報とが含まれる。

相対位置情報が有効な値を持つ場合、採用リンクが接続対象となるノードを通過することを示している。たとえば、図１１（ｂ）のように、ノードＮ５の接続先がＮ２であった場合、標準リンクである採用リンクはリンクＬ７で表される。ここで、リンクＬ７上にノードＮ７が追加され、ノードＮ５の接続先がノードＮ７に変更された場合、ノードＮ５の接続ノード情報の接続ノードＩＤはノードＮ７、採用リンクＩＤはリンクＬ７をそれぞれ表すこととなる。

相対位置情報は、採用リンクの始点から終点までの距離に対する接続対象のノードまでの採用リンク上の距離で表される。たとえば、図１１（ｂ）において、ノードＮ５からノードＮ２を結ぶ採用リンクＬ７の始点から終点までの距離が「１００」であって、接続対象のノードＮ７までの通過リンク上の距離が「５０」であるならば、相対位置情報には５０パーセントを示す値が記されることとなる。このようなデータ構造とすることで、ネットワークデータ４１はノードデータを接続する全てのリンクデータを格納する必要がなくなるので、データ容量を削減できる効果がある。なお、図１２ではネットワークデータ４１のノードデータであって、便宜上他のデータを省略して表している。

（経路案内処理）
相対位置情報を用いた経路案内処理を、図１３を用いて以下で詳細に説明する。まず、経路案内部３２は、経路探索部３１が出力したノードの採用リンクＩＤを参照して、リンクデータを記憶部２３のネットワークデータ４１から抽出する処理を実行する（ステップＳ１３０１）。たとえば、図１０の５Ｆの階層においては、経路探索部３１が出力したノードがノードＮ６→ノードＮ５→ノードＮ７→ノードＮ８であった場合、実施例２においては、経路案内部３２は図１１（ｂ）に示すように標準ネットワークデータのリンクＬ５、Ｌ７、差分ネットワークデータのリンクＬ９をネットワークデータ４１から抽出する。

ステップＳ１３０１が終了すると、経路案内部３２は、鉛直方向に見て採用リンクが接続対象のノードの位置を通過するリンクデータであることを相対位置情報が示しているか否かを判定する処理を実行する（ステップＳ１３０２）。ステップＳ１３０２において、採用リンクが接続対象のノードの位置を通過するリンクデータであると判定された場合は（ステップＳ１３０２：Ｎｏ）、経路案内部３２は、ステップＳ１３０４へ移行して経路案内データを生成する処理を行なう。

一方、ステップＳ１３０２において、採用リンクが有効な相対位置情報を含むと判定された場合は（ステップＳ１３０２：Ｙｅｓ）、経路案内部３２は、ノードデータから相対位置情報を抽出し、この相対位置情報を抽出した採用リンクに適用して変更する（ステップＳ１３０３）。具体的には、図１１（ｂ）においては、経路案内部３２は、たとえばリンクＬ７の相対位置情報が５０パーセントの場合、リンクＬ７はノードＮ５から５０パーセントの長さに変更される。経路案内部３２は、経路表現データとしてリンクＬ５→リンクＬ７（５０パーセント）→リンクＬ９を生成する。

ステップＳ１３０３およびステップＳ１３０２が終了すると、経路案内部３２は、採用リンクおよび変更した採用リンクと表示用地図データとから経路案内データを生成する処理を実行する（ステップＳ１３０４）。経路案内部３２は、リンクデータを画像により表現した経路表現データに、このリンクデータの階層ＩＤに対応する階層単位表示用データを重ねることで、経路案内データを生成する。

ステップＳ１３０４が終了すると、経路案内部３２は生成した経路案内データをデータ通信部２１へ出力し、配信サーバ２０からインターネットＷを介して携帯端末１０の無線通信部１１へ送信する。経路案内部３２は経路案内データを無線通信部１１から表示部１３へ送信し、液晶ディスプレイ等に表示させる（ステップＳ１３０５）。

＜実施例３＞
実施例３では、１つの建造物における標準ネットワークデータのパターンの数が実施例１および２と異なる。すなわち、実施例３の地図データは標準ネットワークデータを１つの建造物に対して複数のパターンで用意することを可能な構造にしている。たとえば低階層が店舗フロアで中高階層がオフィスフロアという構造を持つ複合商業施設の場合、店舗フロアとオフィスフロアとでネットワークの構造が大きく異なることは珍しくない。このような場合、差分ネットワークデータは各階層の通路網と任意に選択された１つの標準ネットワークデータとの差分となる。すなわち、各階層の差分ネットワークデータは、選択された店舗フロアに対応する標準ネットワークデータもくしはオフィスフロアに対応する標準ネットワークデータとの差分となる。このように店舗フロアにおける標準ネットワークデータのパターンとオフィスフロアにおける標準ネットワークデータのパターンとを持つようにすることで、差分ネットワークデータを少なくすることができる。

たとえば、階層によって構造の異なる建造物について、図１４を用いて説明する。図１４における建造物Ｂは、１Ｆ〜２Ｆを店舗フロア、３Ｆ〜６Ｆをオフィスフロアとする複合商業施設である。１Ｆ〜２Ｆの店舗フロアと３Ｆ〜６Ｆのオフィスフロアとは用途が異なるため、通路を含む構造が大きく異なっている。このような場合、標準パターン情報の標準パターンＩＤにより店舗フロアとオフィスフロアとを区別し、店舗フロアに対応する標準ノードはノードＮ１１１〜Ｎ１１５、オフィスフロアに対応する標準ノードはノードＮ１０１〜Ｎ１０６と設定することができる。

（経路探索処理）
実施例３における経路探索処理について、図１５を用いて以下に詳細に説明する。
実施例３の経路探索処理のうち、図１５に示したステップＳ１５０１からステップＳ１５０５までの処理は、図５に示した実施例１の経路探索処理のうちステップＳ２１１からステップＳ２１５までの処理と同じである。したがってステップＳ１５０１からステップＳ１５０５までの処理の説明を省略し、ステップＳ１５０６の処理から説明を行う。

ステップＳ１５０５において確定ノードに階層遷移情報が有ると判定した場合は（ステップＳ１５０５：Ｙｅｓ）、経路探索部３１は接続先階層ＩＤを参照し、接続先の階層がノードデータ群を生成しているか否かの判定をおこなう（ステップＳ１５０６）。ステップＳ１５０６において、接続先の階層のノードデータ群を生成済みであると判定された場合は（ステップＳ１５０６：Ｙｅｓ）、経路探索部３１はステップＳ１５０３へ移行する。

ステップＳ１５０６において、接続先の階層のノードデータ群を生成済みでないと判定された場合は（ステップＳ１５０６：Ｎｏ）、経路探索部３１は接続先階層の標準ノードデータが取得済みか否かの判定をおこなう（ステップＳ１５０７）。具体的には、経路探索部３１はネットワークデータ４１を参照し、接続先階層の階層ＩＤに対応する標準パターンＩＤとこれまでのステップＳ１５０１で取得した標準パターンＩＤとを比較して、それぞれのＩＤが同じであるか否かを判定する。ステップＳ１５０７において、経路探索部３１が接続先階層の階層ＩＤに対応する標準パターンＩＤとステップＳ２１１で取得した標準パターンＩＤとが同じであり、これにより、接続先階層の標準ノードデータは取得済みであると判定した場合（ステップＳ１５０７：Ｙｅｓ）、ステップＳ１５０２へ移行する。

一方、ステップＳ１５０７において接続先階層の階層ＩＤに対応する標準パターンＩＤとステップＳ２１１で取得した標準パターンＩＤとが異なり、これにより、接続先階層の標準ノードデータは取得済みでないと判定した場合（ステップＳ１５０７：Ｎｏ）、ステップＳ１５０１へ移行する。

以上のように、実施例３の地図データは１つの建造物に対して標準ノードデータを複数パターン用意することで、差分ネットワークデータを少なくすることができ、地図データの容量を削減できる効果がある。たとえば店舗フロアとオフィスフロアが混在する複合商業施設のような場合、店舗フロアの標準パターンおよびオフィスフロアの標準パターンを設定することで、差分ネットワークデータを削減できるのである。

＜その他＞
なお、本発明は上述の実施例に限定されるものではなく、本発明の要旨を逸脱しない範囲内において種々の変更、改良が可能であることは言うまでもない。例えば実施例１ではノードデータの接続ノード情報を用いて経路探索を行い、リンクデータは経路案内表示に用いるが、リンクデータとノードデータとを用いて経路探索を行なっても良い。

１０ 携帯端末、１１ 無線通信部、１２ 現在位置検出部、１３ 画像表示部、１４ 入力部、２０ サーバ装置、２１ データ通信部、２２ 計算機、２３ 記憶部、３０ 地点設定部、３１ 経路探索部、３２ 経路案内部、４０ 地図表示用データ、４１ ネットワークデータ

Claims (2)

1. 多層階構造を有する建造物内を含む地図上の経路探索を行う経路探索装置であって、
   前記建造物の各階層の通路網の内で鉛直方向に見て一致する所定の通路網を表現した標準ネットワークデータと、前記建造物の各階層の通路網と前記標準ネットワークデータにより表現された通路網との差分を表現した前記各階層単位に規定される差分ネットワークデータとを含む地図データを記憶する記憶部と、
   前記地図上に出発地と目的地とを設定する地点設定部と、
   前記記憶部から前記標準ネットワークデータと所望の階層の前記差分ネットワークデータとを読み出し、当該所望の階層の前記通路網を再現して前記出発地から前記目的地に至る経路探索を行う経路探索部と、
   を備える経路探索装置。
2. 請求項１記載の経路探索装置であって、
   前記記憶部に記憶される標準ネットワークデータは前記建造物に複数用意されており、前記差分ネットワークデータは前記建造物の各階層の通路網と任意に選択された１つの標準ネットワークデータとの差分であることを特徴とする経路探索装置。