• ポートフォリオ機能


ポートフォリオを新規に作成して保存
既存のポートフォリオに追加保存

  • この表をプリントする
PDF PDFをダウンロード
審決分類 審判 一部申し立て 2項進歩性  G01C
管理番号 1068832
異議申立番号 異議2000-73716  
総通号数 37 
発行国 日本国特許庁(JP) 
公報種別 特許決定公報 
発行日 1994-11-25 
種別 異議の決定 
異議申立日 2000-10-04 
確定日 2002-09-21 
異議申立件数 1 
訂正明細書 有 
事件の表示 特許第3027899号「推奨経路案内装置」の請求項1ないし8に係る特許に対する特許異議の申立てについて、次のとおり決定する。 
結論 訂正を認める。 特許第3027899号の請求項1ないし8に係る特許を維持する。 
理由 1.手続の経緯
特許第3027899号の請求項1ないし8に係る発明は、平成5年5月12日に特許出願され、平成12年2月4日にその特許権の設定登録がなされ、その後、大西蓉子により特許異議の申立てがなされ、取消しの理由が通知され、その指定期間内である平成13年5月1日に訂正請求がなされたものである。
2.訂正の適否についての判断
(1)訂正の内容
1.訂正事項a
特許請求の範囲の請求項1における「前記探索開始終了点設定手段で設定した探索開始点から探索終了点までの経路を前記道路ネットワーク記録手段の情報から探索する探索手段と、」とあるのを、「前記探索開始終了点設定手段で初期コストが与えられた各探索開始点から、加算コストが与えられた各探索終了点までの経路を前記道路ネットワーク記録手段の情報から探索し、前記出発地から前記目的地まで最小コストで到達できる経路を求める探索手段と、」と訂正する。
2.訂正事項b
特許明細書の段落番号【0008】を、
「【課題を解決するための手段】
上記の問題を解決するために本発明は、第1の手段として前記地点設定手段で設定した出発地または目的地の情報から複数個の探索開始点または探索終了点を設定し、それぞれに固有の探索開始時の初期コストまたは探索終了点到達時の加算コストを与える探索開始終了点設定手段と、前記探索開始終了点設定手段で初期コストが与えられた各探索開始点から、加算コストが与えられた各探索終了点までの経路を前記道路ネットワーク記録手段の情報から探索し、前記出発地から前記目的地まで最小コストで到達できる経路を求める探索手段とを備えたことを特徴とする。」と訂正する。
3.訂正事項c
特許明細書の段落番号【0048】を、
「【0048】
第3の実施例における地点設定処理と第1および第2の実施例における地点設定処理の差異は、探索開始点および探索終了点の設定基準をリンク上に置くかノード上に置くかにある。第1および第2の実施例では出発地または目的地の位置から近いノードを探索開始点または探索終了点として選択していたが、第3の実施例では出発地または目的地の位置から近いリンクを選択してそのリンク上の端のノードを探索開始点または探索終了点とする。以降に図12のフローチャートを用いて詳細に説明する。図12のステップ1201においてユーザーは出発地(目的地)の位置を例えばCRTに映し出された地図上にカーソルを表示し、カーソルを移動させることにより位置を決定して、所望の座標系に変換し位置情報を取得する。ステップ1202 では、設定した出発地の座標を中心に半径limit_distの円の範囲(図2の点線の円:例えば50mの範囲)の地図情報を読み込むが、この場合は簡単のため1枚の地図内としている。ステップ1203 では、各リンク(L1〜L12)への距離(各差分データ成分への一番近い距離)を図11(b)の経度・緯度情報および図11(c)のリンク形状差分データとステップ1201で得た出発地(目的地)の位置情報から順次算出し、距離の小さい順にN本(例えば2本)を選択して垂線とリンクの交点の位置および距離を記録する。図11(a)のような場合、出発地側ではリンクL1上の点P1の位置座標と距離DP1、およびリンクL3上の点P2の位置座標と距離DP2が記録され、目的地側ではリンクL8上の点P3の位置座標と距離DP3、およびリンクL11上の点P4の位置座標と距離 DP4が記録される。次にスデップ1204 にて出発地側かどうか判定される。出発地側であればステップ1205 に進み、選択されたリンクL1上の点P1から一方通行規制に従って到達できるノードN1、N3および選択されたリンクL3上の点P2から一方通行規制に従って到達できるノードN3 を探索開始点とする。ノードN1には交点P1からノードN1までの距離を、ノードN3には交点P1からノードN3までの距離または交点P2からノードN3までの距離の短い方を記憶する。さらにステップ1206において選択したノードN1、N3に探索開始点フラグをたてる。ステップ1204 において目的地側であればステップ1208に進み、選択されたリンクL8上の点P3に一方通行規制に従って進入できるノードN7および選択されたリンクL11上の点P4に一方通行規制に従って進入できるノードN11を探索開始点とする。ノードN7 には交点 P3 からノードN7までの距離を、ノードN11には交点P4からノードN11までの距離を記録する。さらにステップ1209 において選択したノードN7、N11に探索終了点フラグをたてる。最後にステップ1207 において、探索開始点(ノードN1、N3)および探索終了点(ノードN7、N11)に初期コストとして一定値(例えば0)を付与する。以上で地点設定処理を終了する。」と訂正する。
(2)訂正の目的の適否、新規事項の有無及び拡張・変更の存否
上記訂正事項aは、発明を特定する事項である「前記探索開始終了点設定手段で設定した探索開始点から探索終了点までの経路を前記道路ネットワーク記録手段の情報から探索する探索手段」を、「前記探索開始終了点設定手段で初期コストが与えられた各探索開始点から、加算コストが与えられた各探索終了点までの経路を前記道路ネットワーク記録手段の情報から探索し、前記出発地から前記目的地まで最小コストで到達できる経路を求める探索手段」という発明特定事項に減縮するものであり、しかも、これについては願書に添付された明細書の段落【0023】〜【0029】に記載されているから、特許請求の範囲の減縮を目的とした明細書の訂正に該当する。
上記訂正事項bは、訂正事項aとの整合をとるための訂正であり、明りょうでない記載の釈明に該当する。
上記訂正事項cは、訂正前の「図12(a)」という記載は明らかに「図11(a)」の誤記であるので、誤記の訂正に該当する。
(3)むすび
したがって、上記訂正は、特許法の一部を改正する法律(平成6年法律第116号)附則第6条第1項の規定によりなお従前の例によるとされる、特許法第120条の4第3項で準用する平成6年法律第116号による改正前の特許法第126条第1項ただし書き及び第2項の規定に適合するので、当該訂正を認める。
3.特許異議の申立てについての判断
(1)申立ての理由の概要
申立人大西蓉子は、証拠として甲第1号証(特開平4-359112号公報)、甲第2号証(特開平4-328789号公報)、甲第3号証(特開昭62-82316号公報)、甲第4号証(特開昭62-276697号公報)、甲第5号証(特開平4-372985号公報)、甲第6号証(特開平4-319986号公報)を提出し、請求項1ないし8に係る発明は、特許法第29条第2項の規定に違反してなされたものであるから、取り消すべき旨主張している。
(2)本件の請求項1に係る発明
上記2.で示したように上記訂正が認められるから、本件の請求項1に係る発明(「本件発明」という。)は、上記訂正請求に係る訂正明細書の特許請求の範囲の請求項1に記載された事項により特定される、以下のとおりのものと認める。
「交差点および道路の位置および接続関係を記録した道路ネットワーク記録手段と、出発地と目的地を設定する地点設定手段と、前記地点設定手段で設定した出発地または目的地の情報から複数個の探索開始点または探索終了点を設定し、それぞれに固有の探索開始時の初期コストまたは探索終了点到達時の加算コストを与える探索開始終了点設定手段と、前記探索開始終了点設定手段で初期コストが与えられた各探索開始点から、加算コストが与えられた各探索終了点までの経路を前記道路ネットワーク記録手段の情報から探索し、前記出発地から前記目的地まで最小コストで到達できる経路を求める探索手段と、前記探索手段で得られた経路を出力する出力手段とを備えたことを特徴とする推奨経路案内装置。」
(3)刊行物等
特許異議申立人が証拠として提出した刊行物には、以下のように記載されている。
1.甲第1号証
「車両を出発地点から目的地点まで案内するために出発地点から目的地点までの経路を設定する車両用経路案内装置であって、各交差点の位置情報、各交差点の隣接交差点までの区間道程、各交差点および各道路に関する属性情報を含む交差点情報を記憶する交差点情報記憶手段と、該交差点情報記憶手段に記憶された交差点情報に基づいて前記出発地点および目的地点からそれぞれ所定範囲内の交差点を候補交差点として選択し、この選択された交差点の中から所定のパラメータに基づいて出発交差点および最終交差点を設定する経路端交差点設定手段と、該経路端交差点設定手段で設定された出発交差点および最終交差点との間の最適誘導経路を前記交差点情報記憶手段に記憶された交差点情報にに基づいて設定する誘導経路設定手段とを有することを特徴とする車両用経路案内装置。」(特許請求の範囲)
「【0026】なお、出発地点および目的地点は、通常はこのように交差点に設定されていない場合が多く、交差点と交差点との間のリンク、すなわち道路上であったり、またはリンク上でない例えば自車の駐車場であったりする。」(公報第6欄)
「【0028】ここで、出発候補交差点の中から最も適した交差点を出発交差点として選定する場合と、最終候補交差点の中から最も適した交差点を最終交差点として選定する場合とはほぼ同じ考えで選定するので、以下、出発候補交差点の中から出発交差点を選定する場合で説明する。抽出した出発候補交差点の中から最も適した交差点を出発交差点として選定する場合、この問題を単純な2次平面上の問題として捕らえる場合には、出発地点から最も近い交差点を出発交差点として選定すればよいことになるけれども、現実には最も近い交差点が出発交差点に適さない場合も多々ある。」(公報第6欄)
「【0030】従って、本実施例では、出発地点から所定距離範囲内にある交差点を出発候補交差点として抽出し(ステップ220)、この抽出した交差点をそれぞれ後述する1つ以上のパラメータによって重み付けを行い、この重みによって最適な交差点をひとつ選定しようとするものである。」(公報第6欄)
「【0047】そして、このように計算された重み合計値Knが最も大きいものを選択することにより出発交差点が選定され、処理を終了する(ステップ260)。」(公報第7,8欄)
2.甲第2ないし4号証
甲第2号証ないし第4号証には、出発地から目的地までの経路を探索する際に、一方通行や通行禁止等の通行規制のある道路・交差点を考慮することにより、到達不可能な経路を探索しないことについて記載されている。
3.甲第5及び6号証
甲第5及び6号証には、出発地や目的地が道路上にない場合において、出発地や目的地から道路に垂線をを下ろして最も近い点を求め、この交点からリンク両端までの距離を算出して経路探索のコスト(重み)として用いることが記載されている。
(4)対比・判断
本件発明と、甲各号証に記載された発明とを対比すると、本件発明の 「前記地点設定手段で設定した出発地または目的地の情報から複数個の探索開始点または探索終了点を設定し、それぞれに固有の探索開始時の初期コストまたは探索終了点到達時の加算コストを与える探索開始終了点設定手段」については、いずれの号証にも記載がなく、また、これを示唆する記載もない。
本件発明は、上記手段を備えることにより、探索開始点または探索終了点をひとつに限定することなく出発地から目的地までの最適な経路を探索することができるものであり、
「このように本発明の第1の手段によると地点設定した位置近傍の複数の地点に固有の探索開始時の初期コストまたは探索終了点到達時の加算コストを与えた探索開始点または探索終了点を設定することによって、新たな入力作業を伴うことなく、順序づけられた複数の探索開始点および探索終了点の中から合理的な探索開始点および探索終了点を選択でき、かつ、行き過ぎ等の不適切な経路を選出することを防ぐことができる。」という、明細書記載の格別の効果を奏するものと認められる。
(5)申立人の主張について
申立人は、本件発明の上記手段に関し、異議申立書において本件発明の 構成Cと分説し、甲第1号証の第4頁右欄第7行〜第5頁第42行の記載を引用の上、甲第1号証にはC要件における「地点設定手段で設定した出発地または目的地の情報から複数個の探索開始点または探索終了点を設定し、それぞれに固有の探索開始時の初期コストまたは探索終了点到達時の加算コストを与える探索開始終了点設定手段」について記載されていると主張しているが、探索開始点または探索終了点を複数個設定することに関しては、前述のとおり、いずれの証拠にも記載がないから、各号証記載のものをいかに組み合わせても本件発明の構成を得ることはできず、申立人の主張は採用できない。
(6)むすび
以上のとおりであるから、特許異議の申立ての理由及び証拠によっては、本件請求項1ないし8に係る特許を取り消すことができない。また、他に本件請求項1ないし8に係る特許を取り消すべき理由を発見しない。
よって、結論のとおり決定する。
 
