• ポートフォリオ機能


ポートフォリオを新規に作成して保存
既存のポートフォリオに追加保存

  • この表をプリントする
PDF PDFをダウンロード
審決分類 審判 全部申し立て 2項進歩性  G01C
管理番号 1044907
異議申立番号 異議2000-72944  
総通号数 22 
発行国 日本国特許庁(JP) 
公報種別 特許決定公報 
発行日 1996-05-21 
種別 異議の決定 
異議申立日 2000-07-26 
確定日 2001-04-25 
異議申立件数
訂正明細書 有 
事件の表示 特許第3007803号「地図データ記憶媒体を用いた経路探索装置」の請求項1ないし6に係る特許に対する特許異議の申立てについて、次のとおり決定する。 
結論 訂正を認める。 特許第3007803号の請求項1ないし6に係る特許を取り消す。 
理由 【1】手続の経緯
本件特許第3007803号の請求項1乃至6に係る発明についての出願は、平成6年11月1日に特許出願され、平成11年11月26日に設定登録され、その後、三菱電機株式会社より特許異議の申立てがなされ、取消理由通知がなされたところ、その指定期間内である平成13年1月29日に訂正請求がなされたものである。

【2】訂正の適否
1.訂正事項
A.特許請求の範囲の請求項1乃至4を、
「 【請求項1】 2点間の経路を地図データに基づいて経路探索を行う経路探索装置において、
(a)少なくとも道路の交差点または行止まりを示すノードに関するノードデータと、前記ノードを連結するリンクに関するリンクデータと、道路の形状を折線近似した折点を示す補間ノードに関する補間ノードデータと、前記補間ノードを連結する補間リンクに関する補間リンクデータとから成る第1地図データと、
道路の交差点または行止まりを示すノードに関するノードデータと、前記ノードを連結するリンクに関するリンクデータとから成る第2地図データとを含む地図データ記憶媒体と、
(b)前記地図データ記憶媒体の第2地図データに基づき経路探索を行う経路探索手段と、
(c)前記経路探索手段が第2地図データに基づいて探索した経路を、前記地図データ記憶媒体の第1地図データに基づいて地図上に表示する表示手段とを備えることを特徴とする地図データ記憶媒体を用いた経路探索装置。
【請求項2】 前記地図データ記憶媒体の第1地図データに基づいて地図を表示する表示手段を備えることを特徴とする請求項1記載の地図データ記憶媒体を用いた経路探索装置。
【請求項3】 2点間の経路を地図データに基づいて経路探索を行う経路探索装置において、
(a)少なくとも道路の交差点または行止まりを示すノードに関するノードデータと、前記ノードを連結するリンクに関するリンクデータと、道路の形状を折線近似した折点を示す補間ノードに関する補間ノードデータと、前記補間ノードを連結する補間リンクに関する補間リンクデータとから成る第1地図データと、
道路の交差点または行止まりを示すノードに関するノードデータと、前記ノードを連結するリンクに関するリンクデータとから成る第2地図データとを含む地図データ記憶媒体と、
(b)前記地図データ記憶媒体の第2地図データに基づき経路探索を行う経路探索手段とを備え、
前記地図データ記憶媒体が記憶する第2地図データのリンクデータには、リンクに対応する道路の属性および経路コストに関するデータが含まれていることを特徴とする地図データ記憶媒体を用いた経路探索装置。
【請求項4】 2点間の経路を地図データに基づいて経路探索を行う経路探索装置において、
(a)少なくとも道路の交差点または行止まりを示すノードに関するノードデータと、前記ノードを連結するリンクに関するリンクデータと、道路の形状を折線近似した折点を示す補間ノードに関する補間ノードデータと、前記補間ノードを連結する補間リンクに関する補間リンクデータとから成る第1地図データと、
道路の交差点または行止まりを示すノードに関するノードデータと、前記ノードを連結するリンクに関するリンクデータとから成る第2地図データとを含む地図データ記憶媒体と、
(b)前記地図データ記憶媒体の第2地図データに基づき経路探索を行う経路探索手段と、
(c)前記経路探索手段が第2地図データに基づいて探索した経路を、前記地図データ記憶媒体の第1地図データに基づいて地図上に表示する表示手段とを備え、
前記地図データ記憶媒体が記憶する第2地図データのリンクデータには、リンクに対応する道路の属性および経路コストに関するデータが含まれていることを特徴とする地図データ記憶媒体を用いた経路探索装置。」と訂正する。
B.明細書の段落【0008】における「本発明は、2点間の経路を地図データに基づいて経路探索を行う経路探索装置において、
(a)少なくとも道路の交差点または行止まりを示すノードに関するノードデータと、前記ノードを連結するリンクに関するリンクデータと、道路の形状を折線近似した折点を示す補間ノードに関する補間ノードデータと、前記補間ノードを連結する補間リンクに関する補間リンクデータとから成る第1地図データと、
道路の交差点または行止まりを示すノードに関するノードデータと、前記ノードを連結するリンクに関するリンクデータとから成る第2地図データとを含む地図データ記憶媒体と、
(b)前記地図データ記憶媒体の第2地図データに基づき経路探索を行う経路探索手段とを備えることを特徴とする地図データ記憶媒体を用いた経路探索装置である。
また本発明は、前記経路探索手段が第2地図データに基づいて探索した経路を、前記地図データ記憶媒体の第1地図データに基づいて地図上に表示する表示手段を備えることを特徴とする。
また本発明は、前記地図データ記憶媒体の第1地図データに基づいて地図を表示する表示手段を備えることを特徴とする。
また本発明は、前記地図データ記憶媒体が記憶する第2地図データのリンクデータには、リンクに対応する道路の属性および経路コストに関するデータが含まれていることを特徴とする。」を、
「本発明は、2点間の経路を地図データに基づいて経路探索を行う経路探索装置において、
(a)少なくとも道路の交差点または行止まりを示すノードに関するノードデータと、前記ノードを連結するリンクに関するリンクデータと、道路の形状を折線近似した折点を示す補間ノードに関する補間ノードデータと、前記補間ノードを連結する補間リンクに関する補間リンクデータとから成る第1地図データと、
道路の交差点または行止まりを示すノードに関するノードデータと、前記ノードを連結するリンクに関するリンクデータとから成る第2地図データとを含む地図データ記憶媒体と、
(b)前記地図データ記憶媒体の第2地図データに基づき経路探索を行う経路探索手段と、
(c)前記経路探索手段が第2地図データに基づいて探索した経路を、前記地図データ記憶媒体の第1地図データに基づいて地図上に表示する表示手段とを備えることを特徴とする地図データ記憶媒体を用いた経路探索装置である。
また、本発明は、前記地図データ記憶媒体の第1地図データに基づいて地図を表示する表示手段を備えることを特徴とする。
また、本発明は、2点間の経路を地図データに基づいて経路探索を行う経路探索装置において、
(a)少なくとも道路の交差点または行止まりを示すノードに関するノードデータと、前記ノードを連結するリンクに関するリンクデータと、道路の形状を折線近似した折点を示す補間ノードに関する補間ノードデータと、前記補間ノードを連結する補間リンクに関する補間リンクデータとから成る第1地図データと、
道路の交差点または行止まりを示すノードに関するノードデータと、前記ノードを連結するリンクに関するリンクデータとから成る第2地図データとを含む地図データ記憶媒体と、
(b)前記地図データ記憶媒体の第2地図データに基づき経路探索を行う経路探索手段とを備え、
前記地図データ記憶媒体が記憶する第2地図データのリンクデータには、リンクに対応する道路の属性および経路コストに関するデータが含まれていることを特徴とする地図データ記憶媒体を用いた経路探索装置である。
また、本発明は、2点間の経路を地図データに基づいて経路探索を行う経路探索装置において、
(a)少なくとも道路の交差点または行止まりを示すノードに関するノードデータと、前記ノードを連結するリンクに関するリンクデータと、道路の形状を折線近似した折点を示す補間ノードに関する補間ノードデータと、前記補間ノードを連結する補間リンクに関する補間リンクデータとから成る第1地図データと、
道路の交差点または行止まりを示すノードに関するノードデータと、前記ノードを連結するリンクに関するリンクデータとから成る第2地図データとを含む地図データ記憶媒体と、
(b)前記地図データ記憶媒体の第2地図データに基づき経路探索を行う経路探索手段と、
(c)前記経路探索手段が第2地図データに基づいて探索した経路を、前記地図データ記憶媒体の第1地図データに基づいて地図上に表示する表示手段とを備え、
前記地図データ記憶媒体が記憶する第2地図データのリンクデータには、リンクに対応する道路の属性および経路コストに関するデータが含まれていることを特徴とする地図データ記憶媒体を用いた経路探索装置である。」と訂正する。
2.訂正の目的の適否、新規事項の有無及び拡張・変更の存否
(1)訂正Aについて
訂正Aは、請求項1に記載の事項を訂正前の請求項1に記載の事項に訂正前の請求項2に記載の事項を組み合わせたものとし、請求項2に記載の事項を訂正前の請求項3に記載の事項とし、請求項3に記載の事項を訂正前の請求項1に記載の事項に訂正前の請求項4に記載の事項を組み合わせたものとし、請求項4に記載の事項を訂正前の請求項1に記載の事項に訂正前の請求項2に記載の事項及び訂正前の請求項4に記載の事項を組み合わせたものとするのであるから、特許請求の範囲の減縮に相当するものである。
また、この訂正Aは訂正前の明細書に記載された事項に基づくものである。
さらに、訂正後の明細書の請求項1に係る発明においても、訂正前の明細書の請求項1に係る発明が解決しようとする、訂正前の明細書における段落【0005】乃至【0007】に記載の技術的課題と同じ技術的課題を解決するものであり、訂正前の明細書の請求項1に係る発明と訂正後の明細書の請求項1に係る発明とは技術思想が異なるものとはいえないのであるから、訂正Aは特許請求の範囲を実質上変更するものではない。また、訂正Aは特許請求の範囲を実質的に拡張するものでもない。
(2)訂正Bについて
訂正Bは、前記特許請求の範囲の訂正(訂正A)に合わせて発明の詳細な説明の対応箇所を訂正するものであり、明りょうでない記載の釈明に相当するものである。
そして、訂正Aと同じく、訂正Bは訂正前の明細書に記載された事項に基づくものであり、また、特許請求の範囲を実質上拡張又は変更するものではない。
3.むすび
以上のとおりであるから、前記訂正(訂正A及びB)は、特許法等の一部を改正する法律(平成6年法律第116号。以下「平成6年改正法」という。)附則第6条第1項の規定によりなお従前の例によるとされる、特許法第120条の4第3項において準用する平成6年改正法による改正前の特許法第126条第1項ただし書き、第2項及び第3項の規定に適合するので、当該訂正を認める。

