JP4358440B2 - ナビゲーションシステムにおけるルート決定のためのソースデータに作用を与える方法 - Google Patents

Description

【０００１】
発明の属する技術分野
本発明は、ディジタルデータベースに基づき移動手段たとえば車両、航空機または船舶のために、まえもって定められたスタートポイントからまえもって定められたターゲットポイントまでのルートを決定するためのソースデータに作用を与える請求項１の上位概念に記載の方法に関する。この場合、前記ディジタルデータベースは、まえもって定められた経路区間ｋ_ｉ を、それら個々の経路区間ｋ_ｉ を相互に結ぶ相応に割り当てられたノードポイントｎ_ｉ とともに有しており、前記の経路区間ｋ_ｉ および／またはノード区間ｎ_ｉ に個々のウェイトｇ_ｉ が割り当てられている。
【０００２】
たとえばＧＰＳ（Global Positioning System）をベースとするようなナビゲーションシステムは、まえもって定められた目的地までのナビゲーションにあたり、移動手段の運転者を支援する。この場合、ナビゲーションシステムは、少なくとも出発地座標と目的地座標ならびに実際の道路網のコピーである相応のディジタルデータベースに基づき、最適な経路もしくは最適なルートを決定する。しかしながら、自立的に求められたナビゲーションシステムのルートであると、これまでのナビゲーションシステムの場合には実際の交通事象たとえば特定の道路区間での渋滞などが考慮されず、または不十分にしか考慮されない。
【０００３】
発明の開示、課題、解決手段、利点
本発明の課題は、冒頭で述べた形式の方法において、上述の欠点を解消し、実際の交通状況で生じたそのような交通事象の作用を、適切なやり方でディジタルマップベースに簡単に変換するよう改良することにある。
【０００４】
この課題は、冒頭で述べた形式の方法において請求項１または請求項２記載の特徴により解決される。
【０００５】
さらに本発明によれば、ウェイトｇ_ｉ を外部の事象に依存して変更してから、ルート探索アルゴリズムによりルートを決定するように構成されている。
【０００６】
これにより得られる利点とは、たとえばルート探索アルゴリズムにより最適な経路を見つけ出す際、設けられているディジタルマップベースに作用が及ぼされた後に代案ルートが生じ、それは基礎を成す交通状況を非常に正確に考慮したものとなる。
【０００７】
請求項２から９には本発明の有利な実施形態が示されている。
【０００８】
この場合、ウェイトｇ_ｉ の合計が最小となるようルート探索アルゴリズムによってルートを決定することにより、最適なルートガイドが実現される。
【０００９】
本発明による方法の有利な実施形態によれば、ウェイトｇ_ｉ は、個々の経路区間ｋ_ｉ の経路長ｌ_ｉ、個々の経路区間ｋ_ｉ の走行時間ｔ_ｋｉ および／または個々のノードポイントｎ_ｉ における個々の待ち時間ｔ_ｎｉ である。その際、ノードポイントはたとえば国境通過地点または料金所であり、待ち時間は個々の手続完了時間に関係する。
【００１０】
好適には、ウェイトｇ_ｉ を変更するためのデータをデータソースが供給し、そのデータをデータシンクにおいて処理する。その際、データソースは、交通メッセージ用の受信機、イベントデータバンクおよび／またはデータベースに交通メッセージをマッピングするデータバンクであり、データシンクは、たとえばナビゲーションシステムにおけるナビゲーションコンピュータ内で交通メッセージデータを処理するソフトウェアである。
【００１１】
事象に即してウェイトを変更するため、データソースおよび／またはまえもって定められたウェイト変更のためのデータシンクにより外部の事象を分類する。
【００１２】
１つの有利な実施形態によれば、ウェイトｇ_ｉ は経路区間ｋ_ｉ の走行時間ｔ_ｋｉであり、変更されたウェイトｔ_ｋｉ ^ｎｅｕは式
【００１３】
【数３】

【００１４】
に従って得られ、ここでＶ（ｋ_ｉ）は経路区間ｋ_ｉ での速度であり、ΔＶ_ｃ は外部の事象に基づく経路区間速度の変更である。
【００１５】
別の有利な実施形態によれば、ウェイトｇ_ｉ は経路区間ｋ_ｉ の走行時間であり、データベースは階層的に構成されていて、変更されるウェイトｔ_ｋｉ ^ｎｅｕは式
【００１６】
【数４】

