図面 (/)

この項目の情報は公開日時点(1998年8月11日)のものです。
また、この項目は機械的に抽出しているため、正しく解析できていない場合があります

図面 (5)

課題

小さな容量のコンピュータでも、記録媒体に記憶されている地図の各交差点毎に付された交差点ネットリストを参照し、出発地から目的地までを結ぶ最適経路を短時間で探索できる、経路探索方法を提供する。

解決手段

出発地から目的地への正順方向ベクトルを求め、各交差点ネットリストに予め登録されている当該交差点と隣接する交差点の位置により、出発地から始まり目的地に至るまで、当該交差点における各隣接交差点へ向かう各隣接方向ベクトルを求めること、および該正順方向ベクトルと各隣接方向ベクトルとがなす角を比較して最小になる隣接交差点を選択することを、順次繰り返す。

概要

背景

自動車用ナビゲーションシステムにおいて、出発地から目的地までの最短経路を探索するには、例えば特開平6−123636号公報に記載されている方法がある。この方法は、いわゆるダイクストラ法とよばれるもので、コンピュータにより、出発地からの累計距離最短となるノード次々と選択して行き、目的地が選択されるまで探索をおこなうものである。

概要

小さな容量のコンピュータでも、記録媒体に記憶されている地図の各交差点毎に付された交差点ネットリストを参照し、出発地から目的地までを結ぶ最適経路を短時間で探索できる、経路探索方法を提供する。

出発地から目的地への正順方向ベクトルを求め、各交差点ネットリストに予め登録されている当該交差点と隣接する交差点の位置により、出発地から始まり目的地に至るまで、当該交差点における各隣接交差点へ向かう各隣接方向ベクトルを求めること、および該正順方向ベクトルと各隣接方向ベクトルとがなす角を比較して最小になる隣接交差点を選択することを、順次繰り返す。

目的

本発明は、このような問題点を解消するためになされたもので、小さな容量のコンピュータでも、出発地から目的地までを結ぶ最適経路を短時間で探索できる、経路探索方法を提供するものである。

効果

実績

技術文献被引用数
0件
牽制数
0件

この技術が所属する分野

(分野番号表示ON)※整理標準化データをもとに当社作成

ライセンス契約や譲渡などの可能性がある特許掲載中! 開放特許随時追加・更新中 詳しくはこちら

請求項1

記録媒体に記憶されている地図の各交差点毎に付された交差点ネットリストを参照し、出発地から目的地までを結ぶ経路を探索する経路探索方法において、出発地と目的地の位置により出発地から目的地への正順方向ベクトルを求め、各交差点ネットリストに予め登録されている当該交差点と隣接する交差点の位置により、出発地から始まり目的地に至るまで、当該交差点における各隣接交差点へ向かう各隣接方向ベクトルを求めること、および該正順方向ベクトルと各隣接方向ベクトルとがなす角を比較して最小になる隣接交差点を選択することを、順次繰り返して最適経路を探索する経路探索方法。

請求項2

記録媒体に記憶されている地図の各交差点毎に付された交差点ネットリストを参照し、出発地から目的地までを結ぶ経路を探索する経路探索方法において、出発地と目的地の位置により目的地から出発地への逆順方向ベクトルを求め、各交差点ネットリストに予め登録されている当該交差点と隣接する交差点の位置により、目的地から始まり出発地に至るまで、当該交差点における各隣接交差点へ向かう各隣接方向ベクトルを求めること、および該逆順方向ベクトルと各隣接方向ベクトルとがなす角を比較して最小になる隣接交差点を選択することを、順次繰り返して最適経路を探索する経路探索方法。

請求項3

請求項1で探索した最適経路、および請求項2で探索した最適経路を照合することを特徴とする経路探索方法。

技術分野

0001

本発明は、自動車に搭載されるナビゲーションシステムで、出発地から目的地への最適な経路を探索する方法に関するものである。

背景技術

0002

自動車用のナビゲーションシステムにおいて、出発地から目的地までの最短経路を探索するには、例えば特開平6−123636号公報に記載されている方法がある。この方法は、いわゆるダイクストラ法とよばれるもので、コンピュータにより、出発地からの累計距離最短となるノード次々と選択して行き、目的地が選択されるまで探索をおこなうものである。

発明が解決しようとする課題

0003

