JP2003194560A - 経路探索装置 - Google Patents

Abstract

(57)【要約】 【課題】 通過方法の規制に応じた経路探索を行うため
の技術の実現を図る。 【解決手段】 コスト付きのリンクで接続されるノード
Ａ，Ｂ，Ｃ，Ｄ，Ｅにおいて、経路Ａ→Ｂ→Ｃに続くノ
ードＥへの進行を禁止する４点規制下で、出発地ノード
Ａから目的地ノードＥへの経路探索を行う。経路探索装
置は、ラベル保持部３１０ａに、候補経路の最先端ノー
ドに応じてラベルデータを作成しつつ探索を行う。ラベ
ルデータにはそのノードまでのコスト値の他、その最先
端ノード直前の２点のノードを記録し、直前の２ノード
の部分が異なる複数のラベルデータを一つのノードに対
応して記録することで、４点規制に応じつつ、コスト値
を基礎とする経路探索を行うことができる。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、通過方法の規制に
応じた経路探索を行うための技術に関する。

【０００２】

【従来の技術】近年、経路探索装置の利用分野は非常に
広範囲なものとなっている。例えば、いわゆるカーナビ
ゲーションシステムの多くは経路探索機能を備えてい
る。車の運転手は現在位置や目的地を設定することによ
り、所望の経路を探索することができる。

【０００３】経路探索は、ダイクストラ法によって行わ
れることが多い。ダイクストラ法とは、通行路をノー
ド、リンクの集合で表すとともに、各リンク等に通行距
離に応じたコストを割り当て、出発地から目的地までの
総コストが最小となるような経路を探索する手法をい
う。

【０００４】

【発明が解決しようとする課題】しかし、ダイクストラ
法では、通過方法に規制がある場合については、適切な
経路探索を行うことができなかった。

【０００５】図１は、通過方法の規制がある通路を例示
する説明図である。図１でノードＡ，Ｂ，Ｃ，Ｄは、リ
ンクによって接続されている。ここで各リンクは正整数
コスト値を有している。例えば、ノードＢは、ノードＡ
及びＣとリンクで接続される。ノードＡと接続するリン
クはコストが３であり、ノードＣと接続するリンクのコ
ストは２である。またノードＢはノードＤと接続するリ
ンクを有さないが、ノードＣを中継点とした、リンクＢ
Ｃ及びＣＤから構成される経路が存在する。なお、経路
のコストはそこに含むリンクが有するコストの総和で与
えられて、前述の経路Ｂ→Ｃ→Ｄのコストは４である。

【０００６】ここでユーザは、出発地ノードＡから目的
地ノードＤまでの経路の探索を所望しているものとす
る。

【０００７】ダイクストラ法においては、出発ノード等
を一方の端点とした候補経路について、リンクを辿りな
がら探索を行う。このとき、ノードごとに出発地ノード
からそのノードまでの総コストをラベルデータとして記
録する。あるノードへの候補経路の延伸は、そのノード
のラベルデータに記憶されたコストを改善可能な場合に
のみ行う。すなわち、既にラベルデータが記憶されたノ
ードに延伸する新しい候補経路が現れた場合、その候補
経路の総コストとラベルデータに記憶されたコスト値と
の大小関係により経路の選択を行う。新たな経路の総コ
ストの方が小さい場合には、ラベルデータの書き換えを
行う。このような手順を繰り返すことで、目的地ノード
まで最小コストで到達する経路を探索することができ
る。

【０００８】ところが、かかる従来の経路探索技術で
は、ノードやリンクの通過方法に規制がある場合には対
処できない。図１では規制の例として、ノードＡからノ
ードＣへ進んだ場合における右折禁止規制があるものと
する。つまり、経路「Ａ→Ｃ→Ｄ」を禁止する規制であ
る。なお、図１で例示したような、ノード、リンク、コ
ストからなる抽象的構造を、以下グラフと呼ぶ。

【０００９】この例の場合、従来の経路探索装置は、出
発ノードＡから中途ノードＣに至るコスト１の経路を発
見すると、その他の候補経路は、コストが１より大きい
ことからノードＣに至る経路として選択される余地がな
かった。すなわち、「Ａ→Ｂ→Ｃ」や「Ａ→Ｃ→Ｂ→
Ｃ」と辿るコスト５の候補経路は、コスト１の候補経路
「Ａ→Ｃ」とのコスト比較によって排除されていた。そ
の一方、「Ａ→Ｃ→Ｄ」の経路は、規制に反するため選
択することはできない。この結果、規制に反しない経路
として、「Ａ→Ｂ→Ｃ→Ｄ」、「Ａ→Ｃ→Ｂ→Ｃ→Ｄ」
という経路が存在するにもかかわらず、所望する経路探
索結果を得ることができなかった。

【００１０】上記課題を解決する方法の一つとして、例
えば、特開平７−２９４２６７号記載の技術が提案され
てはいる。この技術は、単にノードを接続しただけでな
く方向を有する有向リンクとして各リンクを定義してお
り、経路探索時には各リンクにラベルが付される。ま
た、ラベルには、そのリンクに至る直前のリンクを指定
する情報が含まれる。このように、直前のリンクを指定
する情報を含めつつ、各リンクにラベルを付すことによ
り、交通規制がある場合でも経路探索を実現することが
できるとされている。しかしながら、この技術では、４
点以上のノードで規制される交通規制については、やは
り適切な探索を行うことができなかった。

【００１１】かかる課題は図１を利用して説明した場合
に限らず、通過方法の規制がある通路の経路探索を実現
する場合において共通する課題であった。

【００１２】本発明は、これらの課題を解決するために
なされたものであり、通過方法の規制がある通路の探索
を実現するための技術の実現を目的とする。

【００１３】

【課題を解決するための手段およびその作用・効果】上
記課題の少なくとも一部を解決するために、本発明で
は、次の構成を適用した。本発明の第一の経路探索装置
は、経路探索を行う経路探索装置であって、ノード、リ
ンクを要素として表された通路データを記憶する通路デ
ータ記憶部と、前記それぞれのノード及びリンクの少な
くとも一方に対応づけられたコストを記憶するコスト記
憶部と、出発地、目的地に対応するノードを選択する指
示を入力する指示入力部と、前記通路データ記憶部及び
前記コスト記憶部の記憶内容に基づいて出発地から目的
地までの経路を探索する経路探索部とを備え、前記経路
探索部は、複数の候補経路上のノードについて、前記出
発地から該ノードに至るまでに経過した経過ノード及び
経過リンクの少なくとも一方に対応付けられたコストの
積算値を表すラベル情報を生成し、該ノードに対応付け
て記憶するラベル情報記憶部と、前記コスト積算値の大
小関係に基づいて前記候補経路のいずれかを選択する選
択部と、前記ラベル情報記憶部と、選択部とを繰り返し
用いて前記目的地に至る経路を探索する探索遂行部とを
備え、前記ラベル情報記憶部は、前記ノードに２以上の
ラベル情報を対応付けて記憶可能であるとともに、２以
上のラベル情報を記憶する場合には、前記ノードに至る
直前の所定区間の経路を特定する直前経路情報を、各ラ
ベル情報に含めて記憶することを要旨とする。

【００１４】このように本発明では、候補経路の端点、
すなわち出発地から最遠方のノードまたはリンクに、２
以上のラベル情報を記憶させることを許容する。つま
り、端点には、コストが最小とはならない候補経路につ
いても、ラベル情報を記憶する。したがって、コスト以
外の要素によって経路の選択を行う余地を持たせること
ができ、柔軟な経路探索を実現することができる。コス
ト以外の要素としては、例えば、通行規制、直線道路を
優先するなどといった運転者の嗜好、国道優先等の要素
が挙げられる。

