(57)【特許請求の範囲】
【請求項１】
経路探索を行う経路探索装置であって、
ノード、リンクを要素として表された通路データを記憶する通路データ記憶部と、
前記それぞれのノード及びリンクの少なくとも一方に対応づけられたコストを記憶するコスト記憶部と、
出発地、目的地に対応するノードを選択する指示を入力する指示入力部と、
前記通路データ記憶部及び前記コスト記憶部の記憶内容に基づいて出発地から目的地までの経路を探索する経路探索部とを備え、
前記経路探索部は、
複数の候補経路上の候補ノードについて、前記出発地から前記候補ノードに至るまでに経過した経過ノード及び経過リンクの少なくとも一方に対応付けられたコストの積算値を表すラベル情報を生成し、前記候補ノードに対応付けて記憶するラベル情報記憶部と、
前記コスト積算値の大小関係に基づいて前記候補経路のいずれかを選択する選択部と、
前記ラベル情報記憶部と、選択部とを繰り返し用いて前記目的地に至る経路を探索する探索遂行部とを備え、
前記ラベル情報記憶部は、前記候補ノードに２以上のラベル情報を対応付けて記憶し、前記候補ノードに至る直前の所定区間の経路を特定する直前経路情報を、各ラベル情報に含めて記憶する経路探索装置。
【請求項２】
請求項１記載の経路探索装置であって、
少なくとも一部のノードについて、通過方法についての規制情報を記憶する規制情報記憶部を備え、前記選択部は、該規制情報を考慮して前記選択を行う経路探索装置。
【請求項３】
請求項２記載の経路探索装置であって、
前記規制情報は、Ｎ点（Ｎは３以上の自然数）のノードによって定義される規制であり、前記直前経路情報は、Ｎ−２点のノードに相当する区間の経路情報である経路探索装置。
【請求項４】
請求項１または２に記載の経路探索装置であって、
前記直前経路情報は、直前の候補ノードにおける複数のラベル情報から一のラベル情報を特定する情報である経路探索装置。
【請求項５】
経路探索を行う経路探索装置であって、
ノード、リンクを要素として表された通路データを記憶する通路データ記憶部と、
前記それぞれのノード及びリンクの少なくとも一方に対応づけられたコストを記憶するコスト記憶部と、
出発地、目的地に対応するノードを選択する指示を入力する指示入力部と、
前記通路データ記憶部及び前記コスト記憶部の記憶内容に基づいて出発地から目的地までの経路を探索する経路探索部とを備え、
前記経路探索部は、
複数の候補経路上の候補ノードについて、前記出発地から前記候補ノードに至るまでに経過した経過ノード及び経過リンクの少なくとも一方に対応付けられたコストの積算値を表すラベル情報を生成し、前記候補ノードに対応付けて記憶するラベル情報記憶部と、
前記コスト積算値の大小関係に基づいて前記候補経路のいずれかを選択する選択部と、
前記ラベル情報記憶部と、選択部とを繰り返し用いて前記目的地に至る経路を探索する探索遂行部とを備え、
前記ラベル情報記憶部は、前記候補ノードに２以上のラベル情報を対応付けて記憶し、前記候補ノードに至る直前の所定区間の経路を特定する直前経路情報を、各ラベル情報に含めて記憶すると共に前記直前経路情報の少なくとも一部が重複するラベル情報の生成を抑制する経路探索装置。
【請求項６】
コンピュータに経路探索を行わせるためのコンピュータプログラムであって、
ノード、リンクを要素として表された通路データを記憶する通路データ記憶機能と、
前記それぞれのノード及びリンクの少なくとも一方に対応づけられたコストを記憶するコスト記憶機能と、
出発地、目的地に対応するノードを選択する指示を入力する指示入力機能と、
前記通路データ記憶機能及び前記コスト記憶機能の記憶内容に基づいて出発地から目的地までの経路を探索する経路探索機能とを備え、
前記経路探索機能は、
複数の候補経路上の候補ノードについて、前記出発地から前記候補ノードに至るまでに経過した経過ノード及び経過リンクの少なくとも一方に対応付けられたコストの積算値を表すラベル情報を生成し、前記候補ノードに対応付けて記憶するラベル情報記憶機能と、
前記コスト積算値の大小関係に基づいて前記候補経路のいずれかを選択する選択機能と、
前記ラベル情報記憶機能と、選択機能とを繰り返し用いて前記目的地に至る経路を探索する探索遂行機能とを備え、
前記ラベル情報記憶機能は、前記候補ノードに２以上のラベル情報を対応付けて記憶し、前記候補ノードに至る直前の所定区間の経路を特定する直前経路情報を、各ラベル情報に含めて記憶するコンピュータプログラム。
【請求項７】
請求項６に記載のコンピュータプログラムであって、
前記直前経路情報は、直前の候補ノードにおける複数のラベル情報から一のラベル情報を特定する情報であるコンピュータプログラム。
【請求項８】
請求項６または７記載のコンピュータプログラムを記録したコンピュータ読み取り可能な記録媒体。
【請求項９】
コンピュータを用いて経路探索を行う方法であって、
ノード、リンクを要素として表された通路データを記憶する通路データ記憶工程と、
前記それぞれのノード及びリンクの少なくとも一方に対応づけられたコストを記憶するコスト記憶工程と、
出発地、目的地に対応するノードを選択する指示を入力する指示入力工程と、
前記通路データ記憶工程及び前記コスト記憶工程の記憶内容に基づいて出発地から目的地までの経路を探索する経路探索工程とを備え、
前記経路探索工程は、
複数の候補経路上の候補ノードについて、前記出発地から前記候補ノードに至るまでに経過した経過ノード及び経過リンクの少なくとも一方に対応付けられたコストの積算値を表すラベル情報を生成し、前記候補ノードに対応付けて記憶するラベル情報記憶工程と、
前記コスト積算値の大小関係に基づいて前記候補経路のいずれかを選択する選択工程と、
前記ラベル情報記憶工程と、選択工程とを繰り返し用いて前記目的地に至る経路を探索する探索遂行工程とを備え、
前記ラベル情報記憶工程では、前記候補ノードに２以上のラベル情報を対応付けて記憶し、前記候補ノードに至る直前の所定区間の経路を特定する直前経路情報を、各ラベル情報に含めて記憶する方法。
【請求項１０】
請求項９に記載の方法であって、
前記直前経路情報は、直前の候補ノードにおける複数のラベル情報から一のラベル情報を特定する情報である方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、通過方法の規制に応じた経路探索を行うための技術に関する。
【０００２】
【従来の技術】
近年、経路探索装置の利用分野は非常に広範囲なものとなっている。例えば、いわゆるカーナビゲーションシステムの多くは経路探索機能を備えている。車の運転手は現在位置や目的地を設定することにより、所望の経路を探索することができる。
【０００３】
経路探索は、ダイクストラ法によって行われることが多い。ダイクストラ法とは、通行路をノード、リンクの集合で表すとともに、各リンク等に通行距離に応じたコストを割り当て、出発地から目的地までの総コストが最小となるような経路を探索する手法をいう。
【０００４】
【発明が解決しようとする課題】
しかし、ダイクストラ法では、通過方法に規制がある場合については、適切な経路探索を行うことができなかった。
【０００５】
図１は、通過方法の規制がある通路を例示する説明図である。図１でノードＡ，Ｂ，Ｃ，Ｄは、リンクによって接続されている。ここで各リンクは正整数コスト値を有している。例えば、ノードＢは、ノードＡ及びＣとリンクで接続される。ノードＡと接続するリンクはコストが３であり、ノードＣと接続するリンクのコストは２である。またノードＢはノードＤと接続するリンクを有さないが、ノードＣを中継点とした、リンクＢＣ及びＣＤから構成される経路が存在する。なお、経路のコストはそこに含むリンクが有するコストの総和で与えられて、前述の経路Ｂ→Ｃ→Ｄのコストは４である。
【０００６】
ここでユーザは、出発地ノードＡから目的地ノードＤまでの経路の探索を所望しているものとする。
【０００７】
ダイクストラ法においては、出発ノード等を一方の端点とした候補経路について、リンクを辿りながら探索を行う。このとき、ノードごとに出発地ノードからそのノードまでの総コストをラベルデータとして記録する。あるノードへの候補経路の延伸は、そのノードのラベルデータに記憶されたコストを改善可能な場合にのみ行う。すなわち、既にラベルデータが記憶されたノードに延伸する新しい候補経路が現れた場合、その候補経路の総コストとラベルデータに記憶されたコスト値との大小関係により経路の選択を行う。新たな経路の総コストの方が小さい場合には、ラベルデータの書き換えを行う。このような手順を繰り返すことで、目的地ノードまで最小コストで到達する経路を探索することができる。
【０００８】
ところが、かかる従来の経路探索技術では、ノードやリンクの通過方法に規制がある場合には対処できない。図１では規制の例として、ノードＡからノードＣへ進んだ場合における右折禁止規制があるものとする。つまり、経路「Ａ→Ｃ→Ｄ」を禁止する規制である。なお、図１で例示したような、ノード、リンク、コストからなる抽象的構造を、以下グラフと呼ぶ。
【０００９】
この例の場合、従来の経路探索装置は、出発ノードＡから中途ノードＣに至るコスト１の経路を発見すると、その他の候補経路は、コストが１より大きいことからノードＣに至る経路として選択される余地がなかった。すなわち、「Ａ→Ｂ→Ｃ」や「Ａ→Ｃ→Ｂ→Ｃ」と辿るコスト５の候補経路は、コスト１の候補経路「Ａ→Ｃ」とのコスト比較によって排除されていた。その一方、「Ａ→Ｃ→Ｄ」の経路は、規制に反するため選択することはできない。この結果、規制に反しない経路として、「Ａ→Ｂ→Ｃ→Ｄ」、「Ａ→Ｃ→Ｂ→Ｃ→Ｄ」という経路が存在するにもかかわらず、所望する経路探索結果を得ることができなかった。
【００１０】
上記課題を解決する方法の一つとして、例えば、特開平７−２９４２６７号記載の技術が提案されてはいる。この技術は、単にノードを接続しただけでなく方向を有する有向リンクとして各リンクを定義しており、経路探索時には各リンクにラベルが付される。また、ラベルには、そのリンクに至る直前のリンクを指定する情報が含まれる。このように、直前のリンクを指定する情報を含めつつ、各リンクにラベルを付すことにより、交通規制がある場合でも経路探索を実現することができるとされている。しかしながら、この技術では、４点以上のノードで規制される交通規制については、やはり適切な探索を行うことができなかった。
【００１１】
かかる課題は図１を利用して説明した場合に限らず、通過方法の規制がある通路の経路探索を実現する場合において共通する課題であった。
【００１２】
本発明は、これらの課題を解決するためになされたものであり、通過方法の規制がある通路の探索を実現するための技術の実現を目的とする。
【００１３】
【課題を解決するための手段およびその作用・効果】
上記課題の少なくとも一部を解決するために、本発明では、次の構成を適用した。
本発明の第一の経路探索装置は、
経路探索を行う経路探索装置であって、
ノード、リンクを要素として表された通路データを記憶する通路データ記憶部と、
前記それぞれのノード及びリンクの少なくとも一方に対応づけられたコストを記憶するコスト記憶部と、
出発地、目的地に対応するノードを選択する指示を入力する指示入力部と、
前記通路データ記憶部及び前記コスト記憶部の記憶内容に基づいて出発地から目的地までの経路を探索する経路探索部とを備え、
前記経路探索部は、
複数の候補経路上のノードについて、前記出発地から該ノードに至るまでに経過した経過ノード及び経過リンクの少なくとも一方に対応付けられたコストの積算値を表すラベル情報を生成し、該ノードに対応付けて記憶するラベル情報記憶部と、
前記コスト積算値の大小関係に基づいて前記候補経路のいずれかを選択する選択部と、
前記ラベル情報記憶部と、選択部とを繰り返し用いて前記目的地に至る経路を探索する探索遂行部とを備え、
前記ラベル情報記憶部は、
前記ノードに２以上のラベル情報を対応付けて記憶可能であるとともに、
２以上のラベル情報を記憶する場合には、前記ノードに至る直前の所定区間の経路を特定する直前経路情報を、各ラベル情報に含めて記憶することを要旨とする。
【００１４】
このように本発明では、候補経路の端点、すなわち出発地から最遠方のノードまたはリンクに、２以上のラベル情報を記憶させることを許容する。つまり、端点には、コストが最小とはならない候補経路についても、ラベル情報を記憶する。したがって、コスト以外の要素によって経路の選択を行う余地を持たせることができ、柔軟な経路探索を実現することができる。コスト以外の要素としては、例えば、通行規制、直線道路を優先するなどといった運転者の嗜好、国道優先等の要素が挙げられる。
【００１５】
なお、直前経路情報は直前の所定区間の経路を特定するものであるが、ノード、リンクによる順序列や集合で特定してもよいし、直前のノードまたはリンクに対応付けられたラベルを指定することにより、帰納的に直前経路を特定してもよい。
【００１６】
また、本発明の第２の経路探索装置は、
経路探索を行う経路探索装置であって、
ノード、リンクを要素として表された通路データを記憶する通路データ記憶部と、
前記それぞれのノード及びリンクの少なくとも一方に対応づけられたコストを記憶するコスト記憶部と、
出発地、目的地に対応するノードを選択する指示を入力する指示入力部と、
前記通路データ記憶部及び前記コスト記憶部の記憶内容に基づいて出発地から目的地までの経路を探索する経路探索部とを備え、
前記経路探索部は、
複数の候補経路上のノードについて、前記出発地から該ノードに至るまでに経過した経過ノード及び経過リンクの少なくとも一方に対応付けられたコストの積算値を表すラベル情報を生成し、該ノードに対応付けて記憶するラベル情報記憶部と、
前記コスト積算値の大小関係に基づいて前記候補経路のいずれかを選択する選択部と、
前記ラベル情報記憶部と、選択部とを繰り返し用いて前記目的地に至る経路を探索する探索遂行部とを備え、
前記ラベル情報は、該ノードに至る直前のノードに対応したラベル情報を特定する直前経路情報情報を含むことを要旨とする。
【００１７】
ラベル情報には、直前経路に対応するラベル情報を記憶する。４点以上のノードで規制される交通規制である多点規制の場合、直前の経路を特定するためのノードまたはリンクが多数必要となって、データ量が多くなる。これに対し、ラベル情報の指定によって帰納的に直前経路を特定可能とする場合には、多点規制であってもデータ量の増大を抑制することができる。
【００１８】
また、柔軟なラベル処理を実現することができる。一つの直前経路情報の変更により、帰納的な変更を行うことができる。
【００１９】
ここで、１つのノードに複数のラベル情報を付与することを許容しない経路探索を行う場合でも、直前経路に対応する別のラベル情報を特定するラベル情報を利用する方式は適用可能である。本発明の第二の経路探索装置においても、直前経路に対応する別のラベル情報を特定するラベル情報を利用する方式は適用可能である。
【００２０】
本発明の経路探索装置において、
少なくとも一部のノードについて、通過方法についての規制情報を記憶する規制情報記憶部を備え、
前記選択部は、該規制情報を考慮して前記選択を行うものとしてもよい。
【００２１】
このようにすることで、通過方法の規制がある場合でも、柔軟な経路探索を実現することができる。
【００２２】
本発明の経路探索装置において、
前記規制情報は、Ｎ点（Ｎは３以上の自然数）のノードによって定義される規制であり、
前記直前経路情報は、Ｎ−２点のノードに相当する区間の経路情報であるものとしてもよい。
【００２３】
端点へのラベル情報を無制限に記憶させる場合には、実質的に同一のラベル情報が重複して記憶される可能性がある。上述の通り、Ｎ点で規制情報が定義されている場合には、Ｎ−２点のノードに相当する区間の経路が異なるラベル情報を区別して記憶するものとすれば、実質的に同一のラベル情報の重複を避けることができる。
【００２４】
本発明の経路探索装置において、
前記ラベル情報記憶部は、前記直前経路の情報の少なくとも一部が重複するラベル情報の生成を抑制するものとしてもよい。
【００２５】
このようにすることで、直接の有用性を持たない多数のラベル情報を大量に作成することによる弊害を抑制でき、例えば、ラベル情報記憶部の容量を低減することができる。
【００２６】
本発明は、経路探索装置としての態様の他、コンピュータに経路探索を行わせるためのコンピュータプログラムや、コンピュータを用いて経路探索を行う方法など種々の態様で構成することが可能である。また、コンピュータに経路探索を行わせるためのコンピュータプログラムと同視し得る信号として構成してもよい。さらに、これらのコンピュータプログラムを記録した記録媒体として構成してもよい。
【００２７】
ここで記憶媒体としては、フレキシブルディスクやＣＤ−ＲＯＭ、光磁気ディスク、ＩＣカード、ＲＯＭカートリッジ、パンチカード、バーコードなどの符号が印刷された印刷物、コンピュータの内部記憶装置（ＲＡＭやＲＯＭなどのメモリ）および外部記憶装置などコンピュータが読取り可能な種々の媒体を利用できる。
【００２８】
【発明の実施の形態】
以下、本発明の実施の形態について、経路探索装置の実施例に基づき説明する。
Ａ．経路探索装置：
Ｂ．４点規制：
Ｃ．リンクに対応したラベルデータ：
Ｄ．コスト以外の要素に基づく経路選択：
【００２９】
Ａ．経路探索装置：
図２は、経路探索装置の概略構成図である。経路探索装置１００は、無線通信又はＣＤ（Ｃｏｍｐａｃｔ  Ｄｉｓｋ）等を利用して、探索対象となるグラフや規制を特定する地図データを取得する。また、ＧＰＳ（Ｇｌｏｂａｌ  Ｐｏｓｉｔｉｏｎｉｎｇ  Ｓｙｓｔｅｍ）やその他のセンシング装置を利用して地図データと自らの位置を対比することが可能である。ユーザは、リモコン１０３又は操作パネル１０１等を利用して経路探索装置１００に経路探索を行わせることができる。経路探索装置１００は表示デバイス１０２を備えており、経路探索結果をユーザに出力する。
【００３０】
図２には経路探索装置１００の機能ブロック構成を併せて示した。経路探索装置１００は、ＣＰＵおよびメモリ等を備えたマイクロコンピュータとして構成された制御ユニット２００を備えており、図示する機能ブロックは、それぞれ制御ユニット２００の機能としてソフトウェア的に構成されている。もっとも、各機能ブロックは、ハードウェア的に構成しても構わない。なお図２に示した制御ユニット２００は一体的に構成する場合を示したが、互いに通信する複数の装置が全体として制御ユニット２００を構成するものとしてもよい。例えば、ローカル接続する２つの装置に物理的に分離する場合や、その他ネットワークを利用して構成する場合が考えられる。
【００３１】
地図データ入力部２０１は、地図データを入力する機能を備える。地図データには、図１で示したようなノード、リンク、コスト及びその他の情報に関するグラフデータを含む。また地図データは規制データを含む。規制データは、グラフにおける通過方法の規制を特定するデータである。なお、地図データにはその他にも種々の情報を含んでもよい。例えばグラフと対応付けた施設情報を含んでもよい。また、地図データ入力部２０１は、ＣＤのような情報記憶媒体を利用して地図データを入力してもよいし、インターネット、無線ネットワークその他のネットワークを介して入力してもよい。
【００３２】
地図記憶部４００は、地図データ入力部２０１が入力するグラフデータや規制データを記憶する。地図記憶部４００の一部は規制情報記憶部４１０として構成されており、規制データを記憶する。
【００３３】
位置情報入力部２０２は、現在の位置の情報を入力する。位置情報は、ＧＰＳの機能によって生成される。また、その他のセンシングシステムの機能によっても生成される。後者の機能については、例えば、車両に搭載されたカーナビゲーションシステムの場合、車両の車軸やハンドル等に備えられた回転センサを基礎とした位置情報を、位置情報入力部２０２が入力する。
【００３４】
ユーザ入力部２２０は、リモコン１０３を介したユーザ入力を入力する。またユーザ入力は操作パネル１０１に基づいても与えられ、ユーザ入力部２２０はこれも入力する（図中には明示せず）。ユーザはリモコン１０３や操作パネル１０１を利用することで、経路探索を実行させることができる。また、経路の探索における、出発地や目的地その他の探索条件を入力することができる。例えば、探索経路の出発地について、位置情報入力部２０２が入力する位置情報が示す現在位置を採用するか否かを指定することが可能である。
【００３５】
経路探索部３００は、ユーザ入力部２２０から受ける探索の指示に基づいて経路探索を行う。このとき、地図記憶部４００からグラフデータ及び規制データを、位置情報入力部２０２から位置情報を受けて、これらを利用する。経路探索部３００は、経路探索にあたって、候補経路のコスト情報や直前経路情報を含むラベルデータを生成・記憶して利用する。経路探索部３００は、その一部をラベル保持部３１０と探索処理部３１１として構成している。これらについては後述する。
【００３６】
表示制御部２１０は表示制御機能を備えており、経路探索部３００における探索結果を表示デバイス１０２に出力することで、これをユーザに提供することができる。
【００３７】
図３は、経路探索装置で用いるデータの概略構成図である。ここには図１で利用したグラフを再掲している。このグラフを利用して、地図記憶部４００が行う記憶の詳細について以下で説明する。また、図３に示したグラフでは、ノードＢにラベルＬ１とラベルＬ２を付している。これは、経路探索部３００における探索処理において利用するラベルデータの一例を示したものである。図３におけるラベルＬ１、Ｌ２を利用して、経路探索部３００が探索処理にあたって生成・記憶するラベルデータについて説明する。ここで、図３に示したグラフでは、各リンクに対応するコストは括弧でくくって示している。
【００３８】
地図記憶部４００は、その一部をノード記憶部４２０、リンク記憶部４２１、規制情報記憶部４１０として構成している。
【００３９】
ノード記憶部４２０は、図中に模式的に示す通り、グラフのノードを記憶する。表の各欄にはグラフのノードの名前を記憶する。なお、ノードの属性、ノードに接続されているリンク名、ノードに付されたラベル名、関係する規制名等を併せて記憶するものとしてもよい。
【００４０】
リンク記憶部４２１は、リンクごとに、名前、端点である２つのノードの名前、及び、そのリンクに付されたコストの値を組みにして記憶する。なお、端点である２つのノードについて、本実施例では順序を考慮していないが、いわゆる有向リンクを含むデータについては、その旨及びノードの順序に関する情報も記憶すればよい。
【００４１】
規制情報記憶部４１０は、通路の規制に関する規制データを記憶する。図３に示したグラフは、既述のように、経路Ａ→Ｃ→Ｄにかかる右折禁止規制を有する。かかる規制は、順序付けられた３つのノードで特定することが可能である。そこで、規制情報記憶部４１０は、かかる３点規制（以下かかる規制を３点規制と呼ぶ）を、名前「Ｍ」と、種類「３点規制」と、規制内容「Ａ⇒Ｃ⇒Ｄ」との一組のデータとして記憶する。
【００４２】
なお、３点規制は、３つのノードで特定する以外に、２つのリンクで特定することも可能である。この場合、図中の例では、規制内容について、「Ａ⇒Ｃ⇒Ｄ」の代わりに「ｑ⇒ｓ」を記憶することが考えられる。後述する実施例のように、経路探索部３００が、リンクに応じてラベルデータを生成・記憶して探索を行う場合、かかるデータ構造を採用することは有用である。
【００４３】
なお、規制については種々のものがあるため、規制情報記憶部４１０における「規制内容」の欄のデータ構成はそれらに応じて種々のものを利用することができるものとした。例えば、後述する実施例で詳述するように、３点規制と同様な４点規制を利用可能としてもよい。
【００４４】
経路探索部３００は、ラベル情報記憶部としての機能を奏するラベル保持部３１０と、選択部及び探索遂行部としての機能を奏する探索処理部３１１とを有する。
【００４５】
ラベルデータ保持部３１０は、目的地への経路探索の過程における候補の経路について、その管理を行うために利用するラベルデータを保持する。ラベルデータに含むラベル情報は、候補経路の総コスト、直前経路情報として１つ直前のノード名を含む。直前経路情報を規制情報と対比することで、その候補経路のさらなる延伸が規制に阻まれるものか否かを判断することができる。またラベルデータには、候補ラベルの場合と確定ラベルの場合とがある。ラベルデータ中には、候補ラベルと確定ラベルとの別を記録する。
【００４６】
ここにラベル保持部３１０は、一つのノードに対応して、直前経路情報の異なる複数のラベルデータを記憶する。したがって、そのノードに接続するノードの個数だけのラベルデータが記憶され得る。ラベル保持部３１０は、ノードに対応付けてラベルデータを管理するとともに、ノードごとに直前経路情報に応じた管理をも行う。
【００４７】
なお、図３において直前経路情報は、説明の便宜のため、ノードを利用して示したが、後述の説明のように、それらのノードに付されたラベルの名前を含めれば足りる。
【００４８】
探索処理部３１１は、ラベル保持部３１０に対するラベルの生成・更新・削除等の操作を行ったり、また、ラベル情報を読み出してラベルの検索を行ったりする。また、探索処理部３１１は、地図記憶部４００に記憶されたグラフデータや規制データを参照しつつ、ラベル処理を行う。
【００４９】
図４は、経路探索処理のフローチャートである。また、図５は、ラベルデータの処理を示す説明図である。さらに、図６は、図５に示す処理の続きを示す説明図である。ここで図５、６で説明に利用するグラフは、先に図１で示したグラフと同様のグラフであり、図１の場合と同様の右折禁止規制を有する。
【００５０】
図４のステップＳａ０１〜Ｓａ０３は、データ入力を行う処理である。すなわち、ステップＳａ０１ではグラフデータを、ステップＳａ０２では規制データを、ステップＳａ０３では出発地と目的地とのノードに関するデータをそれぞれ入力する。
【００５１】
図４のステップＳａ１１では、探索処理部３１１が、ラベル保持部３１０の初期設定を行う。ここでは、出発ノードから出発してそのまま終端するというコスト０の確定経路について、候補ラベルであるラベルデータとして生成する。このラベルデータは出発地ノードに対応付けて記憶する。
【００５２】
図５のＳＴＥＰ  Ｓｂ００におけるラベルＬａは、かかる初期設定に基づいて生成するラベルである。このラベルでは、経路上の最先端直前のノードは観念し得ないため、特別のデータ「＄」を直前経路情報として含む。
【００５３】
図４のステップＳａ３１では、候補経路の中でコストが最小の候補経路を検索する。かかる候補経路は確定経路であるため、そのラベルを注目ラベルとして選択するとともに、候補ラベルから確定ラベルへと変更する。ここに、確定経路は、出発地ノードから特定のノードへの経路であって、その特定ノードの直前のノードが同一の経路の中でコストが最良の経路である。なお、ステップＳａ１１の初期設定で候補ラベル生成を行うコスト０の候補経路は自明な確定経路である。
【００５４】
図５のＳＴＥＰ  Ｓｂ００において、ラベルＬａは唯一のラベルである。そこで、ステップＳａ３１の処理では必ずこれを選択して注目ラベルとし、確定ラベルへの変更を行う（図５のＳＴＥＰ  Ｓｂ０１を参照）。
【００５５】
図４のステップＳａ３２では、注目経路が目的地ノードに到達する経路であるか否かの判定を行う。目的地ノードに到達しているならば、その経路を検索結果の経路として経路探索を終了する。他方、目的地ノードに到達する経路でなければ、そのラベルを注目ラベルとして、ステップＳａ２１〜Ｓａ２４の処理を実行する。
【００５６】
図５のＳＴＥＰ  Ｓｂ００でラベルＬａの付されたノードＡは目的地ノードではない。そこで、ラベルＬａを注目ラベルとしたステップＳａ２１〜Ｓａ２４の処理を行う。
【００５７】
図４のステップＳａ２１〜２４の処理では、候補経路の延伸を試行し、規制情報及び直前経路情報、及びコスト比較に基づいて、その可否の検討を行う。ステップＳａ２１で候補経路の最先端ノードとリンクで接続するノードを調べる。ステップＳａ２２では、かかるリンクの先への延伸が規制に触れるものでないか否かを調べる。
【００５８】
ステップＳａ２２及びＳａ２３における処理では、既存の候補ラベルを参照しつつ、経路延伸の可否を検討する。ステップＳａ２３では、規制に反しない延伸について、直前経路情報が同一の候補経路の存否を調べる。すなわち、最先端の２ノードが一致することとなる既存の候補経路を検索する。もしも存在するならば、ステップＳａ２４で、延伸の可否を、既存ラベルとのコスト比較に基づいて検討する。コストの改善が得られなければ候補経路の延伸は行わない。これについては、通常のダイクストラ法の場合と同様にして、ラベルに含むコスト情報を利用する。コスト比較によって却下された経路延伸は、ステップＳａ２５におけるラベル生成処理でその対象から除外される。
【００５９】
図４のステップＳａ２５の処理では、以上の検討に基づいて候補経路の延伸を実行する。すなわち延伸した候補経路に応じて候補ラベルを作成する。
【００６０】
図５のＳＴＥＰ  Ｓｂ０１では、ラベルＬａを注目ラベルとして、ラベルＬｂとラベルＬｃとを生成する。ラベルは作成された順に、Lａ，Ｌｂ，Ｌｃ…をラベルの先頭に付与している。図４のフローチャートにおけるステップＳａ２１における処理によって、ノードＡと接続するノードＢ、Ｃを検知する。さらにステップＳａ２２の処理では、ノードＢ、Ｃへの経路延伸が規制違反とならない旨を確認する。さらに、ステップＳａ２３〜Ｓａ２４では、既存のラベルとの照合を行って経路延伸の可否を検討する。なお、図５のＳＴＥＰ  Ｓｂ００で既存の候補ラベルはラベルａのみであったために、ここでは検討の対象となるラベルは存在しない。
【００６１】
以上の処理により、図５のＳＴＥＰ  Ｓｂ０１で示すように、ラベルＬｂとラベルＬｃがそれぞれノードＣ、Ｂに付される。ラベルＬｂとラベルＬｃとは、共に直前経路情報としての「ラベルＬａ」の名前と、ラベルが付されるノード名と、それぞれのラベルが特定する候補経路の総コストの情報を含んでいる。図４に示すフローチャート上の処理はステップＳａ３１に戻る。
【００６２】
次に、図４のフローチャートにおけるステップＳａ３１に示す処理が、再び実行される。ここでは、候補ラベルとしてラベルＬｂ及びラベルＬｃが存在し、最小コストのラベルとしてラベルＬｂを見い出し、確定ラベルへの変更を行う。これにより、ラベルＬｂを注目ラベルとして、図４のフローチャートにおけるステップＳａ２１〜Ｓａ２４の処理を行う。
【００６３】
図６のＳＴＥＰ  Ｓｂ０２は、ラベルＬｂを注目ラベルとして、図４のフローチャートにおけるステップＳａ２１〜Ｓａ２４の処理を行った結果を示したものである。
【００６４】
まず、図４のフローチャートにおけるステップＳａ２１の処理により、ノードＣと接続するノードＢ、Ｄを検知する。ここでノードＣは、ノードＡにも接続されているが、規制情報として「Ｃ→Ａ」はＵターン禁止登録（つまりＣ→Ａ→Ｃの通行禁止登録）がされており、ここでは対象外とする。なお、このＣ→Ａ→Ｃが通行禁止である旨は、規制情報記憶部４１０に記憶されている。
【００６５】
次にステップＳａ２２の処理により、規制情報を参照することで、ノードＤへの候補経路の延伸は規制に反することを検知する。このとき、注目ラベルであるラベルＬｂに含む直前経路情報を参照する。この例では、候補経路におけるノードＣの直前のノードがノードＡであることより、ノードＤへの経路延伸は、「Ａ→Ｃ→Ｄ」経路の右折禁止規制に反することを検知する。これに基づき、ステップＳａ２５におけるラベル作成処理では、ノードＤに対するものは排除される。他方、ノードＢへの経路延伸は、規制に阻まれないために、ステップＳａ２３〜Ｓａ２４における処理の対象として残す。
【００６６】
既述のように、ステップＳａ２３〜Ｓａ２４では、既存のラベルとの照合を行い、経路延伸の可否を検討する。図５の例では、ノードＣからノードＢへの経路延伸の可否を、既存ラベルたるラベルＬｃとの照合により行う。
【００６７】
ステップＳａ２３における処理では、対応ノードを同じくするラベルであって、直前経路情報も同一であるラベルが存在するか否かを検討する。本実施例では、対応ノードが同一であるラベルＬｃを見い出すものの、直前経路情報が異なるために、ラベルＬｃの存在は経路延伸を否定する基礎とはしない。本実施例では、直前経路情報の共通するラベルを見い出さないために、ステップＳａ２４におけるコスト照合処理を行う対象となるラベルは存在しない。したがって、ステップＳａ２３における直前経路情報の照合に続いて、ステップＳａ２５におけるラベル生成処理を即座に実行することとなる。なお、ステップＳａ２３において、対応ノードを同じくするラベルであって、直前経路情報も同一であるラベルが存在する場合には、コスト照合を行い、コストの高いラベルを削除する。
【００６８】
以上、ステップＳａ２１〜Ｓａ２４の検討処理に基づくステップＳａ２５の処理によって、図６のＳＴＥＰ  Ｓｂ０２に示すラベルＬｅが新たに作成される。ラベルＬｅには、直前経路情報としてラベルＬｂが、対応ノードを示す情報としてＮＢが、コスト値として３（＝１＋２）がそれぞれ付される。
【００６９】
ここまでの処理により、図６のＳＴＥＰ  Ｓｂ０２では、ノードＢに、ラベルＬｃとラベルＬｅが付された。ラベルＬｃは候補経路「Ａ→Ｂ」に応じたものであり、ラベルＬｅは候補経路「Ａ→Ｃ→Ｂ」に応じたものである。両者は、直前経路情報が異なるために、同一のノードに対応する複数のラベルとして、ラベル保持部３１０上のラベルデータとして構成する。
【００７０】
図６のＳＴＥＰ  Ｓｂ１０は、ラベルＬｃを注目ラベルとして選択し、ノードＣにラベルＬｆを付す処理の結果を示したものである。ノードＢに２つのラベルが付されることにより、後続のステップＳａ３１における処理で「ラベルｃ」を注目ラベルとし、ラベルＬｆを生成することができる。このとき、ノードＣにおける既存のラベルＬｂは直前経路情報が同一でないために、図４のフローチャートにおけるステップＳａ２３の処理でラベルＬｆの生成を排除する基礎となることはない。
【００７１】
図６のＳＴＥＰ  Ｓｂ２０は、ラベルＬｆを注目ラベルとして選択して、ノードＤにラベルＬｇを付した処理の結果を示したものである。ステップＳａ３１の処理においてラベルＬｆを注目ラベルに選ぶことで、ステップＳａ２５の処理でラベルＬｇを生成する。さらに後続する段階のステップＳａ３１、ステップＳａ３２の処理では、ラベルＬｇを注目ラベルに選ぶことで目的地への到達する確定経路を発見する。これによって、出発地ノードＡから目的地ノードＤに至る、「Ａ→Ｂ→Ｃ→Ｄ」なるコスト７なる経路を発見して、処理を終了する。
【００７２】
なお、本実施例では、直前経路情報として候補経路の直前のノードに付されたラベルを指定する情報を利用したが、かかる場合に限定されるわけではない。最先端ノードに至る直前の所定区間の経路を特定する直前経路情報であれば、種々のものを採ることができる。例えば、直前に通過したノード、リンクを列挙するものとしても良い。また、規制情報が、Ｎ点（Ｎは３以上の自然数）のノードによって定義される規制である場合、直前経路情報は、Ｎ−２点のノードに相当する区間の経路情報とすることができる。
【００７３】
本実施例中では３点のノードによって定義される規制を有するグラフについて、直前経路情報は１（＝３−２）点のノードに相当する区間の経路情報である場合について示したが、かかる場合に限定されるわけではない。例えば、４点のノードによって定義される４点規制を有するグラフについて、直前経路情報は２（＝４−２）点のノードに相当する区間の経路情報である場合も考えられる。このとき、直前経路情報は、２つのノードの順列やリンクとその向きで構成することができる。
【００７４】
また、本実施例では、リンクにのみコストを付しているが、ノード自体にもコストを付して良い。このノード自体にコストを付す場合、信号機の有無、青色信号点灯の時間（右折許容時間含む）を判断根拠とすることが考えられる。
【００７５】
本実施例に従って構成した経路探索装置を利用することにより、通過方法の規制を有する通路における柔軟な経路探索技術を実現することができる。通過方法の規制である３点規制を有するグラフにおいても、コスト優位の原則を基礎とした経路探索を実現することができる。
【００７６】
Ｂ．４点規制：
第１実施例では３点のノードによって定義される規制を有するグラフについて、直前経路情報は１（＝３−２）点のノード列に相当する場合について示した。本実施例では、４点のノードによって定義される４点規制を有するグラフについて、直前経路情報は２（＝４−２）点のノード列に相当する場合について説明する。
【００７７】
図７に示すように、４点規制は、例えば「ノードＡ→ノードＢ→ノードＣ」と経路をとった後の、ノードＣと接続するノードＥへの経路延伸を禁止し、ノードＢへのＵターンも禁止する。かかる規制の場合、４点のノードの順列で規制情報を構成することができる。
【００７８】
経路探索装置の概略構成及びその機能ブロックは、本実施例の場合も、第１実施例の場合と同様である（図２、３を参照）。ただし、規制情報記憶部における規制情報には４点規制を含む。また、２点のノード列に相当する区間の経路情報である直前経路情報を含むラベルデータを、経路探索部中のラベル保持部に生成して利用する。これらの点で第１実施例の場合と相違する。
【００７９】
ここで、直前経路情報は、ノードを列挙する形式で示したが、直前のノードに対応付けられたラベルを指定するものとしてもよい。
【００８０】
４点規制の場合、ノードを列挙する場合には、図中に示す通り、少なくとも２点分のノードを特定する情報が必要となる。これに対し、直前ラベルを指定する場合には、順次ラベルを遡っていくことにより、帰納的に２つのノード分の経路を容易に特定することができるため、４点規制の場合でも単一の直前ラベルを指定すれば足りる。従って、直前ラベルを指定することにより、ラベル情報のデータ量を抑制することができる利点がある。
【００８１】
図７は、４点規制に対応するラベルデータの処理を例示する説明図である。図７では、規制情報記憶部４１０ａ及びラベル保持部３１０ａで、それぞれの機能ブロックが利用するデータの概略構成を併せて示している。
【００８２】
図中の５点のノードＡ、Ｂ、Ｃ、Ｄ、Ｅを含むグラフは４点規制を有する。これは、経路「Ａ→Ｂ→Ｃ」に続く、ノードＥへの経路延伸を規制する４点規制である。
【００８３】
図７に示すラベル保持部３１０ａは、ノードＣに対応して２つのラベルＬｂａ、Ｌｂｄを保持する状態について例示している。ここに、各ラベルの直前経路情報は全て異なるものである。これらのラベルにおける直前経路情報は、それぞれ、ノードＢ，Ａ、ノードＢ，Ｄのノード列をそれぞれ特定する。これらは、各ラベルに対応する候補経路における、ノードＣ到達直前の部分経路を示すものである。
【００８４】
第２実施例におけるグラフ探索処理については、規制情報及び直前経路情報に関係する処理を除けば、第１実施例の場合（図４〜図６を参照）と同様である。そのため、本実施例における探索処理は、図４に示すフローチャートに示した処理と同様である。そこで以下では、図４のフローチャートを参照しながら、先の実施例の場合と相違する処理に注目しつつ、本実施例における処理を説明する。
【００８５】
ステップＳａ０１〜Ｓａ１１における、初期データ入力と、ラベル保持部３１０ａの初期設定については第１実施例の場合と同様である。もっとも、規制データには４点規制の規制データを含む。
【００８６】
この後、ステップＳａ３１におけるラベル選択処理と、ステップＳａ３２における目的地ノードへの到達をチェックする処理と、Ｓａ２１〜Ｓａ２５における経路延伸処理とからなる処理を繰り返し行う。ステップＳａ３２で、目的地ノードに達する確定経路を認定した場合、その確定経路を検索結果として処理を終了する。
【００８７】
ステップＳａ２１において、候補経路の最先端ノードと接続する別のノードを探索する処理は第１実施例の場合と同様である。ステップＳａ２２における規制情報照合処理については、本実施例の処理では２点のノードにかかる照合を行う点で、先の実施例の場合と相違する。また、ステップＳａ２３における既存ラベルとの直前経路情報照合処理についても、本実施例の処理では２点のノードに関する照合を行う点で、先の実施例の場合と相違する。なお、直前経路情報の同一は、２点がともに同一であるか否かで判断する。これは、規制情報との照合処理の場合と同様である。なお、ステップＳａ２４において、対応するノード及び直前経路情報がともに同一の既存ラベルとコスト比較を行う点については、第１実施例の場合と同様である。
【００８８】
結局、ステップＳａ２５におけるラベル作成処理は、直前経路情報が異なるラベルのみの作成を行う点では、第１実施例の場合と同様である。ただし、ステップＳａ２２における処理に基づいて、４点規制に適合する経路延伸に応じたもののみのラベル作成である。また、ステップＳａ２３の処理に基づいて、最先端直前の２点のノードが異なる場合のラベル作成である点でも、１つのノードが異なる場合についてのラベル作成処理であった第１実施例における処理と相違する。さらに、ステップＳａ２５におけるラベルデータ作成処理は、２点のノードの情報を直前経路情報として含むラベルデータの作成処理であり、第１実施例における１点のノードの情報を含むものの場合と相違する。
【００８９】
ここで、図７のラベル保持部３１０ａに例示する、ノードＣに対応する２つのラベルＬｂａ、Ｌｂｄについて考える。これらのラベルに基づくステップＳａ２１〜Ｓａ２５の経路延伸処理は、ステップＳａ３１における処理でこれらのラベルを注目ラベルに選択することで行う。
【００９０】
ステップＳａ２１において、ノードＣに接続するノードＥを検知することは、いずれのラベルにおいても同様である。ステップＳａ２２では、規制情報記憶部４１０ａを参照することで、ラベルＬｂａが特定する候補経路については、ノードＥへの経路延伸ができないことを認定する。これにより、残りのステップＳａ２４からＳａ２５におけるラベル作成処理を抑制する。ラベルＬｂｄの場合には規制に適合する経路延伸であるとの認識を行い、ステップＳａ２３〜Ｓａ２４における既存ラベルとの照合処理を行う。この後、ステップＳａ２５でラベル生成を行ってノードＥへの経路延伸を実行する。
【００９１】
本実施例に従って構成した経路探索装置を利用することにより、通過方法の規制を有する通路における柔軟な経路探索技術を実現することができる。通過方法の規制である４点規制を有するグラフにおいても、コスト優位の原則を基礎とした経路探索を実現することができる。
【００９２】
Ｃ．リンクに対応したラベル：
先に説明した実施例で、ラベルデータはノードに対応して構成した。ところで、リンクは２つのノードの順列であり、リンクに対応してラベルデータを生成して利用する経路探索も可能である。以下では、リンクに対応したラベルデータを利用する場合について例示する。
【００９３】
図８は、リンクに対応するラベルデータの処理を例示する説明図である。図８に示すグラフは、説明の便宜上で形態を変更したものの、第２実施例の説明において利用した図７のグラフと同じものである。ここで図８のグラフは、ノード及びリンクが第２実施例におけるものと同じであるのみならず、４点規制「Ａ⇒Ｂ⇒Ｃ⇒Ｅ」についても同じであるものとする。なお、ここでは図示の便宜上、リンクＡＤ、ＡＢ、ＢＤ、ＢＣ、ＥＣにそれぞれ「ｐ」、「ｑ」、「ｒ」、「ｓ」、「ｔ」の名前を新たに付して説明を行う。
【００９４】
経路探索装置の概略構成及びその機能ブロックは、本実施例の場合は第２実施例の場合と同様に、第１実施例で示したものと同等である。ただし、本実施例での規制情報記憶部４１０ｂにおける規制情報はリンクを利用して規制を特定する規制情報を利用する。また、直前経路情報もリンクを利用して直前の経路を特定するものを利用する。
【００９５】
本実施例で規制情報記憶部４１０ｂは、リンクの順列「ｑ→ｓ→ｔ」なる規制データを利用することで４点規制（３リンク規制）を特定する。また、ラベル保持部３１０ｂにおけるラベルデータは、対応要素と直前経路情報とについて、リンク名を含んだラベルデータである。ラベルデータはリンクに対応して生成する。つまり、候補経路をリンクの列として把握するとともに、かかるリンク列の最先端リンクに対応したラベルを利用してその候補経路を管理する。直前経路情報についても、最先端直前のリンクを利用する。もっとも、これは、第２実施例において直前経路情報に含む２つのノードを、それらを接続する１つのリンクで特定するものである。
【００９６】
図８のラベル保持部３１０ｂでは、リンクに対応する２つのラベルＬｑ、Ｌｒについて例示している。
【００９７】
これらのラベルはノードＣに至る２つの候補経路に対応した候補ラベルを示したものである。直前経路情報を参照することで、候補経路の最先端部分の経路は、ラベルＬｒで「Ｄ→Ｂ→Ｃ」と、ラベルＬｑで「Ａ→Ｂ→Ｃ」と、それぞれ特定できる。これにより、ラベルＬｑにおける候補経路については、リンクｑを介したノードＥへの延伸が不能であることが特定できる。候補経路の最先端ノードに先立つ２ノードに相当する区間の経路情報が、直前経路情報に含むリンクを参照することで特定可能となる。本実施例では、図８で模式的に示すラベルデータを利用することで、第２実施例と同様の経路探索処理を行う。
【００９８】
本実施例におけるグラフ探索処理については、第２実施例の場合と同等である。以下で、第１実施例における処理を示す図４のフローチャートを参照しながら、第２実施例の場合と相違する点に注目しつつ、本実施例における処理を説明する。
【００９９】
ステップＳａ２５におけるラベル作成は、リンクに対応したラベルの作成である。つまり、候補経路における最先端リンクに対応してラベル作成を行う。したがって、ステップＳａ２２における規制情報の照合処理ではリンク列の同一を照合する。これは、ステップＳａ２３における直前経路情報の照合処理も同様である。注目ラベルと既存ラベルとで、直前経路情報に含むリンク列の同一を調べる。
【０１００】
本実施例に従って構成した経路探索装置を利用することにより、通過方法の規制を有する通路における柔軟な経路探索技術を実現することができる。通過方法の規制である３リンク規制を有するグラフにおいても、コスト優位の原則を基礎とした経路探索を実現することができる。経路の性質等に応じた多様なデータ構造を利用しつつ柔軟な処理を行うことができる。リンクデータに基づいたノードデータの統合管理によって効率的な探索処理を実現することができる。
【０１０１】
なお、上記の説明で経路探索装置は、ＣＤ−ＲＯＭ等の地図データ記憶装置と探索結果表示装置とを一体的に備える形態であるものとしたが、そのような場合に限定されるわけではない。以下で、ローカル接続やインターネット、無線ＬＡＮ等のネットワークを利用する変形例について説明する。
【０１０２】
例えば、第一に、地図データについてはネットワークを介して取得を行う形態であってもよい。また、第二に、ユーザの操作する外部装置とネットワークを介して接続することで、表示制御データを送付して探索結果情報の提供を行ったり、ユーザ入力を取得したりするものとしてもよい。第三に、ネットワークを介して取得する地図データに基づいて探索処理を行い、かつ、探索結果についてもネットワークを介した送付を行う態様も考えられる。さらに、探索指示の取得元と探索結果の送付先とが異なる場合も考えられる。なお、以上説明した変形例において、ラベル操作等の探索処理そのものについては、第１〜第３実施例等の探索処理を柔軟に選択して利用することができる。例えば、第１の実施例でＡ→Ｃ→Ａを通行禁止としたが、禁止されていないときに利用してもよい。
【０１０３】
Ｄ．コスト以外の要素に基づく経路選択：
実施例では、コストの大小関係以外に経路を選択するために考慮すべき要素として交通規制が設けられている場合について例示した。本発明は、交通規制に関わらず種々の要素を考慮した経路探索に利用することができる。かかる要素としては、例えば、直進優先、国道優先など運転者の嗜好や安全性が挙げられる。
【０１０４】
図９は、変形例として直線優先を考慮した経路探索例を示す説明図である。図９に示すグラフで、ノード、リンク及びリンクに付されたコストは、第１実施例の説明において図３で示したものと同様である。図９に示すグラフでは、ノードＣにおいて、通過方向に対応したコストが設定されている点で、図３の場合と相違する。
【０１０５】
通過方向に対応したコストは、直線優先を表すコストである。例えば、ノードＢ→Ｃ→Ｄのように、ノードＣを直進する経路については、直進用のコスト値１が適用される。ノードＡ→Ｃ→Ｄのように、ノードＣを右折して通過する経路については、右折用のコスト値７が適用される。
【０１０６】
図９のラベル保持部３１０ｃは、経路探索の過程において、２種類の候補経路Ａ→ＣとＡ→Ｂ→Ｃとに対応するラベルＬｃａ，Ｌｃｂａが記憶されている状態を示した。ノードＣからの延伸方向が未定の状態では、直進コスト、右折コストは反映されないから、ラベルＬｃａのコスト値は１、ラベルＬｃｂａのコスト値は５である。ノードＤへの延伸においては、ラベルに含む直前経路情報から直進・右折コストにかかるコストを求め、候補経路間の対比を行う。これにより、直進優先の条件を基礎とした経路「Ａ→Ｂ→Ｃ→Ｄ」が得られる。
【０１０７】
図１０は、変形例として国道優先を考慮した経路探索例を示す説明図である。図９に示すグラフにおいて、リンクＡ→Ｂ，Ｂ→Ｃ，Ｃ→Ｄ，Ｄ→Ｅの４個のリンクは国道を示す。また、リンクＢ→Ｄ，Ｄ→Ｆは通常の道路を表している。
【０１０８】
ここで、一般に、通常の道路から国道に合流する場合には、危険を伴ったり、時間がかかったり、注意力を要したりする場合が多い。そこで、かかる状況を表すコストとして、ノードＤには、国道合流の経路Ｂ→Ｄ→Ｅについてのコスト値３が設定されている。
【０１０９】
経路探索の結果、２つの経路Ａ→Ｂ→Ｄ、Ａ→Ｂ→Ｃ→Ｄについてのコストが算出され、これらの経路に対応した２つのラベルがノードＤに付された状態を考える。ノードＤからの延伸方向が未決定の状態では、国道合流のコストは反映されない。従って、経路Ａ→Ｂ→Ｄのコストは４、Ａ→Ｂ→Ｃ→Ｄのコストは５となる。
【０１１０】
この状態で目的地Ｅへの延伸を行うと、経路Ａ→Ｂ→ＤにはＤ→Ｅのコスト値１に加えて、国道合流のコスト値３が反映されるため、総コストは８となる。経路Ａ→Ｂ→Ｃ→ＤにはＤ→Ｅのコスト値１のみが加えられるため、総コストは６となる。従って、国道を優先した経路Ａ→Ｂ→Ｃ→Ｄ→Ｅが探索結果として得られる。
【０１１１】
以上、図９と図１０とを利用して説明してきた経路探索装置によれば、一つのノード又はリンクに対応付けて生成する複数のラベルを用いることにより、種々の要素を考慮しつつ経路の延伸を行って経路探索を行うことができる。なお、図９及び図１０の変形例では、直進優先、国道優先などの要素を、コストに反映して考慮する方法を例示したが、これらの要素はコストに反映させずに評価してもよい。例えば、図９の例では、直進する経路が存在する限り、コストに関わらず直進経路を選択するものとし、右折経路は、直進による経路が全く不可能な場合にのみ選択するものとしてもよい。
【０１１２】
以上、本発明の種々の実施例について説明したが、本発明はこれらの実施例に限定されず、その趣旨を逸脱しない範囲で種々の構成を採ることができることはいうまでもない。例えば、以上の処理はソフトウェアで実現する他、ハードウェア的に実現するものとしてもよい。
【図面の簡単な説明】
【図１】通過方法がある通路を例示する説明図である。
【図２】経路探索装置の概略構成図である。
【図３】経路探索装置で用いるデータの概略構成図である
【図４】経路探索処理のフローチャートである。
【図５】ラベルデータの処理を示す説明図である。
【図６】図５に示す処理の続きを示す説明図である。
【図７】４点規制に対応するラベルデータの処理を例示する説明図である。
【図８】リンクに対応するラベルデータの処理を例示する説明図である。
【図９】直線優先を考慮した経路探索例を示す説明図である。
【図１０】国道優先を考慮した経路探索例を示す説明図である。
【符号の説明】
１００…経路探索装置
１０１…操作パネル
１０２…表示デバイス
１０３…リモコン
２００…制御ユニット
２０１…地図データ入力部
２０２…位置情報入力部
２１０…表示制御部
２２０…ユーザ入力部
３００…経路探索部
３１０…ラベル保持部
３１１…探索処理部
４００…地図記憶部
４１０…規制情報記憶部
４２０…ノード記憶部
４２１…リンク記憶部
４１０ａ…規制情報記憶部
３１０ａ…ラベル保持部
４１０ｂ…規制情報記憶部
３１０ｂ…ラベル保持部
４１０ｃ…規制情報記憶部
３１０ｃ…ラベル保持部
４１０ｄ…規制情報記憶部
【図１】
0003983049.tif 000002
【図２】
0003983049.tif 000003
【図３】
0003983049.tif 000004
【図４】
0003983049.tif 000005
【図５】
0003983049.tif 000006
【図６】
0003983049.tif 000007
【図７】
0003983049.tif 000008
【図８】
0003983049.tif 000009
【図９】
0003983049.tif 000010
【図１０】
0003983049.tif 000011