(57)【要約】      （修正有）【課題】テキストを用いたルート案内を送信する際に、ユーザへの伝えたい情報量を減らすことなく、送信すべき情報量を減らす方法を提供する。【解決手段】ユーザによって入力されたルートの始点と終点を結ぶ最適ルートを求めるステップＳ１１と、メモリに保管されたルート履歴と最適ルートを比較して、ルート履歴中のルート部分によって置換可能な最適ルート中のルート部分を抽出するステップＳ１２と、抽出された最適ルート中のルート部分について、置換可能なルート履歴中のルート部分を特定するユーザにとって既知のテキスト表示を用いてルート案内を作成するステップＳ１３と、最適ルート中のルート履歴中のルート部分によって置換可能でないルート部分を特定する新たなテキスト表示を用いて、当該置換可能でないルート部分についてルート案内を作成するステップＳ１４と、を含む。【選択図】図３
2015224868.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータによってテキストを用いたルート案内を行うための方法であって、
（ａ）ユーザによって入力されたルートの始点と終点を結ぶ最適ルートを求めるステップと、
（ｂ）メモリに保管されたルート履歴と前記最適ルートを比較して、前記ルート履歴中のルート部分によって置換可能な前記最適ルート中のルート部分を抽出するステップと、
（ｃ）抽出された前記最適ルート中の前記ルート部分について、前記置換可能な前記ルート履歴中のルート部分を特定する前記ユーザにとって既知のテキスト表示を用いてルート案内を作成するステップと、
（ｄ）前記最適ルート中の前記ルート履歴中のルート部分によって置換可能でないルート部分を特定する新たなテキスト表示を用いて、当該置換可能でないルート部分についてルート案内を作成するステップと、を含む方法。
【請求項２】
前記最適ルート及び前記ルート履歴は、複数のノードと、隣り合う２つのノード間のエッジの各々とを含むグラフとして求められ、
前記ルート履歴中のルート部分及び前記最適ルート中のルート部分は、前記グラフの部分を成す前記ノード及び前記エッジを含む、請求項１に記載の方法。
【請求項３】
前記既知のテキスト表示及び前記新たなテキスト表示は、前記グラフの部分を成す少なくとも１つ以上の前記エッジ毎に作成される、請求項２に記載の方法。
【請求項４】
前記既知のテキスト表示及び前記新たなテキスト表示は、前記グラフの部分を成す連続する複数の前記エッジについての対応する１つのテキスト表示として作成される、請求項２に記載の方法。
【請求項５】
前記置換可能な前記最適ルート中のルート部分を抽出するステップ（ｂ）は、前記ルート履歴中の複数のルート部分の中から過去の抽出回数が多い順に対応するルート部分を抽出するステップを含む、請求項１に記載の方法。
【請求項６】
前記置換可能な前記最適ルート中のルート部分を抽出するステップ（ｂ）は、前記ルート履歴中のルート部分に重複する前記最適ルート中のルート部分を抽出するステップを含む、請求項１に記載の方法。
【請求項７】
前記置換可能な前記ルート履歴中のルート部分を特定する前記ユーザにとって既知のテキスト表示を用いてルート案内を作成するステップ（ｃ）は、前記ユーザが前記既知のテキスト表示によって特定されるルート部分を一義的に認識できるようにルート案内を作成するステップを含む、請求項１に記載の方法。
【請求項８】
前記既知のテキスト表示及び前記新たなテキスト表示を用いて作成された前記ルート案内を前記ユーザが操作可能な端末に送信するステップと、
前記端末の表示画面に受信された前記ルート案内を表示するステップと、をさらに含む請求項１に記載の方法。
【請求項９】
前記ルート案内はカーナビゲーション用のルート案内であり、前記ルートの始点と終点は走行ルートの出発地と目的地である、請求項８に記載の方法。
【請求項１０】
請求項１〜９のいずれか１項の各ステップを実行するためのコンピュータ・プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ルート案内に関し、より具体的には、コンピュータによってテキストを用いたルート案内を行うための方法に関する。
【背景技術】
【０００２】
アフリカなどの新興国では、携帯電話としていまだに通話機能を主とする、いわゆるフィーチャーフォン（Feature phone）あるいはベーシックフォン（Basic phone）と呼ばれる端末が主流で、ショートメッセージサービス（SMS）による情報伝達が活発に行われている。こうした環境下では、車両等のルート案内を行う際にも、情報伝達量の少ないSMSによるテキストベースのルート案内を想定する必要があり、一部ではそうしたルート案内が試験的に提供され始めている。
【０００３】
しかし、１通のSMSで送信可能な情報量が例えば１２０文字分程度しかなく、ルート全体を送信するために約１０通程度を必要とするため、これまでの試験結果では、参加者からのフィードバックとして、“提示経路が長すぎる”との不満の声が上がっているのが現状である。
【０００４】
その解決手段として、ルート案内の内容をさらに要約して送ることが検討されるが、そのルート案内自体が既に簡素化された文章であることから、既存の文章要約の技術をうまく（効果的に）適用することはできない。また、SMSの場合、ユーザ（受信側）で履歴照合ができないため、グラフ（データ構造）の保存のための一般的なキャッシュ技術を適用することはできない。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特表2004-518146（国際公開WO2002/065056）
【発明の概要】
【発明が解決しようとする課題】
【０００６】
したがって、本発明の目的は、テキストを用いたルート案内を送信する際に、ユーザへの伝えたい情報量を減らすことなく、送信すべき情報量を減らすことができる方法を提供することである。
【課題を解決するための手段】
【０００７】
本発明は、コンピュータによってテキストを用いたルート案内を行うための方法を提供する。その方法は、（ａ）ユーザによって入力されたルートの始点と終点を結ぶ最適ルートを求めるステップと、（ｂ）メモリに保管されたルート履歴と最適ルートを比較して、ルート履歴中のルート部分によって置換可能な最適ルート中のルート部分を抽出するステップと、（ｃ）抽出された最適ルート中のルート部分について、置換可能なルート履歴中のルート部分を特定するユーザにとって既知のテキスト表示を用いてルート案内を作成するステップと、（ｄ）最適ルート中のルート履歴中のルート部分によって置換可能でないルート部分を特定する新たなテキスト表示を用いて、当該置換可能でないルート部分についてルート案内を作成するステップと、を含む。
【０００８】
本発明の一態様では、最適ルート及びルート履歴は、複数のノードと、隣り合う２つのノード間のエッジの各々とを含むグラフとして求められる。また、ルート履歴中のルート部分及び最適ルート中のルート部分は、グラフの部分を成すノード及びエッジを含む。
【０００９】
本発明の一態様では、既知のテキスト表示及び新たなテキスト表示は、グラフの部分を成す少なくとも１つ以上のエッジ毎に作成され、あるいは、グラフの部分を成す連続する複数のエッジについての対応する１つのテキスト表示として作成される。
【００１０】
本発明の一態様では、置換可能な最適ルート中のルート部分を抽出するステップ（ｂ）は、ルート履歴中の複数のルート部分の中から過去の抽出回数が多い順に対応するルート部分を抽出するステップを含む。
【００１１】
本発明の一態様では、置換可能な最適ルート中のルート部分を抽出するステップ（ｂ）は、ルート履歴中のルート部分に重複する最適ルート中のルート部分を抽出するステップを含む。
【００１２】
本発明の一態様では、置換可能なルート履歴中のルート部分を特定するユーザにとって既知のテキスト表示を用いてルート案内を作成するステップ（ｃ）は、ユーザが既知のテキスト表示によって特定されるルート部分を一義的に認識できるようにルート案内を作成するステップを含む。
【００１３】
本発明の一態様では、既知のテキスト表示及び新たなテキスト表示を用いて作成されたルート案内をユーザが操作可能な端末に送信するステップと、端末の表示画面に受信されたルート案内を表示するステップと、をさらに含む。
【図面の簡単な説明】
【００１４】
【図１】本発明の方法が適用されるネットワークシステムの基本構成例を示すブロック図である。
【図２】本発明の方法を実行するコンピュータの構成を示す図である。
【図３】本発明の方法のフローを示す図である。
【図４】本発明の適用対象となる一実施例のルートを示す図である。
【図５】本発明の一実施例のルート案内を示す図である。
【発明を実施するための形態】
【００１５】
図面を参照しながら本発明の実施の形態を説明する。図１は、本発明の方法が適用されるネットワークシステムの基本構成例を示すブロック図である。ネットワークシステム１００は、本発明の方法を実行するサーバ１０と、ネットワーク（通信経路）３０を介してサーバ１０と通信可能に接続される端末２０を含む。端末２０には、フィーチャーフォン（Feature phone）あるいはベーシックフォン（Basic phone）と呼ばれる携帯電話やスマートフォンが含まれる。端末２０は、車両等の移動手段内に設置された端末であってもよい。端末２０は、本発明のルート案内を表示するための表示部（ディスプレイ）２０１を含む。なお、図１では、端末２０は３つしか記載されていないが、通信可能な任意の複数の端末を含むことができることは言うまでもない。
【００１６】
図２は、図１のサーバ１０の構成例を示すブロック図である。サーバ１０は、バス103を介して相互に接続された演算処理装置（CPU）101、記憶手段102、各種I/F104を含む。各種I/F104は、入力I/F、出力I/F、外部記憶I/F、外部通信I/F等を含む総称として用いられ、各I/Fが、それぞれ対応するキーボード、マウス等の入力手段105、CRT、LCD等の表示手段106、USB接続の半導体メモリやHDD等の外部記憶手段107等に接続する。記憶手段102は、RAM、ROM等の半導体メモリ、HDD等を含むことができる。本発明の方法は、サーバ１０が例えば記憶手段102、107に格納された所定のソフトウェア呼び出して実行することにより実施される。
【００１７】
図面を参照しながら本発明の方法のフローについて説明する。図３は、本発明の方法の基本的なフローを示す図である。図３のステップＳ１１において、ユーザによって入力されたルートの始点と終点を結ぶ最適ルートを求める。ルートの始点と終点の情報は、ユーザによって端末２０からサーバ１０へ送信される。サーバ１０は、その受信した情報を基に従来からある任意のルート探索のアルゴリズムを用いて最適ルートを算出する。
【００１８】
最適ルートを含む本発明で言うルートは、複数のノードと、隣り合う２つのノード間のエッジの各々とを含むグラフ（データ構造）として求められる。図４は、本発明の適用対象となる一実施例のルートを示すイメージ図である。図４では、いずれも車両４０が走行する、始点Ｓから終点Ｇへ至る実線のルートＡ及び破線のルートＢの２つが示されている。なお、両ルートが重なる区間（Ｓ−Ｐの間、Ｑ−Ｇの間）では破線が隠れてしまって実線のみが見えている。この図４を用いてイメージすると、複数のノードは白丸５０の点（位置）が該当し、ノード間のエッジは各ライン５５が該当する。ノードは例えば道路の交差点の位置として選択することができる。
【００１９】
次のステップＳ１２において、ステップＳ１１で得られた最適ルートと、メモリに保管されたルート履歴とを比較して、ルート履歴中のルート部分によって置換可能な最適ルート中のルート部分を抽出する。メモリに保管されたルート履歴には、例えばユーザが過去に少なくとも何度か利用しているルートとしてお気に入り登録しているルートが含まれる。ルート部分は、上述したグラフの部分を成すノード（例えば図４の５０）及びエッジ（例えば図４の５５）を含む。
【００２０】
置換可能な最適ルート中のルート部分を抽出は、例えば以下のように行うことができる。
（ａ）過去に通知したルートのうちユーザがお気に入り登録したルートを記憶しておき、これから通知するルートと比較することで、記憶ルートでカバーされている既知の部分グラフの集合αと既知でない部分グラフの集合βを抽出する。ただし、記憶ルートには優先順位があり、集合αに属する部分グラフは、カバーされている記憶ルートのうち、最も優先度が高い記憶ルートを示す付随情報を持つ。
（ｂ）上記（ａ）で抽出した集合αに属する連続した部分グラフのうち、同一の付随情報をもつ全てのエッジを１つのエッジとして丸める。丸められたエッジには最も優先度が高い記憶ルートを示す付随情報は伝播される。なお、この（ａ）及び（ｂ）を端末２０（受信）側のルート履歴で行うのではなく、サーバ１０（送信側）のルート履歴に基づいて処理するところが本発明の特徴である。
【００２１】
また、ステップＳ１２のルート部分の抽出は、ルート履歴中のルート部分に重複する最適ルート中のルート部分を抽出することを含むことができる。ここで重複とは、互いのルートが重なる（同一）であることを意味する。図４のルート例では、ルートＡとルートＢにおいて、Ｓ−Ｐの間及びＱ−Ｇの間の区間が重複したルート部分を含む場合に該当する。さらに、複数の置換可能な最適ルート中のルート部分がある場合は、例えば、ルート履歴中の複数のルート部分の中から過去の抽出回数が多い順に対応するルート部分を抽出することができる。
【００２２】
次のステップＳ１３において、抽出された最適ルート中のルート部分について、置換可能なルート履歴中のルート部分を特定するユーザにとって既知のテキスト表示を用いてルート案内を作成する。ここで、ユーザにとって既知のテキスト表示とは、ユーザがそのテキスト表示を見れば一義的に対応するルートを認識することができるテキスト表示を意味する。例えば、ルート１等のルート番号、ＡＡＡ通り等の通り名称のようなよく知られている名称、あるいはユーザが繰り返し走行して記憶が鮮明であってお気に入りに所定の名称で登録してあるルート及びその特定区間等が該当する。
【００２３】
既知のテキスト表示は、上述したグラフの部分を成す少なくとも１つ以上のエッジ毎に作成され、あるいはグラフの部分を成す連続する複数（２以上）のエッジについての対応する１つのテキスト表示として作成される。図４のルート例では、例えば隣接する２つのノード間の１つのエッジ５５に対応して、あるいは連続する２以上のエッジ５５に対応して作成される。
【００２４】
ここでの作成は、上述したステップＳ１３の上記（ｂ）の丸めたエッジを用いる場合は、付随する記憶ルートの情報をもとに、そのエッジに対するルート案内の文章を作成する。例えば、
「登録ルートＸに沿って、Ｙの交差点まで進んでください」、あるいは
「登録ルートＺに沿って、目的地Ｗまで進んでください」
のように作成される。
【００２５】
次のステップＳ１４において、最適ルート中のルート履歴中のルート部分によって置換可能でないルート部分を特定する新たなテキスト表示を用いて、当該置換可能でないルート部分についてルート案内を作成する。テキスト表示は、ステップＳ１３の場合と同様に、上述したグラフの部分を成す少なくとも１つ以上のエッジ毎に作成され、あるいはグラフの部分を成す連続する複数（２以上）のエッジについての対応する１つのテキスト表示として作成される。ここでの作成は、例えば、上述したステップＳ１３の上記（ａ）の抽出した既知でない部分グラフの集合βに属するエッジに対しては、既存システムで用いている従来手法で案内文章を作成する。
【００２６】
次のステップＳ１５において、ステップＳ１３及びＳ１４で作成したルート案内の文章を繋げて１つの最適ルート案内としてユーザの端末２０に送信する。その送信は、ネットワーク（通信経路）３０を介して、例えばSMSを利用して行う。次のステップＳ１６において、受信された最適ルート案内が端末２０の表示画面２０１に表示される。最適ルート案内は、同時に端末２０から音声にてユーザに伝えるようにしてもよい。
【実施例】
【００２７】
図５を参照しながら本発明の一実施例について説明する。図５は、本発明の一実施例のルート案内を示す図である。図５の（ａ）は、本発明の適用前のルート案内の文章であり、（ｂ）は本発明の適用後のルート案内の文章である。両者の比較から、（ａ）の２及び３の案内（文章）が（ｂ）の２‘の案内に簡略化され、さらに（ａ）の６〜９の案内が（ｂ）の５‘の案内に簡略化されていることがわかる。その簡略化によって、減少した文字数分だけ送信するデータ量を低減することができる。同時に、ユーザがより短時間にかつ的確に案内ルート（最適ルート）を把握することが可能になる。この図５（ｂ）に例示される簡略化は、具体的には、例えば下記に示すアルゴリズムによって実施される。
【００２８】
＜前提＞
（ａ）あるユーザAが登録しているルートの集合をSR={R1、R2、…、Ra} とする。Raは、例えば、システム（サーバ）がユーザAに提示したルートの中からユーザAがお気に入り登録した各ルートとする。また、各ルートはユーザが定めた優先順位によってソートされているものとする。
（ｂ）各ルートは案内順にSMSメッセージの基礎情報RaMbの集合Ra={RaM1、RaM2、…、RaMb} として表現される。RaMbには、SI（案内の始点となる交差点）、EI（案内の終点となる交差点）、D（始点と終点の距離）、EId（EI に関する記述）、EIa（EI でのアクション）、EIr（EIから出て行く先の道路名）が含まれる。
（ｃ）新しいルートNRもSMSメッセージの基礎情報NRMcの集合NR ={NRM1、NRM2、…、NRMc} として表現される。
【００２９】
＜アルゴリズム＞
（１）i=1、m=NRMi
（２）mから連続するかつ事前に決定した閾値 X を超えた中で最長のL個の連続する[NRMi、…、NRMi+L-1]に一致もしくは一部を含むRaの中から優先順位の一番高いRxを選択する。Rxの一致部分を[RxMy、…、RxMy+L-1]とする。該当するRaが存在しない場合、i=k-1ならば処理を終了する。それ以外なら、i=i +1、m=NRMiとして、（２）に戻る。
（３）i= 1かつL=kの場合、NR∈Raなので、以下のメッセージに置き換えて、下記の（６）に進む。
“Go to destination according to the route Ra“
【００３０】
（４）NRMiとRxMyを比較し、NRMiの中でRxMyでカバーされないルートがある場合には、NRMi(SI)からRxMy(SI)までのルートを作成する。ただし、全てRxMyでカバーされていればここでルートを作成しない。その後、Rxに従って移動するルートを生成する。また、NRMi+L-1とRxMy+L-1を比較し、NRMi+L-1 の中でRxMy+L-1でカバーされないルートがある場合には、RxMy+L-1(EI)から NRMi(EI)までのルートも合わせて生成する。ただし、全てRxM y+L-1でカバーされていればここでルートを作成しない。この場合、最終的に生成されるルートは以下の通りとなる。
“at RxMy(SI) after D’（=NRMi(SI)からRxMy(SI)までの距離）,  follow the route Rx“ 、または単に、
“follow the route Rx”
（“at RxMy+L-1(EI)、NRMi(EIa) onto NRMi(EIr)”）
【００３１】
（５）ただし、（４）において、i=k-L-1でかつNRM’i+L-1がRxM y+L-1でカバーされる場合には目的地に到着できるため、最後のルートを以下のメッセージに置き換える。
“Go to destination according to the route Rx“
（６）i = i + L
i＞k-xの場合、処理を終了する。それ以外の場合、m=NRMiとして、上記の（２）に戻る。
【００３２】
本発明の実施形態について、図を参照しながら説明をした。しかし、本発明はこれらの実施形態に限られるものではない。本発明はその趣旨を逸脱しない範囲で当業者の知識に基づき種々なる改良、修正、変形を加えた態様で実施できるものである。
【符号の説明】
【００３３】
１０  サーバ
２０  端末
３０  ネットワーク（通信経路）
４０  車両
５０  ノード
５５  エッジ
１００  ネットワークシステム
２０１  表示画面  
【図１】
2015224868.tif 000003
【図２】
2015224868.tif 000004
【図３】
2015224868.tif 000005
【図４】
2015224868.tif 000006
【図５】
2015224868.tif 000007