【００１５】なお、直前経路情報は直前の所定区間の経
路を特定するものであるが、ノード、リンクによる順序
列や集合で特定してもよいし、直前のノードまたはリン
クに対応付けられたラベルを指定することにより、帰納
的に直前経路を特定してもよい。

【００１６】また、本発明の第２の経路探索装置は、経
路探索を行う経路探索装置であって、ノード、リンクを
要素として表された通路データを記憶する通路データ記
憶部と、前記それぞれのノード及びリンクの少なくとも
一方に対応づけられたコストを記憶するコスト記憶部
と、出発地、目的地に対応するノードを選択する指示を
入力する指示入力部と、前記通路データ記憶部及び前記
コスト記憶部の記憶内容に基づいて出発地から目的地ま
での経路を探索する経路探索部とを備え、前記経路探索
部は、複数の候補経路上のノードについて、前記出発地
から該ノードに至るまでに経過した経過ノード及び経過
リンクの少なくとも一方に対応付けられたコストの積算
値を表すラベル情報を生成し、該ノードに対応付けて記
憶するラベル情報記憶部と、前記コスト積算値の大小関
係に基づいて前記候補経路のいずれかを選択する選択部
と、前記ラベル情報記憶部と、選択部とを繰り返し用い
て前記目的地に至る経路を探索する探索遂行部とを備
え、前記ラベル情報は、該ノードに至る直前のノードに
対応したラベル情報を特定する直前経路情報情報を含む
ことを要旨とする。

【００１７】ラベル情報には、直前経路に対応するラベ
ル情報を記憶する。４点以上のノードで規制される交通
規制である多点規制の場合、直前の経路を特定するため
のノードまたはリンクが多数必要となって、データ量が
多くなる。これに対し、ラベル情報の指定によって帰納
的に直前経路を特定可能とする場合には、多点規制であ
ってもデータ量の増大を抑制することができる。

【００１８】また、柔軟なラベル処理を実現することが
できる。一つの直前経路情報の変更により、帰納的な変
更を行うことができる。

【００１９】ここで、１つのノードに複数のラベル情報
を付与することを許容しない経路探索を行う場合でも、
直前経路に対応する別のラベル情報を特定するラベル情
報を利用する方式は適用可能である。本発明の第二の経
路探索装置においても、直前経路に対応する別のラベル
情報を特定するラベル情報を利用する方式は適用可能で
ある。

【００２０】本発明の経路探索装置において、少なくと
も一部のノードについて、通過方法についての規制情報
を記憶する規制情報記憶部を備え、前記選択部は、該規
制情報を考慮して前記選択を行うものとしてもよい。

【００２１】このようにすることで、通過方法の規制が
ある場合でも、柔軟な経路探索を実現することができ
る。

【００２２】本発明の経路探索装置において、前記規制
情報は、Ｎ点（Ｎは３以上の自然数）のノードによって
定義される規制であり、前記直前経路情報は、Ｎ−２点
のノードに相当する区間の経路情報であるものとしても
よい。

【００２３】端点へのラベル情報を無制限に記憶させる
場合には、実質的に同一のラベル情報が重複して記憶さ
れる可能性がある。上述の通り、Ｎ点で規制情報が定義
されている場合には、Ｎ−２点のノードに相当する区間
の経路が異なるラベル情報を区別して記憶するものとす
れば、実質的に同一のラベル情報の重複を避けることが
できる。

【００２４】本発明の経路探索装置において、前記ラベ
ル情報記憶部は、前記直前経路の情報の少なくとも一部
が重複するラベル情報の生成を抑制するものとしてもよ
い。

【００２５】このようにすることで、直接の有用性を持
たない多数のラベル情報を大量に作成することによる弊
害を抑制でき、例えば、ラベル情報記憶部の容量を低減
することができる。

【００２６】本発明は、経路探索装置としての態様の
他、コンピュータに経路探索を行わせるためのコンピュ
ータプログラムや、コンピュータを用いて経路探索を行
う方法など種々の態様で構成することが可能である。ま
た、コンピュータに経路探索を行わせるためのコンピュ
ータプログラムと同視し得る信号として構成してもよ
い。さらに、これらのコンピュータプログラムを記録し
た記録媒体として構成してもよい。

【００２７】ここで記憶媒体としては、フレキシブルデ
ィスクやＣＤ−ＲＯＭ、光磁気ディスク、ＩＣカード、
ＲＯＭカートリッジ、パンチカード、バーコードなどの
符号が印刷された印刷物、コンピュータの内部記憶装置
（ＲＡＭやＲＯＭなどのメモリ）および外部記憶装置な
どコンピュータが読取り可能な種々の媒体を利用でき
る。

【００２８】

【発明の実施の形態】以下、本発明の実施の形態につい
て、経路探索装置の実施例に基づき説明する。 Ａ．経路探索装置： Ｂ．４点規制： Ｃ．リンクに対応したラベルデータ： Ｄ．コスト以外の要素に基づく経路選択：

【００２９】Ａ．経路探索装置：図２は、経路探索装置
の概略構成図である。経路探索装置１００は、無線通信
又はＣＤ（Ｃｏｍｐａｃｔ Ｄｉｓｋ）等を利用して、
探索対象となるグラフや規制を特定する地図データを取
得する。また、ＧＰＳ（Ｇｌｏｂａｌ Ｐｏｓｉｔｉｏ
ｎｉｎｇ Ｓｙｓｔｅｍ）やその他のセンシング装置を
利用して地図データと自らの位置を対比することが可能
である。ユーザは、リモコン１０３又は操作パネル１０
１等を利用して経路探索装置１００に経路探索を行わせ
ることができる。経路探索装置１００は表示デバイス１
０２を備えており、経路探索結果をユーザに出力する。

【００３０】図２には経路探索装置１００の機能ブロッ
ク構成を併せて示した。経路探索装置１００は、ＣＰＵ
およびメモリ等を備えたマイクロコンピュータとして構
成された制御ユニット２００を備えており、図示する機
能ブロックは、それぞれ制御ユニット２００の機能とし
てソフトウェア的に構成されている。もっとも、各機能
ブロックは、ハードウェア的に構成しても構わない。な
お図２に示した制御ユニット２００は一体的に構成する
場合を示したが、互いに通信する複数の装置が全体とし
て制御ユニット２００を構成するものとしてもよい。例
えば、ローカル接続する２つの装置に物理的に分離する
場合や、その他ネットワークを利用して構成する場合が
考えられる。

【００３１】地図データ入力部２０１は、地図データを
入力する機能を備える。地図データには、図１で示した
ようなノード、リンク、コスト及びその他の情報に関す
るグラフデータを含む。また地図データは規制データを
含む。規制データは、グラフにおける通過方法の規制を
特定するデータである。なお、地図データにはその他に
も種々の情報を含んでもよい。例えばグラフと対応付け
た施設情報を含んでもよい。また、地図データ入力部２
０１は、ＣＤのような情報記憶媒体を利用して地図デー
タを入力してもよいし、インターネット、無線ネットワ
ークその他のネットワークを介して入力してもよい。

【００３２】地図記憶部４００は、地図データ入力部２
０１が入力するグラフデータや規制データを記憶する。
地図記憶部４００の一部は規制情報記憶部４１０として
構成されており、規制データを記憶する。

【００３３】位置情報入力部２０２は、現在の位置の情
報を入力する。位置情報は、ＧＰＳの機能によって生成
される。また、その他のセンシングシステムの機能によ
っても生成される。後者の機能については、例えば、車
両に搭載されたカーナビゲーションシステムの場合、車
両の車軸やハンドル等に備えられた回転センサを基礎と
した位置情報を、位置情報入力部２０２が入力する。

