(57)【特許請求の範囲】
【請求項１】
指定された出発地から目的地までの経路を地図情報に基づき選定して、その経路を案内するための案内情報を生成する道案内生成方法において、
出発点から目的地に至る経路上の任意地点における案内の必要度を、経路の直進性と経路上での道路交差の複雑性および道路幅変化とから評価することにより前記必要度の評価値を算出し、
少なくとも前記評価値に基づき、前記出発点から目的地に至る道筋の迷いにくさの観点から最適な経路を選定し、
この選定された経路上で、前記評価値に基づき案内が必要と判定された地点についての案内情報を生成することを特徴とする道案内生成方法。
【請求項２】
前記複雑性の度合いが低い地点においては、前記評価値を算出する際、経路が直進であると判断する前記直進性の判断基準を緩めることを特徴する請求項１記載の道案内生成方法。
【請求項３】
前記経路が他の道路と交差し、前記経路の道路幅が前記他の道路の道路幅より太いときは、その地点の前記評価値に占める前記複雑性の影響度を小さくすることを特徴とする請求項１記載の道案内生成方法。
【請求項４】
前記経路が他の道路と交差し、前記経路の道路幅が前記他の道路の道路幅より太いときは、その地点の前記評価値に占める前記直進性の影響度を小さくすることを特徴とする請求項１記載の道案内生成方法。
【請求項５】
前記案内情報をユーザからの問い合わせや現在位置の報告などに応じて対話形式に提示し、この提示した案内情報に対してのユーザからの応答や前記問い合わせに基づいて、前記ユーザ対応に、前記評価値に占める前記直進性と前記複雑性と前記道路幅の変化のうちのいづれかの影響度を調節することを特徴とする請求項１記載の道案内生成方法。
【請求項６】
指定された出発地から目的地までの経路を地図情報に基づき選定して、その経路を案内するための案内情報を生成する道案内生成装置において、
出発点から目的地に至る経路上の任意地点における案内の必要度を、経路の直進性と経路上での道路交差の複雑性および道路幅変化とから評価することにより前記必要度の評価値を算出する算出手段と、
少なくとも前記評価値に基づき、前記出発点から目的地に至る道筋の迷いにくさの観点から最適な経路を選定する経路選定手段と、
前記選定された経路上で、前記評価値に基づき案内が必要と判定された地点についての案内情報を生成する案内生成手段と、
この案内生成手段で生成された案内情報を提示する提示手段と、
を具備したことを特徴とする道案内生成装置。
【請求項７】
前記複雑性の度合いが低い地点においては、前記評価値を算出する際、経路が直進であると判断する前記直進性の判断基準を緩めることを特徴する請求項６記載の道案内生成装置。
【請求項８】
前記経路が他の道路と交差し、前記経路の道路幅が前記他の道路の道路幅より太いときは、その地点の前記評価値に占める前記複雑性の影度を小さくすることを特徴とする請求項６記載の道案内生成装置。
【請求項９】
前記経路が他の道路と交差し、前記経路の道路幅が前記他の道路の道路幅より太いときは、その地点の前記評価値に占める前記直進性の影響度を小さくすることを特徴とする請求項６記載の道案内生成装置。
【請求項１０】
前記提示手段は、前記案内情報をユーザからの問い合わせや現在位置の報告などに応じて対話形式に提示し、
この提示した案内情報に対してのユーザからの応答や前記問い合わせに基づいて、前記ユーザ対応に、前記評価値に占める前記直進性と前記複雑性と前記道路幅の変化のうちのいづれかの影響度を調節することを特徴とする請求項６記載の道案内生成装置。
【請求項１１】
案内が必要と判定した際の主要原因となった経路の特徴の説明を前記案内情報に追加することを特徴とする請求項６記載の道案内生成装置。
【請求項１２】
前記最適な経路が選定できないとき、あるいは、前記案内が必要と判定された地点の数と、その各地点における道案内の際の目印となるランドマークの有無とを基に道案内が困難であると判定したときは、前記案内情報を生成する代わりに道案内をすることが困難である旨のメッセージを提示することを特徴とする請求項６記載の道案内生成装置。
【請求項１３】
前記案内が必要と判定された地点の前記案内情報の提示形態を該地点の前記評価値と該地点における道案内の際の目印となるランドマークの有無とに応じて決定することを特徴とする請求項６記載の道案内生成装置。
【請求項１４】
前記案内が必要と判定された地点の数と、その各地点における道案内の際の目印となるランドマークの有無とに基づき、前記案内情報を提示するのに適した前記案内情報の提示形態を判定して、ユーザに提案することを特徴とする請求項６記載の道案内生成装置。
【請求項１５】
クライアント端末からの要求に応じて、指定された出発地から目的地までの経路を地図情報に基づき選定して、その経路を案内するための案内情報を提供するサーバ装置において、
出発点から目的地に至る経路上の任意地点における案内の必要度を、経路の直進性と経路上での道路交差の複雑性および道路幅変化とから評価することにより前記必要度の評価値を算出する算出手段と、
少なくとも前記評価値に基づき、前記出発点から目的地に至る道筋の迷いにくさの観点から最適な経路を選定する経路選定手段と、
前記選定された経路上で、前記評価値に基づき案内が必要と判定された地点についての案内情報を生成する案内生成手段と、
を具備し、
この案内生成手段で生成された案内情報を要求元の前記クライアント端末に提供することを特徴とするサーバ装置。
【請求項１６】
前記複雑性の度合いが低い地点においては、前記評価値を算出する際、経路が直進であると判断する前記直進性の判断基準を緩めることを特徴する請求項１５記載のサーバ装置。
【請求項１７】
前記経路が他の道路と交差し、前記経路の道路幅が前記他の道路の道路幅より太いときは、その地点の前記評価値に占める前記複雑性の影響度を小さくすることを特徴とする請求項１５記載のサーバ装置。
【請求項１８】
前記経路が他の道路と交差し、前記経路の道路幅が前記他の道路の道路幅より太いときは、その地点の前記評価値に占める前記直進性の影響度を小さくすることを特徴とする請求項１５記載のサーバ装置。
【請求項１９】
前記案内情報をクライアント端末のユーザからの案内の問い合わせや現在位置の報告などに応じて対話形式に提供し、
この提供した案内情報に対してのユーザからの応答や前記問い合わせに基づいて、前記ユーザ対応に、前記評価値に占める前記直進性と前記複雑性と前記道路幅の変化のうちのいづれかの影響度を調節することを特徴とする請求項１５記載のサーバ装置。
【請求項２０】
案内が必要と判定した際の主要原因となった経路の特徴の説明を前記案内情報に追加することを特徴とする請求項１５記載のサーバ装置。
【請求項２１】
前記最適な経路が選定できないとき、あるいは、前記案内が必要と判定された地点の数と、その各地点における道案内の際の目印となるランドマークの有無とを基に道案内が困難であると判定したときは、前記案内情報を生成する代わりに道案内をすることが困難である旨のメッセージを提示することを特徴とする請求項１５記載のサーバ装置。
【請求項２２】
前記案内が必要と判定された地点の前記案内情報の提示形態を該地点の前記評価値と該地点における道案内の際の目印となるランドマークの有無とに応じて決定することを特徴とする請求項１５記載のサーバ装置。
【請求項２３】
前記案内が必要と判定された地点の数と、その各地点における道案内の際の目印となるランドマークの有無とに基づき、前記案内情報を提示するのに適した前記案内情報の提示形態を判定して、ユーザに提案することを特徴とする請求項１５記載のサーバ装置。
【請求項２４】
指定された出発地から目的地までの経路を案内するための案内情報の生成に用いる地図情報の編集を支援する地図情報編集支援装置において、
道路の直進性と道路交差の複雑性と道路幅変化とを評価することにより前記地図情報から抽出された案内の必要性の高い地点のうち、案内に必要なデータが不足している地点を要調査地点として抽出する抽出手段と、
この抽出手段で抽出された前記要調査地点のリストを出力する出力手段と、
を具備したことを特徴とする地図情報編集支援装置。
【請求項２５】
指定された出発地から目的地までの経路を地図情報に基づき選定して、その経路を案内するための案内情報を生成する処理をコンピュータに実行させるためのプログラムであって、
出発点から目的地に至る経路上の任意地点における案内の必要度を、経路の直進性と経路上での道路交差の複雑性および道路幅変化とから評価することにより前記必要度の評価値を算出するための処理と、
少なくとも前記評価値に基づき、前記出発点から目的地に至る道筋の迷いにくさの観点から最適な経路を選定するための処理と、
前記選定された経路上で、前記評価値に基づき案内が必要と判定された地点についての案内情報を生成するための処理と、
をコンピュータに実行させるためのプログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、地図情報に基づき道案内を生成するための道案内生成方法およびそれを用いた道案内装置に関する。
【０００２】
【従来の技術】
従来から道案内システムとして、カーナビゲーションが広く使われている。最近はＧＰＳ（Ｇｌｏｂａｌ  Ｐｏｓｉｔｉｏｎｉｎｇ  Ｓｙｓｔｅｍｓ）などの小型化により、携帯端末を使った歩行者用の道案内システムも登場してきた。これらのシステムは、ＧＰＳやＰＨＳなどを利用して現在位置を測定し、現在地付近の地図上にユーザがいる地点と進路を描画して、道案内をするシステムである。
【０００３】
さらに、道案内を携帯電話向けにサービスするインターネットサイトも登場し、携帯電話の小さな画面に表示できるように従来地図を使って行ってきた道案内を文章で行うことにより、携帯電話での道案内を可能にするシステムも登場してきた。
【０００４】
これらの道案内システムでは、経路の計算には最短経路を解くアルゴリズムとしてよく知られているＤｉｊｋｓｔｒａの方法をベースにしている。本手法は、ある評価基準にしたがって、コストを最小にする経路を計算する手法である。経路長は短く、道路幅は広くといった評価基準にしたがった評価式のコストを最小にする経路を求めるのがよく使われる。道案内の経路は、なるべく短く、迷いにくいことが重要であり、前記評価基準では「道路幅は広く」というのが迷いにくいを代表していると考えられる。
【０００５】
しかしながら、交差点形状や道路幅などが複雑でわかりにくいところであっても目印が十分にあれば迷いにくく、逆に単純な一本道であっても進路変更をする地点に適当な目印が無ければ迷いやすい。すなわち、案内が必要な所に案内に必要な情報がある経路の中でなるべく短い経路を計算することが本来重要である。しかしながら、従来のシステムの経路計算はこの点で不十分である。
【０００６】
一部の歩行者向け道案内携帯端末を含むカーナビのようなシステムでは、決まりきったベース地図を求めた経路沿いに順に表示していって単純に道案内を行う。最新のカーナビでは音声によるナビゲーションを行うものもあるが、進路変更を行う交差点付近に来たときに単純に進路方向を指示したり、決まった時間や距離で進路変更地点までの残りの距離を指示するだけである。これも、迷いにくくするという点で不十分であり、案内が必要な所では、きめ細かく案内を出し、そうでなければ案内を少なくするといった制御をすることがより望ましい。
【０００７】
他の道案内システムでは、略地図や案内文を示して道案内をするという手法が使われている。特に案内を自動生成している一部のシステムでは、ユーザの利用している端末の種類に応じて略地図のサイズを変更したり、画面サイズが小さすぎたり画像が表示できない端末向けにテキストで案内を表示したりといったように、自動生成のメリットを生かした道案内をしているものもある。
【０００８】
元々小さいサイズの略地図を生成するために目印をたくさん描画できなかったり、わかりやすくするには案内はシンプルである方がよいという点から、案内の中に表現する道路や目印などの情報はなるべく少なくする必要がある。
【０００９】
道案内という本来の目的からは、迷わないようにするために必要な最小限の情報を満たした道案内を作成するということが最適な道案内システムである。しかしながら、従来の道案内ではどこがどの程度迷いやすい場所かといった評価を行うことなく画一的な処理で案内を生成している。
【００１０】
【発明が解決しようとする課題】
本来、道案内システムは、迷う心配の少ないなるべく短い距離の経路を案内してあげることが重要である。しかしながら、従来のシステムでは、最短経路という点が重視され、迷いにくいという最も重要な点があまり考慮されていないという問題点があった。そのため、計算された経路自体も迷いにくい経路であるとは限らないし、生成される案内も迷いやすい所はどこであり、すなわち案内を十分に行うべき所はどこかということを考慮されない画一的な案内が生成されるだけであった。
【００１１】
そこで、本発明は上記問題点に鑑みなされたもので、ある地点で案内を必要と感じる度合は、主にその地点の景観の特徴によって決まることから、この景観特徴を用いて、迷いにくい経路の選定と、迷いにくい明確な道案内の生成が可能な道案内生成方法およびそれを用いた道案内生成装置、道案内情報を提供するサーバ装置、プログラムおよび、上記道案内生成方法の実施に使用する（迷いにくい経路の選択のためと、迷いにくい明確な道案内の生成のために用いられる）地図情報の編集を支援する地図情報編集支援装置を提供することを目的とする。
【００１２】
【課題を解決するための手段】
本発明は、指定された出発地から目的地までの経路を地図情報に基づき選定して、その経路を案内するための案内情報を生成するものであって、出発点から目的地に至る経路上の任意地点における案内の必要度を、経路の直進性と経路上での道路交差の複雑性および道路幅変化とから評価することにより前記必要度の評価値を算出し、少なくとも前記評価値に基づき、前記出発点から目的地に至る道筋の迷いにくさの観点から最適な経路を選定し、この選定された経路上で、前記評価値に基づき案内が必要と判定された地点についての案内情報を生成することにより、迷いにくいわかりやすい経路の選定と、迷いにくい明確な道案内の生成が可能となる。
【００１３】
また、案内必要度に基づき地図情報から抽出された案内の必要性の高い地点のうち、案内に必要なデータが不足している地点を要調査地点として抽出し、例えば、この抽出された要調査地点のリストを印刷することにより、調査員は、このリストに基づき効率よく実地調査が行え、地図情報のメンテナンス作業を効率化することができるとともに、このようにしてメンテナンスされた地図情報を用いることにより、経路選択の性能の向上と、生成される案内情報の質の向上が図れる。
【００１４】
【発明の実施の形態】
以下、本発明の実施形態について、図面を参照して説明する。
【００１５】
（第１の実施形態）
図１は、第１の実施形態に係る道案内生成装置の全体構成図を示したもので、経路選定部１，地図情報管理部２、案内必要度計算部３，案内生成部４，入力部、案内提示部６から構成されている。
【００１６】
なお、コンピュータに、上記各機能部の処理手順を記述したプログラムを実行させて、上記道案内生成装置として機能させることもできる。
【００１７】
図１において、地図情報管理部２は、道案内に使用する地図情報を記憶し、入力部５を介して、指定された地点を含む所定範囲の地図情報を検索する。
【００１８】
入力部５からは、キーボード、テンキー等の各種入力装置を用いてユーザからの指示が入力される。ユーザから出発地と目的地等が入力されると、これらを含む道案内生成要求を経路選定部１へ送られる。
【００１９】
経路選定部１では、道案内生成要求を受けると、地図情報管理部２に記憶されている地図情報を用いて、出発地から目的地に至る幾つかの経路を探索し、その中で迷いにくさに重点をおいた最適な経路を選定する。
【００２０】
案内必要度計算部３は、地図情報管理部２に記憶されている地図情報を用いて、経路計算部１で経路を選定する際に目安とする探索した経路のコストの計算に用いたりもする、経路上の要所要所における案内を必要とする度合を計算する。
【００２１】
案内生成部４は、地図情報管理部２に記憶されている地図情報を用いて、経路選定部１で選定された経路を案内するための案内情報を生成する。
【００２２】
この生成された案内情報は、案内情報出力部６により、所定の表示装置の画面上に表示されたり、音声にて出力したりするようになっている。
【００２３】
地図情報管理部２に蓄積されている地図情報は、道路ネットワークとランドマークのデータである。図２がその例であり、道路ネットワークは、道路上に適当に設けられた複数のノードの位置情報と、例えば、ノードｎ０からｎ１まで、ｎ１からｎ２までといった線分と線分どおしの接続関係を表した情報とから構成されている。１つ１つの線分には、接続関係、道路種別、道路名、道路幅、などの道路に関するデータが属性として付けられ、これら線分の属性情報も地図情報管理２に記憶されている。
【００２４】
以後の説明では、ｎ０、ｎ１…をノード、ノードとノードで表される線分を経路線分と言い、ｎ０とｎ１で表される経路線分を経路線分ｌａなどと表記する。
【００２５】
図２の中の「○」はランドマークの場所を表しており、名称を付加して、「○郵便局」などと以後表記する。ランドマークは建物や交差点などの案内の際に目印となる物であり、１つ１つに種別、名称、位置などの属性が付加され、これらランドマークの属性情報も地図情報管理部２に記憶されている。
【００２６】
ランドマークの属性情報や、道路の属性情報は、案内生成部４で案内情報を生成する際に用いられる。
【００２７】
経路選定部１は、出発地、目的地、時刻、移動手段などのユーザからの入力情報を含む道案内生成要求に応じて、出発地から目的地までの経路を選定し、選定した経路を案内生成部４に通知する。
【００２８】
図３に示すフローチャートを参照して、経路選定部１の概略動作について説明する。
【００２９】
（ステップＳ１）地図情報管理部２に蓄積されている道路ネットワークを用いて、出発地と目的地付近のノードを選択する。
【００３０】
（ステップＳ２）出発地のノード（以下、始点ノードと呼ぶ）から順に、その始点ノードに経路線分を介して接続するノードを探索して目的地のノード（以下、終点ノードと呼ぶ）に到る経路を探索する。
【００３１】
（ステップＳ３）探索した経路の中から最もコストの小さい経路を選択し、案内生成部４に出力する。
【００３２】
次に、ステップＳ２の経路の探索処理について、図４に示すフローチャートを参照して、より詳細に説明する。ここでは、例えば、図２の始点ノードｎ１から終点ノードｎ４への経路を探索する場合を例にとり説明する。
【００３３】
（ステップＳ１１）始点ノードｎ１を現ノードとし、現ノードｎ１に接続しているノードを道路ネットワーク情報から検索し、配列Ｓ［ｉ］に格納する。現ノードｎ０に対しては、（ｎ２，ｎ５）がＳ［ｉ］に格納される。ここで、変数ｉは、配列Ｓの各要素を識別するために用いる。
【００３４】
（ステップＳ１２）変数ｉを１つづつインクリメントしながら、配列Ｓに格納された各ノードについて、順に、ステップＳ１３〜ステップＳ１７の処理を繰り返し、配列Ｓの全てのノードに対して処理が終了したら、次に、最初のステップＳ１１へ戻り、配列Ｓの要素であった各ノードをそれぞれ現ノードに設定し、以下に説明するステップＳ１２以下の処理を同様に行う。
【００３５】
（ステップＳ１３）配列Ｓの要素であるノードＳ［ｉ］が、目的地付近のノード、すなわち、終点ノードであればステップＳ１５へ、そうでなければステップＳ１４へ進む。例えば、ここでは、ノードＳ［ｉ］がｎ２なので、ステップＳ１４へ進む。
【００３６】
（ステップＳ１４）ノードＳ［ｉ］の案内必要度を案内必要度計算部３に計算させ、ノードＳ［ｉ］の案内必要度Ｒｉとして記憶する。他にも現ノードからノードＳ［ｉ］までの距離Ｌｉや、ノードＳ［ｉ］地点での案内に必要な目印がある度合Ｅｉなども計算し、記憶する。
【００３７】
目印がある度合Ｅｉは、例えば、ノードＳ［ｉ］の一定範囲にあるランドマークのランドマーク適正度Ｐｊの総和を計算することにより求める。
【００３８】
Ｅｉ＝ΣＰｊ＋β
ランドマーク適正度は、目印としての適正度を表す値であり、「０」から「１」までのいずれかの値がランドマーク毎に付けられて地図情報管理部２に記憶されているものとする。βはデフォルト値である。
【００３９】
（ステップＳ１６）ノードＳ［ｉ］に進んだ場合の現ノードからノードＳ［ｉ］までの経路線分のコストＣｉを計算する。経路線分のコストＣｉは、例えば、Ｃｉ＝α×Ｌｉ＋Ｒｉ／Ｅｉ
の式で計算される。Ｌｉは現ノードとノードＳ［ｉ］との間の距離であり、この距離が長い程コストＣｉが高くなる。Ｒｉ／Ｅｉは、案内の困難度を表しており、目印が少なくて案内必要度Ｒｉが高い程コストＣｉが高くなる。αは距離の値をコスト計算に反映させる比率を調整するパラメータである。なお、上記コスト計算には、道路長Ｌｉの他に、道路幅も道路長Ｌｉと同様、コスト計算に反映させるようにしてもよい。
【００４０】
（ステップＳ１７）始点ノードからノードＳ［ｉ］までの経路のコストＣ（ｑ）を計算し、記憶する。この変数ｑは、経由するノードの違いにより異なる経路のそれぞれを識別するための識別子である。始点ノードからノードＳ［ｉ］に至るまでに経由した各経路線分のコストの総和が、経路のコストＣ（ｑ）である。
【００４１】
以下、ｑの値として、経由するノードの識別子（ｎ１、ｎ２、…）を羅列して表記する。
【００４２】
例えば、始点ノードｎ１からノードｎ２に至るまでの経路のコストＣ（ｎ１、ｎ２）が求まる。次に、ｉを１つインクリメントして、ステップＳ１２へ進み、以下、上記同様、ステップＳ１３〜ステップＳ１７の処理を行い、ノードｎ５について、始点ノードｎ１からノードｎ５に至るまでの経路のコストＣ（ｎ１，ｎ５）が求まる。
【００４３】
この段階で、配列Ｓの各要素に対する処理は終了したので、次に、最初のステップＳ１１へ戻り、例えば、ノードｎ２を現ノードに設定し、現ノードｎ２に接続しているノードｎ３を道路ネットワーク情報から検索し、配列Ｓ［ｉ］に格納する。すなわち、例えば、（ｎ３）がＳ［ｉ］に格納される。以下、上記同様にして、始点ノードｎ１からノードｎ２を経由してノードｎ３に至るまでの経路のコストＣ（ｎ１，ｎ２、ｎ３）が求まる。次に、最初のステップＳ１１へ戻り、ノードｎ５を現ノードに設定すると、（ｎ３）がＳ［ｉ］に格納され、始点ノードｎ１からノードｎ５を経由してノードｎ３に至るまでの経路のコストＣ（ｎ１、ｎ５，ｎ３）が求まる。
【００４４】
さらに、最初のステップＳ１１へ戻り、ノードｎ３を現ノードに設定すると、（ｎ４）がＳ［ｉ］に格納される。この場合、ノードＳ［ｉ］は終点ノードであるので、ステップＳ１３からステップＳ１５ヘ進む。
【００４５】
（ステップＳ１５）始点ノードからこのノードＳ［ｉ］までの経路を経路候補として、経路とコストを記憶し、ｉを１つインクリメントした後、ステップＳ１２に戻る。例えば、経路（ｎ１，ｎ２，ｎ３，ｎ４）、コストＣ（ｎ１，ｎ２，ｎ３，ｎ４）＝１０、経路（ｎ１，ｎ５，ｎ３，ｎ４）、コストＣ（ｎ１，ｎ５，ｎ３，ｎ４）＝１８、といった情報を記憶する。
【００４６】
このように、例えば、現ノードをノードｎ１に設定し、このノードｎ１に接続するノードｎ０，ｎ２，ｎ５までの経路のコストを計算し、さらにｎ０，ｎ２，ｎ５のそれぞれを現ノードに設定して、それぞれ、次の接続ノードに進んだときの経路のコストを同様に計算していけばよい。経路計算の終了は、経路候補が一定数求まったり、一定の時間を経過した時点で終了し、利用目的や運用コストに応じて調整する。
【００４７】
さて、図２の例では、（ｎ１，ｎ５，ｎ３，ｎ４）と（ｎ１，ｎ２，ｎ３，ｎ４）の２つの経路が経路候補として求まるが、ノードｎ５付近には目印が少ないため、Ｅｉが小さくなり、コストが大きくなる。したがって、図３のステップＳ３において、経路としてコストＣの値が最も小さい（ｎ１，ｎ２，ｎ３，ｎ４）が選択される。
【００４８】
次に、案内必要度計算部３の処理について説明する。案内必要度計算部３は、ある地点での案内を必要とする度合を計算する。ある地点で案内を必要と感じる度合は、主にその地点の景観の特徴によって決まる。景観特徴としては様々な要因があるが、ここでは、地図情報報管理部２に記憶されている地図情報から得られる情報で必要度を計算する手順を例として説明する。
【００４９】
人が案内を必要と感じる地点に影響を与えるような景観の特徴（指標）としては、例えば、経路の直進性、道路の交差の複雑性、道路幅の変化が上げられる。それぞれについて順に説明する。
【００５０】
図５は、直進性の評価方法について説明するための図である。経路線分ｌａから経路線分ｌｂへ進む時のｌａとｌｂの変化角度θにより、例えば
０≦θ＜２２．５°のとき直進性の評価値を「０」
２２．５°≦θ＜６７．５°のとき直進性の評価値を「０．３」
６７．５°≦θのとき直進性の評価値を「０．５」
と予め定める。この直進性の評価値をここでは、直進度と呼ぶ。直進度は、θの値が大きくなるにつれ案内を必要とする度合が大きくなることを表している。
【００５１】
図６は、複雑性の評価方法について説明するための図である。経路線分ｌａから経路線分ｌｂへ進む時に、ノードｎで他の経路線分ｌｃとｌｄが交差している場合には、それぞれと経路線分ｌｂとの間の交差角度θｂｅとθｂｄの角度により、例えば
０≦θ＜６７．５°のとき複雑性の評価値を「０．６」
６７．５°≦θ＜１１２．５°のとき複雑性の評価値を「０．３」
１１２．５°≦θ＜１８０°のとき複雑性の評価値を「０」
と予め定める。この複雑性の評価値をここでは、複雑度と呼ぶ。複雑度は、経路線分ｌｂと方向が近い交差道路があると進路の判別が難しくなり、案内を必要とする度合が大きくなることを表している。
【００５２】
図７は、道路幅の変化の評価方法を説明するための図である。矢印で示した経路（経路線分ｌａ、ｌｂ）と他の線分で表した交差する道路との太さの関係によって、３通りに分類しており、（ａ）図は、経路が交差する他の道路に比べて道路幅が太い場合であり、（ｂ）図は、経路線分ｌａと経路でない線分ｌｄの連続した太い道路から経路線分ｌｂの細い道路へ進む場合であり、（ｃ）図は、逆に細い経路線分ｌａの道路ａ太い経路線分ｌｂの道路へ進む場合であり、（ｄ）図は、太い道路の連続が無い、単純な太さの変化の場合である。それぞれのパターン毎に例えば、
（ａ）図の場合の道路幅の変化の評価値を「−０．３」
（ｂ）図の場合の道路幅の変化の評価値を「０．３」
（ｃ）図の場合の道路幅の変化の評価値を「０．２」
（ｄ）図の場合の道路幅の変化の評価値を「０．２」
と予め定める。この道路幅の変化の評価値をここでは、道路幅変化度と呼ぶ。道路幅変化度は、（ａ）図の場合には、案内を必要とする度合を下げ、（ｂ）（ｃ）（ｄ）図の場合では、案内を必要とする度合を上げることを表している。また、経路上の道路幅の変化が無い場合でも太い道路と交差する場合には案内を必要とする度合が上昇する。ここでは、これも道路幅変化度とし、このような場合は、例えば、「０．２」とする。
【００５３】
以上の３つの指標の評価値に基づいてノードでの案内必要度Ｒを、例えば、以下のように計算する。
【００５４】
Ｒ＝（直進度）＋Ａ×（複雑度）＋Ｂ×（道路幅変化度）
上記式において、ＡとＢは、それぞれ複雑度、道路幅変化度の比率を調整するパラメータである。このパラメータを調整することにより、個人差を吸収する例については第２の実施形態において説明する。
【００５５】
さらに、上記３つの指標にはいくつかの相関関係があり、例えば下記のような場合にはそれぞれの評価指標の影響の度合が変化する。
【００５６】
図８は、複雑度に応じて直進性の評価基準がゆるくなる例を示したものである。（ａ）図のように、複雑度が低い場合には、経路の変化角度θはより大きな角度まで案内を必要とする度合いが小さくなるので、例えば
０≦θ＜４５°で直進度を「０」
４５°≦θ＜６７．５°で直進度を「０．３」
といった具合に直進度の評価を緩くする。
【００５７】
図９は、経路上の２つの経路線分ｌａ、ｌｂの道路幅が、この２つの経路線分ｌａ、ｌｂが交差するノードｎにおいて交差する他の線分ｌｃの道路幅より太い場合に、複雑性の影響が小さくなる例を示したものである。太い道路の連続は、つながりのある道路と一般的に解釈されるため、道路幅に変化がない場合に比べ、複雑性の影響が緩和される。したがって、このような場合には、例えば複雑度の値を
０≦θ＜６７．５°のとき「０．２」
６７．５°≦θ＜１１２．５°のとき「０．１」
１１２．５°≦θ＜１８０°のとき「０」
と小さくする。
【００５８】
図１０は、経路上の２つの経路線分ｌａ、ｌｄの道路幅が、この２つの経路線分ｌａ、ｌｄが交差するノードｎにおいて交差する他の線分ｌｃ、ｌｂの道路幅より太い場合に、直進性の影響が小さくなる例である。すなわち、（ａ）図に示すように、経路線分ｌａから経路線分ｌｄへ進路変更をする時では、太い道路の連続をつながりのある道路と一般的に解釈されるため、（ａ）図方が（ｂ）図の場合より、案内を必要とする度合が小さくなる。したがって、（ａ）図の場合には、直進度を例えば
０≦θ＜２２．５°のとき「０」
２２．５°≦θ＜６７．５°のとき「０．２」
６７．５°≦θのとき「０．４」
と小さくする。
【００５９】
なお、以上説明したような、案内必要度の計算のための、上記３つの指標の評価方法は、多数の被験者からフィールドテストやアンケート調査により収集したデータを分析することにより決定するものである。上記は健常者が道路を歩行する際の基準の例であるが、同様の手法により分析を行い老人向け、障害者向け、自転車向けなどの場合に調整することが可能である。
【００６０】
次に、案内生成部４について説明する。案内生成部４は、経路選定部１で選定された経路を案内するための案内情報を生成するものである。図１１に示すフローチャートを参照して、道案内生成処理動作について説明する。
【００６１】
（ステップＳ２１）経路選定部１から送られた経路情報を配列Ｓに格納する。図２の例なら、（ｎ１，ｎ２，ｎ３，ｎ４）が格納される。ここで、変数ｉは、配列Ｓの各要素を識別するために用いる。
【００６２】
（ステップＳ２２）変数ｉを１つづつインクリメントしながら、配列Ｓに格納された経路上の各ノードについて、順に、ステップＳ２３〜ステップＳ２４の処理を繰り返し、配列Ｓの全てのノードに対して処理が終了したら、生成された案内情報を出力する。
【００６３】
（ステップＳ２３）配列Ｓの要素であるノードＳ［ｉ］の地点に対して案内が必要かを判定する。必要と判定された場合には案内を生成するためにステップＳ２４へ進み、必要ないと判定された場合には次のノードに処理を進める。
【００６４】
案内が必要が否かの判定は基本的にノードＳ［ｉ］の案内必要度で判定する。必要度が高ければ必要と判定する。案内必要度の値が、案内が必要であると判定する閾値として予め定められた値以上のときは、案内情報を生成するが、案内必要度の値が上記閾値に満たないときであっても、前後のノード間の距離が離れているとか、前のノードの案内があまり十分ではないなどの条件の時には必要と判定する。
【００６５】
（ステップＳ２４）現在処理中のノードＳ［ｉ］の地点についての案内情報を作成する。現在処理中のノードＳ［ｉ］の直前に案内情報を作成したノード（例えば、ノードＳ［ｉ−１］）を基点に、主に、ノードＳ［ｉ］に存在するランドマークを用いて説明する案内を生成する。
【００６６】
案内情報を出力するための案内情報出力部２の仕様や、ユーザの指定により略地図やテキスト、音声などの様々な出力形式に合わせて作成される。図１２〜図１５に案内情報出力部６から出力される案内情報の提示形態を示す。
【００６７】
図１２は略地図のみによる提示形態の例であり、図１３は文章のみによる提示形態の例であり、図１４は案内必要度の高いノード地点の略地図を順に表示するラリー図形式の提示形態の例である。
【００６８】
図１５は、案内必要度の値が非常に高い（案内が必要と判定する閾値よりもさらに高い所定値以上の）地点もしくは、案内の目印となるランドマークがないなどの理由により、文章で説明するのが困難な地点のみ略地図にて案内情報を提示し、それ以外の地点の案内情報は文章にて提示した文章＋略地図による提示形態の例である。
【００６９】
以上の処理により、道案内生成装置は、地図情報からある地点の迷いやすさ、すなわち案内を必要とする度合（案内必要度）を計算し、迷いにくい経路の選択と案内必要度に合わせた道案内を生成することができる。
【００７０】
次に、具体的な案内情報の提示例を示す。
【００７１】
図１６は、案内必要度の値に応じて案内が出される場所が変更されている例で、（ａ）図に示した地図情報に従って、ノードｎ０からノードｎ４へ行く場合に作成された経路（ｎ０、ｎ１、ｎ２、ｎ３、ｎ４）の案内情報と、ノードｎ４からノードｎ０へ行く場合に作成された経路（ｎ４、ｎ３、ｎ２、ｎ１、ｎ０）の案内情報を、それぞれ（ｂ）図と（ｃ）図に示している。ここで案内情報は、テキスト情報の場合を示している。
【００７２】
ノードｎ０からノードｎ４へ行く場合と、ノードｎ４からノードｎ０へ行く場合とでは、通過するノードは同一であるが、ノードｎ０からｎ４へ向かう場合、ノードｎ２の地点で複雑度が高いため、案内必要度が高くなり、図１６（ｂ）に示すように、「Ｂ銀行の所は直進します」という案内が追加されている。逆方向の場合には、複雑度は小さく、案内必要度は高くならないので、図１６（ｃ）に示すような案内はない。
【００７３】
従来の手法で（案内必要度を加味せずに）案内情報を生成した場合は、図１６（ｂ）に示すようなノードｎ２の地点の案内は生成されない。
【００７４】
図１７は、案内必要度Ｒの計算要素である（直進度）、（複雑度）、（道路幅変化度）の各項目に注目することにより、ステップＳ２４で生成する案内情報に案内必要度が高くなっている主要原因についての説明を追加するように案内情報を生成した例である。すなわち、図１７（ａ）と図１７（ｃ）に示す地図情報に従って、ともに、ノードｎ０からノードｎ４へ行く場合に生成された経路（ｎ０、ｎ１、ｎ２、ｎ３、ｎ４）の案内情報を図１７（ｂ）、図１７（ｄ）にそれぞれ示している。
【００７５】
図１７（ｃ）に示した地図情報では、ノードｎ２で経路より太い道路と交差しているので、ノードｎ２の地点は、交差する２本のそれぞれの道路幅により、ユーザは、どう進めばよいか不安になる可能性が高い迷いやすい地点であり、このノードｎ２の案内必要度は、図１７（ａ）に示した地図情報に従って計算されたノードｎ２の案内必要度と比較すると、道路幅変化度が影響を与えてより高い値となっている。すなわち、図１７（ｃ）によれば、図１７（ｃ）の地図情報に従ったノードｎ２の案内必要度には、道路幅変化度が大きいウエイトを示しているために高い値となっている。
【００７６】
従って、図１７（ｃ）の地図情報に従った案内情報では、ノードｎ２において、道路幅変化度の影響が大きいことから判断して、案内に、その説明を付加して、図１７（ｄ）に示すように、「太い道路と交差しますが、そのまま直進します」という案内情報が生成されている。
【００７７】
このように、案内情報生成部４では、各ノードの案内必要度の計算要素である、（直進度）、（複雑度）、（道路幅変化度）の値を参照して、案内情報を生成することもできる。
【００７８】
図１８は、経路上の各ノードにおける案内必要度Ｒから、案内情報の提示形態をユーザに提案する画面の例である。従来の手法による生成された案内情報は、多くは、その提示形態はユーザに指定させるようになっている。しかしながら、経路上に案内必要度Ｒが高すぎるノードが存在したり、複雑度が高すぎて文章でわかりやすく説明するのが困難であったり、といった場合にはファイルサイズは大きくなるが大きなサイズの略地図画像を使うべきであったり、文章と略地図を組み合わせて利用すべき場合がある。これに対して、従来からある道案内システムでは、ユーザは一度指定した提示形態による案内情報を確認して、それが役に立たないことを確認し、もう一度提示形態を指定しなおして最初から道案内要求をし直さなければならない。
【００７９】
本発明によれば、案内必要度Ｒを計算することができるので、求めた経路の各ノードの案内必要度Ｒを調べることにより、（例えば、案内生成部４で案内情報を生成する際に、）どの提示形態を使うべきかを予め判定し、生成された案内情報とともに、この提示形態の判定結果を案内情報出力部６に渡し、案内情報出力部６は、図１８（ａ）に示すような画面を表示して、ユーザに提示形態を提案することがきる。図１８（ａ）では、「２．案内文＋略地図」が反転表示することにより、案内文＋略地図の提示形態が適当であることをユーザに示している。
【００８０】
案内情報の提示形態の判定方法としては、例えば案内必要度Ｒが案内が必要であると判断する基準となる値を超えるノードの数と、案内の際の目印となるランドマークの有無（数であってもよい）に基づき判定する。例えば、案内の必要のあるノードの全てにランドマークが存在するときは、案内文のみ、案内の必要のあるノードのうちランドマークが存在しないノードが例えば、２つまでなら案内文＋略地図形式、それ以上なら詳細地図といったように判定する。さらに、案内の必要のあるノードの全てにランドマークが存在しても、案内の必要のあるノードの数が所定値以上のときは、案内文の量が多くなり、わかりにくいことから、案内案内文＋略地図形式で提示するようにしてもよい。
【００８１】
図１９は、上記案内情報の提示形態の判定において、道案内をすることが困難であると判定されたとき、すなわち、案内の必要のある（案内必要度Ｒがある一定値を超える）ノード数が多いとき（所定値以上のとき）、案内の必要のあるノードのうち、ランドマークが存在しないノードが例えば５箇所以上あるときなどは、道案内をすることが困難であり、出力する案内情報が役に立たないかもしれないことをユーザに通知するために、案内情報出力部６から出力される画面表示例である。
【００８２】
図１９に示す画面表示では、道案内が困難であることを通知し、利用を止めるかデータ量は大きくなるが詳細地図を参照するように指示をしている。
【００８３】
なお、経路選定部１で経路を選定する際、経路のコストＣが最も小さい経路を選定するが、その際、この選定された経路のコストＣが、予め定められた値以上のときも道案内が困難であると判定し、図１９に示すような表示を行うようにしてもよい。
【００８４】
以上説明したように、上記第１の実施形態によれば、出発点から目的地に至る経路上の任意地点における案内必要度を、その地点の景観の特徴としての３つの要素（経路の直進性と経路上での道路交差の複雑性および道路幅変化）から評価することにより算出し、この案内必要度や、距離、ランドマークの適性度に基づき、前記出発点から目的地に至る道筋の迷いにくさの観点から最適な経路を選定し、この選定された経路上で、案内必要度に基づき案内が必要と判定された地点についての案内情報を生成することにより、迷いにくい経路の選定と、迷いにくい明確な道案内の生成が可能となる。
【００８５】
また、従来、地図情報不足や案内に適当な目印の無い場所への道案内をそのまま出力してしまうことにより、ユーザに不満を感じさせてしまう程度をやわらげることが可能になる。
【００８６】
また、図１７（ｄ）に示すように、案内が必要と判定した際の主要原因となった経路の特徴の説明を前記案内情報に追加することにより、より明確な道案内が可能になる。
【００８７】
また、経路を選定する際、案内必要度に基づく迷いにくさの観点から最適な経路が選定できないときや、案内の必要な地点が所定数を越えて案内情報が膨大になるときなどは、役に立たない案内情報を提示して、ユーザに不満感を与えてしまうよりはむしろ、ユーザからの信頼を裏切らないためにも、案内情報を生成する代わりに、道案内をすることが困難である旨のメッセージを提示する事が望ましい。
【００８８】
また、図１５に示すように、案内が必要と判定された地点の案内必要度が所定値以上のときは、その地点の案内情報は略地図にて提示し、それ以外の地点の案内情報は文章にて提示するなど、案内が必要と判定された地点の案内情報の提示形態を該地点の案内必要度に応じて決定することにより、より明確な道案内が可能になる。
【００８９】
また、案内が必要と判定された地点の数に基づき、案内情報を提示するのに適した案内情報の提示形態を判定して、図１８に示したようにユーザに提案することにより、従来のように、例えば、道案内の要求を行って提示された文章のみの案内情報が、案内の説明が多すぎて文章のみでわかりにくいので、その提示形態を文章と略地図からなる提示形態に変更するためにだけ、再度、道案内の要求を行うといった無駄な操作を繰り返す必要がない。
【００９０】
（第２の実施形態）
スタンドアロンの道案内生成装置について説明したが、この場合に限らず、本発明は、図２０に示すように、図１に示した道案内生成装置の要部の構成をサーバ装置１００に持たせ、インターネット等の所定のネットワークを介して、このサーバ装置１００にアクセスしてきたクライアント端末に道案内情報を提供する道案内システムの場合も上記第１の実施形態と同様に適用できる。
【００９１】
この場合、図２０に示すように、サーバ装置１００は、経路選定部１と地図情報管理部２と案内必要度計算部３と案内生成部４と、さらに、クライアント端末１００との間で通信を行うための送受信部７とから構成されている。
【００９２】
なお、図２０において、図１と同一部分には同一符号を伏し、異なる部分についてのみ説明する。
【００９３】
クライアント端末１０１としては、例えば、携帯型の通信端末であり、携帯電話やＰＨＳなどであってもよい。
【００９４】
送受信部７は、例えば、ＨＴＴＰ（Ｈｙｐｅｒｔｅｘｔ  Ｔｒａｎｓｆｅｒ  Ｐｒｏｔｏｃｏｌ）などのプロトコルを用いて、クライアント端末１０１と通信を行う。
【００９５】
クライアント端末１０１が、例えば、インターネット上のサーバ装置１００に接続すると、サーバ装置１００からは、出発地、目的地などの入力画面が提供される。クライアント端末１０１で、ユーザが、この入力画面上に所定の事項を入力して道案内生成要求をサーバ装置２００へ送信すると、これを受けて、サーバ装置１００は、第１の実施形態と同様に動作して、案内情報を生成し、送受信部７を介して、クライアント端末１０１へ返す。
【００９６】
クライアント端末１０１では、サーバ装置１００から案内情報を受信して、これをディスプレイ上に表示したり、音声にて出力したりする。
【００９７】
（第３の実施形態）
図２１は、ユーザと対話形式で道案内を行う道案内システムの構成図を示したものである。なお、図２１において、図２０と同一部分には同一符号を付し、異なる部分についてのみ説明する。すなわち、図２６に示すサーバ装置１００の構成では、対話部８と案内必要度ユーザ適応部９が追加されている。
【００９８】
対話部８には、クライアント端末１０１から送信されてくる、ユーザからの問い合わせ（質問）や現在位置の報告などが入力され、それに応じて案内情報を出力する、ユーザとの道案内の対話を行う手段である。
【００９９】
ユーザは、サーバ装置１００へ送る質問などをクライアント端末から音声にて入力して、音声認識した結果をサーバ装置１００に送るようにしてもよいし、クライアント端末１０１からキー入力による入力であってもよい。
【０１００】
サーバ装置１００からクライアント端末１０１へ案内情報を出力する際には、音声、画像、テキストなどが用いられる。
【０１０１】
案内必要度ユーザ適応部９は、対話部８でのユーザとの道案内の対話の履歴を記憶するとともに、この履歴から、このユーザが案内必要度Ｒを計算するための式である
Ｒ＝（直進度）＋Ａ×（複雑度）＋Ｂ×（道路幅変化度）
のパラメータＡ，Ｂをユーザにより適した値に調整する手段である。
【０１０２】
その他の構成部は、第１の実施形態と同様である。
【０１０３】
図２２は、図１６（ａ）に示した地図情報に従って、ノードｎ４からノードｎ０へ至る経路（ｎ４、ｎ３、ｎ２、ｎ１、ｎ０）を案内する際のユーザとの対話の例である。図２２の左側がサーバ装置１００からの案内メッセージで、右側がユーザの発話を表している。この例では自然な文章での対話を示しているが、同様の内容の対話であれば、音声入力、キー入力、メニュー選択などの方法で入力した対話記録でも案内必要度ユーザ適応部９は処理可能である。
【０１０４】
この経路の場合、案内必要度Ｒの高い場所は、例えば、ノードｎ３とノードｎ１であるため、サーバ装置１００が自動的に生成した案内情報は、この２カ所についての案内である（ステップＳ１０１、ステップＳ１０３、ステップＳ１０５、ステップＳ１０９，ステップＳ１１１）。
【０１０５】
ノードｎ２では、ステップＳ１０６に示すように、ユーザ側からの質問「Ｂ銀行のところは直進でいいの？」が発生したので、これに応じる形で、ステップＳ１０７に示すように、「１００ｍ先のＡ交差点までそのまま直進してください」という案内メッセージが発せられている。
【０１０６】
したがって、図２２に示した対話から、案内必要度計算部３が計算した各ノードの案内必要度の中で、ノードｎ２での案内必要度がこのユーザに対しては低かったということが推定される。すなわち、図２２に示した対話から、案内必要度ユーザ適応部９は、案内必要度Ｒの計算過程で用いた各計算要素の値を参照して、ノードｎ２では、案内必要度Ｒの計算要素のうち、複雑度のみが案内必要度に影響を与えている（有効）ので、このユーザに対しては複雑度の案内必要度に与える影響力を強くする必要があると判断する。
【０１０７】
同様にして、道路幅変化度が有効な地点で同様の対話があった場合には、案内必要度ユーザ適応部９は、道路幅変化度の影響力を強くする必要があると判断する。
【０１０８】
逆に、サーバ装置１００では、案内必要度が高く案内が必要と判断し、案内情報を生成したノードであっても、ユーザが案内を必要無いと指示してもらうことにより、案内必要度ユーザ適応部９は、このユーザに対しては、そのノードの案内必要度の計算要素のうち、そのノードの案内必要度の値を高くした計算要素の影響力を弱くする必要があると判断する。
【０１０９】
ユーザが案内が不要と指示する方法としては、例えば、サーバ装置１００から提供された図２２に示したような案内メッセージをクライアント端末１０１で音声にて出力する場合には、案内メッセージを出力した後にクライアント端末１０１が所定の操作を行えばよい（例えば、所定のキーを入力するなど）。また、図２２に示したような案内メッセージをクライアント端末１０１でテキスト文にて出力する場合には、その案内メッセージに不要のときには「チェック」印を入力するためのチェックボックスを設けたり、上記同様、案内メッセージが表示された後に、クライアント端末１０１が所定の操作を行うようにしてもよい（例えば、所定のキーを入力するなど）。
【０１１０】
また、ユーザからの質問の中に、「どっちの道を行けばいいの？」とか、「太い道路と交差したけどどっちに行くの？」などの案内必要度の計算要素に関連する内容がある場合には、案内必要度ユーザ適応部９は、その計算要素の影響力を強くする必要があると判断する。
【０１１１】
以下、図２４に示すフローチャートを参照して、案内必要度ユーザ適応部９の処理動作について説明する。
【０１１２】
案内必要度ユーザ適応部９は、上記したように、対話の内容を解析して、あるいは、提示した案内情報に対するユーザからの応答（例えば、当該案内情報は不要である旨の指示も含む）に従って、案内必要度を見直すべきノードを検知する（ステップＳ２１）。そして、対話の内容や、案内必要度の計算に用いた各計算要素の値などから当該見直すべきノードの案内必要度の値に影響を与えた計算要素であって、影響力を調整すべきと判断した案内必要度の計算要素（調整すべき要素）、と影響力を強くすべきか弱くすべきかなどの情報を抽出する（ステップＳ２２）。
【０１１３】
図２３は、案内必要度ユーザ適応部９により、対話部８を通じて得られた対話などからの抽出情報の例である。対話部８を通じて得られる対話からリアルタイムに、あるいは、一時記憶した対話の記録から後に適当なタイミングで、見直すべきノードがあるか否かチェックする。見直すべきノードが検知される毎に、図２３に示すようなテーブル形式に対話から抽出された情報をログとして記録する（ステップＳ２３）。
【０１１４】
図２３において、「見直しノード」は案内必要度を見直すべきと判断されたノードの番号Ｑであり、ノードを識別するユニークなＩＤが表記される。「進入ノード」と「退出ノード」は、案内必要度を見直すべきと判断した時の経路で見直しノードの前後にあったノードのノード番号である。「調整すべき要素」は調整が必要と判断された案内必要度の計算要素であり、「強弱」は、調整すべき要素の影響を強くすべきか弱くすべきかであり、修正内容はどうなるように調整すべきかを表している。
【０１１５】
図２３のテーブルの最初の行には、例えば、図２２に示した対話に対応したログが記録されている。すなわち、ノードｎ２では複雑度の影響力が強くなるようにして、ノードｎ２が案内の必要なノードになるようにするというログが記録されている。
【０１１６】
案内適応度ユーザ適応部９は、図２３に示したテーブルを参照して、パラメータＡ、Ｂの値を計算するわけだが、その計算方法としては、例えば、上記テーブル上のログの多数決から各計算要素の影響力はぞれぞれ強くすべきか弱くすべきかを決定する。すなわち、複雑度を強くすべきログの数や、道路幅変化度を弱くすべきログの数などを集計し、その集計結果を基に、複雑度を強くするならＡを大きくし、道路幅変化度を弱くすべきならＢを小さくし、直進度を強くするならＡとＢを小さくする。そしてＡ，Ｂを微調整しながら、テーブルにログとして記録された地点の案内必要度を再計算し、修正内容に示された通りに結果が改善されたノードの数が一番多くなるＡ，Ｂを求める（ステップＳ２４）。
【０１１７】
サーバ装置１００は、ユーザ毎に上記パラメータＡ、Ｂの値をパラメータ格納部１０に格納する。サーバ装置１００は、クライアント端末１０１からのアクセス時に、当該クライアント端末１０１のユーザの識別情報を受け取るので、これを基に、各ユーザを識別し、案内必要度計算部３は、当該ユーザに対応したパラメータＡ、Ｂをユーザ毎パラメータ格納部１０から読みとって、これを基に前述の処理行う。また、案内必要度ユーザ適応部９では、上記したようにして、パラメータ格納部１０に格納されている各ユーザ対応のパラメータＡ、Ｂを更新していく。
【０１１８】
なお、図２２のステップＳ１０２やステップＳ１０８のように、ユーザからの現在位置の報告に応じて、ステップＳ１０３やステップＳ１０９で、報告された現位置に対応する案内情報を提示しているが、将来的には、ユーザの（クライアント端末の）現在位置は、ＧＰＳ（Ｇｌｏｂａｌ  Ｐｏｓｉｔｉｏｎｉｎｇ  Ｓｙｓｔｅｍｓ）、ＰＨＳ（Ｐｅｒｓｏｎａｌ  Ｈａｎｄｙ−ｐｈｏｎｅ  Ｓｙｓｔｅｍ）などにより自動的に取得されて、サーバ装置１００に通知されるであろう。この場合には、上記したように、対話形式で問い合わせなどに応じて案内情報を提供するとともに、そのようなクライアント端末の現在位置情報と地図情報管理部２に管理されている地図情報とを照らし合わせて、経路上のユーザ位置を特定した後、その位置に対応する案内情報を提供するようにしてもよい。
【０１１９】
以上説明したように、上記第３の実施形態によれば、対話部８は、案内情報をユーザからの問い合わせや現在位置の報告などに応じて対話形式に提示し、この提示した案内情報に対してのユーザからの応答や問い合わせに基づいて、案内必要度ユーザ適応部９は、各ユーザ対応に、案内必要度に占める直進性と複雑性と道路幅の変化の影響度を調節するパラメータＡ、Ｂを更新することにより、各ユーザに応じた、迷いにくい経路の選定と、迷いにくい明確な道案内の生成が可能となる。
【０１２０】
なお、上記第３の実施形態では、クライアント端末１０１からの要求に応じて、案内情報を提供するサーバ装置の構成として説明したが、この場合に限らず、ノート型パソコンのような携帯可能な情報通信端末装置などにも適用可能である。すなわち、例えば、図２１に示した構成のうち、経路選定部１，地図情報管理部２，案内必要度計算部３，案内生成部４，対話部８，案内必要度ユーザ適応部９の各機能部の処理手順を記述したプログラムを上記情報通信端末装置に実行させて、道案内生成装置として機能させることもできる。この場合は、当該情報通信端末装置のユーザのみのパラメータＡ、Ｂをパラメータ格納部１０に格納すればよい。
【０１２１】
（第４の実施形態）
第４の実施形態では、本発明の道案内生成方法の実施に使用する地図情報編集支援装置であって、迷いにくい経路の選択のためと、迷いにくい明確な道案内の生成に適した地図情報をメンテナンスするための地図情報編集支援装置２０１について説明する。
【０１２２】
従来、地図情報のメンテナンスは、定期的な地図情報の更新と、ユーザからのクレームを発端として局所的な修正が行われている。前者は主に地図作成会社によるしらみつぶしの調査により情報が更新されるため、非常に時間とコストがかかる。後者は、多くのユーザは間違いがあった時点で不満をかかえただけで止めてしまうため、多くの問題点は発見されずに繰り返し同じ間違いが発生してしまう。
【０１２３】
本発明の案内必要度を用いれば、多くの地点の中から、案内を行うのに情報が不足している部分を推定することができるので、現地調査における時間とコストの削減と、潜在しているデータの欠如を自主的に改善していくことが可能になる。
【０１２４】
図２５に示すように、地図情報編集支援装置２０１は、例えば、サーバ装置１００に接続して用いられる。
【０１２５】
地図情報編集支援装置２０１は、地図情報管理部２に蓄積された地図情報の中から、案内必要度の高い場所を調べてリストアップすることにより、道案内の性能を向上させるのに重要な地点を優先して地図情報の編集を支援するための手段である。
【０１２６】
図２６に示すように、地図情報編集支援装置２０１は、要調査地点抽出部２０２とリストデータ出力部２０３とから構成されている。
【０１２７】
以下、図２７に示すフローチャートを参照して、地図情報編集支援装置２０１の各構成部の処理動作について説明する。
【０１２８】
例えば、案内必要度計算部３は、過去に計算したノード毎の案内必要度や、その計算に用いた各計算要素の値などを履歴として記憶しているものとする。
【０１２９】
要調査地点抽出部２０２は、例えば、案内必要度計算部３から履歴として記憶されているノード毎の案内必要度を読み出すとともに、地図情報管理部２に蓄積された地図情報を順に調べ、まず、案内必要度がある値より高い場所をリストアップする。また、例えば、ユーザから、地図上の任意の範囲が指定されたとき、その指定範囲内に存在する全てのノードについて、案内必要度計算部３に案内必要度を計算させ、地図情報から案内必要度がある値より高い場所をリストアップするようにしてもよい（ステップＳ３１）。
【０１３０】
次に、案内必要度がある値より高い場所の調査内容を抽出する。調査内容は、例えば、地図情報管理部２に記憶されている地図情報を参照して、要調査場所と判断されたノード付近のランドマークの有無、数など、線分の属性として記憶されている道路に関するデータを参照して、これらの中から道案内に不足しているデータを抽出する（ステップＳ３２）。
【０１３１】
リストデータ出力部２０３は、案内必要度の値の高い場所（ノード）であって、道案内に必要なデータが不足している場所を要調査場所として、所定の地域毎にリストアップし、例えば、各地域毎に各要調査場所と調査すべき内容を明記したリストデータを出力する（ステップＳ３３）。例えば、所定の用紙に印刷したりする。このようなリストデータを印刷した調査用紙などを用いることで、調査員の調査効率を向上させ、地図情報のメンテナンス作業を効率化することができる。
【０１３２】
図２８は地図情報編集部１１からの出力の一例を示したものである。調査員が調査に行く時に利用するプリントアウトされた調査用紙もしくは携帯端末の画面表示の例である。図２８において、領域Ｇ１の「周辺地図」は、調査地域の地図であり、領域Ｇ２の「調査内容」は要調査場所とその調査内容についての記載であり、領域Ｇ３の「調査欄」は、「調査内容」として指定された調査の結果を記入する欄である。
【０１３３】
図２８では、ノードｎ５付近では、道案内の目印となるランドマークがないために、ランドマークの追加が調査内容として挙げられている。そこで、調査員は領域Ｇ１に表示されている周辺地図上に追加するランドマークの位置をそのＩＤとともに記入（あるいは入力）するとともに、領域Ｇ３に表示されている調査欄に当該ランドマークの名称、種別などの属性情報を記入（あるいは入力）すればよい。
【０１３４】
後に、地図情報管理部２に記憶されている地図情報に、上記調査用紙あるいは表示画面上に記入あるいは入力したデータを追加すればよい。
【０１３５】
また、要調査地点抽出部２０２は、案内必要度の計算に用いる必要な各計算要素毎にその値が所定値以上の高いノードについて、例えば、道路幅の調査、道路交差点の調査などを調査内容として抽出して、図２８に示したような、それらの調査のためのリストデータを出力するようにしてもよい。
【０１３６】
なお、図２９に示すように、上記した地図情報編集支援装置２０１の機能構成部（要調査地点抽出部２０２、リスト出力部２０３）と、少なくとも地図情報管理部２と案内必要度計算部３を有した地図情報編集支援装置２１０も実現可能である。
【０１３７】
図２９に示すような構成において、例えば、要調査地点抽出部２０２は、地図上の範囲が指定されたとき、その指定範囲内に存在する全てのノードについて、案内必要度計算部３に案内必要度を計算させ、地図情報から案内必要度がある値より高い場所をリストアップするようにしてもよい。
【０１３８】
さらに、上記した地図情報編集支援装置２０１の機能は、コンピュータに実行させることのできるプログラムとして構成することも可能である。
【０１３９】
以上説明したように、上記第４の実施形態によれば、案内必要度に基づき地図情報から抽出された案内の必要性の高い地点のうち、案内に必要なデータが不足している地点を要調査地点として抽出し、例えば、この抽出された要調査地点のリストを印刷することにより、調査員は、このリストに基づき効率よく実地調査が行え、地図情報のメンテナンス作業を効率化することができるとともに、このようにしてメンテナンスされた地図情報を図１や、図２０，図２１に示したような道案内生成装置や、サーバ装置の地図情報管理部２に登録して用いることにより、経路選択の性能の向上と、生成される案内情報の質の向上が図れる。
【０１４０】
また、従来、道案内の性能を向上させるために地図情報のどの部分を改善すればよいか自動的に解析することが困難であったが、案内必要度を用いることにより、地図情報を改善すべき個所の絞込みができるようになり、性能の向上と、地図情報のメンテナンスコストの削減を実現することができる。
【０１４１】
本発明の実施の形態に記載した本発明の手法は、コンピュータに実行させることのできるプログラムとして、磁気ディスク（フロッピーディスク、ハードディスクなど）、光ディスク（ＣＤ−ＲＯＭ、ＤＶＤなど）、半導体メモリなどの記録媒体に格納して頒布することもできる。
【０１４２】
なお、本発明は、上記実施形態に限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で種々に変形することが可能である。さらに、上記実施形態には種々の段階の発明は含まれており、開示される複数の構成用件における適宜な組み合わせにより、種々の発明が抽出され得る。例えば、実施形態に示される全構成要件から幾つかの構成要件が削除されても、発明が解決しようとする課題の欄で述べた課題（の少なくとも１つ）が解決でき、発明の効果の欄で述べられている効果（のなくとも１つ）が得られる場合には、この構成要件が削除された構成が発明として抽出され得る。
【０１４３】
【発明の効果】
以上説明したように、本発明によれば、迷いにくい経路の選定と、迷いにくい明確な道案内の生成が可能となる。
【図面の簡単な説明】
【図１】本発明の第１の実施形態に係る道案内生成装置の全体構成図。
【図２】地図情報について説明するための図。
【図３】経路選定処理を説明するためのフローチャート。
【図４】経路探索処理を説明するためのフローチャート。
【図５】経路の直進性の評価方法について説明するための図。
【図６】道路交差の複雑性の評価方法について説明するための図
【図７】道路幅変化の評価方法について説明するための図。
【図８】複雑度に応じて直進性の評価基準が緩くなる場合を説明するための図。
【図９】太い道路の連続により、案内必要度に占める複雑度の影響度が小さくなる場合を説明するための図。
【図１０】経路の道路幅が、この道路に交差する他の道路の幅より太いとき、案内必要度に占める直進性の影響度が小さくなる場合を説明するための図。
【図１１】道案内生成処理を説明するためのフローチャート。
【図１２】案内情報の提示形態の一例を示した図。
【図１３】案内情報の提示形態の他の例を示した図。
【図１４】案内情報の提示形態のさらに他の例を示した図。
【図１５】案内情報の提示形態のさらに他の例を示した図。
【図１６】案内必要度の値に応じて案内が出される場所が変更される場合を説明するための図。
【図１７】案内必要度が高くなっている主要原因についての説明を案内情報に追加する場合を説明するための図。
【図１８】案内が必要と判定された地点の案内情報の提示形態をユーザに提示する場合の提示画面の一例を示した図。
【図１９】道案内をすることが困難である旨のメッセージを提示する場合の提示画面の一例を示した図。
【図２０】本発明の第２の実施形態に係るサーバ装置の構成例を示した図。
【図２１】本発明の第３の実施形態に係るサーバ装置の構成例を示した図。
【図２２】ユーザとの対話により案内情報を提示する場合を説明するための図。
【図２３】案内必要度を見直すべきと判断されたノードのログデータの記憶例を示した図。
【図２４】案内必要度ユーザ適応処理を説明するためのフローチャート。
【図２５】本発明の第４の実施形態に係る地図情報編集支援装置の利用方法について説明するための図。
【図２６】地図情報編集支援装置の構成例を示した図。
【図２７】地図情報編集支援装置の処理動作を説明するためのフローチャート。
【図２８】地図情報編集支援装置からの出力データの一例を示した図。
【図２９】地図情報編集支援装置の他の構成例を示した図。
【符号の説明】
１…経路選定部
２…地図情報管理部
３…案内必要度計算部
４…案内生成部
５…入力部
６…案内情報出力部
７…送受信部
８…対話部
９…案内必要度ユーザ対応部
１０…パラメータ格納部
５０…道案内生成装置
１００…サーバ装置
１０１…クライアント端末
２０１、２１０…地図情報編集支援装置
【図１】
0003727854.tif 000002
【図２】
0003727854.tif 000003
【図３】
0003727854.tif 000004
【図４】
0003727854.tif 000005
【図５】
0003727854.tif 000006
【図６】
0003727854.tif 000007
【図７】
0003727854.tif 000008
【図８】
0003727854.tif 000009
【図９】
0003727854.tif 000010
【図１０】
0003727854.tif 000011
【図１１】
0003727854.tif 000012
【図１２】
0003727854.tif 000013
【図１３】
0003727854.tif 000014
【図１４】
0003727854.tif 000015
【図１５】
0003727854.tif 000016
【図１６】
0003727854.tif 000017
【図１７】
0003727854.tif 000018
【図１８】
0003727854.tif 000019
【図１９】
0003727854.tif 000020
【図２０】
0003727854.tif 000021
【図２１】
0003727854.tif 000022
【図２２】
0003727854.tif 000023
【図２３】
0003727854.tif 000024
【図２４】
0003727854.tif 000025
【図２５】
0003727854.tif 000026
【図２６】
0003727854.tif 000027
【図２７】
0003727854.tif 000028
【図２８】
0003727854.tif 000029
【図２９】
0003727854.tif 000030