【3】特許異議の申立てについての判断(取消理由についての判断)
1.本件発明
本件請求項1乃至6に係る発明は、訂正された明細書及び図面の記載からみて、特許請求の範囲の請求項1乃至6に記載された次の事項によって特定されるとおりのものである。
【請求項1】 2点間の経路を地図データに基づいて経路探索を行う経路探索装置において、
(a)少なくとも道路の交差点または行止まりを示すノードに関するノードデータと、前記ノードを連結するリンクに関するリンクデータと、道路の形状を折線近似した折点を示す補間ノードに関する補間ノードデータと、前記補間ノードを連結する補間リンクに関する補間リンクデータとから成る第1地図データと、
道路の交差点または行止まりを示すノードに関するノードデータと、前記ノードを連結するリンクに関するリンクデータとから成る第2地図データとを含む地図データ記憶媒体と、
(b)前記地図データ記憶媒体の第2地図データに基づき経路探索を行う経路探索手段と、
(c)前記経路探索手段が第2地図データに基づいて探索した経路を、前記地図データ記憶媒体の第1地図データに基づいて地図上に表示する表示手段とを備えることを特徴とする地図データ記憶媒体を用いた経路探索装置。
【請求項2】 前記地図データ記憶媒体の第1地図データに基づいて地図を表示する表示手段を備えることを特徴とする請求項1記載の地図データ記憶媒体を用いた経路探索装置。
【請求項3】 2点間の経路を地図データに基づいて経路探索を行う経路探索装置において、
(a)少なくとも道路の交差点または行止まりを示すノードに関するノードデータと、前記ノードを連結するリンクに関するリンクデータと、道路の形状を折線近似した折点を示す補間ノードに関する補間ノードデータと、前記補間ノードを連結する補間リンクに関する補間リンクデータとから成る第1地図データと、
道路の交差点または行止まりを示すノードに関するノードデータと、前記ノードを連結するリンクに関するリンクデータとから成る第2地図データとを含む地図データ記憶媒体と、
(b)前記地図データ記憶媒体の第2地図データに基づき経路探索を行う経路探索手段とを備え、
前記地図データ記憶媒体が記憶する第2地図データのリンクデータには、リンクに対応する道路の属性および経路コストに関するデータが含まれていることを特徴とする地図データ記憶媒体を用いた経路探索装置。
【請求項4】 2点間の経路を地図データに基づいて経路探索を行う経路探索装置において、
(a)少なくとも道路の交差点または行止まりを示すノードに関するノードデータと、前記ノードを連結するリンクに関するリンクデータと、道路の形状を折線近似した折点を示す補間ノードに関する補間ノードデータと、前記補間ノードを連結する補間リンクに関する補間リンクデータとから成る第1地図データと、
道路の交差点または行止まりを示すノードに関するノードデータと、前記ノードを連結するリンクに関するリンクデータとから成る第2地図データとを含む地図データ記憶媒体と、
(b)前記地図データ記憶媒体の第2地図データに基づき経路探索を行う経路探索手段と、
(c)前記経路探索手段が第2地図データに基づいて探索した経路を、前記地図データ記憶媒体の第1地図データに基づいて地図上に表示する表示手段とを備え、
前記地図データ記憶媒体が記憶する第2地図データのリンクデータには、リンクに対応する道路の属性および経路コストに関するデータが含まれていることを特徴とする地図データ記憶媒体を用いた経路探索装置。
【請求項5】 (a)地図データ記憶媒体であって、
複数種類の道路のうちから予め定められた選択規則に従って選別された道路の接続関係を表す第1道路データと、
選別された道路が選別によって寸断されることがないように、前記複数種類の道路のうちから選別された道路の接続関係を表す第2道路データとを含んで構成される地図データを記憶する地図データ記憶媒体と、
(b)地図データ記憶媒体に記憶されている地図データに基づいて、所定の地域の地図画面を表示する表示手段とを備えることを特徴とする地図データ記憶媒体を用いた表示装置。
【請求項6】 指定された2地点間の経路を、記憶されている地図データに基づいて経路探索を行う経路探索装置において、
(a)地図データ記憶媒体であって、
複数種類の道路のうちから予め定められた選択規則に従って選別された道路の接続関係を表す第1道路データと、
選別された道路が選別によって寸断されることがないように、前記複数種類の道路のうちから選別された道路の接続関係を表す第2道路データとを含んで構成される地図データを記憶する地図データ記憶媒体と、
(b)前記地図データ記憶媒体から地図データを読出し、読出した地図デー夕に基づいて前記2地点間の経路探索を行う探索手段と、
(c)前記地図データ記憶媒体に記憶されている地図データに基づいて、地図画面を表示し、その地図画面上に前記探索手段が探索した経路を表示する表示手段とを備えることを特徴とする地図データ記憶媒体を用いた経路探索装置。
2.引用刊行物
当審が通知した取消理由に引用した特開平5-165406号公報(以下、「引用例1」という。)には、「デジタル地図データとしては、図3に示すような実際の道路形状を、図4に示すように線分によって折線近似したときの各線分の端点および接続点からなるノードNの位置およびノード間の接続状態に関するデータからなっている。 図4からもわかるように、道路のカーブ部分ではその曲率に応じて短い線分によって細かくデジタル化されることになる。」(2頁左欄29行乃至36行)、「従来、デジタル地図データにもとづいて経路探索を行わせるには、例えばDijkstra法などの公知のアルゴリズムにしたがって出発点から目的地に到るまでの最短の経路探索を行わせる」(2頁左欄37行乃至40行)、「デジタル地図データからその道路地図上における各道路端点および各交差点のノードなどの経路探索のために必要最小限となるノードに関するデータのみを抽出して、各道路端点および各交差点の接続間を結んだ経路用地図データを新たに作成したうえで、その作成された経路用地図データにしたがって経路探索を行わせるようにしている。」(2頁右欄15行乃至21行)、「予めデジタル地図データによる道路地図情報が記憶されている地図情報記憶媒体5と、その記憶媒体5から必要なエリアの道路地図情報を選択的に読み出す記憶媒体再生装置6と、その読み出された道路地図情報にもとづいて所定の道路地図を画面に写し出すとともに、その画面に写し出された道路地図上に、車両の現在位置を、必要に応じて走行軌跡および現在位置における車両の進行方向などとともに、車両の走行にしたがって更新的に表示させる表示装置7」(2頁右欄37行乃至46行)、「本発明はこのような車両走行案内装置にあって、信号処理装置3において、デジタル地図データにもとづいて、画面に写し出される道路地図上に設定された出発点から目的地に到るまでの経路を探索して、所要距離や一方通行などの道路情報を加味した最適経路の決定を行い、例えば画面に写し出される道路地図上における最適経路を特別な色で示すなどして、その最適経路上に車両の現在位置が更新表示されていくように車両の走行案内を行わせることができるようにしている。 その際、特に本発明では、図5に示すように、道路地図上に設定された出発点Sから目的地Oに到るまでの経路を探索する場合、交差点I1,I2,I3,...,Inの各間におけるノードNを何ら考慮することなく、経路上にある交差点I1,I2,I3,…,Inに対応するノードのみを次々とたどっていけば経路探索を行わせることができることに着目し、信号処理装置3において、地図情報記憶媒体5から読み出されたデジタル地図データからその道路地図上における各道路端点および各交差点のノードに関するデータのみを抽出して、各道路端点および各交差点の接続間を結んだ経路用地図データを新たに作成したうえで、その作成された経路用地図データにしたがって経路探索を行わせるようにしている。」(3頁左欄20行乃至42行)及び「以上、本発明による車両走行案内装置にあっては、デジタル地図データからその道路地図上における各道路端点および各交差点のノードに関するデータのみを抽出して、各道路端点および各交差点の接続間を結んだ経路用地図データを新たに作成したうえで、その各道路端点および各交差点の接続関係が何ら変化することなくデータ量だけが有効に軽減された経路用地図データをもって、出発点から目的地に到るまでの経路上にある交差点のノードを次々とたどっていくことにより、ノード追跡のための処理の軽減化を有効に図りながら経路探索を正確にかつ迅速に行わせることができるという利点を有している。」(3頁右欄12行乃至23行)との記載並びに図1乃至図7の記載がされている。
ここで、デジタル地図データの「図4に示すように線分によって接線近似したときの各線分の端点及び接続点からなるノードNの位置およびノード間の接続状態に関するデータ」(2頁左欄30行乃至33行)において、「道路地図上における各道路端点及び各交差点のノードなどの経路探索のために必要最小限となるノードに関するデータ」(2頁右欄16行乃至17行)については「少なくとも道路の交差点または行止まりを示すノードに関するノードデータ」といえ、これ以外のノードに関するデータは「道路の形状を折線近似した折点を示す補間ノードに関する補間ノードデータ」といえる。 また、「各道路端点および各交差点の接続点間を結んだ経路用地図データ」(2頁右欄18行乃至19行)については、ダイクストラ法などの公知のアルゴリズムにより経路探索を行う場合にリンクのデータを用いることが通常行われている(例えば、後記の引用例2等を参照。)のであるから、前記ノードデータのみならず、「ノードを連結するリンクに関するリンクデータ」を有しているものと認められる。 そして、経路用地図データはデジタル地図データから作成されているのであるから、デジタル地図データの「ノード間の接続状態に関するデータ」については、「補間ノードを連結する補間リンクに関する補間リンクデータ」を有しているといえると共に、ノード間に補間ノードを有さない場合の「ノードを連結するリンクに関するリンクデータ」を有しているといえる。
よって、これらの記載によれば、引用例1には「2点間の経路(出発点から目的地に到るまでの経路)を地図データに基づいて経路探索を行う車両走行案内装置において、
少なくとも道路の交差点または行止まりを示すノードに関するノードデータと、前記ノードを連結するリンクに関するリンクデータと、道路の形状を折線近似した折点を示す補間ノードに関する補間ノードデータと、前記補間ノードを連結する補間リンクに関する補間リンクデータとから成るデジタル地図データを含む地図情報記憶媒体と、
前記地図情報記憶媒体のデジタル地図データから、道路の交差点または行止まりを示すノードに関するノードデータと、前記ノードを連結するリンクに関するリンクデータとから成る経路用地図データを作成し、該経路用地図データに基づき経路探索を行う経路探索手段と、
前記経路探索手段が経路用地図データに基づいて探索した経路を地図上に表示する表示手段と、
前記地図情報記憶媒体のデジタル地図データに基づいて地図を表示する表示手段とを備えた地図情報記憶媒体を用いた車両走行案内装置。」(以下、「引用発明1」という。)が開示されているものと認められる。
同じく、当審が通知した取消理由に引用した特開平6-288782号公報(以下、「引用例2」という。)には、「本発明は、指定された道路地図上の2点間を走行する場合の最適経路を計算する機能を備えた経路探索装置に関するものである。」(2頁右欄4行乃至6行)、「事前に装填されている地図専用ディスクD1から車両現在地に対応する表示用道路地図データを読み出し、コントローラ7へ出力する。コントローラ7は、ロケータ5で算出された現在地データと、メモリドライブ8から与えられる表示用道路地図データとを表示装置10へ与え、地図とその地図上における車両現在地マークとを生成させ、表示させる。」(3頁右欄34行乃至41行)、「また、メモリドライブ8は、コントローラ7から与えられる制御信号に応答して、事前に装填されている経路計算ディスクD2から経路計算のための経路計算用リンクデータを読み出し、コントローラ7へ出力する。コントローラ7は、現在地から目的地までの最適経路の計算をし、表示地図上の座標を求め、最適経路を表示させる。 ここに、経路計算用リンクデータは、道路地図(高速自動車国道、自動車専用道路、国道、都道府県道、指定都市の市道、その他の生活道路を含む。)をメッシュ状に分割し、各メッシュ単位でノードとリンクとの組み合わせからなるデータを記憶している。地図データベースの特性上、幹線道路のうち国道以上の道路については全国的に閉じたネットワークが形成されている。 ここに、ノードとは、一般に、道路の交差点、道路の折曲点、メッシュの境界、行き止まり点などを特定するための座標点のことである。 各ノードをつないだものがリンクである。リンクデータはリンク番号、リンクの始点ノード及び終点ノードのアドレス、リンクの距離、リンクを通過する方向、その方向における所要時間、道路の種類若しくは種別、道路幅、一方通行、右折禁止、左折禁止、有料道路などのデータ等を含む。 なお、表示用道路地図データは、2500分の1の地図データベースから作成されたもので、道路、地名、有名施設、鉄道、川等を特定する地図データ等で構成されている。」(3頁右欄42行乃至4頁左欄18行)及び「そして、この経路計算領域の中で計算開始リンクと計算終了リンクとの間の最適経路を計算する(図3、ステップS5)。すなわち、最適経路計算処理部は、経路計算ディスクD2から読み出された経路計算用リンクデータに基づき、ダイクストラ法等(実施例では、ダイクストラ法の一種であるポテンシャル法を採用している)により現在地から目的地までの最適経路の計算を行う。このポテンシャル法は、目的地又は現在地に最も近いリンクを計算開始リンクとし、現在地又は目的地に最も近いリンクを計算終了リンクとし、計算開始リンクから計算終了リンクに至るリンクコストを順次加算してリンクのツリーを構成していき、計算終了リンクに到達する最もリンクコストの少ない経路のみを選択する方法である。ここでリンクコストを見積もるときに考慮すべき事項(評価関数)として、走行距離、走行時間、高速道路の利用の有無、右折左折回数、幹線道路の走行確率、事故多発地帯回避、その他運転者の好みに応じて設定された事項がある。 得られた最適経路は、リンク?座標変換テーブルを参照して、該当する座標列に変換される(ステップS6)。そして、表示要求があれば(ステップS7)、表示しようとする道路地図の範囲に含まれる最適経路を構成する座標列が、道路地図とともに読み出され、表示装置12に表示される(ステップS8)。表示は、例えば座標間をドット、太線、破線等で結ぶことにより行われる。」(5頁左欄9行乃至34行)との記載並びに図1乃至図3の記載がされている。
同じく、当審が通知した取消理由に引用した特開平2-172000号公報(以下、「引用例3」という。)には、「第1発明は、第1図(a)に示すように、 ・・・(中略)・・・ 経路データ記憶手段は、ノード及び枝で構成される、例えば、道路地図、回路等の最短経路探索の対象となる経路データを記憶する手段である。 ・・・(中略)・・・ 双方向探索手段は、位置入力手段により入力された探索開始位置及び探索終了位置の双方向から経路データを用いて順次ノード又は枝を検索して最短経路を探索する手段である。最短経路は経路長、所要時間、費用等やこれらの量を総合評価した評価値が最小となる経路として定義される。 ・・・(中略)・・・ 表示手段は、その最短経路を表示する手段である。例えば、道路地図を表示すると共に、その道路地図上に探索開始位置である現在位置と探索終了位置である目的位置と、その両位置を結ぶ最短経路とを表示する手段である。」(3頁右上欄11行乃至右下欄8行)、「経路データ記憶手段はノード及び枝の情報及び枝の優先度を示す等級データを記憶するものである。 又、縮退探索手段は、順次探索される探索ノード又は探索枝を、その等級データにより制限する手段である。この等級は、例えば、道幅や車線数及び高速道路、国道、県市町村道などの道路等級等で区別されるような枝の優先度を示すものである。したがって、選択枝の等級を所定の条件で制限するということは、例えば、広い国道に沿って1つの経路が探索されている場合に、その国道に接続されている狭い脇道等は探索の対象から除外され、その脇道に接続される枝はそれ以上探索されないことを意味しており、探索速度が向上する。」(4頁左上欄20行乃至右上欄13行)、「第2図は本発明の実施例に係る車載ナビゲーション装置10の構成を示すものである。 ・・・(中略)・・・ 図において、コンピュータ20はデータ記憶媒体21をアクセスして、最短経路探索演算等を実行する装置である。 ・・・(中略)・・・ 記憶媒体21は、フロピィディスク、ハードディスク若しくはRAMディスク等で構成される。その記憶媒体21には地図データベースと探索プログラムが記憶され、探索過程データや探索結果データを記憶する探索データファイルが形成されている。」(5頁右上欄5行乃至18行)、「地図はノードを中心に構成しても各(リンク)を中心に構成してもよい。ノードを中心として構成される地図データベースは次の情報で構成されている。 ・・・(中略)・・・ この記憶された地図データベースは地理的に所与の領域を移動するときに使用される。」(6頁左上欄15行乃至右上欄11行)、「車両が、ある地点からある地点へ移動する時、コンピュータ20が適切な地図を呼び出し、CRTディスプレイ41に表示することができる。推測航法を備えた車載ナビゲーション装置では車両の移動軌跡を推測でき、これを表示中の地図に重ね書きすることができる。又、後に述べる経路探索アルゴリズムによって得られる最短経路を表示中の地図に重ね書きすることができる。」(6頁右上欄12行乃至19行)、「経路探索が終了した時点の探索結果データはトランジェントな探索データファイルとして記憶媒体21に記憶される。そして、探索データファイルは探索枝を展開するノードファイルとで構成される。」(6頁左下欄3行乃至5行)、「メインプログラムはコンピュータによって処理される全ての情報に応答して、必要なデータを計算しフォーマット化する。例えば、CRTディスプレイ41に表示され選択される地図のデータ、現在位置及び目的位置のコマンドデータ、最短経路探索プログラムに与える現在位置と目的位置を示す地点コードと探索モード等を計算し処理する。」(7頁左上欄20行乃至右上欄6行)、「縮退探索は、探索の際、探索枝を順次道路等級の等しいか、又は高い方へ上げながら、優先順位の低い道路枝をカットし、縮退した道路網により探索を行うものである。これにより、例えば、道路幅の広い国道等に沿って探索が実行されている時、その国道に接続される道幅の狭い脇道等へ探索枝が伸びることが防止され、効率のよい探索が行われる。道路等級は任意に設定でき、例えば市町村道、県道、国道、高速道路の順に等級を設定することでも良い。この他の、道路巾の大小、設計交通容量、設計速度、有料道路と無料道路の違いによって等級を設定することもできる。道路等級により縮退を行うと、等級が上がるに従いネットワークが粗となり、経路の跡切れを生じる場合があるので、跡切れを避けるため、前の選択枝のnランク下位の等級まで接続を認めるようにする。」(8頁左下欄9行乃至右下欄4行)及び「又、第3発明は、双方向探索過程において探索される探索ノード又は探索枝を、枝の優先度を示す等級データに基づいて制限しているので、経路探索が等級の高い枝に接続された等級の低い枝への経路探索が防止されるため、極めて効率の高い探索が可能となり最短経路探索時間が短縮される。」(14頁右上欄10行乃至17行)との記載並びに第1図(a)乃至第2図の記載によれば、引用例3には「記憶媒体(経路データ記憶手段)であって、
道路の接続関係を表す道路データを含んで構成される地図データベース(経路データ)を記憶する記憶媒体と、
記憶媒体に記憶されている地図データベースに基づいて、所定の地域の地図画面を表示する表示手段とを備える記憶媒体を用いた表示装置。」(以下、「引用発明2」という。)及び「指定された2地点間の経路(探索開始位置である現在位置と探索終了位置である目的位置とを結ぶ経路)を、記憶されている地図データベース(経路データ)に基づいて経路探索を行う経路探索装置において、
記憶媒体(経路データ記憶手段)であって、
道路の接続関係を表す道路データを含んで構成される地図データベースを記憶する記憶媒体と、
前記記憶媒体から地図データベースを読出し、読出した地図データベースに基づいて、複数種類の道路に予め定められた選択規則に従って設定された等級により、探索枝を順次道路等級の等しいか、又は高い方へ上げながら、優先順位の低い探索枝をカットすると共に、道路が寸断されることがないように下位の等級の探索枝の接続を認めるようにして、前記2地点間の経路探索を行う探索手段と、
前記記憶媒体に記憶されている地図データベースに基づいて、地図画面を表示し、その地図画面上に前記探索手段が探索した経路を表示する表示手段とを備えることを特徴とする記憶媒体を用いた経路探索装置。」(以下、「引用発明3」という。)が開示されているものと認められる。
3.対比・判断
(1)請求項1に係る発明について
本件請求項1に係る発明と引用発明1とを対比すると、引用発明1における「車両走行案内装置」、「デジタル地図データ」、「地図情報記憶媒体」及び「経路用地図データ」は、それぞれ本件請求項1に係る発明の「経路探索装置」、「第1地図データ」、「地図データ記憶媒体」及び「第2地図データ」に相当するものといえるから、両者は、「2点間の経路を地図データに基づいて経路探索を行う経路探索装置において、
少なくとも道路の交差点または行止まりを示すノードに関するノードデータと、前記ノードを連結するリンクに関するリンクデータと、道路の形状を折線近似した折点を示す補間ノードに関する補間ノードデータと、前記補間ノードを連結する補間リンクに関する補間リンクデータとから成る第1地図データを含む地図データ記憶媒体と、
道路の交差点または行止まりを示すノードに関するノードデータと、前記ノードを連結するリンクに関するリンクデータとから成る第2地図データに基づき経路探索を行う経路探索手段と、
前記経路探索手段が第2地図データに基づいて探索した経路を地図上に表示する表示手段とを備えることを特徴とする地図データ記憶媒体を用いた経路探索装置。」である点で一致し、次の点で相違するものと認められる。
(相違点1)第2地図データが、本件請求項1に係る発明では、地図データ記憶媒体に含まれているのに対して、引用発明1では、地図データ記憶媒体に含まれている第1地図データから作成される点。
(相違点2)探索した経路を、本件請求項1に係る発明では、地図データ記憶媒体の第1地図データに基づいて地図上に表示するものであるのに対して、引用発明1では、第1地図データに基づいて地図上に表示するものであるのか否か明らかでない点。
そこで、前記相違点について検討する。
(相違点1について)
地図データ記憶媒体を用いた経路探索装置において、経路探索用の第2地図データを表示用の第1の地図データと同じく予め地図データ記憶媒体に含むことは周知(必要であれば、引用例2、特開平4-321090号公報、特開平6-119562号公報及び特開平4-280287号公報を参照。)であり、また、地図データ記憶媒体に表示用の第1の地図データと共に経路探索用の第2地図データを含むことも周知(必要であれば、特開平4-321090号公報、特開平6-119562号公報及び特開平4-280287号公報を参照。)であるから、第2地図データを第1地図データから作成することに代え、予め第2地図データを第1地図データと共に地図データ記憶媒体に含むようにすること、すなわち、本件請求項1に係る発明の前記相違点1に係る構成とすることは当業者が容易に想到し得たものと認められる。
(相違点2について)
引用発明1において、探索した経路を地図上に表示するのに、第1地図データに基づいて表示するか第2地図データに基づいて表示するかの2通りが考えられるが、地図は第1地図データに基づき表示されていることから、経路を第1地図データに基づき地図上に表示した方が経路を第2地図データに基づき地図上に表示した場合に比べて経路と地図の整合性がとれて見やすいことは当業者であれば容易に認識し得るものと認められる。
してみれば、探索した経路を第1地図データに基づいて地図上に表示すること、すなわち、本件請求項1に係る発明の前記相違点2に係る構成は当業者が容易に想到し得たものと認められる。
そして、本件請求項1に係る発明が奏する効果は、引用例1に記載された事項及び周知の事項から当業者が予測し得る範囲のものと認められる。
なお、特許権者は平成13年1月29日付け特許異議意見書により、「本件請求項1に係る発明は、記憶媒体に経路探索専用の地図データを準備しておくことにより、(a)経路探索用の地図を作成する時間は必要なくなる。また、(b)経路探索用の地図データだけを取り込むので、一度に広いエリアをカバーすることができる。その結果、経路探索にかかる時間が見かけ上、短縮される。」(5頁5行乃至9行)旨主張しているが、(a)については前記周知の事項によれば経路探索用の第2地図データを地図データ記憶媒体に有しており、経路探索用の地図を作成する必要はないのであるから、当業者が予測し得る効果と認められる。また、(b)については訂正された明細書の記載に基づくものではなく、当該主張は採用することができない。
よって、本件請求項1に係る発明は、引用例1に記載された事項及び周知の事項に基づいて当業者が容易に発明することができたものである。
(2)請求項2に係る発明について
本件請求項2に係る発明と引用発明1とを対比すると、引用発明1における「車両走行案内装置」、「デジタル地図データ」、「地図情報記憶媒体」及び「経路用地図データ」は、それぞれ本件請求項1に係る発明の「経路探索装置」、「第1地図データ」、「地図データ記憶媒体」及び「第2地図データ」に相当するものといえるから、両者は、「2点間の経路を地図データに基づいて経路探索を行う経路探索装置において、
少なくとも道路の交差点または行止まりを示すノードに関するノードデータと、前記ノードを連結するリンクに関するリンクデータと、道路の形状を折線近似した折点を示す補間ノードに関する補間ノードデータと、前記補間ノードを連結する補間リンクに関する補間リンクデータとから成る第1地図データを含む地図データ記憶媒体と、
道路の交差点または行止まりを示すノードに関するノードデータと、前記ノードを連結するリンクに関するリンクデータとから成る第2地図データに基づき経路探索を行う経路探索手段と、
前記経路探索手段が第2地図データに基づいて探索した経路を地図上に表示する表示手段と、
前記地図データ記憶媒体の第1地図データに基づいて地図を表示する表示手段とを備えた地図データ記憶媒体を用いた経路探索装置。」である点で一致し、本件請求項1に係る発明についての検討で示した前記相違点1及び2と同じ相違点で相違するものと認められる。
そして、本件請求項2に係る発明の前記相違点1及び2と同じ相違点に係る構成については、本件請求項1に係る発明についての検討で述べたとおり当業者が容易に想到し得たものと認められ、本件請求項2に係る発明が奏する効果も引用例1に記載された事項及び周知の事項から当業者が予測し得る範囲のものと認められる。
よって、本件請求項2に係る発明は、引用例1に記載された事項及び周知の事項に基づいて当業者が容易に発明することができたものである。
(3)請求項3に係る発明について
本件請求項3に係る発明と引用発明1とを対比すると、引用発明1における「車両走行案内装置」、「デジタル地図データ」、「地図情報記憶媒体」及び「経路用地図データ」は、それぞれ本件請求項1に係る発明の「経路探索装置」、「第1地図データ」、「地図データ記憶媒体」及び「第2地図データ」に相当するものといえるから、両者は、「2点間の経路を地図データに基づいて経路探索を行う経路探索装置において、
少なくとも道路の交差点または行止まりを示すノードに関するノードデータと、前記ノードを連結するリンクに関するリンクデータと、道路の形状を折線近似した折点を示す補間ノードに関する補間ノードデータと、前記補間ノードを連結する補間リンクに関する補間リンクデータとから成る第1地図データを含む地図データ記憶媒体と、
道路の交差点または行止まりを示すノードに関するノードデータと、前記ノードを連結するリンクに関するリンクデータとから成る第2地図データに基づき経路探索を行う経路探索手段とを備えた地図データ記憶媒体を用いた経路探索装置。」である点で一致し、本件請求項1に係る発明についての検討で示した前記相違点1及び2と同じ相違点に加え、次の点で相違するものと認められる。
(相違点3)
第2地図データのリンクデータには、本件請求項3に係る発明では、リンクに対応する道路の属性及び経路コストに関するデータが含まれているのに対して、引用発明1では、リンクに対応する道路の属性及び経路コストに関するデータが含まれているのか否か明らかでない点。
本件請求項3に係る発明の前記相違点1及び2と同じ相違点に係る構成については、本件請求項1に係る発明についての検討で述べたとおり当業者が容易に想到し得たものと認められ、以下、相違点3について検討する。
地図データ記憶媒体を用いた経路探索装置において、経路探索用の地図データに、リンクに対応する道路の属性および経路コストに関するデータが含まれることは引用例2に記載されているものと認められ、引用発明1及び引用例2に記載の事項は共に、ダイクストラ法などの公知のアルゴリズムにより経路探索を行う技術分野において共通するものであるから、引用発明1に前記引用例2に記載の事項を適用し、引用発明1における第2地図データのリンクデータに、リンクに対応する道路の属性および経路コストに関するデータが含まれるようにすること、すなわち、本件請求項3に係る発明の前記相違点3に係る構成は当業者が容易に想到し得たものと認められる。
なお、特許権者は平成13年1月29日付け特許異議意見書により、「引用例2に開示されている経路探索装置は、段落[0017]に示されるデータから運転者の好みなどによって、コストを決定するものである。すなわち、記憶媒体に記憶されている探索用データ自体には実質的にはコストデータは含まれておらず、一定のルール(運転者の好み)に従ってコストを求める構成である。したがって、引用例2に経路コストに関するデータが予め地図データに含まれていることが記載されているという認定には承服できない。」(7頁4行乃至10行)旨を主張している。
しかしながら、本件の訂正された明細書には、「始点から探索点までの経路長や自動車が移動する際の所要時間などを示す経路コスト」(8頁23行乃至24行)及び「この経路コストには、構成リンクLaに対応する道路の区間の実距離、またはその道路の区間を実際に自動車が通過する際の推定の所要時間が登録される。」(18頁15行乃至17行)との記載がされており、これらの記載によれば本件請求項3に係る発明は経路コストを経路の距離または所要時間とすることを含むものと認められるところ、引用例2には、リンクコストを見積もるときに考慮すべき事項として走行距離または走行時間があることが記載されている(5頁左欄22行乃至26行)と共に、該走行距離又は走行時間に関するリンクの距離やリンクを通過する方向における所要時間を経路計算用リンクデータとして記憶媒体である経路計算ディスクD2に記憶することが記載されている(3頁右欄42行乃至4頁左欄14行)のであるから、経路コストに関するデータが予め経路探索用の地図データに含まれていることが記載されているものといえる。また、「経路コストに関するデータ」には、経路コスト自体のデータのみでなく、経路コストを算出するのに用いるデータも含まれるものと解釈できることからも、引用例2には経路コストに関するデータが予め経路探索用の地図データに含まれていることが記載されているものといえ、当該主張は採用することができない。
そして、本件請求項3に係る発明が奏する効果も引用例1及び2に記載された事項並びに周知の事項から当業者が予測し得る範囲のものと認められる。
よって、本件請求項3に係る発明は、引用例1及び2に記載された事項並びに周知の事項に基づいて当業者が容易に発明することができたものである。
(4)請求項4に係る発明について
本件請求項4に係る発明と引用発明1とを対比すると、引用発明1における「車両走行案内装置」、「デジタル地図データ」、「地図情報記憶媒体」及び「経路用地図データ」は、それぞれ本件請求項1に係る発明の「経路探索装置」、「第1地図データ」、「地図データ記憶媒体」及び「第2地図データ」に相当するものといえるから、両者は、「2点間の経路を地図データに基づいて経路探索を行う経路探索装置において、
少なくとも道路の交差点または行止まりを示すノードに関するノードデータと、前記ノードを連結するリンクに関するリンクデータと、道路の形状を折線近似した折点を示す補間ノードに関する補間ノードデータと、前記補間ノードを連結する補間リンクに関する補間リンクデータとから成る第1地図データを含む地図データ記憶媒体と、
道路の交差点または行止まりを示すノードに関するノードデータと、前記ノードを連結するリンクに関するリンクデータとから成る第2地図データに基づき経路探索を行う経路探索手段と、
前記経路探索手段が第2地図データに基づいて探索した経路を地図上に表示する表示手段とを備えた地図データ記憶媒体を用いた経路探索装置。」である点で一致し、本件請求項1に係る発明についての検討で示した前記相違点1及び2並びに本件請求項3に係る発明についての検討で示した前記相違点3と同じ相違点で相違するものと認められる。
そして、本件請求項4に係る発明の前記相違点1及び2と同じ相違点に係る構成については、本件請求項1に係る発明についての検討で述べたとおり当業者が容易に想到し得たものと認められると共に、本件請求項4に係る発明の前記相違点3と同じ相違点に係る構成については、本件請求項3に係る発明についての検討で述べたとおり当業者が容易に想到し得たものと認められ、本件請求項4に係る発明が奏する効果も引用例1及び2に記載された事項並びに周知の事項から当業者が予測し得る範囲のものと認められる。
よって、本件請求項4に係る発明は、引用例1及び2に記載された事項並びに周知の事項に基づいて当業者が容易に発明することができたものである。
(5)請求項5に係る発明について
本件請求項5に係る発明と引用発明2とを対比すると、引用発明2における「記憶媒体(経路データ記憶手段)」及び「地図データベース(経路データ)」は、それぞれ本件請求項5に係る発明の「地図データ記憶媒体」及び「地図データ」に相当するものといえるから、両者は、「地図データ記憶媒体であって、
道路の接続関係を表す道路データとを含んで構成される地図データを記憶する地図データ記憶媒体と、
地図データ記憶媒体に記憶されている地図データに基づいて、所定の地域の地図画面を表示する表示手段とを備える地図データ記憶媒体を用いた表示装置。」である点で一致し、次の点で相違するものと認められる。
(相違点4)複数種類の道路のうちから予め定められた選択規則に従って選別された道路の接続関係を表す第1道路データと、選別された道路が選別によって寸断されることがないように、前記複数種類の道路のうちから選別された道路の接続関係を表す第2道路データとを含んで構成される地図データが、本件請求項5に係る発明では、地図データ記憶媒体に記憶されているのに対して、引用発明2では、そのような地図データが地図データ記憶媒体に記憶されていない点。
そこで、前記相違点4について検討すると、地図データ記憶媒体を用いた表示装置において、複数種類の道路のうちから予め定められた選択規則に従って選別された道路の接続関係を表す第1道路データと、選別された道路が選別によって寸断されることがないように、前記複数種類の道路のうちから選別された道路の接続関係を表す第2道路データとを含んで構成される地図データを地図データ記憶媒体に記憶することは周知(必要であれば、特開平5-232875号公報、特開平4-365088号公報及び特開平6-119562号公報を参照。)であり、これを引用発明2に採用することができないという事情は認められないのであるから、複数種類の道路のうちから予め定められた選択規則に従って選別された道路の接続関係を表す第1道路データと、選別された道路が選別によって寸断されることがないように、前記複数種類の道路のうちから選別された道路の接続関係を表す第2道路データとを含んで構成される地図データを地図データ記憶媒体に記憶すること、すなわち、本願請求項5に係る発明の前記相違点4に係る構成は当業者が容易に想到し得たものと認められる。
なお、特許権者は平成13年1月29日付け特許異議意見書により、「本件の第2道路データは、選別された道路の接続関係を示すものであって、第1道路データの下層に相当するデータとは異なるものである。つまり、第1道路データが国道および高速道路からなるデータであった場合、本件の第2道路データは選別された国道などを接続する県道や主要地方道の一部からなるデータとなるのであり、県道や主要地方道以上の全ての道路からなるデータとは異なるものである。」(8頁21行乃至26行)旨を主張している。
しかしながら、前記周知の事項の例示文献として挙げた各刊行物(以下、「周知文献」という。)に開示された第2道路データが第1道路データの下層に相当するデータであるとしても、第2道路データにおいて第1道路データに係る道路は寸断されないように接続されている(このことは、前記周知文献において、第1道路データを用いたのでは経路探索できない場合に第2道路データを用いて経路探索することが開示されていることからも理解できる。)のであるから、第2道路データを「選別された道路が選別によって寸断されることがないように、前記複数種類の道路のうちから選別された道路の接続関係を表す第2道路データ」として解釈することができるのであって、当該主張は採用することができない。
そして、本件請求項5に係る発明が奏する効果は、引用例3に記載の事項及び周知の事項から当業者が予測し得る範囲のものである。
よって、本件請求項5に係る発明は、引用例3に記載の事項及び周知の事項に基づき、当業者が容易に発明することができたものと認められる。
(6)請求項6に係る発明について
本件請求項5に係る発明と引用発明3とを対比すると、引用発明3における「地図データベース(経路データ)」及び「記憶媒体(経路データ記憶手段)」及びは、それぞれ本件請求項5に係る発明の「地図データ記憶媒体」及び「地図データ」に相当するものといえるから、両者は、「指定された2地点間の経路を、記憶されている地図データに基づいて経路探索を行う経路探索装置において、
地図データ記憶媒体であって、
道路の接続関係を表す道路データを含んで構成される地図データを記憶する地図データ記憶媒体と、
前記地図データ記憶媒体から地図データを読出し、読出した地図データに基づいて前記2地点間の経路探索を行う探索手段と、
前記地図データ記憶媒体に記憶されている地図データに基づいて、地図画面を表示し、その地図画面上に前記探索手段が探索した経路を表示する表示手段とを備える地図データ記憶媒体を用いた経路探索装置。」である点で一致し、本件請求項5に係る発明についての検討で示した前記相違点4と同じ相違点で相違するものと認められる。
そこで、前記相違点4について検討すると、地図データ記憶媒体を用いた経路探索装置において、複数種類の道路のうちから予め定められた選択規則に従って選別された道路の接続関係を表す第1道路データと、選別された道路が選別によって寸断されることがないように、前記複数種類の道路のうちから選別された道路の接続関係を表す第2道路データとを含んで構成される地図データを地図データ記憶媒体に記憶し、該地図データ記憶手段から読出した地図データに基づいて2地点間の経路探索を行うことは周知(必要であれば、特開平5-232875号公報、特開平4-365088号公報、特開平4-88600号公報及び特開平6-119562号公報を参照。)であり、引用発明3において、2地点間の経路探索を行うにあたり、複数種類の道路に予め定められた選択規則に従って設定された等級により、探索枝を順次道路等級の等しいか、又は高い方へ上げながら、優先順位の低い探索枝をカットすると共に、道路が寸断されることがないように下位の等級の探索枝の接続を認めるようにした(以下、「縮退探索に係る構成」という。)のは、上位の道路データを優先的に経路探索に用いると共に、上位の道路データでは経路探索が不可能な場合に下位の道路データを経路探索に用いることにより、経路探索時間を短縮するためと認められるところ、この点において前記周知の事項は共通するものと認められるのであるから、引用発明3における前記縮退探索に係る構成の代わりに前記周知の事項を採用し、複数種類の道路のうちから予め定められた選択規則に従って選別された道路の接続関係を表す第1道路データと、選別された道路が選別によって寸断されることがないように、前記複数種類の道路のうちから選別された道路の接続関係を表す第2道路データとを含んで構成される地図データを地図データ記憶媒体に記憶すること、すなわち、本願請求項6に係る発明の前記相違点4に係る構成は当業者が容易に想到し得たものと認められる。
そして、本件請求項6に係る発明が奏する効果は、引用例3に記載の事項及び周知の事項から当業者が予測し得る範囲のものである。
よって、本件請求項6に係る発明は、引用例3に記載の事項及び周知の事項に基づき、当業者が容易に発明することができたものと認められる。
4.むすび
以上のとおりであるから、本件請求項1乃至6に係る発明は、特許法第29条第2項の規定により特許を受けることができない。
したがって、本件請求項1乃至6に係る発明についての特許は拒絶の査定をしなければならない特許出願に対してされたものと認める。
よって、特許法等の一部を改正する法律(平成6年法律第116号)附則第9条第4項及び第7項並びに第14条の規定に基づく、特許法等の一部を改正する法律の施行に伴う経過措置を定める政令(平成7年政令第205号)第4条第1項及び第2項の規定により、結論のとおり決定する。
 