【００３４】ユーザ入力部２２０は、リモコン１０３を
介したユーザ入力を入力する。またユーザ入力は操作パ
ネル１０１に基づいても与えられ、ユーザ入力部２２０
はこれも入力する（図中には明示せず）。ユーザはリモ
コン１０３や操作パネル１０１を利用することで、経路
探索を実行させることができる。また、経路の探索にお
ける、出発地や目的地その他の探索条件を入力すること
ができる。例えば、探索経路の出発地について、位置情
報入力部２０２が入力する位置情報が示す現在位置を採
用するか否かを指定することが可能である。

【００３５】経路探索部３００は、ユーザ入力部２２０
から受ける探索の指示に基づいて経路探索を行う。この
とき、地図記憶部４００からグラフデータ及び規制デー
タを、位置情報入力部２０２から位置情報を受けて、こ
れらを利用する。経路探索部３００は、経路探索にあた
って、候補経路のコスト情報や直前経路情報を含むラベ
ルデータを生成・記憶して利用する。経路探索部３００
は、その一部をラベル保持部３１０と探索処理部３１１
として構成している。これらについては後述する。

【００３６】表示制御部２１０は表示制御機能を備えて
おり、経路探索部３００における探索結果を表示デバイ
ス１０２に出力することで、これをユーザに提供するこ
とができる。

【００３７】図３は、経路探索装置で用いるデータの概
略構成図である。ここには図１で利用したグラフを再掲
している。このグラフを利用して、地図記憶部４００が
行う記憶の詳細について以下で説明する。また、図３に
示したグラフでは、ノードＢにラベルＬ１とラベルＬ２
を付している。これは、経路探索部３００における探索
処理において利用するラベルデータの一例を示したもの
である。図３におけるラベルＬ１、Ｌ２を利用して、経
路探索部３００が探索処理にあたって生成・記憶するラ
ベルデータについて説明する。ここで、図３に示したグ
ラフでは、各リンクに対応するコストは括弧でくくって
示している。

【００３８】地図記憶部４００は、その一部をノード記
憶部４２０、リンク記憶部４２１、規制情報記憶部４１
０として構成している。

【００３９】ノード記憶部４２０は、図中に模式的に示
す通り、グラフのノードを記憶する。表の各欄にはグラ
フのノードの名前を記憶する。なお、ノードの属性、ノ
ードに接続されているリンク名、ノードに付されたラベ
ル名、関係する規制名等を併せて記憶するものとしても
よい。

【００４０】リンク記憶部４２１は、リンクごとに、名
前、端点である２つのノードの名前、及び、そのリンク
に付されたコストの値を組みにして記憶する。なお、端
点である２つのノードについて、本実施例では順序を考
慮していないが、いわゆる有向リンクを含むデータにつ
いては、その旨及びノードの順序に関する情報も記憶す
ればよい。

【００４１】規制情報記憶部４１０は、通路の規制に関
する規制データを記憶する。図３に示したグラフは、既
述のように、経路Ａ→Ｃ→Ｄにかかる右折禁止規制を有
する。かかる規制は、順序付けられた３つのノードで特
定することが可能である。そこで、規制情報記憶部４１
０は、かかる３点規制（以下かかる規制を３点規制と呼
ぶ）を、名前「Ｍ」と、種類「３点規制」と、規制内容
「Ａ⇒Ｃ⇒Ｄ」との一組のデータとして記憶する。

【００４２】なお、３点規制は、３つのノードで特定す
る以外に、２つのリンクで特定することも可能である。
この場合、図中の例では、規制内容について、「Ａ⇒Ｃ
⇒Ｄ」の代わりに「ｑ⇒ｓ」を記憶することが考えられ
る。後述する実施例のように、経路探索部３００が、リ
ンクに応じてラベルデータを生成・記憶して探索を行う
場合、かかるデータ構造を採用することは有用である。

【００４３】なお、規制については種々のものがあるた
め、規制情報記憶部４１０における「規制内容」の欄の
データ構成はそれらに応じて種々のものを利用すること
ができるものとした。例えば、後述する実施例で詳述す
るように、３点規制と同様な４点規制を利用可能として
もよい。

【００４４】経路探索部３００は、ラベル情報記憶部と
しての機能を奏するラベル保持部３１０と、選択部及び
探索遂行部としての機能を奏する探索処理部３１１とを
有する。

【００４５】ラベルデータ保持部３１０は、目的地への
経路探索の過程における候補の経路について、その管理
を行うために利用するラベルデータを保持する。ラベル
データに含むラベル情報は、候補経路の総コスト、直前
経路情報として１つ直前のノード名を含む。直前経路情
報を規制情報と対比することで、その候補経路のさらな
る延伸が規制に阻まれるものか否かを判断することがで
きる。またラベルデータには、候補ラベルの場合と確定
ラベルの場合とがある。ラベルデータ中には、候補ラベ
ルと確定ラベルとの別を記録する。

【００４６】ここにラベル保持部３１０は、一つのノー
ドに対応して、直前経路情報の異なる複数のラベルデー
タを記憶する。したがって、そのノードに接続するノー
ドの個数だけのラベルデータが記憶され得る。ラベル保
持部３１０は、ノードに対応付けてラベルデータを管理
するとともに、ノードごとに直前経路情報に応じた管理
をも行う。

【００４７】なお、図３において直前経路情報は、説明
の便宜のため、ノードを利用して示したが、後述の説明
のように、それらのノードに付されたラベルの名前を含
めれば足りる。

【００４８】探索処理部３１１は、ラベル保持部３１０
に対するラベルの生成・更新・削除等の操作を行った
り、また、ラベル情報を読み出してラベルの検索を行っ
たりする。また、探索処理部３１１は、地図記憶部４０
０に記憶されたグラフデータや規制データを参照しつ
つ、ラベル処理を行う。

【００４９】図４は、経路探索処理のフローチャートで
ある。また、図５は、ラベルデータの処理を示す説明図
である。さらに、図６は、図５に示す処理の続きを示す
説明図である。ここで図５、６で説明に利用するグラフ
は、先に図１で示したグラフと同様のグラフであり、図
１の場合と同様の右折禁止規制を有する。

【００５０】図４のステップＳａ０１〜Ｓａ０３は、デ
ータ入力を行う処理である。すなわち、ステップＳａ０
１ではグラフデータを、ステップＳａ０２では規制デー
タを、ステップＳａ０３では出発地と目的地とのノード
に関するデータをそれぞれ入力する。

【００５１】図４のステップＳａ１１では、探索処理部
３１１が、ラベル保持部３１０の初期設定を行う。ここ
では、出発ノードから出発してそのまま終端するという
コスト０の確定経路について、候補ラベルであるラベル
データとして生成する。このラベルデータは出発地ノー
ドに対応付けて記憶する。

【００５２】図５のＳＴＥＰ Ｓｂ００におけるラベル
Ｌａは、かかる初期設定に基づいて生成するラベルであ
る。このラベルでは、経路上の最先端直前のノードは観
念し得ないため、特別のデータ「＄」を直前経路情報と
して含む。

【００５３】図４のステップＳａ３１では、候補経路の
中でコストが最小の候補経路を検索する。かかる候補経
路は確定経路であるため、そのラベルを注目ラベルとし
て選択するとともに、候補ラベルから確定ラベルへと変
更する。ここに、確定経路は、出発地ノードから特定の
ノードへの経路であって、その特定ノードの直前のノー
ドが同一の経路の中でコストが最良の経路である。な
お、ステップＳａ１１の初期設定で候補ラベル生成を行
うコスト０の候補経路は自明な確定経路である。