【００１７】
に従い得られ、ここでＶ（ｋ_ｉ）は経路区間ｋ_ｉ での速度であり、ΔＶ_ｃ は外部の事象に基づく経路区間速度の変更であり、Δｌ_{Ｌｅｖｅｌｊ} は全エッジ長のパーセントで表した長さ配分であり、この長さの配分によって、階層状のデータベースの縮尺単純化レベルｊにおける配分に応じた作用が表される。
【００１８】
図面の簡単な説明
次に、添付の図面を参照しながら本発明について詳しく説明する。
【００１９】
図１は、実際の道路網をマッピングするディジタルデータベースを示す図である。
【００２０】
図２は、経路区間もしくはエッジとディジタルデータベースの経路区間ウェイトもしくはエッジウェイトとの対応関係を示す図である。
【００２１】
図３は、ディジタルデータベースに基づく自動車のためのルートの実例を示す図であって、この場合、個々の走行時間がエッジのウェイトとして割り当てられている。
【００２２】
図４は、ディジタルデータベースの階層構造を示す図である。
【００２３】
図５は、交通事象の分類を示す図である。
【００２４】
図６は、図３によるディジタルデータベースに基づく自動車のためのルートの実例を示す図である。
【００２５】
図７は、変更されたウェイトを階層データベースにおける１つの縮尺単純化レベルから次のレベルへ一貫して受け渡す様子を示す図である。
【００２６】
本発明を実施するための最良のやり方
次に、本発明による方法の動作説明のため、図１〜図４を参照しながら、ディジタル形式のデータベースないしはマップベースによる実際の道路網のマッピング、ならびにルート探索アルゴリズムによるその方法について詳しく説明する。
【００２７】
ディジタルマップベースによる実際の道路網のマッピングは、たとえば図１に示されている形態をもつ。このように道路網は、数学的に簡単に２分グラフによって表される。そこにおいて道路の通りは、方向づけられた経路区間またはネットエッジ（ｋ_ｉ）によってシンボリックに表される。ネットノード（ｎ_ｉ）によって、道路要素相互間の結合（交差点、高速道路ジャンクション等）が表される。これらの属性を用いることで、このようなネットに関して経路記述を生成することができる。エッジの名前やその方向（エッジベクトル）に関して１つの経路はエッジリストのかたちで、規定されたスタートエレメントから出発して設定されたターゲットエレメントまで、一義的に規定される。
【００２８】
ネット内のエッジに特定の属性（エッジウェイト）を割り当てる場合にはそのようなネットに対し、目下の車両位置（スタートエッジ）から出発して所望の目的地（ターゲットエッジ）まで、最適なルートを決定するアルゴリズム手法を適用することができる。この場合、エッジに割り当てられたウェイトは、様々な種類のものである。アルゴリズムにとって重要であるのは、データベースのすべてのエッジからアルゴリズムによって使用されたウェイトを取り出せることである。この課題を解決する公知の手法は、たとえば Ford または Moore による最適化アルゴリズムである。最も簡単な事例では、たとえば個々のエッジのエッジウェイトとして、図２の表に示されているように、それらの固有の長さを割り当てることができる。
【００２９】
ついでこのようなネットに固有のルートサーチアルゴリズムが適用される。この目的は、見つけ出された選択に対し、「関与しているすべてのエッジウェイトの合計が、スタートエッジからターゲットエッジに至る決定可能な他のどのようなエッジ選択よりも小さい」ことがあてはまるよう、エッジ選択を決めることである。したがってこの手法によって、スタートエッジとターゲットエッジとの間の可能な最短接続が求められ、これは図１の実例では以下のとおりとなる：
k1 -＞ -k5 -＞ k8 -＞ -k10
ここで極性符号は、所定のエッジベクトルに関する走行方向を表す（正の極性符号：ベクトル方向；負の極性符号：反ベクトル方向）。
【００３０】
エッジの属性づけのため、ウェイトとして他の解釈も可能である。走行時間に関して最適な経路を求めるため、たとえばウェイトとしてマップに走行時間を割り当てることができる。それらの走行時間は、エッジ長と区間要素（図３）において車両のとっている速度とから得られる。上述の記載において用いられたルート探索アルゴリズムは図３の実例であれば、２５秒の最小総走行時間をもつ最適なルート K_１ -＞ -k5 -＞ k6 を見つけ出す。
【００３１】
次に図４を参照しながら、ディジタル形式のマップベースもしくはデータベースの構造について説明する。ディジタル形式のデータベースの規模ならびに計算技術的に制限された自立的ナビゲーションシステムの性能ゆえに一般に、そのようなデータベース（たとえばドイツ）を全体的にルート探索アルゴリズムによって用いることはできず、好適には種々の領域に分割される。このため、様々な分解能によって道路網を記述する複数のレベルへの分割を行うことができる（図４）。そのような部分領域の重要な特性は、それらがグラフエレメントの個数においてまえもって定められたオーダを超えない、ということである。このため道路マップのいっそう高い分解能のレベルには、相応に多くの部分領域が含まれる。
【００３２】
この場合、階層状のディジタルデータベースの構造ならびに使用法を、地図帳形式の構造と似たものとして思い浮かべることができる。データベースによってカバーされる領域は、最も高い分解能では個々のページにおいて複数の部分領域に分割される。隣り合うページへの参照は、各ページ間の関係によって形成される。しかしながら一般的にユーザやアルゴリズム手法にとっては、１つのページまたは制限された個数のページしか同時に処理できない。このため、かなり遠い距離に及ぶルートを求めるためには、概要マップの形式でさらに縮尺単純化された表示が必要とされる（ディジタルデータベースの縮尺単純化されたレベル）。
【００３３】
本発明による方法によれば、前述のグラフ（データベースと呼ぶ）における個々のエレメントのウェイトを、交通事象に依存して適切に変更することができる。この場合、操作すべきウェイトがグラフ中でエッジウェイトとして表されるのか、および／またはノードウェイトとして表されるのかは、重要ではない。以下では実例としてエッジウェイトについて説明するが、本発明はそれに限定されるものではない。たとえば交通事象の処理によって、エッジウェイトが変更される。エッジウェイトにマッピングされる他のどのような作用であっても、本発明による方法によって処理することができる。
【００３４】
一貫したウェイト変更のために必要とされるすべてのデータは、少なくとも１つのデータソースへ完全に供給される。データシンクは、データソースから供給されたデータをデータベース内のデータと結びつける。データソースはたとえば交通メッセージの受信機、イベントデータバンクおよび／またはデータベースへ交通メッセージをマッピングするデータバンクであり、その際、作用を与えるべきデータベースエレメントを求めるやり方は、本発明による方法とは無関係である。データシンクはたとえば、ナビゲーションシステムのナビゲーションコンピュータにおいて交通メッセージデータを処理するソフトウェアである。
【００３５】
あるグラフエレメントのウェイトを変更するため、ウェイト変更のソースと処理を行うシンクとの間のウェイト変更のフォームに関する取り決めが設けられている。このような取り決めは、たとえば事象の分類である。この場合、受信機は、定められたルールに従い交通メッセージに識別子をつける。ナビゲーションにおいて識別子に、規定されたウェイト変更を割り当てる。しかし本発明による方法によれば、メッセージ自体によってウェイト変更を規定することも可能である。その場合には、交通メッセージの送信側によってウェイト変更が指定される。ナビゲーション内には、ウェイト変更のためのデータは記憶されていない。
【００３６】
本発明による方法を適用するために、関連するすべての事象が様々な事象クラスに格付けされる。その際、ある事象クラスはたとえば、目下の速度に対する所定の作用に相当し、図５に実例として示されているように、その作用はディジタルマップベース内の各エッジエレメントに割り当てられている。
【００３７】
次に特別な実施例として、走行時間属性をもつエッジを重みづけるための計算式について詳しく説明する。スタートエッジとターゲットエッジとの間の所要走行時間に関して最適な経路を求めるため、図２に示した対応づけと同様に、ウェイトとしてエッジに個々の走行時間が割り当てられる。この場合、あるエッジの走行時間ｔ_ｋｉ は、エッジ長ｌ_ｋｉ とその区間エレメントに対してとられている走行速度Ｖ（k_ｉ）から、
【００３８】
【数５】