発明の名称 (54)【発明の名称】
地図データ記憶媒体を用いた経路探索装置
(57)【特許請求の範囲】
【請求項1】 2点間の経路を地図データに基づいて経路探索を行う経路探索装置において、
(a)少なくとも道路の交差点または行止まりを示すノードに関するノードデータと、前記ノードを連結するリンクに関するリンクデータと、道路の形状を折線近似した折点を示す補間ノードに関する補間ノードデータと、前記補間ノードを連結する補間リンクに関する補間リンクデータとから成る第1地図データと、
道路の交差点または行止まりを示すノードに関するノードデータと、前記ノードを連結するリンクに関するリンクデータとから成る第2地図データとを含む地図データ記憶媒体と、
(b)前記地図データ記憶媒体の第2地図データに基づき経路探索を行う経路探索手段と、
(c)前記経路探索手段が第2地図データに基づいて探索した経路を、前記地図データ記憶媒体の第1地図データに基づいて地図上に表示する表示手段とを備えることを特徴とする地図データ記憶媒体を用いた経路探索装置。
【請求項2】 前記地図データ記憶媒体の第1地図データに基づいて地図を表示する表示手段を備えることを特徴とする請求項1記載の地図データ記憶媒体を用いた経路探索装置。
【請求項3】 2点間の経路を地図データに基づいて経路探索を行う経路探索装置において、
(a)少なくとも道路の交差点または行止まりを示すノードに関するノードデータと、前記ノードを連結するリンクに関するリンクデータと、道路の形状を折線近似した折点を示す補間ノードに関する補間ノードデータと、前記補間ノードを連結する補間リンクに関する補間リンクデータとから成る第1地図データと、
道路の交差点または行止まりを示すノードに関するノードデータと、前記ノードを連結するリンクに関するリンクデータとから成る第2地図データとを含む地図データ記憶媒体と、
(b)前記地図データ記憶媒体の第2地図データに基づき経路探索を行う経路探索手段とを備え、
前記地図データ記憶媒体が記憶する第2地図データのリンクデータには、リンクに対応する道路の属性および経路コストに関するデータが含まれていることを特徴とする地図データ記憶媒体を用いた経路探索装置。
【請求項4】 2点間の経路を地図データに基づいて経路探索を行う経路探索装置において、
(a)少なくとも道路の交差点または行止まりを示すノードに関するノードデータと、前記ノードを連結するリンクに関するリンクデータと、道路の形状を折線近似した折点を示す補間ノードに関する補間ノードデータと、前記補間ノードを連結する補間リンクに関する補間リンクデータとから成る第1地図データと、
道路の交差点または行止まりを示すノードに関するノードデータと、前記ノードを連結するリンクに関するリンクデータとから成る第2地図データとを含む地図データ記憶媒体と、
(b)前記地図データ記憶媒体の第2地図データに基づき経路探索を行う経路探索手段と、
(c)前記経路探索手段が第2地図データに基づいて探索した経路を、前記地図データ記憶媒体の第1地図データに基づいて地図上に表示する表示手段とを備え、
前記地図データ記憶媒体が記憶する第2地図データのリンクデータには、リンクに対応する道路の属性および経路コストに関するデータが含まれていることを特徴とする地図データ記憶媒体を用いた経路探索装置。
【請求項5】 (a)地図データ記憶媒体であって、
複数種類の道路のうちから予め定められた選択規則に従って選別された道路の接続関係を表す第1道路データと、
選別された道路が選別によって寸断されることがないように、前記複数種類の道路のうちから選別された道路の接続関係を表す第2道路データとを含んで構成される地図データを記憶する地図データ記憶媒体と、
(b)地図データ記憶媒体に記憶されている地図データに基づいて、所定の地域の地図画面を表示する表示手段とを備えることを特徴とする地図データ記憶媒体を用いた表示装置。
【請求項6】 指定された2地点間の経路を、記憶されている地図データに基づいて経路探索を行う経路探索装置において、
(a)地図データ記憶媒体であって、
複数種類の道路のうちから予め定められた選択規則に従って選別された道路の接続関係を表す第1道路データと、
選別された道路が選別によって寸断されることがないように、前記複数種類の道路のうちから選別された道路の接続関係を表す第2道路データとを含んで構成される地図データを記憶する地図データ記憶媒体と、
(b)前記地図データ記憶媒体から地図データを読出し、読出した地図データに基づいて前記2地点間の経路探索を行う探索手段と、
(c)前記地図データ記憶媒体に記憶されている地図データに基づいて、地図画面を表示し、その地図画面上に前記探索手段が探索した経路を表示する表示手段とを備えることを特徴とする地図データ記憶媒体を用いた経路探索装置。
【発明の詳細な説明】
【0001】
【産業上の利用分野】
本発明は、地図画面上に自車位置や目的地を表示することができる、いわゆるナビゲーション装置に好適に実施され、目的地や経由地までの経路を探索するためなどに用いられる地図データを記憶する地図データ記憶媒体を用いた経路探索装置に関する。
【0002】
【従来の技術】
ナビゲーション装置は、自動車に搭載され、地図画面上に自車位置を併せて表示し、その表示を自車の走行に伴って更新してゆく装置である。また近年、このナビゲーション装置において、現在位置および目的地または経由地を入力することによって、現在位置からの目的地または経由地までで、たとえば最短経路となる経路が演算されて、推薦経路として表示するようにした経路探索機能が付加されるようになってきている。
【0003】
従来の経路探索に用いられる地図データは、大略的に、道路の曲線形状を折線近似した折点または交差点を示すノードデータと、各ノード間を連結するリンクデータとを含んで構成されている。経路探索の際には、CD-ROMディスクに記憶されている地図データを、順次読出し経路探索が行われる。
【0004】
また前述の地図データを作成する際には、データの情報量の削減などの理由によって、その地図データが網羅する地域の全ての道路を表す親データから、道路の種別や幅員などに基づいて地図データの縮尺や用途に応じて必要な道路に関するデータを選別して、地図データを作成する。
【0005】
【発明が解決しようとする課題】
上述の従来技術では、経路探索に用いる地図データには、道路の接続状態を表す交差点を示すノードデータのほかに、経路探索に必ずしも必要でない道路の曲線形状を表すための折点を示すノードデータが含まれているので、経路探索の処理速度が遅くなる。また、CD-ROMディスクから読出した地図データを一時記憶するためのメモリの記憶容量が増大する。
【0006】
また上述の従来技術では、必要な道路を選別して地図データを形成する際に、道路の幅員などの変化によって道路が途中で途切れることがある。このような道路が途中で途切れた地図データに基づいて経路探索を行うと、道路が途切れている部分では経路探索ができない。また、このような地図データに基づいて地図画面を表示すると、道路が途切れている部分では道路のつながり方が判らず、地図として用いることができない。
【0007】
本発明の目的は、経路探索処理の高速化を図ることができる、または道路の接続関係の完全性が向上された地図データを記憶する地図データ記憶媒体を用いた経路探索装置を提供することである。
【0008】
【課題を解決するための手段】
本発明は、2点間の経路を地図データに基づいて経路探索を行う経路探索装置において、
(a)少なくとも道路の交差点または行止まりを示すノードに関するノードデータと、前記ノードを連結するリンクに関するリンクデータと、道路の形状を折線近似した折点を示す補間ノードに関する補間ノードデータと、前記補間ノードを連結する補間リンクに関する補間リンクデータとから成る第1地図データと、
道路の交差点または行止まりを示すノードに関するノードデータと、前記ノードを連結するリンクに関するリンクデータとから成る第2地図データとを含む地図データ記憶媒体と、
(b)前記地図データ記憶媒体の第2地図データに基づき経路探索を行う経路探索手段と、
(c)前記経路探索手段が第2地図データに基づいて探索した経路を、前記地図データ記憶媒体の第1地図データに基づいて地図上に表示する表示手段とを備えることを特徴とする地図データ記憶媒体を用いた経路探索装置である。
また本発明は、前記地図データ記憶媒体の第1地図データに基づいて地図を表示する表示手段を備えることを特徴とする。
また本発明は、2点間の経路を地図データに基づいて経路探索を行う経路探索装置において、
(a)少なくとも道路の交差点または行止まりを示すノードに関するノードデータと、前記ノードを連結するリンクに関するリンクデータと、道路の形状を折線近似した折点を示す補間ノードに関する補間ノードデータと、前記補間ノードを連結する補間リンクに関する補間リンクデータとから成る第1地図データと、
道路の交差点または行止まりを示すノードに関するノードデータと、前記ノードを連結するリンクに関するリンクデータとから成る第2地図データとを含む地図データ記憶媒体と、
(b)前記地図データ記憶媒体の第2地図データに基づき経路探索を行う経路探索手段とを備え、
前記地図データ記憶媒体が記憶する第2地図データのリンクデータには、リンクに対応する道路の属性および経路コストに関するデータが含まれていることを特徴とする地図データ記憶媒体を用いた経路探索装置である。
また本発明は、2点間の経路を地図データに基づいて経路探索を行う経路探索装置において、
(a)少なくとも道路の交差点または行止まりを示すノードに関するノードデータと、前記ノードを連結するリンクに関するリンクデータと、道路の形状を折線近似した折点を示す補間ノードに関する補間ノードデータと、前記補間ノードを連結する補間リンクに関する補間リンクデータとから成る第1地図データと、
道路の交差点または行止まりを示すノードに関するノードデータと、前記ノードを連結するリンクに関するリンクデータとから成る第2地図データとを含む地図データ記憶媒体と、
(b)前記地図データ記憶媒体の第2地図データに基づき経路探索を行う経路探索手段と、
(c)前記経路探索手段が第2地図データに基づいて探索した経路を、前記地図データ記憶媒体の第1地図データに基づいて地図上に表示する表示手段とを備え、
前記地図データ記憶媒体が記憶する第2地図データのリンクデータには、リンクに対応する道路の属性および経路コストに関するデータが含まれていることを特徴とする地図データ記憶媒体を用いた経路探索装置である。
また本発明は、(a)地図データ記憶媒体であって、
複数種類の道路のうちから予め定められた選択規則に従って選別された道路の接続関係を表す第1道路データと、
選別された道路が選別によって寸断されることがないように、前記複数種類の道路のうちから選別された道路の接続関係を表す第2道路データとを含んで構成される地図データを記憶する地図データ記憶媒体と、
(b)地図データ記憶媒体に記憶されている地図データに基づいて、所定の地域の地図画面を表示する表示手段とを備えることを特徴とする地図データ記憶媒体を用いた表示装置である。
また本発明は、指定された2地点間の経路を、記憶されている地図データに基づいて経路探索を行う経路探索装置において、
(a)地図データ記憶媒体であって、
複数種類の道路のうちから予め定められた選択規則に従って選別された道路の接続関係を表す第1道路データと、
選別された道路が選別によって寸断されることがないように、前記複数種類の道路のうちから選別された道路の接続関係を表す第2道路データとを含んで構成される地図データを記憶する地図データ記憶媒体と、
(b)前記地図データ記憶媒体から地図データを読出し、読出した地図データに基づいて前記2地点間の経路探索を行う探索手段と、
(c)前記地図データ記憶媒体に記憶されている地図データに基づいて、地図画面を表示し、その地図画面上に前記探索手段が探索した経路を表示する表示手段とを備えることを特徴とする地図データ記憶媒体を用いた経路探索装置である。
【0009】
【作用】
本発明に従えば、経路探索に用いられる第2地図データには、道路の交差点または行止まりを示すノードに関するノードデータと、各ノードを連結するリンクに関するリンクデータとのみが含まれており、従来のように道路の曲線形状を折線近似するための補間ノードや補間リンクに関するデータが含まれていないので、経路探索を行う際に、選択すべき推薦経路を互いに隣接する1つの交差点から他の交差点までの区間毎に確定することができ、探索すべき推薦経路を速やかに確定することができる。また、第2地図データには、補間ノードおよび補間リンクに関するデータが含まれていないので、経路探索の際に演算処理すべきデータの情報量が少なくなり、処理速度を向上することができる。また、補間ノードおよび補間リンクに関するデータが含まれていないので、地図データ記憶媒体から読出した地図データを一時記憶しておくためのメモリなどの記憶容量を小さくすることができ、装置の製造コストを削減することができる。第1地図データは、ノードデータとリンクデータと補間ノードデータと補間リンクデータとから成り、これによって地図を表示することができる。地図データ記憶媒体には、前述の第1地図データと第2地図データとが個別的に設けられており、したがって本発明では、経路探索時に、補間ノードおよび補間リンクが含まれる第1地図データから必要なノードデータおよびリンクデータを抽出するものではなく、このような抽出工程が、第2地図データを用いることによって、不要になる。これによって上述のように経路探索を速やかに行うことができる。また、地図データのリンクデータには、リンクが対応する道路属性および経路コストに関するデータが予め含まれているので、経路探索を行う際に一々道路の道路属性を検索する必要がなく、また道路の経路コストを算出する必要がなく、その結果、経路探索の処理速度を向上することができる。
【0010】
また本発明によれば、上記地図データ記憶装置を用いた経路探索装置によって、経路探索を行うべき2つの地点が指定されると、2つの地点のうちの一方の地点が経路探索を開始する始点と設定され、他方の地点が経路探索を終了する終点と設定され、探索手段による経路探索が開始される。経路探索は、探索中の探索経路の末端の点である探索点を移動しながら、始点から探索点までの経路長や自動車が移動する際の所要時間などを示す経路コストの和を算出し、経路コストの和が最も小さくなる探索点の位置を選択する。次に、その選択した探索点の位置に至る他の経路があるかどうかを調べ、他の経路がある場合には、選択した探索点の位置に至るその複数の経路のうちから経路コストの和が最も小さくなる経路を、始点から選択した探索点の位置までの推薦経路とする。このように選択された探索点の位置までの推薦経路が確定すると、新たな探索点を、選択された探索点の位置のノードに1つのリンクを介して隣接するノード上に設け、その新たな探索点を順次移動しながら、同様に新たな探索点までの推薦経路を決定する。ここで、高速道路よりも一般道路を優先して経路探索を行うべきことなどが予め設定されている場合には、道路が一般道路であるか高速道路であるか、および道路の幅員などを示すリンクデータが含む道路属性を参照しながら経路探索が行われる。
【0011】
このように経路探索によって探索される推薦経路は、互いに隣接するノード間の1つのリンクに対応する区間毎に、すなわち本発明では交差点を示す1つのノードから隣接する交差点の他のノードまでの区間毎に確定されてゆき、設定される探索点が終点に到達すると、経路探索が終了される。
【0012】
探索点の移動および新たな探索点の設定に伴って、探索点の位置する地域の地図データが地図データ記憶媒体から順次読出される。
【0013】
このような構成によって、経路探索に用いられる地図データには、道路の交差点または行止まりを示すノードに関するノードデータと、各ノードを連結するリンクに関するリンクデータとのみが含まれており、従来のように道路の曲線形状を折線近似するための補間ノードや補間リンクに関するデータが含まれていないので、経路探索を行う際に、選択すべき推薦経路を互いに隣接する1つの交差点から他の交差点までの区間毎に確定することができ、探索すべき推薦経路を速やかに確定することができる。
【0014】
また、第2地図データには、補間ノードおよび補間リンクに関するデータが含まれていないので、経路探索の際に演算処理すべきデータの情報量が少なくなり、処理速度を向上することができる。また、補間ノードおよび補間リンクに関するデータが含まれていないので、地図データ記憶媒体から読出した地図データを一時記憶しておくためのメモリなどの記憶容量を小さくすることができ、装置の製造コストを削減することができる。
【0015】
また、地図データのリンクデータには、リンクが対応する道路属性および経路コストに関するデータが予め含まれているので、経路探索を行う際に一々道路の道路属性を検索する必要がなく、また道路の経路コストを算出する必要がなく、その結果、経路探索の処理速度を向上することができる。
【0016】
また本発明に従えば、前述の経路探索によって探索すべき推薦経路が得られると、表示手段は、地図データ記憶媒体に記憶されている地図データと、補間ノードおよび補間リンクに関する補間ノードデータとに基づいて、地図画面を表示し、その地図画面上に推薦経路を表示する。
【0017】
また本発明に従えば、地図データ記憶装置には道路の曲線形状を表す補間ノードおよび補間リンクに関する補間ノードデータおよび補間リンクデータが記憶されているので、表示手段において、実際の道路の形状に近い道路の曲線形状が表現された地図画面を表示することができる。その結果、道路の形状が実際の道路の形状に即して表された推薦経路を、地図画面上に表示することができ、運転者が探索された推薦経路を認識しやすくすることができる。また本発明に従えば、地図データのリンクデータには、リンクが対応する道路属性および経路コストに関するデータが予め含まれているので、経路探索を行う際に一々道路の道路属性を検索する必要がなく、また道路の経路コストを算出する必要がなく、その結果、経路探索の処理速度を向上することができる。
【0018】
また本発明に従えば、経路探索手段による経路探索は、複数種類の道路のうちから予め定められた選択規則に従って選別された道路の接続関係を表す第1道路データと、選別された道路が選別によって寸断されることがないように前記複数種類の道路のうちから選別された道路の接続関係を表す第2道路データとを含んで構成される地図データ記憶装置に記憶されている地図データに基づいて行われる。
【0019】
【0020】
したがって、経路探索に用いる地図データには、第1道路データに含まれる道路が選別によって寸断された部分をつなぎ合わせて補間する道路に関する第2道路データが含まれているので、道路の接続関係の完全性が向上された地図データに基づいて経路探索が行われる。その結果、適切な経路を推薦経路として選択することができる。
【0021】
【0022】
また、地図データ記憶装置および表示手段を備える表示装置において、表示手段によって道路の接続関係の完全性が向上された地図画面を表示することができ、道路の接続関係の完全性が向上されているので、運転者が自ら道順を決定する際などに用いる地図として地図画面を利用することができる。
【0023】
【実施例】
図1は、本発明の一実施例のナビゲーション装置1の電気的構成を示すブロック図である。このナビゲーション装置1は、自動車に搭載されて、現在位置表示や目的地までの経路案内表示を行い、運転者の進路決定などに役立てられる。
【0024】
したがって、概略的に、このナビゲーション装置1では、操作キー2への入力操作に応答して、マイクロコンピュータなどで実現される中央処理装置3が通信バス4を介してCD-ROM装置5へ所望とする地域の地図データの読取りを指示する。その指示に応答して、処理回路6が、デコーダ7を介して、記憶媒体であるCD-ROMディスク8に記録されている地図データから対応する地域の地図データを読出す。こうして処理回路6から前記通信バス4を介して入力された地図データに対応して、前記中央処理装置3が、表示駆動回路9を介して、液晶表示装置などで実現される表示装置10を表示駆動することによって、前記所望とする地域の地図画面表示が実現される。
【0025】
また、このナビゲーション装置1には、GPS(Global Positioning System)受信機11が設けられており、このGPS受信機11は、GPSアンテナ12で受信された地球周回軌道を回る測位衛星からの信号に基づいて三角測量を行い、自車の緯度、経度、高度および走行速度などを演算し、その演算結果を前記通信バス4を介して中央処理装置3へ出力する。
【0026】
さらにまた、このナビゲーション装置1には、地磁気センサ13と、ジャイロセンサ14と、車輪速センサ15とが備えられている。地磁気センサ13は車両の進行方向を検出し、ジャイロセンサ14は車両の姿勢変化を検出し、車輪速センサ15は車体速度を検出する。センサ13,14の検出結果は、それぞれアナログ/デジタル変換器16,17でデジタル値に変換されて処理回路19に入力される。また、車輪速センサ15からの車速パルスは、パルスカウンタ18でカウントされ、処理回路19に入力される。このとき、後退位置検出器25によって変速機の変速段が後退位置であることが検出されると、前記カウント値は負の値とされる。
【0027】
処理回路19へは前記中央処理装置3から操作キー2で入力された自車位置などに関するデータが入力され、これによって該処理回路19は、前記各センサ13〜15の検出結果から現在の自車位置を推測演算し、その演算結果を中央処理装置3へ出力する。こうして、たとえばビル影、高架下またはトンネル内などで前記GPS受信機11によって正確な自車位置を計測することが不可能な地点においても、いわゆる推測航法によって正確に自車位置を計測することができる。
【0028】
さらにまた、中央処理装置3に関連してメモリ20が設けられている。このメモリ20には、後述するように選択された経路の目的地や経由地などが記憶されるとともに、探索の始点または終点となった探索地点が記憶されている。
【0029】
図2は、上述のように構成されたナビゲーション装置1の経路案内動作を説明するための機能ブロック図である。前記操作キー2、GPS受信機11および処理回路19などの入力部31から現在位置および目的地または経由地が入力されると、探索を開始する前に経路探索部32の地点設定部33が、入力された地点に関連して、探索を開始すべき地点または探索を終了すべき地点となるべき探索地点を初期設定する。
【0030】
設定された探索地点間で探索部34は、CD-ROM装置5などから参照符35で示すように地図データを読出して、リンクを辿って経路を探索し、その探索結果36は経路案内部37に与えられるとともに、該経路探索部32内のデータ管理部38で前記メモリ20に保管される。
【0031】
一方、前記地図データ35はまた、自車位置検出部39に与えられており、この自車位置検出部39は、前記GPS受信機11および処理回路19などからの出力と前記地図データ35とのマップマッチングを行い、正確な自車位置を演算して前記経路案内部37に与えるとともに、前記表示駆動回路9および表示装置10などで実現される出力部40に与える。出力部40にはまた、前記経路案内部37から、選択された経路に関するデータが与えられており、こうして、経路案内部37によって作成された経路上に、自車位置検出部39で計測された自車位置が併せて表示され、経路案内を行うことができる。
【0032】
図3は、CD-ROMディスク8に記憶される地図データの構成例を示す図である。地図データは、図3に示されるように、各ノードデータが含まれるノードテーブルNTと、各リンクデータが含まれるリンクテーブルLTと、ヘッダHとを有する。
【0033】
ヘッダHには、地図データの全データサイズ、その地図データが網羅する範囲を示す緯度および経度、ノードテーブルNTのデータサイズ、ノードテーブルNTの先頭アドレス、リンクテーブルLTのデータサイズ、リンクテーブルLTの先頭アドレスなどに関する情報が含まれている。
【0034】
ノードテーブルNTには、道路の交差点、行止まり点、および道路の曲線形状を折線近似する折点などを示す各ノードに個別に対応するノードデータND1〜NDnが含まれている。各ノードデータND1〜NDnには、対応するノードの座標データ、そのノードに接続しているリンクの数を示す分岐数、そのノードに接続するリンクを示す接続リンクリスト、そのノードにリンクを介して接続される全てのノードを示す接続ノードリスト、そのノードが交差点である場合の交差点名称、右左折禁止に関する情報などが含まれている。
【0035】
リストテーブルLTには、各ノード間に連結される各リンクに個別に対応するリンクデータLD1〜LDnが含まれている。各リンクデータLD1〜LDnには、そのリンクが対応する道路の道路種別、幅員、一方通行や速度規制などの交通規制、トンネルであるかどうかを示すトンネル属性、高架道路であるかどうかを示す高架属性、有料道路であるかどうかを示す有料属性、道路名称などの道路の属性に関する情報が含まれている。前記道路種別によって、リンクに対応する道路がたとえば高速道路であるか一般道路であるかが示される。
【0036】
上述のように構成される地図データは、メッシュ状に分割された各地域毎に分割されて記憶されている。各地域間で地図データに含まれるノードおよびリンクを連結するために、各地域に対応する地図データにはそれぞれメッシュコードが付されており、1つの地図データに含まれるノードがリンクを介して他の地図データに含まれるノードに連結される場合には、1つの地図データに含まれるノードに対応するノードデータに含まれる接続ノードリストに、連結される相手方の地図データのメッシュコードと、相手方のノードを特定するための相手方の地図データにおけるノード座標に関する情報とを含ませておくことによって、異なる地図データ間でノードおよびリンクを接続することができる。
【0037】
図4は、道路形状を表現した第1地図データおよび道路の接続関係のみを表現した第2地図データを説明するための図である。第1地図データは、表示装置10に地図画面を表示し、表示した地図画面上に自車の位置を表示して運転者の進路決定を補助する進路案内動作などに用いられる。第1地図データには、図4(1)に示されるように、道路の接続関係を表す黒丸で示される構成ノードSNおよび構成リンクSLのほかに、道路の形状を表す補間ノードCNおよび補間リンクCLが含まれている。
【0038】
構成ノードSNは、交差点や行止まり点を示し、構成リンクSLは各構成ノードSN間を接続する道路を示す。補間ノードCNは道路の曲線形状を折線近似して示す折点を示し、補間リンクCLは構成ノードSNまたは補間ノードCNと補間ノードCNとの間を連結する道路を示す。第1地図データには、道路の曲線形状を表す補間ノードCNおよび補間リンクCLが含まれているので、実際の道路の曲線形状が表現された地図データに基づいて適切な進路案内動作を行うことができる。
【0039】
第2地図データは、運転者によって指定された2つの地点間の最短経路などを探索する経路探索に用いられる。第2地図データには、図4(2)に示されるように、道路の接続関係を表す構成ノードSNおよび構成リンクSLが含まれている。
【0040】
本実施例のCD-ROM装置5におけるCD-ROMディスク8には、第1地図データとともに第2地図データが記憶されている。図4(2)に示される第2地図データは、図4(1)に示される第1地図データに基づいて作成されたものであり、第1地図データに含まれる補間ノードCNおよび補間リンクCしの部分を、図4に示されるように、対応する構成リンクSLに後述するように置き換えることによって形成される。
【0041】
図5は第1地図データの構成を示す図であり、図6は第2地図データの構成を示す図である。図5および図6に基づいて、第1地図データから第2地図データを作成する際の処理について説明する。ここでは例として、図5(1)に示される構成ノードN1と構成ノードN4との間の補間ノードN2,N3および補間リンクL1〜L3を、図6(1)に示される構成リンクLAに置き換える場合について説明する。
【0042】
第1地図データには、図3に基づいて前述したように、補間リンクL1〜L3にそれぞれ対応する各リンクデータが図5(2)に示されるように含まれている。その各リンクデータには、各補間リンクL1〜L3に対応する道路の道路種別が国道であること、幅員が10mであること、交通規制において一方通行でないこと、および各補間リンクL1〜L3に対応する区間の道路の実際の距離である実距離などに関する情報が含まれている。
【0043】
また第1地図データには、構成ノードN1,N4に対応する各ノードデータが図5(3)に示されるように含まれている。その各ノードデータには、構成ノードN1,N4に対応する交差点においてそれぞれ接続数が3であること、および右左折禁止でないことを示す右左折禁止情報が含まれている。このほか第1地図データには、補間ノードN2,N3に対応するノードデータも含まれている。補間ノードN2,N3は、道路の曲線形状を折線近似する折点を表すので、補間ノードN2,N3に対応するノードデータには、それぞれ接続数が2として登録されている。
【0044】
ノードデータにおいて、接続数が1である場合には、そのノードデータに対応するノードが道路の行止まり点に対応することを示し、接続数が3以上である場合には、そのノードデータに対応するノードが道路の交差点に対応することを示す。また接続数が2である場合には、そのノードデータに対応するノードが補間ノードであることを示し、接続数が2以外である場合には、そのノードデータに対応するノードが構成ノードであることを示す。したがって、接続数が2であるかどうかを判断することによって、そのノードデータに対応するノードが補間ノードであるかどうかを判断することができる。
【0045】
図5に示される第1地図データに基づいて、図6に示される第2地図データを作成する際には、第1地図データに含まれるノードのうちから補間ノードをピックアップし、ピックアップした補間ノードおよびその補間ノードに接続される補間リンクをそれぞれ構成リンクに置き換え、置き換えた構成リンクに対応するリンクデータを第2地図データ内に作成する。図5および図6の図示例では、補間ノードN2,N3および補間リンクL1〜L3に対応する構成リンクLaが図6(1)に示されるように設けられ、構成リンクLaに対応するリンクデータが、図6(2)に示されるように第2地図データ内に作成される。
【0046】
これに伴って、第1地図データにおける構成ノード、たとえば構成ノードN1,N4はそのまま構成ノード、たとえば構成ノードNa,Nbとして採用され、採用された構成ノードNa,Nbに対応するノードデータが、図6(3)に示されるように第2地図データ内に作成される。また、第1地図データにおける構成リンクは、そのまま構成リンクとして採用され、採用された構成リンクに対応するリンクデータが、第2地図データ内に作成される。
【0047】
構成リンクLaに対応するリンクデータには、図6(2)に示されるように、補間リンクL1〜L3に対応する各リンクデータから引継いだ道路種別、幅員、交通規制などに関する情報が含まれている。また構成リンクLaに対応するリンクデータには、第1地図データにおいて構成リンクLaの区間に含まれる全てのリンクを表すリンクリスト、第1地図データにおいて構成リストLaの区間に含まれる全てのノードを表すノードリスト、構成リストLaの区間に対応する道路の実際の距離を示す実距離、構成リンクLaの区間に対応する経路コストなどに関する情報が含まれている。
【0048】
図6(2)のリンクリストおよびノードリストによって、第2地図データにおける構成ノードNaと構成ノードNbとの間の構成リンクLaが、第1地図データにおいて補間リンクL1〜L3に対応され、構成リンクLaに対応する区間にはノードN1〜N4が含まれていることが表される。
【0049】
図6(2)の実距離に関するデータは、図5(2)の補間リンクL1〜L3に対応するリンクデータに含まれる実距離の値が加算されて作成され、図6(2)の図示例では実距離が1000mとなっている。
【0050】
図6(2)の経路コストは、後述するように第2地図データに基づいて経路探索を行う際に用いられるデータである。この経路コストには、構成リンクLaに対応する道路の区間の実距離、またはその道路の区間を実際に自動車が通過する際の推定の所要時間が登録される。本実施例では、所要時間が経路コストとして用いられている。この経路コストに関する情報は、第1地図データの補間リンクに対応しない第2地図データの補間リンクに対応するリンクデータにも同様に登録される。
【0051】
経路コストに用いられる所要時間は、実際に自動車が構成リンクLaに対応する区間を通過するのに要した時間を計測した計測値でもよく、構成リンクLaに対応するリンクデータに基づいて所定の演算を行い、算出した算出値でもよい。前記所定の演算の一例として、道路種別に対応して設定される所定の定数と、道路の幅員に対応して設定される所定の定数と、構成リンクLaの区間に対応する道路の実距離とを乗算して推定の所要時間を算出する方法が挙げられる。図6(2)の図示例では、経路コストは1.5分と登録されている。
【0052】
第2地図データにおける構成ノードNa,Nbに対応する各ノードデータには、図6(3)に示されるように、図5(3)の構成ノードN1,N4に対応する各ノードデータの内容がそのまま移植されて登録されており、その移植された登録データの他に第2地図データにおける各構成ノードNa,Nbがそれぞれ第1地図データにおける構成ノードN1,N4にそれぞれ対応することを示す対応ノードデータに関する情報が含まれている。また、第2地図データにおいて第1地図データの構成リンクに対応する構成リンクのリンクデータには、第1地図データのリンクデータの内容がそのまま移植され、さらに第1地図データにおいて対応する構成リンクを表す対応リンクデータが含まれている。
【0053】
次に上述の第2地図データを用いた経路探索を説明する。現在位値と目的地または経由地とをそれぞれ示す2つの地点が入力され、2つの地点のうちの一方の地点が経路探索を開始する始点と設定され、他方の地点が経路探索を終了する終点と設定されると、始点を含む第2地図データが読出され、始点を起点として経路探索が開始される。なお、始点および終点は、対応するノード上にそれぞれ設定される。
【0054】
Dijkstra法などが用いられる経路探索は、探索中の探索経路の末端の点である探索点を移動しながら、始点から探索点までの経路コストの和を算出し、経路コストの和が最も小さくなる探索点の位置を選択する。次に、その選択した探索点の位置に至る他の経路があるかどうかを調べ、他の経路がある場合には、選択した探索点の位置に至るその複数の経路のうちから経路コストの和が最も小さくなる経路を、始点から選択した探索点の位置までの推薦経路とする。ここで、高速道路よりも一般道路を優先して経路探索を行うべきことなどが予め設定されている場合には、リンクデータが示す道路属性を参照しながら経路探索が行われる。
【0055】
このように選択された探索点の位置までの推薦経路が確定すると、新たな探索点を選択された探索点の位置のノードに1つのリンクを介して隣接するノード上に設け、その新たな探索点を順次移動しながら、同様に新たな探索点までの推薦経路を決定する。
【0056】
このように経路探索によって探索される推薦経路は、互いに隣接するノード間の1つのリンクに対応する区間毎に、すなわち本発明では交差点を示す1つのノードから隣接する交差点を示す他のノードまでの区間毎に確定されてゆき、順次設定される探索点が終点に到達すると、経路探索が終了される。
【0057】
探索点の移動および新たな探索点の設定に伴って、探索経路における末端の探索点の位置する地域の第2地図データが順次読出される。
【0058】
経路探索によって2地点間の選択すべき推薦経路が得られると、経路探索に伴って読出した第2地図データに対応する第1地図データが読出され、得られた推薦経路を表示するための地図画面が、読出した第2地図データに基づいて表示される。第2地図データ上に形成されている推薦経路は、第2地図データのリンクデータに含まれる前述のリンクリストおよびノードリスト、および対応リンクデータに基づいて、またノードデータに含まれる対応ノードデータに基づいて第1地図データ上における推薦経路へと変換され、読出した第1地図データに基づいて表示される地図画面上に変換された推薦経路が表示される。
【0059】
したがって、経路探索に用いられる第2地図データには、道路の曲線形状を表す補間ノードおよび補間リンクに対応する図5(2),(3)に示されるようなノードデータおよびリンクデータが含まれていないので、経路探索の際、選択すべき推薦経路を隣接する交差点の区間毎に確定することができ、従来のように折点を示すノードを含めた互いに隣接する各ノード間毎に推薦経路を確定するのに比べて、選択すべき推薦経路をいち早く確定することができ、経路探索の処理速度を向上することができる。
【0060】
また、第2地図データには補間ノードおよび補間リンクに対応するノードデータおよびリンクデータが含まれていないので、経路探索の際に演算処理すべき情報量を小さくすることができ、処理速度を向上することができる。またCD-ROMディスク8から読出した地図データを一時記憶しておくためのメモリ20の記憶容量を削減することができ、ナビゲーション装置1の製造コストを削減することができる。
【0061】
また、第2地図データのリンクデータには、各リンクが対応する道路の道路属性および経路コストに関するデータが予め含まれているので、道路属性を参照しながら適切な経路を推薦経路としていち早く探索することができる。
【0062】
また、第2地図データにおいて、構成リンクが第1地図データにおける補間ノードおよび補間リンクに対応する場合には、第2地図データのリンクデータには、対応する補間ノードおよび補間リンクを示すノードリストおよびリンクリストが図6(2)に示されるように含まれており、推薦経路を表示する際には、ノードリストおよびリンクリストに基づいて第2地図データ上における構成リンクが第1地図データ上における補間ノードおよび補間リンクが対応付けられるので、道路の形状が表現された第1の地図データに基づいて、推薦経路を表示することができる。その結果、運転者が選択された推薦経路を認識しやすくなる。
【0063】
なお、上述の実施例では、道路の形状を表現した第1地図データに伴って経路探索用の第2地図データがCD-ROMディスク8に記憶されていたが、他の実施例として第1地図データがCD-ROMディスク8に記憶されていない場合を説明する。本実施例では、第1地図データがCD-ROMディスク8に記憶されていないので、前述した補間ノードおよび補間リンクに対応するノードデータおよびリンクデータを第2地図データとは別に記憶しておく必要がある。
【0064】
本実施例では、図7に示されるように、補間リンクCL1〜CLnに対応する補間リンクデータCLD1〜CLDnが含まれる補間リンクテーブルCLDが、第2地図データとは別にCD-ROMディスク8に記憶されている。またこれと同様に補間ノードに対応する各補間ノードデータが含まれる補間ノードテーブルも、CD-ROMディスク8に記憶されている。第2地図データに含まれる構成リンクに、補間ノードおよび補間リンクが対応する場合には、その構成リンクのリンクデータに、前述のリンクリストおよびノードリストの代わりに図8に示される補間データDCが付与される。
【0065】
この補間データDCは、対応する補間ノードおよび補間リンクの補間ノードデータおよび補間リンクデータを前述の補間ノードテーブルおよび補間リンクテーブルから読出すためのデータであり、図8の図示例では補間リンクに関する補間データDCが示されている。補間データDCは、図8に示されるように、構成リンクに対応する補間リンクの補間リンクデータが補間リンクテーブルにおいて先頭から何番目かを示すディスプレイスメントデータDC1と、何個分の補間リンクデータが構成リンクに対応しているかを示す構成数に関するデータDC2とから成る。同様に、図示しない補間ノードに関する補間データも、ディスプレイスメントデータと構成数に関するデータとから成る。
【0066】
経路探索の際には、図7の補間ノードテーブルおよび補間リンクテーブル内のデータを読込まずに第2地図データ内のデータのみを読込みながら経路探索を行い、推薦経路が確定して探索動作が終了すると、前述の補間データに基づいて補間リンクテーブルおよび補間ノードテーブル内のデータを読込み、道路の曲線形状に関するデータを補ってから推薦経路を表示する。
【0067】
次に、前述の実施例のナビゲーション装置1とCD-ROMディスク8に記憶されている地図データが異なるナビゲーション装置に関するまた他の実施例について説明する。
【0068】
CD-ROMディスク8に記憶される進路案内や経路探索に用いられるデータは、データの情報量を減らし、処理速度を向上するため、全ての道路に関する道路データを含む親データのうちから所定の選択規則に基づいて選別された道路に関する道路データを含んで構成される。このように構成される地図データを作成する際の手順を図9〜図12に基づいて説明する。
【0069】
前述の実施例において説明したように、リンクデータには、道路種別や幅員などの道路属性に関する情報が含まれている。まず、道路属性に基づいて各道路毎にランク付けを行い、全ての道路に関するデータを含んだ親データから、ランクの高い所定の道路に対応する道路データのみを図9に示されるように抜出し、第1道路データとする。
【0070】
図9(1)において太い実線で示される道路A〜Dはランクの高い道路であり、細い実線で示される道路E1〜E6はランクの低い道路であり、選別の結果、図9(2)に示されるようにランクの高い道路A〜Dのみが抜き出されている。このように、単純なランク付けに基づいて道路を選別すると、たとえば1本につながった道路であっても、ランク付けの低い部分、たとえば幅員が狭くなった部分などでは、道路データが抜き出されることなく取り残されてしまい、図9(2)に示されるように、道路が寸断されてしまう。
【0071】
本実施例において注目すべきは、前述のような道路の選別によって道路が寸断された部分を、図10に示されるように、つなぎ合わせて道路の接続関係の完全性を回復する点である。
【0072】
図10(1)において寸断されている道路Aおよび道路Dの問には、図10(2)に示されるように選別されなかったランクの低い道路E4が補間されている。同様に図10(1)において宙に浮いている形となっている道路Bには、図10(2)に示されるように、道路Aおよび道路Cにそれぞれ通ずる道路E3,E6がそれぞれ接続されて補間されている。このような補間された道路E3,E4,E6に関するデータは第2道路データに含まれる。
【0073】
このような道路E3,E4,E6の補間は、図9(1)に対応する親データに基づいて表示された地図画面を人間が目視して補間すべき道路を選択するようにしてもよい。または、図10(1)における道路Aの末端A1と道路Dの末端D1との間と、道路Bの一方の末端B1と道路Aとの間と、道路Bの他方の末端B2と道路Cとの間とにおいて、図9(1)の親データに基づいて経路探索を行い、経路コストが最も小さくなるような経路を補間道路として選択するようにしてもよい。
【0074】
図11に基づいて道路の他の補間方法を説明する。図11(1)に示されるように、選別された第1道路データに含まれる道路Fが地点Pと地点Qとの問の区間で大きく回り込んでいる場合に、地点Pと地点Qとを短絡する選別されなかった道路が存在する場合には、図11(2)に示されるように地点Pと地点Qとを短絡する道路E7を補間する。この道路E7の補間は、前述の図10における補間処理と同様に、人間の目視によって行ってもよいし、経路探索によって行ってもよい。
【0075】
また、道路Fが地点Pから地点Qまでの間で囲い込む領域FA内において経路探索を行い、経路探索の結果、領域FAの部分を短絡する経路、すなわち道路Fよりも実距離の短い経路が発見された場合には、予め定められた所定の選択規則に基づいて発見された経路のうちから所定の経路を選択して補間経路として補間する。選択された道路は、第2道路データに含められる。ここで、道路Fの地点Pと地点Qとの間の区間は、図10に示される補間処理によって補間された第2道路データに含まれる道路であってもよい。
【0076】
前記所定の選択規則は、地点Pと地点Qとの間の経路コストが最小の経路の経路コストC1とし、経路探索によって発見された経路を経由する経路の経路コストをC2とするとき、C2がC1>C2・Kの条件を満たす場合に、その発見された経路を補間するという選択規則が例として挙げられる。ここで、Kは1以上の定数である。
【0077】
図12に基づいて、また他の補間方法を説明する。道路の選別によって図12(1)に示されるように道路RBと道路RAとが寸断されてしまった場合に、まず、道路RBの末端RBlと道路RAとを接続する全ての道路をピックアップし、ピックアップした道路のうちから末端RB1から道路RAまでの実距離が最短の道路の実距離をs0とし、ピックアップした道路のうちから末端RB1から道路RAまでの実距離snが、sn-s0<K1の条件を満たす道路を補間候補として、図12(2)に示されるように抜出す。ここで、K1は所定の定数である。図12(2)において、実距離が最短の道路は道路R0であり、その道路R0の他に道路R1〜R3が補間候補として抜き出されている。抜き出された道路R0〜R3は、接続点P0〜P3においてそれぞれ道路RAとつながっている。
【0078】
上述のような条件に従って補間道路の候補を抜き出すことによって、図12(2)に示されるように、定数K1の値を適当に調整することによって、道路RBの末端RB1よりも左側で道路RAに接続する道路R0,R1,R2と右側で道路RAに接続する道路R3とを補間候補として抜き出すことができる。これによって、運転者が道路RBを経由して道路RAに至り、道路RA上を図12(2)における左方向に進行する場合にも右方向に進行する場合にも対応できる道路を補間することが可能となる。
【0079】
図12(2)に示されるように補間候補が抜き出されると、前述の実距離が最短の道路R0の接続点P0から接続点P1〜P3までの道路RA上における距離が、所定の値M以上の道路R1〜R3が、抜き出されている道路R1〜R3のうちから道路R0とともに、図12(3)に示されるように選択されて補間される。図12(3)の図示例では、道路R1,R2は接続点P1,P2の接続点P0からの距離が所定の値Mよりも短いので間引かれ、道路R0,R3が補間道路として選択されている。
【0080】
このように補間候補として抜き出された道路R0〜R3のうちから、道路R0,R3を選択して補間することによって、道路RBと道路RAとを結ぶ必要かつ充分な道路、すなわち運転者が道路RBから道路RAに至り、道路RA上を図12(3)における左方向に進行する場合にも右方向に進行する場合にも対応可能な道路を補間することができる。
【0081】
以上のように作成された地図データは、CD-ROMディスク8に記憶されており、進路案内および経路探索の際には、CD-ROMディスク8に記憶されている地図データのうちから所定の地域の地図データが順次読出されて案内動作および探索動作が行われる。
【0082】
したがって、CD-ROMディスク8に記憶されている地図データでは、道路の選別によって道路が寸断された部分がつなぎ合わされて補間されており、道路の接続関係の完全性が向上されているので、CD-ROMディスク8に記憶されている地図データを用いて正確な経路探索を行うことができる。また、CD-ROMディスク8に記憶されている地図データを用いて進路案内を行う際にも、運転者が道路の寸断された部分に到達し、道が判らなくなってしまうようなことがなく、確実に進路案内を行うことができる。またCD-ROMディスク8に記憶されている地図データに基づいて地図画面を表示した際には、道路の接続関係の完全性が向上されているので、表示した地図画面を運転者が自ら移動経路を選択するためなどの地図としても利用することができる。
【0083】
また、図11に示されるように、選別された道路Fが大きく回り込んでいる場合には、回り込んでいる部分を短絡する道路E7が補間されるので、CD-ROMディスク8に記憶されている地図データに基づいて経路探索を行う際に、道路E7を辿る経路の方が回り込んだ経路を取るよりも経路コストが小さい場合には、道路E7を辿る経路が推薦経路として選択され、道路Fに沿った大回りの経路が推薦経路として探索されてしまうのを防止することができる。
【0084】
また図12に示されるように、道路RBと道路RAとの間の道路を補間する際には、道路RBを経由して道路RAに至った場合に、道路RA上を図12における左方向に進行する場合にも右方向に進行する場合にも対応可能なように、補間する道路を所定の選択規則に基づいて決定するので、CD-ROMディスク8に記憶されている地図データに基づいて経路探索を行う際に、適切な経路を探索することができる。
【0085】
【発明の効果】
以上のように本発明によれば、経路探索に用いられる第2地図データには、道路の交差点または行止まりを示すノードに関するノードデータと、各ノードを連結するリンクに関するリンクデータとのみが含まれており、従来のように道路の曲線形状を折線近似するための補間ノードや補間リンクに関するデータが含まれていないので、経路探索を行う際に、選択すべき推薦経路を互いに隣接する1つの交差点から他の交差点までの区間毎に確定することができ、探索すべき推薦経路を速やかに確定することができる。
【0086】
また、第2地図データには、補間ノードおよび補間リンクに関するデータが含まれていないので、経路探索の際に演算処理すべきデータの情報量が少なくなり、処理速度を向上することができる。また、補間ノードおよび補間リンクに関するデータが含まれていないので、地図データ記憶媒体から読出した地図データを一時記憶しておくためのメモリなどの記憶容量を小さくすることができ、装置の製造コストを削減することができる。
【0087】
また、地図データのリンクデータには、リンクが対応する道路属性および経路コストに関するデータが予め含まれているので、経路探索を行う際に一々道路の道路属性を検索する必要がなく、また道路の経路コストを算出する必要がなく、その結果、経路探索の処理速度を向上することができる。
【0088】
また本発明によれば、経路探索に用いる地図データには、第1道路データに含まれる道路が選別によって寸断された部分をつなぎ合わせて補間する道路に関する第2道路データが含まれているので、道路の接続関係の完全性が向上された地図データに基づいて経路探索が行われる。その結果、適切な経路を推薦経路として選択することができる。
【図面の簡単な説明】
【図1】
本発明の一実施例のナビゲーション装置1の電気的構成を示すブロック図である。
【図2】
ナビゲーション装置1における経路案内を説明する機能ブロック図である。
【図3】
地図データの構成例を示す図である。
【図4】
道路形状を表現した第1地図データと道路の接続関係のみを表現した第2地図データとを説明するための図である。
【図5】
第1地図データの構成を説明するための図である。
【図6】
第2地図データの構成を説明するための図である。
【図7】
補間データDCの構成を示す図である。
【図8】
補間リンクテーブルCLTの構成を示す図である。
【図9】
道路の選別処理を説明するための図である。
【図10】
道路の補間処理を説明するための図である。
【図11】
道路の補間処理を説明するための図である。
【図12】
道路の補間処理を説明するための図である。
【符号の説明】
1 ナビゲーション装置
2 操作キー
3 中央処理装置
5 CD-ROM装置
8 CD-ROMディスク
10 表示装置
11 GPS受信機
13〜15 センサ
19 処理回路
20 メモリ
 