【００５４】図５のＳＴＥＰ Ｓｂ００において、ラベ
ルＬａは唯一のラベルである。そこで、ステップＳａ３
１の処理では必ずこれを選択して注目ラベルとし、確定
ラベルへの変更を行う（図５のＳＴＥＰ Ｓｂ０１を参
照）。

【００５５】図４のステップＳａ３２では、注目経路が
目的地ノードに到達する経路であるか否かの判定を行
う。目的地ノードに到達しているならば、その経路を検
索結果の経路として経路探索を終了する。他方、目的地
ノードに到達する経路でなければ、そのラベルを注目ラ
ベルとして、ステップＳａ２１〜Ｓａ２４の処理を実行
する。

【００５６】図５のＳＴＥＰ Ｓｂ００でラベルＬａの
付されたノードＡは目的地ノードではない。そこで、ラ
ベルＬａを注目ラベルとしたステップＳａ２１〜Ｓａ２
４の処理を行う。

【００５７】図４のステップＳａ２１〜２４の処理で
は、候補経路の延伸を試行し、規制情報及び直前経路情
報、及びコスト比較に基づいて、その可否の検討を行
う。ステップＳａ２１で候補経路の最先端ノードとリン
クで接続するノードを調べる。ステップＳａ２２では、
かかるリンクの先への延伸が規制に触れるものでないか
否かを調べる。

【００５８】ステップＳａ２２及びＳａ２３における処
理では、既存の候補ラベルを参照しつつ、経路延伸の可
否を検討する。ステップＳａ２３では、規制に反しない
延伸について、直前経路情報が同一の候補経路の存否を
調べる。すなわち、最先端の２ノードが一致することと
なる既存の候補経路を検索する。もしも存在するなら
ば、ステップＳａ２４で、延伸の可否を、既存ラベルと
のコスト比較に基づいて検討する。コストの改善が得ら
れなければ候補経路の延伸は行わない。これについて
は、通常のダイクストラ法の場合と同様にして、ラベル
に含むコスト情報を利用する。コスト比較によって却下
された経路延伸は、ステップＳａ２５におけるラベル生
成処理でその対象から除外される。

【００５９】図４のステップＳａ２５の処理では、以上
の検討に基づいて候補経路の延伸を実行する。すなわち
延伸した候補経路に応じて候補ラベルを作成する。

【００６０】図５のＳＴＥＰ Ｓｂ０１では、ラベルＬ
ａを注目ラベルとして、ラベルＬｂとラベルＬｃとを生
成する。ラベルは作成された順に、Lａ，Ｌｂ，Ｌｃ…
をラベルの先頭に付与している。図４のフローチャート
におけるステップＳａ２１における処理によって、ノー
ドＡと接続するノードＢ、Ｃを検知する。さらにステッ
プＳａ２２の処理では、ノードＢ、Ｃへの経路延伸が規
制違反とならない旨を確認する。さらに、ステップＳａ
２３〜Ｓａ２４では、既存のラベルとの照合を行って経
路延伸の可否を検討する。なお、図５のＳＴＥＰ Ｓｂ
００で既存の候補ラベルはラベルａのみであったため
に、ここでは検討の対象となるラベルは存在しない。

【００６１】以上の処理により、図５のＳＴＥＰ Ｓｂ
０１で示すように、ラベルＬｂとラベルＬｃがそれぞれ
ノードＣ、Ｂに付される。ラベルＬｂとラベルＬｃと
は、共に直前経路情報としての「ラベルＬａ」の名前
と、ラベルが付されるノード名と、それぞれのラベルが
特定する候補経路の総コストの情報を含んでいる。図４
に示すフローチャート上の処理はステップＳａ３１に戻
る。

【００６２】次に、図４のフローチャートにおけるステ
ップＳａ３１に示す処理が、再び実行される。ここで
は、候補ラベルとしてラベルＬｂ及びラベルＬｃが存在
し、最小コストのラベルとしてラベルＬｂを見い出し、
確定ラベルへの変更を行う。これにより、ラベルＬｂを
注目ラベルとして、図４のフローチャートにおけるステ
ップＳａ２１〜Ｓａ２４の処理を行う。

【００６３】図６のＳＴＥＰ Ｓｂ０２は、ラベルＬｂ
を注目ラベルとして、図４のフローチャートにおけるス
テップＳａ２１〜Ｓａ２４の処理を行った結果を示した
ものである。

【００６４】まず、図４のフローチャートにおけるステ
ップＳａ２１の処理により、ノードＣと接続するノード
Ｂ、Ｄを検知する。ここでノードＣは、ノードＡにも接
続されているが、規制情報として「Ｃ→Ａ」はＵターン
禁止登録（つまりＣ→Ａ→Ｃの通行禁止登録）がされて
おり、ここでは対象外とする。なお、このＣ→Ａ→Ｃが
通行禁止である旨は、規制情報記憶部４１０に記憶され
ている。

【００６５】次にステップＳａ２２の処理により、規制
情報を参照することで、ノードＤへの候補経路の延伸は
規制に反することを検知する。このとき、注目ラベルで
あるラベルＬｂに含む直前経路情報を参照する。この例
では、候補経路におけるノードＣの直前のノードがノー
ドＡであることより、ノードＤへの経路延伸は、「Ａ→
Ｃ→Ｄ」経路の右折禁止規制に反することを検知する。
これに基づき、ステップＳａ２５におけるラベル作成処
理では、ノードＤに対するものは排除される。他方、ノ
ードＢへの経路延伸は、規制に阻まれないために、ステ
ップＳａ２３〜Ｓａ２４における処理の対象として残
す。

【００６６】既述のように、ステップＳａ２３〜Ｓａ２
４では、既存のラベルとの照合を行い、経路延伸の可否
を検討する。図５の例では、ノードＣからノードＢへの
経路延伸の可否を、既存ラベルたるラベルＬｃとの照合
により行う。

【００６７】ステップＳａ２３における処理では、対応
ノードを同じくするラベルであって、直前経路情報も同
一であるラベルが存在するか否かを検討する。本実施例
では、対応ノードが同一であるラベルＬｃを見い出すも
のの、直前経路情報が異なるために、ラベルＬｃの存在
は経路延伸を否定する基礎とはしない。本実施例では、
直前経路情報の共通するラベルを見い出さないために、
ステップＳａ２４におけるコスト照合処理を行う対象と
なるラベルは存在しない。したがって、ステップＳａ２
３における直前経路情報の照合に続いて、ステップＳａ
２５におけるラベル生成処理を即座に実行することとな
る。なお、ステップＳａ２３において、対応ノードを同
じくするラベルであって、直前経路情報も同一であるラ
ベルが存在する場合には、コスト照合を行い、コストの
高いラベルを削除する。

【００６８】以上、ステップＳａ２１〜Ｓａ２４の検討
処理に基づくステップＳａ２５の処理によって、図６の
ＳＴＥＰ Ｓｂ０２に示すラベルＬｅが新たに作成され
る。ラベルＬｅには、直前経路情報としてラベルＬｂ
が、対応ノードを示す情報としてＮＢが、コスト値とし
て３（＝１＋２）がそれぞれ付される。

【００６９】ここまでの処理により、図６のＳＴＥＰ
Ｓｂ０２では、ノードＢに、ラベルＬｃとラベルＬｅが
付された。ラベルＬｃは候補経路「Ａ→Ｂ」に応じたも
のであり、ラベルＬｅは候補経路「Ａ→Ｃ→Ｂ」に応じ
たものである。両者は、直前経路情報が異なるために、
同一のノードに対応する複数のラベルとして、ラベル保
持部３１０上のラベルデータとして構成する。