【００３９】
となる。
【００４０】
ここで関数Ｖ（ｋ_ｉ）は目下のエッジエレメントに対し、固有のエッジ属性（たとえば機能的な道路クラス、国の帰属等）に依存して速度が割り当てられる。
【００４１】
この場合、エッジの重み付けに対し、速度によって以下のように作用が及ぼされる。分類された交通事象は、とられている速度Ｖ（ｋ_ｉ)の直線的な変更によりエッジエレメントｋ_ｉ に対し作用が及ぼされる：
【００４２】
【数６】

【００４３】
この場合、ΔＶ_ｃ は、エッジもしくは経路区間ｋ_ｉ における外部の事象に基づく速度変更である。このようにして目下のネット全体において、すべての他のエッジエレメントはルート探索アルゴリズムにとってその「魅力」に関して、作用を受けたエレメントよりも良好なかたちで現れる。作用を受けたネットにそれを適用した場合、エッジエレメントはそれらの新たなウェイトに基づき評価され、個々のエレメントに適切な強さで作用が及ぼされれば、従来のやり方で得られるようなものに対して代案となるエッジ列もしくは分岐ルートまたは代案ルートが得られる。
【００４４】
図３の実例のネットにおいてルート探索アルゴリズムが、スタートエッジとターゲットエッジに関して時間的に最短の経路についての最適な結果として、２５秒の全走行時間をもつエッジ列 k1 -＞ -k5 -＞ k6 を求めたものとする。エッジエレメントｋ５に対し渋滞など十分に強い作用が及ぼされると、そのエッジウェイトは図５に従って１０秒〜５０秒に変更される：
【００４５】
【数７】

