経路探索装置、経路探索システム、プログラム、及び経路探索方法
始点から終点までの移動に用いるべき移動経路を探索する経路探索装置であって、始点及び終点を含む全体領域を分割した複数のブロック領域のそれぞれに対応して、当該ブロック領域に含まれるブロック内経路を用いて当該ブロック領域を通過する場合に要する移動コストである内経路コストを管理するブロック管理部と、全体領域における始点及び終点の位置に基づき、複数のブロック領域を選択するブロック選択部と、ブロック選択部が選択する複数のブロック領域のそれぞれに含まれるブロック内経路を経由して、始点から終点に至る移動経路を生成する移動経路生成部と、当該移動経路に含まれるブロック内経路に対応する内経路コストに基づき、当該移動経路を用いて移動する場合の移動コストである経路移動コストを算出する移動コスト算出部とを備える。
【発明の詳細な説明】
【技術分野】
本発明は、経路探索装置、経路探索システム、プログラム、及び経路探索方法に関する。特に本発明は、始点から終点までの移動に用いるべき移動経路を探索する経路探索装置に関する。
【背景技術】
従来、複数のノードを利用して経路探索を行う方法が知られている。当該方法においては、それぞれのノード間の距離等に基づいて経路探索を行う。
しかし、始点と終点との間に多くのノードが存在する場合、経路探索に必要な演算量が増大するため、経路探索に時間がかかる場合があった。そのため、従来、経路探索を効率よく行うのが困難な場合があった。
そこで本発明は、上記の課題を解決することのできる経路探索装置、経路探索システム、プログラム、及び経路探索方法を提供することを目的とする。この目的は特許請求の範囲における独立項に記載の特徴の組み合わせにより達成される。また従属項は本発明の更なる有利な具体例を規定する。
【発明の開示】
このような目的を達成するために、本発明の第１の形態によれば、始点から終点までの移動に用いるべき移動経路を探索する経路探索装置であって、始点及び終点を含む全体領域を分割した複数のブロック領域のそれぞれに対応して、当該ブロック領域に含まれるブロック内経路を用いて当該ブロック領域を通過する場合に要する移動コストである内経路コストを管理するブロック管理部と、全体領域における始点及び終点の位置に基づき、複数のブロック領域を選択するブロック選択部と、ブロック選択部が選択する複数のブロック領域のそれぞれに含まれるブロック内経路を経由して、始点から終点に至る移動経路を生成する移動経路生成部と、移動経路に含まれるブロック内経路に対応する内経路コストに基づき、移動経路を用いて移動する場合の移動コストである経路移動コストを算出する移動コスト算出部とを備える。
また、少なくとも一部のブロック領域は、当該ブロック領域の内部と外部とを結ぶ、少なくとも３個の出入口を有し、ブロック管理部は、少なくとも一部のブロック領域のそれぞれに対応して、それぞれが少なくとも３個の出入口のうちの２個を一端及び他端とし、互いに異なる少なくとも２個のブロック内経路を管理してよい。
また、それぞれのブロック領域は、当該ブロック領域と、全体領域において当該ブロック領域に隣接するブロック領域とを接続する複数の出入口を有し、ブロック管理部は、複数の出入口のうちの２個の出入口の組み合わせを、ブロック内経路として管理し、当該２個の出入口の間における移動コストを、当該ブロック内経路に対応する内径路コストとして管理し、ブロック選択部は、複数のブロック領域の少なくとも一部として、互いに隣接する２個のブロック領域を選択し、移動経路生成部は、２個のブロック領域に対し、それぞれのブロック領域におけるブロック内経路を、当該２個のブロック領域を接続する出入口を介して接続することにより、移動経路の少なくとも一部を生成してよい。
また、移動経路生成部は複数の移動経路を生成し、移動コスト算出部は、複数の移動経路に対し、それぞれの経路移動コストを算出し、経路検索装置は、それぞれの経路移動コストに基づき、複数の移動経路から一の移動経路を選択する経路選択部を更に備えてよい。
また、ブロック管理部は、複数のブロック領域を挟んで互いに離間されたブロック領域である２個の離間ブロックに対し、当該２個の離間ブロックの間の移動コストである離間移動コストを更に管理し、ブロック選択部は、複数のブロック領域の少なくとも一部として、始点を含むブロック領域である始点ブロックと、終点を含むブロック領域である終点ブロックとを選択し、移動経路生成部は、始点ブロックに含まれるブロック内経路に基づき、始点から一の離間ブロックに至る始点経路を生成し、終点ブロックに含まれるブロック内経路に基づき、他の離間ブロックから終点に至る終点経路を生成することにより、始点経路及び終点経路を経由する移動経路を生成し、移動コスト算出部は、始点経路及び終点経路のそれぞれに含まれるブロック内経路に対応する内経路コストに基づき、始点経路及び終点経路における移動コストである始点移動コスト及び終点移動コストのそれぞれを算出し、始点移動コスト、終点移動コスト、及び離間移動コストに基づき、経路移動コストを算出してよい。
また、ブロック選択部は、始点ブロックの近傍のブロック領域である始点近傍ブロックと、終点ブロックの近傍のブロック領域である終点近傍ブロックと、を更に選択し、移動経路生成部は、始点ブロック及び始点近傍ブロックのそれぞれに含まれるブロック内経路を経由することにより、始点から一の離間ブロックに至る始点経路と、終点近傍ブロック及び終点ブロックのそれぞれに含まれるブロック内経路を経由することにより、他の離間ブロックから終点に至る終点経路とを生成してよい。
また、ブロック管理部は、全体領域を分割した複数のブロック領域である複数の全体分割ブロックと、複数の全体分割ブロックのそれぞれを更に分割した複数の領域に対応する複数のブロック領域である複数の部分分割ブロックとそれぞれに対応する内経路コストを管理し、ブロック選択部は、複数のブロック領域の少なくとも一部として、始点を含む部分分割ブロックである始点ブロックと、終点を含む部分分割ブロックである終点ブロックと、それぞれが始点及び終点のいずれも含まない全体分割ブロックである一又は複数の中間ブロックとを選択し、移動経路生成部は、始点ブロックに含まれるブロック内経路に基づく始点経路と、一又は複数の中間ブロックのそれぞれに含まれるブロック内経路に基づく中間経路と、終点ブロックに含まれるブロック内経路に基づく終点経路とをそれぞれ生成することにより、始点経路、中間経路、及び終点経路を経由する移動経路を生成してよい。
また、ブロック選択部は、始点ブロックの近傍の部分分割ブロックである始点近傍ブロックと、終点ブロックの近傍の部分分割ブロックである終点近傍ブロックとを更に選択し、移動経路生成部は、始点ブロック及び始点近傍ブロックのそれぞれに含まれるブロック内経路を経由することにより、始点からいずれかの中間ブロックに至る始点経路と、終点近傍ブロック及び終点ブロックのそれぞれに含まれるブロック内経路を経由することにより、いずれかの中間ブロックから終点に至る終点経路とを生成してよい。
また、移動経路の途中に経由すべき経由点の指定を受け付ける受付部を更に備え、ブロック選択部は、複数のブロック領域の一部として、経由点を含む部分分割ブロックである経由点ブロックを更に選択し、移動経路生成部は、経由点ブロックに含まれるブロック内経路に更に基づき、移動経路を生成してよい。
また、ブロック選択部は、経由点ブロックの近傍の部分分割ブロックである経由点近傍ブロックを更に選択し、移動経路生成部は、経由点ブロック及び経由点近傍ブロックのそれぞれに含まれるブロック内経路を経由することにより、いずれかの中間ブロックから、経由点を経由して、いずれかの中間ブロックに至る経由経路を生成し、経由経路を経由する移動経路を生成してよい。
また、ブロック管理部は、ブロック内経路沿いに位置する施設を示すブロック施設情報を更に管理し、経路検索装置は、移動経路が経由するブロック内経路に対応するブロック施設情報に基づき、当該移動経路沿いに位置する施設を示す経路施設情報を生成する施設情報生成部と、移動経路を示す情報を、当該移動経路に対応する経路施設情報と対応付けて出力する情報出力部とを更に備えてよい。
また、ブロック管理部は、ブロック内経路を用いて移動した場合の所要時間の誤差範囲を示すブロック内誤差情報を更に管理し、経路検索装置は、移動経路が経由するブロック内経路に対応するブロック内誤差情報に基づき、当該移動経路を用いて移動した場合の所要時間の誤差範囲を示す経路誤差情報を算出する誤差情報算出部と、移動経路を示す情報を、当該移動経路に対応する経路誤差情報と対応付けて出力する情報出力部とを更に備えてよい。
また、ブロック管理部は、経路検索装置の外部に設けられたサーバから、内径路コストを更新するための更新コスト情報を受け取り、当該更新コスト情報に基づき、少なくとも一部の内径路コストを更新してよい。
また、ブロック選択部は、予め定められた形状のテンプレート図形を格納するテンプレート格納部と、テンプレート図形を、始点及び終点を含む大きさに拡大又は縮小する図形サイズ変更部と、拡大又は縮小されたテンプレート図形を、始点及び終点の位置を基準として全体領域上に配置し、配置されたテンプレート図形を含む複数のブロック領域を選択する選択実行部とを有してよい。
また、全体領域の少なくとも一部の状態を取得する状態取得部を更に備え、ブロック管理部は、少なくとも一部のブロック内経路を、当該ブロック内経路の使用の可否を示す使用可否情報と対応付けて管理し、かつ、状態取得部が取得した状態に基づき、当該ブロック内経路に対する使用可否情報を変更し、移動経路生成部は、使用可否情報に基づいてブロック内経路の使用の可否を判定することにより、使用可能なブロック内経路に基づき、移動経路を生成してよい。
本発明の第２の形態によれば、始点から終点までの移動に用いるべき移動経路を探索する経路探索システムであって、始点及び終点を含む全体領域を分割した複数のブロック領域の少なくとも一部に対応して、当該ブロック領域に含まれるブロック内経路を用いて当該ブロック領域を通過する場合に要する移動コストである内経路コストを更新するための更新コスト情報を格納するサーバと、サーバと通信する端末とを備え、端末は、複数のブロック領域のそれぞれに対応して、当該ブロック領域に含まれるブロック内経路を用いて当該ブロック領域を通過する場合に要する内経路コストを管理し、かつ、サーバから受け取る更新コスト情報に基づき、少なくとも一部のブロック領域に対応する内径路コストを更新するブロック管理部と、全体領域における始点及び終点の位置に基づき、複数のブロック領域を選択するブロック選択部と、ブロック選択部が選択する複数のブロック領域のそれぞれに含まれるブロック内経路を経由して、始点から終点に至る移動経路を生成する移動経路生成部と、移動経路に含まれるブロック内経路に対応する内経路コストに基づき、移動経路を用いて移動する場合の移動コストである経路移動コストを算出する移動コスト算出部とを有する。
本発明の第３の形態によれば、始点から終点までの移動に用いるべき移動経路を探索するプログラムであって、始点及び終点を含む全体領域を分割した複数のブロック領域のそれぞれに対応して、当該ブロック領域に含まれるブロック内経路を用いて当該ブロック領域を通過する場合に要する移動コストである内経路コストを管理するブロック管理部と、全体領域における始点及び終点の位置に基づき、複数のブロック領域を選択するブロック選択部と、ブロック選択部が選択する複数のブロック領域のそれぞれに含まれるブロック内経路を経由して、始点から終点に至る移動経路を生成する移動経路生成部と、移動経路に含まれるブロック内経路に対応する内経路コストに基づき、移動経路を用いて移動する場合の移動コストである経路移動コストを算出する移動コスト算出部とを備える。
本発明の第４の形態によれば、始点から終点までの移動に用いるべき移動経路を探索する経路探索方法であって、始点及び終点を含む全体領域を分割した複数のブロック領域のそれぞれに対応して、当該ブロック領域に含まれるブロック内経路を用いて当該ブロック領域を通過する場合に要する移動コストである内経路コストを管理するブロック管理段階と、全体領域における始点及び終点の位置に基づき、複数のブロック領域を選択するブロック選択段階と、ブロック選択部が選択する複数のブロック領域のそれぞれに含まれるブロック内経路を経由して、始点から終点に至る移動経路を生成する移動経路生成段階と、移動経路に含まれるブロック内経路に対応する内経路コストに基づき、移動経路を用いて移動する場合の移動コストである経路移動コストを算出する移動コスト算出段階とを備える。
なお上記の発明の概要は、本発明の必要な特徴の全てを列挙したものではなく、これらの特徴群のサブコンビネーションも又発明となりうる。
【図面の簡単な説明】
図１は、本発明の一実施形態に係る経路探索システム５０の構成の一例を示す図である。
図２は、ブロック管理部１０４が管理する複数のブロック領域の一例を示す図である。
図３は、１次ブロック３０４ａの詳細な構成を示す図である。
図４は、経路探索装置１００の動作の一例を示すフローチャートである。
図５は、経路探索装置１００の動作の一例を説明する図である。
図６は、ブロック選択部１１２の構成の一例を示す図である。
図７は、経路探索装置１００のハードウェア構成を示す図である。
【発明を実施するための最良の形態】
以下、発明の実施の形態を通じて本発明を説明するが、以下の実施形態は特許請求の範囲にかかる発明を限定するものではなく、又実施形態の中で説明されている特徴の組み合わせの全てが発明の解決手段に必須であるとは限らない。
図１は、本発明の一実施形態に係る経路探索システム５０の構成の一例を示す。本例の経路探索システム５０は、始点及び終点間の移動経路を、高速に探索する。経路探索システム５０は、経路探索装置１００及びサーバ１５０を備える。
サーバ１５０は、経路探索装置１００の外部に設けられており、経路探索装置１００が経路探索に用いるための情報を、経路探索装置１００に与える。経路探索装置１００は、サーバ１５０と通信する端末の一例である。また、経路探索装置１００は、例えば、カーナビゲーション装置であり、予め設定された全体領域において、始点から終点までの移動に用いるべき移動経路を探索する。
経路探索装置１００は、ブロック情報格納部１０６、施設情報格納部１０８、誤差情報格納部１１０、ブロック管理部１０４、ブロック選択部１１２、移動経路生成部１１４、移動コスト算出部１１６、施設情報生成部１２０、誤差情報算出部１２２、経路選択部１１８、及び情報入出力部１０２を有する。
ブロック情報格納部１０６は、全体領域を分割した複数のブロック領域のそれぞれに対応する情報を格納する。本例において、ブロック情報格納部１０６は、それぞれのブロック領域に対応して、そのブロック領域に含まれる経路である一又は複数のブロック内経路と、それぞれブロック内経路を用いて当該ブロック領域を通過する場合に要する移動コストである内経路コストとを対応付けたブロック情報を格納する。
ブロック情報格納部１０６は、内径路コストとして、例えば、対応するブロック内経路を通過するのに要する時間又は料金、そのブロック内経路における曲がり角又は信号数、そのブロック内経路における天候、そのブロック内経路の道路幅又はその他の特徴等の移動コストを、内径路コストとして格納する。
施設情報格納部１０８は、それぞれのブロック内経路に対応付けて、そのブロック経路沿いに位置する施設を示すブロック施設情報を格納する。施設情報格納部１０８は、ブロック施設情報として、例えば、コンビニエンスストア、パーキングエリア、又はユーザにより予め設定された店舗の有無等を示す情報を格納する。
誤差情報格納部１１０は、それぞれのブロック内経路に対応付けて、そのブロック内経路を用いて移動した場合の所要時間の誤差範囲を示すブロック内誤差情報を格納する。誤差情報格納部１１０は、ブロック内誤差情報として、例えば、所要時間の誤差の値と、当該値の誤差が生じる確率とを関連付けた情報を格納する。
ブロック管理部１０４は、ブロック情報格納部１０６、施設情報格納部１０８、及び誤差情報格納部１１０に格納された情報を管理することにより、それぞれのブロック内経路に対応して、内経路コスト、ブロック施設情報、及びブロック内誤差情報を管理する。
ここで、本例において、サーバ１５０は、内経路コストを更新するための更新コスト情報を格納する。ブロック管理部１０４は、更新コスト情報を、情報入出力部１０２を介してサーバ１５０から受け取り、これに基づいて、ブロック情報格納部１０６に格納された内径路コストを更新する。また、ブロック管理部１０４は、サーバ１５０から受け取る情報に基づき、ブロック施設情報、又はブロック内誤差情報を更に更新してもよい。
ブロック選択部１１２は、全体領域に含まれる始点及び終点を指定する情報を情報入出力部１０２及びブロック管理部１０４を介してユーザから受け取り、全体領域における始点及び終点の位置に基づき、複数のブロック領域を選択する。ブロック選択部１１２は、例えば、全てのブロック領域のうち、始点と終点を結ぶ直線から所定の距離以内にある領域ブロックを選択する。
移動経路生成部１１４は、ブロック情報をブロック管理部１０４から受け取り、これに基づき、始点から終点に至る複数の移動経路を生成する。本例において、移動経路生成部１１４は、ブロック選択部１１２が選択する複数のブロック領域のそれぞれに含まれるブロック内経路を経由する移動経路を生成する。
移動コスト算出部１１６は、移動経路生成部１１４を介してブロック管理部１０４から受け取るブロック情報を受け取る。そして、移動コスト算出部１１６は、複数の移動経路のそれぞれに対し、その移動経路に含まれるブロック内経路に対応する内経路コストに基づき、その移動経路を用いて移動する場合の移動コストである経路移動コストを算出する。
施設情報生成部１２０は、ブロック施設情報をブロック管理部１０４から受け取り、移動経路が経由するブロック内経路に対応するブロック施設情報に基づき、その移動経路沿いに位置する施設を示す経路施設情報を生成する。
誤差情報算出部１２２は、ブロック内誤差情報をブロック管理部１０４から受け取り、移動経路が経由するブロック内経路に対応するブロック内誤差情報に基づき、その移動経路を用いて移動した場合の所要時間の誤差範囲を示す経路誤差情報を算出する。誤差情報算出部１２２は、例えば、ブロック内誤差情報として示された誤差の値、及び当該値に対応する確率に基づき、経路誤差情報を算出する。
経路選択部１１８は、複数の移動経路についてそれぞれ算出された経路移動コストに基づき、複数の移動経路から一の移動経路を選択する。経路選択部１１８は、経路施設情報又は経路誤差情報に基づき、移動経路を選択してもよい。また、経路選択部１１８は、複数の移動経路を、それぞれの経路移動コストに基づき、順序付けて選択してもよい。
情報入出力部１０２は、始点及び終点の指定をユーザから受け付け、また、経路選択部１１８が選択した移動経路を示す情報をユーザに対して出力する。ここで、情報入出力部１０２は、移動経路を示す情報を、例えばディスプレイに表示することによりユーザに出力する。情報入出力部１０２は、当該情報を、ユーザに出力する代わりに、例えば他の情報処理装置に供給してもよい。
尚。本例において、情報入出力部１０２は、移動経路を示す情報を、当該移動経路に対応する経路施設情報及び経路誤差情報と対応付けて出力する。また、情報入出力部１０２は、サーバ１５０から更新コスト情報を受け取ってブロック管理部１０４に供給する。本例によれば、移動経路を適切に検索することができる。
図２は、ブロック管理部１０４が管理する複数のブロック領域の一例を示す。本例において、ブロック管理部１０４は、複数の１次ブロック３０４、複数の２次ブロック３０６、及び複数の３次ブロック３０８のそれぞれに対応する内経路コストを管理する。
１次ブロック３０４は、全体分割ブロックの一例であり、全体領域３０２を分割したブロック領域である。２次ブロック３０６及び３次ブロック３０８のそれぞれは、部分分割ブロックの一例であり、複数の１次ブロック３０４のそれぞれを更に分割した領域に対応するブロック領域である。
ブロック管理部１０４は、１個の１次ブロック３０４の領域に対応して、複数の２次ブロック３０６を管理し、１個の２次ブロック３０６の領域に対応して、複数の３次ブロック３０８を管理する。また、２次ブロック３０６は、１次ブロック３０４における対応する領域より詳細に設定されたブロック内経路を含み、３次ブロック３０８は、２次ブロック３０６における対応する領域より詳細に設定されたブロック内経路を含む。この場合、探索する経路の距離に応じて、１次ブロック３０４、２次ブロック３０６、又は３次ブロック３０８を選択して用いることにより、高速に経路探索を行うことができる。また、本例によれば、高い精度が必要な領域に対して３次ブロック３０８を選択することにより、高い精度で経路探索を行うことができる。尚、本例において、１次ブロック３０４、２次ブロック３０６、及び３次ブロック３０８は、それぞれ１辺が８０ｋｍ、１０ｋｍ、及び１ｋｍ程度の正方形形状の領域である。他の例において、１次ブロック３０４、２次ブロック３０６、及び３次ブロック３０８は、例えば長方形形状又は三角形形状等の、他の２次元形状であってもよい。
図３は、１次ブロック３０４ａの詳細な構成を示す。１次ブロック３０４ａは、それぞれ１次ブロック３０４ａの内部と外部とを結ぶ５個の出入口４０２ａ〜ｅを有する。本例において、１次ブロック３０４ａは、全体領域において、複数の１次ブロック３０４ｂ〜ｉと隣接しており、５個の出入口４０２ａ〜ｅは、１次ブロック３０４ａと、複数の１次ブロック３０４ｂ〜ｉとを接続する。
また、１次ブロック３０４ａは、５個の出入口４０２ａ〜ｅのうちの２個を一端及び他端とし、互いに異なる複数のブロック内経路４０４ａ〜ｈを有する。この場合、ブロック管理部１０４（図１参照）は、１次ブロック３０４ａに対応して、複数のブロック内経路４０４ａ〜ｈを管理する。すなわち、ブロック管理部１０４は、複数の出入口４０２ａ〜ｅのうちの、２個の出入口４０２の組み合わせを、ブロック内経路４０４として管理し、当該２個の出入口４０２の間における移動コストを、当該ブロック内経路４０４に対応する内径路コストとして管理する。
ここで、複数の１次ブロック３０４ｂ〜ｉのそれぞれは、１次ブロック３０４ａと同一又は同様の構成を有してよい。また、１次ブロック３０４に含まれる領域ブロックである２次ブロック３０６（図２参照）及び３次ブロック３０８（図２参照）のそれぞれは、領域の大きさが異なる他は、１次ブロック３０４ａと同一又は同様の構成を有してよい。
図４は、経路探索装置１００の動作の一例を示すフローチャートである。経路探索装置１００は、最初に、例えばサーバ１５０と通信することにより、内径路コストの更新が必要か否かを確認し（Ｓ１０２）、更新が必要であれば、サーバ１５０から更新コスト情報を受け取ることにより、ブロック管理部１０４は、内径路コストを更新する（Ｓ１０４）。これにより、ブロック管理部１０４は、内径路コストを管理する。
そして、情報入出力部１０２は、例えばユーザから、探索すべき経路における始点及び終点を示す情報を取得し（Ｓ１０６）、ブロック選択部１１２は、その始点及び終点を示す情報に基づき、複数のブロック領域を選択する（Ｓ１０８）。そして、移動経路生成部１１４は、選択された複数のブロック領域に基づき、複数の移動経路を生成し（Ｓ１１０）、移動コスト算出部１１６は、それら移動経路のそれぞれについて経路移動コストを算出する（Ｓ１１２）。
そして、経路選択部１１８は、算出された経路移動コストに基づき、一又は複数の移動経路を選択し（Ｓ１１４）、情報入出力部１０２は、選択された移動経路についての情報を出力する（Ｓ１１６）。
尚、Ｓ１０８において、ブロック選択部１１２は、複数のブロック領域の少なくとも一部として、互いに隣接する２個のブロック領域を選択する。そして、Ｓ１１０において、移動経路生成部１１４は、その２個のブロック領域に対し、それぞれのブロック領域におけるブロック内経路を、当該２個のブロック領域を接続する出入口を介して接続することにより、移動経路の少なくとも一部を生成する。本例によれば、高速に移動経路を生成することができる。
また、Ｓ１０２において、情報入出力部１０２は、例えば災害情報等の全体領域の少なくとも一部の状態を取得してもよい。この場合、ブロック管理部１０４は、例えば、少なくとも一部のブロック内経路を、当該ブロック内経路の使用の可否を示す使用可否情報と対応付けて管理する。
そして、Ｓ１０４において、ブロック管理部１０４は、情報入出力部１０２が取得した状態に基づき、そのブロック内経路に対する使用可否情報を変更する。この場合、Ｓ１１０において、移動経路生成部１１４は、使用可否情報に基づいてブロック内経路の使用の可否を判定することにより、使用可能なブロック内経路に基づき、移動経路を生成する。これにより、移動経路生成部１１４は、より適切な経路を生成することができる。
図５は、経路探索装置１００の動作の一例を説明する図である。本例において、ブロック選択部１１２（図１参照）は、始点５１６及び終点５１８の位置に基づき、複数のブロック領域を選択する。移動経路生成部１１４（図１参照）は、選択されたブロック領域に含まれるブロック内経路に基づき、始点経路５２０、中間経路５２２及び終点経路５２４を経由する移動経路を生成する。尚、本例においては、説明の便宜上、１次ブロックに対応する領域が４個の２次ブロックに分割され、２次ブロックに対応する領城が４個の３次ブロックに分割される場合の動作を説明する。
ブロック選択部１１２は、複数のブロック領域として、始点ブロック５０２、複数の始点近傍ブロック５０４ａ〜ｆ、終点ブロック５０６、複数の終点近傍ブロック５０８ａ〜ｆ、及び複数の中間ブロック５１０ａ〜ｓを選択する。始点ブロック５０２は、始点を含むブロック領域であり、複数の始点近傍ブロック５０４ａ〜ｆは、始点ブロック５０２の近傍のブロック領域である。また、始点ブロック５０２は、３次ブロックである。複数の始点近傍ブロック５０４ａ〜ｃは、３次ブロックであり、複数の始点近傍ブロック５０４ｄ〜ｆは２次ブロックである。
尚、一の３次ブロックに対する近傍のブロック領域とは、例えば、その３次ブロックを含む１次ブロックから分割された他の２次ブロック及び／又は３次ブロックである。他の例において、近傍のブロック領域とは、一のブロック領域からの距離が予め定められた距離より小さいブロック領域であってもよい。
終点ブロック５０６は、終点を含むブロック領域であり、複数の終点近傍ブロック５０８ａ〜ｆは、終点ブロック５０６の近傍のブロック領域である。また、終点ブロック５０６は、３次ブロック３０８である。複数の終点近傍ブロック５０８ａ〜ｃは、３次ブロックであり、複数の終点近傍ブロック５０８ｄ〜ｆは２次ブロックである。
複数の中間ブロック５１０ａ〜ｓのそれぞれは、始点５１６及び終点５１８のいずれも含まないブロック領域である。本例において、複数の中間ブロック５１０ａ〜ｓは、１次ブロックである。
移動経路生成部１１４は、始点ブロック５０２、及び複数の始点近傍ブロック５０４ａ〜ｆに含まれるブロック内経路に基づき、始点５１６からいずれかの中間ブロック５１０に至る始点経路５２０を生成し、終点ブロック５０６、及び複数の終点近傍ブロック５０８ａ〜ｆに含まれるブロック内経路に基づき、いずれかの中間ブロック５１０から終点５１８に至る終点経路５２４を生成する。この場合、移動経路生成部１１４は、ブロック内経路が詳細に設定されている２次ブロック及び／又は３次ブロックを用いて経路を生成することにより、始点経路５２０及び終点経路５２４を高い精度で生成することができる。
本例において、移動経路生成部１１４は、始点ブロック５０２及び始点近傍ブロック５０４ｄ〜ｅのそれぞれに含まれるブロック内経路を経由することにより、始点５１６から中間ブロック５１０ｎに至る始点経路５２０を生成する。また、移動経路生成部１１４は、終点近傍ブロック５０８ｄ〜ｅ及び終点ブロック５０６のそれぞれに含まれるブロック内経路を経由することにより、中間ブロック５１０ｆから終点５１８に至る終点経路５２４を生成する。
また、移動経路生成部１１４は、複数の中間ブロック５１０ａ〜ｓのそれぞれに含まれるブロック内経路に基づき、始点経路５２０と終点経路５２４とを接続する中間経路５２２を更に生成する。この場合、大きな領域に対応する１次ブロックを用いて経路を生成することにより、中間経路５２２を高速に生成することができる。
そして、移動経路生成部１１４は、始点経路５２０、中間経路５２２、及び終点経路５２４を接続することにより、始点５１６から終点５１８への移動に用いるべき移動経路を生成する。尚、移動経路生成部１１４は、始点経路５２０、終点経路５２４、及び／又は中間経路５２２を、それぞれ複数生成することにより、複数の移動経路を生成してよい。
移動コスト算出部１１６（図１参照）は、始点経路５２０、中間経路５２２、及び終点経路５２４のそれぞれに含まれるブロック内経路に対応する内経路コストに基づき、始点経路５２０、中間経路５２２、及び終点経路５２４における移動コストである始点移動コスト、中間移動コスト、及び終点移動コストのそれぞれを算出し、これらに基づいて経路移動コストを算出する。本例によれば、高速かつ高い精度で移動経路を探索することができる。これにより、経路探索を効率よく行うことができる。
ここで、ブロック管理部１０４は、複数のブロック領域を挟んで互いに離間された２個のブロック領域に対し、これら２個のブロック領域の間の移動コストである離間移動コストを更に管理してもよい。ブロック管理部１０４は、例えば、中間ブロック５１０ｎ及び５１０ｆの間の離間移動コストを管理する。この場合、移動コスト算出部１１６は、例えば、始点経路５２０に対応する始点移動コスト、終点経路５２４に対応する終点移動コスト、及び中間ブロック５１０ｎから５１０ｆへの移動に対応する離間移動コストに基づき、経路移動コストを算出する。この場合、高速に経路移動コストを算出することにより、更に高速に移動経路を探索することができる。
また、情報入出力部１０２（図１参照）は、移動経路の途中に経由すべき経由点５２６の指定を、例えばユーザから、更に受け付けてもよい。この場合、ブロック選択部１１２は、複数のブロック領域の一部として、経由点５２６を含むブロック領域である経由点ブロック５１２と、経由点ブロック５１２の近傍のブロック領域である複数の経由点近傍ブロック５１４ａ〜ｆを更に選択する。また、ブロック選択部１１２は、経由点５２６の位置に基づき、複数の中間ブロック５１０ｔ〜ｙを更に選択する。尚、本例において、経由点ブロック５１２、及び複数の経由点近傍ブロック５１４ａ〜ｃは３次ブロックであり、複数の経由点近傍ブロック５１４ｄ〜ｆは２次ブロックである。
移動経路生成部１１４は、経由点ブロック５１２、及び複数の経由点近傍ブロック５１４ａ〜ｆに含まれるブロック内経路に更に基づき、いずれかの中間ブロック５１０から、経由点５２６を経由して、いずれかの中間ブロック５１０に至る経由経路５３０を生成する。本例において、移動経路生成部１１４は、経由点ブロック５１２、及び複数の経由点近傍ブロック５１４ｂ〜ｄのそれぞれに含まれるブロック内経路を経由することにより、中間ブロック５１０ｖから中間ブロック５１０ｗに至る経由経路５３０を生成する。
また、移動経路生成部１１４は、始点５１６、経由点５２６、及び中間経路５２８の位置に基づき、始点経路５２０及び終点経路５２４のそれぞれと、経由経路５３０とをそれぞれ接続する複数の中間経路５２８−１〜２を生成する。これにより、移動経路生成部１１４は、始点経路５２０、終点経路５２４、複数の中間経路５２８−１〜２、及び経由経路５３０を経由する移動経路を生成する。そのため、本例によれば、経由点の指定に応じて、適切な経路を探索することができる。
図６は、ブロック選択部１１２の構成の一例を示す。ブロック選択部１１２は、テンプレート格納部６０２、図形サイズ変更部６０４、及び選択実行部６０６を有する。
テンプレート格納部６０２は、予め定められた形状のテンプレート図形を格納する。テンプレート格納部６０２は、例えば、長方形のテンプレート図形を格納する。
図形サイズ変更部６０４は、テンプレート図形を、指定された始点及び終点を含む大きさに拡大又は縮小する。図形サイズ変更部６０４は、始点と終点とを結ぶ距離に基づき、テンプレート図形を拡大又は縮小してよい。
選択実行部６０６は、拡大又は縮小されたテンプレート図形を、始点及び終点の位置を基準として全体領域上に配置し、配置されたテンプレート図形を含む複数のブロック領域を選択する。選択実行部６０６は、例えば、配置されたテンプレート図形に対して、少なくとも一部において重なりを生じるブロック領域を、当該複数のブロック領域のそれぞれとして選択してよい。本例によれば、複数のブロック領域を適切に選択することができる。
尚、他の例において、テンプレート格納部６０２は、例えば、略楕円形のテンプレート図形を格納してもよい。選択実行部６０６は、テンプレート図形を、略楕円形の長軸と、始点及び終点を結ぶ方向とを略平行にして、配置してよい。この場合、始点と終点との中間付近において、より多くのブロック領域を選択することにより、より適切な移動経路を探索することができる。
また、例えば全体領域の形状が所定の方向に長い場合、選択実行部６０６は、テンプレート図形を、略楕円形の長軸と、当該所定の方向とを略平行にして、配置してよい。この場合、経路探索を更に効率よく行うことができる。
図７は、本実施形態に係る経路探索装置１００（図１参照）の、ハードウェア構成を示す。本実施形態に係る配信装置１００は、ＣＰＵ８００、ＲＯＭ８１０、ＲＡＭ８２０、通信インターフェイス８３０、ハードディスクドライブ８４０、フレキシブルディスクドライブ８５０、及びＣＤ−ＲＯＭドライブ８６０を備える情報処理装置７００により実現される。
ＣＰＵ８００は、ＲＯＭ８１０及びＲＡＭ８２０に格納されたプログラムに基づいて動作し、各部の制御を行う。ＲＯＭ８１０は、情報処理装置７００の起動時にＣＰＵ８００が実行するブートプログラムや、情報処理装置７００のハードウェアに依存するプログラム等を格納する。ＲＡＭ８２０は、ＣＰＵ８００が実行するプログラム及びＣＰＵ８００が使用するデータ等を格納する。通信インターフェイス８３０は、ネットワークを介して他の装置と通信する。ハードディスクドライブ８４０は、情報処理装置７００が使用するプログラム及びデータを格納し、ＲＡＭ８２０を介してＣＰＵ８００に供給する。また、ハードディスクドライブ８４０は、図１を用いて説明したブロック情報格納部１０６、施設情報格納部１０８、及び誤差情報格納部１１０のそれぞれとして動作してもよい。フレキシブルディスクドライブ８５０は、フレキシブルディスク８９０からプログラム又はデータを読み取り、ＲＡＭ８２０に提供する。ＣＤ−ＲＯＭドライブ８６０は、ＣＤ−ＲＯＭ８９５からプログラム又はデータを読み取り、ＲＡＭ８２０に提供する。
ＲＡＭ８２０を介してＣＰＵ８００に提供されるプログラムは、フレキシブルディスク８９０、ＣＤ−ＲＯＭ８９５、又はＩＣカード等の記録媒体に格納されて利用者によって提供される。プログラムは、記録媒体から読み出され、ＲＡＭ８２０を介して情報処理装置７００にインストールされ、情報処理装置７００において実行される。
情報処理装置７００にインストールされて実行されるプログラムは、ブロック管理モジュールと、ブロック選択モジュールと、移動経路生成モジュールと、移動コスト算出モジュールと、経路選択モジュールとを含む。これらのプログラム又はモジュールは、情報処理装置７００を、図１を用いて説明したブロック管理部１０４、ブロック選択部１１２、移動経路生成部１１４、移動コスト算出部１１６、及び経路選択部１１８としてそれぞれ機能させる。
以上に示したプログラム又はモジュールは、外部の記憶媒体に格納されてもよい。記憶媒体としては、フレキシブルディスク８９０、ＣＤ−ＲＯＭ８９５の他に、ＤＶＤやＰＤ等の光学記録媒体、ＭＤ等の光磁気記録媒体、テープ媒体、ＩＣカード等の半導体メモリ等を用いることができる。また、専用通信ネットワークやインターネットに接続されたサーバシステムに設けたハードディスク又はＲＡＭ等の記憶装置を記録媒体として使用し、ネットワークを介してプログラムを情報処理装置７００に提供してもよい。
以上、本発明を実施の形態を用いて説明したが、本発明の技術的範囲は上記実施の形態に記載の範囲には限定されない。上記実施の形態に、多様な変更又は改良を加えることができる。その様な変更又は改良を加えた形態も本発明の技術的範囲に含まれ得ることが、特許請求の範囲の記載から明らかである。
【産業上の利用可能性】
上記説明から明らかなように、本発明によれば、経路探索を効率よく行うことができる。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【技術分野】
本発明は、経路探索装置、経路探索システム、プログラム、及び経路探索方法に関する。特に本発明は、始点から終点までの移動に用いるべき移動経路を探索する経路探索装置に関する。
【背景技術】
従来、複数のノードを利用して経路探索を行う方法が知られている。当該方法においては、それぞれのノード間の距離等に基づいて経路探索を行う。
しかし、始点と終点との間に多くのノードが存在する場合、経路探索に必要な演算量が増大するため、経路探索に時間がかかる場合があった。そのため、従来、経路探索を効率よく行うのが困難な場合があった。
そこで本発明は、上記の課題を解決することのできる経路探索装置、経路探索システム、プログラム、及び経路探索方法を提供することを目的とする。この目的は特許請求の範囲における独立項に記載の特徴の組み合わせにより達成される。また従属項は本発明の更なる有利な具体例を規定する。
【発明の開示】
このような目的を達成するために、本発明の第１の形態によれば、始点から終点までの移動に用いるべき移動経路を探索する経路探索装置であって、始点及び終点を含む全体領域を分割した複数のブロック領域のそれぞれに対応して、当該ブロック領域に含まれるブロック内経路を用いて当該ブロック領域を通過する場合に要する移動コストである内経路コストを管理するブロック管理部と、全体領域における始点及び終点の位置に基づき、複数のブロック領域を選択するブロック選択部と、ブロック選択部が選択する複数のブロック領域のそれぞれに含まれるブロック内経路を経由して、始点から終点に至る移動経路を生成する移動経路生成部と、移動経路に含まれるブロック内経路に対応する内経路コストに基づき、移動経路を用いて移動する場合の移動コストである経路移動コストを算出する移動コスト算出部とを備える。
また、少なくとも一部のブロック領域は、当該ブロック領域の内部と外部とを結ぶ、少なくとも３個の出入口を有し、ブロック管理部は、少なくとも一部のブロック領域のそれぞれに対応して、それぞれが少なくとも３個の出入口のうちの２個を一端及び他端とし、互いに異なる少なくとも２個のブロック内経路を管理してよい。
また、それぞれのブロック領域は、当該ブロック領域と、全体領域において当該ブロック領域に隣接するブロック領域とを接続する複数の出入口を有し、ブロック管理部は、複数の出入口のうちの２個の出入口の組み合わせを、ブロック内経路として管理し、当該２個の出入口の間における移動コストを、当該ブロック内経路に対応する内径路コストとして管理し、ブロック選択部は、複数のブロック領域の少なくとも一部として、互いに隣接する２個のブロック領域を選択し、移動経路生成部は、２個のブロック領域に対し、それぞれのブロック領域におけるブロック内経路を、当該２個のブロック領域を接続する出入口を介して接続することにより、移動経路の少なくとも一部を生成してよい。
また、移動経路生成部は複数の移動経路を生成し、移動コスト算出部は、複数の移動経路に対し、それぞれの経路移動コストを算出し、経路検索装置は、それぞれの経路移動コストに基づき、複数の移動経路から一の移動経路を選択する経路選択部を更に備えてよい。
また、ブロック管理部は、複数のブロック領域を挟んで互いに離間されたブロック領域である２個の離間ブロックに対し、当該２個の離間ブロックの間の移動コストである離間移動コストを更に管理し、ブロック選択部は、複数のブロック領域の少なくとも一部として、始点を含むブロック領域である始点ブロックと、終点を含むブロック領域である終点ブロックとを選択し、移動経路生成部は、始点ブロックに含まれるブロック内経路に基づき、始点から一の離間ブロックに至る始点経路を生成し、終点ブロックに含まれるブロック内経路に基づき、他の離間ブロックから終点に至る終点経路を生成することにより、始点経路及び終点経路を経由する移動経路を生成し、移動コスト算出部は、始点経路及び終点経路のそれぞれに含まれるブロック内経路に対応する内経路コストに基づき、始点経路及び終点経路における移動コストである始点移動コスト及び終点移動コストのそれぞれを算出し、始点移動コスト、終点移動コスト、及び離間移動コストに基づき、経路移動コストを算出してよい。
また、ブロック選択部は、始点ブロックの近傍のブロック領域である始点近傍ブロックと、終点ブロックの近傍のブロック領域である終点近傍ブロックと、を更に選択し、移動経路生成部は、始点ブロック及び始点近傍ブロックのそれぞれに含まれるブロック内経路を経由することにより、始点から一の離間ブロックに至る始点経路と、終点近傍ブロック及び終点ブロックのそれぞれに含まれるブロック内経路を経由することにより、他の離間ブロックから終点に至る終点経路とを生成してよい。
また、ブロック管理部は、全体領域を分割した複数のブロック領域である複数の全体分割ブロックと、複数の全体分割ブロックのそれぞれを更に分割した複数の領域に対応する複数のブロック領域である複数の部分分割ブロックとそれぞれに対応する内経路コストを管理し、ブロック選択部は、複数のブロック領域の少なくとも一部として、始点を含む部分分割ブロックである始点ブロックと、終点を含む部分分割ブロックである終点ブロックと、それぞれが始点及び終点のいずれも含まない全体分割ブロックである一又は複数の中間ブロックとを選択し、移動経路生成部は、始点ブロックに含まれるブロック内経路に基づく始点経路と、一又は複数の中間ブロックのそれぞれに含まれるブロック内経路に基づく中間経路と、終点ブロックに含まれるブロック内経路に基づく終点経路とをそれぞれ生成することにより、始点経路、中間経路、及び終点経路を経由する移動経路を生成してよい。
また、ブロック選択部は、始点ブロックの近傍の部分分割ブロックである始点近傍ブロックと、終点ブロックの近傍の部分分割ブロックである終点近傍ブロックとを更に選択し、移動経路生成部は、始点ブロック及び始点近傍ブロックのそれぞれに含まれるブロック内経路を経由することにより、始点からいずれかの中間ブロックに至る始点経路と、終点近傍ブロック及び終点ブロックのそれぞれに含まれるブロック内経路を経由することにより、いずれかの中間ブロックから終点に至る終点経路とを生成してよい。
また、移動経路の途中に経由すべき経由点の指定を受け付ける受付部を更に備え、ブロック選択部は、複数のブロック領域の一部として、経由点を含む部分分割ブロックである経由点ブロックを更に選択し、移動経路生成部は、経由点ブロックに含まれるブロック内経路に更に基づき、移動経路を生成してよい。
また、ブロック選択部は、経由点ブロックの近傍の部分分割ブロックである経由点近傍ブロックを更に選択し、移動経路生成部は、経由点ブロック及び経由点近傍ブロックのそれぞれに含まれるブロック内経路を経由することにより、いずれかの中間ブロックから、経由点を経由して、いずれかの中間ブロックに至る経由経路を生成し、経由経路を経由する移動経路を生成してよい。
また、ブロック管理部は、ブロック内経路沿いに位置する施設を示すブロック施設情報を更に管理し、経路検索装置は、移動経路が経由するブロック内経路に対応するブロック施設情報に基づき、当該移動経路沿いに位置する施設を示す経路施設情報を生成する施設情報生成部と、移動経路を示す情報を、当該移動経路に対応する経路施設情報と対応付けて出力する情報出力部とを更に備えてよい。
また、ブロック管理部は、ブロック内経路を用いて移動した場合の所要時間の誤差範囲を示すブロック内誤差情報を更に管理し、経路検索装置は、移動経路が経由するブロック内経路に対応するブロック内誤差情報に基づき、当該移動経路を用いて移動した場合の所要時間の誤差範囲を示す経路誤差情報を算出する誤差情報算出部と、移動経路を示す情報を、当該移動経路に対応する経路誤差情報と対応付けて出力する情報出力部とを更に備えてよい。
また、ブロック管理部は、経路検索装置の外部に設けられたサーバから、内径路コストを更新するための更新コスト情報を受け取り、当該更新コスト情報に基づき、少なくとも一部の内径路コストを更新してよい。
また、ブロック選択部は、予め定められた形状のテンプレート図形を格納するテンプレート格納部と、テンプレート図形を、始点及び終点を含む大きさに拡大又は縮小する図形サイズ変更部と、拡大又は縮小されたテンプレート図形を、始点及び終点の位置を基準として全体領域上に配置し、配置されたテンプレート図形を含む複数のブロック領域を選択する選択実行部とを有してよい。
また、全体領域の少なくとも一部の状態を取得する状態取得部を更に備え、ブロック管理部は、少なくとも一部のブロック内経路を、当該ブロック内経路の使用の可否を示す使用可否情報と対応付けて管理し、かつ、状態取得部が取得した状態に基づき、当該ブロック内経路に対する使用可否情報を変更し、移動経路生成部は、使用可否情報に基づいてブロック内経路の使用の可否を判定することにより、使用可能なブロック内経路に基づき、移動経路を生成してよい。
本発明の第２の形態によれば、始点から終点までの移動に用いるべき移動経路を探索する経路探索システムであって、始点及び終点を含む全体領域を分割した複数のブロック領域の少なくとも一部に対応して、当該ブロック領域に含まれるブロック内経路を用いて当該ブロック領域を通過する場合に要する移動コストである内経路コストを更新するための更新コスト情報を格納するサーバと、サーバと通信する端末とを備え、端末は、複数のブロック領域のそれぞれに対応して、当該ブロック領域に含まれるブロック内経路を用いて当該ブロック領域を通過する場合に要する内経路コストを管理し、かつ、サーバから受け取る更新コスト情報に基づき、少なくとも一部のブロック領域に対応する内径路コストを更新するブロック管理部と、全体領域における始点及び終点の位置に基づき、複数のブロック領域を選択するブロック選択部と、ブロック選択部が選択する複数のブロック領域のそれぞれに含まれるブロック内経路を経由して、始点から終点に至る移動経路を生成する移動経路生成部と、移動経路に含まれるブロック内経路に対応する内経路コストに基づき、移動経路を用いて移動する場合の移動コストである経路移動コストを算出する移動コスト算出部とを有する。
本発明の第３の形態によれば、始点から終点までの移動に用いるべき移動経路を探索するプログラムであって、始点及び終点を含む全体領域を分割した複数のブロック領域のそれぞれに対応して、当該ブロック領域に含まれるブロック内経路を用いて当該ブロック領域を通過する場合に要する移動コストである内経路コストを管理するブロック管理部と、全体領域における始点及び終点の位置に基づき、複数のブロック領域を選択するブロック選択部と、ブロック選択部が選択する複数のブロック領域のそれぞれに含まれるブロック内経路を経由して、始点から終点に至る移動経路を生成する移動経路生成部と、移動経路に含まれるブロック内経路に対応する内経路コストに基づき、移動経路を用いて移動する場合の移動コストである経路移動コストを算出する移動コスト算出部とを備える。
本発明の第４の形態によれば、始点から終点までの移動に用いるべき移動経路を探索する経路探索方法であって、始点及び終点を含む全体領域を分割した複数のブロック領域のそれぞれに対応して、当該ブロック領域に含まれるブロック内経路を用いて当該ブロック領域を通過する場合に要する移動コストである内経路コストを管理するブロック管理段階と、全体領域における始点及び終点の位置に基づき、複数のブロック領域を選択するブロック選択段階と、ブロック選択部が選択する複数のブロック領域のそれぞれに含まれるブロック内経路を経由して、始点から終点に至る移動経路を生成する移動経路生成段階と、移動経路に含まれるブロック内経路に対応する内経路コストに基づき、移動経路を用いて移動する場合の移動コストである経路移動コストを算出する移動コスト算出段階とを備える。
なお上記の発明の概要は、本発明の必要な特徴の全てを列挙したものではなく、これらの特徴群のサブコンビネーションも又発明となりうる。
【図面の簡単な説明】
図１は、本発明の一実施形態に係る経路探索システム５０の構成の一例を示す図である。
図２は、ブロック管理部１０４が管理する複数のブロック領域の一例を示す図である。
図３は、１次ブロック３０４ａの詳細な構成を示す図である。
図４は、経路探索装置１００の動作の一例を示すフローチャートである。
図５は、経路探索装置１００の動作の一例を説明する図である。
図６は、ブロック選択部１１２の構成の一例を示す図である。
図７は、経路探索装置１００のハードウェア構成を示す図である。
【発明を実施するための最良の形態】
以下、発明の実施の形態を通じて本発明を説明するが、以下の実施形態は特許請求の範囲にかかる発明を限定するものではなく、又実施形態の中で説明されている特徴の組み合わせの全てが発明の解決手段に必須であるとは限らない。
図１は、本発明の一実施形態に係る経路探索システム５０の構成の一例を示す。本例の経路探索システム５０は、始点及び終点間の移動経路を、高速に探索する。経路探索システム５０は、経路探索装置１００及びサーバ１５０を備える。
サーバ１５０は、経路探索装置１００の外部に設けられており、経路探索装置１００が経路探索に用いるための情報を、経路探索装置１００に与える。経路探索装置１００は、サーバ１５０と通信する端末の一例である。また、経路探索装置１００は、例えば、カーナビゲーション装置であり、予め設定された全体領域において、始点から終点までの移動に用いるべき移動経路を探索する。
経路探索装置１００は、ブロック情報格納部１０６、施設情報格納部１０８、誤差情報格納部１１０、ブロック管理部１０４、ブロック選択部１１２、移動経路生成部１１４、移動コスト算出部１１６、施設情報生成部１２０、誤差情報算出部１２２、経路選択部１１８、及び情報入出力部１０２を有する。
ブロック情報格納部１０６は、全体領域を分割した複数のブロック領域のそれぞれに対応する情報を格納する。本例において、ブロック情報格納部１０６は、それぞれのブロック領域に対応して、そのブロック領域に含まれる経路である一又は複数のブロック内経路と、それぞれブロック内経路を用いて当該ブロック領域を通過する場合に要する移動コストである内経路コストとを対応付けたブロック情報を格納する。
ブロック情報格納部１０６は、内径路コストとして、例えば、対応するブロック内経路を通過するのに要する時間又は料金、そのブロック内経路における曲がり角又は信号数、そのブロック内経路における天候、そのブロック内経路の道路幅又はその他の特徴等の移動コストを、内径路コストとして格納する。
施設情報格納部１０８は、それぞれのブロック内経路に対応付けて、そのブロック経路沿いに位置する施設を示すブロック施設情報を格納する。施設情報格納部１０８は、ブロック施設情報として、例えば、コンビニエンスストア、パーキングエリア、又はユーザにより予め設定された店舗の有無等を示す情報を格納する。
誤差情報格納部１１０は、それぞれのブロック内経路に対応付けて、そのブロック内経路を用いて移動した場合の所要時間の誤差範囲を示すブロック内誤差情報を格納する。誤差情報格納部１１０は、ブロック内誤差情報として、例えば、所要時間の誤差の値と、当該値の誤差が生じる確率とを関連付けた情報を格納する。
ブロック管理部１０４は、ブロック情報格納部１０６、施設情報格納部１０８、及び誤差情報格納部１１０に格納された情報を管理することにより、それぞれのブロック内経路に対応して、内経路コスト、ブロック施設情報、及びブロック内誤差情報を管理する。
ここで、本例において、サーバ１５０は、内経路コストを更新するための更新コスト情報を格納する。ブロック管理部１０４は、更新コスト情報を、情報入出力部１０２を介してサーバ１５０から受け取り、これに基づいて、ブロック情報格納部１０６に格納された内径路コストを更新する。また、ブロック管理部１０４は、サーバ１５０から受け取る情報に基づき、ブロック施設情報、又はブロック内誤差情報を更に更新してもよい。
ブロック選択部１１２は、全体領域に含まれる始点及び終点を指定する情報を情報入出力部１０２及びブロック管理部１０４を介してユーザから受け取り、全体領域における始点及び終点の位置に基づき、複数のブロック領域を選択する。ブロック選択部１１２は、例えば、全てのブロック領域のうち、始点と終点を結ぶ直線から所定の距離以内にある領域ブロックを選択する。
移動経路生成部１１４は、ブロック情報をブロック管理部１０４から受け取り、これに基づき、始点から終点に至る複数の移動経路を生成する。本例において、移動経路生成部１１４は、ブロック選択部１１２が選択する複数のブロック領域のそれぞれに含まれるブロック内経路を経由する移動経路を生成する。
移動コスト算出部１１６は、移動経路生成部１１４を介してブロック管理部１０４から受け取るブロック情報を受け取る。そして、移動コスト算出部１１６は、複数の移動経路のそれぞれに対し、その移動経路に含まれるブロック内経路に対応する内経路コストに基づき、その移動経路を用いて移動する場合の移動コストである経路移動コストを算出する。
施設情報生成部１２０は、ブロック施設情報をブロック管理部１０４から受け取り、移動経路が経由するブロック内経路に対応するブロック施設情報に基づき、その移動経路沿いに位置する施設を示す経路施設情報を生成する。
誤差情報算出部１２２は、ブロック内誤差情報をブロック管理部１０４から受け取り、移動経路が経由するブロック内経路に対応するブロック内誤差情報に基づき、その移動経路を用いて移動した場合の所要時間の誤差範囲を示す経路誤差情報を算出する。誤差情報算出部１２２は、例えば、ブロック内誤差情報として示された誤差の値、及び当該値に対応する確率に基づき、経路誤差情報を算出する。
経路選択部１１８は、複数の移動経路についてそれぞれ算出された経路移動コストに基づき、複数の移動経路から一の移動経路を選択する。経路選択部１１８は、経路施設情報又は経路誤差情報に基づき、移動経路を選択してもよい。また、経路選択部１１８は、複数の移動経路を、それぞれの経路移動コストに基づき、順序付けて選択してもよい。
情報入出力部１０２は、始点及び終点の指定をユーザから受け付け、また、経路選択部１１８が選択した移動経路を示す情報をユーザに対して出力する。ここで、情報入出力部１０２は、移動経路を示す情報を、例えばディスプレイに表示することによりユーザに出力する。情報入出力部１０２は、当該情報を、ユーザに出力する代わりに、例えば他の情報処理装置に供給してもよい。
尚。本例において、情報入出力部１０２は、移動経路を示す情報を、当該移動経路に対応する経路施設情報及び経路誤差情報と対応付けて出力する。また、情報入出力部１０２は、サーバ１５０から更新コスト情報を受け取ってブロック管理部１０４に供給する。本例によれば、移動経路を適切に検索することができる。
図２は、ブロック管理部１０４が管理する複数のブロック領域の一例を示す。本例において、ブロック管理部１０４は、複数の１次ブロック３０４、複数の２次ブロック３０６、及び複数の３次ブロック３０８のそれぞれに対応する内経路コストを管理する。
１次ブロック３０４は、全体分割ブロックの一例であり、全体領域３０２を分割したブロック領域である。２次ブロック３０６及び３次ブロック３０８のそれぞれは、部分分割ブロックの一例であり、複数の１次ブロック３０４のそれぞれを更に分割した領域に対応するブロック領域である。
ブロック管理部１０４は、１個の１次ブロック３０４の領域に対応して、複数の２次ブロック３０６を管理し、１個の２次ブロック３０６の領域に対応して、複数の３次ブロック３０８を管理する。また、２次ブロック３０６は、１次ブロック３０４における対応する領域より詳細に設定されたブロック内経路を含み、３次ブロック３０８は、２次ブロック３０６における対応する領域より詳細に設定されたブロック内経路を含む。この場合、探索する経路の距離に応じて、１次ブロック３０４、２次ブロック３０６、又は３次ブロック３０８を選択して用いることにより、高速に経路探索を行うことができる。また、本例によれば、高い精度が必要な領域に対して３次ブロック３０８を選択することにより、高い精度で経路探索を行うことができる。尚、本例において、１次ブロック３０４、２次ブロック３０６、及び３次ブロック３０８は、それぞれ１辺が８０ｋｍ、１０ｋｍ、及び１ｋｍ程度の正方形形状の領域である。他の例において、１次ブロック３０４、２次ブロック３０６、及び３次ブロック３０８は、例えば長方形形状又は三角形形状等の、他の２次元形状であってもよい。
図３は、１次ブロック３０４ａの詳細な構成を示す。１次ブロック３０４ａは、それぞれ１次ブロック３０４ａの内部と外部とを結ぶ５個の出入口４０２ａ〜ｅを有する。本例において、１次ブロック３０４ａは、全体領域において、複数の１次ブロック３０４ｂ〜ｉと隣接しており、５個の出入口４０２ａ〜ｅは、１次ブロック３０４ａと、複数の１次ブロック３０４ｂ〜ｉとを接続する。
また、１次ブロック３０４ａは、５個の出入口４０２ａ〜ｅのうちの２個を一端及び他端とし、互いに異なる複数のブロック内経路４０４ａ〜ｈを有する。この場合、ブロック管理部１０４（図１参照）は、１次ブロック３０４ａに対応して、複数のブロック内経路４０４ａ〜ｈを管理する。すなわち、ブロック管理部１０４は、複数の出入口４０２ａ〜ｅのうちの、２個の出入口４０２の組み合わせを、ブロック内経路４０４として管理し、当該２個の出入口４０２の間における移動コストを、当該ブロック内経路４０４に対応する内径路コストとして管理する。
ここで、複数の１次ブロック３０４ｂ〜ｉのそれぞれは、１次ブロック３０４ａと同一又は同様の構成を有してよい。また、１次ブロック３０４に含まれる領域ブロックである２次ブロック３０６（図２参照）及び３次ブロック３０８（図２参照）のそれぞれは、領域の大きさが異なる他は、１次ブロック３０４ａと同一又は同様の構成を有してよい。
図４は、経路探索装置１００の動作の一例を示すフローチャートである。経路探索装置１００は、最初に、例えばサーバ１５０と通信することにより、内径路コストの更新が必要か否かを確認し（Ｓ１０２）、更新が必要であれば、サーバ１５０から更新コスト情報を受け取ることにより、ブロック管理部１０４は、内径路コストを更新する（Ｓ１０４）。これにより、ブロック管理部１０４は、内径路コストを管理する。
そして、情報入出力部１０２は、例えばユーザから、探索すべき経路における始点及び終点を示す情報を取得し（Ｓ１０６）、ブロック選択部１１２は、その始点及び終点を示す情報に基づき、複数のブロック領域を選択する（Ｓ１０８）。そして、移動経路生成部１１４は、選択された複数のブロック領域に基づき、複数の移動経路を生成し（Ｓ１１０）、移動コスト算出部１１６は、それら移動経路のそれぞれについて経路移動コストを算出する（Ｓ１１２）。
そして、経路選択部１１８は、算出された経路移動コストに基づき、一又は複数の移動経路を選択し（Ｓ１１４）、情報入出力部１０２は、選択された移動経路についての情報を出力する（Ｓ１１６）。
尚、Ｓ１０８において、ブロック選択部１１２は、複数のブロック領域の少なくとも一部として、互いに隣接する２個のブロック領域を選択する。そして、Ｓ１１０において、移動経路生成部１１４は、その２個のブロック領域に対し、それぞれのブロック領域におけるブロック内経路を、当該２個のブロック領域を接続する出入口を介して接続することにより、移動経路の少なくとも一部を生成する。本例によれば、高速に移動経路を生成することができる。
また、Ｓ１０２において、情報入出力部１０２は、例えば災害情報等の全体領域の少なくとも一部の状態を取得してもよい。この場合、ブロック管理部１０４は、例えば、少なくとも一部のブロック内経路を、当該ブロック内経路の使用の可否を示す使用可否情報と対応付けて管理する。
そして、Ｓ１０４において、ブロック管理部１０４は、情報入出力部１０２が取得した状態に基づき、そのブロック内経路に対する使用可否情報を変更する。この場合、Ｓ１１０において、移動経路生成部１１４は、使用可否情報に基づいてブロック内経路の使用の可否を判定することにより、使用可能なブロック内経路に基づき、移動経路を生成する。これにより、移動経路生成部１１４は、より適切な経路を生成することができる。
図５は、経路探索装置１００の動作の一例を説明する図である。本例において、ブロック選択部１１２（図１参照）は、始点５１６及び終点５１８の位置に基づき、複数のブロック領域を選択する。移動経路生成部１１４（図１参照）は、選択されたブロック領域に含まれるブロック内経路に基づき、始点経路５２０、中間経路５２２及び終点経路５２４を経由する移動経路を生成する。尚、本例においては、説明の便宜上、１次ブロックに対応する領域が４個の２次ブロックに分割され、２次ブロックに対応する領城が４個の３次ブロックに分割される場合の動作を説明する。
ブロック選択部１１２は、複数のブロック領域として、始点ブロック５０２、複数の始点近傍ブロック５０４ａ〜ｆ、終点ブロック５０６、複数の終点近傍ブロック５０８ａ〜ｆ、及び複数の中間ブロック５１０ａ〜ｓを選択する。始点ブロック５０２は、始点を含むブロック領域であり、複数の始点近傍ブロック５０４ａ〜ｆは、始点ブロック５０２の近傍のブロック領域である。また、始点ブロック５０２は、３次ブロックである。複数の始点近傍ブロック５０４ａ〜ｃは、３次ブロックであり、複数の始点近傍ブロック５０４ｄ〜ｆは２次ブロックである。
尚、一の３次ブロックに対する近傍のブロック領域とは、例えば、その３次ブロックを含む１次ブロックから分割された他の２次ブロック及び／又は３次ブロックである。他の例において、近傍のブロック領域とは、一のブロック領域からの距離が予め定められた距離より小さいブロック領域であってもよい。
終点ブロック５０６は、終点を含むブロック領域であり、複数の終点近傍ブロック５０８ａ〜ｆは、終点ブロック５０６の近傍のブロック領域である。また、終点ブロック５０６は、３次ブロック３０８である。複数の終点近傍ブロック５０８ａ〜ｃは、３次ブロックであり、複数の終点近傍ブロック５０８ｄ〜ｆは２次ブロックである。
複数の中間ブロック５１０ａ〜ｓのそれぞれは、始点５１６及び終点５１８のいずれも含まないブロック領域である。本例において、複数の中間ブロック５１０ａ〜ｓは、１次ブロックである。
移動経路生成部１１４は、始点ブロック５０２、及び複数の始点近傍ブロック５０４ａ〜ｆに含まれるブロック内経路に基づき、始点５１６からいずれかの中間ブロック５１０に至る始点経路５２０を生成し、終点ブロック５０６、及び複数の終点近傍ブロック５０８ａ〜ｆに含まれるブロック内経路に基づき、いずれかの中間ブロック５１０から終点５１８に至る終点経路５２４を生成する。この場合、移動経路生成部１１４は、ブロック内経路が詳細に設定されている２次ブロック及び／又は３次ブロックを用いて経路を生成することにより、始点経路５２０及び終点経路５２４を高い精度で生成することができる。
本例において、移動経路生成部１１４は、始点ブロック５０２及び始点近傍ブロック５０４ｄ〜ｅのそれぞれに含まれるブロック内経路を経由することにより、始点５１６から中間ブロック５１０ｎに至る始点経路５２０を生成する。また、移動経路生成部１１４は、終点近傍ブロック５０８ｄ〜ｅ及び終点ブロック５０６のそれぞれに含まれるブロック内経路を経由することにより、中間ブロック５１０ｆから終点５１８に至る終点経路５２４を生成する。
また、移動経路生成部１１４は、複数の中間ブロック５１０ａ〜ｓのそれぞれに含まれるブロック内経路に基づき、始点経路５２０と終点経路５２４とを接続する中間経路５２２を更に生成する。この場合、大きな領域に対応する１次ブロックを用いて経路を生成することにより、中間経路５２２を高速に生成することができる。
そして、移動経路生成部１１４は、始点経路５２０、中間経路５２２、及び終点経路５２４を接続することにより、始点５１６から終点５１８への移動に用いるべき移動経路を生成する。尚、移動経路生成部１１４は、始点経路５２０、終点経路５２４、及び／又は中間経路５２２を、それぞれ複数生成することにより、複数の移動経路を生成してよい。
移動コスト算出部１１６（図１参照）は、始点経路５２０、中間経路５２２、及び終点経路５２４のそれぞれに含まれるブロック内経路に対応する内経路コストに基づき、始点経路５２０、中間経路５２２、及び終点経路５２４における移動コストである始点移動コスト、中間移動コスト、及び終点移動コストのそれぞれを算出し、これらに基づいて経路移動コストを算出する。本例によれば、高速かつ高い精度で移動経路を探索することができる。これにより、経路探索を効率よく行うことができる。
ここで、ブロック管理部１０４は、複数のブロック領域を挟んで互いに離間された２個のブロック領域に対し、これら２個のブロック領域の間の移動コストである離間移動コストを更に管理してもよい。ブロック管理部１０４は、例えば、中間ブロック５１０ｎ及び５１０ｆの間の離間移動コストを管理する。この場合、移動コスト算出部１１６は、例えば、始点経路５２０に対応する始点移動コスト、終点経路５２４に対応する終点移動コスト、及び中間ブロック５１０ｎから５１０ｆへの移動に対応する離間移動コストに基づき、経路移動コストを算出する。この場合、高速に経路移動コストを算出することにより、更に高速に移動経路を探索することができる。
また、情報入出力部１０２（図１参照）は、移動経路の途中に経由すべき経由点５２６の指定を、例えばユーザから、更に受け付けてもよい。この場合、ブロック選択部１１２は、複数のブロック領域の一部として、経由点５２６を含むブロック領域である経由点ブロック５１２と、経由点ブロック５１２の近傍のブロック領域である複数の経由点近傍ブロック５１４ａ〜ｆを更に選択する。また、ブロック選択部１１２は、経由点５２６の位置に基づき、複数の中間ブロック５１０ｔ〜ｙを更に選択する。尚、本例において、経由点ブロック５１２、及び複数の経由点近傍ブロック５１４ａ〜ｃは３次ブロックであり、複数の経由点近傍ブロック５１４ｄ〜ｆは２次ブロックである。
移動経路生成部１１４は、経由点ブロック５１２、及び複数の経由点近傍ブロック５１４ａ〜ｆに含まれるブロック内経路に更に基づき、いずれかの中間ブロック５１０から、経由点５２６を経由して、いずれかの中間ブロック５１０に至る経由経路５３０を生成する。本例において、移動経路生成部１１４は、経由点ブロック５１２、及び複数の経由点近傍ブロック５１４ｂ〜ｄのそれぞれに含まれるブロック内経路を経由することにより、中間ブロック５１０ｖから中間ブロック５１０ｗに至る経由経路５３０を生成する。
また、移動経路生成部１１４は、始点５１６、経由点５２６、及び中間経路５２８の位置に基づき、始点経路５２０及び終点経路５２４のそれぞれと、経由経路５３０とをそれぞれ接続する複数の中間経路５２８−１〜２を生成する。これにより、移動経路生成部１１４は、始点経路５２０、終点経路５２４、複数の中間経路５２８−１〜２、及び経由経路５３０を経由する移動経路を生成する。そのため、本例によれば、経由点の指定に応じて、適切な経路を探索することができる。
図６は、ブロック選択部１１２の構成の一例を示す。ブロック選択部１１２は、テンプレート格納部６０２、図形サイズ変更部６０４、及び選択実行部６０６を有する。
テンプレート格納部６０２は、予め定められた形状のテンプレート図形を格納する。テンプレート格納部６０２は、例えば、長方形のテンプレート図形を格納する。
図形サイズ変更部６０４は、テンプレート図形を、指定された始点及び終点を含む大きさに拡大又は縮小する。図形サイズ変更部６０４は、始点と終点とを結ぶ距離に基づき、テンプレート図形を拡大又は縮小してよい。
選択実行部６０６は、拡大又は縮小されたテンプレート図形を、始点及び終点の位置を基準として全体領域上に配置し、配置されたテンプレート図形を含む複数のブロック領域を選択する。選択実行部６０６は、例えば、配置されたテンプレート図形に対して、少なくとも一部において重なりを生じるブロック領域を、当該複数のブロック領域のそれぞれとして選択してよい。本例によれば、複数のブロック領域を適切に選択することができる。
尚、他の例において、テンプレート格納部６０２は、例えば、略楕円形のテンプレート図形を格納してもよい。選択実行部６０６は、テンプレート図形を、略楕円形の長軸と、始点及び終点を結ぶ方向とを略平行にして、配置してよい。この場合、始点と終点との中間付近において、より多くのブロック領域を選択することにより、より適切な移動経路を探索することができる。
また、例えば全体領域の形状が所定の方向に長い場合、選択実行部６０６は、テンプレート図形を、略楕円形の長軸と、当該所定の方向とを略平行にして、配置してよい。この場合、経路探索を更に効率よく行うことができる。
図７は、本実施形態に係る経路探索装置１００（図１参照）の、ハードウェア構成を示す。本実施形態に係る配信装置１００は、ＣＰＵ８００、ＲＯＭ８１０、ＲＡＭ８２０、通信インターフェイス８３０、ハードディスクドライブ８４０、フレキシブルディスクドライブ８５０、及びＣＤ−ＲＯＭドライブ８６０を備える情報処理装置７００により実現される。
ＣＰＵ８００は、ＲＯＭ８１０及びＲＡＭ８２０に格納されたプログラムに基づいて動作し、各部の制御を行う。ＲＯＭ８１０は、情報処理装置７００の起動時にＣＰＵ８００が実行するブートプログラムや、情報処理装置７００のハードウェアに依存するプログラム等を格納する。ＲＡＭ８２０は、ＣＰＵ８００が実行するプログラム及びＣＰＵ８００が使用するデータ等を格納する。通信インターフェイス８３０は、ネットワークを介して他の装置と通信する。ハードディスクドライブ８４０は、情報処理装置７００が使用するプログラム及びデータを格納し、ＲＡＭ８２０を介してＣＰＵ８００に供給する。また、ハードディスクドライブ８４０は、図１を用いて説明したブロック情報格納部１０６、施設情報格納部１０８、及び誤差情報格納部１１０のそれぞれとして動作してもよい。フレキシブルディスクドライブ８５０は、フレキシブルディスク８９０からプログラム又はデータを読み取り、ＲＡＭ８２０に提供する。ＣＤ−ＲＯＭドライブ８６０は、ＣＤ−ＲＯＭ８９５からプログラム又はデータを読み取り、ＲＡＭ８２０に提供する。
ＲＡＭ８２０を介してＣＰＵ８００に提供されるプログラムは、フレキシブルディスク８９０、ＣＤ−ＲＯＭ８９５、又はＩＣカード等の記録媒体に格納されて利用者によって提供される。プログラムは、記録媒体から読み出され、ＲＡＭ８２０を介して情報処理装置７００にインストールされ、情報処理装置７００において実行される。
情報処理装置７００にインストールされて実行されるプログラムは、ブロック管理モジュールと、ブロック選択モジュールと、移動経路生成モジュールと、移動コスト算出モジュールと、経路選択モジュールとを含む。これらのプログラム又はモジュールは、情報処理装置７００を、図１を用いて説明したブロック管理部１０４、ブロック選択部１１２、移動経路生成部１１４、移動コスト算出部１１６、及び経路選択部１１８としてそれぞれ機能させる。
以上に示したプログラム又はモジュールは、外部の記憶媒体に格納されてもよい。記憶媒体としては、フレキシブルディスク８９０、ＣＤ−ＲＯＭ８９５の他に、ＤＶＤやＰＤ等の光学記録媒体、ＭＤ等の光磁気記録媒体、テープ媒体、ＩＣカード等の半導体メモリ等を用いることができる。また、専用通信ネットワークやインターネットに接続されたサーバシステムに設けたハードディスク又はＲＡＭ等の記憶装置を記録媒体として使用し、ネットワークを介してプログラムを情報処理装置７００に提供してもよい。
以上、本発明を実施の形態を用いて説明したが、本発明の技術的範囲は上記実施の形態に記載の範囲には限定されない。上記実施の形態に、多様な変更又は改良を加えることができる。その様な変更又は改良を加えた形態も本発明の技術的範囲に含まれ得ることが、特許請求の範囲の記載から明らかである。
【産業上の利用可能性】
上記説明から明らかなように、本発明によれば、経路探索を効率よく行うことができる。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【特許請求の範囲】
【請求項１】
始点から終点までの移動に用いるべき移動経路を探索する経路探索装置であって、
前記始点及び前記終点を含む全体領域を分割した複数のブロック領域のそれぞれに対応して、当該ブロック領域に含まれるブロック内経路を用いて当該ブロック領域を通過する場合に要する移動コストである内経路コストを管理するブロック管理部と、
前記全体領域における前記始点及び前記終点の位置に基づき、複数の前記ブロック領域を選択するブロック選択部と、
前記ブロック選択部が選択する前記複数のブロック領域のそれぞれに含まれる前記ブロック内経路を経由して、前記始点から前記終点に至る前記移動経路を生成する移動経路生成部と、
前記移動経路に含まれる前記ブロック内経路に対応する前記内経路コストに基づき、前記移動経路を用いて移動する場合の移動コストである経路移動コストを算出する移動コスト算出部と
を備えることを特徴とする経路検索装置。
【請求項２】
少なくとも一部の前記ブロック領域は、当該ブロック領域の内部と外部とを結ぶ、少なくとも３個の出入口を有し、
前記ブロック管理部は、少なくとも一部の前記ブロック領域のそれぞれに対応して、それぞれが前記少なくとも３個の出入口のうちの２個を一端及び他端とし、互いに異なる少なくとも２個の前記ブロック内経路を管理することを特徴とする請求項１に記載の経路探索装置。
【請求項３】
それぞれの前記ブロック領域は、当該ブロック領域と、前記全体領域において当該ブロック領域に隣接する前記ブロック領域とを接続する複数の出入口を有し、
前記ブロック管理部は、前記複数の出入口のうちの２個の前記出入口の組み合わせを、前記ブロック内経路として管理し、当該２個の出入口の間における移動コストを、当該ブロック内経路に対応する前記内径路コストとして管理し、
前記ブロック選択部は、前記複数のブロック領域の少なくとも一部として、互いに隣接する２個の前記ブロック領域を選択し、
前記移動経路生成部は、前記２個の前記ブロック領域に対し、それぞれの前記ブロック領域における前記ブロック内経路を、当該２個のブロック領域を接続する前記出入口を介して接続することにより、前記移動経路の少なくとも一部を生成することを特徴とする請求項１に記載の経路探索装置。
【請求項４】
前記移動経路生成部は複数の前記移動経路を生成し、
前記移動コスト算出部は、前記複数の移動経路に対し、それぞれの前記経路移動コストを算出し、
前記経路検索装置は、前記それぞれの経路移動コストに基づき、前記複数の移動経路から一の前記移動経路を選択する経路選択部を更に備えることを特徴とする請求項１に記載の経路検索装置。
【請求項５】
前記ブロック管理部は、複数の前記ブロック領域を挟んで互いに離間された前記ブロック領域である２個の離間ブロックに対し、当該２個の離間ブロックの間の移動コストである離間移動コストを更に管理し、
前記ブロック選択部は、前記複数のブロック領域の少なくとも一部として、
前記始点を含む前記ブロック領域である始点ブロックと、
前記終点を含む前記ブロック領域である終点ブロックと
を選択し、
前記移動経路生成部は、前記始点ブロックに含まれる前記ブロック内経路に基づき、前記始点から一の前記離間ブロックに至る始点経路を生成し、前記終点ブロックに含まれる前記ブロック内経路に基づき、他の前記離間ブロックから前記終点に至る終点経路を生成することにより、前記始点経路及び前記終点経路を経由する前記移動経路を生成し、
前記移動コスト算出部は、前記始点経路及び前記終点経路のそれぞれに含まれる前記ブロック内経路に対応する前記内経路コストに基づき、前記始点経路及び前記終点経路における移動コストである始点移動コスト及び終点移動コストのそれぞれを算出し、前記始点移動コスト、前記終点移動コスト、及び前記離間移動コストに基づき、前記経路移動コストを算出することを特徴とする請求項１に記載の経路検索装置。
【請求項６】
前記ブロック選択部は、
前記始点ブロックの近傍の前記ブロック領域である始点近傍ブロックと、
前記終点ブロックの近傍の前記ブロック領域である終点近傍ブロックと、
を更に選択し、
前記移動経路生成部は、前記始点ブロック及び前記始点近傍ブロックのそれぞれに含まれる前記ブロック内経路を経由することにより、前記始点から前記一の離間ブロックに至る前記始点経路と、前記終点近傍ブロック及び前記終点ブロックのそれぞれに含まれる前記ブロック内経路を経由することにより、前記他の離間ブロックから前記終点に至る前記終点経路とを生成することを特徴とする請求項５に記載の経路検索装置。
【請求項７】
前記ブロック管理部は、
前記全体領域を分割した複数の前記ブロック領域である複数の全体分割ブロックと、
複数の前記全体分割ブロックのそれぞれを更に分割した複数の領域に対応する複数の前記ブロック領域である複数の部分分割ブロックと
のそれぞれに対応する前記内経路コストを管理し、
前記ブロック選択部は、前記複数のブロック領域の少なくとも一部として、
前記始点を含む前記部分分割ブロックである始点ブロックと、
前記終点を含む前記部分分割ブロックである終点ブロックと、
それぞれが前記始点及び前記終点のいずれも含まない前記全体分割ブロックである一又は複数の中間ブロックと
を選択し、
前記移動経路生成部は、前記始点ブロックに含まれる前記ブロック内経路に基づく始点経路と、前記一又は複数の中間ブロックのそれぞれに含まれる前記ブロック内経路に基づく中間経路と、前記終点ブロックに含まれる前記ブロック内経路に基づく終点経路とをそれぞれ生成することにより、前記始点経路、前記中間経路、及び前記終点経路を経由する前記移動経路を生成することを特徴とする請求項１に記載の経路検索装置。
【請求項８】
前記ブロック選択部は、
前記始点ブロックの近傍の前記部分分割ブロックである始点近傍ブロックと、
前記終点ブロックの近傍の前記部分分割ブロックである終点近傍ブロックと
を更に選択し、
前記移動経路生成部は、前記始点ブロック及び前記始点近傍ブロックのそれぞれに含まれる前記ブロック内経路を経由することにより、前記始点からいずれかの前記中間ブロックに至る前記始点経路と、前記終点近傍ブロック及び前記終点ブロックのそれぞれに含まれる前記ブロック内経路を経由することにより、いずれかの前記中間ブロックから前記終点に至る前記終点経路とを生成することを特徴とする請求項７に記載の経路検索装置。
【請求項９】
前記移動経路の途中に経由すべき経由点の指定を受け付ける受付部を更に備え、
前記ブロック選択部は、前記複数のブロック領域の一部として、前記経由点を含む前記部分分割ブロックである経由点ブロックを更に選択し、
前記移動経路生成部は、前記経由点ブロックに含まれる前記ブロック内経路に更に基づき、前記移動経路を生成することを特徴とする請求項７に記載の経路検索装置。
【請求項１０】
前記ブロック選択部は、前記経由点ブロックの近傍の前記部分分割ブロックである経由点近傍ブロックを更に選択し、
前記移動経路生成部は、前記経由点ブロック及び前記経由点近傍ブロックのそれぞれに含まれる前記ブロック内経路を経由することにより、いずれかの前記中間ブロックから、前記経由点を経由して、いずれかの前記中間ブロックに至る経由経路を生成し、前記経由経路を経由する前記移動経路を生成することを特徴とする請求項９に記載の経路検索装置。
【請求項１１】
前記ブロック管理部は、前記ブロック内経路沿いに位置する施設を示すブロック施設情報を更に管理し、
前記経路検索装置は、
前記移動経路が経由する前記ブロック内経路に対応する前記ブロック施設情報に基づき、当該移動経路沿いに位置する施設を示す経路施設情報を生成する施設情報生成部と、
前記移動経路を示す情報を、当該移動経路に対応する前記経路施設情報と対応付けて出力する情報出力部と
を更に備えることを特徴とする請求項１に記載の経路検索装置。
【請求項１２】
前記ブロック管理部は、前記ブロック内経路を用いて移動した場合の所要時間の誤差範囲を示すブロック内誤差情報を更に管理し、
前記経路検索装置は、
前記移動経路が経由する前記ブロック内経路に対応する前記ブロック内誤差情報に基づき、当該移動経路を用いて移動した場合の所要時間の誤差範囲を示す経路誤差情報を算出する誤差情報算出部と、
前記移動経路を示す情報を、当該移動経路に対応する前記経路誤差情報と対応付けて出力する情報出力部と
を更に備えることを特徴とする請求項１に記載の経路検索装置。
【請求項１３】
前記ブロック管理部は、前記経路検索装置の外部に設けられたサーバから、前記内径路コストを更新するための更新コスト情報を受け取り、当該更新コスト情報に基づき、少なくとも一部の前記内径路コストを更新することを特徴とする請求項１に記載の経路検索装置。
【請求項１４】
前記ブロック選択部は、
予め定められた形状のテンプレート図形を格納するテンプレート格納部と、
前記テンプレート図形を、前記始点及び前記終点を含む大きさに拡大又は縮小する図形サイズ変更部と、
拡大又は縮小された前記テンプレート図形を、前記始点及び前記終点の位置を基準として前記全体領域上に配置し、配置された前記テンプレート図形を含む複数の前記ブロック領域を選択する選択実行部と
を有することを特徴とする請求項１に記載の経路検索装置。
【請求項１５】
前記全体領域の少なくとも一部の状態を取得する状態取得部を更に備え、
前記ブロック管理部は、少なくとも一部の前記ブロック内経路を、当該ブロック内経路の使用の可否を示す使用可否情報と対応付けて管理し、かつ、前記状態取得部が取得した前記状態に基づき、当該ブロック内経路に対する使用可否情報を変更し、
前記移動経路生成部は、前記使用可否情報に基づいて前記ブロック内経路の使用の可否を判定することにより、使用可能な前記ブロック内経路に基づき、前記移動経路を生成することを特徴とする請求項１に記載の経路検索装置。
【請求項１６】
始点から終点までの移動に用いるべき移動経路を探索する経路探索システムであって、
前記始点及び前記終点を含む全体領域を分割した複数のブロック領城の少なくとも一部に対応して、当該ブロック領域に含まれるブロック内経路を用いて当該ブロック領域を通過する場合に要する移動コストである内経路コストを更新するための更新コスト情報を格納するサーバと、
前記サーバと通信する端末と
を備え、
前記端末は、
前記複数のブロック領域のそれぞれに対応して、当該ブロック領域に含まれる前記ブロック内経路を用いて当該ブロック領域を通過する場合に要する前記内経路コストを管理し、かつ、前記サーバから受け取る前記更新コスト情報に基づき、少なくとも一部の前記ブロック領域に対応する前記内径路コストを更新するブロック管理部と、
前記全体領域における前記始点及び前記終点の位置に基づき、複数の前記ブロック領域を選択するブロック選択部と、
前記ブロック選択部が選択する前記複数のブロック領域のそれぞれに含まれる前記ブロック内経路を経由して、前記始点から前記終点に至る前記移動経路を生成する移動経路生成部と、
前記移動経路に含まれる前記ブロック内経路に対応する前記内経路コストに基づき、前記移動経路を用いて移動する場合の移動コストである経路移動コストを算出する移動コスト算出部と
を有することを特徴とする経路探索システム。
【請求項１７】
始点から終点までの移動に用いるべき移動経路を探索するプログラムであって、
前記始点及び前記終点を含む全体領域を分割した複数のブロック領域のそれぞれに対応して、当該ブロック領域に含まれるブロック内経路を用いて当該ブロック領域を通過する場合に要する移動コストである内経路コストを管理するブロック管理部と、
前記全体領域における前記始点及び前記終点の位置に基づき、複数の前記ブロック領域を選択するブロック選択部と、
前記ブロック選択部が選択する前記複数のブロック領域のそれぞれに含まれる前記ブロック内経路を経由して、前記始点から前記終点に至る前記移動経路を生成する移動経路生成部と、
前記移動経路に含まれる前記ブロック内経路に対応する前記内経路コストに基づき、前記移動経路を用いて移動する場合の移動コストである経路移動コストを算出する移動コスト算出部と
を備えることを特徴とするプログラム。
【請求項１８】
始点から終点までの移動に用いるべき移動経路を探索する経路探索方法であって、
前記始点及び前記終点を含む全体領域を分割した複数のブロック領域のそれぞれに対応して、当該ブロック領域に含まれるブロック内経路を用いて当該ブロック領域を通過する場合に要する移動コストである内経路コストを管理するブロック管理段階と、
前記全体領域における前記始点及び前記終点の位置に基づき、複数の前記ブロック領域を選択するブロック選択段階と、
前記ブロック選択部が選択する前記複数のブロック領域のそれぞれに含まれる前記ブロック内経路を経由して、前記始点から前記終点に至る前記移動経路を生成する移動経路生成段階と、
前記移動経路に含まれる前記ブロック内経路に対応する前記内経路コストに基づき、前記移動経路を用いて移動する場合の移動コストである経路移動コストを算出する移動コスト算出段階と
を備えることを特徴とする経路検索方法。
【請求項１】
始点から終点までの移動に用いるべき移動経路を探索する経路探索装置であって、
前記始点及び前記終点を含む全体領域を分割した複数のブロック領域のそれぞれに対応して、当該ブロック領域に含まれるブロック内経路を用いて当該ブロック領域を通過する場合に要する移動コストである内経路コストを管理するブロック管理部と、
前記全体領域における前記始点及び前記終点の位置に基づき、複数の前記ブロック領域を選択するブロック選択部と、
前記ブロック選択部が選択する前記複数のブロック領域のそれぞれに含まれる前記ブロック内経路を経由して、前記始点から前記終点に至る前記移動経路を生成する移動経路生成部と、
前記移動経路に含まれる前記ブロック内経路に対応する前記内経路コストに基づき、前記移動経路を用いて移動する場合の移動コストである経路移動コストを算出する移動コスト算出部と
を備えることを特徴とする経路検索装置。
【請求項２】
少なくとも一部の前記ブロック領域は、当該ブロック領域の内部と外部とを結ぶ、少なくとも３個の出入口を有し、
前記ブロック管理部は、少なくとも一部の前記ブロック領域のそれぞれに対応して、それぞれが前記少なくとも３個の出入口のうちの２個を一端及び他端とし、互いに異なる少なくとも２個の前記ブロック内経路を管理することを特徴とする請求項１に記載の経路探索装置。
【請求項３】
それぞれの前記ブロック領域は、当該ブロック領域と、前記全体領域において当該ブロック領域に隣接する前記ブロック領域とを接続する複数の出入口を有し、
前記ブロック管理部は、前記複数の出入口のうちの２個の前記出入口の組み合わせを、前記ブロック内経路として管理し、当該２個の出入口の間における移動コストを、当該ブロック内経路に対応する前記内径路コストとして管理し、
前記ブロック選択部は、前記複数のブロック領域の少なくとも一部として、互いに隣接する２個の前記ブロック領域を選択し、
前記移動経路生成部は、前記２個の前記ブロック領域に対し、それぞれの前記ブロック領域における前記ブロック内経路を、当該２個のブロック領域を接続する前記出入口を介して接続することにより、前記移動経路の少なくとも一部を生成することを特徴とする請求項１に記載の経路探索装置。
【請求項４】
前記移動経路生成部は複数の前記移動経路を生成し、
前記移動コスト算出部は、前記複数の移動経路に対し、それぞれの前記経路移動コストを算出し、
前記経路検索装置は、前記それぞれの経路移動コストに基づき、前記複数の移動経路から一の前記移動経路を選択する経路選択部を更に備えることを特徴とする請求項１に記載の経路検索装置。
【請求項５】
前記ブロック管理部は、複数の前記ブロック領域を挟んで互いに離間された前記ブロック領域である２個の離間ブロックに対し、当該２個の離間ブロックの間の移動コストである離間移動コストを更に管理し、
前記ブロック選択部は、前記複数のブロック領域の少なくとも一部として、
前記始点を含む前記ブロック領域である始点ブロックと、
前記終点を含む前記ブロック領域である終点ブロックと
を選択し、
前記移動経路生成部は、前記始点ブロックに含まれる前記ブロック内経路に基づき、前記始点から一の前記離間ブロックに至る始点経路を生成し、前記終点ブロックに含まれる前記ブロック内経路に基づき、他の前記離間ブロックから前記終点に至る終点経路を生成することにより、前記始点経路及び前記終点経路を経由する前記移動経路を生成し、
前記移動コスト算出部は、前記始点経路及び前記終点経路のそれぞれに含まれる前記ブロック内経路に対応する前記内経路コストに基づき、前記始点経路及び前記終点経路における移動コストである始点移動コスト及び終点移動コストのそれぞれを算出し、前記始点移動コスト、前記終点移動コスト、及び前記離間移動コストに基づき、前記経路移動コストを算出することを特徴とする請求項１に記載の経路検索装置。
【請求項６】
前記ブロック選択部は、
前記始点ブロックの近傍の前記ブロック領域である始点近傍ブロックと、
前記終点ブロックの近傍の前記ブロック領域である終点近傍ブロックと、
を更に選択し、
前記移動経路生成部は、前記始点ブロック及び前記始点近傍ブロックのそれぞれに含まれる前記ブロック内経路を経由することにより、前記始点から前記一の離間ブロックに至る前記始点経路と、前記終点近傍ブロック及び前記終点ブロックのそれぞれに含まれる前記ブロック内経路を経由することにより、前記他の離間ブロックから前記終点に至る前記終点経路とを生成することを特徴とする請求項５に記載の経路検索装置。
【請求項７】
前記ブロック管理部は、
前記全体領域を分割した複数の前記ブロック領域である複数の全体分割ブロックと、
複数の前記全体分割ブロックのそれぞれを更に分割した複数の領域に対応する複数の前記ブロック領域である複数の部分分割ブロックと
のそれぞれに対応する前記内経路コストを管理し、
前記ブロック選択部は、前記複数のブロック領域の少なくとも一部として、
前記始点を含む前記部分分割ブロックである始点ブロックと、
前記終点を含む前記部分分割ブロックである終点ブロックと、
それぞれが前記始点及び前記終点のいずれも含まない前記全体分割ブロックである一又は複数の中間ブロックと
を選択し、
前記移動経路生成部は、前記始点ブロックに含まれる前記ブロック内経路に基づく始点経路と、前記一又は複数の中間ブロックのそれぞれに含まれる前記ブロック内経路に基づく中間経路と、前記終点ブロックに含まれる前記ブロック内経路に基づく終点経路とをそれぞれ生成することにより、前記始点経路、前記中間経路、及び前記終点経路を経由する前記移動経路を生成することを特徴とする請求項１に記載の経路検索装置。
【請求項８】
前記ブロック選択部は、
前記始点ブロックの近傍の前記部分分割ブロックである始点近傍ブロックと、
前記終点ブロックの近傍の前記部分分割ブロックである終点近傍ブロックと
を更に選択し、
前記移動経路生成部は、前記始点ブロック及び前記始点近傍ブロックのそれぞれに含まれる前記ブロック内経路を経由することにより、前記始点からいずれかの前記中間ブロックに至る前記始点経路と、前記終点近傍ブロック及び前記終点ブロックのそれぞれに含まれる前記ブロック内経路を経由することにより、いずれかの前記中間ブロックから前記終点に至る前記終点経路とを生成することを特徴とする請求項７に記載の経路検索装置。
【請求項９】
前記移動経路の途中に経由すべき経由点の指定を受け付ける受付部を更に備え、
前記ブロック選択部は、前記複数のブロック領域の一部として、前記経由点を含む前記部分分割ブロックである経由点ブロックを更に選択し、
前記移動経路生成部は、前記経由点ブロックに含まれる前記ブロック内経路に更に基づき、前記移動経路を生成することを特徴とする請求項７に記載の経路検索装置。
【請求項１０】
前記ブロック選択部は、前記経由点ブロックの近傍の前記部分分割ブロックである経由点近傍ブロックを更に選択し、
前記移動経路生成部は、前記経由点ブロック及び前記経由点近傍ブロックのそれぞれに含まれる前記ブロック内経路を経由することにより、いずれかの前記中間ブロックから、前記経由点を経由して、いずれかの前記中間ブロックに至る経由経路を生成し、前記経由経路を経由する前記移動経路を生成することを特徴とする請求項９に記載の経路検索装置。
【請求項１１】
前記ブロック管理部は、前記ブロック内経路沿いに位置する施設を示すブロック施設情報を更に管理し、
前記経路検索装置は、
前記移動経路が経由する前記ブロック内経路に対応する前記ブロック施設情報に基づき、当該移動経路沿いに位置する施設を示す経路施設情報を生成する施設情報生成部と、
前記移動経路を示す情報を、当該移動経路に対応する前記経路施設情報と対応付けて出力する情報出力部と
を更に備えることを特徴とする請求項１に記載の経路検索装置。
【請求項１２】
前記ブロック管理部は、前記ブロック内経路を用いて移動した場合の所要時間の誤差範囲を示すブロック内誤差情報を更に管理し、
前記経路検索装置は、
前記移動経路が経由する前記ブロック内経路に対応する前記ブロック内誤差情報に基づき、当該移動経路を用いて移動した場合の所要時間の誤差範囲を示す経路誤差情報を算出する誤差情報算出部と、
前記移動経路を示す情報を、当該移動経路に対応する前記経路誤差情報と対応付けて出力する情報出力部と
を更に備えることを特徴とする請求項１に記載の経路検索装置。
【請求項１３】
前記ブロック管理部は、前記経路検索装置の外部に設けられたサーバから、前記内径路コストを更新するための更新コスト情報を受け取り、当該更新コスト情報に基づき、少なくとも一部の前記内径路コストを更新することを特徴とする請求項１に記載の経路検索装置。
【請求項１４】
前記ブロック選択部は、
予め定められた形状のテンプレート図形を格納するテンプレート格納部と、
前記テンプレート図形を、前記始点及び前記終点を含む大きさに拡大又は縮小する図形サイズ変更部と、
拡大又は縮小された前記テンプレート図形を、前記始点及び前記終点の位置を基準として前記全体領域上に配置し、配置された前記テンプレート図形を含む複数の前記ブロック領域を選択する選択実行部と
を有することを特徴とする請求項１に記載の経路検索装置。
【請求項１５】
前記全体領域の少なくとも一部の状態を取得する状態取得部を更に備え、
前記ブロック管理部は、少なくとも一部の前記ブロック内経路を、当該ブロック内経路の使用の可否を示す使用可否情報と対応付けて管理し、かつ、前記状態取得部が取得した前記状態に基づき、当該ブロック内経路に対する使用可否情報を変更し、
前記移動経路生成部は、前記使用可否情報に基づいて前記ブロック内経路の使用の可否を判定することにより、使用可能な前記ブロック内経路に基づき、前記移動経路を生成することを特徴とする請求項１に記載の経路検索装置。
【請求項１６】
始点から終点までの移動に用いるべき移動経路を探索する経路探索システムであって、
前記始点及び前記終点を含む全体領域を分割した複数のブロック領城の少なくとも一部に対応して、当該ブロック領域に含まれるブロック内経路を用いて当該ブロック領域を通過する場合に要する移動コストである内経路コストを更新するための更新コスト情報を格納するサーバと、
前記サーバと通信する端末と
を備え、
前記端末は、
前記複数のブロック領域のそれぞれに対応して、当該ブロック領域に含まれる前記ブロック内経路を用いて当該ブロック領域を通過する場合に要する前記内経路コストを管理し、かつ、前記サーバから受け取る前記更新コスト情報に基づき、少なくとも一部の前記ブロック領域に対応する前記内径路コストを更新するブロック管理部と、
前記全体領域における前記始点及び前記終点の位置に基づき、複数の前記ブロック領域を選択するブロック選択部と、
前記ブロック選択部が選択する前記複数のブロック領域のそれぞれに含まれる前記ブロック内経路を経由して、前記始点から前記終点に至る前記移動経路を生成する移動経路生成部と、
前記移動経路に含まれる前記ブロック内経路に対応する前記内経路コストに基づき、前記移動経路を用いて移動する場合の移動コストである経路移動コストを算出する移動コスト算出部と
を有することを特徴とする経路探索システム。
【請求項１７】
始点から終点までの移動に用いるべき移動経路を探索するプログラムであって、
前記始点及び前記終点を含む全体領域を分割した複数のブロック領域のそれぞれに対応して、当該ブロック領域に含まれるブロック内経路を用いて当該ブロック領域を通過する場合に要する移動コストである内経路コストを管理するブロック管理部と、
前記全体領域における前記始点及び前記終点の位置に基づき、複数の前記ブロック領域を選択するブロック選択部と、
前記ブロック選択部が選択する前記複数のブロック領域のそれぞれに含まれる前記ブロック内経路を経由して、前記始点から前記終点に至る前記移動経路を生成する移動経路生成部と、
前記移動経路に含まれる前記ブロック内経路に対応する前記内経路コストに基づき、前記移動経路を用いて移動する場合の移動コストである経路移動コストを算出する移動コスト算出部と
を備えることを特徴とするプログラム。
【請求項１８】
始点から終点までの移動に用いるべき移動経路を探索する経路探索方法であって、
前記始点及び前記終点を含む全体領域を分割した複数のブロック領域のそれぞれに対応して、当該ブロック領域に含まれるブロック内経路を用いて当該ブロック領域を通過する場合に要する移動コストである内経路コストを管理するブロック管理段階と、
前記全体領域における前記始点及び前記終点の位置に基づき、複数の前記ブロック領域を選択するブロック選択段階と、
前記ブロック選択部が選択する前記複数のブロック領域のそれぞれに含まれる前記ブロック内経路を経由して、前記始点から前記終点に至る前記移動経路を生成する移動経路生成段階と、
前記移動経路に含まれる前記ブロック内経路に対応する前記内経路コストに基づき、前記移動経路を用いて移動する場合の移動コストである経路移動コストを算出する移動コスト算出段階と
を備えることを特徴とする経路検索方法。
【国際公開番号】ＷＯ２００４／０５７２７３
【国際公開日】平成１６年７月８日（２００４．７．８）
【発行日】平成１８年４月２０日（２００６．４．２０）
【国際特許分類】
【出願番号】特願２００４−５６１９９７（Ｐ２００４−５６１９９７）
【国際出願番号】ＰＣＴ／ＪＰ２００２／０１３３３３
【国際出願日】平成１４年１２月２０日（２００２．１２．２０）
【出願人】（３０２０４９３３４）ジクー・データシステムズ株式会社 (9)
【Ｆターム（参考）】
【国際公開日】平成１６年７月８日（２００４．７．８）
【発行日】平成１８年４月２０日（２００６．４．２０）
【国際特許分類】
【国際出願番号】ＰＣＴ／ＪＰ２００２／０１３３３３
【国際出願日】平成１４年１２月２０日（２００２．１２．２０）
【出願人】（３０２０４９３３４）ジクー・データシステムズ株式会社 (9)
【Ｆターム（参考）】
[ Back to top ]