【００７０】図６のＳＴＥＰ Ｓｂ１０は、ラベルＬｃ
を注目ラベルとして選択し、ノードＣにラベルＬｆを付
す処理の結果を示したものである。ノードＢに２つのラ
ベルが付されることにより、後続のステップＳａ３１に
おける処理で「ラベルｃ」を注目ラベルとし、ラベルＬ
ｆを生成することができる。このとき、ノードＣにおけ
る既存のラベルＬｂは直前経路情報が同一でないため
に、図４のフローチャートにおけるステップＳａ２３の
処理でラベルＬｆの生成を排除する基礎となることはな
い。

【００７１】図６のＳＴＥＰ Ｓｂ２０は、ラベルＬｆ
を注目ラベルとして選択して、ノードＤにラベルＬｇを
付した処理の結果を示したものである。ステップＳａ３
１の処理においてラベルＬｆを注目ラベルに選ぶこと
で、ステップＳａ２５の処理でラベルＬｇを生成する。
さらに後続する段階のステップＳａ３１、ステップＳａ
３２の処理では、ラベルＬｇを注目ラベルに選ぶことで
目的地への到達する確定経路を発見する。これによっ
て、出発地ノードＡから目的地ノードＤに至る、「Ａ→
Ｂ→Ｃ→Ｄ」なるコスト７なる経路を発見して、処理を
終了する。

【００７２】なお、本実施例では、直前経路情報として
候補経路の直前のノードに付されたラベルを指定する情
報を利用したが、かかる場合に限定されるわけではな
い。最先端ノードに至る直前の所定区間の経路を特定す
る直前経路情報であれば、種々のものを採ることができ
る。例えば、直前に通過したノード、リンクを列挙する
ものとしても良い。また、規制情報が、Ｎ点（Ｎは３以
上の自然数）のノードによって定義される規制である場
合、直前経路情報は、Ｎ−２点のノードに相当する区間
の経路情報とすることができる。

【００７３】本実施例中では３点のノードによって定義
される規制を有するグラフについて、直前経路情報は１
（＝３−２）点のノードに相当する区間の経路情報であ
る場合について示したが、かかる場合に限定されるわけ
ではない。例えば、４点のノードによって定義される４
点規制を有するグラフについて、直前経路情報は２（＝
４−２）点のノードに相当する区間の経路情報である場
合も考えられる。このとき、直前経路情報は、２つのノ
ードの順列やリンクとその向きで構成することができ
る。

【００７４】また、本実施例では、リンクにのみコスト
を付しているが、ノード自体にもコストを付して良い。
このノード自体にコストを付す場合、信号機の有無、青
色信号点灯の時間（右折許容時間含む）を判断根拠とす
ることが考えられる。

【００７５】本実施例に従って構成した経路探索装置を
利用することにより、通過方法の規制を有する通路にお
ける柔軟な経路探索技術を実現することができる。通過
方法の規制である３点規制を有するグラフにおいても、
コスト優位の原則を基礎とした経路探索を実現すること
ができる。

【００７６】Ｂ．４点規制：第１実施例では３点のノー
ドによって定義される規制を有するグラフについて、直
前経路情報は１（＝３−２）点のノード列に相当する場
合について示した。本実施例では、４点のノードによっ
て定義される４点規制を有するグラフについて、直前経
路情報は２（＝４−２）点のノード列に相当する場合に
ついて説明する。

【００７７】図７に示すように、４点規制は、例えば
「ノードＡ→ノードＢ→ノードＣ」と経路をとった後
の、ノードＣと接続するノードＥへの経路延伸を禁止
し、ノードＢへのＵターンも禁止する。かかる規制の場
合、４点のノードの順列で規制情報を構成することがで
きる。

【００７８】経路探索装置の概略構成及びその機能ブロ
ックは、本実施例の場合も、第１実施例の場合と同様で
ある（図２、３を参照）。ただし、規制情報記憶部にお
ける規制情報には４点規制を含む。また、２点のノード
列に相当する区間の経路情報である直前経路情報を含む
ラベルデータを、経路探索部中のラベル保持部に生成し
て利用する。これらの点で第１実施例の場合と相違す
る。

【００７９】ここで、直前経路情報は、ノードを列挙す
る形式で示したが、直前のノードに対応付けられたラベ
ルを指定するものとしてもよい。

【００８０】４点規制の場合、ノードを列挙する場合に
は、図中に示す通り、少なくとも２点分のノードを特定
する情報が必要となる。これに対し、直前ラベルを指定
する場合には、順次ラベルを遡っていくことにより、帰
納的に２つのノード分の経路を容易に特定することがで
きるため、４点規制の場合でも単一の直前ラベルを指定
すれば足りる。従って、直前ラベルを指定することによ
り、ラベル情報のデータ量を抑制することができる利点
がある。

【００８１】図７は、４点規制に対応するラベルデータ
の処理を例示する説明図である。図７では、規制情報記
憶部４１０ａ及びラベル保持部３１０ａで、それぞれの
機能ブロックが利用するデータの概略構成を併せて示し
ている。

【００８２】図中の５点のノードＡ、Ｂ、Ｃ、Ｄ、Ｅを
含むグラフは４点規制を有する。これは、経路「Ａ→Ｂ
→Ｃ」に続く、ノードＥへの経路延伸を規制する４点規
制である。

【００８３】図７に示すラベル保持部３１０ａは、ノー
ドＣに対応して２つのラベルＬｂａ、Ｌｂｄを保持する
状態について例示している。ここに、各ラベルの直前経
路情報は全て異なるものである。これらのラベルにおけ
る直前経路情報は、それぞれ、ノードＢ，Ａ、ノード
Ｂ，Ｄのノード列をそれぞれ特定する。これらは、各ラ
ベルに対応する候補経路における、ノードＣ到達直前の
部分経路を示すものである。

【００８４】第２実施例におけるグラフ探索処理につい
ては、規制情報及び直前経路情報に関係する処理を除け
ば、第１実施例の場合（図４〜図６を参照）と同様であ
る。そのため、本実施例における探索処理は、図４に示
すフローチャートに示した処理と同様である。そこで以
下では、図４のフローチャートを参照しながら、先の実
施例の場合と相違する処理に注目しつつ、本実施例にお
ける処理を説明する。

【００８５】ステップＳａ０１〜Ｓａ１１における、初
期データ入力と、ラベル保持部３１０ａの初期設定につ
いては第１実施例の場合と同様である。もっとも、規制
データには４点規制の規制データを含む。

【００８６】この後、ステップＳａ３１におけるラベル
選択処理と、ステップＳａ３２における目的地ノードへ
の到達をチェックする処理と、Ｓａ２１〜Ｓａ２５にお
ける経路延伸処理とからなる処理を繰り返し行う。ステ
ップＳａ３２で、目的地ノードに達する確定経路を認定
した場合、その確定経路を検索結果として処理を終了す
る。

【００８７】ステップＳａ２１において、候補経路の最
先端ノードと接続する別のノードを探索する処理は第１
実施例の場合と同様である。ステップＳａ２２における
規制情報照合処理については、本実施例の処理では２点
のノードにかかる照合を行う点で、先の実施例の場合と
相違する。また、ステップＳａ２３における既存ラベル
との直前経路情報照合処理についても、本実施例の処理
では２点のノードに関する照合を行う点で、先の実施例
の場合と相違する。なお、直前経路情報の同一は、２点
がともに同一であるか否かで判断する。これは、規制情
報との照合処理の場合と同様である。なお、ステップＳ
ａ２４において、対応するノード及び直前経路情報がと
もに同一の既存ラベルとコスト比較を行う点について
は、第１実施例の場合と同様である。

