【事件の表示】
　特許第３００７８０３号「地図データ記憶媒体を用いた経路探索装置」の請求項１ないし６に係る特許に対する特許異議の申立てについて、次のとおり決定する。
【結　論】
　訂正を認める。
　特許第３００７８０３号の請求項１ないし６に係る特許を取り消す。
【理　由】
【１】手続の経緯
　本件特許第３００７８０３号の請求項１乃至６に係る発明についての出願は、平成６年１１月１日に特許出願され、平成１１年１１月２６日に設定登録され、その後、三菱電機株式会社より特許異議の申立てがなされ、取消理由通知がなされたところ、その指定期間内である平成１３年１月２９日に訂正請求がなされたものである。
　
【２】訂正の適否
　１．訂正事項
Ａ．特許請求の範囲の請求項１乃至４を、
「　【請求項１】　２点間の経路を地図データに基づいて経路探索を行う経路探索装置において、
　（ａ）少なくとも道路の交差点または行止まりを示すノードに関するノードデータと、前記ノードを連結するリンクに関するリンクデータと、道路の形状を折線近似した折点を示す補間ノードに関する補間ノードデータと、前記補間ノードを連結する補間リンクに関する補間リンクデータとから成る第１地図データと、
　道路の交差点または行止まりを示すノードに関するノードデータと、前記ノードを連結するリンクに関するリンクデータとから成る第２地図データとを含む地図データ記憶媒体と、
　（ｂ）前記地図データ記憶媒体の第２地図データに基づき経路探索を行う経路探索手段と、
　（ｃ）前記経路探索手段が第２地図データに基づいて探索した経路を、前記地図データ記憶媒体の第１地図データに基づいて地図上に表示する表示手段とを備えることを特徴とする地図データ記憶媒体を用いた経路探索装置。
　【請求項２】　前記地図データ記憶媒体の第１地図データに基づいて地図を表示する表示手段を備えることを特徴とする請求項１記載の地図データ記憶媒体を用いた経路探索装置。
　【請求項３】　２点間の経路を地図データに基づいて経路探索を行う経路探索装置において、
　（ａ）少なくとも道路の交差点または行止まりを示すノードに関するノードデータと、前記ノードを連結するリンクに関するリンクデータと、道路の形状を折線近似した折点を示す補間ノードに関する補間ノードデータと、前記補間ノードを連結する補間リンクに関する補間リンクデータとから成る第１地図データと、
　道路の交差点または行止まりを示すノードに関するノードデータと、前記ノードを連結するリンクに関するリンクデータとから成る第２地図データとを含む地図データ記憶媒体と、
　（ｂ）前記地図データ記憶媒体の第２地図データに基づき経路探索を行う経路探索手段とを備え、
　前記地図データ記憶媒体が記憶する第２地図データのリンクデータには、リンクに対応する道路の属性および経路コストに関するデータが含まれていることを特徴とする地図データ記憶媒体を用いた経路探索装置。
　【請求項４】　２点間の経路を地図データに基づいて経路探索を行う経路探索装置において、
　（ａ）少なくとも道路の交差点または行止まりを示すノードに関するノードデータと、前記ノードを連結するリンクに関するリンクデータと、道路の形状を折線近似した折点を示す補間ノードに関する補間ノードデータと、前記補間ノードを連結する補間リンクに関する補間リンクデータとから成る第１地図データと、
　道路の交差点または行止まりを示すノードに関するノードデータと、前記ノードを連結するリンクに関するリンクデータとから成る第２地図データとを含む地図データ記憶媒体と、
　（ｂ）前記地図データ記憶媒体の第２地図データに基づき経路探索を行う経路探索手段と、
　（ｃ）前記経路探索手段が第２地図データに基づいて探索した経路を、前記地図データ記憶媒体の第１地図データに基づいて地図上に表示する表示手段とを備え、
　前記地図データ記憶媒体が記憶する第２地図データのリンクデータには、リンクに対応する道路の属性および経路コストに関するデータが含まれていることを特徴とする地図データ記憶媒体を用いた経路探索装置。」と訂正する。
Ｂ．明細書の段落【０００８】における「本発明は、２点間の経路を地図データに基づいて経路探索を行う経路探索装置において、
　（ａ）少なくとも道路の交差点または行止まりを示すノードに関するノードデータと、前記ノードを連結するリンクに関するリンクデータと、道路の形状を折線近似した折点を示す補間ノードに関する補間ノードデータと、前記補間ノードを連結する補間リンクに関する補間リンクデータとから成る第１地図データと、
　道路の交差点または行止まりを示すノードに関するノードデータと、前記ノードを連結するリンクに関するリンクデータとから成る第２地図データとを含む地図データ記憶媒体と、
　（ｂ）前記地図データ記憶媒体の第２地図データに基づき経路探索を行う経路探索手段とを備えることを特徴とする地図データ記憶媒体を用いた経路探索装置である。
　また本発明は、前記経路探索手段が第２地図データに基づいて探索した経路を、前記地図データ記憶媒体の第１地図データに基づいて地図上に表示する表示手段を備えることを特徴とする。
　また本発明は、前記地図データ記憶媒体の第１地図データに基づいて地図を表示する表示手段を備えることを特徴とする。
　また本発明は、前記地図データ記憶媒体が記憶する第２地図データのリンクデータには、リンクに対応する道路の属性および経路コストに関するデータが含まれていることを特徴とする。」を、
「本発明は、２点間の経路を地図データに基づいて経路探索を行う経路探索装置において、
　（ａ）少なくとも道路の交差点または行止まりを示すノードに関するノードデータと、前記ノードを連結するリンクに関するリンクデータと、道路の形状を折線近似した折点を示す補間ノードに関する補間ノードデータと、前記補間ノードを連結する補間リンクに関する補間リンクデータとから成る第１地図データと、
　道路の交差点または行止まりを示すノードに関するノードデータと、前記ノードを連結するリンクに関するリンクデータとから成る第２地図データとを含む地図データ記憶媒体と、
　（ｂ）前記地図データ記憶媒体の第２地図データに基づき経路探索を行う経路探索手段と、
　（ｃ）前記経路探索手段が第２地図データに基づいて探索した経路を、前記地図データ記憶媒体の第１地図データに基づいて地図上に表示する表示手段とを備えることを特徴とする地図データ記憶媒体を用いた経路探索装置である。
　また、本発明は、前記地図データ記憶媒体の第１地図データに基づいて地図を表示する表示手段を備えることを特徴とする。
　また、本発明は、２点間の経路を地図データに基づいて経路探索を行う経路探索装置において、
　（ａ）少なくとも道路の交差点または行止まりを示すノードに関するノードデータと、前記ノードを連結するリンクに関するリンクデータと、道路の形状を折線近似した折点を示す補間ノードに関する補間ノードデータと、前記補間ノードを連結する補間リンクに関する補間リンクデータとから成る第１地図データと、
　道路の交差点または行止まりを示すノードに関するノードデータと、前記ノードを連結するリンクに関するリンクデータとから成る第２地図データとを含む地図データ記憶媒体と、
　（ｂ）前記地図データ記憶媒体の第２地図データに基づき経路探索を行う経路探索手段とを備え、
　前記地図データ記憶媒体が記憶する第２地図データのリンクデータには、リンクに対応する道路の属性および経路コストに関するデータが含まれていることを特徴とする地図データ記憶媒体を用いた経路探索装置である。
　また、本発明は、２点間の経路を地図データに基づいて経路探索を行う経路探索装置において、
　（ａ）少なくとも道路の交差点または行止まりを示すノードに関するノードデータと、前記ノードを連結するリンクに関するリンクデータと、道路の形状を折線近似した折点を示す補間ノードに関する補間ノードデータと、前記補間ノードを連結する補間リンクに関する補間リンクデータとから成る第１地図データと、
　道路の交差点または行止まりを示すノードに関するノードデータと、前記ノードを連結するリンクに関するリンクデータとから成る第２地図データとを含む地図データ記憶媒体と、
　（ｂ）前記地図データ記憶媒体の第２地図データに基づき経路探索を行う経路探索手段と、
　（ｃ）前記経路探索手段が第２地図データに基づいて探索した経路を、前記地図データ記憶媒体の第１地図データに基づいて地図上に表示する表示手段とを備え、
　前記地図データ記憶媒体が記憶する第２地図データのリンクデータには、リンクに対応する道路の属性および経路コストに関するデータが含まれていることを特徴とする地図データ記憶媒体を用いた経路探索装置である。」と訂正する。
　２．訂正の目的の適否、新規事項の有無及び拡張・変更の存否
（１）訂正Ａについて
　訂正Ａは、請求項１に記載の事項を訂正前の請求項１に記載の事項に訂正前の請求項２に記載の事項を組み合わせたものとし、請求項２に記載の事項を訂正前の請求項３に記載の事項とし、請求項３に記載の事項を訂正前の請求項１に記載の事項に訂正前の請求項４に記載の事項を組み合わせたものとし、請求項４に記載の事項を訂正前の請求項１に記載の事項に訂正前の請求項２に記載の事項及び訂正前の請求項４に記載の事項を組み合わせたものとするのであるから、特許請求の範囲の減縮に相当するものである。
　また、この訂正Ａは訂正前の明細書に記載された事項に基づくものである。
　さらに、訂正後の明細書の請求項１に係る発明においても、訂正前の明細書の請求項１に係る発明が解決しようとする、訂正前の明細書における段落【０００５】乃至【０００７】に記載の技術的課題と同じ技術的課題を解決するものであり、訂正前の明細書の請求項１に係る発明と訂正後の明細書の請求項１に係る発明とは技術思想が異なるものとはいえないのであるから、訂正Ａは特許請求の範囲を実質上変更するものではない。また、訂正Ａは特許請求の範囲を実質的に拡張するものでもない。
（２）訂正Ｂについて
　訂正Ｂは、前記特許請求の範囲の訂正（訂正Ａ）に合わせて発明の詳細な説明の対応箇所を訂正するものであり、明りょうでない記載の釈明に相当するものである。
　そして、訂正Ａと同じく、訂正Ｂは訂正前の明細書に記載された事項に基づくものであり、また、特許請求の範囲を実質上拡張又は変更するものではない。
　３．むすび
　以上のとおりであるから、前記訂正（訂正Ａ及びＢ）は、特許法等の一部を改正する法律（平成６年法律第１１６号。以下「平成６年改正法」という。）附則第６条第１項の規定によりなお従前の例によるとされる、特許法第１２０条の４第３項において準用する平成６年改正法による改正前の特許法第１２６条第１項ただし書き、第２項及び第３項の規定に適合するので、当該訂正を認める。
　
【３】特許異議の申立てについての判断（取消理由についての判断）
　１．本件発明
　本件請求項１乃至６に係る発明は、訂正された明細書及び図面の記載からみて、特許請求の範囲の請求項１乃至６に記載された次の事項によって特定されるとおりのものである。
　【請求項１】　２点間の経路を地図データに基づいて経路探索を行う経路探索装置において、
　（ａ）少なくとも道路の交差点または行止まりを示すノードに関するノードデータと、前記ノードを連結するリンクに関するリンクデータと、道路の形状を折線近似した折点を示す補間ノードに関する補間ノードデータと、前記補間ノードを連結する補間リンクに関する補間リンクデータとから成る第１地図データと、
　道路の交差点または行止まりを示すノードに関するノードデータと、前記ノードを連結するリンクに関するリンクデータとから成る第２地図データとを含む地図データ記憶媒体と、
　（ｂ）前記地図データ記憶媒体の第２地図データに基づき経路探索を行う経路探索手段と、
　（ｃ）前記経路探索手段が第２地図データに基づいて探索した経路を、前記地図データ記憶媒体の第１地図データに基づいて地図上に表示する表示手段とを備えることを特徴とする地図データ記憶媒体を用いた経路探索装置。
　【請求項２】　前記地図データ記憶媒体の第１地図データに基づいて地図を表示する表示手段を備えることを特徴とする請求項１記載の地図データ記憶媒体を用いた経路探索装置。
　【請求項３】　２点間の経路を地図データに基づいて経路探索を行う経路探索装置において、
　（ａ）少なくとも道路の交差点または行止まりを示すノードに関するノードデータと、前記ノードを連結するリンクに関するリンクデータと、道路の形状を折線近似した折点を示す補間ノードに関する補間ノードデータと、前記補間ノードを連結する補間リンクに関する補間リンクデータとから成る第１地図データと、
　道路の交差点または行止まりを示すノードに関するノードデータと、前記ノードを連結するリンクに関するリンクデータとから成る第２地図データとを含む地図データ記憶媒体と、
　（ｂ）前記地図データ記憶媒体の第２地図データに基づき経路探索を行う経路探索手段とを備え、
　前記地図データ記憶媒体が記憶する第２地図データのリンクデータには、リンクに対応する道路の属性および経路コストに関するデータが含まれていることを特徴とする地図データ記憶媒体を用いた経路探索装置。
　【請求項４】　２点間の経路を地図データに基づいて経路探索を行う経路探索装置において、
　（ａ）少なくとも道路の交差点または行止まりを示すノードに関するノードデータと、前記ノードを連結するリンクに関するリンクデータと、道路の形状を折線近似した折点を示す補間ノードに関する補間ノードデータと、前記補間ノードを連結する補間リンクに関する補間リンクデータとから成る第１地図データと、
　道路の交差点または行止まりを示すノードに関するノードデータと、前記ノードを連結するリンクに関するリンクデータとから成る第２地図データとを含む地図データ記憶媒体と、
　（ｂ）前記地図データ記憶媒体の第２地図データに基づき経路探索を行う経路探索手段と、
　（ｃ）前記経路探索手段が第２地図データに基づいて探索した経路を、前記地図データ記憶媒体の第１地図データに基づいて地図上に表示する表示手段とを備え、
　前記地図データ記憶媒体が記憶する第２地図データのリンクデータには、リンクに対応する道路の属性および経路コストに関するデータが含まれていることを特徴とする地図データ記憶媒体を用いた経路探索装置。
　【請求項５】 （ａ）地図データ記憶媒体であって、
　複数種類の道路のうちから予め定められた選択規則に従って選別された道路の接続関係を表す第１道路データと、
　選別された道路が選別によって寸断されることがないように、前記複数種類の道路のうちから選別された道路の接続関係を表す第２道路データとを含んで構成される地図データを記憶する地図データ記憶媒体と、
　（ｂ）地図データ記憶媒体に記憶されている地図データに基づいて、所定の地域の地図画面を表示する表示手段とを備えることを特徴とする地図データ記憶媒体を用いた表示装置。
　【請求項６】　指定された２地点間の経路を、記憶されている地図データに基づいて経路探索を行う経路探索装置において、
　（ａ）地図データ記憶媒体であって、
　複数種類の道路のうちから予め定められた選択規則に従って選別された道路の接続関係を表す第１道路データと、
　選別された道路が選別によって寸断されることがないように、前記複数種類の道路のうちから選別された道路の接続関係を表す第２道路データとを含んで構成される地図データを記憶する地図データ記憶媒体と、
　（ｂ）前記地図データ記憶媒体から地図データを読出し、読出した地図デー夕に基づいて前記２地点間の経路探索を行う探索手段と、
　（ｃ）前記地図データ記憶媒体に記憶されている地図データに基づいて、地図画面を表示し、その地図画面上に前記探索手段が探索した経路を表示する表示手段とを備えることを特徴とする地図データ記憶媒体を用いた経路探索装置。
　２．引用刊行物
　当審が通知した取消理由に引用した特開平５−１６５４０６号公報（以下、「引用例１」という。）には、「デジタル地図データとしては、図３に示すような実際の道路形状を、図４に示すように線分によって折線近似したときの各線分の端点および接続点からなるノードＮの位置およびノード間の接続状態に関するデータからなっている。　図４からもわかるように、道路のカーブ部分ではその曲率に応じて短い線分によって細かくデジタル化されることになる。」（２頁左欄２９行乃至３６行）、「従来、デジタル地図データにもとづいて経路探索を行わせるには、例えばＤｉｊｋｓｔｒａ法などの公知のアルゴリズムにしたがって出発点から目的地に到るまでの最短の経路探索を行わせる」（２頁左欄３７行乃至４０行）、「デジタル地図データからその道路地図上における各道路端点および各交差点のノードなどの経路探索のために必要最小限となるノードに関するデータのみを抽出して、各道路端点および各交差点の接続間を結んだ経路用地図データを新たに作成したうえで、その作成された経路用地図データにしたがって経路探索を行わせるようにしている。」（２頁右欄１５行乃至２１行）、「予めデジタル地図データによる道路地図情報が記憶されている地図情報記憶媒体５と、その記憶媒体５から必要なエリアの道路地図情報を選択的に読み出す記憶媒体再生装置６と、その読み出された道路地図情報にもとづいて所定の道路地図を画面に写し出すとともに、その画面に写し出された道路地図上に、車両の現在位置を、必要に応じて走行軌跡および現在位置における車両の進行方向などとともに、車両の走行にしたがって更新的に表示させる表示装置７」（２頁右欄３７行乃至４６行）、「本発明はこのような車両走行案内装置にあって、信号処理装置３において、デジタル地図データにもとづいて、画面に写し出される道路地図上に設定された出発点から目的地に到るまでの経路を探索して、所要距離や一方通行などの道路情報を加味した最適経路の決定を行い、例えば画面に写し出される道路地図上における最適経路を特別な色で示すなどして、その最適経路上に車両の現在位置が更新表示されていくように車両の走行案内を行わせることができるようにしている。　その際、特に本発明では、図５に示すように、道路地図上に設定された出発点Ｓから目的地Ｏに到るまでの経路を探索する場合、交差点Ｉ１，Ｉ２，Ｉ３，．．．，Ｉｎの各間におけるノードＮを何ら考慮することなく、経路上にある交差点Ｉ１，Ｉ２，Ｉ３，…，Ｉｎに対応するノードのみを次々とたどっていけば経路探索を行わせることができることに着目し、信号処理装置３において、地図情報記憶媒体５から読み出されたデジタル地図データからその道路地図上における各道路端点および各交差点のノードに関するデータのみを抽出して、各道路端点および各交差点の接続間を結んだ経路用地図データを新たに作成したうえで、その作成された経路用地図データにしたがって経路探索を行わせるようにしている。」（３頁左欄２０行乃至４２行）及び「以上、本発明による車両走行案内装置にあっては、デジタル地図データからその道路地図上における各道路端点および各交差点のノードに関するデータのみを抽出して、各道路端点および各交差点の接続間を結んだ経路用地図データを新たに作成したうえで、その各道路端点および各交差点の接続関係が何ら変化することなくデータ量だけが有効に軽減された経路用地図データをもって、出発点から目的地に到るまでの経路上にある交差点のノードを次々とたどっていくことにより、ノード追跡のための処理の軽減化を有効に図りながら経路探索を正確にかつ迅速に行わせることができるという利点を有している。」（３頁右欄１２行乃至２３行）との記載並びに図１乃至図７の記載がされている。
　ここで、デジタル地図データの「図４に示すように線分によって接線近似したときの各線分の端点及び接続点からなるノードＮの位置およびノード間の接続状態に関するデータ」（２頁左欄３０行乃至３３行）において、「道路地図上における各道路端点及び各交差点のノードなどの経路探索のために必要最小限となるノードに関するデータ」（２頁右欄１６行乃至１７行）については「少なくとも道路の交差点または行止まりを示すノードに関するノードデータ」といえ、これ以外のノードに関するデータは「道路の形状を折線近似した折点を示す補間ノードに関する補間ノードデータ」といえる。　また、「各道路端点および各交差点の接続点間を結んだ経路用地図データ」（２頁右欄１８行乃至１９行）については、ダイクストラ法などの公知のアルゴリズムにより経路探索を行う場合にリンクのデータを用いることが通常行われている（例えば、後記の引用例２等を参照。）のであるから、前記ノードデータのみならず、「ノードを連結するリンクに関するリンクデータ」を有しているものと認められる。　そして、経路用地図データはデジタル地図データから作成されているのであるから、デジタル地図データの「ノード間の接続状態に関するデータ」については、「補間ノードを連結する補間リンクに関する補間リンクデータ」を有しているといえると共に、ノード間に補間ノードを有さない場合の「ノードを連結するリンクに関するリンクデータ」を有しているといえる。
　よって、これらの記載によれば、引用例１には「２点間の経路（出発点から目的地に到るまでの経路）を地図データに基づいて経路探索を行う車両走行案内装置において、
　少なくとも道路の交差点または行止まりを示すノードに関するノードデータと、前記ノードを連結するリンクに関するリンクデータと、道路の形状を折線近似した折点を示す補間ノードに関する補間ノードデータと、前記補間ノードを連結する補間リンクに関する補間リンクデータとから成るデジタル地図データを含む地図情報記憶媒体と、
　前記地図情報記憶媒体のデジタル地図データから、道路の交差点または行止まりを示すノードに関するノードデータと、前記ノードを連結するリンクに関するリンクデータとから成る経路用地図データを作成し、該経路用地図データに基づき経路探索を行う経路探索手段と、
　前記経路探索手段が経路用地図データに基づいて探索した経路を地図上に表示する表示手段と、
　前記地図情報記憶媒体のデジタル地図データに基づいて地図を表示する表示手段とを備えた地図情報記憶媒体を用いた車両走行案内装置。」（以下、「引用発明１」という。）が開示されているものと認められる。
　同じく、当審が通知した取消理由に引用した特開平６−２８８７８２号公報（以下、「引用例２」という。）には、「本発明は、指定された道路地図上の２点間を走行する場合の最適経路を計算する機能を備えた経路探索装置に関するものである。」（２頁右欄４行乃至６行）、「事前に装填されている地図専用ディスクＤ１から車両現在地に対応する表示用道路地図データを読み出し、コントローラ７へ出力する。コントローラ７は、ロケータ５で算出された現在地データと、メモリドライブ８から与えられる表示用道路地図データとを表示装置１０へ与え、地図とその地図上における車両現在地マークとを生成させ、表示させる。」（３頁右欄３４行乃至４１行）、「また、メモリドライブ８は、コントローラ７から与えられる制御信号に応答して、事前に装填されている経路計算ディスクＤ２から経路計算のための経路計算用リンクデータを読み出し、コントローラ７へ出力する。コントローラ７は、現在地から目的地までの最適経路の計算をし、表示地図上の座標を求め、最適経路を表示させる。　ここに、経路計算用リンクデータは、道路地図（高速自動車国道、自動車専用道路、国道、都道府県道、指定都市の市道、その他の生活道路を含む。）をメッシュ状に分割し、各メッシュ単位でノードとリンクとの組み合わせからなるデータを記憶している。地図データベースの特性上、幹線道路のうち国道以上の道路については全国的に閉じたネットワークが形成されている。　ここに、ノードとは、一般に、道路の交差点、道路の折曲点、メッシュの境界、行き止まり点などを特定するための座標点のことである。　各ノードをつないだものがリンクである。リンクデータはリンク番号、リンクの始点ノード及び終点ノードのアドレス、リンクの距離、リンクを通過する方向、その方向における所要時間、道路の種類若しくは種別、道路幅、一方通行、右折禁止、左折禁止、有料道路などのデータ等を含む。　なお、表示用道路地図データは、２５００分の１の地図データベースから作成されたもので、道路、地名、有名施設、鉄道、川等を特定する地図データ等で構成されている。」（３頁右欄４２行乃至４頁左欄１８行）及び「そして、この経路計算領域の中で計算開始リンクと計算終了リンクとの間の最適経路を計算する（図３、ステップＳ５）。すなわち、最適経路計算処理部は、経路計算ディスクＤ２から読み出された経路計算用リンクデータに基づき、ダイクストラ法等（実施例では、ダイクストラ法の一種であるポテンシャル法を採用している）により現在地から目的地までの最適経路の計算を行う。このポテンシャル法は、目的地又は現在地に最も近いリンクを計算開始リンクとし、現在地又は目的地に最も近いリンクを計算終了リンクとし、計算開始リンクから計算終了リンクに至るリンクコストを順次加算してリンクのツリーを構成していき、計算終了リンクに到達する最もリンクコストの少ない経路のみを選択する方法である。ここでリンクコストを見積もるときに考慮すべき事項（評価関数）として、走行距離、走行時間、高速道路の利用の有無、右折左折回数、幹線道路の走行確率、事故多発地帯回避、その他運転者の好みに応じて設定された事項がある。　得られた最適経路は、リンク?座��変換テーブルを参照して、該当する座標列に変換される（ステップＳ６）。そして、表示要求があれば（ステップＳ７）、表示しようとする道路地図の範囲に含まれる最適経路を構成する座標列が、道路地図とともに読み出され、表示装置１２に表示される（ステップＳ８）。表示は、例えば座標間をドット、太線、破線等で結ぶことにより行われる。」（５頁左欄９行乃至３４行）との記載並びに図１乃至図３の記載がされている。
　同じく、当審が通知した取消理由に引用した特開平２−１７２０００号公報（以下、「引用例３」という。）には、「第１発明は、第１図（ａ）に示すように、　・・・（中略）・・・　経路データ記憶手段は、ノード及び枝で構成される、例えば、道路地図、回路等の最短経路探索の対象となる経路データを記憶する手段である。　・・・（中略）・・・　双方向探索手段は、位置入力手段により入力された探索開始位置及び探索終了位置の双方向から経路データを用いて順次ノード又は枝を検索して最短経路を探索する手段である。最短経路は経路長、所要時間、費用等やこれらの量を総合評価した評価値が最小となる経路として定義される。　・・・（中略）・・・　表示手段は、その最短経路を表示する手段である。例えば、道路地図を表示すると共に、その道路地図上に探索開始位置である現在位置と探索終了位置である目的位置と、その両位置を結ぶ最短経路とを表示する手段である。」（３頁右上欄１１行乃至右下欄８行）、「経路データ記憶手段はノード及び枝の情報及び枝の優先度を示す等級データを記憶するものである。　又、縮退探索手段は、順次探索される探索ノード又は探索枝を、その等級データにより制限する手段である。この等級は、例えば、道幅や車線数及び高速道路、国道、県市町村道などの道路等級等で区別されるような枝の優先度を示すものである。したがって、選択枝の等級を所定の条件で制限するということは、例えば、広い国道に沿って１つの経路が探索されている場合に、その国道に接続されている狭い脇道等は探索の対象から除外され、その脇道に接続される枝はそれ以上探索されないことを意味しており、探索速度が向上する。」（４頁左上欄２０行乃至右上欄１３行）、「第２図は本発明の実施例に係る車載ナビゲーション装置１０の構成を示すものである。　・・・（中略）・・・　図において、コンピュータ２０はデータ記憶媒体２１をアクセスして、最短経路探索演算等を実行する装置である。　・・・（中略）・・・　記憶媒体２１は、フロピィディスク、ハードディスク若しくはＲＡＭディスク等で構成される。その記憶媒体２１には地図データベースと探索プログラムが記憶され、探索過程データや探索結果データを記憶する探索データファイルが形成されている。」（５頁右上欄５行乃至１８行）、「地図はノードを中心に構成しても各（リンク）を中心に構成してもよい。ノードを中心として構成される地図データベースは次の情報で構成されている。　・・・（中略）・・・　この記憶された地図データベースは地理的に所与の領域を移動するときに使用される。」（６頁左上欄１５行乃至右上欄１１行）、「車両が、ある地点からある地点へ移動する時、コンピュータ２０が適切な地図を呼び出し、ＣＲＴディスプレイ４１に表示することができる。推測航法を備えた車載ナビゲーション装置では車両の移動軌跡を推測でき、これを表示中の地図に重ね書きすることができる。又、後に述べる経路探索アルゴリズムによって得られる最短経路を表示中の地図に重ね書きすることができる。」（６頁右上欄１２行乃至１９行）、「経路探索が終了した時点の探索結果データはトランジェントな探索データファイルとして記憶媒体２１に記憶される。そして、探索データファイルは探索枝を展開するノードファイルとで構成される。」（６頁左下欄３行乃至５行）、「メインプログラムはコンピュータによって処理される全ての情報に応答して、必要なデータを計算しフォーマット化する。例えば、ＣＲＴディスプレイ４１に表示され選択される地図のデータ、現在位置及び目的位置のコマンドデータ、最短経路探索プログラムに与える現在位置と目的位置を示す地点コードと探索モード等を計算し処理する。」（７頁左上欄２０行乃至右上欄６行）、「縮退探索は、探索の際、探索枝を順次道路等級の等しいか、又は高い方へ上げながら、優先順位の低い道路枝をカットし、縮退した道路網により探索を行うものである。これにより、例えば、道路幅の広い国道等に沿って探索が実行されている時、その国道に接続される道幅の狭い脇道等へ探索枝が伸びることが防止され、効率のよい探索が行われる。道路等級は任意に設定でき、例えば市町村道、県道、国道、高速道路の順に等級を設定することでも良い。この他の、道路巾の大小、設計交通容量、設計速度、有料道路と無料道路の違いによって等級を設定することもできる。道路等級により縮退を行うと、等級が上がるに従いネットワークが粗となり、経路の跡切れを生じる場合があるので、跡切れを避けるため、前の選択枝のｎランク下位の等級まで接続を認めるようにする。」（８頁左下欄９行乃至右下欄４行）及び「又、第３発明は、双方向探索過程において探索される探索ノード又は探索枝を、枝の優先度を示す等級データに基づいて制限しているので、経路探索が等級の高い枝に接続された等級の低い枝への経路探索が防止されるため、極めて効率の高い探索が可能となり最短経路探索時間が短縮される。」（１４頁右上欄１０行乃至１７行）との記載並びに第１図（ａ）乃至第２図の記載によれば、引用例３には「記憶媒体（経路データ記憶手段）であって、
　道路の接続関係を表す道路データを含んで構成される地図データベース（経路データ）を記憶する記憶媒体と、
　記憶媒体に記憶されている地図データベースに基づいて、所定の地域の地図画面を表示する表示手段とを備える記憶媒体を用いた表示装置。」（以下、「引用発明２」という。）及び「指定された２地点間の経路（探索開始位置である現在位置と探索終了位置である目的位置とを結ぶ経路）を、記憶されている地図データベース（経路データ）に基づいて経路探索を行う経路探索装置において、
　記憶媒体（経路データ記憶手段）であって、
　道路の接続関係を表す道路データを含んで構成される地図データベースを記憶する記憶媒体と、
　前記記憶媒体から地図データベースを読出し、読出した地図データベースに基づいて、複数種類の道路に予め定められた選択規則に従って設定された等級により、探索枝を順次道路等級の等しいか、又は高い方へ上げながら、優先順位の低い探索枝をカットすると共に、道路が寸断されることがないように下位の等級の探索枝の接続を認めるようにして、前記２地点間の経路探索を行う探索手段と、
　前記記憶媒体に記憶されている地図データベースに基づいて、地図画面を表示し、その地図画面上に前記探索手段が探索した経路を表示する表示手段とを備えることを特徴とする記憶媒体を用いた経路探索装置。」（以下、「引用発明３」という。）が開示されているものと認められる。
　３．対比・判断
（１）請求項１に係る発明について
　本件請求項１に係る発明と引用発明１とを対比すると、引用発明１における「車両走行案内装置」、「デジタル地図データ」、「地図情報記憶媒体」及び「経路用地図データ」は、それぞれ本件請求項１に係る発明の「経路探索装置」、「第１地図データ」、「地図データ記憶媒体」及び「第２地図データ」に相当するものといえるから、両者は、「２点間の経路を地図データに基づいて経路探索を行う経路探索装置において、
　少なくとも道路の交差点または行止まりを示すノードに関するノードデータと、前記ノードを連結するリンクに関するリンクデータと、道路の形状を折線近似した折点を示す補間ノードに関する補間ノードデータと、前記補間ノードを連結する補間リンクに関する補間リンクデータとから成る第１地図データを含む地図データ記憶媒体と、
　道路の交差点または行止まりを示すノードに関するノードデータと、前記ノードを連結するリンクに関するリンクデータとから成る第２地図データに基づき経路探索を行う経路探索手段と、
　前記経路探索手段が第２地図データに基づいて探索した経路を地図上に表示する表示手段とを備えることを特徴とする地図データ記憶媒体を用いた経路探索装置。」である点で一致し、次の点で相違するものと認められる。
（相違点１）第２地図データが、本件請求項１に係る発明では、地図データ記憶媒体に含まれているのに対して、引用発明１では、地図データ記憶媒体に含まれている第１地図データから作成される点。
（相違点２）探索した経路を、本件請求項１に係る発明では、地図データ記憶媒体の第１地図データに基づいて地図上に表示するものであるのに対して、引用発明１では、第１地図データに基づいて地図上に表示するものであるのか否か明らかでない点。
　そこで、前記相違点について検討する。
（相違点１について）
　地図データ記憶媒体を用いた経路探索装置において、経路探索用の第２地図データを表示用の第１の地図データと同じく予め地図データ記憶媒体に含むことは周知（必要であれば、引用例２、特開平４−３２１０９０号公報、特開平６−１１９５６２号公報及び特開平４−２８０２８７号公報を参照。）であり、また、地図データ記憶媒体に表示用の第１の地図データと共に経路探索用の第２地図データを含むことも周知（必要であれば、特開平４−３２１０９０号公報、特開平６−１１９５６２号公報及び特開平４−２８０２８７号公報を参照。）であるから、第２地図データを第１地図データから作成することに代え、予め第２地図データを第１地図データと共に地図データ記憶媒体に含むようにすること、すなわち、本件請求項１に係る発明の前記相違点１に係る構成とすることは当業者が容易に想到し得たものと認められる。
（相違点２について）
　引用発明１において、探索した経路を地図上に表示するのに、第１地図データに基づいて表示するか第２地図データに基づいて表示するかの２通りが考えられるが、地図は第１地図データに基づき表示されていることから、経路を第１地図データに基づき地図上に表示した方が経路を第２地図データに基づき地図上に表示した場合に比べて経路と地図の整合性がとれて見やすいことは当業者であれば容易に認識し得るものと認められる。
　してみれば、探索した経路を第１地図データに基づいて地図上に表示すること、すなわち、本件請求項１に係る発明の前記相違点２に係る構成は当業者が容易に想到し得たものと認められる。
　そして、本件請求項１に係る発明が奏する効果は、引用例１に記載された事項及び周知の事項から当業者が予測し得る範囲のものと認められる。
　なお、特許権者は平成１３年１月２９日付け特許異議意見書により、「本件請求項１に係る発明は、記憶媒体に経路探索専用の地図データを準備しておくことにより、（ａ）経路探索用の地図を作成する時間は必要なくなる。また、（ｂ）経路探索用の地図データだけを取り込むので、一度に広いエリアをカバーすることができる。その結果、経路探索にかかる時間が見かけ上、短縮される。」（５頁５行乃至９行）旨主張しているが、（ａ）については前記周知の事項によれば経路探索用の第２地図データを地図データ記憶媒体に有しており、経路探索用の地図を作成する必要はないのであるから、当業者が予測し得る効果と認められる。また、（ｂ）については訂正された明細書の記載に基づくものではなく、当該主張は採用することができない。
　よって、本件請求項１に係る発明は、引用例１に記載された事項及び周知の事項に基づいて当業者が容易に発明することができたものである。
（２）請求項２に係る発明について
　本件請求項２に係る発明と引用発明１とを対比すると、引用発明１における「車両走行案内装置」、「デジタル地図データ」、「地図情報記憶媒体」及び「経路用地図データ」は、それぞれ本件請求項１に係る発明の「経路探索装置」、「第１地図データ」、「地図データ記憶媒体」及び「第２地図データ」に相当するものといえるから、両者は、「２点間の経路を地図データに基づいて経路探索を行う経路探索装置において、
　少なくとも道路の交差点または行止まりを示すノードに関するノードデータと、前記ノードを連結するリンクに関するリンクデータと、道路の形状を折線近似した折点を示す補間ノードに関する補間ノードデータと、前記補間ノードを連結する補間リンクに関する補間リンクデータとから成る第１地図データを含む地図データ記憶媒体と、
　道路の交差点または行止まりを示すノードに関するノードデータと、前記ノードを連結するリンクに関するリンクデータとから成る第２地図データに基づき経路探索を行う経路探索手段と、
　前記経路探索手段が第２地図データに基づいて探索した経路を地図上に表示する表示手段と、
　前記地図データ記憶媒体の第１地図データに基づいて地図を表示する表示手段とを備えた地図データ記憶媒体を用いた経路探索装置。」である点で一致し、本件請求項１に係る発明についての検討で示した前記相違点１及び２と同じ相違点で相違するものと認められる。
　そして、本件請求項２に係る発明の前記相違点１及び２と同じ相違点に係る構成については、本件請求項１に係る発明についての検討で述べたとおり当業者が容易に想到し得たものと認められ、本件請求項２に係る発明が奏する効果も引用例１に記載された事項及び周知の事項から当業者が予測し得る範囲のものと認められる。
　よって、本件請求項２に係る発明は、引用例１に記載された事項及び周知の事項に基づいて当業者が容易に発明することができたものである。
（３）請求項３に係る発明について
　本件請求項３に係る発明と引用発明１とを対比すると、引用発明１における「車両走行案内装置」、「デジタル地図データ」、「地図情報記憶媒体」及び「経路用地図データ」は、それぞれ本件請求項１に係る発明の「経路探索装置」、「第１地図データ」、「地図データ記憶媒体」及び「第２地図データ」に相当するものといえるから、両者は、「２点間の経路を地図データに基づいて経路探索を行う経路探索装置において、
　少なくとも道路の交差点または行止まりを示すノードに関するノードデータと、前記ノードを連結するリンクに関するリンクデータと、道路の形状を折線近似した折点を示す補間ノードに関する補間ノードデータと、前記補間ノードを連結する補間リンクに関する補間リンクデータとから成る第１地図データを含む地図データ記憶媒体と、
　道路の交差点または行止まりを示すノードに関するノードデータと、前記ノードを連結するリンクに関するリンクデータとから成る第２地図データに基づき経路探索を行う経路探索手段とを備えた地図データ記憶媒体を用いた経路探索装置。」である点で一致し、本件請求項１に係る発明についての検討で示した前記相違点１及び２と同じ相違点に加え、次の点で相違するものと認められる。
（相違点３）
　第２地図データのリンクデータには、本件請求項３に係る発明では、リンクに対応する道路の属性及び経路コストに関するデータが含まれているのに対して、引用発明１では、リンクに対応する道路の属性及び経路コストに関するデータが含まれているのか否か明らかでない点。
　本件請求項３に係る発明の前記相違点１及び２と同じ相違点に係る構成については、本件請求項１に係る発明についての検討で述べたとおり当業者が容易に想到し得たものと認められ、以下、相違点３について検討する。
　地図データ記憶媒体を用いた経路探索装置において、経路探索用の地図データに、リンクに対応する道路の属性および経路コストに関するデータが含まれることは引用例２に記載されているものと認められ、引用発明１及び引用例２に記載の事項は共に、ダイクストラ法などの公知のアルゴリズムにより経路探索を行う技術分野において共通するものであるから、引用発明１に前記引用例２に記載の事項を適用し、引用発明１における第２地図データのリンクデータに、リンクに対応する道路の属性および経路コストに関するデータが含まれるようにすること、すなわち、本件請求項３に係る発明の前記相違点３に係る構成は当業者が容易に想到し得たものと認められる。
　なお、特許権者は平成１３年１月２９日付け特許異議意見書により、「引用例２に開示されている経路探索装置は、段落［００１７］に示されるデータから運転者の好みなどによって、コストを決定するものである。すなわち、記憶媒体に記憶されている探索用データ自体には実質的にはコストデータは含まれておらず、一定のルール（運転者の好み）に従ってコストを求める構成である。したがって、引用例２に経路コストに関するデータが予め地図データに含まれていることが記載されているという認定には承服できない。」（７頁４行乃至１０行）旨を主張している。
　しかしながら、本件の訂正された明細書には、「始点から探索点までの経路長や自動車が移動する際の所要時間などを示す経路コスト」（８頁２３行乃至２４行）及び「この経路コストには、構成リンクＬａに対応する道路の区間の実距離、またはその道路の区間を実際に自動車が通過する際の推定の所要時間が登録される。」（１８頁１５行乃至１７行）との記載がされており、これらの記載によれば本件請求項３に係る発明は経路コストを経路の距離または所要時間とすることを含むものと認められるところ、引用例２には、リンクコストを見積もるときに考慮すべき事項として走行距離または走行時間があることが記載されている（５頁左欄２２行乃至２６行）と共に、該走行距離又は走行時間に関するリンクの距離やリンクを通過する方向における所要時間を経路計算用リンクデータとして記憶媒体である経路計算ディスクＤ２に記憶することが記載されている（３頁右欄４２行乃至４頁左欄１４行）のであるから、経路コストに関するデータが予め経路探索用の地図データに含まれていることが記載されているものといえる。また、「経路コストに関するデータ」には、経路コスト自体のデータのみでなく、経路コストを算出するのに用いるデータも含まれるものと解釈できることからも、引用例２には経路コストに関するデータが予め経路探索用の地図データに含まれていることが記載されているものといえ、当該主張は採用することができない。
　そして、本件請求項３に係る発明が奏する効果も引用例１及び２に記載された事項並びに周知の事項から当業者が予測し得る範囲のものと認められる。
　よって、本件請求項３に係る発明は、引用例１及び２に記載された事項並びに周知の事項に基づいて当業者が容易に発明することができたものである。
（４）請求項４に係る発明について
　本件請求項４に係る発明と引用発明１とを対比すると、引用発明１における「車両走行案内装置」、「デジタル地図データ」、「地図情報記憶媒体」及び「経路用地図データ」は、それぞれ本件請求項１に係る発明の「経路探索装置」、「第１地図データ」、「地図データ記憶媒体」及び「第２地図データ」に相当するものといえるから、両者は、「２点間の経路を地図データに基づいて経路探索を行う経路探索装置において、
　少なくとも道路の交差点または行止まりを示すノードに関するノードデータと、前記ノードを連結するリンクに関するリンクデータと、道路の形状を折線近似した折点を示す補間ノードに関する補間ノードデータと、前記補間ノードを連結する補間リンクに関する補間リンクデータとから成る第１地図データを含む地図データ記憶媒体と、
　道路の交差点または行止まりを示すノードに関するノードデータと、前記ノードを連結するリンクに関するリンクデータとから成る第２地図データに基づき経路探索を行う経路探索手段と、
　前記経路探索手段が第２地図データに基づいて探索した経路を地図上に表示する表示手段とを備えた地図データ記憶媒体を用いた経路探索装置。」である点で一致し、本件請求項１に係る発明についての検討で示した前記相違点１及び２並びに本件請求項３に係る発明についての検討で示した前記相違点３と同じ相違点で相違するものと認められる。
　そして、本件請求項４に係る発明の前記相違点１及び２と同じ相違点に係る構成については、本件請求項１に係る発明についての検討で述べたとおり当業者が容易に想到し得たものと認められると共に、本件請求項４に係る発明の前記相違点３と同じ相違点に係る構成については、本件請求項３に係る発明についての検討で述べたとおり当業者が容易に想到し得たものと認められ、本件請求項４に係る発明が奏する効果も引用例１及び２に記載された事項並びに周知の事項から当業者が予測し得る範囲のものと認められる。
　よって、本件請求項４に係る発明は、引用例１及び２に記載された事項並びに周知の事項に基づいて当業者が容易に発明することができたものである。
（５）請求項５に係る発明について
　本件請求項５に係る発明と引用発明２とを対比すると、引用発明２における「記憶媒体（経路データ記憶手段）」及び「地図データベース（経路データ）」は、それぞれ本件請求項５に係る発明の「地図データ記憶媒体」及び「地図データ」に相当するものといえるから、両者は、「地図データ記憶媒体であって、
　道路の接続関係を表す道路データとを含んで構成される地図データを記憶する地図データ記憶媒体と、
　地図データ記憶媒体に記憶されている地図データに基づいて、所定の地域の地図画面を表示する表示手段とを備える地図データ記憶媒体を用いた表示装置。」である点で一致し、次の点で相違するものと認められる。
（相違点４）複数種類の道路のうちから予め定められた選択規則に従って選別された道路の接続関係を表す第１道路データと、選別された道路が選別によって寸断されることがないように、前記複数種類の道路のうちから選別された道路の接続関係を表す第２道路データとを含んで構成される地図データが、本件請求項５に係る発明では、地図データ記憶媒体に記憶されているのに対して、引用発明２では、そのような地図データが地図データ記憶媒体に記憶されていない点。
　そこで、前記相違点４について検討すると、地図データ記憶媒体を用いた表示装置において、複数種類の道路のうちから予め定められた選択規則に従って選別された道路の接続関係を表す第１道路データと、選別された道路が選別によって寸断されることがないように、前記複数種類の道路のうちから選別された道路の接続関係を表す第２道路データとを含んで構成される地図データを地図データ記憶媒体に記憶することは周知（必要であれば、特開平５−２３２８７５号公報、特開平４−３６５０８８号公報及び特開平６−１１９５６２号公報を参照。）であり、これを引用発明２に採用することができないという事情は認められないのであるから、複数種類の道路のうちから予め定められた選択規則に従って選別された道路の接続関係を表す第１道路データと、選別された道路が選別によって寸断されることがないように、前記複数種類の道路のうちから選別された道路の接続関係を表す第２道路データとを含んで構成される地図データを地図データ記憶媒体に記憶すること、すなわち、本願請求項５に係る発明の前記相違点４に係る構成は当業者が容易に想到し得たものと認められる。
　なお、特許権者は平成１３年１月２９日付け特許異議意見書により、「本件の第２道路データは、選別された道路の接続関係を示すものであって、第１道路データの下層に相当するデータとは異なるものである。つまり、第１道路データが国道および高速道路からなるデータであった場合、本件の第２道路データは選別された国道などを接続する県道や主要地方道の一部からなるデータとなるのであり、県道や主要地方道以上の全ての道路からなるデータとは異なるものである。」（８頁２１行乃至２６行）旨を主張している。
　しかしながら、前記周知の事項の例示文献として挙げた各刊行物（以下、「周知文献」という。）に開示された第２道路データが第１道路データの下層に相当するデータであるとしても、第２道路データにおいて第１道路データに係る道路は寸断されないように接続されている（このことは、前記周知文献において、第１道路データを用いたのでは経路探索できない場合に第２道路データを用いて経路探索することが開示されていることからも理解できる。）のであるから、第２道路データを「選別された道路が選別によって寸断されることがないように、前記複数種類の道路のうちから選別された道路の接続関係を表す第２道路データ」として解釈することができるのであって、当該主張は採用することができない。
　そして、本件請求項５に係る発明が奏する効果は、引用例３に記載の事項及び周知の事項から当業者が予測し得る範囲のものである。
　よって、本件請求項５に係る発明は、引用例３に記載の事項及び周知の事項に基づき、当業者が容易に発明することができたものと認められる。
（６）請求項６に係る発明について
　本件請求項５に係る発明と引用発明３とを対比すると、引用発明３における「地図データベース（経路データ）」及び「記憶媒体（経路データ記憶手段）」及びは、それぞれ本件請求項５に係る発明の「地図データ記憶媒体」及び「地図データ」に相当するものといえるから、両者は、「指定された２地点間の経路を、記憶されている地図データに基づいて経路探索を行う経路探索装置において、
　地図データ記憶媒体であって、
　道路の接続関係を表す道路データを含んで構成される地図データを記憶する地図データ記憶媒体と、
　前記地図データ記憶媒体から地図データを読出し、読出した地図データに基づいて前記２地点間の経路探索を行う探索手段と、
　前記地図データ記憶媒体に記憶されている地図データに基づいて、地図画面を表示し、その地図画面上に前記探索手段が探索した経路を表示する表示手段とを備える地図データ記憶媒体を用いた経路探索装置。」である点で一致し、本件請求項５に係る発明についての検討で示した前記相違点４と同じ相違点で相違するものと認められる。
　そこで、前記相違点４について検討すると、地図データ記憶媒体を用いた経路探索装置において、複数種類の道路のうちから予め定められた選択規則に従って選別された道路の接続関係を表す第１道路データと、選別された道路が選別によって寸断されることがないように、前記複数種類の道路のうちから選別された道路の接続関係を表す第２道路データとを含んで構成される地図データを地図データ記憶媒体に記憶し、該地図データ記憶手段から読出した地図データに基づいて２地点間の経路探索を行うことは周知（必要であれば、特開平５−２３２８７５号公報、特開平４−３６５０８８号公報、特開平４−８８６００号公報及び特開平６−１１９５６２号公報を参照。）であり、引用発明３において、２地点間の経路探索を行うにあたり、複数種類の道路に予め定められた選択規則に従って設定された等級により、探索枝を順次道路等級の等しいか、又は高い方へ上げながら、優先順位の低い探索枝をカットすると共に、道路が寸断されることがないように下位の等級の探索枝の接続を認めるようにした（以下、「縮退探索に係る構成」という。）のは、上位の道路データを優先的に経路探索に用いると共に、上位の道路データでは経路探索が不可能な場合に下位の道路データを経路探索に用いることにより、経路探索時間を短縮するためと認められるところ、この点において前記周知の事項は共通するものと認められるのであるから、引用発明３における前記縮退探索に係る構成の代わりに前記周知の事項を採用し、複数種類の道路のうちから予め定められた選択規則に従って選別された道路の接続関係を表す第１道路データと、選別された道路が選別によって寸断されることがないように、前記複数種類の道路のうちから選別された道路の接続関係を表す第２道路データとを含んで構成される地図データを地図データ記憶媒体に記憶すること、すなわち、本願請求項６に係る発明の前記相違点４に係る構成は当業者が容易に想到し得たものと認められる。
　そして、本件請求項６に係る発明が奏する効果は、引用例３に記載の事項及び周知の事項から当業者が予測し得る範囲のものである。
　よって、本件請求項６に係る発明は、引用例３に記載の事項及び周知の事項に基づき、当業者が容易に発明することができたものと認められる。
　４．むすび
　以上のとおりであるから、本件請求項１乃至６に係る発明は、特許法第２９条第２項の規定により特許を受けることができない。
　したがって、本件請求項１乃至６に係る発明についての特許は拒絶の査定をしなければならない特許出願に対してされたものと認める。
　よって、特許法等の一部を改正する法律（平成６年法律第１１６号）附則第９条第４項及び第７項並びに第１４条の規定に基づく、特許法等の一部を改正する法律の施行に伴う経過措置を定める政令（平成７年政令第２０５号）第４条第１項及び第２項の規定により、結論のとおり決定する。
【異議決定日】
平成１３年３月５日（２００１．３．５）
【訂正の要旨】
　訂正の要旨
訂正Ａ：
　特許第３００７８０３号発明の明細書中特許請求の範囲の請求項１乃至４を、特許請求の範囲の減縮を目的として、
「　【請求項１】　２点間の経路を地図データに基づいて経路探索を行う経路探索装置において、
　（ａ）少なくとも道路の交差点または行止まりを示すノードに関するノードデータと、前記ノードを連結するリンクに関するリンクデータと、道路の形状を折線近似した折点を示す補間ノードに関する補間ノードデータと、前記補間ノードを連結する補間リンクに関する補間リンクデータとから成る第１地図データと、
　道路の交差点または行止まりを示すノードに関するノードデータと、前記ノードを連結するリンクに関するリンクデータとから成る第２地図データとを含む地図データ記憶媒体と、
　（ｂ）前記地図データ記憶媒体の第２地図データに基づき経路探索を行う経路探索手段と、
　（ｃ）前記経路探索手段が第２地図データに基づいて探索した経路を、前記地図データ記憶媒体の第１地図データに基づいて地図上に表示する表示手段とを備えることを特徴とする地図データ記憶媒体を用いた経路探索装置。
　【請求項２】　前記地図データ記憶媒体の第１地図データに基づいて地図を表示する表示手段を備えることを特徴とする請求項１記載の地図データ記憶媒体を用いた経路探索装置。
　【請求項３】　２点間の経路を地図データに基づいて経路探索を行う経路探索装置において、
　（ａ）少なくとも道路の交差点または行止まりを示すノードに関するノードデータと、前記ノードを連結するリンクに関するリンクデータと、道路の形状を折線近似した折点を示す補間ノードに関する補間ノードデータと、前記補間ノードを連結する補間リンクに関する補間リンクデータとから成る第１地図データと、
　道路の交差点または行止まりを示すノードに関するノードデータと、前記ノードを連結するリンクに関するリンクデータとから成る第２地図データとを含む地図データ記憶媒体と、
　（ｂ）前記地図データ記憶媒体の第２地図データに基づき経路探索を行う経路探索手段とを備え、
　前記地図データ記憶媒体が記憶する第２地図データのリンクデータには、リンクに対応する道路の属性および経路コストに関するデータが含まれていることを特徴とする地図データ記憶媒体を用いた経路探索装置。
　【請求項４】　２点間の経路を地図データに基づいて経路探索を行う経路探索装置において、
　（ａ）少なくとも道路の交差点または行止まりを示すノードに関するノードデータと、前記ノードを連結するリンクに関するリンクデータと、道路の形状を折線近似した折点を示す補間ノードに関する補間ノードデータと、前記補間ノードを連結する補間リンクに関する補間リンクデータとから成る第１地図データと、
　道路の交差点または行止まりを示すノードに関するノードデータと、前記ノードを連結するリンクに関するリンクデータとから成る第２地図データとを含む地図データ記憶媒体と、
　（ｂ）前記地図データ記憶媒体の第２地図データに基づき経路探索を行う経路探索手段と、
　（ｃ）前記経路探索手段が第２地図データに基づいて探索した経路を、前記地図データ記憶媒体の第１地図データに基づいて地図上に表示する表示手段とを備え、
　前記地図データ記憶媒体が記憶する第２地図データのリンクデータには、リンクに対応する道路の属性および経路コストに関するデータが含まれていることを特徴とする地図データ記憶媒体を用いた経路探索装置。」と訂正する。
訂正Ｂ：
　特許第３００７８０３号発明の明細書中段落【０００８】における「本発明は、２点間の経路を地図データに基づいて経路探索を行う経路探索装置において、
　（ａ）少なくとも道路の交差点または行止まりを示すノードに関するノードデータと、前記ノードを連結するリンクに関するリンクデータと、道路の形状を折線近似した折点を示す補間ノードに関する補間ノードデータと、前記補間ノードを連結する補間リンクに関する補間リンクデータとから成る第１地図データと、
　道路の交差点または行止まりを示すノードに関するノードデータと、前記ノードを連結するリンクに関するリンクデータとから成る第２地図データとを含む地図データ記憶媒体と、
　（ｂ）前記地図データ記憶媒体の第２地図データに基づき経路探索を行う経路探索手段とを備えることを特徴とする地図データ記憶媒体を用いた経路探索装置である。
　また本発明は、前記経路探索手段が第２地図データに基づいて探索した経路を、前記地図データ記憶媒体の第１地図データに基づいて地図上に表示する表示手段を備えることを特徴とする。
　また本発明は、前記地図データ記憶媒体の第１地図データに基づいて地図を表示する表示手段を備えることを特徴とする。
　また本発明は、前記地図データ記憶媒体が記憶する第２地図データのリンクデータには、リンクに対応する道路の属性および経路コストに関するデータが含まれていることを特徴とする。」を、
「本発明は、２点間の経路を地図データに基づいて経路探索を行う経路探索装置において、
　（ａ）少なくとも道路の交差点または行止まりを示すノードに関するノードデータと、前記ノードを連結するリンクに関するリンクデータと、道路の形状を折線近似した折点を示す補間ノードに関する補間ノードデータと、前記補間ノードを連結する補間リンクに関する補間リンクデータとから成る第１地図データと、
　道路の交差点または行止まりを示すノードに関するノードデータと、前記ノードを連結するリンクに関するリンクデータとから成る第２地図データとを含む地図データ記憶媒体と、
　（ｂ）前記地図データ記憶媒体の第２地図データに基づき経路探索を行う経路探索手段と、
　（ｃ）前記経路探索手段が第２地図データに基づいて探索した経路を、前記地図データ記憶媒体の第１地図データに基づいて地図上に表示する表示手段とを備えることを特徴とする地図データ記憶媒体を用いた経路探索装置である。
　また、本発明は、前記地図データ記憶媒体の第１地図データに基づいて地図を表示する表示手段を備えることを特徴とする。
　また、本発明は、２点間の経路を地図データに基づいて経路探索を行う経路探索装置において、
　（ａ）少なくとも道路の交差点または行止まりを示すノードに関するノードデータと、前記ノードを連結するリンクに関するリンクデータと、道路の形状を折線近似した折点を示す補間ノードに関する補間ノードデータと、前記補間ノードを連結する補間リンクに関する補間リンクデータとから成る第１地図データと、
　道路の交差点または行止まりを示すノードに関するノードデータと、前記ノードを連結するリンクに関するリンクデータとから成る第２地図データとを含む地図データ記憶媒体と、
　（ｂ）前記地図データ記憶媒体の第２地図データに基づき経路探索を行う経路探索手段とを備え、
　前記地図データ記憶媒体が記憶する第２地図データのリンクデータには、リンクに対応する道路の属性および経路コストに関するデータが含まれていることを特徴とする地図データ記憶媒体を用いた経路探索装置である。
　また、本発明は、２点間の経路を地図データに基づいて経路探索を行う経路探索装置において、
　（ａ）少なくとも道路の交差点または行止まりを示すノードに関するノードデータと、前記ノードを連結するリンクに関するリンクデータと、道路の形状を折線近似した折点を示す補間ノードに関する補間ノードデータと、前記補間ノードを連結する補間リンクに関する補間リンクデータとから成る第１地図データと、
　道路の交差点または行止まりを示すノードに関するノードデータと、前記ノードを連結するリンクに関するリンクデータとから成る第２地図データとを含む地図データ記憶媒体と、
　（ｂ）前記地図データ記憶媒体の第２地図データに基づき経路探索を行う経路探索手段と、
　（ｃ）前記経路探索手段が第２地図データに基づいて探索した経路を、前記地図データ記憶媒体の第１地図データに基づいて地図上に表示する表示手段とを備え、
　前記地図データ記憶媒体が記憶する第２地図データのリンクデータには、リンクに対応する道路の属性および経路コストに関するデータが含まれていることを特徴とする地図データ記憶媒体を用いた経路探索装置である。」と、明りょうでない記載の釈明を目的として、訂正する。
（５４）【発明の名称】
地図データ記憶媒体を用いた経路探索装置
（５７）【特許請求の範囲】
　【請求項１】　２点間の経路を地図データに基づいて経路探索を行う経路探索装置において、
　（ａ）少なくとも道路の交差点または行止まりを示すノードに関するノードデータと、前記ノードを連結するリンクに関するリンクデータと、道路の形状を折線近似した折点を示す補間ノードに関する補間ノードデータと、前記補間ノードを連結する補間リンクに関する補間リンクデータとから成る第１地図データと、
　道路の交差点または行止まりを示すノードに関するノードデータと、前記ノードを連結するリンクに関するリンクデータとから成る第２地図データとを含む地図データ記憶媒体と、
　（ｂ）前記地図データ記憶媒体の第２地図データに基づき経路探索を行う経路探索手段と
、
　（ｃ）前記経路探索手段が第２地図データに基づいて探索した経路を、前記地図データ記憶媒体の第１地図データに基づいて地図上に表示する表示手段と
　【請求項２】　
前記地図データ記憶媒体の第１地図データに基づいて地図を表示する表示手段を備えることを特徴とする請求項１記載の地図データ記憶媒体を用いた経路探索装置。
　【請求項３】　
２点間の経路を地図データに基づいて経路探索を行う経路探索装置において、
　（ａ）少なくとも道路の交差点または行止まりを示すノードに関するノードデータと、前記ノードを連結するリンクに関するリンクデータと、道路の形状を折線近似した折点を示す補間ノードに関する補間ノードデータと、前記補間ノードを連結する補間リンクに関する補間リンクデータとから成る第１地図データと、
　道路の交差点または行止まりを示すノードに関するノードデータと、前記ノードを連結するリンクに関するリンクデータとから成る第２地図データとを含む地図データ記憶媒体と、
　（ｂ）前記地図データ記憶媒体の第２地図データに基づき経路探索を行う経路探索手段とを備え、
　前記地図データ記憶媒体が記憶する第２地図データのリンクデータには、リンクに対応する道路の属性および経路コストに関するデータが含まれていることを特徴とする地図データ記憶媒体を用いた経路探索装置。
　【請求項４】　
２点間の経路を地図データに基づいて経路探索を行う経路探索装置において、
　（ａ）少なくとも道路の交差点または行止まりを示すノードに関するノードデータと、前記ノードを連結するリンクに関するリンクデータと、道路の形状を折線近似した折点を示す補間ノードに関する補間ノードデータと、前記補間ノードを連結する補間リンクに関する補間リンクデータとから成る第１地図データと、
　道路の交差点または行止まりを示すノードに関するノードデータと、前記ノードを連結するリンクに関するリンクデータとから成る第２地図データとを含む地図データ記憶媒体と、
　（ｂ）前記地図データ記憶媒体の第２地図データに基づき経路探索を行う経路探索手段と、
　（ｃ）前記経路探索手段が第２地図データに基づいて探索した経路を、前記地図データ記憶媒体の第１地図データに基づいて地図上に表示する表示手段とを備え、
　前記地図データ記憶媒体が記憶する第２地図データのリンクデータには、リンクに対応する道路の属性および経路コストに関するデータが含まれていることを特徴とする
地図データ記憶媒体を用いた経路探索装置。
　【請求項５】　（ａ）地図データ記憶媒体であって、
　複数種類の道路のうちから予め定められた選択規則に従って選別された道路の接続関係を表す第１道路データと、
　選別された道路が選別によって寸断されることがないように、前記複数種類の道路のうちから選別された道路の接続関係を表す第２道路データとを含んで構成される地図データを記憶する地図データ記憶媒体と、
　（ｂ）地図データ記憶媒体に記憶されている地図データに基づいて、所定の地域の地図画面を表示する表示手段とを備えることを特徴とする地図データ記憶媒体を用いた表示装置。
　【請求項６】　指定された２地点間の経路を、記憶されている地図データに基づいて経路探索を行う経路探索装置において、
　（ａ）地図データ記憶媒体であって、
　複数種類の道路のうちから予め定められた選択規則に従って選別された道路の接続関係を表す第１道路データと、
　選別された道路が選別によって寸断されることがないように、前記複数種類の道路のうちから選別された道路の接続関係を表す第２道路データとを含んで構成される地図データを記憶する地図データ記憶媒体と、
　（ｂ）前記地図データ記憶媒体から地図データを読出し、読出した地図データに基づいて前記２地点間の経路探索を行う探索手段と、
　（ｃ）前記地図データ記憶媒体に記憶されている地図データに基づいて、地図画面を表示し、その地図画面上に前記探索手段が探索した経路を表示する表示手段とを備えることを特徴とする地図データ記憶媒体を用いた経路探索装置。
【発明の詳細な説明】
　【０００１】
　【産業上の利用分野】
　本発明は、地図画面上に自車位置や目的地を表示することができる、いわゆるナビゲーション装置に好適に実施され、目的地や経由地までの経路を探索するためなどに用いられる地図データを記憶する地図データ記憶媒体を用いた経路探索装置に関する。
　【０００２】
　【従来の技術】
　ナビゲーション装置は、自動車に搭載され、地図画面上に自車位置を併せて表示し、その表示を自車の走行に伴って更新してゆく装置である。また近年、このナビゲーション装置において、現在位置および目的地または経由地を入力することによって、現在位置からの目的地または経由地までで、たとえば最短経路となる経路が演算されて、推薦経路として表示するようにした経路探索機能が付加されるようになってきている。
　【０００３】
　従来の経路探索に用いられる地図データは、大略的に、道路の曲線形状を折線近似した折点または交差点を示すノードデータと、各ノード間を連結するリンクデータとを含んで構成されている。経路探索の際には、ＣＤ−ＲＯＭディスクに記憶されている地図データを、順次読出し経路探索が行われる。
　【０００４】
　また前述の地図データを作成する際には、データの情報量の削減などの理由によって、その地図データが網羅する地域の全ての道路を表す親データから、道路の種別や幅員などに基づいて地図データの縮尺や用途に応じて必要な道路に関するデータを選別して、地図データを作成する。
　【０００５】
　【発明が解決しようとする課題】
　上述の従来技術では、経路探索に用いる地図データには、道路の接続状態を表す交差点を示すノードデータのほかに、経路探索に必ずしも必要でない道路の曲線形状を表すための折点を示すノードデータが含まれているので、経路探索の処理速度が遅くなる。また、ＣＤ−ＲＯＭディスクから読出した地図データを一時記憶するためのメモリの記憶容量が増大する。
　【０００６】
　また上述の従来技術では、必要な道路を選別して地図データを形成する際に、道路の幅員などの変化によって道路が途中で途切れることがある。このような道路が途中で途切れた地図データに基づいて経路探索を行うと、道路が途切れている部分では経路探索ができない。また、このような地図データに基づいて地図画面を表示すると、道路が途切れている部分では道路のつながり方が判らず、地図として用いることができない。
　【０００７】
　本発明の目的は、経路探索処理の高速化を図ることができる、または道路の接続関係の完全性が向上された地図データを記憶する地図データ記憶媒体を用いた経路探索装置を提供することである。
　【０００８】
　【課題を解決するための手段】
　本発明は、２点間の経路を地図データに基づいて経路探索を行う経路探索装置において、
　　（ａ）少なくとも道路の交差点または行止まりを示すノードに関するノードデータと、前記ノードを連結するリンクに関するリンクデータと、道路の形状を折線近似した折点を示す補間ノードに関する補間ノードデータと、前記補間ノードを連結する補間リンクに関する補間リンクデータとから成る第１地図データと、
　道路の交差点または行止まりを示すノードに関するノードデータと、前記ノードを連結するリンクに関するリンクデータとから成る第２地図データとを含む地図データ記憶媒体と、
　（ｂ）前記地図データ記憶媒体の第２地図データに基づき経路探索を行う経路探索手段と
、
　（ｃ）前記経路探索手段が第２地図データに基づいて探索した経路を、前記地図データ記憶媒体の第１地図データに基づいて地図上に表示する表示手段と
　また本発明は、
前記地図データ記憶媒体の第１地図データに基づいて地図を表示する表示手段を備える
　また本発明は、
２点間の経路を地図データに基づいて経路探索を行う経路探索装置において、
　（ａ）少なくとも道路の交差点または行止まりを示すノードに関するノードデータと、前記ノードを連結するリンクに関するリンクデータと、道路の形状を折線近似した折点を示す補間ノードに関する補間ノードデータと、前記補間ノードを連結する補間リンクに関する補間リンクデータとから成る第１地図データと、
　道路の交差点または行止まりを示すノードに関するノードデータと、前記ノードを連結するリンクに関するリンクデータとから成る第２地図データとを含む地図データ記憶媒体と、
　（ｂ）前記地図データ記憶媒体の第２地図データに基づき経路探索を行う経路探索手段とを備え、
　前記地図データ記憶媒体が記憶する第２地図データのリンクデータには、リンクに対応する道路の属性および経路コストに関するデータが含まれていることを特徴とする地図データ記憶媒体を用いた経路探索装置である。
　また本発明は、
２点間の経路を地図データに基づいて経路探索を行う経路探索装置において、
　（ａ）少なくとも道路の交差点または行止まりを示すノードに関するノードデータと、前記ノードを連結するリンクに関するリンクデータと、道路の形状を折線近似した折点を示す補間ノードに関する補間ノードデータと、前記補間ノードを連結する補間リンクに関する補間リンクデータとから成る第１地図データと、
　道路の交差点または行止まりを示すノードに関するノードデータと、前記ノードを連結するリンクに関するリンクデータとから成る第２地図データとを含む地図データ記憶媒体と、
　（ｂ）前記地図データ記憶媒体の第２地図データに基づき経路探索を行う経路探索手段と、
　（ｃ）前記経路探索手段が第２地図データに基づいて探索した経路を、前記地図データ記憶媒体の第１地図データに基づいて地図上に表示する表示手段とを備え、
　前記地図データ記憶媒体が記憶する第２地図データのリンクデータには、リンクに対応する道路の属性および経路コストに関するデータが含まれていることを特徴とする
地図データ記憶媒体を用いた経路探索装置である。
　また本発明は、（ａ）地図データ記憶媒体であって、
　複数種類の道路のうちから予め定められた選択規則に従って選別された道路の接続関係を表す第１道路データと、
　選別された道路が選別によって寸断されることがないように、前記複数種類の道路のうちから選別された道路の接続関係を表す第２道路データとを含んで構成される地図データを記憶する地図データ記憶媒体と、
　（ｂ）地図データ記憶媒体に記憶されている地図データに基づいて、所定の地域の地図画面を表示する表示手段とを備えることを特徴とする地図データ記憶媒体を用いた表示装置である。
　また本発明は、指定された２地点間の経路を、記憶されている地図データに基づいて経路探索を行う経路探索装置において、
　（ａ）地図データ記憶媒体であって、
　複数種類の道路のうちから予め定められた選択規則に従って選別された道路の接続関係を表す第１道路データと、
　選別された道路が選別によって寸断されることがないように、前記複数種類の道路のうちから選別された道路の接続関係を表す第２道路データとを含んで構成される地図データを記憶する地図データ記憶媒体と、
　（ｂ）前記地図データ記憶媒体から地図データを読出し、読出した地図データに基づいて前記２地点間の経路探索を行う探索手段と、
　（ｃ）前記地図データ記憶媒体に記憶されている地図データに基づいて、地図画面を表示し、その地図画面上に前記探索手段が探索した経路を表示する表示手段とを備えることを特徴とする地図データ記憶媒体を用いた経路探索装置である。
　【０００９】
　【作用】
　本発明に従えば、経路探索に用いられる第２地図データには、道路の交差点または行止まりを示すノードに関するノードデータと、各ノードを連結するリンクに関するリンクデータとのみが含まれており、従来のように道路の曲線形状を折線近似するための補間ノードや補間リンクに関するデータが含まれていないので、経路探索を行う際に、選択すべき推薦経路を互いに隣接する１つの交差点から他の交差点までの区間毎に確定することができ、探索すべき推薦経路を速やかに確定することができる。また、第２地図データには、補間ノードおよび補間リンクに関するデータが含まれていないので、経路探索の際に演算処理すべきデータの情報量が少なくなり、処理速度を向上することができる。また、補間ノードおよび補間リンクに関するデータが含まれていないので、地図データ記憶媒体から読出した地図データを一時記憶しておくためのメモリなどの記憶容量を小さくすることができ、装置の製造コストを削減することができる。第１地図データは、ノードデータとリンクデータと補間ノードデータと補間リンクデータとから成り、これによって地図を表示することができる。地図データ記憶媒体には、前述の第１地図データと第２地図データとが個別的に設けられており、したがって本発明では、経路探索時に、補間ノードおよび補間リンクが含まれる第１地図データから必要なノードデータおよびリンクデータを抽出するものではなく、このような抽出工程が、第２地図データを用いることによって、不要になる。これによって上述のように経路探索を速やかに行うことができる。また、地図データのリンクデータには、リンクが対応する道路属性および経路コストに関するデータが予め含まれているので、経路探索を行う際に一々道路の道路属性を検索する必要がなく、また道路の経路コストを算出する必要がなく、その結果、経路探索の処理速度を向上することができる。
　【００１０】
　また本発明によれば、上記地図データ記憶装置を用いた経路探索装置によって、経路探索を行うべき２つの地点が指定されると、２つの地点のうちの一方の地点が経路探索を開始する始点と設定され、他方の地点が経路探索を終了する終点と設定され、探索手段による経路探索が開始される。経路探索は、探索中の探索経路の末端の点である探索点を移動しながら、始点から探索点までの経路長や自動車が移動する際の所要時間などを示す経路コストの和を算出し、経路コストの和が最も小さくなる探索点の位置を選択する。次に、その選択した探索点の位置に至る他の経路があるかどうかを調べ、他の経路がある場合には、選択した探索点の位置に至るその複数の経路のうちから経路コストの和が最も小さくなる経路を、始点から選択した探索点の位置までの推薦経路とする。このように選択された探索点の位置までの推薦経路が確定すると、新たな探索点を、選択された探索点の位置のノードに１つのリンクを介して隣接するノード上に設け、その新たな探索点を順次移動しながら、同様に新たな探索点までの推薦経路を決定する。ここで、高速道路よりも一般道路を優先して経路探索を行うべきことなどが予め設定されている場合には、道路が一般道路であるか高速道路であるか、および道路の幅員などを示すリンクデータが含む道路属性を参照しながら経路探索が行われる。
　【００１１】
　このように経路探索によって探索される推薦経路は、互いに隣接するノード間の１つのリンクに対応する区間毎に、すなわち本発明では交差点を示す１つのノードから隣接する交差点の他のノードまでの区間毎に確定されてゆき、設定される探索点が終点に到達すると、経路探索が終了される。
　【００１２】
　探索点の移動および新たな探索点の設定に伴って、探索点の位置する地域の地図データが地図データ記憶媒体から順次読出される。
　【００１３】
　このような構成によって、経路探索に用いられる地図データには、道路の交差点または行止まりを示すノードに関するノードデータと、各ノードを連結するリンクに関するリンクデータとのみが含まれており、従来のように道路の曲線形状を折線近似するための補間ノードや補間リンクに関するデータが含まれていないので、経路探索を行う際に、選択すべき推薦経路を互いに隣接する１つの交差点から他の交差点までの区間毎に確定することができ、探索すべき推薦経路を速やかに確定することができる。
　【００１４】
　また、第２地図データには、補間ノードおよび補間リンクに関するデータが含まれていないので、経路探索の際に演算処理すべきデータの情報量が少なくなり、処理速度を向上することができる。また、補間ノードおよび補間リンクに関するデータが含まれていないので、地図データ記憶媒体から読出した地図データを一時記憶しておくためのメモリなどの記憶容量を小さくすることができ、装置の製造コストを削減することができる。
　【００１５】
　また、地図データのリンクデータには、リンクが対応する道路属性および経路コストに関するデータが予め含まれているので、経路探索を行う際に一々道路の道路属性を検索する必要がなく、また道路の経路コストを算出する必要がなく、その結果、経路探索の処理速度を向上することができる。
　【００１６】
　また本発明に従えば、前述の経路探索によって探索すべき推薦経路が得られると、表示手段は、地図データ記憶媒体に記憶されている地図データと、補間ノードおよび補間リンクに関する補間ノードデータとに基づいて、地図画面を表示し、その地図画面上に推薦経路を表示する。
　【００１７】
　また本発明に従えば、地図データ記憶装置には道路の曲線形状を表す補間ノードおよび補間リンクに関する補間ノードデータおよび補間リンクデータが記憶されているので、表示手段において、実際の道路の形状に近い道路の曲線形状が表現された地図画面を表示することができる。その結果、道路の形状が実際の道路の形状に即して表された推薦経路を、地図画面上に表示することができ、運転者が探索された推薦経路を認識しやすくすることができる。また本発明に従えば、地図データのリンクデータには、リンクが対応する道路属性および経路コストに関するデータが予め含まれているので、経路探索を行う際に一々道路の道路属性を検索する必要がなく、また道路の経路コストを算出する必要がなく、その結果、経路探索の処理速度を向上することができる。
　【００１８】
　また本発明に従えば、経路探索手段による経路探索は、複数種類の道路のうちから予め定められた選択規則に従って選別された道路の接続関係を表す第１道路データと、選別された道路が選別によって寸断されることがないように前記複数種類の道路のうちから選別された道路の接続関係を表す第２道路データとを含んで構成される地図データ記憶装置に記憶されている地図データに基づいて行われる。
　【００１９】
　【００２０】
　したがって、経路探索に用いる地図データには、第１道路データに含まれる道路が選別によって寸断された部分をつなぎ合わせて補間する道路に関する第２道路データが含まれているので、道路の接続関係の完全性が向上された地図データに基づいて経路探索が行われる。その結果、適切な経路を推薦経路として選択することができる。
　【００２１】
　【００２２】
　また、地図データ記憶装置および表示手段を備える表示装置において、表示手段によって道路の接続関係の完全性が向上された地図画面を表示することができ、道路の接続関係の完全性が向上されているので、運転者が自ら道順を決定する際などに用いる地図として地図画面を利用することができる。
　【００２３】
　【実施例】
　図１は、本発明の一実施例のナビゲーション装置１の電気的構成を示すブロック図である。このナビゲーション装置１は、自動車に搭載されて、現在位置表示や目的地までの経路案内表示を行い、運転者の進路決定などに役立てられる。
　【００２４】
　したがって、概略的に、このナビゲーション装置１では、操作キー２への入力操作に応答して、マイクロコンピュータなどで実現される中央処理装置３が通信バス４を介してＣＤ−ＲＯＭ装置５へ所望とする地域の地図データの読取りを指示する。その指示に応答して、処理回路６が、デコーダ７を介して、記憶媒体であるＣＤ−ＲＯＭディスク８に記録されている地図データから対応する地域の地図データを読出す。こうして処理回路６から前記通信バス４を介して入力された地図データに対応して、前記中央処理装置３が、表示駆動回路９を介して、液晶表示装置などで実現される表示装置１０を表示駆動することによって、前記所望とする地域の地図画面表示が実現される。
　【００２５】
　また、このナビゲーション装置１には、ＧＰＳ（Ｇｌｏｂａｌ　Ｐｏｓｉｔｉｏｎｉｎｇ　Ｓｙｓｔｅｍ）受信機１１が設けられており、このＧＰＳ受信機１１は、ＧＰＳアンテナ１２で受信された地球周回軌道を回る測位衛星からの信号に基づいて三角測量を行い、自車の緯度、経度、高度および走行速度などを演算し、その演算結果を前記通信バス４を介して中央処理装置３へ出力する。
　【００２６】
　さらにまた、このナビゲーション装置１には、地磁気センサ１３と、ジャイロセンサ１４と、車輪速センサ１５とが備えられている。地磁気センサ１３は車両の進行方向を検出し、ジャイロセンサ１４は車両の姿勢変化を検出し、車輪速センサ１５は車体速度を検出する。センサ１３，１４の検出結果は、それぞれアナログ／デジタル変換器１６，１７でデジタル値に変換されて処理回路１９に入力される。また、車輪速センサ１５からの車速パルスは、パルスカウンタ１８でカウントされ、処理回路１９に入力される。このとき、後退位置検出器２５によって変速機の変速段が後退位置であることが検出されると、前記カウント値は負の値とされる。
　【００２７】
　処理回路１９へは前記中央処理装置３から操作キー２で入力された自車位置などに関するデータが入力され、これによって該処理回路１９は、前記各センサ１３〜１５の検出結果から現在の自車位置を推測演算し、その演算結果を中央処理装置３へ出力する。こうして、たとえばビル影、高架下またはトンネル内などで前記ＧＰＳ受信機１１によって正確な自車位置を計測することが不可能な地点においても、いわゆる推測航法によって正確に自車位置を計測することができる。
　【００２８】
　さらにまた、中央処理装置３に関連してメモリ２０が設けられている。このメモリ２０には、後述するように選択された経路の目的地や経由地などが記憶されるとともに、探索の始点または終点となった探索地点が記憶されている。
　【００２９】
　図２は、上述のように構成されたナビゲーション装置１の経路案内動作を説明するための機能ブロック図である。前記操作キー２、ＧＰＳ受信機１１および処理回路１９などの入力部３１から現在位置および目的地または経由地が入力されると、探索を開始する前に経路探索部３２の地点設定部３３が、入力された地点に関連して、探索を開始すべき地点または探索を終了すべき地点となるべき探索地点を初期設定する。
　【００３０】
　設定された探索地点間で探索部３４は、ＣＤ−ＲＯＭ装置５などから参照符３５で示すように地図データを読出して、リンクを辿って経路を探索し、その探索結果３６は経路案内部３７に与えられるとともに、該経路探索部３２内のデータ管理部３８で前記メモリ２０に保管される。
　【００３１】
　一方、前記地図データ３５はまた、自車位置検出部３９に与えられており、この自車位置検出部３９は、前記ＧＰＳ受信機１１および処理回路１９などからの出力と前記地図データ３５とのマップマッチングを行い、正確な自車位置を演算して前記経路案内部３７に与えるとともに、前記表示駆動回路９および表示装置１０などで実現される出力部４０に与える。出力部４０にはまた、前記経路案内部３７から、選択された経路に関するデータが与えられており、こうして、経路案内部３７によって作成された経路上に、自車位置検出部３９で計測された自車位置が併せて表示され、経路案内を行うことができる。
　【００３２】
　図３は、ＣＤ−ＲＯＭディスク８に記憶される地図データの構成例を示す図である。地図データは、図３に示されるように、各ノードデータが含まれるノードテーブルＮＴと、各リンクデータが含まれるリンクテーブルＬＴと、ヘッダＨとを有する。
　【００３３】
　ヘッダＨには、地図データの全データサイズ、その地図データが網羅する範囲を示す緯度および経度、ノードテーブルＮＴのデータサイズ、ノードテーブルＮＴの先頭アドレス、リンクテーブルＬＴのデータサイズ、リンクテーブルＬＴの先頭アドレスなどに関する情報が含まれている。
　【００３４】
　ノードテーブルＮＴには、道路の交差点、行止まり点、および道路の曲線形状を折線近似する折点などを示す各ノードに個別に対応するノードデータＮＤ１〜ＮＤｎが含まれている。各ノードデータＮＤ１〜ＮＤｎには、対応するノードの座標データ、そのノードに接続しているリンクの数を示す分岐数、そのノードに接続するリンクを示す接続リンクリスト、そのノードにリンクを介して接続される全てのノードを示す接続ノードリスト、そのノードが交差点である場合の交差点名称、右左折禁止に関する情報などが含まれている。
　【００３５】
　リストテーブルＬＴには、各ノード間に連結される各リンクに個別に対応するリンクデータＬＤ１〜ＬＤｎが含まれている。各リンクデータＬＤ１〜ＬＤｎには、そのリンクが対応する道路の道路種別、幅員、一方通行や速度規制などの交通規制、トンネルであるかどうかを示すトンネル属性、高架道路であるかどうかを示す高架属性、有料道路であるかどうかを示す有料属性、道路名称などの道路の属性に関する情報が含まれている。前記道路種別によって、リンクに対応する道路がたとえば高速道路であるか一般道路であるかが示される。
　【００３６】
　上述のように構成される地図データは、メッシュ状に分割された各地域毎に分割されて記憶されている。各地域間で地図データに含まれるノードおよびリンクを連結するために、各地域に対応する地図データにはそれぞれメッシュコードが付されており、１つの地図データに含まれるノードがリンクを介して他の地図データに含まれるノードに連結される場合には、１つの地図データに含まれるノードに対応するノードデータに含まれる接続ノードリストに、連結される相手方の地図データのメッシュコードと、相手方のノードを特定するための相手方の地図データにおけるノード座標に関する情報とを含ませておくことによって、異なる地図データ間でノードおよびリンクを接続することができる。
　【００３７】
　図４は、道路形状を表現した第１地図データおよび道路の接続関係のみを表現した第２地図データを説明するための図である。第１地図データは、表示装置１０に地図画面を表示し、表示した地図画面上に自車の位置を表示して運転者の進路決定を補助する進路案内動作などに用いられる。第１地図データには、図４（１）に示されるように、道路の接続関係を表す黒丸で示される構成ノードＳＮおよび構成リンクＳＬのほかに、道路の形状を表す補間ノードＣＮおよび補間リンクＣＬが含まれている。
　【００３８】
　構成ノードＳＮは、交差点や行止まり点を示し、構成リンクＳＬは各構成ノードＳＮ間を接続する道路を示す。補間ノードＣＮは道路の曲線形状を折線近似して示す折点を示し、補間リンクＣＬは構成ノードＳＮまたは補間ノードＣＮと補間ノードＣＮとの間を連結する道路を示す。第１地図データには、道路の曲線形状を表す補間ノードＣＮおよび補間リンクＣＬが含まれているので、実際の道路の曲線形状が表現された地図データに基づいて適切な進路案内動作を行うことができる。
　【００３９】
　第２地図データは、運転者によって指定された２つの地点間の最短経路などを探索する経路探索に用いられる。第２地図データには、図４（２）に示されるように、道路の接続関係を表す構成ノードＳＮおよび構成リンクＳＬが含まれている。
　【００４０】
　本実施例のＣＤ−ＲＯＭ装置５におけるＣＤ−ＲＯＭディスク８には、第１地図データとともに第２地図データが記憶されている。図４（２）に示される第２地図データは、図４（１）に示される第１地図データに基づいて作成されたものであり、第１地図データに含まれる補間ノードＣＮおよび補間リンクＣしの部分を、図４に示されるように、対応する構成リンクＳＬに後述するように置き換えることによって形成される。
　【００４１】
　図５は第１地図データの構成を示す図であり、図６は第２地図データの構成を示す図である。図５および図６に基づいて、第１地図データから第２地図データを作成する際の処理について説明する。ここでは例として、図５（１）に示される構成ノードＮ１と構成ノードＮ４との間の補間ノードＮ２，Ｎ３および補間リンクＬ１〜Ｌ３を、図６（１）に示される構成リンクＬＡに置き換える場合について説明する。
　【００４２】
　第１地図データには、図３に基づいて前述したように、補間リンクＬ１〜Ｌ３にそれぞれ対応する各リンクデータが図５（２）に示されるように含まれている。その各リンクデータには、各補間リンクＬ１〜Ｌ３に対応する道路の道路種別が国道であること、幅員が１０ｍであること、交通規制において一方通行でないこと、および各補間リンクＬ１〜Ｌ３に対応する区間の道路の実際の距離である実距離などに関する情報が含まれている。
　【００４３】
　また第１地図データには、構成ノードＮ１，Ｎ４に対応する各ノードデータが図５（３）に示されるように含まれている。その各ノードデータには、構成ノードＮ１，Ｎ４に対応する交差点においてそれぞれ接続数が３であること、および右左折禁止でないことを示す右左折禁止情報が含まれている。このほか第１地図データには、補間ノードＮ２，Ｎ３に対応するノードデータも含まれている。補間ノードＮ２，Ｎ３は、道路の曲線形状を折線近似する折点を表すので、補間ノードＮ２，Ｎ３に対応するノードデータには、それぞれ接続数が２として登録されている。
　【００４４】
　ノードデータにおいて、接続数が１である場合には、そのノードデータに対応するノードが道路の行止まり点に対応することを示し、接続数が３以上である場合には、そのノードデータに対応するノードが道路の交差点に対応することを示す。また接続数が２である場合には、そのノードデータに対応するノードが補間ノードであることを示し、接続数が２以外である場合には、そのノードデータに対応するノードが構成ノードであることを示す。したがって、接続数が２であるかどうかを判断することによって、そのノードデータに対応するノードが補間ノードであるかどうかを判断することができる。
　【００４５】
　図５に示される第１地図データに基づいて、図６に示される第２地図データを作成する際には、第１地図データに含まれるノードのうちから補間ノードをピックアップし、ピックアップした補間ノードおよびその補間ノードに接続される補間リンクをそれぞれ構成リンクに置き換え、置き換えた構成リンクに対応するリンクデータを第２地図データ内に作成する。図５および図６の図示例では、補間ノードＮ２，Ｎ３および補間リンクＬ１〜Ｌ３に対応する構成リンクＬａが図６（１）に示されるように設けられ、構成リンクＬａに対応するリンクデータが、図６（２）に示されるように第２地図データ内に作成される。
　【００４６】
　これに伴って、第１地図データにおける構成ノード、たとえば構成ノードＮ１，Ｎ４はそのまま構成ノード、たとえば構成ノードＮａ，Ｎｂとして採用され、採用された構成ノードＮａ，Ｎｂに対応するノードデータが、図６（３）に示されるように第２地図データ内に作成される。また、第１地図データにおける構成リンクは、そのまま構成リンクとして採用され、採用された構成リンクに対応するリンクデータが、第２地図データ内に作成される。
　【００４７】
　構成リンクＬａに対応するリンクデータには、図６（２）に示されるように、補間リンクＬ１〜Ｌ３に対応する各リンクデータから引継いだ道路種別、幅員、交通規制などに関する情報が含まれている。また構成リンクＬａに対応するリンクデータには、第１地図データにおいて構成リンクＬａの区間に含まれる全てのリンクを表すリンクリスト、第１地図データにおいて構成リストＬａの区間に含まれる全てのノードを表すノードリスト、構成リストＬａの区間に対応する道路の実際の距離を示す実距離、構成リンクＬａの区間に対応する経路コストなどに関する情報が含まれている。
　【００４８】
　図６（２）のリンクリストおよびノードリストによって、第２地図データにおける構成ノードＮａと構成ノードＮｂとの間の構成リンクＬａが、第１地図データにおいて補間リンクＬ１〜Ｌ３に対応され、構成リンクＬａに対応する区間にはノードＮ１〜Ｎ４が含まれていることが表される。
　【００４９】
　図６（２）の実距離に関するデータは、図５（２）の補間リンクＬ１〜Ｌ３に対応するリンクデータに含まれる実距離の値が加算されて作成され、図６（２）の図示例では実距離が１０００ｍとなっている。
　【００５０】
　図６（２）の経路コストは、後述するように第２地図データに基づいて経路探索を行う際に用いられるデータである。この経路コストには、構成リンクＬａに対応する道路の区間の実距離、またはその道路の区間を実際に自動車が通過する際の推定の所要時間が登録される。本実施例では、所要時間が経路コストとして用いられている。この経路コストに関する情報は、第１地図データの補間リンクに対応しない第２地図データの補間リンクに対応するリンクデータにも同様に登録される。
　【００５１】
　経路コストに用いられる所要時間は、実際に自動車が構成リンクＬａに対応する区間を通過するのに要した時間を計測した計測値でもよく、構成リンクＬａに対応するリンクデータに基づいて所定の演算を行い、算出した算出値でもよい。前記所定の演算の一例として、道路種別に対応して設定される所定の定数と、道路の幅員に対応して設定される所定の定数と、構成リンクＬａの区間に対応する道路の実距離とを乗算して推定の所要時間を算出する方法が挙げられる。図６（２）の図示例では、経路コストは１．５分と登録されている。
　【００５２】
　第２地図データにおける構成ノードＮａ，Ｎｂに対応する各ノードデータには、図６（３）に示されるように、図５（３）の構成ノードＮ１，Ｎ４に対応する各ノードデータの内容がそのまま移植されて登録されており、その移植された登録データの他に第２地図データにおける各構成ノードＮａ，Ｎｂがそれぞれ第１地図データにおける構成ノードＮ１，Ｎ４にそれぞれ対応することを示す対応ノードデータに関する情報が含まれている。また、第２地図データにおいて第１地図データの構成リンクに対応する構成リンクのリンクデータには、第１地図データのリンクデータの内容がそのまま移植され、さらに第１地図データにおいて対応する構成リンクを表す対応リンクデータが含まれている。
　【００５３】
　次に上述の第２地図データを用いた経路探索を説明する。現在位値と目的地または経由地とをそれぞれ示す２つの地点が入力され、２つの地点のうちの一方の地点が経路探索を開始する始点と設定され、他方の地点が経路探索を終了する終点と設定されると、始点を含む第２地図データが読出され、始点を起点として経路探索が開始される。なお、始点および終点は、対応するノード上にそれぞれ設定される。
　【００５４】
　Ｄｉｊｋｓｔｒａ法などが用いられる経路探索は、探索中の探索経路の末端の点である探索点を移動しながら、始点から探索点までの経路コストの和を算出し、経路コストの和が最も小さくなる探索点の位置を選択する。次に、その選択した探索点の位置に至る他の経路があるかどうかを調べ、他の経路がある場合には、選択した探索点の位置に至るその複数の経路のうちから経路コストの和が最も小さくなる経路を、始点から選択した探索点の位置までの推薦経路とする。ここで、高速道路よりも一般道路を優先して経路探索を行うべきことなどが予め設定されている場合には、リンクデータが示す道路属性を参照しながら経路探索が行われる。
　【００５５】
　このように選択された探索点の位置までの推薦経路が確定すると、新たな探索点を選択された探索点の位置のノードに１つのリンクを介して隣接するノード上に設け、その新たな探索点を順次移動しながら、同様に新たな探索点までの推薦経路を決定する。
　【００５６】
　このように経路探索によって探索される推薦経路は、互いに隣接するノード間の１つのリンクに対応する区間毎に、すなわち本発明では交差点を示す１つのノードから隣接する交差点を示す他のノードまでの区間毎に確定されてゆき、順次設定される探索点が終点に到達すると、経路探索が終了される。
　【００５７】
　探索点の移動および新たな探索点の設定に伴って、探索経路における末端の探索点の位置する地域の第２地図データが順次読出される。
　【００５８】
　経路探索によって２地点間の選択すべき推薦経路が得られると、経路探索に伴って読出した第２地図データに対応する第１地図データが読出され、得られた推薦経路を表示するための地図画面が、読出した第２地図データに基づいて表示される。第２地図データ上に形成されている推薦経路は、第２地図データのリンクデータに含まれる前述のリンクリストおよびノードリスト、および対応リンクデータに基づいて、またノードデータに含まれる対応ノードデータに基づいて第１地図データ上における推薦経路へと変換され、読出した第１地図データに基づいて表示される地図画面上に変換された推薦経路が表示される。
　【００５９】
　したがって、経路探索に用いられる第２地図データには、道路の曲線形状を表す補間ノードおよび補間リンクに対応する図５（２），（３）に示されるようなノードデータおよびリンクデータが含まれていないので、経路探索の際、選択すべき推薦経路を隣接する交差点の区間毎に確定することができ、従来のように折点を示すノードを含めた互いに隣接する各ノード間毎に推薦経路を確定するのに比べて、選択すべき推薦経路をいち早く確定することができ、経路探索の処理速度を向上することができる。
　【００６０】
　また、第２地図データには補間ノードおよび補間リンクに対応するノードデータおよびリンクデータが含まれていないので、経路探索の際に演算処理すべき情報量を小さくすることができ、処理速度を向上することができる。またＣＤ−ＲＯＭディスク８から読出した地図データを一時記憶しておくためのメモリ２０の記憶容量を削減することができ、ナビゲーション装置１の製造コストを削減することができる。
　【００６１】
　また、第２地図データのリンクデータには、各リンクが対応する道路の道路属性および経路コストに関するデータが予め含まれているので、道路属性を参照しながら適切な経路を推薦経路としていち早く探索することができる。
　【００６２】
　また、第２地図データにおいて、構成リンクが第１地図データにおける補間ノードおよび補間リンクに対応する場合には、第２地図データのリンクデータには、対応する補間ノードおよび補間リンクを示すノードリストおよびリンクリストが図６（２）に示されるように含まれており、推薦経路を表示する際には、ノードリストおよびリンクリストに基づいて第２地図データ上における構成リンクが第１地図データ上における補間ノードおよび補間リンクが対応付けられるので、道路の形状が表現された第１の地図データに基づいて、推薦経路を表示することができる。その結果、運転者が選択された推薦経路を認識しやすくなる。
　【００６３】
　なお、上述の実施例では、道路の形状を表現した第１地図データに伴って経路探索用の第２地図データがＣＤ−ＲＯＭディスク８に記憶されていたが、他の実施例として第１地図データがＣＤ−ＲＯＭディスク８に記憶されていない場合を説明する。本実施例では、第１地図データがＣＤ−ＲＯＭディスク８に記憶されていないので、前述した補間ノードおよび補間リンクに対応するノードデータおよびリンクデータを第２地図データとは別に記憶しておく必要がある。
　【００６４】
　本実施例では、図７に示されるように、補間リンクＣＬ１〜ＣＬｎに対応する補間リンクデータＣＬＤ１〜ＣＬＤｎが含まれる補間リンクテーブルＣＬＤが、第２地図データとは別にＣＤ−ＲＯＭディスク８に記憶されている。またこれと同様に補間ノードに対応する各補間ノードデータが含まれる補間ノードテーブルも、ＣＤ−ＲＯＭディスク８に記憶されている。第２地図データに含まれる構成リンクに、補間ノードおよび補間リンクが対応する場合には、その構成リンクのリンクデータに、前述のリンクリストおよびノードリストの代わりに図８に示される補間データＤＣが付与される。
　【００６５】
　この補間データＤＣは、対応する補間ノードおよび補間リンクの補間ノードデータおよび補間リンクデータを前述の補間ノードテーブルおよび補間リンクテーブルから読出すためのデータであり、図８の図示例では補間リンクに関する補間データＤＣが示されている。補間データＤＣは、図８に示されるように、構成リンクに対応する補間リンクの補間リンクデータが補間リンクテーブルにおいて先頭から何番目かを示すディスプレイスメントデータＤＣ１と、何個分の補間リンクデータが構成リンクに対応しているかを示す構成数に関するデータＤＣ２とから成る。同様に、図示しない補間ノードに関する補間データも、ディスプレイスメントデータと構成数に関するデータとから成る。
　【００６６】
　経路探索の際には、図７の補間ノードテーブルおよび補間リンクテーブル内のデータを読込まずに第２地図データ内のデータのみを読込みながら経路探索を行い、推薦経路が確定して探索動作が終了すると、前述の補間データに基づいて補間リンクテーブルおよび補間ノードテーブル内のデータを読込み、道路の曲線形状に関するデータを補ってから推薦経路を表示する。　
　【００６７】
　次に、前述の実施例のナビゲーション装置１とＣＤ−ＲＯＭディスク８に記憶されている地図データが異なるナビゲーション装置に関するまた他の実施例について説明する。
　【００６８】
　ＣＤ−ＲＯＭディスク８に記憶される進路案内や経路探索に用いられるデータは、データの情報量を減らし、処理速度を向上するため、全ての道路に関する道路データを含む親データのうちから所定の選択規則に基づいて選別された道路に関する道路データを含んで構成される。このように構成される地図データを作成する際の手順を図９〜図１２に基づいて説明する。
　【００６９】
　前述の実施例において説明したように、リンクデータには、道路種別や幅員などの道路属性に関する情報が含まれている。まず、道路属性に基づいて各道路毎にランク付けを行い、全ての道路に関するデータを含んだ親データから、ランクの高い所定の道路に対応する道路データのみを図９に示されるように抜出し、第１道路データとする。
　【００７０】
　図９（１）において太い実線で示される道路Ａ〜Ｄはランクの高い道路であり、細い実線で示される道路Ｅ１〜Ｅ６はランクの低い道路であり、選別の結果、図９（２）に示されるようにランクの高い道路Ａ〜Ｄのみが抜き出されている。このように、単純なランク付けに基づいて道路を選別すると、たとえば１本につながった道路であっても、ランク付けの低い部分、たとえば幅員が狭くなった部分などでは、道路データが抜き出されることなく取り残されてしまい、図９（２）に示されるように、道路が寸断されてしまう。
　【００７１】
　本実施例において注目すべきは、前述のような道路の選別によって道路が寸断された部分を、図１０に示されるように、つなぎ合わせて道路の接続関係の完全性を回復する点である。
　【００７２】
　図１０（１）において寸断されている道路Ａおよび道路Ｄの問には、図１０（２）に示されるように選別されなかったランクの低い道路Ｅ４が補間されている。同様に図１０（１）において宙に浮いている形となっている道路Ｂには、図１０（２）に示されるように、道路Ａおよび道路Ｃにそれぞれ通ずる道路Ｅ３，Ｅ６がそれぞれ接続されて補間されている。このような補間された道路Ｅ３，Ｅ４，Ｅ６に関するデータは第２道路データに含まれる。
　【００７３】
　このような道路Ｅ３，Ｅ４，Ｅ６の補間は、図９（１）に対応する親データに基づいて表示された地図画面を人間が目視して補間すべき道路を選択するようにしてもよい。または、図１０（１）における道路Ａの末端Ａ１と道路Ｄの末端Ｄ１との間と、道路Ｂの一方の末端Ｂ１と道路Ａとの間と、道路Ｂの他方の末端Ｂ２と道路Ｃとの間とにおいて、図９（１）の親データに基づいて経路探索を行い、経路コストが最も小さくなるような経路を補間道路として選択するようにしてもよい。
　【００７４】
　図１１に基づいて道路の他の補間方法を説明する。図１１（１）に示されるように、選別された第１道路データに含まれる道路Ｆが地点Ｐと地点Ｑとの問の区間で大きく回り込んでいる場合に、地点Ｐと地点Ｑとを短絡する選別されなかった道路が存在する場合には、図１１（２）に示されるように地点Ｐと地点Ｑとを短絡する道路Ｅ７を補間する。この道路Ｅ７の補間は、前述の図１０における補間処理と同様に、人間の目視によって行ってもよいし、経路探索によって行ってもよい。
　【００７５】
　また、道路Ｆが地点Ｐから地点Ｑまでの間で囲い込む領域ＦＡ内において経路探索を行い、経路探索の結果、領域ＦＡの部分を短絡する経路、すなわち道路Ｆよりも実距離の短い経路が発見された場合には、予め定められた所定の選択規則に基づいて発見された経路のうちから所定の経路を選択して補間経路として補間する。選択された道路は、第２道路データに含められる。ここで、道路Ｆの地点Ｐと地点Ｑとの間の区間は、図１０に示される補間処理によって補間された第２道路データに含まれる道路であってもよい。
　【００７６】
　前記所定の選択規則は、地点Ｐと地点Ｑとの間の経路コストが最小の経路の経路コストＣ１とし、経路探索によって発見された経路を経由する経路の経路コストをＣ２とするとき、Ｃ２がＣ１＞Ｃ２・Ｋの条件を満たす場合に、その発見された経路を補間するという選択規則が例として挙げられる。ここで、Ｋは１以上の定数である。
　【００７７】
　図１２に基づいて、また他の補間方法を説明する。道路の選別によって図１２（１）に示されるように道路ＲＢと道路ＲＡとが寸断されてしまった場合に、まず、道路ＲＢの末端ＲＢｌと道路ＲＡとを接続する全ての道路をピックアップし、ピックアップした道路のうちから末端ＲＢ１から道路ＲＡまでの実距離が最短の道路の実距離をｓ０とし、ピックアップした道路のうちから末端ＲＢ１から道路ＲＡまでの実距離ｓｎが、ｓｎ−ｓ０＜Ｋ１の条件を満たす道路を補間候補として、図１２（２）に示されるように抜出す。ここで、Ｋ１は所定の定数である。図１２（２）において、実距離が最短の道路は道路Ｒ０であり、その道路Ｒ０の他に道路Ｒ１〜Ｒ３が補間候補として抜き出されている。抜き出された道路Ｒ０〜Ｒ３は、接続点Ｐ０〜Ｐ３においてそれぞれ道路ＲＡとつながっている。
　【００７８】
　上述のような条件に従って補間道路の候補を抜き出すことによって、図１２（２）に示されるように、定数Ｋ１の値を適当に調整することによって、道路ＲＢの末端ＲＢ１よりも左側で道路ＲＡに接続する道路Ｒ０，Ｒ１，Ｒ２と右側で道路ＲＡに接続する道路Ｒ３とを補間候補として抜き出すことができる。これによって、運転者が道路ＲＢを経由して道路ＲＡに至り、道路ＲＡ上を図１２（２）における左方向に進行する場合にも右方向に進行する場合にも対応できる道路を補間することが可能となる。
　【００７９】
　図１２（２）に示されるように補間候補が抜き出されると、前述の実距離が最短の道路Ｒ０の接続点Ｐ０から接続点Ｐ１〜Ｐ３までの道路ＲＡ上における距離が、所定の値Ｍ以上の道路Ｒ１〜Ｒ３が、抜き出されている道路Ｒ１〜Ｒ３のうちから道路Ｒ０とともに、図１２（３）に示されるように選択されて補間される。図１２（３）の図示例では、道路Ｒ１，Ｒ２は接続点Ｐ１，Ｐ２の接続点Ｐ０からの距離が所定の値Ｍよりも短いので間引かれ、道路Ｒ０，Ｒ３が補間道路として選択されている。
　【００８０】
　このように補間候補として抜き出された道路Ｒ０〜Ｒ３のうちから、道路Ｒ０，Ｒ３を選択して補間することによって、道路ＲＢと道路ＲＡとを結ぶ必要かつ充分な道路、すなわち運転者が道路ＲＢから道路ＲＡに至り、道路ＲＡ上を図１２（３）における左方向に進行する場合にも右方向に進行する場合にも対応可能な道路を補間することができる。
　【００８１】
　以上のように作成された地図データは、ＣＤ−ＲＯＭディスク８に記憶されており、進路案内および経路探索の際には、ＣＤ−ＲＯＭディスク８に記憶されている地図データのうちから所定の地域の地図データが順次読出されて案内動作および探索動作が行われる。
　【００８２】
　したがって、ＣＤ−ＲＯＭディスク８に記憶されている地図データでは、道路の選別によって道路が寸断された部分がつなぎ合わされて補間されており、道路の接続関係の完全性が向上されているので、ＣＤ−ＲＯＭディスク８に記憶されている地図データを用いて正確な経路探索を行うことができる。また、ＣＤ−ＲＯＭディスク８に記憶されている地図データを用いて進路案内を行う際にも、運転者が道路の寸断された部分に到達し、道が判らなくなってしまうようなことがなく、確実に進路案内を行うことができる。またＣＤ−ＲＯＭディスク８に記憶されている地図データに基づいて地図画面を表示した際には、道路の接続関係の完全性が向上されているので、表示した地図画面を運転者が自ら移動経路を選択するためなどの地図としても利用することができる。
　【００８３】
　また、図１１に示されるように、選別された道路Ｆが大きく回り込んでいる場合には、回り込んでいる部分を短絡する道路Ｅ７が補間されるので、ＣＤ−ＲＯＭディスク８に記憶されている地図データに基づいて経路探索を行う際に、道路Ｅ７を辿る経路の方が回り込んだ経路を取るよりも経路コストが小さい場合には、道路Ｅ７を辿る経路が推薦経路として選択され、道路Ｆに沿った大回りの経路が推薦経路として探索されてしまうのを防止することができる。
　【００８４】
　また図１２に示されるように、道路ＲＢと道路ＲＡとの間の道路を補間する際には、道路ＲＢを経由して道路ＲＡに至った場合に、道路ＲＡ上を図１２における左方向に進行する場合にも右方向に進行する場合にも対応可能なように、補間する道路を所定の選択規則に基づいて決定するので、ＣＤ−ＲＯＭディスク８に記憶されている地図データに基づいて経路探索を行う際に、適切な経路を探索することができる。
　【００８５】
　【発明の効果】
　以上のように本発明によれば、経路探索に用いられる第２地図データには、道路の交差点または行止まりを示すノードに関するノードデータと、各ノードを連結するリンクに関するリンクデータとのみが含まれており、従来のように道路の曲線形状を折線近似するための補間ノードや補間リンクに関するデータが含まれていないので、経路探索を行う際に、選択すべき推薦経路を互いに隣接する１つの交差点から他の交差点までの区間毎に確定することができ、探索すべき推薦経路を速やかに確定することができる。
　【００８６】
　また、第２地図データには、補間ノードおよび補間リンクに関するデータが含まれていないので、経路探索の際に演算処理すべきデータの情報量が少なくなり、処理速度を向上することができる。また、補間ノードおよび補間リンクに関するデータが含まれていないので、地図データ記憶媒体から読出した地図データを一時記憶しておくためのメモリなどの記憶容量を小さくすることができ、装置の製造コストを削減することができる。
　【００８７】
　また、地図データのリンクデータには、リンクが対応する道路属性および経路コストに関するデータが予め含まれているので、経路探索を行う際に一々道路の道路属性を検索する必要がなく、また道路の経路コストを算出する必要がなく、その結果、経路探索の処理速度を向上することができる。
　【００８８】
　また本発明によれば、経路探索に用いる地図データには、第１道路データに含まれる道路が選別によって寸断された部分をつなぎ合わせて補間する道路に関する第２道路データが含まれているので、道路の接続関係の完全性が向上された地図データに基づいて経路探索が行われる。その結果、適切な経路を推薦経路として選択することができる。
【図面の簡単な説明】
　【図１】
　本発明の一実施例のナビゲーション装置１の電気的構成を示すブロック図である。
　【図２】
　ナビゲーション装置１における経路案内を説明する機能ブロック図である。
　【図３】
　地図データの構成例を示す図である。
　【図４】
　道路形状を表現した第１地図データと道路の接続関係のみを表現した第２地図データとを説明するための図である。
　【図５】
　第１地図データの構成を説明するための図である。
　【図６】
　第２地図データの構成を説明するための図である。
　【図７】
　補間データＤＣの構成を示す図である。
　【図８】
　補間リンクテーブルＣＬＴの構成を示す図である。
　【図９】
　道路の選別処理を説明するための図である。
　【図１０】
　道路の補間処理を説明するための図である。
　【図１１】
　道路の補間処理を説明するための図である。
　【図１２】
　道路の補間処理を説明するための図である。
　【符号の説明】
　１　ナビゲーション装置
　２　操作キー
　３　中央処理装置
　５　ＣＤ−ＲＯＭ装置
　８　ＣＤ−ＲＯＭディスク
　１０　表示装置
　１１　ＧＰＳ受信機
　１３〜１５　センサ
　１９　処理回路
　２０　メモリ