【００４６】
このようして時間的に最適な経路を新たに計算した後、図６に示されているように、３０秒の総走行時間をもつ択一的なエッジ列 k1 -＞ -k2 -＞ -k3 -＞ k6 が生じる。
【００４７】
次に、階層状のデータモデルにおける一貫したエッジウェイト変更について詳しく説明する。分類された交通事象に関する先に説明したエッジウェイトに作用を及ぼす方法は、はじめはもっぱら一定のネットレベル内でエッジウェイトの変更を行う。これにより、ネット全体においてただ１つの縮尺単純化レベルにおいてのみ行われる（ディジタルデータベースの階層構造の描かれた図４参照）。ルート計算のためのアルゴリズムにとって、任意の縮尺単純化レベルからのデータを使用できなければならないため、好適には外部からのネット制御により変更されたエッジウェイトコンフィグレーションが、異なる縮尺単純化の他のあらゆるレベルにおいても行われる。この場合、特定のレベルで行われた変更は、他のすべてのレベルにおいて等価もしくは首尾一貫している。
【００４８】
図７には、種々の縮尺単純化レベルにおける特定のネット区間が示されている。この場合、縮尺単純化レベルの番号が大きくなるにつれて、ディジタルマップベースもしくはデータベースにおけるそのネットマッピングのネット分解能が粗くなる。その際、実例として示されている最低縮尺単純化レベルの３つのエッジエレメントｋ_１，ｋ_２，ｋ_３ は、最高縮尺単純化レベルではただ１つのエッジエレメントｋ_６ によって表されている。ここで、エッジエレメントｋ_２ に対し（式（ＩＩ）に従い）分類されたある事象のマッピングによって、この最低縮尺レベルにおいてエレメントがその長さについて１００％に設定されるある特定のエッジウェイト変更が引き起こされると、そのような作用はそれよりも高いレベルでは、（縮尺単純化に基づき）設けられているマッピング規則にのみ応じて、長さの配分に影響を及ぼすことができる。次に高い縮尺単純化レベルにおけるエレメントｋ_５ も、作用を受けていないレベル０のエレメントｋ_３ を表しており、その結果、エッジウェイト変更のためにレベル１でも、エッジｋ_２ について相応の長さの配分だけしか変更できない。
【００４９】
このように、作用を及ぼすべきエッジエレメントについて付加的な属性が必要とされ、それは個々のエレメントの該当する長さの配分を設けられている縮尺単純化レベルに依存して記述するものである。したがって式（ＩＩ）で記述したエッジウェイト変更のための規則は、好適には対応する係数について以下のように拡張される：
【００５０】
【数８】

【００５１】
ここでΔｌ_{Ｌｅｖｅｌｊ} は全エッジ長のパーセントで表した長さの配分であり、これは縮尺単純化レベルｊにおいて配分に応じた作用を表す。
【００５２】
このように本発明による方法によれば、まえもって定められた固定的なディジタルマップベースにおいて、スタティックに設定されたエッジウェイトおよび／またはノードウェイトに汎用的な作用を及ぼすことができるようになる。考慮すべき事象は、データベースに左右されずに設定可能な影響（事象分類）を用いてそれらに作用を及ぼすので、種々の影響を想定することができる。たとえば渋滞やのろのろ運転などの交通事象によって、特定の区間が悪化する可能性がある。この場合、自立的ナビゲーションシステムは、悪化したウェイトに応じてそのような区間（たとえば高速道路における渋滞）を避け、たとえば一般国道区間を経由した迂回が可能ならば、時間的に好適な方の選択肢を指示する。
【００５３】
さらに別の可能な構成として、ある特定の属性に対応する所定のネット内における特定の区間が完全に閉鎖される。たとえば重たい貨物搬送車などの車両に対し、そのようなダイナミックなナビゲーションシステムは、最大走行重量が小さすぎる区間を閉鎖することができる。それ相応に悪化させたノードウェイトによって、そのような区間はルート探索アルゴリズムにとって通行不能というようにはたらき、したがって生成された走行推奨に関してそれ相応に迂回が行われる。
【００５４】
他方、たとえば特定のルートをまえもって作り出し、システムによって提案されたルートに対しそのようにして適切なやり方で影響を与える目的で、ネット内のエッジウェイトの改善を行うことも考えられる。
【００５５】
本発明による方法によれば、階層状のデータモデルにおいて首尾一貫した作用を確実に与えることができる。たとえばルート探索や目的地ガイドのためのこれまで基礎としてきたアルゴリズムをそのために整合させる必要はない。それというのも、それらにとって外部からの影響はわからないからである。
【図面の簡単な説明】
【図１】 実際の道路網をマッピングするディジタルデータベースを示す図である。
【図２】 経路区間もしくはエッジとディジタルデータベースの経路区間ウェイトもしくはエッジウェイトとの対応関係を示す図である。
【図３】 ディジタルデータベースに基づく自動車のためのルートの実例を示す図であって、この場合、個々の走行時間がエッジのウェイトとして割り当てられている。
【図４】 ディジタルデータベースの階層構造を示す図である。
【図５】 交通事象の分類を示す図である。
【図６】 図３によるディジタルデータベースに基づく自動車のためのルートの実例を示す図である。
【図７】 変更されたウェイトを階層データベースにおける１つの縮尺単純化レベルから次のレベルへ一貫して受け渡す様子を示す図である。