訂正の要旨 訂正の要旨
訂正A:
特許第3007803号発明の明細書中特許請求の範囲の請求項1乃至4を、特許請求の範囲の減縮を目的として、
「 【請求項1】 2点間の経路を地図データに基づいて経路探索を行う経路探索装置において、
(a)少なくとも道路の交差点または行止まりを示すノードに関するノードデータと、前記ノードを連結するリンクに関するリンクデータと、道路の形状を折線近似した折点を示す補間ノードに関する補間ノードデータと、前記補間ノードを連結する補間リンクに関する補間リンクデータとから成る第1地図データと、
道路の交差点または行止まりを示すノードに関するノードデータと、前記ノードを連結するリンクに関するリンクデータとから成る第2地図データとを含む地図データ記憶媒体と、
(b)前記地図データ記憶媒体の第2地図データに基づき経路探索を行う経路探索手段と、
(c)前記経路探索手段が第2地図データに基づいて探索した経路を、前記地図データ記憶媒体の第1地図データに基づいて地図上に表示する表示手段とを備えることを特徴とする地図データ記憶媒体を用いた経路探索装置。
【請求項2】 前記地図データ記憶媒体の第1地図データに基づいて地図を表示する表示手段を備えることを特徴とする請求項1記載の地図データ記憶媒体を用いた経路探索装置。
【請求項3】 2点間の経路を地図データに基づいて経路探索を行う経路探索装置において、
(a)少なくとも道路の交差点または行止まりを示すノードに関するノードデータと、前記ノードを連結するリンクに関するリンクデータと、道路の形状を折線近似した折点を示す補間ノードに関する補間ノードデータと、前記補間ノードを連結する補間リンクに関する補間リンクデータとから成る第1地図データと、
道路の交差点または行止まりを示すノードに関するノードデータと、前記ノードを連結するリンクに関するリンクデータとから成る第2地図データとを含む地図データ記憶媒体と、
(b)前記地図データ記憶媒体の第2地図データに基づき経路探索を行う経路探索手段とを備え、
前記地図データ記憶媒体が記憶する第2地図データのリンクデータには、リンクに対応する道路の属性および経路コストに関するデータが含まれていることを特徴とする地図データ記憶媒体を用いた経路探索装置。
【請求項4】 2点間の経路を地図データに基づいて経路探索を行う経路探索装置において、
(a)少なくとも道路の交差点または行止まりを示すノードに関するノードデータと、前記ノードを連結するリンクに関するリンクデータと、道路の形状を折線近似した折点を示す補間ノードに関する補間ノードデータと、前記補間ノードを連結する補間リンクに関する補間リンクデータとから成る第1地図データと、
道路の交差点または行止まりを示すノードに関するノードデータと、前記ノードを連結するリンクに関するリンクデータとから成る第2地図データとを含む地図データ記憶媒体と、
(b)前記地図データ記憶媒体の第2地図データに基づき経路探索を行う経路探索手段と、
(c)前記経路探索手段が第2地図データに基づいて探索した経路を、前記地図データ記憶媒体の第1地図データに基づいて地図上に表示する表示手段とを備え、
前記地図データ記憶媒体が記憶する第2地図データのリンクデータには、リンクに対応する道路の属性および経路コストに関するデータが含まれていることを特徴とする地図データ記憶媒体を用いた経路探索装置。」と訂正する。
訂正B:
特許第3007803号発明の明細書中段落【0008】における「本発明は、2点間の経路を地図データに基づいて経路探索を行う経路探索装置において、
(a)少なくとも道路の交差点または行止まりを示すノードに関するノードデータと、前記ノードを連結するリンクに関するリンクデータと、道路の形状を折線近似した折点を示す補間ノードに関する補間ノードデータと、前記補間ノードを連結する補間リンクに関する補間リンクデータとから成る第1地図データと、
道路の交差点または行止まりを示すノードに関するノードデータと、前記ノードを連結するリンクに関するリンクデータとから成る第2地図データとを含む地図データ記憶媒体と、
(b)前記地図データ記憶媒体の第2地図データに基づき経路探索を行う経路探索手段とを備えることを特徴とする地図データ記憶媒体を用いた経路探索装置である。
また本発明は、前記経路探索手段が第2地図データに基づいて探索した経路を、前記地図データ記憶媒体の第1地図データに基づいて地図上に表示する表示手段を備えることを特徴とする。
また本発明は、前記地図データ記憶媒体の第1地図データに基づいて地図を表示する表示手段を備えることを特徴とする。
また本発明は、前記地図データ記憶媒体が記憶する第2地図データのリンクデータには、リンクに対応する道路の属性および経路コストに関するデータが含まれていることを特徴とする。」を、
「本発明は、2点間の経路を地図データに基づいて経路探索を行う経路探索装置において、
(a)少なくとも道路の交差点または行止まりを示すノードに関するノードデータと、前記ノードを連結するリンクに関するリンクデータと、道路の形状を折線近似した折点を示す補間ノードに関する補間ノードデータと、前記補間ノードを連結する補間リンクに関する補間リンクデータとから成る第1地図データと、
道路の交差点または行止まりを示すノードに関するノードデータと、前記ノードを連結するリンクに関するリンクデータとから成る第2地図データとを含む地図データ記憶媒体と、
(b)前記地図データ記憶媒体の第2地図データに基づき経路探索を行う経路探索手段と、
(c)前記経路探索手段が第2地図データに基づいて探索した経路を、前記地図データ記憶媒体の第1地図データに基づいて地図上に表示する表示手段とを備えることを特徴とする地図データ記憶媒体を用いた経路探索装置である。
また、本発明は、前記地図データ記憶媒体の第1地図データに基づいて地図を表示する表示手段を備えることを特徴とする。
また、本発明は、2点間の経路を地図データに基づいて経路探索を行う経路探索装置において、
(a)少なくとも道路の交差点または行止まりを示すノードに関するノードデータと、前記ノードを連結するリンクに関するリンクデータと、道路の形状を折線近似した折点を示す補間ノードに関する補間ノードデータと、前記補間ノードを連結する補間リンクに関する補間リンクデータとから成る第1地図データと、
道路の交差点または行止まりを示すノードに関するノードデータと、前記ノードを連結するリンクに関するリンクデータとから成る第2地図データとを含む地図データ記憶媒体と、
(b)前記地図データ記憶媒体の第2地図データに基づき経路探索を行う経路探索手段とを備え、
前記地図データ記憶媒体が記憶する第2地図データのリンクデータには、リンクに対応する道路の属性および経路コストに関するデータが含まれていることを特徴とする地図データ記憶媒体を用いた経路探索装置である。
また、本発明は、2点間の経路を地図データに基づいて経路探索を行う経路探索装置において、
(a)少なくとも道路の交差点または行止まりを示すノードに関するノードデータと、前記ノードを連結するリンクに関するリンクデータと、道路の形状を折線近似した折点を示す補間ノードに関する補間ノードデータと、前記補間ノードを連結する補間リンクに関する補間リンクデータとから成る第1地図データと、
道路の交差点または行止まりを示すノードに関するノードデータと、前記ノードを連結するリンクに関するリンクデータとから成る第2地図データとを含む地図データ記憶媒体と、
(b)前記地図データ記憶媒体の第2地図データに基づき経路探索を行う経路探索手段と、
(c)前記経路探索手段が第2地図データに基づいて探索した経路を、前記地図データ記憶媒体の第1地図データに基づいて地図上に表示する表示手段とを備え、
前記地図データ記憶媒体が記憶する第2地図データのリンクデータには、リンクに対応する道路の属性および経路コストに関するデータが含まれていることを特徴とする地図データ記憶媒体を用いた経路探索装置である。」と、明りょうでない記載の釈明を目的として、訂正する。
異議決定日 2001-03-05 
出願番号 特願平6-269144
審決分類 P 1 651・ 121- ZA (G01C)
最終処分 取消  
前審関与審査官 太田 恒明秋田 将行  
特許庁審判長 大森 蔵人
特許庁審判官 西川 一
槙原 進
登録日 1999-11-26 
登録番号 特許第3007803号(P3007803)
権利者 富士通テン株式会社
発明の名称 地図データ記憶媒体を用いた経路探索装置  
代理人 宮田 金雄  
代理人 廣瀬 峰太郎  
代理人 廣瀬 峰太郎  
代理人 竹内 三喜夫  
代理人 竹内 三喜夫  
代理人 西教 圭一郎  
代理人 杉山 毅至  
代理人 杉山 毅至  
代理人 西教 圭一郎  
代理人 高瀬 彌平  
  • この表をプリントする

プライバシーポリシー   セキュリティーポリシー   運営会社概要   サービスに関しての問い合わせ