【００８８】結局、ステップＳａ２５におけるラベル作
成処理は、直前経路情報が異なるラベルのみの作成を行
う点では、第１実施例の場合と同様である。ただし、ス
テップＳａ２２における処理に基づいて、４点規制に適
合する経路延伸に応じたもののみのラベル作成である。
また、ステップＳａ２３の処理に基づいて、最先端直前
の２点のノードが異なる場合のラベル作成である点で
も、１つのノードが異なる場合についてのラベル作成処
理であった第１実施例における処理と相違する。さら
に、ステップＳａ２５におけるラベルデータ作成処理
は、２点のノードの情報を直前経路情報として含むラベ
ルデータの作成処理であり、第１実施例における１点の
ノードの情報を含むものの場合と相違する。

【００８９】ここで、図７のラベル保持部３１０ａに例
示する、ノードＣに対応する２つのラベルＬｂａ、Ｌｂ
ｄについて考える。これらのラベルに基づくステップＳ
ａ２１〜Ｓａ２５の経路延伸処理は、ステップＳａ３１
における処理でこれらのラベルを注目ラベルに選択する
ことで行う。

【００９０】ステップＳａ２１において、ノードＣに接
続するノードＥを検知することは、いずれのラベルにお
いても同様である。ステップＳａ２２では、規制情報記
憶部４１０ａを参照することで、ラベルＬｂａが特定す
る候補経路については、ノードＥへの経路延伸ができな
いことを認定する。これにより、残りのステップＳａ２
４からＳａ２５におけるラベル作成処理を抑制する。ラ
ベルＬｂｄの場合には規制に適合する経路延伸であると
の認識を行い、ステップＳａ２３〜Ｓａ２４における既
存ラベルとの照合処理を行う。この後、ステップＳａ２
５でラベル生成を行ってノードＥへの経路延伸を実行す
る。

【００９１】本実施例に従って構成した経路探索装置を
利用することにより、通過方法の規制を有する通路にお
ける柔軟な経路探索技術を実現することができる。通過
方法の規制である４点規制を有するグラフにおいても、
コスト優位の原則を基礎とした経路探索を実現すること
ができる。

【００９２】Ｃ．リンクに対応したラベル：先に説明し
た実施例で、ラベルデータはノードに対応して構成し
た。ところで、リンクは２つのノードの順列であり、リ
ンクに対応してラベルデータを生成して利用する経路探
索も可能である。以下では、リンクに対応したラベルデ
ータを利用する場合について例示する。

【００９３】図８は、リンクに対応するラベルデータの
処理を例示する説明図である。図８に示すグラフは、説
明の便宜上で形態を変更したものの、第２実施例の説明
において利用した図７のグラフと同じものである。ここ
で図８のグラフは、ノード及びリンクが第２実施例にお
けるものと同じであるのみならず、４点規制「Ａ⇒Ｂ⇒
Ｃ⇒Ｅ」についても同じであるものとする。なお、ここ
では図示の便宜上、リンクＡＤ、ＡＢ、ＢＤ、ＢＣ、Ｅ
Ｃにそれぞれ「ｐ」、「ｑ」、「ｒ」、「ｓ」、「ｔ」
の名前を新たに付して説明を行う。

【００９４】経路探索装置の概略構成及びその機能ブロ
ックは、本実施例の場合は第２実施例の場合と同様に、
第１実施例で示したものと同等である。ただし、本実施
例での規制情報記憶部４１０ｂにおける規制情報はリン
クを利用して規制を特定する規制情報を利用する。ま
た、直前経路情報もリンクを利用して直前の経路を特定
するものを利用する。

【００９５】本実施例で規制情報記憶部４１０ｂは、リ
ンクの順列「ｑ→ｓ→ｔ」なる規制データを利用するこ
とで４点規制（３リンク規制）を特定する。また、ラベ
ル保持部３１０ｂにおけるラベルデータは、対応要素と
直前経路情報とについて、リンク名を含んだラベルデー
タである。ラベルデータはリンクに対応して生成する。
つまり、候補経路をリンクの列として把握するととも
に、かかるリンク列の最先端リンクに対応したラベルを
利用してその候補経路を管理する。直前経路情報につい
ても、最先端直前のリンクを利用する。もっとも、これ
は、第２実施例において直前経路情報に含む２つのノー
ドを、それらを接続する１つのリンクで特定するもので
ある。

【００９６】図８のラベル保持部３１０ｂでは、リンク
に対応する２つのラベルＬｑ、Ｌｒについて例示してい
る。

【００９７】これらのラベルはノードＣに至る２つの候
補経路に対応した候補ラベルを示したものである。直前
経路情報を参照することで、候補経路の最先端部分の経
路は、ラベルＬｒで「Ｄ→Ｂ→Ｃ」と、ラベルＬｑで
「Ａ→Ｂ→Ｃ」と、それぞれ特定できる。これにより、
ラベルＬｑにおける候補経路については、リンクｑを介
したノードＥへの延伸が不能であることが特定できる。
候補経路の最先端ノードに先立つ２ノードに相当する区
間の経路情報が、直前経路情報に含むリンクを参照する
ことで特定可能となる。本実施例では、図８で模式的に
示すラベルデータを利用することで、第２実施例と同様
の経路探索処理を行う。

【００９８】本実施例におけるグラフ探索処理について
は、第２実施例の場合と同等である。以下で、第１実施
例における処理を示す図４のフローチャートを参照しな
がら、第２実施例の場合と相違する点に注目しつつ、本
実施例における処理を説明する。

【００９９】ステップＳａ２５におけるラベル作成は、
リンクに対応したラベルの作成である。つまり、候補経
路における最先端リンクに対応してラベル作成を行う。
したがって、ステップＳａ２２における規制情報の照合
処理ではリンク列の同一を照合する。これは、ステップ
Ｓａ２３における直前経路情報の照合処理も同様であ
る。注目ラベルと既存ラベルとで、直前経路情報に含む
リンク列の同一を調べる。

【０１００】本実施例に従って構成した経路探索装置を
利用することにより、通過方法の規制を有する通路にお
ける柔軟な経路探索技術を実現することができる。通過
方法の規制である３リンク規制を有するグラフにおいて
も、コスト優位の原則を基礎とした経路探索を実現する
ことができる。経路の性質等に応じた多様なデータ構造
を利用しつつ柔軟な処理を行うことができる。リンクデ
ータに基づいたノードデータの統合管理によって効率的
な探索処理を実現することができる。

【０１０１】なお、上記の説明で経路探索装置は、ＣＤ
−ＲＯＭ等の地図データ記憶装置と探索結果表示装置と
を一体的に備える形態であるものとしたが、そのような
場合に限定されるわけではない。以下で、ローカル接続
やインターネット、無線ＬＡＮ等のネットワークを利用
する変形例について説明する。

【０１０２】例えば、第一に、地図データについてはネ
ットワークを介して取得を行う形態であってもよい。ま
た、第二に、ユーザの操作する外部装置とネットワーク
を介して接続することで、表示制御データを送付して探
索結果情報の提供を行ったり、ユーザ入力を取得したり
するものとしてもよい。第三に、ネットワークを介して
取得する地図データに基づいて探索処理を行い、かつ、
探索結果についてもネットワークを介した送付を行う態
様も考えられる。さらに、探索指示の取得元と探索結果
の送付先とが異なる場合も考えられる。なお、以上説明
した変形例において、ラベル操作等の探索処理そのもの
については、第１〜第３実施例等の探索処理を柔軟に選
択して利用することができる。例えば、第１の実施例で
Ａ→Ｃ→Ａを通行禁止としたが、禁止されていないとき
に利用してもよい。

