説明

経路探索システム

【課題】 道路を横断するために無用な迂回を柔軟に回避できる実用的な経路探索を行う。
【解決手段】 歩行者用の経路探索システムにおいて、道路の両側に位置するリンク同士を、予めペアとして関連づけておく。経路探索時には、ペアとして設定されたリンク間は任意の場所で横断可能という条件で経路を探索する。つまり、予め横断用のリンクが設定されていない場所でも、一方のリンクから他方のリンクに垂線をおろし、そこに仮想ノードLVeを設定することによって、仮想的なリンクを生成するのである。こうすることによって出発地STから目的地GLに至る経路を探索する際には、この仮想的なリンクを通る経路RT2を得ることができ、横断歩道を経由する経路RT1のように無用な迂回を回避した経路を探索することができる。

【発明の詳細な説明】
【技術分野】
【0001】
本発明は、道路ネットワークデータを用いて出発地から目的地までの経路探索を行う経路探索システムに関する。
【背景技術】
【0002】
道路ネットワークを用いて経路探索、経路案内をするナビゲーションシステムが普及している。近年では、歩行者が通行する歩道などに設定された歩行者ネットワークデータを用いて歩行者用に経路探索、案内を行う歩行者用のナビゲーションシステムも実用化されるようになってきている。歩行者用のナビゲーションシステムにおいては、1本の道路の両側にある歩道上に設定されたリンク同士は、経路探索上は別々の道路として扱われるため、両者間を横断できるようにデータを整備しておく必要がある。
特許文献1では、かかる観点から、横断歩道をリンクとして設定する他、横断歩道以外の場所でも、道路の両側の歩道間を横断するための横断用のリンクを設定している。特許文献2では、歩行者ネットワークデータを自動生成する際に、一定幅以上の道路の交差点には自動的に横断用のリンクを生成している。
【先行技術文献】
【特許文献】
【0003】
【特許文献1】特開2007−78655号公報
【特許文献2】特開2004−301956号公報
【発明の概要】
【発明が解決しようとする課題】
【0004】
従来技術では、ノード、リンクを用いて経路探索を行っていたため、リンクが設定されていない場所を通行する経路は探索することができず、無用に大回りする経路が探索される場合があった。
図1は従来技術における経路探索例を示す説明図である。出発地STから目的地GLまでの経路探索の結果を示している。道路RDの両側には歩道が設けられており、横断歩道CWで横断可能となっている。この条件下で経路探索を行うと、経路PS1(実線)のように、横断歩道CWを通過する経路が得られる。しかし、横断歩道CW以外の場所でも道路RDを横断することを許容すれば、経路PS2(破線)のように、最短距離の適切な経路が存在するのである。従って、経路PS1は、無用な大回りをしていることになる。
特許文献1で開示されているように、横断歩道が存在する場所以外にも、横断用のリンクを設けることにより上述の課題を回避しようとすれば、歩行者ネットワークデータを整備する負担が大きくなるという別の課題を招いてしまう。
無用な大回りが生じるという課題は、歩行者用のナビゲーションシステムに特有のものではなく、自動車用のナビゲーションシステムにおいても、道路ネットワークが十分に整備されていない場所では、同様に生じ得る問題であった。
本発明は、かかる課題に鑑み、自動車用か歩行者用かを問わず、リンクが整備されていない場所も通行可能な経路探索を実現することを目的とする。
【課題を解決するための手段】
【0005】
本発明の経路探索システムは、
経路を探索する経路探索システムであって、
道路網をノードおよびリンクで表した道路ネットワークデータを記憶する道路ネットワークデータ記憶部と、
前記道路ネットワークデータを用いて、指定された出発地から指定された目的地までの経路を探索する経路探索部とを備え、
前記道路ネットワークデータは、複数のリンクにつき、該リンク同士を結ぶ横断リンクの存否にかかわらず一方のリンクから他方のリンクに横断可能であることを示す横断可能情報を有しており、
前記経路探索部は、前記横断可能情報で関連づけられたリンク間では、前記横断リンクの位置にかかわらず、一方のリンクから他方のリンクへの仮想的な横断経路をひくことにより経路探索を実行するものである。
横断リンクとは、道路網を表すリンクと異なるものではなく、上述の横断可能情報が定義されたリンク間を連結するリンクを便宜上、横断リンクと称するものである。
【0006】
本発明の経路探索システムによれば、道路ネットワークデータには、横断可能情報が付されている。そして、経路探索部は、横断可能情報で関連づけられたリンク間では、仮想的な横断経路をひくことにより経路探索を実行することができる。従って、リンクが設定されていない場所を通行する経路を探索することが可能となる。仮想的な横断経路は、一時的にリンクを設定することにより形成する方法としてもよいし、単に横断時にコストを加算するという方法、つまり経路を単に想定した状態探索を行う方法など、種々の方法でひくことができる。
本発明の経路探索システムは、自動車用または歩行者用に限定されるものではなく、道路ネットワークデータも、自動車用に整備されたものであっても、歩行者用に整備されたものであってもよい。
横断可能情報で関連づけられるリンクは、必ずしも1対1である必要はない。3本以上のリンクを相互に関連づけるものとしてもよいし、1対2、1対3などの態様で関連づけしてもよい。横断可能情報は、種々の態様で格納可能であり、例えば、道路ネットワークデータのリンクに対して属性などの形式で格納してもよいし、ノード、リンクのデータとは別のデータとして道路ネットワーク記憶部に格納してもよい。
【0007】
上述の経路探索は、種々の方法で実現可能である。仮想的な横断経路は、例えば、横断可能情報で関連づけられたリンクの一方から他方に下ろした垂線や、これらのリンク上の端点のノード同士を結ぶ線分などとすることができる。仮想的な横断経路とリンクとの交点にノードが設定されていない場合には、仮想的なノードを設定してもよい。こうして設定された仮想的な横断経路に対して、その長さなどに応じて、経路探索用のコストを設定することにより、経路探索を行うことが可能となる。
【0008】
本発明は、歩行者用の経路探索システムとしてもよい。
例えば、
前記道路ネットワークデータは、歩行者が通行する道路網を表しており、
前記横断可能情報が付される複数のリンクは、道路の両側に存在する歩道に対応するリンクとすることができる。
こうすれば、道路の両側に設定されたリンク間を任意の場所で横断することを許容した経路探索を実現することができる。歩行者は、道路を自由な場所で横断できるなど、自動車以上に移動の自由度が高いのが通常であるから、本発明の経路探索は、特に有用性が高い。ここで、「道路の両側に存在する歩道」とは、必ずしも車道と区別された歩道だけを意味するものではなく、歩行者用の道路網として道路の両側にリンクが設定されている場合も含む。
【0009】
歩行者用の経路探索システムにおいては、
前記横断可能情報は、前記横断リンクから所定範囲外に存在するリンクに対して設定されているものとしてもよい。
こうすることによって、横断歩道など道路を横断するように設けられたリンク付近では、仮想的な横断経路を設定することを回避できる。横断歩道など横断用に設けられたリンクが付近にある場合には、これらの場所を通る経路の方が、安全性が高いと考えられるため、上述の態様によれば、通行の安全性も考慮した経路探索を実現することができることになる。「所定範囲外に存在するリンク」とは、リンク全体が所定範囲外にあるものだけを意味するものではなく、リンクの一部が所定範囲外にあるものも含む。
上述の態様を実現するためには、例えば、上述の所定範囲の内外でリンクを分断した形で道路ネットワークデータを用意しておく方法をとることができる。
また、別の態様として、リンクの一部の区間を特定して横断可能情報を設定するようにしてもよい。例えば、横断可能情報に、それが適用されるべきリンクの区間を特定する情報を付す方法を採ることができる。こうすることにより、リンクを分断するまでなく、上述の態様と同様の経路探索を実現することが可能となる。
【0010】
さらに別の態様として、
前記経路探索部は、前記横断リンクから所定範囲外に存在する領域を前記横断可能な領域として、前記経路探索を行うものとしてもよい。
つまり、経路探索する際に、所定範囲を回避して仮想的な横断経路を設定する方法である。こうすることにより、所定範囲を考慮して横断可能情報の設定等をするデータ整備上の負荷を軽減することができる。また、道路ネットワークデータに変動が生じた場合、それに応じて横断可能情報を変更する必要もない点でも負荷が軽減できる。「所定範囲外に存在する領域」とは、所定範囲の外側に、所定範囲とは別に「横断可能な領域」が設定されている必要はなく、単に所定範囲を除く領域を横断可能な領域として使う場合も含む。
【0011】
本発明においては、自動車用か歩行者用かに関わらず、
前記経路探索部は、前記仮想的な横断経路については、前記横断リンクを通過する経路よりも優先度を下げて経路探索を行うものとしてもよい。
仮想的な横断経路は、予めリンクが整備された経路に比べて、通行できるか否かに不確定性が高いおそれがある。上述の態様によれば、仮想的な横断経路の優先度を下げることによって、このように不確定性が高い経路の利用を抑制することができる。
優先度を下げる方法としては、例えば、仮想的な横断経路に対しては経路探索用のコストを高く設定する方法、仮想的な横断経路を通過する経路とそうでない経路とのコスト差が所定範囲内であれば仮想的な横断経路を通過しない経路を選択する方法などが考えられる。
【0012】
以上で説明した本発明においては、さらに、探索された経路について、前記仮想的な横断経路とその他の経路とで案内態様を切り替えて案内を行う経路案内部を備えるものとしてもよい。
こうすることにより、利用者は、案内された経路が、仮想的な横断経路か否かを容易に判断することができ、仮想的な横断経路であることを意識しながら通行することができる。
案内態様の切り替えは種々の方法で行うことができる。例えば、表示態様を切り替えてもよいし、仮想的な横断経路であることを音声で案内するようにしてもよい。
【0013】
本発明は、その他、コンピュータによって経路探索を行うための経路探索方法として構成してもよいし、かかる経路探索をコンピュータに実行させるためのコンピュータプログラムとして構成してもよい。また、かかるコンピュータプログラムを記録したコンピュータが読み取り可能な記録媒体として構成してもよい。記録媒体としては、フレキシブルディスクやCD−ROM、光磁気ディスク、ICカード、ROMカートリッジ、パンチカード、バーコードなどの符号が印刷された印刷物、コンピュータの内部記憶装置(RAMやROMなどのメモリ)および外部記憶装置等、コンピュータが読取り可能な種々の媒体を利用できる。
【図面の簡単な説明】
【0014】
【図1】従来技術における経路探索例を示す説明図である。
【図2】実施例としての経路探索システムの構成を示す説明図である。
【図3】道路ネットワークデータの構造例を示す説明図である。
【図4】経路探索例を示す説明図である。
【図5】経路探索処理のフローチャートである。
【図6】変形例としての経路探索処理のフローチャートである。
【図7】経路案内処理のフローチャートである。
【図8】経路案内表示例を示す説明図である。
【図9】変形例における経路探索例を示す説明図である。
【発明を実施するための形態】
【実施例1】
【0015】
A.装置構成:
図2は実施例としての経路探索システムの構成を示す説明図である。実施例の経路探索システムは、端末100とサーバ200をネットワークINTで接続して構成されている。端末100としては、パーソナルコンピュータ、携帯電話、スマートフォン、PND(ポータブル・ナビゲーション・システム)などを用いることができる。端末100、サーバ200ともに、CPU、RAM、ROMなどを有するコンピュータとして構成されており、それぞれ図示する機能ブロックを実現するためのコンピュータプログラムをインストールすることによって、本実施例の経路探索システムとして機能する。
本実施例では、端末100とサーバ200からなるシステムを例示するが、両者の機能をスタンドアロンで稼働する単一の装置で実現してもよいし、更に多くのコンピュータからなる分散システムとして構成してもよい。
【0016】
サーバ200には、地図データ記憶部250、道路ネットワークデータ記憶部260が用意されている。地図データ記憶部250は、地図を表示するためのポリゴンデータなどからなる地図データを記憶したデータベースである。道路ネットワークデータ記憶部260は、道路網をノードおよびリンクで表した道路ネットワークデータを記憶したデータベースである。道路ネットワークデータには、リンク、ノードの形状、位置等を特定するデータの他、リンク同士を関連づけるペアデータ(横断可能情報に相当するもの)が属性情報として格納されている。道路ネットワークデータの具体的内容については、後で説明する。
経路探索部230は、道路ネットワークデータ記憶部260に記憶されたネットワークデータを利用して、端末100を介して利用者によって指定された出発地から目的地までの経路を探索する。経路探索は、例えば、ダイクストラ法を用いることができ、後述する通り、上述のペアデータを用いて、予めリンク、ノードが整備されていない場所の通行を許容して行うことができる。仮想リンク生成部240は、かかる経路探索を実現するために、ペアデータに基づいて、仮想的な横断経路に対応するリンク(以下、「仮想リンク」という)を設定する。
経路案内データ生成部220は、道路ネットワークデータ記憶部260、地図データ記憶部250にそれぞれ格納されたデータを用いて経路案内用のデータを生成する。
通信部210は、サーバ200でのこれらの処理において、端末100との通信を制御する。
【0017】
端末100において、通信部120は、サーバ200との通信を制御する。
コマンド入力部130からは、ユーザの操作に基づいて出発地、目的地の指定など経路探索、経路案内に必要な情報が入力される。
GPS(Global Positioning System)140は、端末100の位置情報を緯度経度などの座標値で取得する。
探索結果記憶部150は、サーバ200から経路探索結果を受け取り、一時的に記憶するメモリである。
表示制御部160は、端末100の表示内容を制御する。制御対象には、例えば、出発地、目的地を指定するための画面、経路案内を行う際の地図や経路を表示する画面などが含まれる。
【0018】
図3は道路ネットワークデータの構造例を示す説明図である。道路RDA付近の歩道上には、リンクLA1〜LA3、LB、LC1〜LC3、LD、ノードNA1〜NA4、NB1、NB2、NC1〜NC4、ND1、ND2が設定されている。また、道路RDAを横断するためのリンクLCW(以下、「横断リンク」ということもある)が設定されている。
道路ネットワークデータにおいて、ノードは通常、ノードNA1,NA2、NA4など(図中の黒丸で示したノード)のように、リンク同士の交点に設けられている。本実施例では、かかるノードの他にノードNA3、NC2(図中の白丸で示したノード)を設定した。ノードNA3は、本来一本のリンクとして構成しても差し支えない部分を敢えてリンクLA2、LA3の2つに分割するために設定されている。ノードNC3は、同様に、リンクLC2、LC3の2つに分割するために設定されている。ノードNA3、NC3が設けられている位置は、横断リンクLCWから所定の距離Dだけ離れた地点である。距離Dは、任意に設定可能であるが、本実施例では30メートルとした。
【0019】
図3中にリンクLA3、LB、LC3、LDのデータ例を示した。いずれも道路ネットワークデータの一部として、これらのリンクに格納されている内容を示すものである。リンクLA3には、名称、位置、ペアデータなどの情報が格納されている。この他にも道路種別、階段や斜面の有無などの属性情報を格納してもよい。位置は、リンクLA3の端点に当たるノードNA3、NA4の座標およびこれらの間に位置する点列が座標値で特定される。ペアデータは、属性情報の一つであり、リンク同士を関連づけるデータである。リンクLA3には、リンクLC3、LDが関連づけられていることを表している。他のリンクLB、LC3、LDも同様の形式でデータが格納されている。
【0020】
ここで、ペアデータについて説明する。本実施例では、後述する通り、関連づけられたリンク間では、任意の場所で横断可能として経路探索を行う。このような横断可能な範囲を特定するのがペアデータである。
図3の例に即して説明する。通常はリンクLA3からリンクLC3に移動するためには、横断リンクLCWを通ることが求められる。これに対し、本実施例では、リンクLA3には、ペアデータによって、リンクLC3が関連づけられているから、リンクLA3からリンクLC3には、横断リンクLCW以外の任意の部分で横断可能とするのである。
本実施例では、リンクLA3の垂線と交差するリンクを、リンクLA3に関連づけるものとした。図3に示すとおり、リンクLA3の端点NA3を通る垂線NL1がリンクLC3と交差するため、リンクLC3が関連づけられる。この垂線NL1はリンクLC2とも交差するが、リンクLC2は横断リンクLCWから距離Dの範囲内にあるため、除外する。この意味については、後述する。リンクLA3の他の端点NA4を通る垂線NL3は、リンクLDと交差するため、リンクLA3にはリンクLDも関連づけられている。
同様にして、リンクLC3には、リンクLA3が関連づけられる。ノードNC3、NC4を通る垂線NL2がリンクLA3と交差するからである。
リンクLA3には、リンクLC3、LDの2本が関連づけられているのに対し、逆にリンクLC3には、リンクLA3のみが関連づけられているように、ペアデータは、必ずしも1対1に関連づけるものでなくてもよい。
リンクLB、LDにも同様にしてペアデータが設定される。リンクLA1、LA2、LC1、LC2は、横断リンクLCWから距離D内にあるので、いずれもペアデータは設定されていない。
【0021】
横断リンクLCWから距離D内の領域(以下、「任意横断禁止領域」という)にはペアデータを設定しないデータ内容とすることによって、任意横断禁止領域内では、横断リンクLCWを通らずに道路RDAを横断する経路が探索されることを回避できる。横断リンクLCWの付近では、ここを通る経路とすることが安全などの観点から好ましいからである。
【0022】
図3では、ノードNA3、NC3を設けることで、任意横断禁止領域内のリンク(LA1、LA2、LC1、LC2)とその他のリンク(LA3、LC3)とを分ける例を示した。こうすることによって、リンクLA3、LC3については、リンク全体を対象としてペアデータを設定することができ、データ構造の簡素化を図ることができる。
変形例として、リンクLA2、LA3およびリンクLC2、LC3をそれぞれ一本のリンク(リンクLA2+LA3、リンクLC2+LC3と表すものとする)にまとめた形のデータとしてもよい。この場合には、ペアデータにおいて、関連づけられたリンクは、リンクLA3、LC3に相当する部分についてのみ使用するようにしておけばよい。例えば、リンクLA2+LA3側のペアデータにおいて、リンクLC2+LC3を関連づけるとともに、ノードNA3の座標などでリンクLA3に相当する部分を特定するのである。
【0023】
B.経路探索処理:
図4は経路探索例を示す説明図である。出発地STから目的地GLまでの経路を探索する様子を図4(a)〜図4(c)の順に示した。
図4(a)に示すように、経路探索では、出発地STおよび目的地GLから、それぞれ到達可能なノードを探索し、コストを計算した結果を、ラベルLVa、LVbとして付与する。
次に、図4(b)に示すように、ラベルLVa、LVbを付した地点から、到達可能なノードを探索し、ラベルLVf、LVdを付与する。
これと併せて、本実施例では、ペアデータによって関連づけられているリンク間に仮想リンクを設定する。図の例では、破線Lbeで示すように、ラベルLVbから垂線を下ろした地点にラベルLVeを付す。ラベルLVaからも垂線Lacを下ろした地点にラベルLVcを付す。このように仮想リンクによってラベルを付した点を仮想ノードと称する。ここでは、垂線Lbe,Lacを下ろして仮想ノードを設定する方法を示したが、ペアリンク上の最短距離にある通常のノードを仮想ノードと扱うようにしてもよい。
こうして仮想リンクを設けて、それぞれ経路探索を継続すると、図4(c)に示すように、経路RT1〜RT3が得られる。これらの経路のコストを評価し、最適な経路を選択することになる。このように、本実施例では、横断リンクを通る経路RT1だけでなく、仮想リンクを通行することで道路を任意の地点で渡る経路RT2、RT3が得られる点が特徴である。
【0024】
図5は経路探索処理のフローチャートである。図4に示した経路探索を実現するための処理であり、ハードウェア的にはサーバ200のCPUが実行する処理である。処理内容は、経路探索部230、仮想リンク生成部240が実行する処理に相当する。
処理を開始すると、CPUは、ユーザによって端末100が操作されて出発地、目的地が入力されると(ステップS10)、経路探索を実行する(ステップS20)。その手順は、次の通りである。
まず、CPUは各端点から到達できるノードへ新規ラベルを生成する(ステップS21)。端点とは、それまでに探索されている経路の端点という意味である。経路探索を開始した当初は、出発地、目的地が端点となる。
そして、各端点からペアリンク、つまりペアデータによって関連づけられたリンクの仮想ノードに対し新規ラベルを生成する(ステップS22)。仮想ノードは、例えば、図4(b)で示したように、端点からペアリンクに対して下ろした垂線の足とすることができる。端点にペアデータが設定されていない場合には、ステップS22では、新規ラベルは生成されないことになる。
こうして新規ラベルを付すと、CPUは、それぞれコストを評価し、経路探索を行う(ステップS23)。仮想リンクは、通常のリンクと異なり、予めコストを設定しておくことはできない。従って、ステップS23では、仮想リンクの長さを算出し、この長さに基づいて、所定の計算式でコストを設定することになる。このコストは、通常のリンクと同じ式を用いるようにしてもよいし、通常のリンクよりも高い値となるようにしてもよい。後者の態様とすることにより、仮想リンクを通る経路が選択されることを抑制できる。仮想リンクは、通常のリンクと異なり、通行可能性や、通行の安全性を十分に保証できない場合があるので、かかる経路を抑制的にすることが好ましい場合もあるからである。
CPUは、以上の処理を、出発地から目的地に至る経路が完成するまで(ステップS24)、繰り返し実行し、経路探索が完了すると、探索結果を出力して(ステップS30)、経路探索処理を終了する。この処理によって、図4に示す経路探索を実現することができる。
【0025】
図5では、図3に示したように、任意横断禁止領域外のリンクに対してのみペアデータが設定されている場合の経路探索処理を示した。かかる場合には、任意横断禁止領域を考慮することなく、経路探索を行っても、この領域内では、横断リンクLCW以外の地点で横断する経路となることを回避できる。
これに対し、任意横断禁止領域の回避は、経路探索時に考慮するようにしてもよい。この処理について以下、変形例として説明する。
【0026】
図6は変形例としての経路探索処理のフローチャートである。
CPUは、出発地、目的地を入力し(ステップ10)、経路探索を実行する(ステップS20A)。
まず、各端点から到達できるノードへ新規ラベルを生成する(ステップS21A)。そして、各端点のうち横断リンクからの距離が所定値D以上のものを抽出し(ステップS22A)、抽出された端点からペアリンクの仮想ノードに対して新規ラベルを生成する(ステップS23A)。そして、図5で説明したのと同じく仮想リンクの距離等に応じてコストを設定した上でコスト評価をし、経路を選択する(ステップS24A)。以上の処理を繰り返して、出発地から目的地までの経路が完成すると(ステップS25A)、探索結果を出力する(ステップS30)。
【0027】
変形例の処理のように、任意横断禁止領域外にある端点のみから仮想リンクを生成することによって、この領域での自由横断を回避することができる。
変形例の処理を用いる場合には、図3に示すデータ構造において、リンクLA2+LA3、リンクLC2+LC3のように、ノードNA3、NC3でリンクを分割することなくデータを用意し、しかもペアデータもリンクLA3、LC3の区分を特定せずに設定しておけばよいため、データ構造の簡素化を図ることができる利点がある。
【0028】
C.経路案内処理:
次に、経路案内について説明する。
図7は経路案内処理のフローチャートである。サーバ200が案内に必要なデータを生成した上で、端末100のCPUが出力処理を分担することによって実現されるものである。経路案内部220、表示制御部160が実行する処理に相当する。
【0029】
処理を開始すると、端末100のCPUは、経路探索結果を読み込む(ステップS50)。経路探索結果は、経路に沿って通行するリンク、ノードを順次規定するとともに、仮想ノード、仮想リンクを通行する場合には、その位置座標を規定するデータとして用意されている。経路探索結果を読み込むと、CPUは、以下の手順で、案内処理を実行する。
GPS140から現在位置の情報を取得し(ステップS52)、現在位置、経路を表示するとともに、音声案内を行う(ステップS54)。図中に経路の表示例を示した。本実施例では、仮想リンクに相当する経路と通常のリンクに相当する経路とで経路案内時の表示を変える。図の例では、通常のリンクに相当する経路は実線で示し、仮想リンクに相当する経路は破線で示した。表示態様は任意に設定可能であり、色や線の太さを変えるなどの態様としてもよい。
また音声案内は、現在位置とノードおよび仮想ノードとの位置関係に基づいて行う。CPUは、現在位置が仮想ノードに対応する位置付近に到達したと判断した場合には、図示しないスピーカから単に「道路を横断します」などの進行方向の案内に加えて、「横断歩道がないので気をつけて下さい」のように仮想リンクを通る経路であることを知らせるようにしてもよい。
CPUは以上の処理を目的地に到着するまで繰り返し実行する(ステップS56)。
【0030】
経路案内時に仮想リンクを通る経路の表示および音声出力は種々の態様をとることができる。
図8は経路案内表示例を示す説明図である。
図8(a)は、図7の処理で説明した態様に相当するものである。通常のリンク部分は実線、仮想リンクは破線のように、異なる表示態様で表示する。また、仮想ノードVN1に到達する前に、仮想リンクを通る旨の音声案内を行う。
図8(b)は、仮想ノードVN1の直前直後に位置する通常のノードN1、N2を対角線上の頂点とする平行四辺形領域(図中のハッチング)を表示する例を示した。経路探索時には、図8(a)に示した破線の経路が得られているが、経路案内時には仮想リンクについては明示せず、横断可能な領域として示す態様である。この場合、音声案内は、直前のノードN1に到達する前に、「道路を渡って下さい」のように横断する旨を知らせる。
図8(c)も、仮想ノードVN1の直前直後に位置する通常のノードN1、N2を利用して案内を表示する。この例では、矩形領域を表示するのではなく、ノードN1、N2を結ぶ経路を破線で表示するのである。経路探索時に得られる仮想リンク(図8(a)の経路)とは異なり、道路を横断する旨を利用者に直感的に知らせることができる方法で経路を知らせる態様である。音声案内は、ノードN1の直前で「道路を渡って下さい」のように横断する旨を知らせる。
このように、経路案内時の表示および音声案内は種々の態様をとることができる。仮想リンクは、通常のリンクと異なり、歩道などのように整備された通路とは異なる部分を通るものであるから、必ずしも経路探索結果を厳密に案内する必要はなく、利用者が進行方向を直感的に把握可能であればよい。図8で例示した以外に種々の案内態様をとることができる。
【0031】
D.効果および変形例:
本実施例の経路探索システムによれば、リンク同士をペアデータで関連づけておくことにより、横断リンクが設定されていない箇所でも任意に横断可能として経路を探索することができる。こうすることにより、横断リンクが遠方にある場合に無用な迂回経路を探索することなく、実用的な経路を探索することができる。
【0032】
実施例では、道路の両側にあるリンク同士を関連づける例を示したが、リンクの関連付けは、種々の態様で行うことが可能である。
図9は変形例における経路探索例を示す説明図である。この例では、道路ネットワークデータが細部の道路も含めて整備されている整備領域A、B間で出発地から目的地までの経路を探索する例を示した。整備領域A、Bの間には、道路ネットワークデータが全くまたは十分に整備されていない非整備領域が存在する。
本実施例を、かかる場合にも適用するためには、整備領域A、B間のリンクLA1、LA2をペアデータで関連づけておく。こうすることにより、出発地からリンクLA1上のノードNA1までの経路PA1、および目的地からリンクLA2上のノードNA2までの経路PA2が得られると、それぞれのノードNA1、NA2から他方のリンクLA2、LA1に垂線を下ろして仮想ノードVNA2、VNA1を設定して仮想リンク(NA1→VNA2およびNA2→VNA1)を設定することができる。こうすることで整備領域A、Bをまたぐ経路探索を実現することができる。得られた探索結果は、非整備領域内の具体的な経路を示すものではないが、かかる領域でも、進むべき方向を利用者が判断できる程度の情報を提示することは可能である。
経路案内時には、ノードNA1,VNA2、NA2、VNA1を通る接続領域を表示すればよい。こうすることによって、利用者は、具体的な経路の表示がなくても、概ねの進行方向を判断することができ、経路探索結果に従って、整備領域Aから整備領域Bに到達することが可能となる。図9の表示に変えて、図8(a)、図8(c)のように、仮想リンク等を表示してもよい。仮想リンクは、非整備領域内の経路に沿ったものである必要はなく、領域内の家屋等を突き抜ける状態で描かれる直線的なもので構わない。かかる表示であっても、利用者に対して、概ねの進行方向を提示することは可能だからである。
【0033】
以上、本発明の実施例について説明した。経路探索システムは、必ずしも上述した実施例の全ての機能を備えている必要はなく、一部のみを実現するようにしてもよい。また、上述した内容に追加の機能を設けてもよい。
本発明は上述の実施例に限定されず、その趣旨を逸脱しない範囲で種々の構成を採ることができることはいうまでもない。例えば、実施例においてハードウェア的に構成されている部分は、ソフトウェア的に構成することもでき、その逆も可能である。
実施例では、歩行者用の経路探索システムを例示したが、例えば、図9に示した例などは、自動車用の経路探索システムとして適用することもできる。
【産業上の利用可能性】
【0034】
本発明は、リンクが整備されていない部分の通行を許容する出発地から目的地までの経路探索に利用可能である。
【符号の説明】
【0035】
100…端末
110…主制御部
120…通信部
130…コマンド入力部
140…GPS
150…探索結果記憶部
160…表示制御部
200…サーバ
210…通信部
220…経路案内部
230…経路探索部
240…仮想リンク生成部
250…地図データ記憶部
260…道路ネットワークデータ記憶部