しかしながら、上記した従来の探索方法では、出発地から様々な経路での累計距離を計算し、互いに比較しながらより累計距離の短い経路を選択していくという処理を行うので、出発地からみて目的地と反対方向へも探索を行ってしまい、最適経路の探索が完了するまでにかなり長い時間を要する。またコンピュータの処理も多くのメモリを必要とし、ハードウエア的にみて大規模な装置が要求される。

0004

本発明は、このような問題点を解消するためになされたもので、小さな容量のコンピュータでも、出発地から目的地までを結ぶ最適経路を短時間で探索できる、経路探索方法を提供するものである。

課題を解決するための手段

0005

前記の目的を達成するためになされた本発明の第1発明は、記録媒体に記憶されている地図の各交差点毎に付された交差点ネットリストを参照し、出発地から目的地までを結ぶ経路を探索する経路探索方法であり、出発地と目的地の位置により出発地から目的地への正順方向ベクトルを求め、各交差点ネットリストに予め登録されている当該交差点と隣接する交差点の位置により、出発地から始まり目的地に至るまで、当該交差点における各隣接交差点へ向かう各隣接方向ベクトルを求めること、および該正順方向ベクトルと各隣接方向ベクトルとがなす角を比較して最小になる隣接交差点を選択することを、順次繰り返して最適経路を探索するものである。

0006

このように構成されたことで、出発地から全方向に広がる様々な経路での累計距離を計算し、互いに比較しながらより累計距離を選択していくという複雑な処理を行わなくても済み、出発地から目的地までを結ぶ最適経路を短時間で探索できるようになる。

0007

同じく本発明の第2発明は、記録媒体に記憶されている地図の各交差点毎に付された交差点ネットリストを参照し、出発地から目的地までを結ぶ経路を探索する経路探索方法であり、出発地と目的地の位置により目的地から出発地への逆順方向ベクトルを求め、各交差点ネットリストに予め登録されている当該交差点と隣接する交差点の位置により、目的地から始まり出発地に至るまで、当該交差点における各隣接交差点へ向かう各隣接方向ベクトルを求めること、および該逆順方向ベクトルと各隣接方向ベクトルとがなす角を比較して最小になる隣接交差点を選択することを、順次繰り返して最適経路を探索するものである。

0008

この第2発明は、第1発明とは逆に目的地から出発地へと経路を探索してゆくもので、第1発明と同様に複雑な処理を行わなくても済み、出発地から目的地までを結ぶ最適経路を短時間で探索できる。

0009

また第3発明は、第1発明で探索した最適経路、および第2発明で探索した最適経路を照合する経路探索方法である。

0010

このように経路を照合することで、得られる出発地から目的地までを結ぶ最適経路がより信頼性の高いものとなる。

発明を実施するための最良の形態

0011

本発明の経路探索方法は、CD−ROMなどに記載されている地図上の各交差点ネットリストに、その交差点に隣接する各隣接交差点の位置情報を登録しておき、入力される出発地からこれに対する交差点ネットリストに登録された隣接交差点への方向ベクトルの内、出発地から目的地への正順方向ベクトルとのなす角θが、予め設定された角度以内に存在するものを第1経由地交差点と定める。次に第1経由地交差点から、これに対する交差点ネットリストに登録された隣接交差点への方向ベクトルの内、第1経由地交差点から目的地への方向ベクトルとの角θが設定角内に存在するものを第2経由地交差点と定める。以下、同様にして第3経由地交差点以降の各経由地交差点を求めてゆき、最後に求めた経由地交差点が目的地に直近となったところで探索を止め、各経由地交差点を正順に並べて出発地から目的地までを結ぶ最適な経路とする。

0012

以下、本発明の好適な実施例を図面を参照しながら説明する。

0013

図1は本発明の経路探索方法を実施するための車両用経路誘導装置の実施例の基本構成ブロック図である。同図の車両用経路誘導装置は、演算処理装置4を中心とし、演算処理装置4へのデータ供給手段として、自車位置検出装置1、CD−ROM(コンパクトディスクメモリ)7、データを手動入力するためのリモートコントロールキー8を有している。さらに演算処理装置4からのデータ出力手段として、例えば液晶表示による表示装置9を有している。

0014

自車位置検出装置1は、GPS(Grobal Positioning System)と呼ばれる衛星航法装置であり、GPS受信機およびGPSアンテナ3を備えている。さらに自車位置検出装置1は、四六時中、高い検出精度を得るため距離センサ5と方位センサ6による位置検出手段を併設している。CD−ROM7は地図を記憶してあり、その地図は道路の交差点ネットリストを持っている。

