経路探索装置
【課題】検索した経路中に現在位置を検出できない位置検出不能範囲が有る場合であっても、ユーザを目的地まで円滑に導くことのできる経路を提供する経路探索装置を提供する。
【解決手段】現在位置を検出する現在位置検出手段１７と、地図情報を記憶する地図記憶手段１９と、目的地を設定する目的地設定手段２５と、地図情報および目的地に従い、目的地までの経路を探索する経路探索手段１８とを備えた経路探索装置において、地図情報に基づき、探索した前記経路中に現在位置を検出できない位置検出不能範囲が有るか否かを判定する判定手段を備え、経路探索手段１８は、経路中に位置検出不能範囲が有るとき、位置検出不能範囲で進行方向が変化する回数が最も少ない経路を最適経路として探索する。
【解決手段】現在位置を検出する現在位置検出手段１７と、地図情報を記憶する地図記憶手段１９と、目的地を設定する目的地設定手段２５と、地図情報および目的地に従い、目的地までの経路を探索する経路探索手段１８とを備えた経路探索装置において、地図情報に基づき、探索した前記経路中に現在位置を検出できない位置検出不能範囲が有るか否かを判定する判定手段を備え、経路探索手段１８は、経路中に位置検出不能範囲が有るとき、位置検出不能範囲で進行方向が変化する回数が最も少ない経路を最適経路として探索する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、経路探索装置に関し、特に、位置検出不能な範囲を通過する経路を探索する経路探索装置に関する。
【背景技術】
【０００２】
従来から、ＧＰＳ（Global Positioning System）等により車両の現在位置を検出し、その現在位置をディスプレイに道路地図とともに表示し、また、目的地までの経路を探索してディスプレイに表示することにより、ユーザを目的地まで円滑に導くようにしたナビゲーション装置が知られている。なお、ナビゲーション装置は、車両に搭載される装置に限られるものではなく、例えば、ユーザが所持する携帯電話やＰＤＡ等の携帯端末に搭載し、ユーザが徒歩や電車、バス等の交通機関により目的地に向う際の支援装置として利用できるものもある。
【０００３】
このようなナビゲーション装置において、目的地までユーザを円滑に導くためには、ユーザの要望に適した経路を案内できることが重要である。
【０００４】
そこで、例えば、下記の特許文献１（特開平６−２４９６７２号公報）には、出発地から目的地までの間に複数の推奨経路を探索して表示するとともに、各推奨経路の右左折の回数を演算して表示し、ユーザが右折または左折の回数の少ない推奨経路を選択可能としたナビゲーション装置が開示されている。
【０００５】
また、下記の特許文献２（特開２００４−２０５４０９号公報）には、交差点等の分岐点の手前に合流地点がある道路の場合、ドライバの負担となるような右左折を極力回避可能な経路探索を行うようにしたナビゲーション装置が開示されている。
【０００６】
また、下記の特許文献３（特開平９−３２５０３８号公報）には、右折回数が可能な限り少ない経路を探索することにより、より早く目的地に到達可能とした経路探索装置が開示されている。
【０００７】
さらに、下記の特許文献４（特開２００６−２２６７８６号公報）には、左折優先経路を算出することにより、不案内なエリアでも、右折に伴う負担やリスクを軽減することができるナビゲーション装置が開示されている。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】特開平６−２４９６７２号公報（段落［００２５］〜［００２８］）
【特許文献２】特開２００４−２０５４０９号公報（段落［０００７］、［０００８］）
【特許文献３】特開平９−３２５０３８号公報（段落［００１７］）
【特許文献４】特開２００６−２２６７８６号公報（段落［００１８］、［００１９］）
【発明の概要】
【発明が解決しようとする課題】
【０００９】
しかしながら、上記特許文献１に開示されたナビゲーション装置では、推奨経路の全行程で右左折の回数が少ない経路を探索して選択することが可能であるが、特定の範囲での右左折回数を必ずしも少なく設定できるものではない。
【００１０】
ここで、特定の範囲が、例えば、屋内駐車場や地下駐車場のように、ＧＰＳ衛星からの電波を受信できない建造物の内部である場合、ナビゲーション装置の正確な現在位置を検出することができないため、右左折ポイント（案内地点）で音声などによる案内をすることができない。
【００１１】
そのため、建造物の内部に多数の右左折があるような複雑な経路が設定されていると、ユーザにとっては、その経路に沿って円滑に移動することが困難になる場合がある。
【００１２】
車両用のナビゲーション装置では、屋内駐車場や地下駐車場内の経路を探索できるように地図情報に当該施設内（屋内駐車場や地下駐車場）の通路情報を備えているものもあり、また歩行者用のナビゲーション装置では、駅構内や地下街等の建造物内においても経路探索が行えるように、地図情報として当該施設内（駅構内や地下街）の通路情報を記憶しているものがある。しかしながら、これらの施設内、建造物内ではＧＰＳ衛星からの電波を受信することができない場合がある。
【００１３】
従って、それらの施設内の通路に位置情報を提供する位置送信ユニットなどの専用のインフラが整備されていない限り、車両や歩行者の位置を検出することができない。このためそれらの施設内の経路を探索することはできても、右左折などのポイント（案内地点）で音声案内ができないという問題がある。
【００１４】
そのため、施設や建造物内を通過する場合においては、施設や建造物外で右左折の回数が増えたとしても、施設や建造物内での右左折回数を減らすことが望まれる。
【００１５】
なお、上記特許文献２〜４に開示されたナビゲーション装置または経路探索装置の場合、単に右左折が少ない経路を探索することにより、移動時間の短縮やドライバに対する負担を軽減することを目的としているだけであり、現在位置を検出できない範囲において、ユーザを目的地まで円滑に導くことを目的としたものではない。
【００１６】
本発明は、上記の問題点を解消することを課題とするものであり、検索した経路中に現在位置を検出できない位置検出不能範囲が有る場合であっても、ユーザを目的地まで円滑に導くことのできる経路探索装置を提供することを目的とするものである。
【課題を解決するための手段】
【００１７】
前記課題を解決するために、本願の請求項１にかかる発明は、
地図情報を参照して出発地から目的地までの経路を探索する経路探索手段を備えた経路探索装置であって、
前記経路探索装置は、前記経路探索手段により探索された経路中に現在位置を検出できない位置検出不能範囲が有るか否かを判定する判定手段を備え、
前記経路探索手段は、前記判定手段により前記位置検出不能範囲が有ると判定された場合、前記位置検出不能範囲内で進行方向が変化する回数が最も少ない経路を探索することを特徴とする。
【００１８】
本願の請求項２にかかる発明は、請求項１に記載の経路探索装置において、前記経路探索手段は、前記位置検出不能範囲内で進行方向が変化する回数が最も少ない経路、前記出発地及び前記目的地に基づき、前記出発地から前記目的地までの経路を探索することを特徴とする。
【００１９】
本願の請求項３にかかる発明は、請求項１又は２に記載の経路探索装置において、前記経路探索手段は、前記判定手段により前記位置検出不能範囲が有ると判定された場合、前記位置検出不能範囲の入口及び出口を特定し、前記入口から前記出口までの経路を探索することで、前記位置検出不能範囲内で進行方向が変化する回数が最も少ない経路を探索することを特徴とする。
【００２０】
本願の請求項４にかかる発明は、請求項３に記載の経路探索装置において、前記経路探索手段は、前記入口から前記出口までの経路を複数の探索条件で探索することを特徴とする。
【００２１】
本願の請求項５にかかる発明は、請求項３又は４に記載の経路探索装置において、前記経路探索手段は、前記出発地から前記位置検出不能範囲の出入口までの経路を探索し、前記位置検出不能範囲を通過しない前記経路の前記出入口を入口とし、前記位置検出不能範囲を通過する前記経路の前記出入口を出口とすることを特徴とする。
【００２２】
本願の請求項６にかかる発明は、請求項１〜５の何れかに記載の経路探索装置において、前記位置検出不能範囲は、建造物の内部であることを特徴とすることを特徴とする。
【００２３】
本願の請求項７にかかる発明は、請求項１〜６の何れかに記載の経路探索装置において、前記進行方向が変化する回数は、上下方向への進行方向の変化及び／又は右左折の回数であることを特徴とする。
【００２４】
本願の請求項８にかかる発明は、請求項１〜７の何れかに記載の経路探索装置において、前記経路探索手段は、前記進行方向が変化する回数が最も少ない経路が複数あるとき、移動距離が最も短い経路を前記進行方向が変化する回数が最も少ない経路として探索することを特徴とする。
【発明の効果】
【００２５】
請求項１にかかる発明においては、地図情報を参照して出発地から目的地までの経路を探索する経路探索手段を備えた経路探索装置であって、前記経路探索装置は、前記経路探索手段により探索された経路中に現在位置を検出できない位置検出不能範囲が有るか否かを判定する判定手段を備え、前記経路探索手段は、前記判定手段により前記位置検出不能範囲が有ると判定された場合、前記位置検出不能範囲内で進行方向が変化する回数が最も少ない経路を探索する。
【００２６】
かかる構成によれば、目的地までの経路中に位置検出不能範囲が有る場合であっても、前記位置検出不能範囲における経路を再探索し、進行方向が変化する回数が最も少ない経路を特定するから、現在位置が特定できず、分岐点（進行方向が変化する地点）における右左折等の音声案内ができなくても、ユーザを比較的円滑に目的地まで導く経路を提示することができるようになる。
【００２７】
請求項２にかかる発明においては、請求項１にかかる発明において、経路探索手段は、前記位置検出不能範囲内で進行方向が変化する回数が最も少ない経路、前記出発地及び前記目的地に基づき、前記出発地から前記目的地までの経路を探索する。かかる構成によれば、かかる構成によれば、経路探索手段は効率よく位置検出不能範囲内で進行方向が変化する回数が最も少ない経路を有する出発地から目的地までの最適経路を再探索することができるようになる。
【００２８】
また、請求項３にかかる発明においては、請求項１又は２にかかる発明において、経路探索手段は、前記判定手段により前記位置検出不能範囲が有ると判定された場合、前記位置検出不能範囲の入口及び出口を特定し、前記入口から前記出口までの経路を探索することで、前記位置検出不能範囲内で進行方向が変化する回数が最も少ない経路を探索する。かかる構成によれば、経路探索手段は効率よく位置検出不能範囲内で進行方向が変化する回数が最も少ない経路を再探索することができるようになる。
【００２９】
請求項４にかかる発明においては、請求項３にかかる発明において、経路探索手段は、前記入口から前記出口までの経路を複数の探索条件で探索する。かかる構成によれば、距離優先、時間優先、道幅優先、自転車兼用道路回避などの種々の探索条件で経路を探索し、複数の案内経路のうち、最も右左折の回数が少ない経路を抽出してユーザに提供することができるようになる。
【００３０】
また、請求項５にかかる発明においては、請求項３又は４に記載の発明において、経路探索手段は、前記出発地から前記位置検出不能範囲の出入口までの経路を探索し、前記位置検出不能範囲を通過しない前記経路の前記出入口を入口とし、前記位置検出不能範囲を通過する前記経路の前記出入口を出口とする。かかる構成によれば、出発地の場所に寄らず入口と出口を特定することが可能となる。
【００３１】
請求項６にかかる発明においては、請求項１〜５の何れかに記載の発明において、位置検出不能範囲は、建造物の内部であるから、建物内の駐車や地下街において、進行方向が変化する回数が最も少ない経路を特定するから、現在位置が特定できず、分岐点（進行方向が変化する地点）における右左折等の音声案内ができなくても、ユーザを比較的円滑に目的地まで導く経路を提示することができるようになる。
【００３２】
請求項７にかかる発明においては、請求項１〜６の何れかに記載の発明において、進行方向が変化する回数は、上下方向への進行方向の変化及び／又は右左折の回数であるから、建物内の駐車や地下街において、水平方向のみなら垂直方向であるフロアを上下することが少ない経路をユーザに提示できるようになる。
【００３３】
請求項８にかかる発明においては、請求項１〜７の何れかに記載の発明において、経路探索手段は、前記進行方向が変化する回数が最も少ない経路が複数あるとき、移動距離が最も短い経路を前記進行方向が変化する回数が最も少ない経路として探索するから、ユーザに最も右左折の回数が少ない経路であって、かつ移動距離が最短の最適経路を提示することができるようになる。
【図面の簡単な説明】
【００３４】
【図１】本発明の実施例にかかるナビゲーション装置の要部構成を示すブロック図である。
【図２】本発明の実施例にかかるナビゲーション装置における処理フローチャートである。
【図３】本発明の実施例にかかるナビゲーション装置により検索された目的地までの経路の説明図である。
【図４】本発明の実施例にかかるナビゲーション装置により検索された建造物の出入口までの経路の説明図である。
【図５】本発明の実施例にかかるナビゲーション装置により検索された建造物内の経路の説明図である。
【図６】本発明の実施例にかかるナビゲーション装置により検索された目的地までの適切な経路の説明図である。
【図７】本発明の実施例にかかるナビゲーション装置による建造物およびその出入口を検索する説明図である。
【図８】本発明の実施例にかかるナビゲーション装置により検索された建造物内の経路の説明図である。
【発明を実施するための形態】
【００３５】
以下、本発明の具体例を実施例及び図面を用いて詳細に説明する。但し、以下に示す実施形態は、本発明の技術的思想を具体化するための経路探索装置としてナビゲーション装置を例示するものであって、本発明をこのナビゲーション装置に特定することを意図するものではなく、特許請求の範囲に含まれるその他の実施形態の経路探索装置にも等しく適応し得るものである。
【実施例】
【００３６】
図１は、本発明の実施例にかかるナビゲーション装置１０の要部構成を示すブロック図である。
【００３７】
ナビゲーション装置１０は、例えば、ユーザが所持する携帯電話やＰＤＡ等の携帯端末に搭載され、徒歩や電車、バス等の交通機関を利用して移動する際における経路案内を行うものである。なお、ナビゲーション装置１０は、ユーザに目的地までの経路案内を行うとともに、目的地又は案内経路に関連した施設や観光スポット等の関連情報をユーザに提供するものであってもよい。
【００３８】
ナビゲーション装置１０は、制御手段１３を備える。制御手段１３は、ＣＰＵ１４、ＲＯＭ１５、ＲＡＭ１６からなるプロセッサで構成され、ＲＯＭ１５、ＲＡＭ１６に記録された制御プログラムに従ってナビゲーション装置１０の各部の動作を制御するものである。
【００３９】
また、ナビゲーション装置１０は、現在位置検出手段１７、経路探索手段１８、地図記憶手段１９、判定手段２０、入力手段２５、出力手段２６などを備えて構成されている。
【００４０】
現在位置検出手段１７は、地球上空を周回している複数のＧＰＳ衛星から時刻情報及び位置情報を含む電波を受信するＧＰＳ受信機等で構成される。３個以上のＧＰＳ衛星からの電波を受信して処理することにより、ユーザが所持するナビゲーション装置１０の現在位置を算出することができる。また、現在位置検出手段１７は、車両又はナビゲーション装置１０に搭載された加速度センサ、距離センサ、方位センサ、舵角センサ等からなる自立航法装置を備えることもできる。
【００４１】
なお、現在位置検出手段１７が自律航法装置を備えた場合であっても、ユーザが徒歩で使用する場合には、ユーザがナビゲーション装置１０を固定して使用しなければ自律航法装置で正確な現在位置を算出することができない。また、ユーザがナビゲーション装置１０を固定して使用した場合であっても、自律航法装置で算出する現在位置は、ＧＰＳ衛星からの電波に基づき算出する絶対的な現在位置とは異なり、前回の現在位置からの相対的な現在位置であるため、自律航法装置のみで現在位置を検出した場合では、現在位置の誤差が増大してしまう恐れがある。
【００４２】
経路探索手段１８は、ユーザが入力手段２５を用いて目的地を入力することにより、地図記憶手段１９に記憶されている地図情報を参照し、現在位置又はユーザによって指定された出発地から目的地に至る最適な案内経路を探索するものである。
【００４３】
なお、案内経路の探索は、現在位置又は出発地に対応するノードから目的地に対応するノードに至るリンクと、ノードとをダイクストラ法等の各種の手法によって探索し、リンク長（リンクコスト）や所要時間等を累積し、総リンク長（移動距離）又は総所要時間等が最短となる経路を案内経路とし、当該経路に属するノードやリンクを案内経路データとして提供するものである。
【００４４】
地図記憶手段１９は、地図情報、施設情報、交通機関の時刻情報及び乗り換え情報等の各種情報を記憶する。
【００４５】
地図情報には、道路や通路の分岐点をノードとするノードデータ、それぞれのノード間を結ぶ経路をリンクとしたリンクデータ、地形図データが含まれる。
【００４６】
ノードデータには、ノード番号、位置座標、接続リンク本数、分岐点名称の他、分岐点から所定距離だけ離れた案内地点において、右左折、直進等の経路案内を行う経路案内データ及び案内地点の位置座標が記憶されている。また、ノードは、駅構内、地下街等の建造物の出入口に対しても設定される。出入口のノードには、建造物の出入口であることを示す識別情報（フラグ）が設定される。また、建造物の出入口に対して設定されるノードには、当該建造物の名称等の当該建造物に関連する情報が含まれる。
【００４７】
リンクデータには、始点及び終点となるノード番号、道路種別（歩行者優先通路、自転車兼用道路等）、ノード間の距離情報であるリンク長（リンクコスト）、所要時間等が含まれる。また、建造物内部のリンクデータには、建造物内部の通路であることを示す識別情報（フラグ）が設定される。さらに、リンクデータには、リンク属性として橋、トンネル、踏切、料金所等のデータが付与される。
【００４８】
地形図データには、海岸線、湖沼、河川形状などの水系データ、行政境界データからなる背景データが含まれる。
【００４９】
また、地図記憶手段１９には、駐車場やガソリンスタンドなどの施設毎の施設情報も記憶されている。施設情報には、○○支店などの施設の名称、施設形状、位置座標、営業時間、ガソリンスタンドや地下駐車場、地下街、駅などの施設の種別、ランドマークなどの施設の画像などが含まれている。また、施設情報には、施設毎に出入口の情報も含まれ、この出入口の情報は、地図情報に含まれるノードデータに関連している。
【００５０】
判定手段２０は、経路探索手段１８が探索した案内経路に、位置検出不能範囲が含まれるか否かを判定する。具体的には、地図情報を参照して、地下駐車場や屋内駐車場あるいは地下街や建物内等の建造物内を通過するかを判定する。
【００５１】
入力手段２５は、ナビゲーション装置１０における操作入力や、出発地、目的地などの経路検索条件、あるいは、出発地又は目的地とする施設、駐車場などの所望の施設を検索するための検索条件等を設定するための各種キー、タッチパネル、リモートコントローラ等から構成される。
【００５２】
出力手段２６は、地図情報および施設情報に基づいた地図画像、案内経路画像、施設の写真や施設の詳細な説明のテキスト等をユーザに表示する液晶ディスプレイ、及び、案内経路における案内地点での経路案内や警告を含む音声情報を出力するスピーカ等で構成される。
【００５３】
本実施例にかかるナビゲーション装置１０においては、判定手段２０が、経路探索手段１８が探索した案内経路に、地下駐車場や屋内駐車場あるいは地下街や建物内等の建造物内を通過すると判定すると、経路探索手段１８は、当該建造物内の出口ノード、入口ノード（出入口ノード）を抽出し、出発地から出入口ノードまでのそれぞれの案内経路を探索し、そのうち建造物内を通過せずに出入口ノードに到達した経路の出入口ノードを「入口」とし、建造物内を通過して出入口ノードに到達した経路の出入口ノードを「出口」とする。そして経路探索手段１８は、各入口から各出口までの建造物内の案内経路を各々再探索し、最も進行方向が変化する回数の少ない案内経路を建造物内の案内経路とする。
【００５４】
なお、進行方向が変化する回数が少ない案内経路とは、案内経路上において、上下方向への進行方向の変化や右左折の回数が少ない案内経路である。なお、以下の説明では、単に右左折回数が少ない案内経路として説明を行う。
【００５５】
そして、当該建造物内の案内経路、出発地から当該建造物内の案内経路の「入口」（出発地）までの案内経路、および、当該建造物内の案内経路の「出口」（目的地）から目的地までの案内経路を接続してユーザに提示する。このことにより、ユーザには建造物内で右左折回数が最も少ない案内経路が提示されるから、ユーザは経路案内ができない建造物内であっても比較的容易に経路に沿って進行することができるようになる。
【００５６】
なお、本発明において、進行方向の変化とは、建造物内における水平方向の右左折の他、建造物内の垂直方向への変化、例えば、階段、エスカレータにより上下方向（垂直方向）に進行方向が変化する場合も含むものとしてもよい。
【００５７】
次に、図２に示す処理フローチャートに基づき、本実施例のナビゲーション装置１０の動作を説明する。
【００５８】
現在位置検出手段１７は、ＧＰＳ衛星から位置情報を含む電波を受信することにより、ナビゲーション装置１０の現在位置を検出する（ステップＳ１０１）。制御手段１３は、検出した現在位置に基づき、地図記憶手段１９から対応する地図情報を抽出し、現在位置を示すマークとともに出力手段２６に地図画像を表示する。ユーザは、表示された地図画像に従い、現在位置を確認することができる。
【００５９】
ユーザは、ナビゲーション装置１０の入力手段２５を用いて目的地を設定するとともに（ステップＳ１０２）、必要に応じて出発地を設定する。目的地等が設定されると、経路探索手段１８は、現在位置検出手段１７により検出した現在位置、または、ユーザが設定した出発地から、目的地までの案内経路を探索する（ステップＳ１０３）。案内経路は、地図記憶手段１９に記憶されているノードデータおよびリンクデータに基づき、例えば、目的地までの所要時間が最も短い経路、または、目的地までの距離が最も短い経路として探索することができる。図３は、現在位置（出発地）Ｓから目的地Ｇに至る案内経路２７を模式的に示したものである。
【００６０】
次に、判定手段２０は、ステップＳ１０３で経路探索手段１８が探索した案内経路２７の一部に位置検出不能範囲２８が有るか否かを判定する（ステップＳ１０４）。この場合、位置検出不能範囲２８とは、現在位置検出手段１７がＧＰＳ衛星から電波を受信できないため、現在位置を検出することができない範囲であり、例えば、駅構内、デパート内、地下街、トンネル内等の建造物内の範囲である。
【００６１】
位置検出不能範囲２８の有無は、案内経路データを構成するノードデータに建造物の出入口であることを示す識別情報（フラグ）が設定されているか否か、または、案内経路データを構成するリンクデータに建造物内の通路であることを示す識別情報（フラグ）が設定されているか否かにより判定することができる。図３は、一部に位置検出不能範囲２８が有る案内経路２７を示す。なお、経路探索手段１８が探索した案内経路データ（ノードデータ、リンクデータ）に前述のようなフラグを付加しない場合であっても、地図情報に属性情報として構造物内の通路リンクであることを示す情報が付加されていれば、判定手段２０は、この地図情報（属性情報）を参照してこれを判定することもできる。
【００６２】
案内経路２７の一部に位置検出不能範囲２８が無い場合（ステップＳ１０４、ＮＯ）、案内経路２７を最適な経路として確定する。確定した案内経路２７は、出力手段２６に現在位置を示すマークとともに表示される。ユーザは、表示された案内経路２７に従い、所望の目的地に移動することができる。
【００６３】
一方、案内経路２７の一部に位置検出不能範囲２８が有る場合（ステップＳ１０４、ＹＥＳ）、図４に示すように、経路探索手段１８は、現在位置（出発地）Ｓから位置検出不能範囲２８の各出入口２９ａ〜２９ｇまでの案内経路３０ａ〜３０ｇを探索する（ステップＳ１０５）。なお、位置検出不能範囲２８の出入口２９ａ〜２９ｇは、位置検出不能範囲２８（例えば、位置検出不能範囲２８が、駅であれば当該駅の出入口の情報）のノードデータに設定されている識別情報（フラグ）に基づいて抽出することができる。
【００６４】
次いで、探索された案内経路３０ａ〜３０ｇに基づき、位置検出不能範囲２８を通過して出入口に到達した案内経路３０ｅ〜３０ｇの出入口２９ｅ〜２９ｇを出口に決定し、位置検出不能範囲２８を通過せずに出入口に到達した案内経路３０ａ〜３０ｄの出入口２９ａ〜２９ｄを入口に決定する（ステップＳ１０６）。
【００６５】
位置検出不能範囲２８の出入口２９ａ〜２９ｇの入口および出口が決定された後、経路探索手段１８は、位置検出不能範囲２８における各入口から各出口までの案内経路を探索する（ステップＳ１０７）。案内経路は、地図記憶手段１９に記憶されているノードデータおよびリンクデータに基づき、例えば、入口、出口間での所要時間が最も短い経路、または、入口、出口間の距離が最も短い経路として探索することができる。なお、図５に示す例では、入口である出入口２９ａ〜２９ｄから出口である出入口２９ｅ〜２９ｇまでの経路として、１２通りの案内経路が探索される。
【００６６】
次に、探索された位置検出不能範囲２８における複数の経路から、右左折回数が最も少ない案内経路を抽出する（ステップＳ１０８）。右左折回数が最も少ない案内経路を抽出することにより、ユーザは、現在位置を検出することができない位置検出不能範囲２８において、経路を誤ることなく、案内された出口まで円滑に移動することが可能となる。なお、右左折回数が少ない案内経路を抽出する方法は、上記の先行文献に記載されている通り種々の方法を用いることができる。例えば、リンクデータにリンクの進行方向が含まれる場合、案内経路データに含まれるリンクの進行方向と、案内経路データに含まれ、当該リンクに隣接するリンクの進行方向とを比較することで、進行方向が変化する角度を算出し、当該角度が所定値以上であれば、右左折を行なう回数としてカウントする。
【００６７】
そして、カウントした右左折を行う回数が最も少ない案内経路を、右左折回数が最も少ない案内経路として抽出する。抽出された案内経路は、後述するようにして出発地から入口までの経路、出口から目的地までの経路と接続されてユーザに提示される。
【００６８】
図６は、ステップＳ１０８の処理で抽出された２本の案内経路３１ａ、３１ｂを示す。これらの案内経路３１ａ、３１ｂは、右左折回数が同じであるため、右左折回数のみを条件とした場合には、いずれの案内経路３１ａ、３１ｂも選択可能である。右左折回数の条件に加えて、道幅や道路種別（歩行者優先通路であるか、自転車専用道路であるか等）等の条件を付加することにより、経路を絞り込むことができる。また、案内経路３１ａ、３１ｂを比較し、距離や所要時間が短い案内経路を選択してもよい。
【００６９】
位置検出不能範囲２８内の案内経路（右左折回数が最も少ない案内経路３１ａ、３１ｂ）が決定された後、経路探索手段１８は、現在位置（出発地）Ｓから決定した案内経路の入口までの案内経路、および、前記案内経路の出口から目的地Ｇまでの案内経路を探索する（ステップＳ１０９）。例えば、案内経路３１ａを位置検出不能範囲２８内の案内経路に決定した場合、現在位置（出発地）Ｓから案内経路３１ａの入口である出入口２９ｃまでの案内経路を探索するとともに、案内経路３１ａの出口である出入口２９ｆから目的地Ｇまでの案内経路３２を探索する。
【００７０】
最後に、案内経路３０ｃと、位置検出不能範囲２８内の案内経路３１ａと、案内経路３２とを接続することにより、現在位置（出発地）Ｓから位置検出不能範囲２８を経由して目的地Ｇまでの案内経路を決定する（ステップＳ１１０）。決定した案内経路は、出力手段２６に表示される。ユーザは、表示された案内経路に従い、現在位置（出発地）Ｓから位置検出不能範囲２８を経由して目的地Ｇまで移動することができる。
【００７１】
なお、案内経路３１ａ、３１ｂのように、位置検出不能範囲２８で右左折回数が最も少ない案内経路が複数ある場合は、ステップＳ１１０で、夫々の案内経路（３１ａ、３１ｂ）に対して出発地Ｓから目的地Ｇまでの案内経路を探索し、探索した案内経路のうち、距離や所要時間が最も短いものを案内経路に決定してもよい。
【００７２】
ここで、上述した実施例のステップＳ１０４では、ノードデータおよびリンクデータのそれぞれに、建造物の出入口および建造物内の通路であるか否かを示す識別情報（フラグ）が設定されていることを利用して、位置検出不能範囲２８およびその出入口を決定するようにしている。これに対して、リンクデータに対してのみ、建造物内の通路であるか否かを示す識別情報（フラグ）を設定しておき、このリンクデータを用いて位置検出不能範囲２８および出入口を決定することもできる。
【００７３】
すなわち、図７に示すように、建造物内の通路であることを示す識別情報が設定されたリンクデータに対応するリンク３３、３４（黒丸間のラインで示す。）が連続して接続する範囲を、位置検出不能範囲２８を規定するリンク網３５、３６とし、リンク網３５、３６を構成するリンク３３、３４と、建造物外の通路であることを示す識別が設定されたリンクデータに対応するリンク３７とが接続されるノード３８、３９を当該建造物の出入口に決定することができる。
【００７４】
また、図８は、位置検出不能範囲４０が１階４１ａおよび２階４１ｂを有する建造物である場合を示す。このような位置検出不能範囲４０においては、通路が上り、下り、平坦のいずれであるのかを示す勾配情報をリンクデータに設定しておき、この勾配情報を用いて位置検出不能範囲４０内での経路を決定するようにすればよい。例えば、１階４１ａのノード４２ａが入口、１階４２ｂのノード４２ｂが出口、上りのリンク４３、下りのリンク４４、平坦なリンク４５、４６がある場合、ノード４２ａから１階の平坦なリンク４６を介してノード４２ｂに至る上り、下りの少ない経路とすることができる。
【００７５】
以上、詳細に説明したように、本実施例のナビゲーション装置１０によれば、現在位置（出発地）Ｓから目的地Ｇに至る経路中に位置検出不能範囲２８が有る場合、位置検出不能範囲２８内の経路を進行方向が変化する回数が最も少ない経路とすることにより、位置検出不能範囲２８で現在位置を検出できない場合であっても、ナビゲーション装置１０を所持するユーザを経路に従って円滑に目的地に導くことができる。
【００７６】
なお、本発明は、上述した実施例に限定されるものではなく、本発明の要旨を逸脱しない範囲で変更することが可能である。
【００７７】
例えば、徒歩で移動するユーザが所持するナビゲーション装置１０を用いて経路案内する場合について説明したが、公共機関を利用して移動する際の乗り換え案内を行う場合、または、車両に搭載したナビゲーション装置を用いてユーザを目的地に導く場合にも適用することができる。車両の場合、本発明は、例えば、地下駐車場や立体駐車場、複数の分岐点を有するトンネル等の位置検出不能範囲が経路中に含まれる場合において有効である。
【００７８】
また、本発明は上記の手順に限られるものでなく、例えば、経路探索手段１８が当該建造物の全ての出入口を対象に各出入口間を結ぶ全ての案内経路を総あたりで再探索し、そのうち進行方向が変化する回数が最も少ない案内経路を特定し、その経路の建造物への入口ノード、出口ノードと、出発地、目的地との間の案内経路を再探索して、探索された案内経路と先に再探索した建造物内の案内経路とを統合してユーザに提示する手順としてもよい。
【００７９】
また、上記実施例においては、経路探索手段１８と判定手段２０はそれぞれ別の構成要素として説明したが、経路探索手段１８に判定手段２０の機能を含むように構成してもよい。
【００８０】
さらに、本実施例では、位置検出不能範囲（建造物）内の出入口が複数ある場合を例示したが、これに限ることはなく、例えば、位置検出不能範囲（建造物）内の出口、入口が１つずつしかない場合であっても、入口から出口までの案内経路を複数の探索条件（距離優先、時間優先、道幅優先など）で探索し、複数の案内経路のうち、最も右左折の回数が少ない経路を抽出すること好ましい。
【符号の説明】
【００８１】
１０・・・ナビゲーション装置
１３・・・制御手段
１４・・・ＣＰＵ
１５・・・ＲＯＭ
１６・・・ＲＡＭ
１７・・・現在位置検出手段
１８・・・経路探索手段
１９・・・地図記憶手段
２０・・・判定手段
２５・・・入力手段
２６・・・出力手段
２７、３０ａ〜３０ｇ、３１ａ、３１ｂ、３２・・・案内経路
２８、４０・・・位置検出不能範囲
２９ａ〜２９ｇ・・・出入口
３３、３４、３７、４３、４４、４５、４６・・・リンク
３５、３６・・・リンク網
３８、３９、４２ａ、４２ｂ・・・ノード
【技術分野】
【０００１】
本発明は、経路探索装置に関し、特に、位置検出不能な範囲を通過する経路を探索する経路探索装置に関する。
【背景技術】
【０００２】
従来から、ＧＰＳ（Global Positioning System）等により車両の現在位置を検出し、その現在位置をディスプレイに道路地図とともに表示し、また、目的地までの経路を探索してディスプレイに表示することにより、ユーザを目的地まで円滑に導くようにしたナビゲーション装置が知られている。なお、ナビゲーション装置は、車両に搭載される装置に限られるものではなく、例えば、ユーザが所持する携帯電話やＰＤＡ等の携帯端末に搭載し、ユーザが徒歩や電車、バス等の交通機関により目的地に向う際の支援装置として利用できるものもある。
【０００３】
このようなナビゲーション装置において、目的地までユーザを円滑に導くためには、ユーザの要望に適した経路を案内できることが重要である。
【０００４】
そこで、例えば、下記の特許文献１（特開平６−２４９６７２号公報）には、出発地から目的地までの間に複数の推奨経路を探索して表示するとともに、各推奨経路の右左折の回数を演算して表示し、ユーザが右折または左折の回数の少ない推奨経路を選択可能としたナビゲーション装置が開示されている。
【０００５】
また、下記の特許文献２（特開２００４−２０５４０９号公報）には、交差点等の分岐点の手前に合流地点がある道路の場合、ドライバの負担となるような右左折を極力回避可能な経路探索を行うようにしたナビゲーション装置が開示されている。
【０００６】
また、下記の特許文献３（特開平９−３２５０３８号公報）には、右折回数が可能な限り少ない経路を探索することにより、より早く目的地に到達可能とした経路探索装置が開示されている。
【０００７】
さらに、下記の特許文献４（特開２００６−２２６７８６号公報）には、左折優先経路を算出することにより、不案内なエリアでも、右折に伴う負担やリスクを軽減することができるナビゲーション装置が開示されている。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】特開平６−２４９６７２号公報（段落［００２５］〜［００２８］）
【特許文献２】特開２００４−２０５４０９号公報（段落［０００７］、［０００８］）
【特許文献３】特開平９−３２５０３８号公報（段落［００１７］）
【特許文献４】特開２００６−２２６７８６号公報（段落［００１８］、［００１９］）
【発明の概要】
【発明が解決しようとする課題】
【０００９】
しかしながら、上記特許文献１に開示されたナビゲーション装置では、推奨経路の全行程で右左折の回数が少ない経路を探索して選択することが可能であるが、特定の範囲での右左折回数を必ずしも少なく設定できるものではない。
【００１０】
ここで、特定の範囲が、例えば、屋内駐車場や地下駐車場のように、ＧＰＳ衛星からの電波を受信できない建造物の内部である場合、ナビゲーション装置の正確な現在位置を検出することができないため、右左折ポイント（案内地点）で音声などによる案内をすることができない。
【００１１】
そのため、建造物の内部に多数の右左折があるような複雑な経路が設定されていると、ユーザにとっては、その経路に沿って円滑に移動することが困難になる場合がある。
【００１２】
車両用のナビゲーション装置では、屋内駐車場や地下駐車場内の経路を探索できるように地図情報に当該施設内（屋内駐車場や地下駐車場）の通路情報を備えているものもあり、また歩行者用のナビゲーション装置では、駅構内や地下街等の建造物内においても経路探索が行えるように、地図情報として当該施設内（駅構内や地下街）の通路情報を記憶しているものがある。しかしながら、これらの施設内、建造物内ではＧＰＳ衛星からの電波を受信することができない場合がある。
【００１３】
従って、それらの施設内の通路に位置情報を提供する位置送信ユニットなどの専用のインフラが整備されていない限り、車両や歩行者の位置を検出することができない。このためそれらの施設内の経路を探索することはできても、右左折などのポイント（案内地点）で音声案内ができないという問題がある。
【００１４】
そのため、施設や建造物内を通過する場合においては、施設や建造物外で右左折の回数が増えたとしても、施設や建造物内での右左折回数を減らすことが望まれる。
【００１５】
なお、上記特許文献２〜４に開示されたナビゲーション装置または経路探索装置の場合、単に右左折が少ない経路を探索することにより、移動時間の短縮やドライバに対する負担を軽減することを目的としているだけであり、現在位置を検出できない範囲において、ユーザを目的地まで円滑に導くことを目的としたものではない。
【００１６】
本発明は、上記の問題点を解消することを課題とするものであり、検索した経路中に現在位置を検出できない位置検出不能範囲が有る場合であっても、ユーザを目的地まで円滑に導くことのできる経路探索装置を提供することを目的とするものである。
【課題を解決するための手段】
【００１７】
前記課題を解決するために、本願の請求項１にかかる発明は、
地図情報を参照して出発地から目的地までの経路を探索する経路探索手段を備えた経路探索装置であって、
前記経路探索装置は、前記経路探索手段により探索された経路中に現在位置を検出できない位置検出不能範囲が有るか否かを判定する判定手段を備え、
前記経路探索手段は、前記判定手段により前記位置検出不能範囲が有ると判定された場合、前記位置検出不能範囲内で進行方向が変化する回数が最も少ない経路を探索することを特徴とする。
【００１８】
本願の請求項２にかかる発明は、請求項１に記載の経路探索装置において、前記経路探索手段は、前記位置検出不能範囲内で進行方向が変化する回数が最も少ない経路、前記出発地及び前記目的地に基づき、前記出発地から前記目的地までの経路を探索することを特徴とする。
【００１９】
本願の請求項３にかかる発明は、請求項１又は２に記載の経路探索装置において、前記経路探索手段は、前記判定手段により前記位置検出不能範囲が有ると判定された場合、前記位置検出不能範囲の入口及び出口を特定し、前記入口から前記出口までの経路を探索することで、前記位置検出不能範囲内で進行方向が変化する回数が最も少ない経路を探索することを特徴とする。
【００２０】
本願の請求項４にかかる発明は、請求項３に記載の経路探索装置において、前記経路探索手段は、前記入口から前記出口までの経路を複数の探索条件で探索することを特徴とする。
【００２１】
本願の請求項５にかかる発明は、請求項３又は４に記載の経路探索装置において、前記経路探索手段は、前記出発地から前記位置検出不能範囲の出入口までの経路を探索し、前記位置検出不能範囲を通過しない前記経路の前記出入口を入口とし、前記位置検出不能範囲を通過する前記経路の前記出入口を出口とすることを特徴とする。
【００２２】
本願の請求項６にかかる発明は、請求項１〜５の何れかに記載の経路探索装置において、前記位置検出不能範囲は、建造物の内部であることを特徴とすることを特徴とする。
【００２３】
本願の請求項７にかかる発明は、請求項１〜６の何れかに記載の経路探索装置において、前記進行方向が変化する回数は、上下方向への進行方向の変化及び／又は右左折の回数であることを特徴とする。
【００２４】
本願の請求項８にかかる発明は、請求項１〜７の何れかに記載の経路探索装置において、前記経路探索手段は、前記進行方向が変化する回数が最も少ない経路が複数あるとき、移動距離が最も短い経路を前記進行方向が変化する回数が最も少ない経路として探索することを特徴とする。
【発明の効果】
【００２５】
請求項１にかかる発明においては、地図情報を参照して出発地から目的地までの経路を探索する経路探索手段を備えた経路探索装置であって、前記経路探索装置は、前記経路探索手段により探索された経路中に現在位置を検出できない位置検出不能範囲が有るか否かを判定する判定手段を備え、前記経路探索手段は、前記判定手段により前記位置検出不能範囲が有ると判定された場合、前記位置検出不能範囲内で進行方向が変化する回数が最も少ない経路を探索する。
【００２６】
かかる構成によれば、目的地までの経路中に位置検出不能範囲が有る場合であっても、前記位置検出不能範囲における経路を再探索し、進行方向が変化する回数が最も少ない経路を特定するから、現在位置が特定できず、分岐点（進行方向が変化する地点）における右左折等の音声案内ができなくても、ユーザを比較的円滑に目的地まで導く経路を提示することができるようになる。
【００２７】
請求項２にかかる発明においては、請求項１にかかる発明において、経路探索手段は、前記位置検出不能範囲内で進行方向が変化する回数が最も少ない経路、前記出発地及び前記目的地に基づき、前記出発地から前記目的地までの経路を探索する。かかる構成によれば、かかる構成によれば、経路探索手段は効率よく位置検出不能範囲内で進行方向が変化する回数が最も少ない経路を有する出発地から目的地までの最適経路を再探索することができるようになる。
【００２８】
また、請求項３にかかる発明においては、請求項１又は２にかかる発明において、経路探索手段は、前記判定手段により前記位置検出不能範囲が有ると判定された場合、前記位置検出不能範囲の入口及び出口を特定し、前記入口から前記出口までの経路を探索することで、前記位置検出不能範囲内で進行方向が変化する回数が最も少ない経路を探索する。かかる構成によれば、経路探索手段は効率よく位置検出不能範囲内で進行方向が変化する回数が最も少ない経路を再探索することができるようになる。
【００２９】
請求項４にかかる発明においては、請求項３にかかる発明において、経路探索手段は、前記入口から前記出口までの経路を複数の探索条件で探索する。かかる構成によれば、距離優先、時間優先、道幅優先、自転車兼用道路回避などの種々の探索条件で経路を探索し、複数の案内経路のうち、最も右左折の回数が少ない経路を抽出してユーザに提供することができるようになる。
【００３０】
また、請求項５にかかる発明においては、請求項３又は４に記載の発明において、経路探索手段は、前記出発地から前記位置検出不能範囲の出入口までの経路を探索し、前記位置検出不能範囲を通過しない前記経路の前記出入口を入口とし、前記位置検出不能範囲を通過する前記経路の前記出入口を出口とする。かかる構成によれば、出発地の場所に寄らず入口と出口を特定することが可能となる。
【００３１】
請求項６にかかる発明においては、請求項１〜５の何れかに記載の発明において、位置検出不能範囲は、建造物の内部であるから、建物内の駐車や地下街において、進行方向が変化する回数が最も少ない経路を特定するから、現在位置が特定できず、分岐点（進行方向が変化する地点）における右左折等の音声案内ができなくても、ユーザを比較的円滑に目的地まで導く経路を提示することができるようになる。
【００３２】
請求項７にかかる発明においては、請求項１〜６の何れかに記載の発明において、進行方向が変化する回数は、上下方向への進行方向の変化及び／又は右左折の回数であるから、建物内の駐車や地下街において、水平方向のみなら垂直方向であるフロアを上下することが少ない経路をユーザに提示できるようになる。
【００３３】
請求項８にかかる発明においては、請求項１〜７の何れかに記載の発明において、経路探索手段は、前記進行方向が変化する回数が最も少ない経路が複数あるとき、移動距離が最も短い経路を前記進行方向が変化する回数が最も少ない経路として探索するから、ユーザに最も右左折の回数が少ない経路であって、かつ移動距離が最短の最適経路を提示することができるようになる。
【図面の簡単な説明】
【００３４】
【図１】本発明の実施例にかかるナビゲーション装置の要部構成を示すブロック図である。
【図２】本発明の実施例にかかるナビゲーション装置における処理フローチャートである。
【図３】本発明の実施例にかかるナビゲーション装置により検索された目的地までの経路の説明図である。
【図４】本発明の実施例にかかるナビゲーション装置により検索された建造物の出入口までの経路の説明図である。
【図５】本発明の実施例にかかるナビゲーション装置により検索された建造物内の経路の説明図である。
【図６】本発明の実施例にかかるナビゲーション装置により検索された目的地までの適切な経路の説明図である。
【図７】本発明の実施例にかかるナビゲーション装置による建造物およびその出入口を検索する説明図である。
【図８】本発明の実施例にかかるナビゲーション装置により検索された建造物内の経路の説明図である。
【発明を実施するための形態】
【００３５】
以下、本発明の具体例を実施例及び図面を用いて詳細に説明する。但し、以下に示す実施形態は、本発明の技術的思想を具体化するための経路探索装置としてナビゲーション装置を例示するものであって、本発明をこのナビゲーション装置に特定することを意図するものではなく、特許請求の範囲に含まれるその他の実施形態の経路探索装置にも等しく適応し得るものである。
【実施例】
【００３６】
図１は、本発明の実施例にかかるナビゲーション装置１０の要部構成を示すブロック図である。
【００３７】
ナビゲーション装置１０は、例えば、ユーザが所持する携帯電話やＰＤＡ等の携帯端末に搭載され、徒歩や電車、バス等の交通機関を利用して移動する際における経路案内を行うものである。なお、ナビゲーション装置１０は、ユーザに目的地までの経路案内を行うとともに、目的地又は案内経路に関連した施設や観光スポット等の関連情報をユーザに提供するものであってもよい。
【００３８】
ナビゲーション装置１０は、制御手段１３を備える。制御手段１３は、ＣＰＵ１４、ＲＯＭ１５、ＲＡＭ１６からなるプロセッサで構成され、ＲＯＭ１５、ＲＡＭ１６に記録された制御プログラムに従ってナビゲーション装置１０の各部の動作を制御するものである。
【００３９】
また、ナビゲーション装置１０は、現在位置検出手段１７、経路探索手段１８、地図記憶手段１９、判定手段２０、入力手段２５、出力手段２６などを備えて構成されている。
【００４０】
現在位置検出手段１７は、地球上空を周回している複数のＧＰＳ衛星から時刻情報及び位置情報を含む電波を受信するＧＰＳ受信機等で構成される。３個以上のＧＰＳ衛星からの電波を受信して処理することにより、ユーザが所持するナビゲーション装置１０の現在位置を算出することができる。また、現在位置検出手段１７は、車両又はナビゲーション装置１０に搭載された加速度センサ、距離センサ、方位センサ、舵角センサ等からなる自立航法装置を備えることもできる。
【００４１】
なお、現在位置検出手段１７が自律航法装置を備えた場合であっても、ユーザが徒歩で使用する場合には、ユーザがナビゲーション装置１０を固定して使用しなければ自律航法装置で正確な現在位置を算出することができない。また、ユーザがナビゲーション装置１０を固定して使用した場合であっても、自律航法装置で算出する現在位置は、ＧＰＳ衛星からの電波に基づき算出する絶対的な現在位置とは異なり、前回の現在位置からの相対的な現在位置であるため、自律航法装置のみで現在位置を検出した場合では、現在位置の誤差が増大してしまう恐れがある。
【００４２】
経路探索手段１８は、ユーザが入力手段２５を用いて目的地を入力することにより、地図記憶手段１９に記憶されている地図情報を参照し、現在位置又はユーザによって指定された出発地から目的地に至る最適な案内経路を探索するものである。
【００４３】
なお、案内経路の探索は、現在位置又は出発地に対応するノードから目的地に対応するノードに至るリンクと、ノードとをダイクストラ法等の各種の手法によって探索し、リンク長（リンクコスト）や所要時間等を累積し、総リンク長（移動距離）又は総所要時間等が最短となる経路を案内経路とし、当該経路に属するノードやリンクを案内経路データとして提供するものである。
【００４４】
地図記憶手段１９は、地図情報、施設情報、交通機関の時刻情報及び乗り換え情報等の各種情報を記憶する。
【００４５】
地図情報には、道路や通路の分岐点をノードとするノードデータ、それぞれのノード間を結ぶ経路をリンクとしたリンクデータ、地形図データが含まれる。
【００４６】
ノードデータには、ノード番号、位置座標、接続リンク本数、分岐点名称の他、分岐点から所定距離だけ離れた案内地点において、右左折、直進等の経路案内を行う経路案内データ及び案内地点の位置座標が記憶されている。また、ノードは、駅構内、地下街等の建造物の出入口に対しても設定される。出入口のノードには、建造物の出入口であることを示す識別情報（フラグ）が設定される。また、建造物の出入口に対して設定されるノードには、当該建造物の名称等の当該建造物に関連する情報が含まれる。
【００４７】
リンクデータには、始点及び終点となるノード番号、道路種別（歩行者優先通路、自転車兼用道路等）、ノード間の距離情報であるリンク長（リンクコスト）、所要時間等が含まれる。また、建造物内部のリンクデータには、建造物内部の通路であることを示す識別情報（フラグ）が設定される。さらに、リンクデータには、リンク属性として橋、トンネル、踏切、料金所等のデータが付与される。
【００４８】
地形図データには、海岸線、湖沼、河川形状などの水系データ、行政境界データからなる背景データが含まれる。
【００４９】
また、地図記憶手段１９には、駐車場やガソリンスタンドなどの施設毎の施設情報も記憶されている。施設情報には、○○支店などの施設の名称、施設形状、位置座標、営業時間、ガソリンスタンドや地下駐車場、地下街、駅などの施設の種別、ランドマークなどの施設の画像などが含まれている。また、施設情報には、施設毎に出入口の情報も含まれ、この出入口の情報は、地図情報に含まれるノードデータに関連している。
【００５０】
判定手段２０は、経路探索手段１８が探索した案内経路に、位置検出不能範囲が含まれるか否かを判定する。具体的には、地図情報を参照して、地下駐車場や屋内駐車場あるいは地下街や建物内等の建造物内を通過するかを判定する。
【００５１】
入力手段２５は、ナビゲーション装置１０における操作入力や、出発地、目的地などの経路検索条件、あるいは、出発地又は目的地とする施設、駐車場などの所望の施設を検索するための検索条件等を設定するための各種キー、タッチパネル、リモートコントローラ等から構成される。
【００５２】
出力手段２６は、地図情報および施設情報に基づいた地図画像、案内経路画像、施設の写真や施設の詳細な説明のテキスト等をユーザに表示する液晶ディスプレイ、及び、案内経路における案内地点での経路案内や警告を含む音声情報を出力するスピーカ等で構成される。
【００５３】
本実施例にかかるナビゲーション装置１０においては、判定手段２０が、経路探索手段１８が探索した案内経路に、地下駐車場や屋内駐車場あるいは地下街や建物内等の建造物内を通過すると判定すると、経路探索手段１８は、当該建造物内の出口ノード、入口ノード（出入口ノード）を抽出し、出発地から出入口ノードまでのそれぞれの案内経路を探索し、そのうち建造物内を通過せずに出入口ノードに到達した経路の出入口ノードを「入口」とし、建造物内を通過して出入口ノードに到達した経路の出入口ノードを「出口」とする。そして経路探索手段１８は、各入口から各出口までの建造物内の案内経路を各々再探索し、最も進行方向が変化する回数の少ない案内経路を建造物内の案内経路とする。
【００５４】
なお、進行方向が変化する回数が少ない案内経路とは、案内経路上において、上下方向への進行方向の変化や右左折の回数が少ない案内経路である。なお、以下の説明では、単に右左折回数が少ない案内経路として説明を行う。
【００５５】
そして、当該建造物内の案内経路、出発地から当該建造物内の案内経路の「入口」（出発地）までの案内経路、および、当該建造物内の案内経路の「出口」（目的地）から目的地までの案内経路を接続してユーザに提示する。このことにより、ユーザには建造物内で右左折回数が最も少ない案内経路が提示されるから、ユーザは経路案内ができない建造物内であっても比較的容易に経路に沿って進行することができるようになる。
【００５６】
なお、本発明において、進行方向の変化とは、建造物内における水平方向の右左折の他、建造物内の垂直方向への変化、例えば、階段、エスカレータにより上下方向（垂直方向）に進行方向が変化する場合も含むものとしてもよい。
【００５７】
次に、図２に示す処理フローチャートに基づき、本実施例のナビゲーション装置１０の動作を説明する。
【００５８】
現在位置検出手段１７は、ＧＰＳ衛星から位置情報を含む電波を受信することにより、ナビゲーション装置１０の現在位置を検出する（ステップＳ１０１）。制御手段１３は、検出した現在位置に基づき、地図記憶手段１９から対応する地図情報を抽出し、現在位置を示すマークとともに出力手段２６に地図画像を表示する。ユーザは、表示された地図画像に従い、現在位置を確認することができる。
【００５９】
ユーザは、ナビゲーション装置１０の入力手段２５を用いて目的地を設定するとともに（ステップＳ１０２）、必要に応じて出発地を設定する。目的地等が設定されると、経路探索手段１８は、現在位置検出手段１７により検出した現在位置、または、ユーザが設定した出発地から、目的地までの案内経路を探索する（ステップＳ１０３）。案内経路は、地図記憶手段１９に記憶されているノードデータおよびリンクデータに基づき、例えば、目的地までの所要時間が最も短い経路、または、目的地までの距離が最も短い経路として探索することができる。図３は、現在位置（出発地）Ｓから目的地Ｇに至る案内経路２７を模式的に示したものである。
【００６０】
次に、判定手段２０は、ステップＳ１０３で経路探索手段１８が探索した案内経路２７の一部に位置検出不能範囲２８が有るか否かを判定する（ステップＳ１０４）。この場合、位置検出不能範囲２８とは、現在位置検出手段１７がＧＰＳ衛星から電波を受信できないため、現在位置を検出することができない範囲であり、例えば、駅構内、デパート内、地下街、トンネル内等の建造物内の範囲である。
【００６１】
位置検出不能範囲２８の有無は、案内経路データを構成するノードデータに建造物の出入口であることを示す識別情報（フラグ）が設定されているか否か、または、案内経路データを構成するリンクデータに建造物内の通路であることを示す識別情報（フラグ）が設定されているか否かにより判定することができる。図３は、一部に位置検出不能範囲２８が有る案内経路２７を示す。なお、経路探索手段１８が探索した案内経路データ（ノードデータ、リンクデータ）に前述のようなフラグを付加しない場合であっても、地図情報に属性情報として構造物内の通路リンクであることを示す情報が付加されていれば、判定手段２０は、この地図情報（属性情報）を参照してこれを判定することもできる。
【００６２】
案内経路２７の一部に位置検出不能範囲２８が無い場合（ステップＳ１０４、ＮＯ）、案内経路２７を最適な経路として確定する。確定した案内経路２７は、出力手段２６に現在位置を示すマークとともに表示される。ユーザは、表示された案内経路２７に従い、所望の目的地に移動することができる。
【００６３】
一方、案内経路２７の一部に位置検出不能範囲２８が有る場合（ステップＳ１０４、ＹＥＳ）、図４に示すように、経路探索手段１８は、現在位置（出発地）Ｓから位置検出不能範囲２８の各出入口２９ａ〜２９ｇまでの案内経路３０ａ〜３０ｇを探索する（ステップＳ１０５）。なお、位置検出不能範囲２８の出入口２９ａ〜２９ｇは、位置検出不能範囲２８（例えば、位置検出不能範囲２８が、駅であれば当該駅の出入口の情報）のノードデータに設定されている識別情報（フラグ）に基づいて抽出することができる。
【００６４】
次いで、探索された案内経路３０ａ〜３０ｇに基づき、位置検出不能範囲２８を通過して出入口に到達した案内経路３０ｅ〜３０ｇの出入口２９ｅ〜２９ｇを出口に決定し、位置検出不能範囲２８を通過せずに出入口に到達した案内経路３０ａ〜３０ｄの出入口２９ａ〜２９ｄを入口に決定する（ステップＳ１０６）。
【００６５】
位置検出不能範囲２８の出入口２９ａ〜２９ｇの入口および出口が決定された後、経路探索手段１８は、位置検出不能範囲２８における各入口から各出口までの案内経路を探索する（ステップＳ１０７）。案内経路は、地図記憶手段１９に記憶されているノードデータおよびリンクデータに基づき、例えば、入口、出口間での所要時間が最も短い経路、または、入口、出口間の距離が最も短い経路として探索することができる。なお、図５に示す例では、入口である出入口２９ａ〜２９ｄから出口である出入口２９ｅ〜２９ｇまでの経路として、１２通りの案内経路が探索される。
【００６６】
次に、探索された位置検出不能範囲２８における複数の経路から、右左折回数が最も少ない案内経路を抽出する（ステップＳ１０８）。右左折回数が最も少ない案内経路を抽出することにより、ユーザは、現在位置を検出することができない位置検出不能範囲２８において、経路を誤ることなく、案内された出口まで円滑に移動することが可能となる。なお、右左折回数が少ない案内経路を抽出する方法は、上記の先行文献に記載されている通り種々の方法を用いることができる。例えば、リンクデータにリンクの進行方向が含まれる場合、案内経路データに含まれるリンクの進行方向と、案内経路データに含まれ、当該リンクに隣接するリンクの進行方向とを比較することで、進行方向が変化する角度を算出し、当該角度が所定値以上であれば、右左折を行なう回数としてカウントする。
【００６７】
そして、カウントした右左折を行う回数が最も少ない案内経路を、右左折回数が最も少ない案内経路として抽出する。抽出された案内経路は、後述するようにして出発地から入口までの経路、出口から目的地までの経路と接続されてユーザに提示される。
【００６８】
図６は、ステップＳ１０８の処理で抽出された２本の案内経路３１ａ、３１ｂを示す。これらの案内経路３１ａ、３１ｂは、右左折回数が同じであるため、右左折回数のみを条件とした場合には、いずれの案内経路３１ａ、３１ｂも選択可能である。右左折回数の条件に加えて、道幅や道路種別（歩行者優先通路であるか、自転車専用道路であるか等）等の条件を付加することにより、経路を絞り込むことができる。また、案内経路３１ａ、３１ｂを比較し、距離や所要時間が短い案内経路を選択してもよい。
【００６９】
位置検出不能範囲２８内の案内経路（右左折回数が最も少ない案内経路３１ａ、３１ｂ）が決定された後、経路探索手段１８は、現在位置（出発地）Ｓから決定した案内経路の入口までの案内経路、および、前記案内経路の出口から目的地Ｇまでの案内経路を探索する（ステップＳ１０９）。例えば、案内経路３１ａを位置検出不能範囲２８内の案内経路に決定した場合、現在位置（出発地）Ｓから案内経路３１ａの入口である出入口２９ｃまでの案内経路を探索するとともに、案内経路３１ａの出口である出入口２９ｆから目的地Ｇまでの案内経路３２を探索する。
【００７０】
最後に、案内経路３０ｃと、位置検出不能範囲２８内の案内経路３１ａと、案内経路３２とを接続することにより、現在位置（出発地）Ｓから位置検出不能範囲２８を経由して目的地Ｇまでの案内経路を決定する（ステップＳ１１０）。決定した案内経路は、出力手段２６に表示される。ユーザは、表示された案内経路に従い、現在位置（出発地）Ｓから位置検出不能範囲２８を経由して目的地Ｇまで移動することができる。
【００７１】
なお、案内経路３１ａ、３１ｂのように、位置検出不能範囲２８で右左折回数が最も少ない案内経路が複数ある場合は、ステップＳ１１０で、夫々の案内経路（３１ａ、３１ｂ）に対して出発地Ｓから目的地Ｇまでの案内経路を探索し、探索した案内経路のうち、距離や所要時間が最も短いものを案内経路に決定してもよい。
【００７２】
ここで、上述した実施例のステップＳ１０４では、ノードデータおよびリンクデータのそれぞれに、建造物の出入口および建造物内の通路であるか否かを示す識別情報（フラグ）が設定されていることを利用して、位置検出不能範囲２８およびその出入口を決定するようにしている。これに対して、リンクデータに対してのみ、建造物内の通路であるか否かを示す識別情報（フラグ）を設定しておき、このリンクデータを用いて位置検出不能範囲２８および出入口を決定することもできる。
【００７３】
すなわち、図７に示すように、建造物内の通路であることを示す識別情報が設定されたリンクデータに対応するリンク３３、３４（黒丸間のラインで示す。）が連続して接続する範囲を、位置検出不能範囲２８を規定するリンク網３５、３６とし、リンク網３５、３６を構成するリンク３３、３４と、建造物外の通路であることを示す識別が設定されたリンクデータに対応するリンク３７とが接続されるノード３８、３９を当該建造物の出入口に決定することができる。
【００７４】
また、図８は、位置検出不能範囲４０が１階４１ａおよび２階４１ｂを有する建造物である場合を示す。このような位置検出不能範囲４０においては、通路が上り、下り、平坦のいずれであるのかを示す勾配情報をリンクデータに設定しておき、この勾配情報を用いて位置検出不能範囲４０内での経路を決定するようにすればよい。例えば、１階４１ａのノード４２ａが入口、１階４２ｂのノード４２ｂが出口、上りのリンク４３、下りのリンク４４、平坦なリンク４５、４６がある場合、ノード４２ａから１階の平坦なリンク４６を介してノード４２ｂに至る上り、下りの少ない経路とすることができる。
【００７５】
以上、詳細に説明したように、本実施例のナビゲーション装置１０によれば、現在位置（出発地）Ｓから目的地Ｇに至る経路中に位置検出不能範囲２８が有る場合、位置検出不能範囲２８内の経路を進行方向が変化する回数が最も少ない経路とすることにより、位置検出不能範囲２８で現在位置を検出できない場合であっても、ナビゲーション装置１０を所持するユーザを経路に従って円滑に目的地に導くことができる。
【００７６】
なお、本発明は、上述した実施例に限定されるものではなく、本発明の要旨を逸脱しない範囲で変更することが可能である。
【００７７】
例えば、徒歩で移動するユーザが所持するナビゲーション装置１０を用いて経路案内する場合について説明したが、公共機関を利用して移動する際の乗り換え案内を行う場合、または、車両に搭載したナビゲーション装置を用いてユーザを目的地に導く場合にも適用することができる。車両の場合、本発明は、例えば、地下駐車場や立体駐車場、複数の分岐点を有するトンネル等の位置検出不能範囲が経路中に含まれる場合において有効である。
【００７８】
また、本発明は上記の手順に限られるものでなく、例えば、経路探索手段１８が当該建造物の全ての出入口を対象に各出入口間を結ぶ全ての案内経路を総あたりで再探索し、そのうち進行方向が変化する回数が最も少ない案内経路を特定し、その経路の建造物への入口ノード、出口ノードと、出発地、目的地との間の案内経路を再探索して、探索された案内経路と先に再探索した建造物内の案内経路とを統合してユーザに提示する手順としてもよい。
【００７９】
また、上記実施例においては、経路探索手段１８と判定手段２０はそれぞれ別の構成要素として説明したが、経路探索手段１８に判定手段２０の機能を含むように構成してもよい。
【００８０】
さらに、本実施例では、位置検出不能範囲（建造物）内の出入口が複数ある場合を例示したが、これに限ることはなく、例えば、位置検出不能範囲（建造物）内の出口、入口が１つずつしかない場合であっても、入口から出口までの案内経路を複数の探索条件（距離優先、時間優先、道幅優先など）で探索し、複数の案内経路のうち、最も右左折の回数が少ない経路を抽出すること好ましい。
【符号の説明】
【００８１】
１０・・・ナビゲーション装置
１３・・・制御手段
１４・・・ＣＰＵ
１５・・・ＲＯＭ
１６・・・ＲＡＭ
１７・・・現在位置検出手段
１８・・・経路探索手段
１９・・・地図記憶手段
２０・・・判定手段
２５・・・入力手段
２６・・・出力手段
２７、３０ａ〜３０ｇ、３１ａ、３１ｂ、３２・・・案内経路
２８、４０・・・位置検出不能範囲
２９ａ〜２９ｇ・・・出入口
３３、３４、３７、４３、４４、４５、４６・・・リンク
３５、３６・・・リンク網
３８、３９、４２ａ、４２ｂ・・・ノード
【特許請求の範囲】
【請求項１】
地図情報を参照して出発地から目的地までの経路を探索する経路探索手段を備えた経路探索装置であって、
前記経路探索装置は、前記経路探索手段により探索された経路中に現在位置を検出できない位置検出不能範囲が有るか否かを判定する判定手段を備え、
前記経路探索手段は、前記判定手段により前記位置検出不能範囲が有ると判定された場合、前記位置検出不能範囲内で進行方向が変化する回数が最も少ない経路を探索することを特徴とする経路探索装置。
【請求項２】
前記経路探索手段は、前記位置検出不能範囲内で進行方向が変化する回数が最も少ない経路、前記出発地及び前記目的地に基づき、前記出発地から前記目的地までの経路を探索することを特徴とする請求項１に記載の経路探索装置。
【請求項３】
前記経路探索手段は、前記判定手段により前記位置検出不能範囲が有ると判定された場合、前記位置検出不能範囲の入口及び出口を特定し、前記入口から前記出口までの経路を探索することで、前記位置検出不能範囲内で進行方向が変化する回数が最も少ない経路を探索することを特徴とする請求項１又は２に記載の経路探索装置。
【請求項４】
前記経路探索手段は、前記入口から前記出口までの経路を複数の探索条件で探索することを特徴とする請求項３に記載の経路探索装置。
【請求項５】
前記経路探索手段は、前記出発地から前記位置検出不能範囲の出入口までの経路を探索し、前記位置検出不能範囲を通過しない前記経路の前記出入口を入口とし、前記位置検出不能範囲を通過する前記経路の前記出入口を出口とすることを特徴とする請求項３又は４に記載の経路探索装置。
【請求項６】
前記位置検出不能範囲は、建造物の内部であることを特徴とする請求項１〜５の何れかに記載の経路探索装置。
【請求項７】
前記進行方向が変化する回数は、上下方向への進行方向の変化及び／又は右左折の回数であることを特徴とする請求項１〜６の何れかに記載の経路探索装置。
【請求項８】
前記経路探索手段は、前記進行方向が変化する回数が最も少ない経路が複数あるとき、移動距離が最も短い経路を前記進行方向が変化する回数が最も少ない経路として探索することを特徴とする請求項１〜７の何れかに記載の経路探索装置。
【請求項１】
地図情報を参照して出発地から目的地までの経路を探索する経路探索手段を備えた経路探索装置であって、
前記経路探索装置は、前記経路探索手段により探索された経路中に現在位置を検出できない位置検出不能範囲が有るか否かを判定する判定手段を備え、
前記経路探索手段は、前記判定手段により前記位置検出不能範囲が有ると判定された場合、前記位置検出不能範囲内で進行方向が変化する回数が最も少ない経路を探索することを特徴とする経路探索装置。
【請求項２】
前記経路探索手段は、前記位置検出不能範囲内で進行方向が変化する回数が最も少ない経路、前記出発地及び前記目的地に基づき、前記出発地から前記目的地までの経路を探索することを特徴とする請求項１に記載の経路探索装置。
【請求項３】
前記経路探索手段は、前記判定手段により前記位置検出不能範囲が有ると判定された場合、前記位置検出不能範囲の入口及び出口を特定し、前記入口から前記出口までの経路を探索することで、前記位置検出不能範囲内で進行方向が変化する回数が最も少ない経路を探索することを特徴とする請求項１又は２に記載の経路探索装置。
【請求項４】
前記経路探索手段は、前記入口から前記出口までの経路を複数の探索条件で探索することを特徴とする請求項３に記載の経路探索装置。
【請求項５】
前記経路探索手段は、前記出発地から前記位置検出不能範囲の出入口までの経路を探索し、前記位置検出不能範囲を通過しない前記経路の前記出入口を入口とし、前記位置検出不能範囲を通過する前記経路の前記出入口を出口とすることを特徴とする請求項３又は４に記載の経路探索装置。
【請求項６】
前記位置検出不能範囲は、建造物の内部であることを特徴とする請求項１〜５の何れかに記載の経路探索装置。
【請求項７】
前記進行方向が変化する回数は、上下方向への進行方向の変化及び／又は右左折の回数であることを特徴とする請求項１〜６の何れかに記載の経路探索装置。
【請求項８】
前記経路探索手段は、前記進行方向が変化する回数が最も少ない経路が複数あるとき、移動距離が最も短い経路を前記進行方向が変化する回数が最も少ない経路として探索することを特徴とする請求項１〜７の何れかに記載の経路探索装置。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【公開番号】特開２０１１−２１４８７７（Ｐ２０１１−２１４８７７Ａ）
【公開日】平成２３年１０月２７日（２０１１．１０．２７）
【国際特許分類】
【出願番号】特願２０１０−８０８８４（Ｐ２０１０−８０８８４）
【出願日】平成２２年３月３１日（２０１０．３．３１）
【出願人】（０００００１８８９）三洋電機株式会社 (18,308)
【出願人】（０００２１４８９２）三洋電機コンシューマエレクトロニクス株式会社 (1,582)
【Ｆターム（参考）】
【公開日】平成２３年１０月２７日（２０１１．１０．２７）
【国際特許分類】
【出願日】平成２２年３月３１日（２０１０．３．３１）
【出願人】（０００００１８８９）三洋電機株式会社 (18,308)
【出願人】（０００２１４８９２）三洋電機コンシューマエレクトロニクス株式会社 (1,582)
【Ｆターム（参考）】
[ Back to top ]