【特許請求の範囲】
【請求項1】
経路を探索する経路探索システムであって、
道路網をノードおよびリンクで表した道路ネットワークデータを記憶する道路ネットワークデータ記憶部と、
前記道路ネットワークデータを用いて、指定された出発地から指定された目的地までの経路を探索する経路探索部とを備え、
前記道路ネットワークデータは、複数のリンクにつき、該リンク同士を結ぶ横断リンクの存否にかかわらず一方のリンクから他方のリンクに横断可能であることを示す横断可能情報を有しており、
前記経路探索部は、前記横断可能情報で関連づけられたリンク間では、前記横断リンクの位置にかかわらず、一方のリンクから他方のリンクへの仮想的な横断経路をひくことにより経路探索を実行する経路探索システム。
【請求項2】
請求項1記載の経路探索システムであって、
前記道路ネットワークデータは、歩行者が通行する道路網を表しており、
前記横断可能情報が付される複数のリンクは、道路の両側に存在する歩道に対応するリンクである経路探索システム。
【請求項3】
請求項2記載の経路探索システムであって、
前記横断可能情報は、前記横断リンクから所定範囲外に存在するリンクに対して設定されている経路探索システム。
【請求項4】
請求項2記載の経路探索システムであって、
前記経路探索部は、前記横断リンクから所定範囲外に存在する領域を前記横断可能な領域として、前記経路探索を行う経路探索システム。
【請求項5】
請求項1〜4いずれか記載の経路探索システムであって、
前記経路探索部は、前記仮想的な横断経路を通過する経路については、前記横断リンクを通過する経路よりも優先度を下げて経路探索を行う経路探索システム。
【請求項6】
請求項1〜5いずれか記載の経路探索システムであって、
さらに、探索された経路について、前記仮想的な横断経路とその他の経路とで案内態様を切り替えて案内を行う経路案内部を備える経路探索システム。

【図2】
image rotate

【図3】
image rotate

【図4】
image rotate

【図5】
image rotate

【図6】
image rotate

【図7】
image rotate

【図8】
image rotate

【図9】
image rotate

【図1】
image rotate


【公開番号】特開2012−202885(P2012−202885A)
【公開日】平成24年10月22日(2012.10.22)
【国際特許分類】
【出願番号】特願2011−69056(P2011−69056)
【出願日】平成23年3月28日(2011.3.28)
【出願人】(597151563)株式会社ゼンリン (155)
【Fターム(参考)】