0015

図2図1に示した演算処理装置4の機能ブロック図である。演算処理装置4は経路探索処理部11、最適経路計算部12、地図データ管理部13、メモリ14、表示制御部15を有している。

0016

この実施例の車両用経路誘導装置を用いて本発明の第1発明を適用する経路探索方法を実施した例を記載する。

0017

記載する例は、図3に示す地図で出発地から目的地に到達する最適経路を探索するものである。この地図はCD−ROM7に記録されているものである。出発地周辺および目的地周辺は、矩形網目状に道路があり、略の道路をA,B,C,D,E,Fとし、略東西の道路を1,2,3,4,5,6,7と名づけ、各交差点は、A道路上にA1,A2,A3,A4,A5,A6,A7、B道路上にB1,B2,B3,,,、C道路上にC1,C2,C3,,,、またD道路上、E道路上、F道路上にも各々存在するものとする。出発地に直近の交差点を第0次経由地交差点B2とし、目的地に直近交差点を第n次経由地交差点D6とする。

0018

上記の各交差点には、図4に示す交差点ネットリストが予め登録されている。同図に示すように、その交差点の位置情報とともに隣接する交差点(通常は複数ある)の位置情報が登録されている。

0019

上記のような条件の下、車両用経路誘導装置スイッチを入れると、自車位置検出装置1のGPS航法装置2・3(および/または距離センサ5と方位センサ6)が動作し、自車位置が検出される。この状態から車両用経路誘導装置は、図5フローチャートに示すソフトウエア立ち上がって経路探索処理部11の制御で動作する。

0020

このフローチャートのステップ101で、自車位置検出装置1で検出された自車位置が経路探索処理部11に出発地として指定され、その周辺の地図がCD−ROM7からメモり14に読み込まれる。さらにリモートコントロールキー8で手動により目的地の地図を指定し、地図が表示装置9に表示されたら、そこで目的地の位置を指定する。最適経路計算部12では出発地から目的地に至る直線の正順方向ベクトルを算出し、メモり14に蓄積しておく。尚、出発地と目的地の中間で未だメモり14に読み込まれていない地図があれば、その目録が地図データ管理部13に読み込まれる。

0021

ステップ102では、出発地を第0次経由地交差点A0として地図データ管理部13にある交差点ネットリスト(図4参照)から各隣接交差点への方向ベクトルを最適経路計算部12により算出する。図3に示すように出発地(第0次経由地交差点)B2には4つの交差点B1,C2,B3,A2が隣接して存在する。ここで第0次経由地交差点B2から4つの交差点B1,C2,B3,A2に向かう方向ベクトルの中から、ステップ101で算出された出発地から目的地への順方向ベクトルとのなす角度θの絶対値が設定値以内のものを探す。本例では設定値を45°としてある。

0022

尚、角度θを求めるには次式に従う。出発地の経緯度を(xs,ys)、目的地の経緯度を(xd,yd)、隣の交差点の経緯度を(xm,ym)の整数、出発地から目的地の距離をLSD、出発地から隣の交差点までの距離をLSmとしたとき、ベクトルの内積により

0023

0024

となり、θ=cos-1αである。

0025

4つの交差点B1,C2,B3,A2のなかに設定角以下(θ<45°)が存在し(ステップ103)、交差点C2および交差点B3の2つが該当する(ステップ104)。

0026

ステップ105で、θが最少角の交差点B2が選ばれて第1次経由地交差点となり、交差点B2の交差点ネットリストの第6項に前交差点(第0次経由地交差点B2)のシーケンシャル番号、同じく第7項に累計距離をそれぞれ登録する。ステップ106で交差点B3が目的地ではないので、再びステップ102に戻る。交差点B3に隣接する交差点C3,B4,A2の内、交差点B4が同様にして選ばれると(ステップ105)、交差点B4が第2次経由地交差点となる。

0027

以降、同様にして目的地に到達するまで探索を行い、選択された交差点ネットリストに前交差点シーケンシャル番号と累計距離を登録していく。また、ステップ103で、交差点のなかに設定角以下(θ<45°)が存在しない(目的地に向かう方向が行き止まり)ときには、隣接交差点への距離が最も近いものを選択する。

0028

以上の処理を順次繰り返し、目的地に到達したときには(ステップ106)、ステップ107で最適経路計算部12により各経由地交差点番号を正順に並べ、最適な経路が導出される。

0029

