(57)【要約】【課題】  道路を横断するために無用な迂回を柔軟に回避できる実用的な経路探索を行う。【解決手段】  歩行者用の経路探索システムにおいて、道路の両側に位置するリンク同士を、予めペアとして関連づけておく。経路探索時には、ペアとして設定されたリンク間は任意の場所で横断可能という条件で経路を探索する。つまり、予め横断用のリンクが設定されていない場所でも、一方のリンクから他方のリンクに垂線をおろし、そこに仮想ノードＬＶｅを設定することによって、仮想的なリンクを生成するのである。こうすることによって出発地ＳＴから目的地ＧＬに至る経路を探索する際には、この仮想的なリンクを通る経路ＲＴ２を得ることができ、横断歩道を経由する経路ＲＴ１のように無用な迂回を回避した経路を探索することができる。【選択図】  図１
2012202885.tif 000002
【特許請求の範囲】
【請求項１】
経路を探索する経路探索システムであって、
道路網をノードおよびリンクで表した道路ネットワークデータを記憶する道路ネットワークデータ記憶部と、
前記道路ネットワークデータを用いて、指定された出発地から指定された目的地までの経路を探索する経路探索部とを備え、
前記道路ネットワークデータは、複数のリンクにつき、該リンク同士を結ぶ横断リンクの存否にかかわらず一方のリンクから他方のリンクに横断可能であることを示す横断可能情報を有しており、
前記経路探索部は、前記横断可能情報で関連づけられたリンク間では、前記横断リンクの位置にかかわらず、一方のリンクから他方のリンクへの仮想的な横断経路をひくことにより経路探索を実行する経路探索システム。
【請求項２】
請求項１記載の経路探索システムであって、
前記道路ネットワークデータは、歩行者が通行する道路網を表しており、
前記横断可能情報が付される複数のリンクは、道路の両側に存在する歩道に対応するリンクである経路探索システム。
【請求項３】
請求項２記載の経路探索システムであって、
前記横断可能情報は、前記横断リンクから所定範囲外に存在するリンクに対して設定されている経路探索システム。
【請求項４】
請求項２記載の経路探索システムであって、
前記経路探索部は、前記横断リンクから所定範囲外に存在する領域を前記横断可能な領域として、前記経路探索を行う経路探索システム。
【請求項５】
請求項１〜４いずれか記載の経路探索システムであって、
前記経路探索部は、前記仮想的な横断経路を通過する経路については、前記横断リンクを通過する経路よりも優先度を下げて経路探索を行う経路探索システム。
【請求項６】
請求項１〜５いずれか記載の経路探索システムであって、
さらに、探索された経路について、前記仮想的な横断経路とその他の経路とで案内態様を切り替えて案内を行う経路案内部を備える経路探索システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、道路ネットワークデータを用いて出発地から目的地までの経路探索を行う経路探索システムに関する。
【背景技術】
【０００２】
道路ネットワークを用いて経路探索、経路案内をするナビゲーションシステムが普及している。近年では、歩行者が通行する歩道などに設定された歩行者ネットワークデータを用いて歩行者用に経路探索、案内を行う歩行者用のナビゲーションシステムも実用化されるようになってきている。歩行者用のナビゲーションシステムにおいては、１本の道路の両側にある歩道上に設定されたリンク同士は、経路探索上は別々の道路として扱われるため、両者間を横断できるようにデータを整備しておく必要がある。
特許文献１では、かかる観点から、横断歩道をリンクとして設定する他、横断歩道以外の場所でも、道路の両側の歩道間を横断するための横断用のリンクを設定している。特許文献２では、歩行者ネットワークデータを自動生成する際に、一定幅以上の道路の交差点には自動的に横断用のリンクを生成している。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２００７−７８６５５号公報
【特許文献２】特開２００４−３０１９５６号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
従来技術では、ノード、リンクを用いて経路探索を行っていたため、リンクが設定されていない場所を通行する経路は探索することができず、無用に大回りする経路が探索される場合があった。
図１は従来技術における経路探索例を示す説明図である。出発地ＳＴから目的地ＧＬまでの経路探索の結果を示している。道路ＲＤの両側には歩道が設けられており、横断歩道ＣＷで横断可能となっている。この条件下で経路探索を行うと、経路ＰＳ１（実線）のように、横断歩道ＣＷを通過する経路が得られる。しかし、横断歩道ＣＷ以外の場所でも道路ＲＤを横断することを許容すれば、経路ＰＳ２（破線）のように、最短距離の適切な経路が存在するのである。従って、経路ＰＳ１は、無用な大回りをしていることになる。
特許文献１で開示されているように、横断歩道が存在する場所以外にも、横断用のリンクを設けることにより上述の課題を回避しようとすれば、歩行者ネットワークデータを整備する負担が大きくなるという別の課題を招いてしまう。
無用な大回りが生じるという課題は、歩行者用のナビゲーションシステムに特有のものではなく、自動車用のナビゲーションシステムにおいても、道路ネットワークが十分に整備されていない場所では、同様に生じ得る問題であった。
本発明は、かかる課題に鑑み、自動車用か歩行者用かを問わず、リンクが整備されていない場所も通行可能な経路探索を実現することを目的とする。
【課題を解決するための手段】
【０００５】
本発明の経路探索システムは、
経路を探索する経路探索システムであって、
道路網をノードおよびリンクで表した道路ネットワークデータを記憶する道路ネットワークデータ記憶部と、
前記道路ネットワークデータを用いて、指定された出発地から指定された目的地までの経路を探索する経路探索部とを備え、
前記道路ネットワークデータは、複数のリンクにつき、該リンク同士を結ぶ横断リンクの存否にかかわらず一方のリンクから他方のリンクに横断可能であることを示す横断可能情報を有しており、
前記経路探索部は、前記横断可能情報で関連づけられたリンク間では、前記横断リンクの位置にかかわらず、一方のリンクから他方のリンクへの仮想的な横断経路をひくことにより経路探索を実行するものである。
横断リンクとは、道路網を表すリンクと異なるものではなく、上述の横断可能情報が定義されたリンク間を連結するリンクを便宜上、横断リンクと称するものである。
【０００６】
本発明の経路探索システムによれば、道路ネットワークデータには、横断可能情報が付されている。そして、経路探索部は、横断可能情報で関連づけられたリンク間では、仮想的な横断経路をひくことにより経路探索を実行することができる。従って、リンクが設定されていない場所を通行する経路を探索することが可能となる。仮想的な横断経路は、一時的にリンクを設定することにより形成する方法としてもよいし、単に横断時にコストを加算するという方法、つまり経路を単に想定した状態探索を行う方法など、種々の方法でひくことができる。
本発明の経路探索システムは、自動車用または歩行者用に限定されるものではなく、道路ネットワークデータも、自動車用に整備されたものであっても、歩行者用に整備されたものであってもよい。
横断可能情報で関連づけられるリンクは、必ずしも１対１である必要はない。３本以上のリンクを相互に関連づけるものとしてもよいし、１対２、１対３などの態様で関連づけしてもよい。横断可能情報は、種々の態様で格納可能であり、例えば、道路ネットワークデータのリンクに対して属性などの形式で格納してもよいし、ノード、リンクのデータとは別のデータとして道路ネットワーク記憶部に格納してもよい。
【０００７】
上述の経路探索は、種々の方法で実現可能である。仮想的な横断経路は、例えば、横断可能情報で関連づけられたリンクの一方から他方に下ろした垂線や、これらのリンク上の端点のノード同士を結ぶ線分などとすることができる。仮想的な横断経路とリンクとの交点にノードが設定されていない場合には、仮想的なノードを設定してもよい。こうして設定された仮想的な横断経路に対して、その長さなどに応じて、経路探索用のコストを設定することにより、経路探索を行うことが可能となる。
【０００８】
本発明は、歩行者用の経路探索システムとしてもよい。
例えば、
前記道路ネットワークデータは、歩行者が通行する道路網を表しており、
前記横断可能情報が付される複数のリンクは、道路の両側に存在する歩道に対応するリンクとすることができる。
こうすれば、道路の両側に設定されたリンク間を任意の場所で横断することを許容した経路探索を実現することができる。歩行者は、道路を自由な場所で横断できるなど、自動車以上に移動の自由度が高いのが通常であるから、本発明の経路探索は、特に有用性が高い。ここで、「道路の両側に存在する歩道」とは、必ずしも車道と区別された歩道だけを意味するものではなく、歩行者用の道路網として道路の両側にリンクが設定されている場合も含む。
【０００９】
歩行者用の経路探索システムにおいては、
前記横断可能情報は、前記横断リンクから所定範囲外に存在するリンクに対して設定されているものとしてもよい。
こうすることによって、横断歩道など道路を横断するように設けられたリンク付近では、仮想的な横断経路を設定することを回避できる。横断歩道など横断用に設けられたリンクが付近にある場合には、これらの場所を通る経路の方が、安全性が高いと考えられるため、上述の態様によれば、通行の安全性も考慮した経路探索を実現することができることになる。「所定範囲外に存在するリンク」とは、リンク全体が所定範囲外にあるものだけを意味するものではなく、リンクの一部が所定範囲外にあるものも含む。
上述の態様を実現するためには、例えば、上述の所定範囲の内外でリンクを分断した形で道路ネットワークデータを用意しておく方法をとることができる。
また、別の態様として、リンクの一部の区間を特定して横断可能情報を設定するようにしてもよい。例えば、横断可能情報に、それが適用されるべきリンクの区間を特定する情報を付す方法を採ることができる。こうすることにより、リンクを分断するまでなく、上述の態様と同様の経路探索を実現することが可能となる。
【００１０】
さらに別の態様として、
前記経路探索部は、前記横断リンクから所定範囲外に存在する領域を前記横断可能な領域として、前記経路探索を行うものとしてもよい。
つまり、経路探索する際に、所定範囲を回避して仮想的な横断経路を設定する方法である。こうすることにより、所定範囲を考慮して横断可能情報の設定等をするデータ整備上の負荷を軽減することができる。また、道路ネットワークデータに変動が生じた場合、それに応じて横断可能情報を変更する必要もない点でも負荷が軽減できる。「所定範囲外に存在する領域」とは、所定範囲の外側に、所定範囲とは別に「横断可能な領域」が設定されている必要はなく、単に所定範囲を除く領域を横断可能な領域として使う場合も含む。
【００１１】
本発明においては、自動車用か歩行者用かに関わらず、
前記経路探索部は、前記仮想的な横断経路については、前記横断リンクを通過する経路よりも優先度を下げて経路探索を行うものとしてもよい。
仮想的な横断経路は、予めリンクが整備された経路に比べて、通行できるか否かに不確定性が高いおそれがある。上述の態様によれば、仮想的な横断経路の優先度を下げることによって、このように不確定性が高い経路の利用を抑制することができる。
優先度を下げる方法としては、例えば、仮想的な横断経路に対しては経路探索用のコストを高く設定する方法、仮想的な横断経路を通過する経路とそうでない経路とのコスト差が所定範囲内であれば仮想的な横断経路を通過しない経路を選択する方法などが考えられる。
【００１２】
以上で説明した本発明においては、さらに、探索された経路について、前記仮想的な横断経路とその他の経路とで案内態様を切り替えて案内を行う経路案内部を備えるものとしてもよい。
こうすることにより、利用者は、案内された経路が、仮想的な横断経路か否かを容易に判断することができ、仮想的な横断経路であることを意識しながら通行することができる。
案内態様の切り替えは種々の方法で行うことができる。例えば、表示態様を切り替えてもよいし、仮想的な横断経路であることを音声で案内するようにしてもよい。
【００１３】
本発明は、その他、コンピュータによって経路探索を行うための経路探索方法として構成してもよいし、かかる経路探索をコンピュータに実行させるためのコンピュータプログラムとして構成してもよい。また、かかるコンピュータプログラムを記録したコンピュータが読み取り可能な記録媒体として構成してもよい。記録媒体としては、フレキシブルディスクやＣＤ−ＲＯＭ、光磁気ディスク、ＩＣカード、ＲＯＭカートリッジ、パンチカード、バーコードなどの符号が印刷された印刷物、コンピュータの内部記憶装置（ＲＡＭやＲＯＭなどのメモリ）および外部記憶装置等、コンピュータが読取り可能な種々の媒体を利用できる。
【図面の簡単な説明】
【００１４】
【図１】従来技術における経路探索例を示す説明図である。
【図２】実施例としての経路探索システムの構成を示す説明図である。
【図３】道路ネットワークデータの構造例を示す説明図である。
【図４】経路探索例を示す説明図である。
【図５】経路探索処理のフローチャートである。
【図６】変形例としての経路探索処理のフローチャートである。
【図７】経路案内処理のフローチャートである。
【図８】経路案内表示例を示す説明図である。
【図９】変形例における経路探索例を示す説明図である。
【発明を実施するための形態】
【実施例１】
【００１５】
Ａ．装置構成：
図２は実施例としての経路探索システムの構成を示す説明図である。実施例の経路探索システムは、端末１００とサーバ２００をネットワークＩＮＴで接続して構成されている。端末１００としては、パーソナルコンピュータ、携帯電話、スマートフォン、ＰＮＤ（ポータブル・ナビゲーション・システム）などを用いることができる。端末１００、サーバ２００ともに、ＣＰＵ、ＲＡＭ、ＲＯＭなどを有するコンピュータとして構成されており、それぞれ図示する機能ブロックを実現するためのコンピュータプログラムをインストールすることによって、本実施例の経路探索システムとして機能する。
本実施例では、端末１００とサーバ２００からなるシステムを例示するが、両者の機能をスタンドアロンで稼働する単一の装置で実現してもよいし、更に多くのコンピュータからなる分散システムとして構成してもよい。
【００１６】
サーバ２００には、地図データ記憶部２５０、道路ネットワークデータ記憶部２６０が用意されている。地図データ記憶部２５０は、地図を表示するためのポリゴンデータなどからなる地図データを記憶したデータベースである。道路ネットワークデータ記憶部２６０は、道路網をノードおよびリンクで表した道路ネットワークデータを記憶したデータベースである。道路ネットワークデータには、リンク、ノードの形状、位置等を特定するデータの他、リンク同士を関連づけるペアデータ（横断可能情報に相当するもの）が属性情報として格納されている。道路ネットワークデータの具体的内容については、後で説明する。
経路探索部２３０は、道路ネットワークデータ記憶部２６０に記憶されたネットワークデータを利用して、端末１００を介して利用者によって指定された出発地から目的地までの経路を探索する。経路探索は、例えば、ダイクストラ法を用いることができ、後述する通り、上述のペアデータを用いて、予めリンク、ノードが整備されていない場所の通行を許容して行うことができる。仮想リンク生成部２４０は、かかる経路探索を実現するために、ペアデータに基づいて、仮想的な横断経路に対応するリンク（以下、「仮想リンク」という）を設定する。
経路案内データ生成部２２０は、道路ネットワークデータ記憶部２６０、地図データ記憶部２５０にそれぞれ格納されたデータを用いて経路案内用のデータを生成する。
通信部２１０は、サーバ２００でのこれらの処理において、端末１００との通信を制御する。
【００１７】
端末１００において、通信部１２０は、サーバ２００との通信を制御する。
コマンド入力部１３０からは、ユーザの操作に基づいて出発地、目的地の指定など経路探索、経路案内に必要な情報が入力される。
ＧＰＳ（Global  Positioning  System）１４０は、端末１００の位置情報を緯度経度などの座標値で取得する。
探索結果記憶部１５０は、サーバ２００から経路探索結果を受け取り、一時的に記憶するメモリである。
表示制御部１６０は、端末１００の表示内容を制御する。制御対象には、例えば、出発地、目的地を指定するための画面、経路案内を行う際の地図や経路を表示する画面などが含まれる。
【００１８】
図３は道路ネットワークデータの構造例を示す説明図である。道路ＲＤＡ付近の歩道上には、リンクＬＡ１〜ＬＡ３、ＬＢ、ＬＣ１〜ＬＣ３、ＬＤ、ノードＮＡ１〜ＮＡ４、ＮＢ１、ＮＢ２、ＮＣ１〜ＮＣ４、ＮＤ１、ＮＤ２が設定されている。また、道路ＲＤＡを横断するためのリンクＬＣＷ（以下、「横断リンク」ということもある）が設定されている。
道路ネットワークデータにおいて、ノードは通常、ノードＮＡ１，ＮＡ２、ＮＡ４など（図中の黒丸で示したノード）のように、リンク同士の交点に設けられている。本実施例では、かかるノードの他にノードＮＡ３、ＮＣ２（図中の白丸で示したノード）を設定した。ノードＮＡ３は、本来一本のリンクとして構成しても差し支えない部分を敢えてリンクＬＡ２、ＬＡ３の２つに分割するために設定されている。ノードＮＣ３は、同様に、リンクＬＣ２、ＬＣ３の２つに分割するために設定されている。ノードＮＡ３、ＮＣ３が設けられている位置は、横断リンクＬＣＷから所定の距離Ｄだけ離れた地点である。距離Ｄは、任意に設定可能であるが、本実施例では３０メートルとした。
【００１９】
図３中にリンクＬＡ３、ＬＢ、ＬＣ３、ＬＤのデータ例を示した。いずれも道路ネットワークデータの一部として、これらのリンクに格納されている内容を示すものである。リンクＬＡ３には、名称、位置、ペアデータなどの情報が格納されている。この他にも道路種別、階段や斜面の有無などの属性情報を格納してもよい。位置は、リンクＬＡ３の端点に当たるノードＮＡ３、ＮＡ４の座標およびこれらの間に位置する点列が座標値で特定される。ペアデータは、属性情報の一つであり、リンク同士を関連づけるデータである。リンクＬＡ３には、リンクＬＣ３、ＬＤが関連づけられていることを表している。他のリンクＬＢ、ＬＣ３、ＬＤも同様の形式でデータが格納されている。
【００２０】
ここで、ペアデータについて説明する。本実施例では、後述する通り、関連づけられたリンク間では、任意の場所で横断可能として経路探索を行う。このような横断可能な範囲を特定するのがペアデータである。
図３の例に即して説明する。通常はリンクＬＡ３からリンクＬＣ３に移動するためには、横断リンクＬＣＷを通ることが求められる。これに対し、本実施例では、リンクＬＡ３には、ペアデータによって、リンクＬＣ３が関連づけられているから、リンクＬＡ３からリンクＬＣ３には、横断リンクＬＣＷ以外の任意の部分で横断可能とするのである。
本実施例では、リンクＬＡ３の垂線と交差するリンクを、リンクＬＡ３に関連づけるものとした。図３に示すとおり、リンクＬＡ３の端点ＮＡ３を通る垂線ＮＬ１がリンクＬＣ３と交差するため、リンクＬＣ３が関連づけられる。この垂線ＮＬ１はリンクＬＣ２とも交差するが、リンクＬＣ２は横断リンクＬＣＷから距離Ｄの範囲内にあるため、除外する。この意味については、後述する。リンクＬＡ３の他の端点ＮＡ４を通る垂線ＮＬ３は、リンクＬＤと交差するため、リンクＬＡ３にはリンクＬＤも関連づけられている。
同様にして、リンクＬＣ３には、リンクＬＡ３が関連づけられる。ノードＮＣ３、ＮＣ４を通る垂線ＮＬ２がリンクＬＡ３と交差するからである。
リンクＬＡ３には、リンクＬＣ３、ＬＤの２本が関連づけられているのに対し、逆にリンクＬＣ３には、リンクＬＡ３のみが関連づけられているように、ペアデータは、必ずしも１対１に関連づけるものでなくてもよい。
リンクＬＢ、ＬＤにも同様にしてペアデータが設定される。リンクＬＡ１、ＬＡ２、ＬＣ１、ＬＣ２は、横断リンクＬＣＷから距離Ｄ内にあるので、いずれもペアデータは設定されていない。
【００２１】
横断リンクＬＣＷから距離Ｄ内の領域（以下、「任意横断禁止領域」という）にはペアデータを設定しないデータ内容とすることによって、任意横断禁止領域内では、横断リンクＬＣＷを通らずに道路ＲＤＡを横断する経路が探索されることを回避できる。横断リンクＬＣＷの付近では、ここを通る経路とすることが安全などの観点から好ましいからである。
【００２２】
図３では、ノードＮＡ３、ＮＣ３を設けることで、任意横断禁止領域内のリンク（ＬＡ１、ＬＡ２、ＬＣ１、ＬＣ２）とその他のリンク（ＬＡ３、ＬＣ３）とを分ける例を示した。こうすることによって、リンクＬＡ３、ＬＣ３については、リンク全体を対象としてペアデータを設定することができ、データ構造の簡素化を図ることができる。
変形例として、リンクＬＡ２、ＬＡ３およびリンクＬＣ２、ＬＣ３をそれぞれ一本のリンク（リンクＬＡ２＋ＬＡ３、リンクＬＣ２＋ＬＣ３と表すものとする）にまとめた形のデータとしてもよい。この場合には、ペアデータにおいて、関連づけられたリンクは、リンクＬＡ３、ＬＣ３に相当する部分についてのみ使用するようにしておけばよい。例えば、リンクＬＡ２＋ＬＡ３側のペアデータにおいて、リンクＬＣ２＋ＬＣ３を関連づけるとともに、ノードＮＡ３の座標などでリンクＬＡ３に相当する部分を特定するのである。
【００２３】
Ｂ．経路探索処理：
図４は経路探索例を示す説明図である。出発地ＳＴから目的地ＧＬまでの経路を探索する様子を図４（ａ）〜図４（ｃ）の順に示した。
図４（ａ）に示すように、経路探索では、出発地ＳＴおよび目的地ＧＬから、それぞれ到達可能なノードを探索し、コストを計算した結果を、ラベルＬＶａ、ＬＶｂとして付与する。
次に、図４（ｂ）に示すように、ラベルＬＶａ、ＬＶｂを付した地点から、到達可能なノードを探索し、ラベルＬＶｆ、ＬＶｄを付与する。
これと併せて、本実施例では、ペアデータによって関連づけられているリンク間に仮想リンクを設定する。図の例では、破線Ｌｂｅで示すように、ラベルＬＶｂから垂線を下ろした地点にラベルＬＶｅを付す。ラベルＬＶａからも垂線Ｌａｃを下ろした地点にラベルＬＶｃを付す。このように仮想リンクによってラベルを付した点を仮想ノードと称する。ここでは、垂線Ｌｂｅ，Ｌａｃを下ろして仮想ノードを設定する方法を示したが、ペアリンク上の最短距離にある通常のノードを仮想ノードと扱うようにしてもよい。
こうして仮想リンクを設けて、それぞれ経路探索を継続すると、図４（ｃ）に示すように、経路ＲＴ１〜ＲＴ３が得られる。これらの経路のコストを評価し、最適な経路を選択することになる。このように、本実施例では、横断リンクを通る経路ＲＴ１だけでなく、仮想リンクを通行することで道路を任意の地点で渡る経路ＲＴ２、ＲＴ３が得られる点が特徴である。
【００２４】
図５は経路探索処理のフローチャートである。図４に示した経路探索を実現するための処理であり、ハードウェア的にはサーバ２００のＣＰＵが実行する処理である。処理内容は、経路探索部２３０、仮想リンク生成部２４０が実行する処理に相当する。
処理を開始すると、ＣＰＵは、ユーザによって端末１００が操作されて出発地、目的地が入力されると（ステップＳ１０）、経路探索を実行する（ステップＳ２０）。その手順は、次の通りである。
まず、ＣＰＵは各端点から到達できるノードへ新規ラベルを生成する（ステップＳ２１）。端点とは、それまでに探索されている経路の端点という意味である。経路探索を開始した当初は、出発地、目的地が端点となる。
そして、各端点からペアリンク、つまりペアデータによって関連づけられたリンクの仮想ノードに対し新規ラベルを生成する（ステップＳ２２）。仮想ノードは、例えば、図４（ｂ）で示したように、端点からペアリンクに対して下ろした垂線の足とすることができる。端点にペアデータが設定されていない場合には、ステップＳ２２では、新規ラベルは生成されないことになる。
こうして新規ラベルを付すと、ＣＰＵは、それぞれコストを評価し、経路探索を行う（ステップＳ２３）。仮想リンクは、通常のリンクと異なり、予めコストを設定しておくことはできない。従って、ステップＳ２３では、仮想リンクの長さを算出し、この長さに基づいて、所定の計算式でコストを設定することになる。このコストは、通常のリンクと同じ式を用いるようにしてもよいし、通常のリンクよりも高い値となるようにしてもよい。後者の態様とすることにより、仮想リンクを通る経路が選択されることを抑制できる。仮想リンクは、通常のリンクと異なり、通行可能性や、通行の安全性を十分に保証できない場合があるので、かかる経路を抑制的にすることが好ましい場合もあるからである。
ＣＰＵは、以上の処理を、出発地から目的地に至る経路が完成するまで（ステップＳ２４）、繰り返し実行し、経路探索が完了すると、探索結果を出力して（ステップＳ３０）、経路探索処理を終了する。この処理によって、図４に示す経路探索を実現することができる。
【００２５】
図５では、図３に示したように、任意横断禁止領域外のリンクに対してのみペアデータが設定されている場合の経路探索処理を示した。かかる場合には、任意横断禁止領域を考慮することなく、経路探索を行っても、この領域内では、横断リンクＬＣＷ以外の地点で横断する経路となることを回避できる。
これに対し、任意横断禁止領域の回避は、経路探索時に考慮するようにしてもよい。この処理について以下、変形例として説明する。
【００２６】
図６は変形例としての経路探索処理のフローチャートである。
ＣＰＵは、出発地、目的地を入力し（ステップ１０）、経路探索を実行する（ステップＳ２０Ａ）。
まず、各端点から到達できるノードへ新規ラベルを生成する（ステップＳ２１Ａ）。そして、各端点のうち横断リンクからの距離が所定値Ｄ以上のものを抽出し（ステップＳ２２Ａ）、抽出された端点からペアリンクの仮想ノードに対して新規ラベルを生成する（ステップＳ２３Ａ）。そして、図５で説明したのと同じく仮想リンクの距離等に応じてコストを設定した上でコスト評価をし、経路を選択する（ステップＳ２４Ａ）。以上の処理を繰り返して、出発地から目的地までの経路が完成すると（ステップＳ２５Ａ）、探索結果を出力する（ステップＳ３０）。
【００２７】
変形例の処理のように、任意横断禁止領域外にある端点のみから仮想リンクを生成することによって、この領域での自由横断を回避することができる。
変形例の処理を用いる場合には、図３に示すデータ構造において、リンクＬＡ２＋ＬＡ３、リンクＬＣ２＋ＬＣ３のように、ノードＮＡ３、ＮＣ３でリンクを分割することなくデータを用意し、しかもペアデータもリンクＬＡ３、ＬＣ３の区分を特定せずに設定しておけばよいため、データ構造の簡素化を図ることができる利点がある。
【００２８】
Ｃ．経路案内処理：
次に、経路案内について説明する。
図７は経路案内処理のフローチャートである。サーバ２００が案内に必要なデータを生成した上で、端末１００のＣＰＵが出力処理を分担することによって実現されるものである。経路案内部２２０、表示制御部１６０が実行する処理に相当する。
【００２９】
処理を開始すると、端末１００のＣＰＵは、経路探索結果を読み込む（ステップＳ５０）。経路探索結果は、経路に沿って通行するリンク、ノードを順次規定するとともに、仮想ノード、仮想リンクを通行する場合には、その位置座標を規定するデータとして用意されている。経路探索結果を読み込むと、ＣＰＵは、以下の手順で、案内処理を実行する。
ＧＰＳ１４０から現在位置の情報を取得し（ステップＳ５２）、現在位置、経路を表示するとともに、音声案内を行う（ステップＳ５４）。図中に経路の表示例を示した。本実施例では、仮想リンクに相当する経路と通常のリンクに相当する経路とで経路案内時の表示を変える。図の例では、通常のリンクに相当する経路は実線で示し、仮想リンクに相当する経路は破線で示した。表示態様は任意に設定可能であり、色や線の太さを変えるなどの態様としてもよい。
また音声案内は、現在位置とノードおよび仮想ノードとの位置関係に基づいて行う。ＣＰＵは、現在位置が仮想ノードに対応する位置付近に到達したと判断した場合には、図示しないスピーカから単に「道路を横断します」などの進行方向の案内に加えて、「横断歩道がないので気をつけて下さい」のように仮想リンクを通る経路であることを知らせるようにしてもよい。
ＣＰＵは以上の処理を目的地に到着するまで繰り返し実行する（ステップＳ５６）。
【００３０】
経路案内時に仮想リンクを通る経路の表示および音声出力は種々の態様をとることができる。
図８は経路案内表示例を示す説明図である。
図８（ａ）は、図７の処理で説明した態様に相当するものである。通常のリンク部分は実線、仮想リンクは破線のように、異なる表示態様で表示する。また、仮想ノードＶＮ１に到達する前に、仮想リンクを通る旨の音声案内を行う。
図８（ｂ）は、仮想ノードＶＮ１の直前直後に位置する通常のノードＮ１、Ｎ２を対角線上の頂点とする平行四辺形領域（図中のハッチング）を表示する例を示した。経路探索時には、図８（ａ）に示した破線の経路が得られているが、経路案内時には仮想リンクについては明示せず、横断可能な領域として示す態様である。この場合、音声案内は、直前のノードＮ１に到達する前に、「道路を渡って下さい」のように横断する旨を知らせる。
図８（ｃ）も、仮想ノードＶＮ１の直前直後に位置する通常のノードＮ１、Ｎ２を利用して案内を表示する。この例では、矩形領域を表示するのではなく、ノードＮ１、Ｎ２を結ぶ経路を破線で表示するのである。経路探索時に得られる仮想リンク（図８（ａ）の経路）とは異なり、道路を横断する旨を利用者に直感的に知らせることができる方法で経路を知らせる態様である。音声案内は、ノードＮ１の直前で「道路を渡って下さい」のように横断する旨を知らせる。
このように、経路案内時の表示および音声案内は種々の態様をとることができる。仮想リンクは、通常のリンクと異なり、歩道などのように整備された通路とは異なる部分を通るものであるから、必ずしも経路探索結果を厳密に案内する必要はなく、利用者が進行方向を直感的に把握可能であればよい。図８で例示した以外に種々の案内態様をとることができる。
【００３１】
Ｄ．効果および変形例：
本実施例の経路探索システムによれば、リンク同士をペアデータで関連づけておくことにより、横断リンクが設定されていない箇所でも任意に横断可能として経路を探索することができる。こうすることにより、横断リンクが遠方にある場合に無用な迂回経路を探索することなく、実用的な経路を探索することができる。
【００３２】
実施例では、道路の両側にあるリンク同士を関連づける例を示したが、リンクの関連付けは、種々の態様で行うことが可能である。
図９は変形例における経路探索例を示す説明図である。この例では、道路ネットワークデータが細部の道路も含めて整備されている整備領域Ａ、Ｂ間で出発地から目的地までの経路を探索する例を示した。整備領域Ａ、Ｂの間には、道路ネットワークデータが全くまたは十分に整備されていない非整備領域が存在する。
本実施例を、かかる場合にも適用するためには、整備領域Ａ、Ｂ間のリンクＬＡ１、ＬＡ２をペアデータで関連づけておく。こうすることにより、出発地からリンクＬＡ１上のノードＮＡ１までの経路ＰＡ１、および目的地からリンクＬＡ２上のノードＮＡ２までの経路ＰＡ２が得られると、それぞれのノードＮＡ１、ＮＡ２から他方のリンクＬＡ２、ＬＡ１に垂線を下ろして仮想ノードＶＮＡ２、ＶＮＡ１を設定して仮想リンク（ＮＡ１→ＶＮＡ２およびＮＡ２→ＶＮＡ１）を設定することができる。こうすることで整備領域Ａ、Ｂをまたぐ経路探索を実現することができる。得られた探索結果は、非整備領域内の具体的な経路を示すものではないが、かかる領域でも、進むべき方向を利用者が判断できる程度の情報を提示することは可能である。
経路案内時には、ノードＮＡ１，ＶＮＡ２、ＮＡ２、ＶＮＡ１を通る接続領域を表示すればよい。こうすることによって、利用者は、具体的な経路の表示がなくても、概ねの進行方向を判断することができ、経路探索結果に従って、整備領域Ａから整備領域Ｂに到達することが可能となる。図９の表示に変えて、図８（ａ）、図８（ｃ）のように、仮想リンク等を表示してもよい。仮想リンクは、非整備領域内の経路に沿ったものである必要はなく、領域内の家屋等を突き抜ける状態で描かれる直線的なもので構わない。かかる表示であっても、利用者に対して、概ねの進行方向を提示することは可能だからである。
【００３３】
以上、本発明の実施例について説明した。経路探索システムは、必ずしも上述した実施例の全ての機能を備えている必要はなく、一部のみを実現するようにしてもよい。また、上述した内容に追加の機能を設けてもよい。
本発明は上述の実施例に限定されず、その趣旨を逸脱しない範囲で種々の構成を採ることができることはいうまでもない。例えば、実施例においてハードウェア的に構成されている部分は、ソフトウェア的に構成することもでき、その逆も可能である。
実施例では、歩行者用の経路探索システムを例示したが、例えば、図９に示した例などは、自動車用の経路探索システムとして適用することもできる。
【産業上の利用可能性】
【００３４】
本発明は、リンクが整備されていない部分の通行を許容する出発地から目的地までの経路探索に利用可能である。
【符号の説明】
【００３５】
１００…端末
１１０…主制御部
１２０…通信部
１３０…コマンド入力部
１４０…ＧＰＳ
１５０…探索結果記憶部
１６０…表示制御部
２００…サーバ
２１０…通信部
２２０…経路案内部
２３０…経路探索部
２４０…仮想リンク生成部
２５０…地図データ記憶部
２６０…道路ネットワークデータ記憶部
【図２】
2012202885.tif 000003
【図３】
2012202885.tif 000004
【図４】
2012202885.tif 000005
【図５】
2012202885.tif 000006
【図６】
2012202885.tif 000007
【図７】
2012202885.tif 000008
【図８】
2012202885.tif 000009
【図９】
2012202885.tif 000010
【図１】
2012202885.tif 000011