(57)【要約】  本発明は、経路探索方法およびシステムに関し、より詳しくは、道路情報と連関したレイヤ(Layer)を用い、前記道路情報に基づいて経路を探索するために必要とされる時間およびシステムの負荷を減少させることができる経路探索方法およびシステムに関する。本発明による経路探索方法は、所定の数値地図データベースに、道路に対応する道路情報および前記道路情報と連関し所定の基準によって決定されたレイヤ(layer)を維持する段階と、少なくとも一つ以上の前記レイヤを含む所定の第1レイヤ集合と連関した前記道路情報に基づいて出発地から所定の第1距離以内における第1経路を探索する段階と、少なくとも一つ以上の前記レイヤを含む所定の第2レイヤ集合と連関した前記道路情報に基づいて前記出発地より前記所定の第1距離だけ離れている地点から、前記目的地より所定の第2距離だけ離れている地点までの第2経路を探索する段階と、少なくとも一つ以上の前記レイヤを含む所定の第3レイヤ集合と連関した前記道路情報に基づいて目的地から前記第2距離以内における第3経路を探索する段階と、前記第1経路、前記第2経路および前記第3経路を用いて前記出発地から前記目的地までの経路を生成する段階とを含むことを特徴とする。本発明によると、所定の道路情報に基づいて経路を探索するために必要とされる時間を減少させ、前記経路を探索するための経路探索システムにおける負荷を減少させることができる。
2006527837.tif 000002
【特許請求の範囲】
【請求項１】
経路探索方法において、
道路に対応する道路情報および前記道路情報と連関して所定の基準によって決定されたレイヤ(layer)を、所定の数値地図データベースに維持する段階と、
少なくとも一つ以上の前記レイヤを含む所定の第1レイヤ集合と連関した前記道路情報に基づいて、出発地から所定の第1距離以内で第1経路を探索する段階と、
少なくとも一つ以上の前記レイヤを含む所定の第2レイヤ集合と連関した前記道路情報に基づいて、前記出発地より前記所定の第1距離だけ離れている地点から、前記目的地より所定の第2距離だけ離れている地点までの第2経路を探索する段階と、
少なくとも一つ以上の前記レイヤを含む所定の第3レイヤ集合と連関した前記道路情報に基づいて、目的地から前記第2距離以内で第3経路を探索する段階と、
前記第1経路、前記第2経路および前記第3経路を用いて前記出発地から前記目的地までの経路を生成する段階とを含むことを特徴とする経路探索方法。
【請求項２】
前記第1レイヤ集合または前記第3レイヤ集合は、すべてのレイヤを含む集合であることを特徴とする請求項1に記載の経路探索方法。
【請求項３】
ユーザの移動通信端末機から前記出発地および前記目的地の入力を受ける段階と、
前記生成された経路を前記移動通信端末機に送信する段階とを更に含むことを特徴とする請求項1に記載の経路探索方法。
【請求項４】
前記移動通信端末機において、
GPS受信機を用いて、前記移動通信端末機の現在位置を前記移動通信端末機から受信する段階と、
前記送信された経路および前記現在位置に基づいて、前記移動通信端末機が前記送信された経路から離脱したかを判断する段階と、
前記ユーザが前記送信された経路から離脱した場合、前記現在位置を前記出発地として設定する段階が遂行されることを特徴とする請求項3に記載の経路探索方法。
【請求項５】
前記所定の基準は、前記道路の種類、前記道路を利用する車両の通行量、前記道路の車線数の中のいずれか一つ以上であることを特徴とする請求項1に記載の経路探索方法。
【請求項６】
前記所定の第1距離および前記所定の第2距離は、ユーザから入力された距離、および管理者が設定した距離の中のいずれか一つによって決定されることを特徴とする請求項1に記載の経路探索方法。
【請求項７】
経路探索方法において、
所定の数値地図データベースに、道路に対応する道路情報を維持する段階と、
前記道路情報に基づいて、出発地から目的地までの一つ以上の第1候補経路を計算する段階と、
前記第1候補経路の中から、前記目的地から一定距離に位置する臨界地点に到達した所定個数の第1候補経路を第2候補経路として決定する段階と、
前記第2候補経路として決定されなかった前記第1候補経路の計算を中止する段階と、
前記臨界地点から前記目的地まで前記第2候補経路を計算する段階と、
計算が完了した前記第2候補経路を経路として決定する段階とを含むことを特徴とする経路探索方法。
【請求項８】
請求項1ないし7のいずれか一項の方法を実行させるためのプログラムを記録したコンピュータ読み取り可能な記録媒体。
【請求項９】
経路探索システムにおいて、
道路に対応する道路情報および前記道路情報と連関して所定の基準によって決定されたレイヤ(layer)を維持するための数値地図データベースと、
ユーザの移動通信端末機から出発地および目的地の入力を受けるためのユーザ受信部と、
前記道路情報に基づいて前記出発地から前記目的地までの経路を探索する経路探索部と、
前記探索された経路を前記移動通信端末機に送信するためのユーザ送信部
とを含み、
前記経路探索部は少なくとも一つ以上のレイヤを含む所定の第1レイヤ集合と連関した前記道路情報に基づいて、前記出発地から所定の第1距離以内で第1経路を探索し、
少なくとも一つ以上の前記レイヤを含む所定の第2レイヤ集合と連関した前記道路情報に基づいて、前記出発地より前記所定の第1距離だけ離れている地点から、前記目的地より所定の第2距離だけ離れている地点までの第2経路を探索し、
少なくとも一つ以上の前記レイヤを含む所定の第3レイヤ集合と連関した前記道路情報に基づいて、目的地から前記第2距離以内で第3経路を探索し、
前記第1経路、前記第2経路および前記第3経路を用いて前記出発地から前記目的地までの経路を生成することを特徴とする経路探索システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、経路探索方法およびシステムに関し、より詳しくは、道路情報と連関したレイヤ(Layer)を用い、前記道路情報に基づいて経路を探索するために必要とされる時間およびシステムの負荷を減少させることができる経路探索方法およびシステムに関する。
【背景技術】
【０００２】
最近、通信網を用いたサービスの提供によって携帯型コンピュータおよび移動電話などの無線通信環境内における情報検索の機会が増加している。これに伴い、ユーザは自由に移動しながら、いつどこででも必要な情報サービスを検索して提供を受けることが可能となった。
【０００３】
ナビゲーションシステム(Navigation System)は、人工衛星を用いて車両などの運送装置(vehicle)の走行のための情報を提供するシステムであって、自動航法システムとも言われる。このようなナビゲーションシステムは、地球上に浮かんでいるGPS(global positioning system)衛星からGPS受信機を用いて所定のデータを受信し、前記受信されたデータに基づいて自分の位置を計算する。地球上には多数のGPS衛星が浮かんでいるが、運送装置は地球上のどの地域にいたとしても3つのGPS衛星からGPS信号を受信することができ、前記3つのGPS衛星から受信されたGPS信号に基づいて自分の位置を計算することができるようになっている。ナビゲーションシステムは、このように計算された自分の位置情報に基づいて、多様な走行情報を前記車両などの運送装置に提供する。このようなナビゲーションシステムは、既存では主に航空機や船舶などの大型移動体の位置計算と航法に用いられていたが、最近では自動車などにも広く用いられている。前記ナビゲーションシステムは、運送装置の現在の位置情報、運送装置の現在の位置から前記運送装置の目的地までの経路情報、前記位置情報および経路情報と関連した地図情報、交通状況情報など、非常に多様な情報をユーザに提供している。
【０００４】
このようなナビゲーション装置において、運送装置の現在位置などの情報をユーザに伝達する時に地図を用いると、ユーザがより簡単に前記現在位置などの情報を認識することができるため、地図情報が共に提供されるのが一般的である。
【０００５】
従来技術によると、このような地図情報は、CDロムまたはDVDロムのような格納媒体を介して提供されていた。このような従来技術によるナビゲーション装置は、CDロムなどの格納媒体に格納された地図情報を必要な度に読み取り、これを所定の表示手段に表示していた。しかし、このような従来技術のナビゲーション装置において、地図情報を更新しなければならない場合、CDロムなどの格納媒体を交換する必要があるため、その後のアップデート時に相当な不便があった。すなわち、ユーザは前記地図情報を含んだCDロムの提供者から継続してCDロムを追加購入しなければならないという経済的および時間的負担が発生していた。また、前記地図情報の提供者が変更される地図情報をリアルタイムで反映したCDロムなどを製作してユーザに提供することは不可能であるため、変更された地図情報(例えば、道路、建物などが新しく生じたり消滅した場合)をリアルタイムでユーザに提供することができなかった。同様な理由として、既存の地図情報に基づいて経路を探索してユーザに経路情報を提供する場合、前記経路情報に地図情報上の変更事項が反映されないという問題がある。
【０００６】
また、いわゆるテレマティックス(tele-matics)と呼ばれる更に他の従来技術によると、移動電話などの移動通信端末機を用いたナビゲーションサービスが提供されている。前記テレマティックスサービスは、音声を用いてユーザに道を案内したり、自分の車が交通事故にあった場合、GPS衛星を用いて自動的に事故車の位置を追跡し、最も近くに位置する119救助隊や病院などに前記情報を伝達することによって救難活動を簡単にしている。しかし、従来技術による移動電話などを用いたナビゲーションサービスにおいては、移動電話のメモリサイズによる制限のため、地図情報を移動電話に格納しておくことができないという問題点があった。これにより、前記従来技術によると、車の位置情報、走行情報などをユーザに提供する時、地図を共にユーザに提供することができずに音声またはテキスト形態で提供していたため、ユーザが従来技術によるナビゲーションシステムを用いることに不便さが生じていた。
【０００７】
これにより、通信網を用いて移動通信端末機に地図情報を提供することによって、道路などの地図情報の変更をリアルタイムで反映することができるナビゲーションシステムが要求されている。
【０００８】
無線通信網を用いて前記移動通信端末機に地図情報を提供する場合には、前記移動通信端末機に前記地図情報をリアルタイムで提供するため、地図提供に必要とされる時間を減少させることが重要な問題となる。
【０００９】
一方、前記ナビゲーションサービスにおいて、ユーザが必要とする重要なサービスの中の一つは、経路探索の結果から得られた経路情報を提供することである。
【００１０】
経路探索は、一般的に所定の数値地図データベースに格納されている地図情報に基づいて出発地から目的地までの経路を計算し、計算された経路の中から適切な経路(例えば、最短経路)を選択する過程を含む。この時、出発地から目的地までの経路は多数存在するのが通常であるため、前記適切な経路を選択するまで多数の経路を計算するための時間が必要である。このような経路の計算は、前記移動通信端末機に経路探索結果を提供するまでの時間の遅延または所定の経路探索システムにおける負荷の原因となる。
【００１１】
このように、経路探索に必要な作業量が多い程、前記移動通信端末機のユーザは、前記適切な経路の提供を受けるまで待たなければならないという不便さがあり、ナビゲーションサービスを提供するサービス社側においても、経路探索システムにおける負荷を考慮し、十分な容量の装備を購入しなければならないなどの不便さを経るより外ない。従って、経路探索に必要とされる時間を短縮させ、経路探索システムの負荷を減少させるための方案が要求される。
【００１２】
以上、無線通信網を用いて所定の地図提供サーバから経路情報および地図情報の提供を受ける場合に対して説明したが、従来技術のように無線通信網を介して地図情報を提供せず、所定の地図提供サーバから有線通信網を介して地図情報を提供する場合、または記録媒体に格納されている地図情報を用いてユーザ端末機で経路を探索する場合においても、同様な理由で上記のような方案が要求される場合がある。
【発明の開示】
【発明が解決しようとする課題】
【００１３】
本発明は、上記のような従来技術を改善するために案出されたものであり、所定の道路情報に基づいて経路を探索するために必要とされる時間を減少させ、前記経路を探索するための経路探索システムにおける負荷を減少させることができる経路探索方法およびシステムを提供することを目的とする。
【課題を解決するための手段】
【００１４】
上記の目的を達成し、従来技術の問題点を解決するために、本発明の一つの態様によれば、道路に対応する道路情報および前記道路情報と連関して所定の基準によって決定されたレイヤ(layer)を所定の数値地図データベースに維持する段階と、少なくとも一つ以上の前記レイヤを含む所定の第1レイヤ集合と連関した前記道路情報に基づいて出発地から所定の第1距離以内で第1経路を探索する段階と、少なくとも一つ以上の前記レイヤを含む所定の第2レイヤ集合と連関した前記道路情報に基づいて前記出発地より前記所定の第1距離だけ離れている地点から前記目的地より所定の第2距離だけ離れている地点までの第2経路を探索する段階と、少なくとも一つ以上の前記レイヤを含む所定の第3レイヤ集合と連関した前記道路情報に基づいて目的地から前記第2距離以内で第3経路を探索する段階と、前記第1経路、前記第2経路および前記第3経路を用いて前記出発地から前記目的地までの経路を生成する段階とを含む経路探索方法を提供する。
【００１５】
本発明の経路探索方法は、好ましくは、ユーザの移動通信端末機から前記出発地および前記目的地の入力を受ける段階と、前記生成された経路を前記移動通信端末機に送信する段階とを更に含む。
【００１６】
本発明の経路探索システムは、好ましくは、GPS受信機を用いて前記移動通信端末機の現在位置を前記移動通信端末機から受信する段階と、前記送信された経路および前記現在位置に基づいて前記移動通信端末機が前記送信された経路から離脱したかを判断する段階と、前記ユーザが前記送信された経路から離脱した場合に前記現在位置を前記出発地として設定する段階とを遂行する。
【００１７】
また、本発明の経路探索方法は、GPS受信機を用いて前記移動通信端末機から前記移動通信端末機の現在位置を受信する段階と、前記送信された経路および前記現在位置に基づいて前記移動通信端末機が前記経路を離脱したかを判断する段階と、前記ユーザが前記経路を離脱した場合に前記現在位置を出発地として設定する段階とを更に含む。
【００１８】
また、本発明の他の態様によれば、道路に対応する道路情報を所定の数値地図データベースに維持する段階と、前記道路情報に基づいて出発地から目的地までの一つ以上の第1候補経路を計算する段階と、前記第1候補経路の中で前記目的地から一定距離に位置する臨界地点に到逹した所定個数の第1候補経路を第2候補経路として決定する段階と、前記第2候補経路として決定されなかった前記第1候補経路の計算を中止する段階と、前記臨界地点から前記目的地まで前記第2候補経路を計算する段階と、計算が完了した前記第2候補経路を経路として決定する段階とを含む経路探索方法を提供する。
【００１９】
また、本発明の更なる態様によれば、道路に対応する道路情報および前記道路情報と連関して所定の基準によって決定されたレイヤ(layer)を維持するための数値地図データベースと、ユーザの移動通信端末機から出発地および目的地の入力を受けるためのユーザ受信部と、前記数値地図データベースに維持されている道路情報に基づいて前記出発地から前記目的地までの経路を探索する経路探索部と、前記探索された経路を前記移動通信端末機に送信するためのユーザ送信部とを含み、前記経路探索部は少なくとも一つ以上のレイヤを含む所定の第1レイヤ集合と連関した前記道路情報に基づいて前記出発地から所定の第1距離以内で第1経路を探索し、少なくとも一つ以上の前記レイヤを含む所定の第2レイヤ集合と連関した前記道路情報に基づいて前記出発地より前記所定の第1距離だけ離れた地点から前記目的地より所定の第2距離だけ離れた地点までの第2経路を探索し、少なくとも一つ以上の前記レイヤを含む所定の第3レイヤ集合と連関した前記道路情報に基づいて目的地から前記第2距離以内で第3経路を探索し、前記第1経路、前記第2経路および前記第3経路を用いて前記出発地から前記目的地までの経路を生成することを特徴とする経路探索システムを提供する。
【発明の效果】
【００２０】
本発明によると、道路情報全体に基づいて経路を探索した場合と同一またはほぼ類似した経路をユーザに提供すると同時に、前記経路を探索する時間を減少させ、経路探索を遂行する経路探索システムにおける負荷を減少させることができる経路探索方法およびシステムが提供される。経路探索に必要とされる時間が減少するため、ユーザが経路探索を要請し、前記要請に応答した経路の提供を受けるまでの時間も短縮される。
【００２１】
また、本発明によると、前記ユーザが前記経路から離脱した場合、前記ユーザの現在位置を出発地として設定し、新しい経路を前記ユーザに提供することができる経路探索方法が提供される。
【００２２】
また、本発明によると、経路として選択される可能性が高い候補経路を除外した候補経路の計算を、その計算が完了する前に中止することによって、経路探索にかかる時間を減少させ、経路探索システムにおける負荷を減少させることができるような経路探索方法が提供される。
【発明を実施するための最良の形態】
【００２３】
以下、添付された図面を参照して、本発明の実施例を詳しく説明する。
【００２４】
図1は、本発明の一実施例による経路探索方法を示した流れ図である。本実施例による経路探索方法は、所定の経路探索システムで遂行されることができ、図2は、前記経路探索システムのネットワーク連結を示した図である。図面符号(210)は経路探索システムを、図面符号(230)は通信網(220)を介して経路探索システム(210)に接続する移動通信端末機を表示する。経路探索システム(210)は、所定の出発地および目的地に該当する経路を探索して移動通信端末機(230)に前記経路を提供する。
【００２５】
段階(101)で、経路探索システム(210)は、所定の数値地図データベースに道路に対応する道路情報および前記道路情報と連関し、所定の基準によって決定されたレイヤ(Layer)を維持する。
【００２６】
前記道路情報は、地図上で前記道路を特定するためのデータであり、多様な方式で定義される。図3は、道路情報の一例を説明するための図面である。図3において、道路情報は、ノード(Node)、リンク(Link)および補間点(Interpolation Points)を含む。N1で表示される黒色の点はノードを、L1、L2およびL3で表示される前記ノードの間を連結する線はリンクを意味する。前記ノードは、道路が交差する交差点または道路上の袋小路となっている地点を表示するための情報であり、前記リンクは前記ノードの間の道路を表示するための情報である。
【００２７】
また、前記補間点は、曲線からなる道路において前記道路が通過する地点を表示するための情報であって、通常、道路の曲率が大きい程、道路を表示するためにより多くの補間点が必要となる。
【００２８】
このように、道路に対応する道路情報を定義することができ、道路情報はこの他にも多様な方式で定義されることができる。
【００２９】
また、図4は、前記数値地図データベースに維持される前記道路情報および前記道路情報と連関したレイヤの一例を示した図である。本発明の他の実施例によると、前記道路情報と連関するレイヤは、前記道路の種類、前記道路を利用する車両の通行量、前記道路の車線数の中の1つ以上を基準として決定される。
【００３０】
道路の種類の例として、高速道路または都市化高速道路と連関したレイヤはレイヤ2と、一般国道または地方道路と連関したレイヤはレイヤ3として決定することができる。
【００３１】
また、車線の種類に従い、同じ地方道路の場合においても、4車線以上の地方道路に対してはレイヤ3と、4車線未満の地方道路に対してはレイヤ4として定義することができる。
【００３２】
また、4車線未満の地方道路であったとしても、前記地方道路の利用率、すなわち車両の通行量が多い地方道路に対するレイヤはレイヤ3として定義することができる。一日の前記地方道路を利用する車両数の平均値、または特定時間帯における前記地方道路を利用する車両数の平均値などを算出して前記レイヤを決定するのに反映することができる。特定時間帯における平均値を利用する場合には、一つの道路情報に対して各時間帯における各レイヤを維持しておき、ユーザが経路を要請する時間帯に応じた、相違したレイヤに基づいて探索がなされるようにすることができる。
【００３３】
すなわち、原則的に道路の種類に基づいて道路と連関したレイヤを決定することができ、それ以外の多様な基準によって前記レイヤを変更することができる。また、‘経路探索情報の完結性’を保障するように前記レイヤを決定する場合もある。
【００３４】
図5は、経路探索情報の完結性を保障するように所定の道路に対するレイヤを決定する場合を説明するための図面である。後述するように、経路探索システム(210)は、所定のレイヤ集合と連関した道路情報に基づいて経路を探索する。従って、前記レイヤ集合に含まれるレイヤに連関した道路情報は、経路探索のための資料として用いられるが、前記レイヤ集合に含まれていないレイヤと連関した道路情報は、前記経路探索のための資料として用いられない。
【００３５】
図5で示すように、ある道路は、2車線道路である一部区間を除くと4車線道路からなっている場合がある。この時、図面符号(L521ないしL523)で示した各リンクは、図面符号(N511およびN512)で示した各ノードによって区分される。この時、道路の種類または車線数によって道路情報に対応するレイヤを決定する場合、前記数値地図データベースには、例えばリンク(L521)およびリンク（L522)に対してはレイヤ3が、リンク(L523)に対してはレイヤ4が維持される。
【００３６】
ところで、後述するように、経路探索システム(210)が、前記レイヤ4は含まずに前記レイヤ3のみを含むレイヤ集合と連関した道路情報にのみ基づいて経路を探索する場合には、前記道路(道路情報中、リンク(L521)ないしリンク（L523)に対応する)は、リンク(L523)に対応する道路部分が存在しない場合に該当するようになり、リンク(L521)からリンク(L522)に対応する道路までの経路は探索されないという問題がある。
【００３７】
従って、上述したような場合には、道路の種類または車線数が相違した場合でも、リンク(L523)と連関したレイヤは、リンク(L521)およびリンク（L522)と連関したレイヤと同様にレイヤ3として設定する必要性がある。このように、実際の道路状況を反映して各道路情報と連関したレイヤを決定することによって、‘経路探索情報の完結性’を保障することができるようになる。すなわち、レイヤを用いて経路探索過程における計算量を減少させると同時に、道路情報全体に基づいて経路を探索した場合と同じ経路探索結果を保障することができるようになる。
【００３８】
一方、上述したレイヤ2、レイヤ3などは、各レイヤを識別するために用いられたものであり、実際の各レイヤの格納方式および表現方式はこれと相違する場合もある。
【００３９】
段階(102)で、経路探索システム(210)は、通信網(220)を介してユーザの移動通信端末機(230)から出発地および目的地の入力を受ける。図6の(a)ないし(f)は、移動通信端末機(230)で提供される、前記出発地および前記目的地を入力するための入力ウィンドウの一例を示した図である。
【００４０】
図6の(a)の入力ウィンドウで、ユーザは、経路探索のために提供されるメニューである‘初めての道の案内’を選択する。図6の(b)における‘名称検索’(例えば“ソウル市役所”)方式や‘住所検索'(例えば“ノンヒョン洞142”)方式のように、経路探索システム(210)は、ユーザが出発地および目的地を入力するための一つ以上の方式を提供する。図6の(c)で、ユーザは、名称検索方式によって目的地キーワードである“ササン区役所”を入力すると、同図の(d)のような検索結果がディスプレイされる。ユーザは、前記検索結果の中から自分が意図した目的地を選択することができる。
【００４１】
一方、本発明の他の実施例によると、経路探索システム(210)は、経由地を設定する機能を更に提供する。ユーザは、図6の(e)で示したように経由地を選択することができ、前記経由地が入力される場合には、経路探索システム(210)は、出発地から目的地までの経路の中から前記経由地を経由する経路を探索してユーザに提供する。
【００４２】
図6の(f)は、ユーザが出発地を入力することができる入力ウィンドウを示している。本実施例においては、移動通信端末機(230)の現在位置(移動通信端末機(230)と連関したGPS受信機によって受信された移動通信端末機(230)の現在位置に相当する)を出発地として設定する場合を示しているが、出発地の場合にも上述した目的地を入力するための方式と同一の方式が用いられるということは言うまでもない。
【００４３】
上述したような方式によって、経路探索システム(210)は、移動通信端末機(230)から出発地および目的地が入力されると、段階(103)ないし段階（105)で、前記出発地から前記目的地までの経路を探索する。
【００４４】
この時、図7で示したように、前記出発地から所定の第1距離(d1)以内にある地域を第1地域、前記目的地から所定の第2距離(d2)以内にある地域を第3地域、前記第1地域および前記第3地域以外の地域を第2地域と定義することにする。
【００４５】
経路探索システム(210)は、前記数値地図データベースに維持されている少なくとも一つ以上の前記レイヤを含む所定の第1レイヤ集合と連関した前記道路情報に基づいて前記出発地からの経路を前記第1地域において探索する（段階(103)）。
【００４６】
また、同様に、経路探索システム(210)は、少なくとも一つ以上の前記レイヤを含む第2レイヤ集合と連関した前記道路情報に基づいて、前記第2地域において第2経路を探索し段階(104)）、少なくとも一つ以上の前記レイヤを含む所定の第3レイヤ集合と連関した前記道路情報に基づいて、目的地までの第3経路を前記第3地域において探索する（段階(105)）。
【００４７】
本実施例による経路探索方法は、出発地および目的地付近の地域においては全体または大部分の道路情報に基づいて経路を探索し、それ以外の地域においては高速道路、国道などに対応する道路情報に基づいて経路を探索するように構成されている。
【００４８】
例えば、ユーザが‘ソウル市役所’から出発して‘プサン市ササン区ササン区役所’までの経路を要請する場合、前記ソウル市役所および前記ササン区役所付近を除外した地域において、例えばソウル料金所(Toll Gate)からプサン料金所までの高速道路に該当する経路以外の、各地方都市周辺の地方道路などに対して経路を探索することは、不必要である可能性が高い。すなわち、本実施例による経路探索方法によると、第2地域では高速道路、国道などの“実質的にユーザが利用する可能性が高い”道路に対する経路のみを探索することによって、経路探索システム(210)が経路を探索するのに必要とされる時間を減少させ、経路を探索するために必要な作業量を減少させる。
【００４９】
従って、本実施例による経路探索方法は、前記第1レイヤ集合および前記第3レイヤ集合は多数のレイヤを含むように設定することによって、前記出発地および前記目的地周辺においては主要道路以外にも住宅街道路などを含む全体道路情報に基づいて得られた経路と同一または類似した経路をユーザに提供し、第2レイヤ集合は高速道路または主要国道などに対応する道路情報と連関したレイヤを含むように設定することによって、結果的に全体道路情報に基づいて全地域の経路を探索した場合と同一の実質的に等しい経路を提供すると同時に、経路探索システム(210)における計算量を減少させる。
【００５０】
また、前記第1距離(d1)と前記第2距離(d2)は同一な値であったり、相違した値であったりする。
【００５１】
本発明の他の実施例によると、前記第1および第2距離(d1、d2)は、移動通信端末機(230)から入力された値である。例えば、ユーザは、地理を熟知している出発地付近に対しては前記d1値を少なく入力し、地理を熟知していない目的地付近に対しては前記d2値を大きく入力することによって、目的地から相当離れている地域に対しても、詳細な経路の提供を受けることができる。
【００５２】
また、前記第1および第2距離は、経路探索システム(210)の管理者が設定した距離である場合がある。また、本発明の他の実施例によると、ユーザは、経路探索システム(210)が自動的に前記第1および第2距離を設定するようにすることと、自らが入力するものの中から一つを選択することができる。
【００５３】
また、本発明の他の実施例によると、前記第1レイヤ集合または前記第3レイヤ集合は、前記数値地図データベースに維持されているレイヤを全て含む。
【００５４】
図8は、前記第1ないし第3レイヤ集合と連関した道路情報に基づいて探索された経路を説明するための図である。図8の(a)は出発地である‘ソウル市役所’付近を示しており、同図の(b)は目的地である‘ササン区役所’付近を示している。図8の(a)および(b)は、前記第1および第3レイヤ集合がレイヤ集合全体を含む場合に対して示した。従って、経路探索システム(210)は、第1および第3地域においては全体道路情報(各ノード、リンクおよび補間点)を用いて経路を探索するようになる。
【００５５】
また、図8の(c)および(d)は、前記出発地から前記目的地の間にある第2地域を示している。第2地域に対する第2レイヤ集合は、前記第1および第3レイヤ集合に比べて含むレイヤ数が少ないため、経路探索システム(210)は、ユーザが実質的に用いると見なされる主要道路に対する道路情報のみを用いて経路を探索するようになる。
【００５６】
経路探索システム(210)は、段階(103)ないし段階（105)を遂行して得られた第1ないし第3経路を用い、段階(106)で、前記出発地(‘ソウル市役所’)から前記目的地('ササン区役所’)までの経路を生成する。
【００５７】
前記生成された経路は、段階(107)で、ユーザの移動通信端末機(207)に送信される。図6の(g)は、経路探索システム(210)が移動通信端末機(230)に前記経路を送信するまでかかる送信時間中に移動通信端末機(230)においてディスプレイされる画面を示したものである。本実施例による経路探索方法によると、前記送信時間が従来に比べて大幅に減少する。特に、ソウル地域からプサン地域までの経路を探索する場合のように、その経路を探索しなければならない地域が広くなる程、その減少幅はより大きくなることは自明である。
【００５８】
前記経路の送信が完了し、ユーザが図6の(h)で示したように、移動通信端末機(230)上に提供された入力ウィンドウを介して“道案内スタート”を命令すると、同図の(i)に示されるような前記経路が反映された地図データの提供を受けることができる。図6の(i)において、道路上の太い線は前記経路を意味する。
【００５９】
上述したような過程を経て、移動通信端末機(230)のユーザは、要請した経路の提供を受けることができる。
【００６０】
一方、図6の(h)で示したように、“模擬走行”、“走行経路プレビュー”、“目的地情報”および“経路再設定”のように、経路探索と連関した多様なサービスがユーザに提要される。このようなサービスは、経路探索システム(210)から所定のデータの送信を受けることによってなされたり、“走行経路プレビュー”などのように移動通信端末機(230)でなされたりする。
【００６１】
本発明の他の実施例による経路探索システム(210)によると、前記ユーザが前記送信を受けた経路に沿って移動せず、前記経路を離脱する場合に備えて段階(108)ないし段階（110)が遂行される。
【００６２】
経路探索システム (210)は、段階(108)で、移動通信端末機(230)の現在位置を移動通信端末機(230)から受信する。前記現在位置は、移動通信端末機(230)と連関したGPS受信機より得られる。前記GPS受信機は、移動通信端末機(230)に内蔵されていたり、別途設置されて所定の情報を移動通信端末機(230)に送信するように構成されていたりする。
【００６３】
経路探索システム(210)は、前記GPS受信機から移動通信端末機(230)の現在位置を随時に受信し、段階(109)で、移動通信端末機(230)が前記経路を離脱したかを前記現在位置に基づいて判断する。本発明の他の実施例によると、経路探索システム(210)は、移動通信端末機(230)が前記経路から直線距離で所定距離を脱する場合に‘経路の離脱’と判断する。これ以外にも、前記現在位置を用いた多様な判断方法が用いられる。
【００６４】
移動通信端末機(230)が前記経路から離脱した場合、経路探索システム(210)は、段階(110)で、前記受信した現在位置を出発地として設定し、前記設定された出発地を移動通信端末機(230)に送信し、経路探索システム(210)は、段階(104)ないし段階（107)を反復して前記ユーザに新しい経路を提供する。従って、ユーザは経路を離脱した場合でも、新しい位置に基づいて新しい経路の提供を受けることができる。
【００６５】
以下、本発明の他の実施例による経路探索方法に対して説明する。図9は、、本発明の他の実施例による経路探索方法を示した流れ図であり、上述した実施例と同様に所定の経路探索システムで遂行される。図10を用いて、本実施例による経路探索方法を説明することにする。
【００６６】
前記経路探索システムは、段階(901)で、所定の数値地図データベースに道路に対応する道路情報を維持し、段階(902)で、前記道路情報に基づいて出発地から目的地までの第1候補経路を一つ以上計算する。本発明の更に他の実施例によると、前記出発地および目的地は、移動通信端末機を用いてユーザから入力されたデータである。
【００６７】
前記出発地から前記目的地までの経路は一つのみである場合もあるが、最短距離に該当する経路を含み、複数の経路が存在するのが一般的であるため、段階(902)においては、複数の第1候補経路が計算されるようになる。
【００６８】
前記経路探索システムは段階(903)で、前記第1候補経路の中で、前記目的地から一定距離(図10においてd3)に位置する臨界地点に到逹した所定個数の第1候補経路を第2候補経路として決定する。
【００６９】
前記臨界地点は、図10において点線で表示した円上に位置する地点である。本発明の他の実施例によると、前記経路探索システムは、誤差の範囲内で前記臨界地点に到逹したかを判断することによって、地図情報上の誤差などによって実際の距離の誤差問題を解決することができる。すなわち、前記一定距離が2kmである場合、誤差範囲を20mと設定すると、前記経路探索システムは前記目的地から1.98km離れた地点から2.02km離れた地点までを、前記臨界地点と判断するようになる。
【００７０】
前記経路探索システムは、段階(904)で、前記第1候補経路として決定されなかった前記第1候補経路の計算を中止し、段階(905)で、前記臨界地点から前記目的地まで前記第2候補経路を計算する。
【００７１】
段階(903)で、前記第2候補経路として決定される第1候補経路は一つ以上である場合がある。すなわち、前記経路探索システムは、最も先に前記臨界地点に到逹した第1候補経路があれば、それ以外の第1候補経路に対する計算を中止することもできるし、前記所定個数が2つで設定された場合には、最も先に前記臨界地点に到逹した第1候補経路とその次に前記臨界地点に到逹した第1候補経路を除いた第1候補経路に対する計算を中止することもできる。
【００７２】
一方、前記第2候補経路として選択された第1候補経路に対しては、経路を計算する時に中止されず、出発地から目的地までの経路が計算される。第2候補経路に対して目的地までの経路計算が完了すると、前記経路探索システムは、段階(906)で、前記第2候補経路を‘経路’として決定する。前記決定された経路はユーザに提供される。
【００７３】
図10で示すように、出発地から目的地までの第1候補経路は複数存在する可能性が高く、その中で大多数の経路は、所定の基準によって前記経路探索システムによって選択されない経路である。前記所定の基準は、経路の全長、経路に該当する道路の車線数などの多様な事項を考慮することができる。例えば、前記経路探索システムは、単純に全長が最小である経路を選択したり、経路に該当する車線数が2車線以上の経路の中から全長が最小である経路を選択したりするよう複合的に判断するなど、多様な方式でユーザに提供する経路を選択することができる。
【００７４】
ところで、図10で示したように、一般的に前記目的地付近までの経路計算が完了した第2候補経路が経路として決定されるのが大部分であり、それ以外の第1候補経路に対する計算を継続することは、前記経路探索システムの負荷を増加させ、経路探索が完了するまでの時間を遅延させる原因となるだけである。
【００７５】
すなわち、従来技術のように候補経路に対する計算を全て完了し、その中から経路を選択するのではなく、経路として選択される可能性が高い候補経路を除外した候補経路の計算は、その計算が完了する前に中止させることによって、本実施例による経路探索方法は、経路探索にかかる時間を減少させ、経路探索システムにおける負荷を減少させる。
【００７６】
また、本発明は、上述した各実施例による経路探索方法を実行させるためのプログラムを記録した、コンピュータによる読み取り可能な記録媒体を提供する。前記コンピュータによる読み取りが可能な媒体は、プログラム命令、データファイル、データ構造などを単独でまたは組み合わせて含む。前記プログラム命令は、本発明のために特別に設計されて構成されたものであったり、コンピュータソフトウェア当業者に公知されて使用可能なものであったりする。コンピュータによる読み取りが可能な記録媒体の例としては、ハードディスク、フロッピィーディスクおよび磁気のテープのような磁気媒体(magnetic media)、CD-ROM、DVDのような光媒体(optical media)、フロプティカルディスク(floptical disk)のような磁気-光媒体(magneto-optical media)、およびロム(ROM)、ラム(RAM)、フラッシュメモリなどのようなプログラム命令を格納して遂行するように特別に構成されたハードウェア装置が含まれる。前記媒体は、プログラム命令、データ構造などを指定する信号を送信する搬送波を含む光または金属線、導波管などの送信媒体であったりする。プログラム命令の例としては、コンパイラによって生成されるような機械語コードだけでなく、インタプリタなどを用いてコンピュータによって実行される高級言語コードを含む。
【００７７】
以下、本発明の一実施例による経路探索システムに対して説明する。図11は、本実施例による経路探索システムを示したブロック図である。
【００７８】
数値地図データベース(1101)は、道路に対応する道路情報および前記道路情報と連関して所定の基準によって決定されたレイヤ(layer)を維持する。
【００７９】
ユーザ受信部(1102)は、通信網(1120)を介してユーザの移動通信端末機(1110)から出発地および目的地の入力を受け、経路探索部(1103)は、前記道路情報に基づいて前記目的地までの経路を探索する。ユーザ送信部(1104)は前記探索された経路を通信網(1120)を介して移動通信端末機(1110)に送信することによって、前記探索された経路を前記ユーザに提供する。
【００８０】
この時、経路探索部(1103)は、少なくとも一つ以上のレイヤを含む所定の第1レイヤ集合と連関した前記道路情報に基づいて前記出発地から所定の第1距離以内における第1経路を探索し、少なくとも一つ以上の前記レイヤを含む所定の第2レイヤ集合と連関した前記道路情報に基づいて前記出発地より前記所定の第1距離だけ離れている地点から、前記目的地より所定の第2距離だけ離れている地点までの第2経路を探索し、少なくとも一つ以上の前記レイヤを含む所定の第3レイヤ集合と連関した前記道路情報に基づいて目的地から前記第2距離以内における第3経路を探索し、前記第1経路、前記第2経路および前記第3経路を用いて前記出発地から前記目的地までの経路を生成する。
【００８１】
前記第1および第3レイヤ集合、前記第1および第2距離、および経路探索部(1103)における経路探索および経路生成過程に対しては、上述した実施例においてすでに説明したため、これに対する詳しい説明は省略することにする。
【００８２】
一方、図12は、本発明による経路探索システムなどを構成するのに採用される汎用コンピュータシステムの内部ブロック図である。
【００８３】
コンピュータシステム(1200)は、ラム(RAM:Random Access Memory)(1002)とロム(ROM:Read Only Memory)(1203)を含む主記憶装置と連結する一つ以上のプロセッサ(1201)を含む。プロセッサ(1201)は、中央処理装置(CPU)と呼ばれることもある。本技術分野で広く知られているように、ロム(1203)はデータ(data)と命令(instruction)を単方向性でCPUに伝達する役割をなし、ラム(1202)は通常、データと命令を両方向性で伝達するのに用いられる。ラム(1202)およびロム(1203)は、コンピュータ読み取り可能媒体のいかなる適切な形態も含むことができる。大容量記憶装置(Mass Storage)(1204)は、双方向的にプロセッサ(1201)と連結して追加的なデータ格納能力を提供し、前記したコンピュータ読み取り可能記録媒体の中のいかなるものにも該当する。大容量記憶装置(1204)は、プログラム、データなどを格納するのに用いられ、通常、主記憶装置より速度が遅いハードディスクのような補助記憶装置である。CDロム(1206)のような特定大容量記憶装置が用いられることもある。プロセッサ(1201)は、ビデオモニタ、トラックボール、マウス、キーボード、マイクロフォン、タッチスクリーン型ディスプレイ、カード読取り機、磁気または紙テープ読み取り機、音声または手書き文字認識機、ジョイスティック、またはその他公知のコンピュータ入出力装置のような１つ以上の入出力インターフェイス（１２０５）と連結する。最後に、プロセッサ（１２０１）は、ネットワークインターフェイス（１２０７）を介して有線または無線通信ネットワークに連結する。このようなネットワーク連結によって、上に述べられた方法の手順に沿って、CPUがネットワークから情報を受信、またはネットワークに情報を送信する。上に述べられた装置または道具は、コンピュータハードウェアおよびソフトウェア技術分野の当業者に広く知られている。
【００８４】
上に述べられたハードウェア装置は、本発明の動作を遂行するために一つ以上のソフトウェアモジュールとして作動するように構成される。
【００８５】
以上のように、本発明は限定された実施例と図面によって説明されたが、本発明は前記の実施例に限定されるものでなく、これは本発明が属する分野において通常の知識を有する者にとっては、このような記載から多様な修正および変形が可能である。よって、本発明思想は、添付の特許請求の範囲によってのみ把握されるべきであり、この均等または等価的変形すべては本発明思想の範囲に属するものであろう。
【図面の簡単な説明】
【００８６】
【図１】本発明の一実施例による経路探索方法を示した流れ図である。
【図２】本発明の一実施例による経路探索方法を遂行する経路探索システムのネットワーク連結を示した図である。
【図３】本発明の一実施例による経路探索方法において、道路情報の一例を説明するための図である。
【図４】本発明の一実施例による経路探索方法において、数値地図データベースに維持される道路情報および前記道路情報と連関したレイヤの一例を示した図である。
【図５】本発明の一実施例による経路探索方法において、経路探索情報の完結性を保障するように所定の道路に対するレイヤを決定する場合を説明するための図である。
【図６ａ】(a)ないし(f)は、本発明の一実施例による経路探索方法において、出発地および目的地を入力するためにユーザの移動通信端末機で提供される入力ウィンドウの一例を示した図である。
【図６ｂ】(g)ないし(i)は、前記移動通信端末機で表示される経路を説明するための図である。
【図７】本発明の一実施例による経路探索方法を説明するための図である。
【図８】本発明の一実施例による経路探索方法において、第1ないし第3レイヤ集合と連関した道路情報に基づいて探索された経路を説明するための図である。
【図９】本発明の他の実施例による経路探索方法を示した流れ図である。
【図１０】本発明の他の実施例による経路探索方法を説明するための図である。
【図１１】本発明の他の実施例による経路探索システムを示したブロック図である。
【図１２】本発明による経路探索システムなどを構成するのに採用される汎用コンピュータシステムの内部ブロック図である。
【図１】
2006527837.tif 000003
【図２】
2006527837.tif 000004
【図３】
2006527837.tif 000005
【図４】
2006527837.tif 000006
【図５】
2006527837.tif 000007
【図６ａ】
2006527837.tif 000008
【図６ｂ】
2006527837.tif 000009
【図７】
2006527837.tif 000010
2006527837.tif 000011
2006527837.tif 000012
【図９】
2006527837.tif 000013
【図１０】
2006527837.tif 000014
【図１１】
2006527837.tif 000015
【図１２】
2006527837.tif 000016
【国際調査報告】
2006527837.tif 000017