(57)【要約】【課題】目的地への案内の途中で目的地が変更される場合でも、変更後の目的地への到達時間の短縮を図ること。【解決手段】経路探索方法は、決定処理と、作成処理と、を有する。決定処理は、ユーザにより入力された目的地Ｄ１に基づいて、目的地Ｄ１に類似する代替目的地Ｄ２を決定する。作成処理は、ユーザの現在位置から目的地Ｄ１までの経路であって、代替目的地Ｄ２への経路を含む推奨経路Ｒ２を作成する。【選択図】図１
2020118652.tif 000002
【特許請求の範囲】
【請求項１】
ユーザにより入力された目的地に基づいて、前記目的地に類似する代替目的地を決定する決定処理と、
前記ユーザの現在位置から前記目的地までの経路であって、前記代替目的地への経路を含む推奨経路を作成する作成処理と、を有する、
経路探索方法。
【請求項２】
前記代替目的地の候補は、前記目的地の種類ごとに分類されている、
請求項１記載の経路探索方法。
【請求項３】
前記代替目的地は、前記ユーザの属性情報に基づいて決定される、
請求項１又は２に記載の経路探索方法。
【請求項４】
前記代替目的地は、前記ユーザとは異なる外部からの情報に基づいて決定される、
請求項１〜３のいずれか１項に記載の経路探索方法。
【請求項５】
前記作成処理は、前記代替目的地の候補が複数存在する場合、前記代替目的地の候補の密集度に応じて前記推奨経路を作成する、
請求項１〜４のいずれか１項に記載の経路探索方法。
【請求項６】
前記目的地に基づいて、前記目的地への仮経路を作成する仮経路作成処理と、
前記仮経路及び前記推奨経路を前記ユーザへ提示する提示処理と、を有する、
請求項１〜５のいずれか１項に記載の経路探索方法。
【請求項７】
前記代替目的地は、前記目的地に基づく前記目的地への仮経路の周囲にある前記代替目的地の候補から決定される、
請求項１〜６のいずれか１項に記載の経路探索方法。
【請求項８】
前記代替目的地は、前記目的地の周囲にある前記代替目的地の候補から決定される、
請求項１〜６のいずれか１項に記載の経路探索方法。
【請求項９】
前記目的地への経路を再度設定する際に、前記決定処理及び前記作成処理を実行する、
請求項１〜８のいずれか１項に記載の経路探索方法。
【請求項１０】
請求項１〜９のいずれか１項に記載の経路探索方法にて作成された前記推奨経路に基づいて、前記ユーザを前記目的地へ案内する案内処理を実行する、
ナビゲーション方法。
【請求項１１】
ユーザにより入力された目的地に基づいて、前記目的地に類似する代替目的地を決定する決定部と、
前記ユーザの現在位置から前記目的地までの経路であって、前記代替目的地への経路を含む推奨経路を作成する作成部と、
前記作成部で作成された前記推奨経路に基づいて、前記ユーザを前記目的地へ案内する案内部と、を備える、
ナビゲーションシステム。
【請求項１２】
請求項１１記載のナビゲーションシステムと、
前記ナビゲーションシステムを有する本体と、を備える、
移動体。
【請求項１３】
１以上のプロセッサに、
ユーザにより入力された目的地に基づいて、前記目的地に類似する代替目的地を決定する決定処理と、
前記ユーザの現在位置から前記目的地までの経路であって、前記代替目的地への経路を含む推奨経路を作成する作成処理と、を実行させるための
プログラム。
【請求項１４】
請求項１〜９のいずれか１項に記載の経路探索方法の前記決定処理及び前記作成処理を実行する分類器を機械学習させる方法であって、
前記目的地を入力として前記分類器が出力する前記推奨経路を、前記ユーザが選択したか否かを教師データとして、前記分類器を機械学習させる、
経路探索用学習方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本開示は、一般に経路探索方法、ナビゲーション方法、ナビゲーションシステム、移動体、プログラム、及び経路探索用学習方法に関する。より詳細には、本開示は、ユーザが目的地へ達するまでの経路を探索する経路探索方法、ナビゲーション方法、ナビゲーションシステム、移動体、プログラム、及び経路探索用学習方法に関する。
【背景技術】
【０００２】
特許文献１には、車が向かう目的地を案内及び提案する目的地提案システムが開示されている。この目的地提案システムは、ユーザにより指定された第１の目的地に向かって出発した後に、第１の目的地に到着する到着時刻が到着予定時刻よりも遅いと判断された場合に、他の目的地を検索する。そして、検索された他の目的地を、車両に搭載された表示部に表示する。他の目的地は、第１の目的地と同一目的を行うことができ、第１の目的地の到着時刻より早く到着することができる目的地である。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特許第４０３６０２８号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
本開示は、目的地への案内の途中で目的地が変更される場合でも、変更後の目的地への到達時間の短縮を図ることのできる経路探索方法、ナビゲーション方法、ナビゲーションシステム、移動体、プログラム、及び経路探索用学習方法を提供することを目的とする。
【課題を解決するための手段】
【０００５】
本開示の一態様に係る経路探索方法は、決定処理と、作成処理と、を有する。前記決定処理は、ユーザにより入力された目的地に基づいて、前記目的地に類似する代替目的地を決定する。前記作成処理は、前記ユーザの現在位置から前記目的地までの経路であって、前記代替目的地への経路を含む推奨経路を作成する。
【０００６】
本開示の一態様に係るナビゲーション方法は、上記の経路探索方法にて作成された前記推奨経路に基づいて、前記ユーザを前記目的地へ案内する案内処理を実行する。
【０００７】
本開示の一態様に係るナビゲーションシステムは、決定部と、作成部と、案内部と、を備える。前記決定部は、前記ユーザにより入力された目的地に基づいて、前記目的地に類似する代替目的地を決定する。前記作成部は、前記ユーザの現在位置から前記目的地までの経路であって、前記代替目的地への経路を含む推奨経路を作成する。前記案内部は、前記作成部で作成された前記推奨経路に基づいて、前記ユーザを前記目的地へ案内する。
【０００８】
本開示の一態様に係る移動体は、上記のナビゲーションシステムと、前記ナビゲーションシステムを有する本体と、を備える。
【０００９】
本開示の一態様に係るプログラムは、１以上のプロセッサに、決定処理と、作成処理と、を実行させるためのプログラムである。前記決定処理は、ユーザにより入力された目的地に基づいて、前記目的地に類似する代替目的地を決定する。前記作成処理は、前記ユーザの現在位置から前記目的地までの経路であって、前記代替目的地への経路を含む推奨経路を作成する。
【００１０】
本開示の一態様に係る経路探索用学習方法は、上記の経路探索方法の前記決定処理及び前記作成処理を実行する分類器を機械学習させる方法である。前記経路探索用学習方法は、前記目的地を入力として前記分類器が出力する前記推奨経路を、前記ユーザが選択したか否かを教師データとして、前記分類器を機械学習させる。
【発明の効果】
【００１１】
本開示は、目的地への案内の途中で目的地が変更される場合でも、変更後の目的地への到達時間の短縮を図ることができる、という利点がある。
【図面の簡単な説明】
【００１２】
【図１】図１は、本開示の一実施形態に係る経路探索方法で作成された推奨経路の概要図である。
【図２】図２は、同上の経路探索方法を採用するナビゲーションシステムの概要を示すブロック図である。
【図３】図３は、同上の経路探索方法の一例を示すフローチャートである。
【図４】図４は、同上のナビゲーションシステムの動作の一例を示すフローチャートである。
【図５】図５は、同上の経路探索方法で作成された推奨経路でユーザを案内する場合の概要図である。
【図６】図６は、比較例の経路探索方法で作成された経路でユーザを案内する場合の概要図である。
【図７】図７は、本開示の一実施形態の第１変形例に係る経路探索方法で作成された推奨経路の概要図である。
【図８】図８は、本開示の一実施形態の第３変形例に係る経路探索方法で作成された推奨経路の概要図である。
【発明を実施するための形態】
【００１３】
（１）概要
本実施形態の経路探索方法は、図１に示すように、例えば車両（移動体）７に搭乗するユーザがナビゲーションシステム１００（図２参照）を用いて目的地Ｄ１を入力した場合に、ユーザの現在位置から目的地Ｄ１までの経路を探索する際に用いられる。本開示でいう「ユーザ」は、経路探索方法の利用者である。本実施形態では、ユーザは、一例として車両７の運転者である。もちろん、ユーザは、車両７の運転者に限らず、運転者以外の搭乗者であってもよい。また、ユーザは、１人に限らず、複数人であってもよい。この場合、複数人のユーザの総意により、目的地Ｄ１が入力されることになる。
【００１４】
本開示でいう「目的地の入力」は、ユーザが目的地Ｄ１を指定して入力する態様に限らず、ユーザの要望を受けてナビゲーションシステム１００がユーザの目的を達成し得る目的地Ｄ１を認識して入力する態様を含み得る。つまり、「目的地の入力」は、ユーザが直接的に目的地Ｄ１を入力する態様に限らず、ユーザが間接的に目的地Ｄ１を入力する態様を含み得る。一例として、ユーザが「〇〇公園」を目的地Ｄ１として入力した場合、「〇〇公園」が目的地Ｄ１となる。一方、ユーザが「△△駅の周辺で食事をしたい」と入力した場合、△△駅の周辺にある１以上の飲食店のうちの１つが目的地Ｄ１となる。
【００１５】
経路探索方法は、決定処理と、作成処理と、を有する。本実施形態では、経路探索方法は、ナビゲーションシステム１００にて実行される。ナビゲーションシステム１００は、図２に示すように、決定部１２と、作成部１３と、を備えている。
【００１６】
決定処理（決定部１２）は、ユーザにより入力された目的地Ｄ１に基づいて、目的地Ｄ１に類似する代替目的地Ｄ２を決定する。本開示でいう「代替目的地」は、ユーザが目的地Ｄ１にて目的を達成することが困難な場合に、ユーザが目的地Ｄ１の代わりに選択し得るスポットである。ユーザが目的地Ｄ１にて目的を達成することが困難な場合とは、例えばユーザが予定通りに目的地Ｄ１に到着することが困難な場合、又はユーザが予定時刻までに目的地Ｄ１にて目的を達成することが困難な場合等を含み得る。
【００１７】
代替目的地Ｄ２は、目的地Ｄ１と同じ種類のスポット、又は目的地Ｄ１と同様にユーザの目的を達成し得るスポットを含み得る。一例として、目的地Ｄ１がスキー場であれば、代替目的地Ｄ２は、このスキー場の近隣にある他のスキー場となり得る。また、一例として、目的地Ｄ１が屋外のレジャー施設であって、ユーザの目的がレジャー施設にて余暇を過ごすことであれば、代替目的地Ｄ２は、このレジャー施設の近隣にある他の屋外のレジャー施設、又は屋内のレジャー施設となり得る。その他、目的地Ｄ１が海水浴場であって、ユーザの目的が泳ぐことであれば、代替目的地Ｄ２は、海水浴場、遊泳が許可されている川、又はプール等となり得る。
【００１８】
作成処理（作成部１３）は、ユーザの現在位置から目的地Ｄ１までの経路であって、代替目的地Ｄ２への経路を含む推奨経路Ｒ２を作成する。つまり、推奨経路Ｒ２は、基本的にはユーザの現在位置から目的地Ｄ１までの経路であるが、ユーザが目的地Ｄ１へ向かう途中において目的地Ｄ１が代替目的地Ｄ２に変更される場合を考慮した、代替目的地Ｄ２にも向かいやすい経路である。一例として、推奨経路Ｒ２は、ユーザの現在位置から代替目的地Ｄ２に到達するまでに要する時間（到達時間）が最も短くなる経路の一部を含み得る。
【００１９】
上述のように、本実施形態では、ユーザが目的地Ｄ１を入力した時点で、目的地Ｄ１への案内の途中で目的地Ｄ１が変更されることを考慮して、推奨経路Ｒ２を作成する。このため、本実施形態では、推奨経路Ｒ２にて目的地Ｄ１への案内を行えば、目的地Ｄ１への案内の途中で目的地Ｄ１が変更される場合でも、変更後の目的地（代替目的地Ｄ２）への到達時間の短縮を図ることができる、という利点がある。
【００２０】
（２）詳細
以下、本実施形態の経路探索方法を実行するナビゲーションシステム１００について図２を参照して詳しく説明する。本実施形態では、ナビゲーションシステム１００は、車両（移動体）７の本体７０に搭載されている、いわゆるカーナビゲーションシステムである。具体的には、ナビゲーションシステム１００は、車両７の本体７０のダッシュボードに取り付けられている。言い換えれば、移動体７は、ナビゲーションシステム１００と、ナビゲーションシステム１００を有する本体７０と、を備えている。以下、特に断りのない限り、「移動体」は「車両」という。
【００２１】
ナビゲーションシステム１００は、図２に示すように、処理部１と、入力部２と、出力部３と、記憶部４と、を備えている。また、処理部１は、認識部１１と、決定部１２と、作成部１３と、仮経路作成部１４と、案内部１５と、を有している。また、ナビゲーションシステム１００は、位置検出部５と、通信部６と、を更に備えている。本実施形態では、処理部１、入力部２、出力部３、記憶部４、位置検出部５、及び通信部６は、いずれもナビゲーションシステム１００の構成要素に含まれることとする。なお、処理部１の決定部１２、作成部１３、及び案内部１５以外の構成は、ナビゲーションシステム１００の構成要素に含まれていなくてもよい。
【００２２】
入力部２は、ユーザによる目的地Ｄ１の入力等、ユーザによる経路案内に関する操作の入力を受け付ける入力インタフェースである。本実施形態では、入力部２は、物理ボタンを含むタッチパネル型のディスプレイ２１と、ユーザの音声による入力を受け付けるマイクロホン２２と、を有している。入力部２は、ユーザによる入力を受け付けると、入力に応じた情報を処理部１に与える。
【００２３】
出力部３は、処理部１にて処理された情報を画像又は音声により出力する。一例として、出力部３は、車両７の現在位置を含む地図情報を画像により出力する。また、一例として、出力部３は、車両７の現在位置から目的地Ｄ１までの経路の一部又は全部を含む案内情報等を画像又は音声により出力する。本実施形態では、出力部３は、ディスプレイ３１と、スピーカ３２と、を有している。そして、本実施形態では、出力部３のディスプレイ３１は、入力部２のディスプレイ２１と共用されている。
【００２４】
記憶部４は、例えばＣＤ（Compact Disk）−ＲＯＭ（Read-Only Memory）、ＤＶＤ（Digital Versatile Disk）−ＲＯＭ、ＨＤＤ（Hard Disk Drive）、又はメモリカード等の非一時的な記録媒体で構成される。なお、記憶部４は、例えばＥＥＰＲＯＭ（Electrically Erasable Programmable Read-Only Memory）等の電気的に書換え可能な不揮発性メモリ、及びＲＡＭ（Random Access Memory）等の揮発性メモリ等で構成されていてもよい。
【００２５】
記憶部４は、車両７が移動する移動経路、及び車両７が移動する地域の地図情報等を記憶する。地図情報には、例えば道路の名称及び交差点の名称等、車両７（ユーザ）を目的地Ｄ１まで案内する際に用いられる情報が含まれる。また、地図情報には、地図上に存在する施設及び場所に関する情報等、目的地Ｄ１を入力する際、及び代替目的地Ｄ２を決定する際に用いられる情報が含まれ得る。一例として、地図情報には、施設に関する情報として、飲食店の位置、及び営業時間（定休日を含む）等の情報が含まれる。また、一例として、地図情報には、場所に関する情報として、観光地を含む名所の位置、及び営業時間等の情報が含まれ得る。
【００２６】
位置検出部５は、車両７の本体７０に備えられており、車両７の状態又は車両７の周囲の状態を検知する。位置検出部５は、例えば、車両７の現在位置、速度、及び向き等を含む車両７の状態を検出する複数種類の検出器を含む。複数種類の検出器としては、測位センサ、加速度センサ、及び角速度センサ等を含む。測位センサは、例えば、全地球航法衛星システム（ＧＮＳＳ：Global Navigation Satellite System）を利用して車両７の現在位置に関する情報を取得する。加速度センサは、車両７の本体７０に加わる加速度を検出する。角速度センサは、車両７の本体７０に加わる角速度を検出するジャイロセンサ等を含む。位置検出部５の検出結果は、処理部１に与えられる。
【００２７】
通信部６は、車両７の外部のサーバ等から発信される情報を受信可能なアンテナを有している。本実施形態では、通信部６は、アンテナを介してＶＩＣＳ（Vehicle Information and Communication System：道路交通情報通信システム）（登録商標）から発信される道路交通情報を取得する。道路交通情報には、例えば渋滞情報及び交通規制情報等の道路の状況に関する情報、並びに駐車場が満車であるか否かといった駐車場に関する情報等が含まれ得る。その他、通信部６は、飲食店等の施設の状況に関する情報（例えば、レストランの空席に関する情報）を、アンテナを介して車両７の外部のサーバから受信する構成を含んでいてもよい。通信部６で受信した情報は、処理部１に与えられる。
【００２８】
処理部１は、ハードウェアとしての１以上のプロセッサ及びメモリを主構成とするコンピュータシステムである。この処理部１では、メモリに記録されたプログラムを１以上のプロセッサで実行することによって、種々の機能が実現される。プログラムは、処理部１のメモリに予め記録されてもよく、電気通信回線を通じて提供されてもよく、コンピュータシステムで読み取り可能な光学ディスク、ハードディスクドライブ等の非一時的記録媒体に記録されて提供されてもよい。
【００２９】
処理部１は、既に述べたように、認識部１１と、決定部１２と、作成部１３と、仮経路作成部１４と、案内部１５と、を有している。具体的には、処理部１は、１以上のプロセッサにより所定のプログラムを実行することで、認識部１１、決定部１２、作成部１３、仮経路作成部１４、及び案内部１５の各々の機能を実現する。
【００３０】
認識部１１は、入力部２から与えられる情報に基づいて、ユーザの目的地Ｄ１を認識する。例えば、入力部２にて、ユーザがディスプレイ２１又は物理ボタンを操作することで「□□旅館」を目的地Ｄ１として指定する入力を行ったと仮定する。この場合、認識部１１は、「□□旅館」がユーザの入力する目的地Ｄ１であると認識する。また、例えば、入力部２にて、ユーザがマイクロホン２２に向かって「××駅の周辺で駐車したい」と声を発したと仮定する。この場合、認識部１１は、ユーザの音声情報に対して適宜の音声解析処理を実行することにより、音声情報に含まれる目的地Ｄ１を認識する。ここでは、認識部１１は、「××駅」の周辺にある１以上の駐車場のうちの１つを目的地Ｄ１として認識する。ここで、目的地Ｄ１の候補が複数ある場合には、認識部１１は、複数の目的地Ｄ１の候補から任意の１つの候補を目的地Ｄ１として認識してもよいし、例えばユーザがあらかじめ設定した条件に従って、目的地Ｄ１を認識してもよい。
【００３１】
決定部１２は、認識部１１により認識された目的地Ｄ１（つまり、ユーザにより入力された目的地Ｄ１）に基づいて、目的地Ｄ１に類似する代替目的地Ｄ２を決定する決定処理を実行する。ここで、ユーザが目的を達成することが困難であると判断した場合に、ユーザが目的地Ｄ１の代わりに選択し得るスポットは、１つ以上である。したがって、決定部１２により決定される代替目的地Ｄ２は、１つであってもよいし複数であってもよい。もちろん、決定部１２は、代替目的地Ｄ２の候補Ｄ２０（図７参照）が複数ある場合に、例えばユーザがあらかじめ設定した条件に従って、複数の代替目的地Ｄ２の候補Ｄ２０から１つの代替目的地Ｄ２を決定してもよい。
【００３２】
決定部１２は、認識部１１により認識された目的地Ｄ１に基づいて、目的地Ｄ１の種類に紐付けられた１以上の代替目的地Ｄ２の候補Ｄ２０を記憶部４から検索する。つまり、本実施形態では、代替目的地Ｄ２の候補Ｄ２０は、目的地Ｄ１の種類ごとに分類されている。そして、決定部１２は、例えばユーザがあらかじめ設定した条件に従って、１以上の代替目的地Ｄ２の候補Ｄ２０から１以上の代替目的地Ｄ２を決定する。
【００３３】
一例として、代替目的地Ｄ２は、ユーザが入力した目的地Ｄ１の周囲にある代替目的地Ｄ２の候補Ｄ２０から決定される。また、一例として、代替目的地Ｄ２は、ユーザが入力した目的地Ｄ１に基づく目的地Ｄ１への仮経路Ｒ１の周囲にある代替目的地Ｄ２の候補Ｄ２０から決定される。仮経路Ｒ１は、後述する仮経路作成部１４にて作成される。決定部１２が上記のいずれの態様で代替目的地Ｄ２を決定するかは、ユーザがあらかじめ設定してもよいし、目的地Ｄ１の種類に応じて決定部１２が決定してもよい。後者の場合、例えば大阪にいるユーザが東京で遊ぶことを目的として東京のレジャー施設を目的地Ｄ１として入力すると、決定部１２は、目的地Ｄ１の周囲にある代替目的地Ｄ２（つまり、東京のレジャー施設）の候補Ｄ２０から代替目的地Ｄ２を決定する。
【００３４】
以下、決定部１２での決定処理の一例について、表１を用いて説明する。ここでは、ユーザが、入力部２のディスプレイ２１又は物理ボタンを操作することで「駐車場Ａ」を目的地Ｄ１として指定する入力を行った、と仮定する。したがって、表１には、認識部１１にて認識された（つまり、ユーザにより入力された）目的地Ｄ１の例として、「駐車場Ａ」が挙げられている。
【００３５】
表１において、目的地Ｄ１の名称の隣にある括弧書きは、目的地Ｄ１の種類を表している。また、表１には、「駐車場Ａ」の種類が駐車場であるため、代替目的地Ｄ２の候補Ｄ２０の例として、「駐車場Ｂ」、「駐車場Ｃ」、「駐車場Ｄ」、及び「ホームセンターＥ」が挙げられている。表１において、各代替目的地Ｄ２の候補Ｄ２０の名称の隣にある括弧書きは、各代替目的地Ｄ２の候補Ｄ２０の種類及び状況を表している。例えば、「ホームセンターＥ」は、種類が「条件付き駐車場（店舗を利用すれば駐車料金が減額される駐車場）」であり、状況が「空有り（駐車場が空いている）」である。
【００３６】
また、表１には、各代替目的地Ｄ２の候補Ｄ２０の適性が挙げられている。適性が「〇」である代替目的地Ｄ２の候補Ｄ２０は、代替目的地Ｄ２として決定され得る。一方、適性が「×」である代替目的地Ｄ２の候補Ｄ２０は、代替目的地Ｄ２として決定されない。表１に示す例では、目的地Ｄ１の種類が駐車場であるため、状況が「空有り」である代替目的地Ｄ２の候補Ｄ２０の適性が「〇」となり、状況が「満車」である代替目的地Ｄ２の候補Ｄ２０の適性が「×」となる。
【００３７】
【表１】
2020118652.tif 000003
【００３８】
表１に示す例では、決定部１２は、目的地Ｄ１として「駐車場Ａ」が入力されると、目的地Ｄ１の種類である駐車場に紐付けられた「駐車場Ａ」の周囲にある代替目的地Ｄ２の候補Ｄ２０を記憶部４から検索する。そして、決定部１２は、検索により得られた代替目的地Ｄ２の候補Ｄ２０のうち、適性が「〇」である「駐車場Ｂ」、「駐車場Ｄ」、及び「ホームセンターＥ」を代替目的地Ｄ２として決定する。
【００３９】
次に、決定部１２での決定処理の一例について、表２を用いて説明する。ここでは、ユーザが、入力部２のマイクロホン２２に向かって「〇〇駅の近くで醤油ラーメンを食べたい」という声を発した、と仮定する。そして、認識部１１が、ユーザの音声情報に基づいて、〇〇駅の近くにて醤油ラーメンを提供している「ラーメン屋Ｆ」を目的地Ｄ１として認識した、と仮定する。したがって、表２には、認識部１１にて認識された（つまり、ユーザにより入力された）目的地Ｄ１の例として、「ラーメン屋Ｆ」が挙げられている。
【００４０】
表２において、目的地Ｄ１の名称の隣にある括弧書きは、ユーザの嗜好、つまりユーザの属性情報を表している。また、表２には、「ラーメン屋Ｆ」の種類がラーメン屋であるため、代替目的地Ｄ２の候補Ｄ２０の例として、「ラーメン屋Ｇ」、「ラーメン屋Ｈ」、「ラーメン屋Ｉ」、及び「中華料理店Ｊ」が挙げられている。表２において、各代替目的地Ｄ２の候補Ｄ２０の名称の隣にある括弧書きは、各代替目的地Ｄ２の候補Ｄ２０の属性を表している。例えば、「中華料理店Ｊ」は、属性（ここでは、取り扱うメニュー）が「醤油ラーメン」である。
【００４１】
また、表２には、各代替目的地Ｄ２の候補Ｄ２０の適性が挙げられている。表２に示す例では、ユーザの嗜好が「醤油ラーメン」であるため、属性が「醤油ラーメン」である代替目的地Ｄ２の候補Ｄ２０の適性が「〇」となり、それ以外の代替目的地Ｄ２の候補Ｄ２０の適性が「×」となる。
【００４２】
【表２】
2020118652.tif 000004
【００４３】
表２に示す例では、決定部１２は、目的地Ｄ１として「ラーメン屋Ｆ」が入力されると、目的地Ｄ１の種類であるラーメン屋に紐付けられた「ラーメン屋Ｆ」の周囲にある代替目的地Ｄ２の候補を記憶部４から検索する。そして、決定部１２は、検索により得られた代替目的地Ｄ２の候補Ｄ２０のうち、適性が「〇」である（つまり、ユーザの嗜好（属性情報）に沿った）「ラーメン屋Ｇ」及び「中華料理店Ｊ」を代替目的地Ｄ２として決定する。
【００４４】
このように、決定部１２（決定処理）において、代替目的地Ｄ２は、ユーザの属性情報に基づいて決定され得る。ユーザの属性情報は、ユーザの嗜好の他に、ユーザの年齢、性別、ユーザの過去の行動パターン（傾向を含む）等を含み得る。
【００４５】
作成部１３は、決定部１２により決定された代替目的地Ｄ２に基づいて、推奨経路Ｒ２を作成する作成処理を実行する。具体的には、作成部１３は、車両７（ユーザ）の現在位置から目的地Ｄ１までの経路の候補を１つ以上、算出する。そして、作成部１３は、１以上の経路の候補のうち、車両７の現在位置から代替目的地Ｄ２までの経路の一部又は全部を含む経路を選択し、選択した経路を推奨経路Ｒ２として作成する。一例として、作成部１３は、決定部１２にて決定された代替目的地Ｄ２が１つの場合、車両７の現在位置から代替目的地Ｄ２までの最短経路、言い換えれば、到達時間が最も短い経路を含む推奨経路Ｒ２を作成する。また、一例として、作成部１３は、決定部１２にて決定された代替目的地Ｄ２が複数の場合、複数の代替目的地Ｄ２の各々への到達時間のばらつきが最も小さくなる経路を含む推奨経路Ｒ２を作成する。
【００４６】
仮経路作成部１４は、認識部１１により認識された目的地Ｄ１（つまり、ユーザにより入力された目的地Ｄ１）に基づいて、目的地Ｄ１への仮経路Ｒ１を作成する仮経路作成処理を実行する。本開示でいう「仮経路」は、既存の一般的なナビゲーションシステムにて目的地Ｄ１が入力された場合に作成される、車両７（ユーザ）の現在位置から目的地Ｄ１までの経路に相当する。仮経路作成部１４は、例えばＶＩＣＳから取得した道路交通情報を参照することで、車両７の現在位置から目的地Ｄ１までの道路の交通状況等を加味して仮経路Ｒ１を作成する。一例として、仮経路Ｒ１は、車両７の現在位置から目的地Ｄ１までの複数の経路のうち、車両７の現在位置から目的地Ｄ１に到達するまでに要する時間（到達時間）が最も短くなる経路である。このように、本実施形態のナビゲーションシステム１００は、既存の一般的なナビゲーションシステムとしての機能も有している。仮経路作成部１４で作成された仮経路Ｒ１は、既に述べたように、決定部１２にて代替目的地Ｄ２を決定する際に参照され得る。
【００４７】
案内部１５は、作成部１３で作成された推奨経路Ｒ２に基づいて、車両７（ユーザ）を目的地Ｄ１へ案内する案内処理を実行する。具体的には、案内部１５は、車両７の現在位置及び作成部１３で作成された推奨経路Ｒ２を含む地図情報を表す画像を、出力部３のディスプレイ３１に表示させる。また、案内部１５は、車両７が移動する過程において、車両７が道路の交差点又は分岐点に差し掛かる前に、車両７が推奨経路Ｒ２に沿うように誘導するための誘導用の画像をディスプレイ３１に表示させたり、誘導用の音声をスピーカ３２から出力させたりする。
【００４８】
本実施形態では、案内部１５は、案内処理を開始すると、ユーザの目的の達成状況を監視する。一例として、ユーザがあらかじめ目的地Ｄ１に到達したい時刻を設定している場合、案内部１５は、目的地Ｄ１への到着予定時刻をリアルタイムに計算し、計算した到着予定時刻が設定時刻を超えるか否かを監視する。また、一例として、ユーザがあらかじめ目的地Ｄ１にて目的を完了させたい時刻を設定している場合、案内部１５は、計算した到着予定時刻に目的地Ｄ１にて目的を完了させるのに要する想定時間を加算した時刻が、設定時刻を超えるか否かを監視する。
【００４９】
上記のいずれの態様においても、案内部１５は、計算した時刻が設定時刻を超えると、ユーザの目的の達成が困難であると判定する。このような状況は、例えば目的地Ｄ１へ向かう途中の道路が渋滞していたり、事故等により交通規制が行われていたりするときに起こり得る。また、このような状況は、例えば目的地Ｄ１が飲食店であって、飲食店が満員のために待機しなければならないときに起こり得る。そして、案内部１５は、車両７の判定時点における位置から代替目的地Ｄ２までの経路及び所要時間等を、出力部３から画像及び／又は音声により出力させることで、ユーザに目的地Ｄ１から代替目的地Ｄ２への変更を促す。
【００５０】
（３）動作
以下、本実施形態のナビゲーションシステム１００の動作の一例について、図３及び図４を用いて説明する。以下の説明では、決定部１２により決定される代替目的地Ｄ２は１つである、と仮定する。
【００５１】
まず、ユーザにより入力された目的地Ｄ１に基づいて、推奨経路Ｒ２を作成するフロー、つまり経路探索方法について図３を用いて説明する。認識部１１にて目的地Ｄ１が認識される（つまり、ユーザにより目的地Ｄ１が入力される）と（Ｓ１）、作成部１３は、入力された目的地Ｄ１に基づいて、車両７（ユーザ）の現在位置から目的地Ｄ１までの経路の候補を１つ以上、算出する（Ｓ２）。また、決定部１２は、入力された目的地Ｄ１に基づいて、目的地Ｄ１の種類に紐付けられた１以上の代替目的地Ｄ２の候補Ｄ２０を記憶部４から検索する（Ｓ３）。そして、決定部１２は、１以上の代替目的地Ｄ２の候補Ｄ２０から代替目的地Ｄ２を決定する（Ｓ４）。その後、作成部１３は、ステップＳ２にて算出した１以上の経路の候補のうち、車両７の現在位置から代替目的地Ｄ２までの経路の一部又は全部を含む経路を選択し、選択した経路を推奨経路Ｒ２として作成する（Ｓ５）。ステップＳ２の処理と、ステップＳ３，Ｓ４の処理とは、前後が逆であってもよいし、並行して実行されてもよい。
【００５２】
次に、経路探索方法にて作成された推奨経路Ｒ２に基づいて、車両７（ユーザ）を目的地Ｄ１へ案内するフロー、つまりナビゲーション方法について図４を用いて説明する。以下の説明では、ユーザは、作成部１３にて作成された推奨経路Ｒ２を用いた目的地Ｄ１への案内を選択している、と仮定する。
【００５３】
案内部１５は、推奨経路Ｒ２を用いた目的地Ｄ１への案内を開始する（つまり、案内処理を開始する）と、ユーザの目的の達成状況をリアルタイムに監視する（Ｓ６）。案内部１５は、監視結果に基づいてユーザの目的の達成が困難でないと判定し（Ｓ７：Ｎｏ）、かつ、車両７（ユーザ）が目的地Ｄ１に到着するまでの間は（Ｓ８：Ｎｏ）、ユーザの目的の達成状況の監視を継続する。一方、案内部１５は、車両７が目的地Ｄ１に到着すると（Ｓ８：Ｙｅｓ）、案内処理を終了する。
【００５４】
ここで、案内部１５は、監視結果に基づいてユーザの目的の達成が困難であると判定すると（Ｓ７：Ｙｅｓ）、出力部３から画像又は音声を出力させることにより、ユーザに対して代替目的地Ｄ２を提示する（Ｓ９）。ユーザが入力部２にて目的地Ｄ１を代替目的地Ｄ２へ変更する操作を行うと（Ｓ１０：Ｙｅｓ）、案内部１５は、目的地を代替目的地Ｄ２に再度設定し、再度設定された目的地への経路を用いた案内を開始する（Ｓ１１）。
【００５５】
ユーザが入力部２にて目的地Ｄ１を代替目的地Ｄ２へ変更する操作を行わずに（Ｓ１０：Ｎｏ）、かつ、案内処理をキャンセルする操作を行うと（Ｓ１２：Ｙｅｓ）、案内部１５は、案内処理を終了する。一方、ユーザが入力部２にて案内処理をキャンセルする操作を行わない場合（Ｓ１２：Ｎｏ）、車両７（ユーザ）が目的地Ｄ１に到着するまでの間は（Ｓ１３：Ｎｏ）、案内部１５は、推奨経路Ｒ２を用いた目的地Ｄ１への案内を継続する。この場合も、案内部１５は、車両７が目的地Ｄ１に到着すると（Ｓ１３：Ｙｅｓ）、案内処理を終了する。
【００５６】
以下、本実施形態の経路探索方法の利点について、比較例の経路探索方法との比較を交えて説明する。比較例の経路探索方法は、決定処理及び作成処理を行わずに、仮経路作成処理を行う点で、本実施形態の経路探索方法と相違する。つまり、比較例の経路探索方法では、代替目的地Ｄ２を参照することなく、ユーザにより入力された目的地Ｄ１に基づく仮経路作成処理により、仮経路Ｒ１を作成する。このため、比較例の経路探索方法を用いたナビゲーションシステム（以下、「比較例のナビゲーションシステム」という）では、案内部は、仮経路Ｒ１を用いた目的地Ｄ１への案内を行うことになる。
【００５７】
まず、本実施形態の経路探索方法を用いたナビゲーションシステム１００において、案内部１５が推奨経路Ｒ２を用いて目的地Ｄ１への案内を開始している、と仮定する。そして、図５に示すように、車両７（ユーザ）が推奨経路Ｒ２に沿って移動している途中の地点Ｐ１で、ユーザにより目的地Ｄ１が代替目的地Ｄ２へ変更された、と仮定する。この場合、推奨経路Ｒ２が代替目的地Ｄ２を考慮した経路であるため、車両７は、地点Ｐ１から代替目的地Ｄ２までの最短経路、又は最短経路に比較的近い経路Ｒ２０に沿って移動することが可能である。
【００５８】
一方、比較例のナビゲーションシステムにおいて、案内部が仮経路Ｒ１を用いて目的地Ｄ１への案内を開始している、と仮定する。そして、図６に示すように、車両２００（ユーザ）が仮経路Ｒ１に沿って移動している途中の地点Ｐ２で、ユーザにより目的地Ｄ１が代替目的地Ｄ２へ変更された、と仮定する。この場合、仮経路Ｒ１が代替目的地Ｄ２を考慮していない経路であるため、車両２００は、地点Ｐ２から代替目的地Ｄ２へ向かう際に遠回りしなければならず（図６の破線参照）、代替目的地Ｄ２へ到達するのに長時間を要する、という問題が生じ得る。
【００５９】
上述のように、本実施形態の経路探索方法では、比較例の経路探索方法と比較して、目的地Ｄ１への案内の途中で目的地Ｄ１が変更される場合でも、変更後の目的地（代替目的地Ｄ２）への到達時間の短縮を図ることができる、という利点がある。
【００６０】
（４）変形例
上述の実施形態は、本開示の様々な実施形態の一つに過ぎない。上述の実施形態は、本開示の目的を達成できれば、設計等に応じて種々の変更が可能である。また、経路探索方法と同様の機能は、（コンピュータ）プログラム、又はプログラムを記録した非一時的記録媒体等で具現化されてもよい。また、ナビゲーションシステム１００と同様の機能は、（コンピュータ）プログラム、又はプログラムを記録した非一時的記録媒体等で具現化されてもよい。
【００６１】
一態様に係るプログラムは、１以上のプロセッサに、決定処理と、作成処理と、を実行させるためのプログラムである。決定処理は、ユーザにより入力された目的地Ｄ１に基づいて、目的地Ｄ１に類似する代替目的地Ｄ２を決定する。作成処理は、ユーザの現在位置から目的地Ｄ１までの経路であって、代替目的地Ｄ２への経路を含む推奨経路Ｒ２を作成する。
【００６２】
以下、上述の実施形態の変形例を列挙する。以下に説明する変形例は、上述の実施形態と適宜組み合わせて適用可能である。
【００６３】
（４．１）第１変形例
第１変形例の経路探索方法（ナビゲーションシステム１００）は、図７に示すように、作成処理は、代替目的地Ｄ２の候補Ｄ２０が複数ある場合に、代替目的地Ｄ２の候補Ｄ２０の密集度に応じて推奨経路Ｒ２を作成する点で、上述の実施形態と相違する。本開示でいう「密集度」は、一例として、複数の代替目的地Ｄ２の候補Ｄ２０が存在するエリアＡ０を複数の小エリアＡ１に分割した場合の、小エリアＡ１ごとの代替目的地Ｄ２の候補Ｄ２０の数に相当する。例えば、小エリアＡ１に代替目的地Ｄ２の候補Ｄ２０が３つあれば、密集度は「３」となる。図７に示す例では、エリアＡ０は、４つの小エリアＡ１１〜Ａ１４に分割されている。本変形例では、小エリアＡ１は、道路の位置を考慮せずに、一定の面積を有する矩形状の領域（固定区間）であってもよいし、道路により区切られた領域（可変区間）であってもよい。
【００６４】
作成処理（作成部１３）は、代替目的地Ｄ２の候補Ｄ２０の密集度の高い小エリアＡ１を通過する、又はこの小エリアＡ１の付近を通過するように、推奨経路Ｒ２を作成する。図７に示す例では、小エリアＡ１１，Ａ１２，Ａ１３，Ａ１４の代替目的地Ｄ２の候補Ｄ２０の数（言い換えれば、密集度）は、それぞれ「３」、「０」、「２」、「１」である。したがって、作成部１３は、密集度の最も高い小エリアＡ１１の付近を通過するように、推奨経路Ｒ２を作成する。
【００６５】
本変形例では、代替目的地Ｄ２の候補Ｄ２０が密集している領域又はその付近を通過するように推奨経路Ｒ２が作成されることになる。したがって、本変形例では、目的地Ｄ１への案内の途中で目的地Ｄ１が変更される場合に、ユーザが選択し得る代替目的地Ｄ２の候補Ｄ２０の数が増えやすく、ユーザによる代替目的地Ｄ２の選択の自由度が向上する、という利点がある。
【００６６】
（４．２）第２変形例
第２変形例の経路探索方法（ナビゲーションシステム１００）では、案内部１５は、作成した推奨経路Ｒ２にて目的地Ｄ１への案内を行わずに、仮経路Ｒ１及び推奨経路Ｒ２をユーザへ提示する提示処理を実行する点で、上述の実施形態と相違する。つまり、本変形例の経路探索方法は、仮経路作成処理と、提示処理と、を有している。本開示でいう「提示」とは、仮経路Ｒ１及び推奨経路Ｒ２の各々をディスプレイ３１に表示する態様に限らない。例えば、「提示」は、ユーザが仮経路Ｒ１を選択した場合の目的地Ｄ１への到達時間、及びユーザが推奨経路Ｒ２を選択した場合の目的地Ｄ１への到達時間をディスプレイ３１に表示する、又はスピーカ３２から音声にて出力する態様を含み得る。以下、前者の到達時間を「第１到達時間」、後者の到達時間を「第２到達時間」ともいう。さらには、「提示」は、ユーザが推奨経路Ｒ２を選択した場合におけるメリット・デメリットをディスプレイ３１に表示する、又はスピーカ３２から音声にて出力する態様を含み得る。
【００６７】
一例として、ユーザが特定の飲食店を目的地Ｄ１と入力することで、決定部１２が、この飲食店の周囲にある他の飲食店を代替目的地Ｄ２として決定する場合を想定する。この場合、案内部１５は、「付近の飲食店に目的地を変更なさる可能性があるならば、こちらのルートの方が近くなる可能性があります」等、推奨経路Ｒ２の選択を促すメッセージをディスプレイ３１に表示させたり、スピーカ３２から音声にて出力させたりする。上記のメッセージは、例えば「最短経路と比べ、推奨経路は到着予想時刻が△△分遅れますが、もし途中で目的地を代替目的地に変更される場合は、推奨経路が最短経路となります。どちらの経路を選択されますか？」等のメッセージであってもよい。このメッセージにおける「最短経路」は、仮経路Ｒ１に相当する。
【００６８】
ユーザは、入力部２を用いて、提示された仮経路Ｒ１及び推奨経路Ｒ２のいずれか一方を選択する操作を行う。これにより、案内部１５は、ユーザにより選択された経路にて目的地Ｄ１への案内を開始する。このように、本変形例では、仮経路Ｒ１及び推奨経路Ｒ２のいずれの経路で目的地Ｄ１へ案内するかをユーザに選択させることができるので、ユーザの望みに沿った経路で目的地Ｄ１へ案内させやすくなる、という利点がある。
【００６９】
ここで、ユーザに仮経路Ｒ１及び推奨経路Ｒ２を提示するか否かは、第１到達時間と第２到達時間との差分に応じて決定してもよい。一例として、差分が第１閾値（例えば、５分）を下回る場合、案内部１５は、ユーザに仮経路Ｒ１及び推奨経路Ｒ２を提示することなく、推奨経路Ｒ２にて目的地Ｄ１への案内を開始する。また、差分が第１閾値以上、第２閾値（例えば、１５分）未満である場合、案内部１５は、ユーザに仮経路Ｒ１及び推奨経路Ｒ２を提示することで、ユーザに経路の選択を促す。また、差分が第２閾値を上回る場合、案内部１５は、ユーザに仮経路Ｒ１及び推奨経路Ｒ２を提示することなく、仮経路Ｒ１にて目的地への案内を開始する。
【００７０】
また、第１閾値及び第２閾値は、ユーザにより入力された目的地Ｄ１に応じて適宜変更されてもよいし、ユーザが適宜設定してもよい。また、ユーザに仮経路Ｒ１及び推奨経路Ｒ２を提示するか否かは、上記の態様に限らず、例えば仮経路Ｒ１を選択した場合に掛かる費用（有料道路の使用料金、又は燃費を含む）と、推奨経路Ｒ２を選択した場合に掛かる費用と、に応じて決定してもよい。その他、ユーザに仮経路Ｒ１及び推奨経路Ｒ２を提示するか否かは、ユーザによりあらかじめ設定された条件（例えば、到達時間を優先するか、又は費用を優先するか等）に応じて決定してもよい。
【００７１】
（４．３）第３変形例
第３変形例の経路探索方法（ナビゲーションシステム１００）では、図８に示すように、処理部１は、目的地Ｄ１への経路を再度設定する際に、決定処理及び作成処理を実行する点で、上述の実施形態と相違する。図８に示す例では、ユーザは、最初に目的地Ｄ１への経路を設定する際に、仮経路Ｒ１での案内を選択している、と仮定する。そして、図８に示す例では、車両７（ユーザ）が仮経路Ｒ１に沿って移動している途中の地点Ｐ３で、渋滞に巻き込まれたユーザが、入力部２を用いて渋滞を回避するための経路を再度設定する、と仮定する。
【００７２】
この場合、決定処理（決定部１２）及び作成処理（作成部１３）により推奨経路Ｒ２としての経路Ｒ２１が作成され、かつ仮経路作成処理（仮経路作成部１４）により仮経路Ｒ１としての経路Ｒ１１が作成される。そして、案内部１５は、経路Ｒ１１，Ｒ２１のうちユーザにより選択された経路にて目的地Ｄ１への案内を再開する。このように、本変形例では、ユーザが目的地Ｄ１への案内開始時においては推奨経路Ｒ２での案内を望んでいない場合でも、目的地Ｄ１へ向かう途中で推奨経路Ｒ２での案内を選択することができる、という利点がある。
【００７３】
本変形例では、処理部１は、ユーザが入力部２を用いて目的地Ｄ１への経路を再度設定する入力を行った場合に、決定処理及び作成処理を実行しているが、この態様に限られない。例えば、処理部１は、目的地Ｄ１の到着予想時刻と、最初に目的地Ｄ１への経路を設定した時点における目的地Ｄ１の到着予想時刻との差分が所定値（例えば、２０分）を上回る場合に、決定処理及び作成処理を実行してもよい。また、例えば、処理部１は、目的地Ｄ１である店舗が既に閉まっている、又は目的地Ｄ１の到着予想時刻では店舗が閉まってしまう場合等、目的地Ｄ１での目的の達成が困難であると判断すると、決定処理及び作成処理を実行してもよい。
【００７４】
本変形例では、処理部１は、ユーザが最初に目的地Ｄ１への経路を設定する時点、及びユーザが目的地Ｄ１への経路を再度設定する時点のいずれにおいても決定処理及び作成処理を実行しているが、この態様に限られない。つまり、処理部１は、ユーザが最初に目的地Ｄ１への経路を設定する時点では決定処理及び作成処理を実行せず、ユーザが目的地Ｄ１への経路を再度設定する時点において決定処理及び作成処理を実行してもよい。この場合、ユーザが最初に目的地Ｄ１への経路を設定する時点においては、案内部１５は、仮経路作成処理（仮経路作成部１４）にて作成された仮経路Ｒ１にて目的地Ｄ１への案内を開始する。
【００７５】
（４．４）その他の変形例
本開示におけるナビゲーションシステム１００は、例えば、処理部１等に、コンピュータシステムを含んでいる。コンピュータシステムは、ハードウェアとしてのプロセッサ及びメモリを主構成とする。コンピュータシステムのメモリに記録されたプログラムをプロセッサが実行することによって、本開示におけるナビゲーションシステム１００としての機能が実現される。プログラムは、コンピュータシステムのメモリに予め記録されてもよく、電気通信回線を通じて提供されてもよく、コンピュータシステムで読み取り可能なメモリカード、光学ディスク、ハードディスクドライブ等の非一時的記録媒体に記録されて提供されてもよい。コンピュータシステムのプロセッサは、半導体集積回路（ＩＣ）又は大規模集積回路（ＬＳＩ）を含む１ないし複数の電子回路で構成される。ここでいうＩＣ又はＬＳＩ等の集積回路は、集積の度合いによって呼び方が異なっており、システムＬＳＩ、ＶＬＳＩ（Very Large Scale Integration）、又はＵＬＳＩ（Ultra Large Scale Integration）と呼ばれる集積回路を含む。さらに、ＬＳＩの製造後にプログラムされる、ＦＰＧＡ（Field-Programmable Gate Array）、又はＬＳＩ内部の接合関係の再構成若しくはＬＳＩ内部の回路区画の再構成が可能な論理デバイスについても、プロセッサとして採用することができる。複数の電子回路は、１つのチップに集約されていてもよいし、複数のチップに分散して設けられていてもよい。複数のチップは、１つの装置に集約されていてもよいし、複数の装置に分散して設けられていてもよい。ここでいうコンピュータシステムは、１以上のプロセッサ及び１以上のメモリを有するマイクロコントローラを含む。したがって、マイクロコントローラについても、半導体集積回路又は大規模集積回路を含む１ないし複数の電子回路で構成される。
【００７６】
また、ナビゲーションシステム１００における複数の機能が、１つの筐体内に集約されていることはナビゲーションシステム１００に必須の構成ではない。ナビゲーションシステム１００の構成要素は、複数の筐体に分散して設けられていてもよい。さらに、ナビゲーションシステム１００の少なくとも一部の機能は、例えば、サーバ装置及びクラウド（クラウドコンピューティング）等によって実現されてもよい。
【００７７】
一例として、決定部１２及び作成部１３の機能は、サーバ装置及びクラウド等によって実現されてもよい。この場合、車両（移動体）７は、例えばインターネット等のネットワークを介してサーバ装置等と通信する通信部を別途備えていればよい。この通信部は、通信部６と兼用されてもよい。
【００７８】
その他、ナビゲーションシステム１００の少なくとも一部の機能は、例えばスマートフォン等の端末にインストールされた専用のアプリケーションにて実行されてもよい。
【００７９】
上述の実施形態において、代替目的地Ｄ２は、ユーザとは異なる外部からの情報に基づいて決定されてもよい。ここでいう「外部からの情報」は、一例として、飲食店に関する情報を取り扱うグルメサイトにて発信された情報の他、Ｔｗｉｔｔｅｒ（登録商標）又はＦａｃｅｂｏｏｋ（登録商標）等のＳＮＳ（Social Networking Service）にて発信された情報を含み得る。また、「外部からの情報」は、他のユーザが過去に入力した代替目的地Ｄ２に関する情報を含み得る。この場合、ナビゲーションシステム１００は、例えばインターネット等のネットワークを介して外部からの情報を取得するための通信部を備えていればよい。この通信部は、通信部６と兼用されてもよい。
【００８０】
上述の実施形態において、目的地Ｄ１は、最終目的地のみならず、中間目的地（つまり、経由地）を含み得る。同様に、代替目的地Ｄ２は、最終目的地のみならず、中間目的地を含み得る。例えば、最終目的地がレジャー施設で、途中でコンビニエンスストアに立ち寄る場合、コンビニエンスストアが中間目的地となる。
【００８１】
上述の実施形態では、案内部１５は、ユーザの目的の達成が困難であると判定すると、ユーザに対して代替目的地Ｄ２を提示しているが、この態様に限られない。例えば、案内部１５は、ユーザが入力部２を用いて目的地Ｄ１を変更する操作を行う際に、ユーザに対して代替目的地Ｄ２を提示する態様であってもよい。この態様では、案内部１５は、ユーザの目的の達成状況をリアルタイムに監視しなくてもよい。
【００８２】
上述の実施形態において、案内部１５は、目的地Ｄ１が入力された時点で目的地Ｄ１を利用することが困難であると判断した場合、この時点で目的地Ｄ１を代替目的地Ｄ２へ変更することをユーザに促す態様であってもよい。
【００８３】
上述の実施形態において、ナビゲーションシステム１００は、処理に用いられるデータを定期的又は不定期にサーバ装置及びクラウド等から取得する態様であってもよい。その他、処理に用いられるデータは、例えばＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭ、又はメモリカード等の非一時的な記録媒体に記録されているデータを記憶部４の記憶領域に上書きすることにより更新されてもよい。
【００８４】
上述の実施形態において、処理部１の決定部１２及び作成部１３は、ユーザにより入力される目的地Ｄ１に基づいて、推奨経路Ｒ２を出力する機械学習済みの分類器であってもよい。分類器は、車両７（ユーザ）の現在地及び目的地Ｄ１を入力データとして機械学習することで得られる。分類器は、例えばＳＶＭ（Support Vector Machine）等の線形分類器の他、ニューラルネットワークを用いた分類器、又は多層ニューラルネットワークを用いた深層学習（ディープラーニング）により生成される分類器を含み得る。この場合、分類器は、ナビゲーションシステム１００の使用中において再学習が可能であってもよい。つまり、経路探索用学習方法は、上述の経路探索方法の決定処理及び作成処理を実行する分類器を機械学習させる方法である。経路探索用学習方法は、目的地Ｄ１を入力として分類器が出力する推奨経路Ｒ２を、ユーザが選択したか否かを教師データとして、分類器を機械学習させる。
【００８５】
（まとめ）
以上述べたように、第１の態様に係る経路探索方法は、決定処理と、作成処理と、を有する。決定処理は、ユーザにより入力された目的地（Ｄ１）に基づいて、目的地（Ｄ１）に類似する代替目的地（Ｄ２）を決定する。作成処理は、ユーザの現在位置から目的地（Ｄ１）までの経路であって、代替目的地（Ｄ２）への経路を含む推奨経路（Ｒ２）を作成する。
【００８６】
この態様によれば、目的地（Ｄ１）への案内の途中で目的地（Ｄ１）が変更される場合でも、変更後の目的地（代替目的地（Ｄ２））への到達時間の短縮を図ることができる、という利点がある。
【００８７】
第２の態様に係る経路探索方法では、第１の態様において、代替目的地（Ｄ２）の候補（Ｄ２０）は、目的地（Ｄ１）の種類ごとに分類されている。
【００８８】
この態様によれば、代替目的地（Ｄ２）の候補（Ｄ２０）が分類されていない場合と比較して、入力された目的地（Ｄ１）に対応する代替目的地（Ｄ２）を探索しやすい、という利点がある。
【００８９】
第３の態様に係る経路探索方法では、第１又は第２の態様において、代替目的地（Ｄ２）は、ユーザの属性情報に基づいて決定される。
【００９０】
この態様によれば、ユーザが望む代替目的地（Ｄ２）に決定しやすくなる、という利点がある。
【００９１】
第４の態様に係る経路探索方法では、第１〜第３のいずれかの態様において、代替目的地（Ｄ２）は、ユーザとは異なる外部からの情報に基づいて決定される。
【００９２】
この態様によれば、例えば現在の流行に沿った代替目的地（Ｄ２）など、ユーザが潜在的に望む代替目的地（Ｄ２）に決定しやすくなる、という利点がある。
【００９３】
第５の態様に係る経路探索方法では、第１〜第４のいずれかの態様において、作成処理は、代替目的地（Ｄ２）の候補（Ｄ２０）が複数存在する場合、代替目的地（Ｄ２）の候補（Ｄ２０）の密集度に応じて推奨経路（Ｒ２）を作成する。
【００９４】
この態様によれば、目的地（Ｄ１）への案内の途中で目的地（Ｄ１）が変更される場合に、ユーザが選択し得る代替目的地（Ｄ２）の候補（Ｄ２０）の数が増えやすく、ユーザによる代替目的地（Ｄ２）の選択の自由度が向上する、という利点がある。
【００９５】
第６の態様に係る経路探索方法は、第１〜第５のいずれかの態様において、仮経路作成処理と、提示処理と、を有する。仮経路作成処理は、目的地（Ｄ１）に基づいて、目的地（Ｄ１）への仮経路（Ｒ１）を作成する。提示処理は、仮経路（Ｒ１）及び推奨経路（Ｒ２）をユーザへ提示する。
【００９６】
この態様によれば、仮経路（Ｒ１）及び推奨経路（Ｒ２）のいずれの経路で目的地（Ｄ１）へ案内するかをユーザに選択させることができるので、ユーザの望みに沿った経路で目的地（Ｄ１）へ案内させやすくなる、という利点がある。
【００９７】
第７の態様に係る経路探索方法では、第１〜第６のいずれかの態様において、代替目的地（Ｄ２）は、目的地（Ｄ１）に基づく目的地（Ｄ１）への仮経路（Ｒ１）の周囲にある代替目的地（Ｄ２）の候補（Ｄ２０）から決定される。
【００９８】
この態様によれば、変更後の目的地（代替目的地（Ｄ２））への到達時間の短縮を図りやすい、という利点がある。
【００９９】
第８の態様に係る経路探索方法では、第１〜第６のいずれかの態様において、代替目的地（Ｄ２）は、目的地（Ｄ１）の周囲にある代替目的地（Ｄ２）の候補（Ｄ２０）から決定される。
【０１００】
この態様によれば、変更後の目的地（代替目的地（Ｄ２））への到達時間の短縮を図りやすい、という利点がある。
【０１０１】
第９の態様に係る経路探索方法は、第１〜第８のいずれかの態様において、目的地（Ｄ１）への経路を再度設定する際に、決定処理及び作成処理を実行する。
【０１０２】
この態様によれば、ユーザが目的地（Ｄ１）への案内開始時においては推奨経路（Ｒ２）での案内を望んでいない場合でも、目的地（Ｄ１）へ向かう途中で推奨経路（Ｒ２）での案内を選択することができる、という利点がある。
【０１０３】
第１０の態様に係るナビゲーション方法は、第１〜第９のいずれかの態様の経路探索方法にて作成された推奨経路（Ｒ２）に基づいて、ユーザを目的地（Ｄ１）へ案内する案内処理を実行する。
【０１０４】
この態様によれば、目的地への案内の途中で目的地が変更される場合でも、変更後の目的地（代替目的地（Ｄ２））への到達時間の短縮を図ることができる、という利点がある。
【０１０５】
第１１の態様に係るナビゲーションシステム（１００）は、決定部（１２）と、作成部（１３）と、案内部（１５）と、を備える。決定部（１２）は、ユーザにより入力された目的地（Ｄ１）に基づいて、目的地（Ｄ１）に類似する代替目的地（Ｄ２）を決定する。作成部（１３）は、ユーザの現在位置から目的地（Ｄ１）までの経路であって、代替目的地（Ｄ２）への経路を含む推奨経路（Ｒ２）を作成する。案内部（１５）は、作成部（１３）で作成された推奨経路（Ｒ２）に基づいて、ユーザを目的地（Ｄ１）へ案内する。
【０１０６】
この態様によれば、目的地（Ｄ１）への案内の途中で目的地（Ｄ１）が変更される場合でも、変更後の目的地（代替目的地（Ｄ２））への到達時間の短縮を図ることができる、という利点がある。
【０１０７】
第１２の態様に係る移動体（７）は、第１１の態様のナビゲーションシステム（１００）と、ナビゲーションシステム（１００）を有する本体（７０）と、を備える。
【０１０８】
この態様によれば、目的地（Ｄ１）への案内の途中で目的地（Ｄ１）が変更される場合でも、変更後の目的地（代替目的地（Ｄ２））への到達時間の短縮を図ることができる、という利点がある。
【０１０９】
第１３の態様に係るプログラムは、１以上のプロセッサに、決定処理と、作成処理と、を実行させるためのプログラムである。決定処理は、ユーザにより入力された目的地（Ｄ１）に基づいて、目的地（Ｄ１）に類似する代替目的地（Ｄ２）を決定する。作成処理は、ユーザの現在位置から目的地（Ｄ１）までの経路であって、代替目的地（Ｄ２）への経路を含む推奨経路（Ｒ２）を作成する。
【０１１０】
この態様によれば、目的地（Ｄ１）への案内の途中で目的地（Ｄ１）が変更される場合でも、変更後の目的地（代替目的地（Ｄ２））への到達時間の短縮を図ることができる、という利点がある。
【０１１１】
第１４の態様に係る経路探索用学習方法は、第１〜第９のいずれかの態様の経路探索方法の決定処理及び作成処理を実行する分類器を機械学習させる方法である。経路探索用学習方法は、目的地（Ｄ１）を入力として分類器が出力する推奨経路（Ｒ２）を、ユーザが選択したか否かを教師データとして、分類器を機械学習させる。
【０１１２】
この態様によれば、目的地（Ｄ１）への案内の途中で目的地（Ｄ１）が変更される場合でも、変更後の目的地（代替目的地（Ｄ２））への到達時間の短縮を図ることができる、という利点がある。
【０１１３】
第２〜第９の態様に係る方法については、経路探索方法に必須の方法ではなく、適宜省略可能である。
【０１１４】
ところで、第１の態様に係る経路探索方法は、決定処理及び作成処理の代わりに、目的地決定処理を有していてもよい。目的地決定処理は、ユーザにより入力された目的地（Ｄ１）に基づいて、目的地（Ｄ１）の候補が複数存在する場合、目的地（Ｄ１）の候補の密集度に応じて目的地（Ｄ１）を決定する。ここでいう「密集度」は、一例として、複数の目的地Ｄ１の候補が存在するエリアを複数の小エリアに分割した場合の、小エリアごとの目的地Ｄ１の候補の数に相当する。例えば、小エリアに目的地Ｄ１の候補が３つあれば、密集度は「３」となる。小エリアは、道路の位置を考慮せずに、一定の面積を有する矩形状の領域（固定区間）であってもよいし、道路により区切られた領域（可変区間）であってもよい。
【０１１５】
例えば、ユーザが入力部２を用いて「〇〇駅の周辺にある駐車場に駐車したい」と入力した、と仮定する。この場合、目的地決定処理により目的地（Ｄ１）を決定しない態様では、駐車場（目的地（Ｄ１））が満車であれば、この駐車場の周辺にある駐車場をユーザが探すことが想定される。そして、この駐車場の周辺に駐車場が存在しない場合、ユーザが駐車場を探す手間が増大する可能性がある。一方、目的地決定処理では、〇〇駅の周辺にある駐車場（目的地（Ｄ１））の候補のうち、密集度の高い小エリアにある駐車場を目的地（Ｄ１）として決定することになる。このため、この態様では、仮に駐車場（目的地（Ｄ１））が満車であっても、この駐車場の周辺にある駐車場をユーザが探しやすく、ユーザが駐車場を探す手間を低減することができる、という利点がある。
【符号の説明】
【０１１６】
１０  分類器
１２  決定部
１３  作成部
１５  案内部
１００  ナビゲーションシステム
７  移動体（車両）
７０  本体
Ｄ１  目的地
Ｄ２  代替目的地
Ｄ２０  代替目的地の候補
Ｒ１  仮経路
Ｒ２  推奨経路
【図１】
2020118652.tif 000005
【図２】
2020118652.tif 000006
【図３】
2020118652.tif 000007
【図４】
2020118652.tif 000008
【図５】
2020118652.tif 000009
【図６】
2020118652.tif 000010
【図７】
2020118652.tif 000011
【図８】
2020118652.tif 000012