発明の名称 (54)【発明の名称】
推奨経路案内装置
(57)【特許請求の範囲】
【請求項1】交差点および道路の位置および接続関係を記録した道路ネットワーク記録手段と、出発地と目的地を設定する地点設定手段と、前記地点設定手段で設定した出発地または目的地の情報から複数個の探索開始点または探索終了点を設定し、それぞれに固有の探索開始時の初期コストまたは探索終了点到達時の加算コストを与える探索開始終了点設定手段と、前記探索開始終了点設定手段で初期コストが与えられた各探索開始点から、加算コストが与えられた各探索終了点までの経路を前記道路ネットワーク記録手段の情報から探索し、前記出発地から前記目的地まで最小コストで到達できる経路を求める探索手段と、前記探索手段で得られた経路を出力する出力手段とを備えたことを特徴とする推奨経路案内装置。
【請求項2】探索開始終了点設定手段は、選択された各交差点と出発地または目的地との距離に関する関数で探索開始時の初期コストまたは探索終了点到達時の加算コストを与えることを特徴とする請求項1記載の推奨経路案内装置。
【請求項3】探索開始終了点設定手段は、出発地と目的地の位置情報から近傍の道路リンクを各々1本以上選出し、そのリンクの両端の交差点を選択することを特徴とする請求項1記載の推奨経路案内装置。
【請求項4】探索開始終了点設定手段は、各道路リンクの両端の交差点のうち通行規制を遵守して到達可能な交差点のみを選択することを特徴とする請求項3記載の推奨経路案内装置。
【請求項5】探索開始終了点設定手段は、出発地または目的地から各道路リンク上の最も近い点とその点までの距離を求め、この距離の関数で探索開始時の初期コストまたは探索終了点到達時の加算コストを与えることを特徴とする請求項4記載の推奨経路案内装置。
【請求項6】探索開始終了点設定手段は、出発地または目的地から各道路リンク上の最も近い点を求め、その点から道路リンクの両端の交差点までの距離の関数で探索開始時の初期コストまたは探索終了点到達時の加算コストを与えることを特徴とする請求項4記載の推奨経路案内装置。
【請求項7】探索開始終了点設定手段は、出発地または目的地から各道路リンク上の最も近い点とその点までの距離を求め、この距離の関数で与えられるコストとその点から道路リンクの両端の交差点までの距離の関数で与えられるコストの和で探索開始時の初期コストまたは探索終了点到達時の加算コストを与えることを特徴とする請求項4記載の推奨経路案内装置。
【請求項8】探索開始終了点設定手段は、出発地および目的地から各探索開始点および探索終了点までの距離の関数で探索開始時の初期コストまたは探索終了点到達時の加算コストを与えることを特徴とする請求項4記載の推奨経路案内装置。
【請求項9】探索開始終了点設定手段は、車両の位置と向きから出発地側の探索開始点または出発地側の探索終了点を決定することを特徴とする請求項4記載の推奨経路案内装置。
【請求項10】探索開始終了点設定手段は、車両の向きと道路リンクのなす角度によるペナルティコストを出発地側の探索開始時の初期コストまたは出発地側の探索終了点到達時の加算コストに加えることを特徴とする請求項4記載の推奨経路案内装置。
【請求項11】探索開始終了点設定手段は、目的地と道路リンクの位置関係により右左折のペナルティコストを目的地側の探索開始時の初期コストまたは目的地側の探索終了点到達時の加算コストに加えることを特徴とする請求項4記載の推奨経路案内装置。
【発明の詳細な説明】
【0001】
【産業上の利用分野】
本発明は、車両がある地点から別の地点へ効率的に移動するために、その地点までの経路を自動的に選定して案内をする推奨経路案内装置に関する。
【0002】
【従来の技術】
従来の経路探索装置の地点設定手段としては、例えばユーザーが設定した地点に一番距離的に近い主要交差点を出発地または目的地としたり、特公平5ー6238で開示されているように複数の候補交差点の中からユーザーに選択させる方法があった。
【0003】
【発明が解決しようとする課題】
しかしながら、探索開始点および探索終了点を単純に出発地あるいは目的地に距離的に一番近い交差点に設定すると、ユーザーの意図しない地点から(あるいはユーザーの意図しない地点まで)経路を導出する可能性がある。ここで、その例を示す。図15(a)は従来の地点設定法では希望する経路が求められない場合の道路網の例(目的地側)を示す図、図15(b)は従来の地点設定法を用いて求めた選択経路の例を示す図である。図15(a)において、出発地はP(S)の方向にあり、ユーザーは網掛けの地点に行きたくて地点P(U)に目的地設定したとする。また、このとき地点P(U)から交差点N0、N1、N2への距離はそれぞれ次の関係があるとする。
【0004】
P(U)・N0間の距離 ＜ P(U)・N2間の距離 ＜ P(U)・N1間の距離
これらの条件において、探索終了点を地点P(U)に一番近い交差点とすると、交差点N0が探索終了点として選択され図15(b)の点線で示したような経路が選出される。このように目的地の前を通り過ぎて裏に誘導してしまうような経路を選出する可能性がある。また、地点設定とは別に複数の候補交差点から一つの交差点をユーザーに選択させることは、ユーザーが必ずしも入力地点付近の状況に詳しいとは限らないし、実際の入力手順として非常に煩わしいものとなる。そこで、新たな入力作業を伴うことなく、行き過ぎ等の不適切な経路を選出しないことを第1の目的とする。
【0005】
また、第1の目的を満たした上で、地点設定した位置に近い交差点が選択されることを第2の目的とする。
【0006】
また、ユーザーが設定した位置の近傍の道路上から離れた交差点に探索開始点または探索終了点が設定されることを防ぐことを第3の目的とする。
【0007】
また、第3の目的を満たした上で、目的地に到達するために最も効率的な方向へ誘導する経路を選出することを第4の目的とする。
【0008】
【課題を解決するための手段】
上記の問題を解決するために本発明は、第1の手段として前記地点設定手段で設定した出発地または目的地の情報から複数個の探索開始点または探索終了点を設定し、それぞれに固有の探索開始時の初期コストまたは探索終了点到達時の加算コストを与える探索開始終了点設定手段と、前記探索開始終了点設定手段で初期コストが与えられた各探索開始点から、加算コストが与えられた各探索終了点までの経路を前記道路ネットワーク記録手段の情報から探索し、前記出発地から前記目的地まで最小コストで到達できる経路を求める探索手段とを備えたことを特徴とする。
【0009】
また、第2の手段は前記地点設定手段において設定された出発地または目的地から前記探索開始終了点設定手段において設定された探索開始点または探索終了点までの距離の関数で探索開始時の初期コストまたは探索終了点到達時の加算コストを設定する処理を第1の手段における探索開始終了点設定手段に加えたことを特徴とする。
【0010】
また、第3の手段は前記地点設定手段で設定された出発地・目的地の位置情報から1本以上の道路を選択し、その両端の交差点のうち交通規制情報に従って到達できる交差点を選択する前記探索開始終了点設定手段を備えたことを特徴とする。
【0011】
また、第4の手段は前記地点設定手段であげられた出発地または目的地から各道路上の最も近い点を求め、出発地または目的地から最も近い点までの距離の関数で与えられるコストとその点から道路の両端の交差点に対する距離の関数で与えられるコストの和で探索開始時の初期コストまたは探索終了点到達時の加算コストを与える処理を第3の手段における前記探索開始終了点設定手段に加えたことを特徴とする。
【0012】
【作用】
本発明は、第1の手段によると、探索開始終了点設定手段において地点設定手段で設定した出発地または目的地の情報から、固有の探索開始時の初期コストまたは探索終了点到達時の加算コストを与えた複数個の探索開始点または探索終了点を設定して、出発地近傍の目的地方向側に探索開始点を、目的地近傍の出発地方向に探索終了点を作成することにより、順序づけられた複数の探索開始点および探索終了点の中から合理的な探索開始点および探索終了点を選択でき、かつ、出発地後方を経路の開始点にしたり目的地を行き過ぎるような経路を選出することを防ぐことができる。
【0013】
また第2の手段によると、第1の手段により実現された機能を満たした上で、出発地または目的地からの距離の関数で探索開始時の初期コストおよび探索終了点到達時の加算コストを与えることにより、遠く離れた探索開始点および探索終了点は大きなコストを持つことになるので、経路の開始点または終了点がそれぞれ出発地または目的地の位置から遠く離れることを防ぐことができる。
【0014】
また第3の手段によると、探索開始終了点設定手段において地点設定手段で入力された出発地または目的地の位置情報から近傍の1本以上の道路を選出し、その両端の交差点のうち交通規制情報に従って到達できる全ての交差点を探索開始点または探索終了点に設定することにより、ユーザーが設定した出発地または目的地に最も近い道路が長いリンクで近くに交差点がない場合でも他の道路上の交差点に探索開始点または探索終了点が設定されることを防ぐことができる。
【0015】
また第4の手段によると、第3の手段により実現された機能を満たした上で、出発地または目的地から最も近い各道路上の点を求め、出発地または目的地から最も近い点までの距離の関数で与えられるコストとその点から道路の両端の交差点に対する距離の関数で与えられるコストの和で探索開始時の初期コストまたは探索終了点到達時の加算コストを与えることにより、出発地から目的地へ到達するために不適切な探索開始点および探索終了点は大きなコストを持つことになるので、出発地から目的地へ向かうために適切な経路を選出することができる。
【0016】
【実施例】
以下、本発明の実施例を図面を用いて詳細に説明する。
【0017】
(実施例1)
図1は本発明の第1の実施例を示す推奨経路案内装置のブロック図である。図1において、101は交差点や道路の接続状況や座標・形状・属性など道路ネットワークに関する情報を地図データとして記録しておく道路ネットワーク記録手段、102は出発地および目的地の位置を入力する地点設定手段、103は前記地点設定手段102で入力された出発地および目的地の位置から地図データ上の探索開始点および探索終了点を設定する探索開始終了点設定手段、104は前記探索開始終了点設定手段103で設定された探索開始点から探索終了点までの経路を前記道路ネットワーク記録手段101に記憶された地図データを利用して選出する探索手段、105は前記探索手段104で求められた経路を画像や音声で出力する出力手段である。
【0018】
以上のように構成された第1の実施例の推奨経路案内装置について以下にその動作を説明する。図2(a)は第1の実施例における道路網の例を示す図、図2(b)は本道路網においてノード情報の例を示す図、図2(c)は本道路網においてリンク情報の例を示す図である。また、図3は本発明の第1の実施例における推奨経路案内装置の全体動作を示すフローチャート、図4は本発明の第1の実施例における地点設定処理のフローチャートである。
【0019】
図2(a)に示されるようにN1〜N10までの10個のノードとL1〜L9までの9本のリンクで表される道路網において、道路ネットワーク記録手段101には図2(b)に示されるように少なくともノードの位置情報「経度・緯度」とそのノードが接続するリンクの情報「接続リンク」を持ったノード情報と、図2(c)に示されるように少なくともリンクの両端のノードの情報「接続ノード1・接続ノード2」とリンクの形状情報「リンク形状差分データ」を持ったリンク情報が記憶されている。ここで、図2(a)において、△(S)は出発地、▽(D)は目的地、○はノード、実線はリンク(太さは重要度を表す)を示すものとする。また、(??km/h)の速度表記はその道路における平均走行速度である。ここでもう少し詳しく図2(b)のノード情報と図2(c)のリンク情報について説明しておく。まず、図2(b)のノード情報について述べる。「経度・緯度」情報は各ノードが実際に位置する座標の情報である。「隣接ノード」情報は地図を分割して持つ場合、道路が地図の境界上を横切るところに双方の地図内においてノードを作成するが、実際には同一のノードである隣の地図内のノードの情報を記録する。ただし、図2(a)の道路網の場合、簡単のため1地図としているので「隣接ノード」の情報は使用しない。「接続リンク」情報はそのノードがどのリンクにつながっているかを示す情報である。次に、図2(c)のリンク情報について述べる。「距離」情報は実際の道路上の距離を記録し、ここでは例えばメートル単位で示している。この情報は後述するリンク形状データから計算することもできるが計算時間の関係からデータとして持っておくことが望ましい。「コスト」情報は経路を選出する際の評価基準により異なる。ここでは、例えば旅行時間を最小にする経路を求めるものとして、そのリンクにおける旅行時間を0.1秒単位で持つものとする。(??km/h)はそのリンクにおける平均走行速度(時速)を示している。距離と時速からこのコストは計算できるが計算時間の関係から記録しておくことが望ましい。「接続ノード1、接続ノード2」はリンクの両端がどのノードにつながっているかを示している。「一方通行」情報は一方通行規制があればその規制を示す。図中、「N3→N2」という表記はノードN3からノードN2方向のみ通行可ということである。「リンク形状差分データ」情報は該当リンクが「接続ノード1」から「接続ノード2」の間でどのような形状をしているのかを「接続ノード1」の位置からの差分データで記録する。ここで、ユーザーは図2(a)の出発地△から目的地▽へ到達する経路を知りたいものと仮定する。このときの処理の詳細を図3、図4のフローチャートに従って以下に説明する。
【0020】
まず、図3のステップ301においてユーザーが出発地側地点設定処理を行う。この処理の詳細を図4に示してある。図4のステップ401においてユーザーは出発地の位置を例えばCRTに映し出された地図上にカーソルを表示し、カーソルを移動させることにより位置を決定し、所望の座標系に変換し位置情報を取得する。ステップ402では、設定した出発地の座標を中心に半径limiｔ_diｓｔの円の範囲(図2の点線の円:例えば50mの範囲)の地図情報を読み込むが、この場合は簡単のため1枚の地図内としている。ステップ403では、各ノード(N1〜N12)への距離を図2(b)の経度・緯度情報とステップ401で得た出発地の位置情報から順次算出し、距離の小さい順にN個(例えば4個)を選択して記録する。図2(a)のような場合、円の範囲内にノードN3しか存在しないので、ノードN3とそこまでの距離DN3を記憶する。次にステップ404にて出発地側かどうか判定し、出発地側であればステップ405に進み、ノードN3に探索開始点フラグを立てる。さらにステップ406において探索開始時の初期コストを一定値(例えば0)とする。以上でステップ301の処理を終了する。
【0021】
次に、ステップ302においてステップ301の処理と同様に目的地側地点設定処理を行う。出発地側と違う点は、ステップ404において目的地側であると判定されると、ステップ407に進み選択したノードに探索終了点フラグを立てる処理を行うことのみである。ステップ302の処理により、図2(a)の例では探索終了点としてノードN5、N7、N8の3点が選択される。
【0022】
次にステップ303において経路探索処理を実行する。図5に本発明の第1の実施例における経路探索処理のフローチャート、図6に本発明の第1の実施例における出発地側探索処理のフローチャート、図7に本発明の第1の実施例における目的地側探索処理のフローチャートを示す。以下、これらを用いて詳述する。ステップ501では、探索開始点フラグが立っているノードN3を出発地側探索候補状態とし、探索終了点フラグが立っているノードN5、N7、N8を目的地側探索候補状態とする。次にステップ502で、出発地側と目的地側探索候補状態以外のノードを未探索状態にして初期コストを無限大とし、初期化を行う。さらにステップ503において最大探索範囲制限を探索コストの値で設定する。この最大探索範囲制限は探索範囲に比べて十分大きいもの(例えば20000m)とする。ステップ504では、出発地側探索処理を実行する。この処理の詳細は図6に示してあるので、本フローチャートに従って説明する。
【0023】
まず、ステップ601では出発地側探索候補状態となっているノードで出発地側探索コストが一番小さいノードを基準交差点とする。ここでは、出発地側探索候補状態となっているノードはノードN3しかないので、ノードN3が基準交差点となる。ステップ602では目的地側の探索に移行すべきかどうか判定する。すなわち出発地側と目的地側探索範囲が接していない状態で、探索範囲がステップ503で設定した値を越えた場合目的地側探索に移行するため出発地側探索を終了する。また、基準交差点がなかった場合も、探索続行不能として出発地側探索処理を終了する。しかし、ここでは基準交差点が存在し、かつ最大探索範囲制限は十分大きいとしているのでステップ603に進む。ステップ603では、出発地側探索コストが出発地側経路確定コスト(初期値:無限大)を越えたかどうかで経路が確定したか判定する。最終的には目的地側探索処理を行って経路を決定する。いま、出発地側経路確定コストは無限大(初期値)のままなのでステップ604の処理に進む。ステップ604では基準交差点が隣の地図に接続したノード(隣接ノード)であるかどうか判定し、そうであればステップ614、615、616の処理を行い隣の地図の隣接ノードに基準交差点を移す処理を行うが、ここでは図2(a)の道路網は簡単のため1地図内を対象にしているので隣接ノードは考慮しないものとする。次にステップ605では、基準交差点に接続するリンクを順に調査対象リンクとする。ノードN3に接続するリンクは、図2(b)のノード情報よりL1、L2、L3、L4の4本である。まず、リンクL1を調査対象リンクとする。ステップ606でノードN3からノードN1ヘリンクL1を使って進むことができるかどうか調べる。もし、一方通行規制のためノードN3からノードN1へ進むことができなかった場合にはステップ611に進む。しかし、図2(c)のリンク情報よりリンクL1は双方向通行可のリンクであるので、ステップ607の処理に進む。ステップ607では、調査対象リンクの先のノードが目的地側探索候補状態か判定する。調査対象リンクの先のノードが目的地側探索候補状態であれば、ステップ617に進み出発地側と目的地側が接続したものとしてこの経路を記録するかどうか判定する。現在、調査対象リンクの先のノードN1は未探索状態であるので、ステップ608に進む。ステップ608では、ノードN1への到達コストを計算する。ノードN3は出発地であり初期コストが0であるので、
ノードN1への到達コスト←基準交差点への到達コスト[初期コスト:0]+調査対象リンクL1のコスト[43]
より、ノードN1への到達コストは「43」となる。次に、ステップ609ではノードN3に今までの最小コストで到達したか判定する。過去にもっと小さいコストで到達したことがあれば、ステップ611に進みノードN1に今回の探索結果を記憶しない。しかし、ノードN3は初期状態なので今回到達するのが初めてである。故に、ステップ610に進み、探索結果をノードN1に記憶する。記憶する内容は、
前ノード ← ノードN3
前リンク ← リンクL1
出発地側探索コスト ← 「43」
である。さらにノードN1を出発地側探索候補状態とする。次に、ステップ611において、ノードN3に接続する全てのリンクを調査対象リンクに選択したか判定する。まだ、リンクL2、L3、L4が残っているのでステップ605の処理に戻る。ステップ605では次に調査対象リンクとしてリンクL2を選択する。ステップ606において、リンクL2上をノードN3からノードN2に進めるかどうかチェックされるが、図2(c)のリンク情報よりこの方向への進行は可能な一方通行規制であるのでステップ607の処理に進む。ステップ607〜ステップ611までの処理を上記と同様に繰り返し、ノードN2に次の探索結果を記憶する。
【0024】
前ノード ← ノードN3
前リンク ← リンクL2
出発地側探索コスト ← 「180」
さらに、ノードN2を出発地側探索候補状態とする。ステップ611において、ノードN3に接続するリンクはリンクL3、L4が残っているので、ステップ605に戻り調査対象リンクをL3にする。しかし、ステップ606でリンクL3上はノードN3からノードN4へは一方通行規制により進めないのでステップ611の処理に進む。ゆえに、ノードN4には探索結果を記憶しない。ステップ611において、ノードN3に接続するリンクはリンクL4が残っているので、ステップ605に戻り調査対象リンクをL4にする。ステップ606までは従来通りであるが、ステップ607で調査対象リンクの先のノードN7は目的地側探索候補状態なので経路選出判定を行うためステップ617に進む。ここでは、経路の総コストを算出する。
【0025】
経路総コスト←基準交差点N3への到達コスト[初期コスト:0]+調査対象リンクのコスト[173]+目的地側探索候補状態の交差点N7のコスト[初期コスト:0]
故に、経路総コストは「173」と算出される。次に、ステップ618において、算出した経路総コストは過去に求められた経路の内、最小のコストであるかどうか判定される。もし最小コストでなければ、もっと小さいコストで出発地から目的地まで到達できる経路が求められていたものとしてステップ611に進み、今回の探索結果を記憶しない。しかし、今の場合、初めて出発地側と目的地側が接続したのでステップ619に進み、経路接続地点情報として次の情報を記憶する。
【0026】
出発地側接続交差点 ← ノードN3
目的地側接続交差点 ← ノードN7
出発地側経路確定コスト ← 「173」
目的地側経路確定コスト ← 「0」
経路接続総コスト ← 「173」
接続リンク ← リンクL4
次にステップ611に進み、基準交差点N3に接続するリンクを全て調査対象リンクとしたか判定する。ここでは、全て調査済みであるのでステップ612に進む。ステップ612では基準交差点N3を出発地側探索済み状態にして、ノードN3を基準とした探索処理を終了する。再びステップ601に戻り全てのノードを調査して、出発地側探索候補状態で出発地側探索コストが最小のノードを捜す。現在、ノードN3に接続している2つのノードN1、N2がそれぞれ出発地側探索コスト「43」、「180」を持ち出発地側探索候補状態となっている。現時点で最小な出発地側探索コストを持つ出発地側探索候補状態ノードはノードN1となる。故に基準交差点としてノードN1が選択される。次にステップ602〜ステップ608までは上記と同様に処理され(簡単のため探索対象地図は1地図のみと考えて隣接ノードは考慮しない)、リンクL1が調査対象リンクとなりノードN3への到達コストとして「43」+「43」が求められるが、ステップ610においてノードN3は探索開始点として初期コスト「0」が与えられているので今までの最小コストで到達していないと判定され、ステップ611へ進む。ステップ611ではノードN1につながった全ての接続リンクが調査されたとしてステップ612に進み、ノードN1を出発地側探索済み状態にする。また、ステップ601に戻り同様に次の基準交差点をノードN2とする。ここで、ステップ603においてノードN2の出発地側探索コスト「180」は出発地側経路確定コスト「173」よりも大きいので、ステップ613に進み出発地側経路探索処理で目的地側に接したことを示すフラグを立てる。以上でステップ504の出発地側探索処理を終了する。
【0027】
次にステップ505に進み、目的地側探索処理を実行する。この処理の詳細は図7に示してある。基本的に出発地側探索処理と異なる点が2点ある。1点は、ステップ706において基準交差点に接続する調査対象リンクが走行できるかどうかチェックする時、目的地側探索の場合は実際に車両が走行する向きとは逆の方向に探索を広げているので一方通行規制を逆に考える点である。もう1点は、ステップ707において目的地側探索範囲と出発地側探索範囲が接した状態の判定を調査対象リンクの先のノードが出発地側探索済み状態であることにより行う点である。これ以外は出発地側と同様の探索処理を行う。この場合、ノードN6、N9、N10がそれぞれ目的地側探索コスト[90」、「90」、「58」を持つ目的地側探索候補状態になり次の基準交差点としてノードN10が選択されたところで、目的地側経路確定コストが「0」であり目的地側探索コストが「58」となるのでステップ703の判定でステップ713の処理に進む。ここで、目的地側経路確定判定がなされ全経路が確定したことを示すフラグを立てる。以上でステップ505の目的地側探索処理を終了する。
【0028】
ステップ506では経路が確定したことを確認し、もし経路が確定されていなければ、ステップ507で探索失敗フラグを立てる。しかし、この場合ステップ713において全経路が確定したフラグが立っているのでステップ506で全経路確定したと判断されてステップ303の経路探索処理を終了する。
【0029】
ステップ304では探索失敗フラグが立っているかどうかチェックする。探索成功と判定されればステップ305に進み、例えば求められた経路を走行順に地図番号とリンク番号(方向性を含む)の列に直し経路構成を行う。さらにステップ306で求められた経路をCRTに写し出された地図に合わせて表示することにより経路をユーザーに示す。ステップ304において、探索失敗フラグが立っていると探索失敗と判定して、ステップ307で例えば経路が求められなかったことをユーザーに告知するなどの探索失敗時の処理を行う。この場合、経路地点接続情報から経路構成を行うとノードN3からノードN7へリンクL4を使って到達する経路が得られる。故に次の経路構成結果が残される。
【0030】
地図番号1 ← *(1地図なので不要)
リンク番号1 ← リンクL4
方向性 ← 「接続ノード1」から「接続ノード2」へ
以上のように、第1の実施例によれば複数の地点を出発地または目的地として選択することにより、例えば図2(a)の道路網の例でノードN3-リンクL4-ノードN7-リンクL7-ノードN8-リンクL5-ノードN5に至るような目的地の前を行き過ぎるような経路を出さないようにすることができる。
【0031】
(実施例2)
次に本発明の第2の実施例について説明する。本発明の第2の実施例を示す推奨経路案内装置のブロック図は第1の実施例と同様である。
【0032】
以上のように構成された第2の実施例の推奨経路案内装置について以下にその動作を説明する。図8(a)は第2の実施例における道路網の例を示す図、図8(b)は本道路網においてノード情報の例を示す図、図8(c)は本道路網においてリンク情報の例を示す図である。また、図9は本発明の第2の実施例における地点設定処理のフローチャートである。
【0033】
それでは、図8の道路網の例と図9の地点設定処理のフローチャートを用いて第1の実施例との差異を説明する。まず、図8(a)に示されるようにN1〜N12までの12個のノードとL1〜L11までの11本のリンクで表される道路網において、道路ネットワーク記録手段101には図8(b)に示されるようなノード情報と図8(c)に示されるようなリンク情報が記憶されている。ここで、各種記号は図2の場合と同様である。
【0034】
このようなネットワークの場合、図4のステップ403で選択される交差点数Nを4として第1の実施例と同様に経路を求めると、図8におけるノードN6が探索終了点の1つに含まれてしまうので、最終的に選択される経路は探索開始点群(ノードN3)と探索終了点群(ノードN6、N7、N9、N10)を結ぶ組合せのうち一番コストの小さい組合せの経路ノードN3-リンクL4-ノードN6が選択されてしまう。ゆえに、ノードN6までの経路しか求められないので目的地▽に到達するかなり手前までしか経路がわからない。そこで、第2の実施例として地点設定処理を図9のような処理に変更することによりこの問題を解決する。
【0035】
第2の実施例における地点設定処理と第1の実施例における地点設定処理の差異はステップ906の初期コストの設定にある。第1の実施例ではステップ406に示すように一律同じ値(0)としていたが、第2の実施例ではステップ906のように距離に比例した値を与える。ここで、ステップ906における比例係数mは正の実数である。なお、これは出発地SとノードN3間へ仮想リンクVL1を、また目的地DとノードN6、N7、N9、N10間へそれぞれ仮想リンクVL2、VL3、VL4、VL5を想定し、それぞれの仮想リンクに初期コスト相当の仮想リンクコストを割り付け、出発地Sから目的地Dまで仮想リンクを含んだ道路ネットワーク上で最小コスト経路を求めたときと同じ結果が地図データに処理を加えないで得られる特徴を持つ。
【0036】
例えば図8(a)中のリンクの中で平均走行速度が一番小さいものは時速10km/hであるが、初期コストとして直線距離を時速5km/hで走行した事に等しい値を与える。ゆえに、ノードN3には次の初期コストが与えられる。
【0037】
5(m)/5(km/h)×36=36(10-1秒)
同様に、各探索開始点・探索終了点とも以下の表1のような初期コストを持つ。
【0038】
【表1】

【0039】
探索開始点の探索終了点の組合せは計4通りある。以上の初期コストの基で全ての経路の組合せについて、これらの経路の総コストを比較すると表2のようになる。
【0040】
【表2】

【0041】
この場合、最小コスト経路はノードN3〜ノードN9までの経路となり、総コストは353となる。
【0042】
このように第2の実施例の特徴である地点設定手法を用いて、第1の実施例と同様に経路探索処理を行うことで探索開始点と探索終了点を結ぶ最短コスト経路であるノードN3-リンクL4-リンクL6-ノードN9を求めることができる。故に、第1の実施例の地点設定手法を使用した場合のように、目的地のかなり手前までしか経路が求められないという現象がなくなり、目的地に対してなるべく近くまでの経路を求めることができる。
【0043】
なお、図9のステップ906では距離に対して比例して初期コストを与えたが、比例でなければならない必要はない。図10に別の初期コストの付与例を示す。図10(a)に示すように非連続的でもよいし、図10(b)に示すように距離により比例乗数mを変更してもよい。
【0044】
(実施例3)
次に本発明の第3の実施例について説明する。本発明の第3の実施例を示す推奨経路案内装置のブロック図は第1の実施例と同様である。
【0045】
以上のように構成された第3の実施例の推奨経路案内装置について以下にその動作を説明する。図11(a)は第3の実施例における道路網の例を示す図、図11(b)は本道路網においてノード情報の例を示す図、図11(c)は本道路網においてリンク情報の例を示す図である。また、図12は本発明の第3の実施例における地点設定処理のフローチャートである。
【0046】
それでは、図11の道路網の例と図12の地点設定処理のフローチャートを用いて第1の実施例との差異を説明する。まず、図11(a)に示されるようにN1〜N13までの13個のノードとL1〜L12までの12本のリンクで表される道路網において、道路ネットワーク記録手段101には図11(b)に示され
るようなノー
ド情報と図11(c)に示されるようなリンク情報が記憶されている。ここで、各種記号は図2の場合と同様である。
【0047】
このようなネットワークの場合、第1および第2の実施例と同様に経路を求めると、図8におけるノードN5のみが探索終了点に選ばれてしまうので、最終的に選択される経路はノードN3-リンクL4-ノードN5が選択されてしまう。ゆえに、ノードN5までの経路しか求められないので目的地▽に到達するかなり手前までしか経路がわからない。そこで、第3の実施例として地点設定処理を図12のような処理に変更することによりこの問題を解決する。
【0048】
第3の実施例における地点設定処理と第1および第2の実施例における地点設定処理の差異は、探索開始点および探索終了点の設定基準をリンク上に置くかノード上に置くかにある。第1および第2の実施例では出発地または目的地の位置から近いノードを探索開始点または探索終了点として選択していたが、第3の実施例では出発地または目的地の位置から近いリンクを選択してそのリンク上の端のノードを探索開始点または探索終了点とする。以降に図12のフローチャートを用いて詳細に説明する。図12のステップ1201においてユーザーは出発地(目的地)の位置を例えばCRTに映し出された地図上にカーソルを表示し、カーソルを移動させることにより位置を決定して、所望の座標系に変換し位置情報を取得する。ステップ1202では、設定した出発地の座標を中心に半径limiｔ_diｓｔの円の範囲(図2の点線の円:例えば50mの範囲)の地図情報を読み込むが、この場合は簡単のため1枚の地図内としている。ステップ1203では、各リンク(L1〜L12)への距離(各差分データ成分への一番近い距離)を図11(b)の経度・緯度情報および図11(c)のリンク形状差分データとステップ1201で得た出発地(目的地)の位置情報から順次算出し、距離の小さい順にN本(例えば2本)を選択して垂線とリンクの交点の位置および距離を記録する。図11(a)のような場合、出発地側ではリンクL1上の点P1の位置座標と距離DP1、およびリンクL3上の点P2の位置座標と距離DP2が記録され、目的地側ではリンクL8上の点P3の位置座標と距離DP3、およびリンクL11上の点P4の位置座標と距離DP4が記録される。次にステップ1204にて出発地側かどうか判定される。出発地側であればステップ1205に進み、選択されたリンクL1上の点P1から一方通行規制に従って到達できるノードN1、N3および選択されたリンクL3上の点P2から一方通行規制に従って到達できるノードN3を探索開始点とする。ノードN1には交点P1からノードN1までの距離を、ノードN3には交点P1からノードN3までの距離または交点P2からノードN3までの距離の短い方を記憶する。さらにステップ1206において選択したノードN1、N3に探索開始点フラグをたてる。ステップ1204において目的地側であればステップ1208に進み、選択されたリンクL8上の点P3に一方通行規制に従って進入できるノードN7および選択されたリンクL11上の点P4に一方通行規制に従って進入できるノードN11を探索開始点とする。ノードN7には交点P3からノードN7までの距離を、ノードN11には交点P4からノードN11までの距離を記録する。さらにステップ1209において選択したノードN7、N11に探索終了点フラグをたてる。最後にステップ1207において、探索開始点(ノードN1、N3)および探索終了点(ノードN7、N11)に初期コストとして一定値(例えば0)を付与する。以上で地点設定処理を終了する。
【0049】
ここで、探索開始点の探索終了点の組合せは計4通りある。全ての経路の組合せについて、これらの経路の総コストを比較すると表3のようになる。
【0050】
【表3】

【0051】
この場合、最小コスト経路はノードN3〜ノードN7までの経路となり、総コストは266となる。
【0052】
このように、第3の実施例の特徴である地点設定手法を用いて、第1および第2の実施例と同様に経路探索処理を行う事により、最小コスト経路としてノードN3-リンクL4-リンクL6-ノードN7を求めることができる。故に、第1および第2の実施例の地点設定手法を使用した場合のように、目的地付近の道路とは離れた道路上の交差点までの経路を求めてしまう現象がなくなり、目的地へ到達するために適した経路を求めることができる。
【0053】
なお、図12のステップ1205ではノードN3には交点P1からノードN3までの距離または交点P2からノードN3までの距離の短い方を記録したが、出発地からの総距離の短い方を記録しても良いし、リンクに出るまでの距離の短い方を記録してもよい。また、予め出発地からリンク上に下ろした垂線との交点と探索開始点との間の形状データおよび目的地からリンク上に下ろした垂線との交点と探索終了点との間の形状データを保持して置くことによりリンク途中までの経路表示や誘導を行ってもよい。また、リンク形状に垂線が下ろせない場合、各形状データの曲折点への距離中、一番距離が小さい点をリンクとの交点として採用してもよい。
【0054】
(実施例4)
次に本発明の第4の実施例について説明する。本発明の第4の実施例を示す推奨経路案内装置のブロック図は第1の実施例と同様である。
【0055】
以上のように構成された第4の実施例の推奨経路案内装置について以下にその動作を説明する。図13(a)は第4の実施例における道路網の例を示す図、図13(b)は本道路網においてノード情報の例を示す図、図13(c)は本道路網においてリンク情報の例を示す図である。また、図14は本発明の第4の実施例における地点設定処理のフローチャートである。
【0056】
それでは、図13の道路網の例と図14の地点設定処理のフローチャートを用いて第3の実施例との差異を説明する。まず、図13(a)に示されるようにN1〜N12までの12個のノードとL1〜L11までの11本のリンクで表される道路網において、道路ネットワーク記録手段101には図13(b)に示されるようなノード情報と図13(c)に示されるようなリンク情報が記憶されている。ここで、各種記号は図2の場合と同様である。
【0057】
このようなネットワークの場合、第1および第2の実施例と同様に経路を求めると、探索開始点としてノードN3が、探索終了点としてノードN6がそれぞれ選択されるので、最終的に選択される経路はノードN3とノードN6を結ぶ経路ノードN3-リンクL4-リンクL6-ノードN6が選択されてしまう。ゆえに、ノードN6までの経路しか求められないので目的地▽に到達するかなり手前までしか経路がわからない。また、第3の実施例と同様に経路を求めると、探索開始点としてノードN3が、探索終了点としてノードN5,N8,N9,N12が選択されるので、最終的に選択される経路は探索開始点群(ノードN3)と探索終了点群(ノードN5,N8,N9,N12)を結ぶ最小コスト経路である経路ノードN3-リンクL4-ノードN5が選択されてしまう。ゆえに、ノードN5を通り地点P3に到達する経路しか求められないので目的地▽に至るにふさわしい経路が求められない。そこで、第4の実施例として地点設定処理を図14のような処理に変更することによりこの問題を解決する。
【0058】
第4の実施例における地点設定処理と第3の実施例における地点設定処理の差異はステップ1407の初期コストの設定にある。第3の実施例ではステップ1207に示すように一律同じ値(0)としていたが、第4の実施例ではステップ1407のようにリンクに下ろした垂線の距離に比例したコストとリンク上を走行するためのコストの和で初期コストを与える。ここで、ステップ1407における比例係数m1、m2は正の実数である。なお、これは出発地SからリンクL1へ下ろした垂線を仮想リンクVL1(リンクL1との交点をP1)、リンクL3に下ろした垂線を仮想リンクVL2(リンクL3との交点をP2)、また目的地DからリンクL5に下ろした垂線を仮想リンクVL3(リンクL5との交点をP3)、リンクL10に下ろした垂線を仮想リンクVL4(リンクL10との交点をP4)として、それぞれの仮想リンクに初期コスト相当の仮想リンクコストを割り付け、出発地Sから目的地Dまで仮想リンクを含んだ道路ネットワーク上で最小コスト経路を求めた場合と同じ結果が地図データに処理を加えなくても得られる特徴を持つ。
【0059】
例えば図13(a)中のリンクの中で平均走行速度が一番小さいものは時速10km/hであるが、仮想リンクコストとして仮想リンク上を時速5km/hで走行した事に等しい値を与える。また、仮想リンクから通常リンク上へ出た地点から次の交差点まで進むコストとして、通常リンク全体のコストを走行した距離の比で分配した値を与える。ゆえに、ノードN3には次の初期コストが与えられる。
[1] 5(m)/5(km/h)×36 …仮想リンコスト
+ 43 (リンクL1のコスト)/60(m)×5(m) …リンクL1上の分配コスト
≒ 40 (10-1秒) [リンクL1経由の初期コスト]
[2] 5(m)/5(km/h)×36 …仮想リンクコスト
+ 252(リンクL3のコスト)/140(m)×5(m)…リンクL3上の分配コスト
≒ 45 (10-1秒) [リンクL3経由の初期コスト]
リンクL1経由の方がリンクL3経由よりも初期コストが小さいのでノードN3にはリンクL1経由の情報が残される。故に初期コストは40となる。
【0060】
同様に、各探索開始点・探索終了点とも以下の表4のような初期コストを持つ。
【0061】
【表4】

【0062】
探索開始点の探索終了点の組合せは計8通りある。以上の初期コストの元で全ての経路の組合せについて、これらの経路の総コストを比較すると表5のようになる。
【0063】
【表5】

【0064】
この場合、最小コスト経路はノードN3〜ノードN8までの経路となり、総コストは436となる。
【0065】
このように第4の実施例の特徴である地点設定手法を用いて、第1の実施例と同様に経路探索処理を行うことで探索開始点と探索終了点を結ぶ最短コスト経路であるノードN3-リンクL4-リンクL6-リンクL8-ノードN8を求めることができる。故に、第1、第2、第3の実施例の地点設定手法を使用した場合のように、目的地へ到達するには不適切な経路を選択する現象がなくなり、目的地に対して適切な経路を求めることができる。
【0066】
なお、図14のステップ1407ではリンクまでの距離に対して比例して仮想リンクコストコストを与えたが、図10(a)に示すように非連続的でもよいし、図10(b)に示すように距離により比例乗数mを変更してもよい。また、リンクへの垂線との交点からリンクの端ノードまでのコストとして、リンク全体のコストを距離で分配したが、特別な仮想走行速度を想定してリンクコストを付与し直してもよい。また、ノードまでの直線距離に比例して初期コストを与えてもよい。さらにこの場合、ノードまでの直線距離に対して図10(a)に示すように非連続的でもよいし、図10(b)に示すように直線距離により比例乗数を変更してもよい。また、目的地から垂線をおろしたリンクを基準にした位置関係、すなわち経路上を走行してそのリンクから目的地へ向かう場合左右どちらに曲がるかによって決定する右左折のペナルティコストを目的地側の初期コストに加えてもよい。
【0067】
さらに、第1から第4の実施例共に、車両の現在位置と向きを取得して出発地側の探索開始点の設定を行なってもよい。例えば、車両がリンク上に存在しなければ取得した位置情報を基に上記実施例に従って出発地側の探索開始点を設定してもよいし、車両がリンク上に存在すれば車両の前方方向のリンクの行き先ノードを出発地側の探索開始点に設定してもよい。また、探索開始点にリンク走行分に相当する初期コストを持たせてもよい。また、車両がリンク上に存在した場合で一方通行規制に従って車両の前方方向と反対向きに進むことが可能な場合は、そのリンクの行き先ノードとは反対側のノードを出発地側の探索開始点に加えてもよい。その場合、リンク走行分に相当するリンクコストとUターンペナルティコストを加えたコストを初期コストとして与えてもよい。さらに、リンク上に現在位置が存在しない場合、車両の向きとリンクの向きがなす角度により初期コストにペナルティコストを加えてもよい。
【0068】
最後に、探索時に交差点で曲がる角度や道なりから外れることなどによりコストを加算してもよいし、探索する評価基準(コストの対象)は例えば料金や走り易さ等の概念を含んでもよい。また、探索法は出発地と目的地双方から探索する双方向探索を用いたが、出発地または目的地のいずれか一方から探索する一方向探索でもよい。その場合、探索の終了点側の初期コストはその点が探索候補状態になったとき到達コストに加算コストとして加えられる。その結果、加算コストを含んだ総コストが最小となる経路が選出される。さらに一方向探索の場合、目的地側を探索開始点として出発地側へ向かって探索を広げてもよい。また、探索法については階層化された地図を用いて探索を行なってもよいし、ダイクストラ法でなくても最小コスト経路を求められる方法であればよい。また、出力手段は経路を表示するだけでなく、車両の現在位置を取得し曲がるべき交差点の手前で音声により誘導案内を行ってもよい。また、出発地側と目的地側の地点設定法は同一でなくてもよい。
【0069】
【発明の効果】
このように本発明の第1の手段によると地点設定した位置近傍の複数の地点に固有の探索開始時の初期コストまたは探索終了点到達時の加算コストを与えた探索開始点または探索終了点を設定することによって、新たな入力作業を伴うことなく、順序づけられた複数の探索開始点および探索終了点の中から合理的な探索開始点および探索終了点を選択でき、かつ、行き過ぎ等の不適切な経路を選出することを防ぐことができる。
【0070】
また、第2の手段によると第1の手段で選択した複数の交差点に地点設定した位置からの距離の関数で初期コストを与えてやることにより、地点設定した位置から遠くの交差点が経路の開始点や終了点となることを防ぐことができる。
【0071】
さらに、第3の手段によると地点設定した位置近傍の1本以上の道路上の両端交差点のなかで通行規制を遵守して通ることができる交差点を探索開始点・探索終了点として設定することにより、地点設定位置の近傍道路に接続していない交差点が経路の開始点や終了点となることを防ぐことができる。
【0072】
最後に、第4の手段によると第3の手段で選択した複数の交差点に、地点設定位置の近傍道路までの距離の関数で与えられたコストと前記近傍道路上の走行距離の関数で与えられたコストの和で初期コストを与えることにより、出発地から目的地まで到達するために最も適切な経路を選択することができる。
【図面の簡単な説明】
【図1】
本発明の第1から第4の実施例を示す推奨経路案内装置のブロック図
【図2】
(a)は本発明の第1の実施例における道路網の例を示す図
(b)は本発明の第1の実施例における道路網においてノード情報データの例を示す図
(c)は本発明の第1の実施例における道路網においてリンク情報データの例を示す図
【図3】
本発明の第1から第4の実施例における推奨経路案内装置の全体動作を示すフローチャート
【図4】
本発明の第1の実施例における地点設定処理のフローチャート
【図5】
本発明の第1から第4の実施例における経路探索処理のフローチャート
【図6】
本発明の第1から第4の実施例における出発地側探索処理のフローチャート
【図7】
本発明の第1から第4の実施例における目的地側探索処理のフローチャート
【図8】
(a)は本発明の第2の実施例における道路網の例を示す図
(b)は本発明の第2の実施例における道路網においてノード情報データの例を示す図
(c)は本発明の第2の実施例における道路網においてリンク情報データの例を示す図
【図9】
本発明の第2の実施例における地点設定処理のフローチャート
【図10】
(a)は本発明の第2、第4の実施例とは別の初期コストの付与例を示す図(1)
(b)は本発明の第2、第4の実施例とは別の初期コストの付与例を示す図(2)
【図11】
(a)は本発明の第3の実施例における道路網の例を示す図
(b)は本発明の第3の実施例における道路網においてノード情報データの例を示す図
(c)は本発明の第3の実施例における道路網においてリンク情報データの例を示す図
【図12】
本発明の第3の実施例における地点設定処理のフローチャート
【図13】
(a)は本発明の第4の実施例における道路網の例を示す図
(b)は本発明の第4の実施例における道路網においてノード情報データの例を示す図
(c)は本発明の第4の実施例における道路網においてリンク情報データの例を示す図
【図14】
本発明の第4の実施例における地点設定処理のフローチャート
【図15】
(a)は従来の地点設定法では希望する経路が求められない場合の道路網の例(目的地側)を示す図
(b)は従来の地点設定法を用いて求めた選択経路の例を示す図
【符号の説明】
101 道路ネットワーク記憶手段
102 地点設定手段
103 探索開始終了点設定手段
104 探索手段
105 出力手段
 
訂正の要旨 訂正の内容
1.訂正事項a
特許請求の範囲の請求項1における「前記探索開始終了点設定手段で設定した探索開始点から探索終了点までの経路を前記道路ネットワーク記録手段の情報から探索する探索手段と、」とあるのを、「前記探索開始終了点設定手段で初期コストが与えられた各探索開始点から、加算コストが与えられた各探索終了点までの経路を前記道路ネットワーク記録手段の情報から探索し、前記出発地から前記目的地まで最小コストで到達できる経路を求める探索手段と、」と訂正する。
2.訂正事項b
特許明細書の段落番号【0008】を、
「【課題を解決するための手段】
上記の問題を解決するために本発明は、第1の手段として前記地点設定手段で設定した出発地または目的地の情報から複数個の探索開始点または探索終了点を設定し、それぞれに固有の探索開始時の初期コストまたは探索終了点到達時の加算コストを与える探索開始終了点設定手段と、前記探索開始終了点設定手段で初期コストが与えられた各探索開始点から、加算コストが与えられた各探索終了点までの経路を前記道路ネットワーク記録手段の情報から探索し、前記出発地から前記目的地まで最小コストで到達できる経路を求める探索手段とを備えたことを特徴とする。」と訂正する。
3.訂正事項c
特許明細書の段落番号【0048】を、
「【0048】
第3の実施例における地点設定処理と第1および第2の実施例における地点設定処理の差異は、探索開始点および探索終了点の設定基準をリンク上に置くかノード上に置くかにある。第1および第2の実施例では出発地または目的地の位置から近いノードを探索開始点または探索終了点として選択していたが、第3の実施例では出発地または目的地の位置から近いリンクを選択してそのリンク上の端のノードを探索開始点または探索終了点とする。以降に図12のフローチャートを用いて詳細に説明する。図12のステップ1201においてユーザーは出発地(目的地)の位置を例えばCRTに映し出された地図上にカーソルを表示し、カーソルを移動させることにより位置を決定して、所望の座標系に変換し位置情報を取得する。ステップ1202では、設定した出発地の座標を中心に半径limiｔ_diｓｔの円の範囲(図2の点線の円:例えば50mの範囲)の地図情報を読み込むが、この場合は簡単のため1枚の地図内としている。ステップ1203では、各リンク(L1〜L12)への距離(各差分データ成分への一番近い距離)を図11(b)の経度・緯度情報および図11(c)のリンク形状差分データとステップ1201で得た出発地(目的地)の位置情報から順次算出し、距離の小さい順にN本(例えば2本)を選択して垂線とリンクの交点の位置および距離を記録する。図11(a)のような場合、出発地側ではリンクL1上の点P1の位置座標と距離DP1、およびリンクL3上の点P2の位置座標と距離DP2が記録され、目的地側ではリンクL8上の点P3の位置座標と距離DP3、およびリンクL11上の点P4の位置座標と距離DP4が記録される。次にスデップ1204にて出発地側かどうか判定される。出発地側であればステップ1205に進み、選択されたリンクL1上の点P1から一方通行規制に従って到達できるノードN1、N3および選択されたリンクL3上の点P2から一方通行規制に従って到達できるノードN3を探索開始点とする。ノードN1には交点P1からノードN1までの距離を、ノードN3には交点P1からノードN3までの距離または交点P2からノードN3までの距離の短い方を記憶する。さらにステップ1206において選択したノードN1、N3に探索開始点フラグをたてる。ステップ1204において目的地側であればステップ1208に進み、選択されたリンクL8上の点P3に一方通行規制に従って進入できるノードN7および選択されたリンクL11上の点P4に一方通行規制に従って進入できるノードN11を探索開始点とする。ノードN7には交点P3からノードN7までの距離を、ノードN11には交点P4からノードN11までの距離を記録する。さらにステップ1209において選択したノードN7、N11に探索終了点フラグをたてる。最後にステップ1207において、探索開始点(ノードN1、N3)および探索終了点(ノードN7、N11)に初期コストとして一定値(例えば0)を付与する。以上で地点設定処理を終了する。」と訂正する。
異議決定日 2002-09-03 
出願番号 特願平5-110351
審決分類 P 1 652・ 121- YA (G01C)
最終処分 維持  
前審関与審査官 千馬 隆之、太田 恒明  
特許庁審判長 大森 蔵人
特許庁審判官 菅澤 洋二
紀本 孝
登録日 2000-02-04 
登録番号 特許第3027899号(P3027899)
権利者 松下電器産業株式会社
発明の名称 推奨経路案内装置  
代理人 内藤 浩樹  
代理人 小笠原 史朗  
代理人 岩橋 文雄  
代理人 坂口 智康  
代理人 岩橋 文雄  
代理人 内藤 浩樹  
代理人 坂口 智康  
代理人 小笠原 史朗  

プライバシーポリシー   セキュリティーポリシー   運営会社概要   サービスに関しての問い合わせ