【０１０３】Ｄ．コスト以外の要素に基づく経路選択：
実施例では、コストの大小関係以外に経路を選択するた
めに考慮すべき要素として交通規制が設けられている場
合について例示した。本発明は、交通規制に関わらず種
々の要素を考慮した経路探索に利用することができる。
かかる要素としては、例えば、直進優先、国道優先など
運転者の嗜好や安全性が挙げられる。

【０１０４】図９は、変形例として直線優先を考慮した
経路探索例を示す説明図である。図９に示すグラフで、
ノード、リンク及びリンクに付されたコストは、第１実
施例の説明において図３で示したものと同様である。図
９に示すグラフでは、ノードＣにおいて、通過方向に対
応したコストが設定されている点で、図３の場合と相違
する。

【０１０５】通過方向に対応したコストは、直線優先を
表すコストである。例えば、ノードＢ→Ｃ→Ｄのよう
に、ノードＣを直進する経路については、直進用のコス
ト値１が適用される。ノードＡ→Ｃ→Ｄのように、ノー
ドＣを右折して通過する経路については、右折用のコス
ト値７が適用される。

【０１０６】図９のラベル保持部３１０ｃは、経路探索
の過程において、２種類の候補経路Ａ→ＣとＡ→Ｂ→Ｃ
とに対応するラベルＬｃａ，Ｌｃｂａが記憶されている
状態を示した。ノードＣからの延伸方向が未定の状態で
は、直進コスト、右折コストは反映されないから、ラベ
ルＬｃａのコスト値は１、ラベルＬｃｂａのコスト値は
５である。ノードＤへの延伸においては、ラベルに含む
直前経路情報から直進・右折コストにかかるコストを求
め、候補経路間の対比を行う。これにより、直進優先の
条件を基礎とした経路「Ａ→Ｂ→Ｃ→Ｄ」が得られる。

【０１０７】図１０は、変形例として国道優先を考慮し
た経路探索例を示す説明図である。図９に示すグラフに
おいて、リンクＡ→Ｂ，Ｂ→Ｃ，Ｃ→Ｄ，Ｄ→Ｅの４個
のリンクは国道を示す。また、リンクＢ→Ｄ，Ｄ→Ｆは
通常の道路を表している。

【０１０８】ここで、一般に、通常の道路から国道に合
流する場合には、危険を伴ったり、時間がかかったり、
注意力を要したりする場合が多い。そこで、かかる状況
を表すコストとして、ノードＤには、国道合流の経路Ｂ
→Ｄ→Ｅについてのコスト値３が設定されている。

【０１０９】経路探索の結果、２つの経路Ａ→Ｂ→Ｄ、
Ａ→Ｂ→Ｃ→Ｄについてのコストが算出され、これらの
経路に対応した２つのラベルがノードＤに付された状態
を考える。ノードＤからの延伸方向が未決定の状態で
は、国道合流のコストは反映されない。従って、経路Ａ
→Ｂ→Ｄのコストは４、Ａ→Ｂ→Ｃ→Ｄのコストは５と
なる。

【０１１０】この状態で目的地Ｅへの延伸を行うと、経
路Ａ→Ｂ→ＤにはＤ→Ｅのコスト値１に加えて、国道合
流のコスト値３が反映されるため、総コストは８とな
る。経路Ａ→Ｂ→Ｃ→ＤにはＤ→Ｅのコスト値１のみが
加えられるため、総コストは６となる。従って、国道を
優先した経路Ａ→Ｂ→Ｃ→Ｄ→Ｅが探索結果として得ら
れる。

【０１１１】以上、図９と図１０とを利用して説明して
きた経路探索装置によれば、一つのノード又はリンクに
対応付けて生成する複数のラベルを用いることにより、
種々の要素を考慮しつつ経路の延伸を行って経路探索を
行うことができる。なお、図９及び図１０の変形例で
は、直進優先、国道優先などの要素を、コストに反映し
て考慮する方法を例示したが、これらの要素はコストに
反映させずに評価してもよい。例えば、図９の例では、
直進する経路が存在する限り、コストに関わらず直進経
路を選択するものとし、右折経路は、直進による経路が
全く不可能な場合にのみ選択するものとしてもよい。

【０１１２】以上、本発明の種々の実施例について説明
したが、本発明はこれらの実施例に限定されず、その趣
旨を逸脱しない範囲で種々の構成を採ることができるこ
とはいうまでもない。例えば、以上の処理はソフトウェ
アで実現する他、ハードウェア的に実現するものとして
もよい。

【図面の簡単な説明】

【図１】通過方法がある通路を例示する説明図である。

【図２】経路探索装置の概略構成図である。

【図３】経路探索装置で用いるデータの概略構成図であ
る

【図４】経路探索処理のフローチャートである。

【図５】ラベルデータの処理を示す説明図である。

【図６】図５に示す処理の続きを示す説明図である。

【図７】４点規制に対応するラベルデータの処理を例示
する説明図である。

【図８】リンクに対応するラベルデータの処理を例示す
る説明図である。

【図９】直線優先を考慮した経路探索例を示す説明図で
ある。

【図１０】国道優先を考慮した経路探索例を示す説明図
である。

【符号の説明】

１００…経路探索装置 １０１…操作パネル １０２…表示デバイス １０３…リモコン ２００…制御ユニット ２０１…地図データ入力部 ２０２…位置情報入力部 ２１０…表示制御部 ２２０…ユーザ入力部 ３００…経路探索部 ３１０…ラベル保持部 ３１１…探索処理部 ４００…地図記憶部 ４１０…規制情報記憶部 ４２０…ノード記憶部 ４２１…リンク記憶部 ４１０ａ…規制情報記憶部 ３１０ａ…ラベル保持部 ４１０ｂ…規制情報記憶部 ３１０ｂ…ラベル保持部 ４１０ｃ…規制情報記憶部 ３１０ｃ…ラベル保持部 ４１０ｄ…規制情報記憶部