Claims (7)

1. ディジタルデータベースに基づき移動手段のために、まえもって定められたスタートポイントからまえもって定められたターゲットポイントまでのルートを決定するためのソースデータに作用を与える方法において、
   前記ディジタルデータベースは、まえもって定められた経路区間ｋ_iを、それら個々の経路区間ｋ_iを相互に結ぶ相応に割り当てられたノードポイントｎ_iとともに有しており、前記の経路区間ｋ_iおよび／またはノード区間ｎ_iに個々のウェイトｇ_iが割り当てられていて、
   該ウェイトｇ_iを外部の事象に依存して変更してから、ルート探索アルゴリズムによってルートを決定し、
   前記ウェイトｇ_iは経路区間ｋ_iの走行時間ｔ_kiであり式
   

   

   に従い変更されたウェイトｔ_ki ^neuを生じさせ、ここでＶ（ｋ_i）は経路区間ｋ_iでの速度であり、ΔＶ_cは外部の事象に基づく経路区間速度の変更であり、ｌ _ki は経路区間ｋ _i の経路長であることを特徴とする、
   ルートを決定するためのソースデータに作用を与える方法。
2. ディジタルデータベースに基づき移動手段のために、まえもって定められたスタートポイントからまえもって定められたターゲットポイントまでのルートを決定するためのソースデータに作用を与える方法において、
   前記ディジタルデータベースは、まえもって定められた経路区間ｋ_iを、それら個々の経路区間ｋ_iを相互に結ぶ相応に割り当てられたノードポイントｎ_iとともに有しており、前記の経路区間ｋ_iおよび／またはノード区間ｎ_iに個々のウェイトｇ_iが割り当てられていて、
   該ウェイトｇ_iを外部の事象に依存して変更してから、ルート探索アルゴリズムによってルートを決定し、
   前記ウェイトｇ_iは経路区間ｋ_iの走行時間ｔ_kiであり、前記データベースは階層状に構成されていて、変更されたウェイトｔ_ki ^neuを式
   

   

   に従い生じさせ、ここでＶ（ｋ_i）は経路区間ｋ_iでの速度であり、ΔＶ_cは外部の事象に基づく経路区間速度の変更であり、Δｌ_Leveljは全エッジ長のパーセントで表した長さ配分であり、該長さの配分によって、階層状のデータベースの縮尺単純化レベルｊにおける配分に応じた作用を表し、ｌ _ki は経路区間ｋ _i の経路長であることを特徴とする、
   ルートを決定するためのソースデータに作用を与える方法。
3. 前記ルート探索アルゴリズムは、前記ウェイトｇ_iの合計が最小となるようにルートを決定する、請求項１または２記載の方法。
4. 前記ウェイトｇ_iを変更するためのデータをデータソースが供給し、該データをデータシンクにおいて処理する、請求項１から３のいずれか１項記載の方法。
5. 前記データソースは、交通メッセージ用の受信機、イベントデータバンクおよび／またはデータベースに交通メッセージをマッピングするデータバンクである、請求項４記載の方法。
6. 前記データシンクは、ナビゲーションシステムにおけるナビゲーションコンピュータ内で交通メッセージデータを処理するソフトウェアである、請求項４または５記載の方法。
7. 前記の外部の事象を、データソースおよび／または所定のウェイト変更のためのデータシンクによって分類する、請求項４から６のいずれか１項記載の方法。

Images