尚、上記実施例は本発明の第1発明を適用する経路探索方法を実施したものであるが、上記とは出発地と目的地を入れ換え、目的地から逆順に出発地へ探索してゆけば、本発明の第2発明を適用する経路探索方法を実施したことになり、最適な経路が導出される。

0030

また第1発明を適用する経路探索方法、第2発明を適用する経路探索方法をともに実施し、両者で導出された経路を照合すれば第3発明を実施したことになる。照合の結果、両者で得られた経路が一致すればその経路はほぼ絶対的に正しいものと判断できる。一致しない場合はより適切な方を仮に選び、途中の交差点を仮目的地にして再度の探索する等の処置が可能となる。

発明の効果

0031

以上、詳細に説明したように、本発明を適用する経路探索方法によれば、出発地から全方向に広がる様々な経路での累計距離を計算し、互いに比較しながらより累計距離を選択していくという複雑な処理を行わなくても済むことになる。したがって処理を実行するコンピュータが小さな容量であっても、短時間で最適な経路が導出される。

図面の簡単な説明

0032

図1本発明を適用する経路探索方法を実施するための車両用経路誘導装置の実施例の基本構成ブロック図である。
図2本発明を適用する経路探索方法を実施するための処理装置内部の機能ブロック図である。
図3本発明を適用する経路探索方法で出発地から目的地に到達する最適経路を探索する例の出発地周辺から目的地周辺に至る地図の例である。
図4本発明を適用する経路探索方法を実施するための交差点ネットリストの説明図である。
図5本発明を適用する経路探索方法の実行手順の一例を示すフローチャートである。

--

0033

1は自車位置検出装置、2はGPS受信機、3はGPSアンテナ、4は処理装置、5は距離センサ、6は方位センサ、7はCD−ROM(コンパクトディスクメモリ)、8はリモートコントロールキー、9は表示装置、11は経路探索処理部、12は最適経路計算部、13は地図データ管理部、14はメモリ、15は表示制御部である。

ページトップへ

この技術を出願した法人

この技術を発明した人物

ページトップへ

関連する挑戦したい社会課題

関連する公募課題

該当するデータがありません

ページトップへ

技術視点だけで見ていませんか?

この技術の活用可能性がある分野

分野別動向を把握したい方- 事業化視点で見る -

(分野番号表示ON)※整理標準化データをもとに当社作成

ページトップへ

おススメ サービス

おススメ astavisionコンテンツ

新着 最近 公開された関連が強い技術

  • 株式会社フォトラダの「 車両の逆走防止システム」が 公開されました。( 2020/12/17)

    【課題】大掛かりな工事を必要としない、車両の逆走防止システムを提供する。【解決手段】本発明の一実施形態に係る逆走防止システム10は、車両に搭載される受信機32であって、所定の逆走区間において車両が逆走... 詳細

  • 株式会社Strolyの「 情報処理装置、情報処理方法、およびプログラム」が 公開されました。( 2020/12/17)

    【課題】従来、付加情報に応じて、表示態様を変更した地図表現データをユーザに提供できなかった。【解決手段】表現している領域を特定する領域特定情報を含む1以上の属性値に対応付けられたデータであり、地図を表... 詳細

  • 三菱電機株式会社の「 運転支援装置、運転支援システムおよび運転支援方法」が 公開されました。( 2020/12/17)

    【課題・解決手段】運転支援装置(2)は、運転者の視界が撮影された映像(3a)内における、運転者の視界に現れた物体に対して運転者が反応を起こすまでの反応時間情報の分布を示す反応時間分布データ(4a)を用... 詳細

この 技術と関連性が強い技術

関連性が強い 技術一覧

この 技術と関連性が強い人物

関連性が強い人物一覧

この 技術と関連する社会課題

関連する挑戦したい社会課題一覧

この 技術と関連する公募課題

該当するデータがありません

astavision 新着記事

サイト情報について

本サービスは、国が公開している情報(公開特許公報、特許整理標準化データ等)を元に構成されています。出典元のデータには一部間違いやノイズがあり、情報の正確さについては保証致しかねます。また一時的に、各データの収録範囲や更新周期によって、一部の情報が正しく表示されないことがございます。当サイトの情報を元にした諸問題、不利益等について当方は何ら責任を負いかねることを予めご承知おきのほど宜しくお願い申し上げます。

主たる情報の出典

特許情報…特許整理標準化データ(XML編)、公開特許公報、特許公報、審決公報、Patent Map Guidance System データ