フロントページの続き Ｆターム(参考） 2C032 HB05 HB22 HB25 HC08 HC15 HD16 HD23 2F029 AA02 AB01 AB07 AB13 AC02 AC09 AC14 AC16 AC20 5H180 AA01 BB13 CC12 FF04 FF05 FF12 FF13 FF22 FF27 FF32

Claims (10)

【特許請求の範囲】
1. 【請求項１】 経路探索を行う経路探索装置であって、 ノード、リンクを要素として表された通路データを記憶
   する通路データ記憶部と、 前記それぞれのノード及びリンクの少なくとも一方に対
   応づけられたコストを記憶するコスト記憶部と、 出発地、目的地に対応するノードを選択する指示を入力
   する指示入力部と、 前記通路データ記憶部及び前記コスト記憶部の記憶内容
   に基づいて出発地から目的地までの経路を探索する経路
   探索部とを備え、 前記経路探索部は、 複数の候補経路上のノードについて、前記出発地から該
   ノードに至るまでに経過した経過ノード及び経過リンク
   の少なくとも一方に対応付けられたコストの積算値を表
   すラベル情報を生成し、該ノードに対応付けて記憶する
   ラベル情報記憶部と、 前記コスト積算値の大小関係に基づいて前記候補経路の
   いずれかを選択する選択部と、 前記ラベル情報記憶部と、選択部とを繰り返し用いて前
   記目的地に至る経路を探索する探索遂行部とを備え、 前記ラベル情報記憶部は、 前記ノードに２以上のラベル情報を対応付けて記憶可能
   であるとともに、 ２以上のラベル情報を記憶する場合には、前記ノードに
   至る直前の所定区間の経路を特定する直前経路情報を、
   各ラベル情報に含めて記憶する経路探索装置。
2. 【請求項２】 経路探索を行う経路探索装置であって、 ノード、リンクを要素として表された通路データを記憶
   する通路データ記憶部と、 前記それぞれのノード及びリンクの少なくとも一方に対
   応づけられたコストを記憶するコスト記憶部と、 出発地、目的地に対応するノードを選択する指示を入力
   する指示入力部と、 前記通路データ記憶部及び前記コスト記憶部の記憶内容
   に基づいて出発地から目的地までの経路を探索する経路
   探索部とを備え、 前記経路探索部は、 複数の候補経路上のノードについて、前記出発地から該
   ノードに至るまでに経過した経過ノード及び経過リンク
   の少なくとも一方に対応付けられたコストの積算値を表
   すラベル情報を生成し、該ノードに対応付けて記憶する
   ラベル情報記憶部と、 前記コスト積算値の大小関係に基づいて前記候補経路の
   いずれかを選択する選択部と、 前記ラベル情報記憶部と、選択部とを繰り返し用いて前
   記目的地に至る経路を探索する探索遂行部とを備え、 前記ラベル情報は、該ノードに至る直前のノードに対応
   したラベル情報を特定する直前経路情報を含む経路探索
   装置。
3. 【請求項３】 請求項１または２記載の経路探索装置で
   あって、 少なくとも一部のノードについて、通過方法についての
   規制情報を記憶する規制情報記憶部を備え、 前記選択部は、該規制情報を考慮して前記選択を行う経
   路探索装置。
4. 【請求項４】 請求項３記載の経路探索装置であって、 前記規制情報は、Ｎ点（Ｎは３以上の自然数）のノード
   によって定義される規制であり、 前記直前経路情報は、Ｎ−２点のノードに相当する区間
   の経路情報である経路探索装置。
5. 【請求項５】 請求項１〜４いずれか記載の経路探索装
   置であって、 前記ラベル情報記憶部は、前記直前経路情報の少なくと
   も一部が重複するラベル情報の生成を抑制する経路探索
   装置。
6. 【請求項６】 コンピュータに経路探索を行わせるため
   のコンピュータプログラムであって、 ノード、リンクを要素として表された通路データを記憶
   する通路データ記憶機能と、 前記それぞれのノード及びリンクの少なくとも一方に対
   応づけられたコストを記憶するコスト記憶機能と、 出発地、目的地に対応するノードを選択する指示を入力
   する指示入力機能と、 前記通路データ記憶機能及び前記コスト記憶機能の記憶
   内容に基づいて出発地から目的地までの経路を探索する
   経路探索機能とを備え、 前記経路探索機能は、 複数の候補経路上のノードについて、前記出発地から該
   ノードに至るまでに経過した経過ノード及び経過リンク
   の少なくとも一方に対応付けられたコストの積算値を表
   すラベル情報を生成し、該ノードに対応付けて記憶する
   ラベル情報記憶機能と、 前記コスト積算値の大小関係に基づいて前記候補経路の
   いずれかを選択する選択機能と、 前記ラベル情報記憶機能と、選択機能とを繰り返し用い
   て前記目的地に至る経路を探索する探索遂行機能とを備
   え、 前記ラベル情報記憶機能は、 前記ノードに２以上のラベル情報を対応付けて記憶可能
   であるとともに、 ２以上のラベル情報を記憶する場合には、前記ノードに
   至る直前の所定区間の経路を特定する直前経路情報を、
   各ラベル情報に含めて記憶するコンピュータプログラ
   ム。
7. 【請求項７】 コンピュータに経路探索を行わせるため
   のコンピュータプログラムであって、 ノード、リンクを要素として表された通路データを記憶
   する通路データ記憶機能と、 前記それぞれのノード及びリンクの少なくとも一方に対
   応づけられたコストを記憶するコスト記憶機能と、 出発地、目的地に対応するノードを選択する指示を入力
   する指示入力機能と、 前記通路データ記憶機能及び前記コスト記憶機能の記憶
   内容に基づいて出発地から目的地までの経路を探索する
   経路探索機能とを備え、 前記経路探索機能は、 複数の候補経路上のノードについて、前記出発地から該
   ノードに至るまでに経過した経過ノード及び経過リンク
   の少なくとも一方に対応付けられたコストの積算値を表
   すラベル情報を生成し、該ノードに対応付けて記憶する
   ラベル情報記憶機能と、 前記コスト積算値の大小関係に基づいて前記候補経路の
   いずれかを選択する選択機能と、 前記ラベル情報記憶機能と、選択機能とを繰り返し用い
   て前記目的地に至る経路を探索する探索遂行機能とを備
   え、 前記ラベル情報は、該ノードに至る直前のノードに対応
   したラベル情報を特定する直前経路情報を含むコンピュ
   ータプログラム。
8. 【請求項８】 請求項６または７記載のコンピュータプ
   ログラムを記録したコンピュータ読み取り可能な記録媒
   体。
9. 【請求項９】 コンピュータを用いて経路探索を行う方
   法であって、 ノード、リンクを要素として表された通路データを記憶
   する通路データ記憶工程と、 前記それぞれのノード及びリンクの少なくとも一方に対
   応づけられたコストを記憶するコスト記憶工程と、 出発地、目的地に対応するノードを選択する指示を入力
   する指示入力工程と、 前記通路データ記憶工程及び前記コスト記憶工程の記憶
   内容に基づいて出発地から目的地までの経路を探索する
   経路探索工程とを備え、 前記経路探索工程は、 複数の候補経路上のノードについて、前記出発地から該
   ノードに至るまでに経過した経過ノード及び経過リンク
   の少なくとも一方に対応付けられたコストの積算値を表
   すラベル情報を生成し、該ノードに対応付けて記憶する
   ラベル情報記憶工程と、 前記コスト積算値の大小関係に基づいて前記候補経路の
   いずれかを選択する選択工程と、 前記ラベル情報記憶工程と、選択工程とを繰り返し用い
   て前記目的地に至る経路を探索する探索遂行工程とを備
   え、 前記ラベル情報記憶工程では、 前記ノードに２以上のラベル情報を対応付けて記憶可能
   であるとともに、 ２以上のラベル情報を記憶する場合には、前記ノードに
   至る直前の所定区間の経路を特定する直前経路情報を、
   各ラベル情報に含めて記憶する方法。
10. 【請求項１０】 コンピュータを用いて経路探索を行う
    方法であって、 ノード、リンクを要素として表された通路データを記憶
    する通路データ記憶工程と、 前記それぞれのノード及びリンクの少なくとも一方に対
    応づけられたコストを記憶するコスト記憶工程と、 出発地、目的地に対応するノードを選択する指示を入力
    する指示入力工程と、 前記通路データ記憶工程及び前記コスト記憶工程の記憶
    内容に基づいて出発地から目的地までの経路を探索する
    経路探索工程とを備え、 前記経路探索工程は、 複数の候補経路上のノードについて、前記出発地から該
    ノードに至るまでに経過した経過ノード及び経過リンク
    の少なくとも一方に対応付けられたコストの積算値を表
    すラベル情報を生成し、該ノードに対応付けて記憶する
    ラベル情報記憶工程と、 前記コスト積算値の大小関係に基づいて前記候補経路の
    いずれかを選択する選択工程と、 前記ラベル情報記憶工程と、選択工程とを繰り返し用い
    て前記目的地に至る経路を探索する探索遂行工程とを備
    え、 前記ラベル情報は、該ノードに至る直前のノードに対応
    したラベル情報を特定する直前経路情報を含む経路探索
    装置。