経路探索システム、経路探索方法、及び自律移動体
【課題】経路探索空間が広い場合であっても、高速で最適な経路を探索可能な経路探索システム、経路探索方法、及び自律移動体を提供すること。
【解決手段】本発明にかかる経路探索システムは、移動始点から移動終点に到達する自律移動体の移動経路を探索する経路探索システムであって、移動領域を複数の領域に分割する領域分割部111と、領域分割部により分割された複数の領域に対応し、それぞれの領域の評価値を算出する複数の評価値算出部112と、評価値算出部112によって算出された評価値に基づいて経路を決定する経路決定部113とを備え、評価値算出部112が、近傍に存在する領域の評価値と、当該近傍領域から自領域までの移動コストに基づいて評価値を算出する評価値処理部114を有するものである。
【解決手段】本発明にかかる経路探索システムは、移動始点から移動終点に到達する自律移動体の移動経路を探索する経路探索システムであって、移動領域を複数の領域に分割する領域分割部111と、領域分割部により分割された複数の領域に対応し、それぞれの領域の評価値を算出する複数の評価値算出部112と、評価値算出部112によって算出された評価値に基づいて経路を決定する経路決定部113とを備え、評価値算出部112が、近傍に存在する領域の評価値と、当該近傍領域から自領域までの移動コストに基づいて評価値を算出する評価値処理部114を有するものである。
【発明の詳細な説明】
【技術分野】
【0001】
本発明は移動経路を探索する経路探索システム、経路探索方法、及び自律移動体に関する。
【背景技術】
【0002】
従来より、ロボットや車両などの移動体が、移動始点から移動終点へと到達するための移動経路を探索する技術が提案されている。移動経路探索手法としては、A*(エースター)アルゴリズムやダイキストラ法を用いる手法が良く知られている(例えば特許文献1、2)。
【特許文献1】特開平9−229704号公報
【特許文献2】特開2003−233768号公報
【発明の開示】
【発明が解決しようとする課題】
【0003】
しかしながら、従来の経路探索手法では、1つ又は少数の演算処理装置(CPUなど)によって逐次的に経路探索処理を行うため、経路探索に要する計算コストが高くなるという問題がある。特に、A*アルゴリズムなどの幅優先探索アルゴリズムでは、コストが最小である経路候補を順々に延長してゆくため、探索空間が広くなるにつれて、経路候補数が指数的に急増する。これにより、演算対象となる経路候補数の増大によって、移動経路を算出するための演算量が多くなるため、演算を行うためのメモリ使用量が多くなると共に、移動経路を算出するための演算時間が長くなる。従って、このような従来手法では、探索空間が広い場合には非常に大きな計算コストを要することになり、ロボットへの実装が現実的には困難である。
また、ダイキストラ法などの従来手法は、ある時点における計算について、それ以前の計算結果を利用しているため並列処理が困難であり、一般的には、1つ又は少数の演算処理装置(CPUなど)によって別個独立に最短経路を探索する。このため、複数の移動終点に対して同時に最短経路を探索することができないという問題がある。
【0004】
このように、従来の移動経路探索方法では逐次的に経路探索処理を行うため、経路探索空間が広い場合には、短時間で最適な経路を探索することができないという問題があった。
また、複数の移動終点に対して、同時に最適な経路を探索することができないという問題があった。
【0005】
本発明は、かかる課題を解決するためになされたものであり、経路探索空間が広い場合であっても、最適な経路を高速で探索することができる経路探索システム、経路探索方法、及び自律移動体を提供することを第一の目的とする。
【0006】
また、本発明は、複数の移動終点に対して、同時に最適な経路を探索することができる経路探索システム、経路探索方法、及び自律移動体を提供することを第二の目的とする。
【課題を解決するための手段】
【0007】
本発明にかかる経路探索システムは、移動領域内に存在する移動始点より移動を開始し、前記移動領域内に存在する移動終点に到達する自律移動体の移動経路を探索する経路探索システムであって、前記移動領域を複数の領域に分割する領域分割部と、前記領域分割部により分割された複数の領域に対応し、それぞれの領域の評価値を算出する複数の評価値算出部と、前記評価値算出部によって算出された評価値に基づいて経路を決定する経路決定部とを備え、前記評価値算出部が、近傍に存在する領域の評価値と、当該近傍領域から自領域までの移動コストに基づいて評価値を算出する評価値処理部を有するものである。
【0008】
これにより、移動領域を複数の領域に分割することで、経路探索のための移動コストを領域間の幾何学的な距離によって表現することができる。そして、複数の評価値算出部が、このような幾何学的な距離と近傍領域の評価値とに基づいて、それぞれの領域における評価値算出処理を並列に実行することで、逐次的に各領域の評価値を算出する場合に比べて、経路探索に要する計算コストを大きく削減することができる。従って、経路探索空間が広い場合であっても、最適な経路を高速で探索することができる。
【0009】
さらに、移動終点として複数の領域を指定する場合においても、複数の移動終点から評価値算出処理がそれぞれ開始されて、それぞれの処理が並列に実行されながらその近傍領域へと伝わっていく。このため、移動終点でない他の領域を注目する領域としたとき、その注目する領域に最初に伝わった処理は、複数の移動終点のうちでそれぞれの移動終点からその近傍領域を介して最初にその注目する領域へと処理を伝えることができた移動終点から開始された処理となる。即ち、評価値算出処理の実行後に、各領域において算出される評価値は、複数の移動終点のうちで最も早く評価値算出処理を各領域に対して伝えることが可能な移動終点であって、その移動終点からの移動コストに基づいた評価値となる。従って、このような評価値によれば、複数の移動終点に対して同時に最適な経路を探索することができる。
【0010】
また、評価値算出部は、近傍領域の評価値のうち最も小さい評価値と、その近傍領域から自領域までの幾何学的な距離に応じた移動コストに基づいて評価値を算出してもよい。このように、近傍領域における最小の評価値と、その近傍領域から自領域までの幾何学的な距離に応じた移動コストに基づいて評価値を算出することで、容易に評価値を算出することができる。
【0011】
さらにまた、前記評価値算出部は、前記評価値処理部による評価値算出結果を格納する第一の評価値記憶部及び第二の評価値記憶部を更に備え、前記評価値処理部が、第一の評価値記憶部に格納された自領域の評価値、及び近傍に存在する領域の評価値に基づいて評価値算出処理を実行するか否かを判定し、判定の結果、評価値算出処理を実行する場合には、当該近傍領域の評価値と、当該近傍領域から自領域までの移動コストに基づいて自領域の評価値を算出し、当該評価値算出結果を第二の評価値記憶部に出力するようにしてもよい。このように、全ての評価値算出部において、評価値算出処理を実行するか否かを、それぞれ第一の評価値記憶部に格納された評価値に基づいて判定し、評価値算出結果を、それぞれ第一の評価値記憶部とは異なる第二の評価値記憶部に出力する。これにより、1回の評価値算出処理の結果、評価値算出結果の干渉を防ぐことができると共に、1近傍を越えて評価値が算出されないよう制限することができるため、1近傍領域に含まれる領域の評価値のみを算出させることができる。従って、複数の評価値算出部による評価値算出処理のタイミングを同期させることができる。
【0012】
また、前記経路決定部は、前記移動始点に対応する領域から前記移動終点に対応する領域に向けて、算出された評価値のうち最も小さい評価値を有する近傍領域を選択してゆくようにしてもよい。このように、移動始点に対応する領域から移動終点に対応する領域に向けて、算出された評価値のうち最小の評価値を有する近傍領域を選択してゆくことで、簡単に経路を決定することができる。
【0013】
さらにまた、前記領域分割部により分割された前記領域について、自領域に対して隣接した領域を越えた領域を近傍領域として設定可能としてもよい。これにより、注目する領域に直接隣接していない領域についても近傍領域に含めることで、それら領域間を通過する経路を作成することができる。従って、移動始点から移動終点へと至る経路の角度分解能を柔軟に設定することができ、より滑らかな経路を作成することができる。
【0014】
また、前記経路探索システムは、前記評価値算出部による評価値算出処理を実行可能又は不能に設定する状態設定部を更に備えるようにしてもよい。これにより、所望の評価値算出部について、評価値算出処理を行うタイミングを調整することができる。例えば、環境に応じて、特定の評価値算出部の評価値算出処理を一定期間実行不能に設定することで、それら評価値算出部は待ち状態となり、対応する領域には評価値が算出されない。一定期間経過後に評価値算出処理が実行可能となった場合に、それら待ち状態を経た評価値算出部によって算出される評価値は、既に算出された他の領域の評価値に比べて、待ち時間の分だけ相対的に大きな評価値が算出される。即ち、評価値算出処理において、待ち時間を評価値に反映させることで、特定の領域の評価値を大きくすることができる。従って、評価値の高い領域は経路として選択されにくくなるため、特定の領域を避けるように柔軟に経路を作成することができる。
【0015】
また、本発明にかかる経路探索システムは、移動領域内に存在する移動始点より移動を開始し、前記移動領域内に存在する移動終点に到達する自律移動体の移動経路を探索する経路探索システムであって、前記移動領域を複数の領域に分割する領域分割部と、前記領域分割部により分割された複数の領域に対応し、近傍に存在する領域の評価値のうち最も小さい評価値と、当該近傍領域から自領域までの幾何学的な距離に応じた移動コストに基づいて、それぞれの領域における評価値算出処理を並列に実行する評価値算出部と、前記評価値算出部によって算出された評価値に基づいて経路を決定する経路決定部とを備え、前記移動領域内に複数の移動終点が存在する場合には、前記評価値算出部は当該移動終点を含む領域のそれぞれから評価値算出処理を開始し、前記経路決定部は当該評価値算出処理結果に基づいて任意の移動始点より経路決定処理を開始するものである。
【0016】
これにより、移動終点として複数の領域を指定する場合においても、評価値算出部が、それぞれ並列に評価値算出処理を実行すると共に、近傍領域における評価値の最小値及び自領域までの移動コストに基づいて評価値算出処理を実行する。このため、各領域における評価値は、複数の移動終点からの移動コストの総和が最小となる評価値が算出され、最も移動コストの少ない移動終点までの経路を探索することができる。従って、このような評価値によれば、複数の移動終点に対して同時に最適な経路を探索することができる。
【0017】
本発明にかかる経路探索方法は、移動領域内に存在する移動始点より移動を開始し、前記移動領域内に存在する移動終点に到達する自律移動体の移動経路を探索する経路探索方法であって、前記移動領域を複数の領域に分割する領域分割ステップと、前記領域分割部により分割された複数の領域における評価値算出処理を並列に実行する評価値算出ステップと、前記評価値算出ステップによって算出された評価値に基づいて経路を決定する経路決定ステップとを備え、前記評価値算出ステップでは、近傍に存在する領域の評価値と、当該近傍領域から自領域までの移動コストに基づいて評価値を算出するものである。
【0018】
これにより、移動領域を複数の領域に分割することで、経路探索のための移動コストを領域間の幾何学的な距離によって表現することができる。そして、複数の評価値算出ステップが、このような幾何学的な距離と近傍領域の評価値とに基づいて、それぞれの領域における評価値算出処理を並列に実行することで、逐次的に各領域の評価値を算出する場合に比べて、経路探索に要する計算コストを大きく削減することができる。従って、経路探索空間が広い場合であっても、最適な経路を高速で探索することができる。
【0019】
さらに、移動終点として複数の領域を指定する場合においても、評価値算出処理は複数の移動終点から開始され、それぞれ並列に実行されながらその近傍領域へと処理が伝わっていく。このため、移動終点を含まない他の領域において、最も早くその領域に伝わった処理は、その処理を最初に開始した移動終点から開始された処理によるものとなる。即ち、評価値算出処理の実行後に、各領域において算出される評価値は、複数の移動終点のうち、各領域に対して最も早く評価値算出処理を伝えることが可能な移動終点であって、その移動終点からの移動コストに基づいた評価値となる。従って、このような評価値によれば、複数の移動終点に対して同時に最適な経路を探索することができる。
【0020】
また、前記評価値算出ステップでは、近傍領域の評価値のうち最も小さい評価値と、当該近傍領域から自領域までの幾何学的な距離に応じた移動コストに基づいて評価値を算出するようにしてもよい。このように、近傍領域における最小の評価値と、その近傍領域から自領域までの幾何学的な距離に応じた移動コストに基づいて評価値を算出することで、容易に評価値を算出することができる。
【0021】
さらにまた、前記経路決定ステップでは、前記移動始点に対応する領域から前記移動終点に対応する領域に向けて、算出された評価値のうち最も小さい評価値を有する近傍領域を選択してゆくようにしてもよい。このように、移動始点に対応する領域から移動終点に対応する領域に向けて、算出された評価値のうち最小の評価値を有する近傍領域を選択してゆくことで、簡単に経路を決定することができる。
【0022】
また、前記領域分割ステップにより分割された前記領域について、自領域に対して隣接した領域を越えた領域を近傍領域として設定可能としてもよい。これにより、注目する領域に直接隣接していない領域についても近傍領域に含めることで、それら領域間を通過する経路を作成することができる。従って、移動始点から移動終点へと至る経路の角度分解能を柔軟に設定することができ、より滑らかな経路を作成することができる。
【0023】
さらにまた、前記経路探索方法は、前記評価値算出ステップによる評価値算出処理を実行可能又は不能に設定する状態設定ステップを更に備えるようにしてもよい。これにより、所望の領域について、評価値算出処理を行うタイミングを調整することができる。例えば、環境に応じて、特定の領域の評価値算出処理を一定期間実行不能に設定することで、それら評価値算出ステップは待ち状態となり、対応する領域には評価値が算出されない。一定期間経過後に評価値算出処理が実行可能となった場合に、それら待ち状態を経た評価値算出ステップによって算出される評価値は、既に算出された他の領域の評価値に比べて、待ち時間の分だけ相対的に大きな評価値が算出される。即ち、評価値算出処理において、待ち時間を評価値に反映させることで、特定の領域の評価値を大きくすることができる。従って、評価値の高い領域は経路として選択されにくくなるため、特定の領域を避けるように柔軟に経路を作成することができる。
【0024】
本発明にかかる経路探索プログラムは、移動領域内に存在する移動始点より移動を開始し、前記移動領域内に存在する移動終点に到達する自律移動体の移動経路を探索する経路探索プログラムであって、コンピュータに対して、前記移動領域を複数の領域に分割する領域分割ステップと、前記領域分割部により分割された複数の領域に対応し、近傍に存在する領域の評価値と、当該近傍領域から自領域までの移動コストに基づいて、それぞれの領域における評価値算出処理を並列に実行する評価値算出ステップと、前記評価値算出ステップによって算出された評価値に基づいて経路を決定する経路決定ステップとを実行させるものである。
【0025】
これにより、移動領域を複数の領域に分割することで、経路探索のための移動コストを領域間の幾何学的な距離によって表現することができる。そして、評価値算出ステップが、このような幾何学的な距離と近傍領域の評価値とに基づいて、それぞれの領域における評価値算出処理を並列に実行することで、逐次的に各領域の評価値を算出する場合に比べて、経路探索に要する計算コストを大きく削減することができる。従って、経路探索空間が広い場合であっても、最適な経路を高速で探索することができる。
【0026】
さらに、移動終点として複数の領域を指定する場合においても、評価値算出処理は複数の移動終点から開始され、それぞれ並列に実行されながらその近傍領域へと処理が伝わっていく。このため、移動終点を含まない他の領域において、最も早くその領域に伝わった処理は、その処理を最初に開始した移動終点から開始された処理によるものとなる。即ち、評価値算出処理の実行後に、各領域において算出される評価値は、複数の移動終点のうち、各領域に対して最も早く評価値算出処理を伝えることが可能な移動終点であって、その移動終点からの移動コストに基づいた評価値となる。従って、このような評価値によれば、複数の移動終点に対して同時に最適な経路を探索することができる。
【0027】
本発明にかかる自律移動体は、移動領域内に存在する移動始点より移動を開始し、前記移動領域内に存在する移動終点に到達する移動経路を探索可能な自律移動体であって、前記移動領域を複数の領域に分割する領域分割部と、前記領域分割部により分割された複数の領域に対応し、それぞれの領域の評価値を算出する複数の評価値算出部と、前記評価値算出部によって算出された評価値に基づいて経路を決定する経路決定部とを備え、前記評価値算出部が、近傍に存在する領域の評価値と、当該近傍領域から自領域までの移動コストに基づいて評価値を算出する評価値処理部を有するものである。
【0028】
これにより、移動領域を複数の領域に分割することで、経路探索のための移動コストを領域間の幾何学的な距離によって表現することができる。そして、複数の評価値算出部が、このような幾何学的な距離と近傍領域の評価値とに基づいて、それぞれの領域における評価値算出処理を並列に実行することで、逐次的に各領域の評価値を算出する場合に比べて、経路探索に要する計算コストを大きく削減することができる。従って、経路探索空間が広い場合であっても、最適な経路を高速で探索することができる。
【0029】
さらに、移動終点として複数の領域を指定する場合においても、評価値算出処理は複数の移動終点から開始され、それぞれ並列に実行されながらその近傍領域へと処理が伝わっていく。このため、移動終点を含まない他の領域において、最も早くその領域に伝わった処理は、その処理を最初に開始した移動終点から開始された処理によるものとなる。即ち、評価値算出処理の実行後に、各領域において算出される評価値は、複数の移動終点のうち、各領域に対して最も早く評価値算出処理を伝えることが可能な移動終点であって、その移動終点からの移動コストに基づいた評価値となる。従って、このような評価値によれば、複数の移動終点に対して同時に最適な経路を探索することができる。
【発明の効果】
【0030】
本発明によれば、経路探索空間が広い場合であっても、最適な経路を高速で探索することができる経路探索システム、経路探索方法、及び自律移動体を提供することを第一の目的とする。
【0031】
また、本発明によれば、複数の移動終点に対して、同時に最適な経路を探索することができる経路探索システム、経路探索方法、及び自律移動体を提供することを第二の目的とする。
【発明を実施するための最良の形態】
【0032】
以下、本発明を適用した具体的な実施の形態について、図面を参照しながら詳細に説明する。尚、各図面において、同一要素には同一の符号を付しており、説明の明確化のため、必要に応じて重複説明を省略する。
【0033】
発明の実施の形態1.
本発明の実施の形態1にかかる経路探索システムでは、自律移動体としてロボットを用いている。ロボットは、例えば、それぞれ独立して回転制御される二つの車輪を備えたものでもよく、2輪よりも多い、例えば4輪走行のロボットや、1輪走行のロボット、2足歩行・4足歩行のロボットであってもよい。また、ロボットに限らず、2輪走行や4輪走行の車両にも適用できる。本例におけるロボットは、障害物を検出するセンサやカメラを備え、検出された障害物に応じて、これを避けるように経路探索を行なう。
【0034】
当該経路探索システムは、移動領域を複数の格子状の領域に分割し、分割された複数の領域に対応する評価値算出部を備える。各評価値算出部は、独立した評価値処理部及び評価値記憶部を備え、各評価値算出部に対応するそれぞれの領域の評価値を算出し、その結果を格納する。評価値算出処理は、近傍に存在する領域の評価値と、その近傍領域から自領域までの移動コストに基づいて実行される。そして、経路探索システムは、各評価値算出部によって算出された評価値に基づいて経路決定処理を実行する。
【0035】
また、本実施の形態1にかかる経路探索システムは、経路探索問題を、離散化された移動領域において、その移動領域を伝播する仮想的なコストポテンシャル波の伝播履歴を求める問題と置き換えて解くものである。移動領域を構成する評価値算出部間の相互作用を利用することで、最短経路を高速に探索することができる。後述するように、移動領域の次元数をpとすると、従来手法ではO(np)の計算時間が必要であったが、本実施の形態1にかかる経路探索システムでは、O(n√p)の計算時間で最短経路を得ることができる。
【0036】
図1は、本実施の形態1にかかる経路探索システムの概略構成を示すブロック図である。図1に示されるように、経路探索システム1は、経路探索処理部11と経路探索記憶部12により構成されている。経路探索処理部11は、領域分割部111、複数の評価値算出ユニット112、及び経路決定部113を備えている。評価値算出部としての評価値算出ユニット112は、物理的に独立した評価値算出ユニットであって、評価値算出処理を並列に実行する。
【0037】
経路探索記憶部12には、ロボットが移動する移動領域全体の形状に、略一定間隔d(例えば10cm)に配置された格子点を結ぶグリッド線を仮想的に描写することで得られるグリッドマップが記憶されている。ロボットは、GPS等から得られた位置情報を、このグリッドマップ上における自己の位置に置き換えて、グリッドマップ上における自己位置を認識する。グリッドマップ上において、ロボットの自己位置に相当する場所、および目的地である移動終点、および移動終点におけるロボットの移動方向が特定される。ロボットは、グリッドマップ上において特定された自己位置を移動始点から、目的地である移動終点までの移動経路を作成し、作成された移動経路に従って移動を行う。
【0038】
領域分割部111は、ロボットが移動する移動領域を格子状の領域に分割する。ここでは、上述の略一定間隔d(例えば10cm)に配置された格子点を囲む複数の領域に分割する。図2は、移動領域を分割して、離散化された複数の領域Cnを示す概念図である。尚、領域分割部111による分割方法はこれに限定されない。例えば、上述の分割後の領域よりも大きな領域へと分割することで、経路探索に要する時間をより短縮することができる。また、グリッドマップが格子状に並んだノードと、各ノードを接続するリンクを備える場合には、分割された領域は、グリッドマップ上に配置されたノードに対応するものとして扱ってもよい(この場合には、近傍領域はリンクによって規定される)。即ち、各領域は各ノードを示し、各ノードに対する評価値を算出し、それらノードに付与された評価値に基づいて、経路を選択するようにしてもよい。
【0039】
領域分割部111により分割された領域間の接続関係が定められ、注目する領域に接続する領域を近傍領域とする。図3は、離散化された領域間の接続関係を説明するための概念図である。図3(a)では、注目する領域C0に対して、隣接領域C1乃至C8を近傍領域として定めるものである。また、図3(b)では、注目する領域C0に対して、隣接領域C1乃至C8に加えて、さらに領域C9乃至C16を近傍領域として定めるものである。このように、自領域に対して隣接した領域を越えた領域を近傍領域として設定可能とすることで、自領域及びそれら近傍領域間を通過する経路を作成することができる。このようにすれば、移動始点から移動終点へと至る経路の角度分解能を柔軟に設定することができ、より滑らかな経路を作成することができる。
【0040】
評価値算出ユニット112は、領域分割部111により分割された領域に対応し、それぞれの領域の評価値を算出する評価値処理部114を有する。図4は、評価値算出ユニット112の構成を示す概念図である。図4(a)に示すように、評価値算出ユニット112は、評価値処理部114と、第一の評価値記憶部及び第二の評価値記憶部としての、少なくとも2つの評価値記憶部32及び33を備える。評価値算出ユニット112には、状態設定部としての状態設定用信号線34が接続されている。
【0041】
尚、評価値算出ユニット112はいずれも同一の構成を有しており、簡易な構成により経路探索システム1を構成することができる。各評価値算出ユニット112は、分割された各領域に一対一で対応付けてもよいし、一つの評価値算出ユニット112が、複数の分割された領域に対応するようにしてもよい。また、評価値算出ユニット112は、例えばFPGA(Field Programmable Gate Array)等のプログラム可能な装置を用いることによって容易に構成することができる。そして、図4(b)に示すように、複数の評価値算出ユニット112Unが配列され、それぞれが分割された複数の領域に対応する。このような配列構造によれば、ロボットなどに対しても容易に実装化することができる。
【0042】
状態設定用信号線34は、評価値処理部114による評価値算出処理を実行可能状態又は実行不能状態に設定するための状態設定信号を評価値処理部114へと送信する。これにより、所望の評価値算出ユニット112について、評価値算出処理を行うタイミングを調整することができる。即ち、評価値算出処理を実行させる場合には、評価値算出ユニット112へと評価値算出処理を実行可能とする状態設定信号を送信し、評価値算出処理を実行させない場合には、評価値算出処理を実行不能とする状態設定信号を送信する。
【0043】
評価値算出ユニット112が評価値算出処理を実行可能とする状態設定信号を受信した場合には、評価値処理部114は、近傍領域の評価値のうち最も小さい評価値と、その近傍領域から自領域までの幾何学的な距離に応じた移動コストに基づいて評価値を算出し、その結果を評価値記憶部32及び33に格納する。尚、評価値算出処理の詳細については後述する。
【0044】
一方、評価値算出ユニット112が評価値算出処理を実行不能とする状態設定信号を受信した場合には、評価値処理部114は評価値算出処理を実行しない。例えば、環境に応じて、特定の評価値算出ユニット112の評価値算出処理を一定期間実行不能に設定することで、それら評価値算出ユニット112を待ち状態として、対応する領域における評価値を算出させないようにすることができる。一定期間経過後に評価値算出処理が実行可能となった場合に、それら待ち状態を経た評価値算出ユニット112によって算出される評価値は、既に算出された他の領域の評価値に比べて、待ち時間の分だけ相対的に大きな評価値が算出される。即ち、評価値算出処理において、待ち時間を評価値に反映させることで、特定の領域の評価値を大きくすることができる。従って、後述するように、評価値の大きな領域は経路として選択されにくくなるため、特定の領域を避けるように柔軟に経路を作成することができる。尚、状態設定用信号線34は、評価値記憶部32及び33に格納された評価値算出結果を初期化するための初期化信号を送信するようにしてもよい。
【0045】
経路決定部113は、評価値算出ユニット112によって算出された評価値に基づいて採用する経路を決定する。より詳細には、移動始点に対応する領域から移動終点に対応する領域に向けて、算出された評価値のうち最も小さい評価値を有する近傍領域を選択してゆく。選択された領域を通過する経路が、移動始点から移動終点へと至る最短経路となる。
【0046】
続いて、本実施の形態1にかかる経路探索システム1の具体的な処理について、図5に示すフローチャート、及び図6、7に示すグリッドマップを用いて説明する。ここで、図6及び7に示すグリッドマップは、ロボットの目標軌道となる目標経路を、グリッド状に離散化された領域の集合として表現するものである。グリッド座標を利用するメリットは、最短経路探索を容易に実行できる点や、確実に目的地に到達できる経路を得ることができる点にある。グリッドマップに関する情報は、経路探索システム1を構成するコンピュータの経路探索記憶部12に格納される。ここで、グリッドマップに関する情報には、各領域の座標情報、各領域の近傍領域を示す領域間の接続情報、及び各領域に関連付けられた評価値情報が含まれる。領域の評価値は、それぞれの領域に対応する評価値算出ユニット112によって算出される。
【0047】
まず、領域分割部111により、移動領域が複数の領域に分割され、分割されたそれぞれの領域に対して評価値算出ユニット112が対応付けられる(S101)。ここでは、移動領域は、グリッド数と等しい数の領域に分割される。例えば、移動領域が2次元平面である場合には、それぞれ10cm×10cmの広さを持つ離散的な複数の領域が分割生成される。分割された各領域に対して、それぞれの領域の評価値を算出する評価値算出ユニット112が対応付けられる。
【0048】
次に、全ての評価値算出ユニット112に対して初期値を代入する(S102)。各領域の状態として、進入が禁止される禁止状態、評価値が未計算である未計算状態、及び評価値を計算済みである計算済み状態からなる3状態を想定する。それぞれの状態に対応する初期値を評価値算出ユニット112に代入する。評価値算出処理の開始段階であるS102においては、経路探索対象となる領域のうち、進入禁止領域以外の領域に対応する評価値算出ユニット112の評価値記憶部32及び33には、初期値として十分大きな値(例えば1.0×10^7)を代入する。進入禁止領域に対応する評価値算出ユニット112の評価値記憶部32及び33には、初期値として十分大きな値(例えば1.0×10^9)を代入する。ここでは、初期値として、後述する評価値算出処理によって算出される評価値を十分上回る値を採用して代入する。尚、領域の状態をこのような初期値を設定することで判断してもよいし、領域の状態を示す状態情報を各評価値算出ユニット112に格納するようにしてもよい。
【0049】
次に、移動終点を指定して、その移動終点を含む領域に対応する評価値算出ユニット112について、その評価値記憶部32又は評価値記憶部33の少なくとも一方に評価値の最小値(例えば0)を代入する(S103)。以下では、評価値記憶部32のみに評価値の最小値が代入されたものとして説明する。
【0050】
次に、評価値算出処理を開始するための計算開始クロックC1を発生する(S104)。状態設定用信号線34を介して、CPUのクロックに相当するパルスが各評価値算出ユニット112へと送信され、各評価値算出ユニット112においてS105乃至108における処理が実行される。またこのとき、評価値算出処理を実行させる評価値算出ユニット112に対しては、評価値算出処理を実行可能とする状態設定信号が送信され、評価値算出処理を実行させない評価値算出ユニット112に対しては、評価値算出処理を実行不能とする状態設定信号が送信される。
【0051】
各評価値算出ユニット112は、対応する自領域の評価値及び近傍領域の評価値に基づいて、以下のようにして自領域の評価値を更新してゆく。まず、評価値記憶部32に格納されている値について、自領域の評価値である自己評価値が、初期値から更新されているか否かを判定する(S105)。
【0052】
ステップS105における判定の結果、自己評価値が初期値のままである場合(自領域の評価値が未計算である場合)には、近傍領域に対応する評価値算出ユニット112において、その評価値記憶部32に格納されている値として、初期値ではない評価値が存在しているか否かを判定する(S106)。
【0053】
ステップS106における判定の結果、近傍領域に初期値以外の値が存在する場合(近傍領域の評価値が計算済みである場合)には、近傍領域の評価値のうち最も小さい評価値と、その最小の評価値を持つ近傍領域から自領域までの幾何学的な距離に応じた移動コストに基づいて自己の領域の評価値を算出し、その結果を評価値記憶部33に格納する(S107)。ここでは、以下の式に基づいて自己の領域の評価値を算出する。
自己評価値=近傍領域の最小評価値+近傍領域から自領域までの移動コスト
【0054】
一方、ステップS105又はS106における判定の結果、評価値記憶部32に格納されている自己評価値が初期値から更新されている場合、又は近傍領域に初期値以外の値が存在しない場合には、現在の自己評価値を更新せずにそのまま維持する(S108)。ここでは、自己評価値を維持する処理として、評価値記憶部32に格納されている評価値を評価値記憶部33へと出力して格納する。このように処理することで、現在の自己評価値を簡易な処理によって維持することができる。尚、評価値記憶部32に格納されている評価値を評価値記憶部33へと出力せずに、何も処理を実行しないようにしてもよい。
【0055】
このように、全ての評価値算出ユニット112において、ステップS105乃至108における評価値算出処理の実行を、それぞれ評価値記憶部32に格納された評価値に基づいて判定し、評価値算出結果を、それぞれ評価値記憶部32とは異なる評価値記憶部33に出力する。これにより、1回の評価値算出処理の結果、評価値算出結果の干渉を防ぐことができると共に、1近傍を越えて評価値が算出されないよう制限することができるため、1近傍領域に含まれる領域の評価値のみを算出させることができる。従って、複数の評価値算出ユニット112による評価値算出処理のタイミングを同期させることができる。尚、次のクロックC2によってステップS105乃至108における処理が実行される場合には、ステップS105乃至S108の処理において、評価値記憶部33に格納されている評価値に基づいて評価値算出処理が実行され、その結果が評価値記憶部32に格納される。更には、クロックC3によってS105乃至108における処理が実行される場合には、評価値記憶部32に格納されている評価値に基づいて評価値算出処理が実行され、その結果が評価値記憶部33に格納される。
【0056】
移動始点を含む領域に対応する評価値算出ユニット112について、その評価値記憶部32又は評価値記憶部33のいずれか一方に初期値ではない評価値が存在しているか否かを判定する(S109)。ステップS109における判定の結果、評価値が存在していない場合には、移動始点を含む領域の評価値は未だに算出されていない未計算状態であるため、ステップS104へと戻り再び各評価値算出ユニット112により領域の評価値算出処理を実行する。
【0057】
一方、ステップS109における判定の結果、移動始点に評価値が存在している場合には、移動始点を含む領域の評価値が計算済みの状態となったことから、評価値算出処理を終了して、ステップS110以降の経路決定処理へと進む。
【0058】
尚、ステップS109における評価値算出処理を終了させる条件としては、全ての領域に対応する評価値が変化しなくなった場合に処理を終了させるようにしてもよい。即ち、全ての評価値算出ユニット112において、評価値記憶部32及び33に格納された評価値が同じ値のまま変化しなくなった場合に処理を終了させることができる。また、このような終了条件をステップS109における終了条件に加えて判定させるように構成することで、移動始点から移動終点までの経路が存在しない場合であっても評価値算出処理を終了させることができる。
【0059】
続いて、評価値算出処理を終了した後、経路決定部113は、分割された各領域の評価値に基づいて、移動始点を含む領域から開始し、その近傍領域において最小の評価値を持つ領域を経路として選択する(S110)。そして、ステップS110において選択した領域が、移動終点を含む領域であるか否かを判定する(S111)。ステップS111における判定の結果、選択された領域が移動終点を含む領域に到達していない場合には、ステップS110へと戻り、次の経路として選択した領域の近傍領域を選択する。一方、ステップS111における判定の結果、選択された領域が移動終点を含む領域に到達した場合には、ステップS110において選択された領域の系列を経路として出力し、経路決定処理を終了する(S111)。このように、移動始点に対応する領域から移動終点に対応する領域に向けて、領域の評価値のうち最も小さい評価値を有する近傍領域を順次選択してゆくことで、選択された領域を通過する経路を最短経路として決定することができる。
【0060】
図6は、評価値算出処理を説明するための一例を示す図である。図6では、移動領域を横16個、縦13個の領域に分割し、各領域の近傍領域を各領域に隣接した前後左右4方向に隣接する領域とした。図において斜線領域は進入禁止領域を示し、外周上の領域は経路探索対象外である領域を示す。図に示す領域Gを移動終点とし、領域Gの初期値を0に設定した場合に、評価値算出ユニット112による評価値算出結果を各領域に示す。尚、ここでは、近傍領域から自領域までの移動コストの値を5とした。分割された208個の領域のうち、39個の領域が進入禁止領域であり、169個の領域が経路探索対象領域である。従来手法では、領域の個数相当の計算ステップが必要となるため、計169回の計算が必要となる。一方、本実施の形態1にかかる経路探索システム1によれば、各評価値算出ユニット112がそれぞれ並列に評価値を算出するため、計22回の計算によって評価値を算出することができる。従って、従来手法と比較して、凡そ8分の1の計算時間によって経路探索のための評価値算出処理を実行することができ、移動領域が広くなる程、計算時間短縮による効果は顕著なものとなる。
【0061】
図7は、経路決定処理を説明するための一例を示す図である。図7では、図6に示した評価値算出後の領域について、図に示す領域Sを移動始点とし、移動始点Sから移動終点Gまでの経路決定処理の結果を示している。移動始点Sから移動終点Gへと向かって選択された領域の系列について、それら領域を通過する白抜き矢印が移動始点Sから移動終点Gまでの最短経路を示している(同時に、移動終点Gから移動始点Sまでの最短経路を意味する)。また、移動始点Sにおける評価値110は、移動始点Sから移動終点Gまでに要する移動コストの総コストを意味している。
【0062】
以上に説明したように、本実施の形態1にかかる経路探索システム1は、移動領域を複数の領域に分割することで、経路探索のための移動コストを領域間の幾何学的な距離によって表現することができる。そして、複数の評価値算出ユニット112が、このような幾何学的な距離と近傍領域の評価値とに基づいて、それぞれの領域における評価値算出処理を並列に実行することで、逐次的に各領域の評価値を算出する場合に比べて、経路探索に要する計算コストを大きく削減することができる。
【0063】
図8は、本実施の形態1にかかる経路探索システム1(発明手法)による計算時間短縮効果を説明するためのグラフを示す図である。図では、一辺L個のグリッドからなるn次元正立方体探索空間において、その対角要素間の経路(最長経路)を探索するために必要な計算ステップの見積もり(最大の計算ステップ数)を示す。L=正立方体の一辺のグリッド数[grid]、n=探索空間の次元数[1]とした場合に、経路探索に要する計算の繰り返し回数(steps)は以下の式に基づいて見積もることができる。
従来手法:steps=Ln
発明手法:steps=L×√n
例えば、一辺が20[grid]の7次元正立方体探索空間内において最短経路探索を行った場合、従来の経路探索手法と、本実施の形態1にかかる経路探索システム1による計算ステップとを比較すると、経路探索システム1は、従来手法に対しておよそ1億分の1のステップ数によって経路探索を実行することができる。
【0064】
また、本実施の形態1にかかる経路探索システム1では、近傍とする領域を変更することで、評価値を算出するタイミングを環境に応じて調整することができる。例えば、接続関係をより広範囲の領域間に広げ、遠方に存在する領域を近傍領域とすることで、遠方の領域に基づいて自領域の評価値を算出することができる。即ち、接続関係を有する遠方の領域における評価値が算出された場合には、次のタイミングにおいて自領域の評価値を算出することができるため、直接隣接する領域を近傍領域とした場合と比べて、評価値算出処理をより早くに実行させることができる。従って、経路探索処理をより短時間で実行させることができるため、環境において動的な障害物が存在する場合であっても効果的に障害物に対処することが可能となる。
【0065】
発明の実施の形態2.
本実施の形態2にかかる経路探索システムは、移動領域内に複数の移動終点を指定した場合には、当該移動終点を含む領域のそれぞれから評価値算出処理を開始し、当該評価値算出処理結果に基づいて任意の移動始点より経路を探索する。評価値算出部は、いずれかの移動始点を含む領域において評価値が算出された場合に、評価値算出処理を終了させることができる。経路決定部は、移動領域内の任意の領域を移動始点として指定し、算出された領域の評価値に基づいて、移動始点に対応する領域から、算出された評価値のうち最も小さい評価値を有する近傍領域を選択してゆく。このとき、複数の移動終点に対応する領域のうち、当該移動始点から最短の移動コストで到達可能な移動終点に向けて経路を決定することができる。尚、以下で説明しない構成及び処理に関しては、本実施の形態1における図1乃至図5で説明した構成及び処理と基本的に同一である。
【0066】
図9は、複数の移動終点が指定された場合に、評価値算出処理を説明するための一例を示す図である。図9では、移動領域を横16個、縦13個の領域に分割し、近傍領域は各領域の前後左右方向に直接隣接する領域とした。図において斜線領域は進入禁止領域を示し、外周上の領域は経路探索対象外である探索領域外を示す。図に示す領域G1及びG2を移動終点とし、領域G1及びG2の初期値を0に設定した場合に、評価値算出ユニット112による評価値算出結果を各領域に示す。尚、ここでは近傍領域から自領域までの移動コストの値は5とした。また、複数の移動終点は上述した図5のステップS103において、複数の移動終点を含む領域に対応する評価値算出ユニット112について、その評価値記憶部32又は評価値記憶部33の少なくとも一方に評価値の最小値(例えば0)を代入すればよい。
【0067】
図10は、複数の移動終点が指定された場合に、経路決定処理を説明するための一例を示す図である。図10では、図9に示した評価値算出後の領域について、図に示す領域S1を移動始点とし、移動始点S1から経路決定処理を実行した。その結果、決定された経路は、移動始点S1から移動終点G1へと到達する経路であった。また、移動始点S1における評価値60は、移動始点S1から移動終点G1までに要する移動コストの総コストを意味している。これにより、移動終点G2に比べて、移動終点G1へと到達する経路長のほうがより短いものであり、移動始点S1からは、移動終点G1へと移動するほうがより少ない移動コストで済むことを示している。
【0068】
このように、複数の領域について、評価値算出ユニット112が、それぞれ並列に評価値算出処理を実行すると共に、近傍領域における評価値の最小値及び自領域までの移動コストに基づいて評価値算出処理を実行する。このため、各領域における評価値は、複数の移動終点からの移動コストの総和が最小となる評価値が算出され、最も移動コストの少ない移動終点までの経路を探索することができる。従って、このような評価値によれば、複数の移動終点に対して同時に最適な経路を探索することができる。例えば、移動領域内に複数のゴミ箱が存在し、それらゴミ箱を含む領域を移動終点とした場合、ロボットは現在位置である移動始点から、移動コストが最小となる移動終点を選択し、その移動終点へと到達する最短経路を移動することが好ましい。また、マニピュレータによる軌道計画を行う場合には、対象物を把持する際に最も把持しやすい位置・姿勢へと至るマニュピレータの軌道を計画することが好ましい。そのため、現在の位置・姿勢から、目標となる位置・姿勢へと到達する最適な軌道計画が必要となるが、そのような目標位置・姿勢は複数存在するものと考えられる。従って、このような場合においても本実施の形態2にかかる経路探索システムを適用することによって、複数の移動終点に対して、同時に最適な移動経路及び軌道を作成することができる。
【0069】
また、本実施の形態2にかかる経路探索システムによれば、複数の移動終点に対して同時に最適な経路を探索することができるため、複数の領域からなる領域範囲を、移動終点エリアとして指定することもできる。これにより、ひとつの領域のみを正確に移動終点として指定する必要がなく、移動終点として指定したい凡その範囲を指定するだけで経路を探索することができ、環境に応じてより柔軟に経路探索を実行させることができる。尚、複数の移動終点に対して、従来手法を用いてそれぞれの移動終点への経路を探索した場合には、算出される最短経路は同じ経路長となるものの、従来手法ではそれぞれの移動終点に対して別々に経路を探索するため、移動終点の個数に応じた計算時間を要する。一方、本実施の形態2にかかる経路探索システムによれば、それぞれの評価値算出ユニット112が並列に評価値を算出してゆくため、移動終点の個数に応じて計算時間が増加することはなく、移動終点の個数が増加した場合であっても、従来手法と比較してより高速に経路探索処理を実行することができる。
【0070】
発明の実施の形態3.
本実施の形態3にかかる経路探索システムは、移動領域内に存在する移動始点より移動を開始し、移動領域内に存在する移動終点に到達する自律移動体の移動経路を探索する経路探索システムであって、移動領域を複数の領域に分割する領域分割部と、領域分割部により分割された複数の領域に対応し、それぞれの領域の評価値を算出する評価値算出部と、評価値算出部によって算出された評価値に基づいて経路を決定する経路決定部とを備え、評価値算出部が、近傍領域の評価値と、その近傍領域から自領域までの移動コストに基づいて評価値を算出するものである。本実施の形態3にかかる経路探索システムでは、上述した実施の形態とは異なり、複数の評価値算出ユニットを用いずに、1つ又は少数の演算処理装置(CPUなど)を用いて各領域における評価値算出処理を逐次的に実行する。尚、以下で説明しない構成及び処理に関しては、本実施の形態1における図1乃至図5で説明した構成及び処理と基本的に同一である。
【0071】
本実施の形態3にかかる経路探索システムは、例えば、ロボットに搭載されたコンピュータやロボットとは別に設けられたコンピュータにより実現される。このコンピュータは、例えば、中央処理装置(CPU)、ROM、RAM、ハードディスク等の補助記憶装置、CD−ROM等の可搬型記憶媒体が挿入される記憶媒体駆動装置、入力手段や出力手段を備えている。ROM、補助記憶装置、可搬型記憶媒体等の記憶媒体には、オペレーティングシステムと協働してCPU等に命令を与え、アプリケーションプログラムを記録することができる。アプリケーションプログラムはRAMにロードされることによって実行される。このアプリケーションプログラムは、本発明にかかる経路探索システムを実現する特有の経路探索プログラムを含む。経路探索システムによる経路探索は、中央処理装置がアプリケーションプログラムをRAM上に展開した上で当該アプリケーションプログラムに従った処理を補助記憶装置に格納されたデータを読み出し、また格納を行なうことにより、実行される。
【0072】
本実施の形態3にかかる経路探索システムによれば、従来手法と同様に1つ又は少数の演算処理装置(CPUなど)を有するコンピュータに容易に実装することできる。また、1つ又は少数の演算処理装置(CPUなど)を用いて評価値算出処理を実行するため、計算時間は従来手法と変わらないものの、複数の移動終点に対して同時に最短経路を探索することができる。
【0073】
その他の実施の形態.
上述した実施の形態では、指定された移動終点から評価値算出処理を開始して、経路決定処理においては任意の移動始点から経路を決定するものとして説明したが本発明はこれに限定されない。例えば、指定された移動始点から評価値算出処理を開始して、経路決定処理においては任意の移動終点から経路を決定するものとしてもよい。また、本発明によれば移動領域内の指定された2領域間の最短経路を算出することができるため、移動始点及び移動終点として指定する領域数が、多対一、一対多、多対多である場合においても本発明を応用することができる。
また、上述した実施の形態では、移動領域が2次元である場合の例を説明したが、移動領域が例えばx、y、z軸によって規定される3次元空間の場合でもよく、さらに、ロボットの姿勢(1次元)を併せて4次元の探索空間とした場合であっても本発明を適用することができる。
【0074】
さらにまた、上述した実施の形態では、移動手段として車輪などを有するロボットに本発明を適用した一例を示したが、これに限定されず、ロボットは足を有し、自律歩行可能な移動ロボットであってもよい。
【0075】
また、本発明は上述した実施の形態のみに限定されるものではなく、既に述べた本発明の要旨を逸脱しない範囲において種々の変更が可能であることは勿論である。
【図面の簡単な説明】
【0076】
【図1】本発明の実施の形態にかかる経路探索システムの構成を示す構成図である。
【図2】本発明の実施の形態にかかる移動領域を分割した複数の領域を示す概念図である。
【図3】本発明の実施の形態にかかる離散化された領域間の接続関係を説明するための概念図である。
【図4】本発明の実施の形態にかかる評価値算出ユニットの構成を示す概念図である。
【図5】本発明の実施の形態にかかる経路探索システムによる経路探索処理を示すフローチャートである。
【図6】本発明の実施の形態にかかる経路探索システムによる評価値算出処理を説明するための一例を示す図である。
【図7】本発明の実施の形態にかかる経路探索システムによる経路決定処理を説明するための一例を示す図である。
【図8】本発明の実施の形態にかかる経路探索システムによる計算時間短縮効果を説明するためのグラフを示す図である
【図9】本発明の実施の形態にかかる経路探索システムによる評価値算出処理を説明するための一例を示す図である。
【図10】本発明の実施の形態にかかる経路探索システムによる経路決定処理を説明するための一例を示す図である。
【符号の説明】
【0077】
1 経路探索システム、
11 経路探索処理部、12 経路探索記憶部、
111 領域分割部、112 評価値算出ユニット、113 経路決定部、
114 評価値処理部、
32 評価値記憶部、33 評価値記憶部、34 状態設定用信号線、
Cn 領域、G 移動終点、S 移動始点
【技術分野】
【0001】
本発明は移動経路を探索する経路探索システム、経路探索方法、及び自律移動体に関する。
【背景技術】
【0002】
従来より、ロボットや車両などの移動体が、移動始点から移動終点へと到達するための移動経路を探索する技術が提案されている。移動経路探索手法としては、A*(エースター)アルゴリズムやダイキストラ法を用いる手法が良く知られている(例えば特許文献1、2)。
【特許文献1】特開平9−229704号公報
【特許文献2】特開2003−233768号公報
【発明の開示】
【発明が解決しようとする課題】
【0003】
しかしながら、従来の経路探索手法では、1つ又は少数の演算処理装置(CPUなど)によって逐次的に経路探索処理を行うため、経路探索に要する計算コストが高くなるという問題がある。特に、A*アルゴリズムなどの幅優先探索アルゴリズムでは、コストが最小である経路候補を順々に延長してゆくため、探索空間が広くなるにつれて、経路候補数が指数的に急増する。これにより、演算対象となる経路候補数の増大によって、移動経路を算出するための演算量が多くなるため、演算を行うためのメモリ使用量が多くなると共に、移動経路を算出するための演算時間が長くなる。従って、このような従来手法では、探索空間が広い場合には非常に大きな計算コストを要することになり、ロボットへの実装が現実的には困難である。
また、ダイキストラ法などの従来手法は、ある時点における計算について、それ以前の計算結果を利用しているため並列処理が困難であり、一般的には、1つ又は少数の演算処理装置(CPUなど)によって別個独立に最短経路を探索する。このため、複数の移動終点に対して同時に最短経路を探索することができないという問題がある。
【0004】
このように、従来の移動経路探索方法では逐次的に経路探索処理を行うため、経路探索空間が広い場合には、短時間で最適な経路を探索することができないという問題があった。
また、複数の移動終点に対して、同時に最適な経路を探索することができないという問題があった。
【0005】
本発明は、かかる課題を解決するためになされたものであり、経路探索空間が広い場合であっても、最適な経路を高速で探索することができる経路探索システム、経路探索方法、及び自律移動体を提供することを第一の目的とする。
【0006】
また、本発明は、複数の移動終点に対して、同時に最適な経路を探索することができる経路探索システム、経路探索方法、及び自律移動体を提供することを第二の目的とする。
【課題を解決するための手段】
【0007】
本発明にかかる経路探索システムは、移動領域内に存在する移動始点より移動を開始し、前記移動領域内に存在する移動終点に到達する自律移動体の移動経路を探索する経路探索システムであって、前記移動領域を複数の領域に分割する領域分割部と、前記領域分割部により分割された複数の領域に対応し、それぞれの領域の評価値を算出する複数の評価値算出部と、前記評価値算出部によって算出された評価値に基づいて経路を決定する経路決定部とを備え、前記評価値算出部が、近傍に存在する領域の評価値と、当該近傍領域から自領域までの移動コストに基づいて評価値を算出する評価値処理部を有するものである。
【0008】
これにより、移動領域を複数の領域に分割することで、経路探索のための移動コストを領域間の幾何学的な距離によって表現することができる。そして、複数の評価値算出部が、このような幾何学的な距離と近傍領域の評価値とに基づいて、それぞれの領域における評価値算出処理を並列に実行することで、逐次的に各領域の評価値を算出する場合に比べて、経路探索に要する計算コストを大きく削減することができる。従って、経路探索空間が広い場合であっても、最適な経路を高速で探索することができる。
【0009】
さらに、移動終点として複数の領域を指定する場合においても、複数の移動終点から評価値算出処理がそれぞれ開始されて、それぞれの処理が並列に実行されながらその近傍領域へと伝わっていく。このため、移動終点でない他の領域を注目する領域としたとき、その注目する領域に最初に伝わった処理は、複数の移動終点のうちでそれぞれの移動終点からその近傍領域を介して最初にその注目する領域へと処理を伝えることができた移動終点から開始された処理となる。即ち、評価値算出処理の実行後に、各領域において算出される評価値は、複数の移動終点のうちで最も早く評価値算出処理を各領域に対して伝えることが可能な移動終点であって、その移動終点からの移動コストに基づいた評価値となる。従って、このような評価値によれば、複数の移動終点に対して同時に最適な経路を探索することができる。
【0010】
また、評価値算出部は、近傍領域の評価値のうち最も小さい評価値と、その近傍領域から自領域までの幾何学的な距離に応じた移動コストに基づいて評価値を算出してもよい。このように、近傍領域における最小の評価値と、その近傍領域から自領域までの幾何学的な距離に応じた移動コストに基づいて評価値を算出することで、容易に評価値を算出することができる。
【0011】
さらにまた、前記評価値算出部は、前記評価値処理部による評価値算出結果を格納する第一の評価値記憶部及び第二の評価値記憶部を更に備え、前記評価値処理部が、第一の評価値記憶部に格納された自領域の評価値、及び近傍に存在する領域の評価値に基づいて評価値算出処理を実行するか否かを判定し、判定の結果、評価値算出処理を実行する場合には、当該近傍領域の評価値と、当該近傍領域から自領域までの移動コストに基づいて自領域の評価値を算出し、当該評価値算出結果を第二の評価値記憶部に出力するようにしてもよい。このように、全ての評価値算出部において、評価値算出処理を実行するか否かを、それぞれ第一の評価値記憶部に格納された評価値に基づいて判定し、評価値算出結果を、それぞれ第一の評価値記憶部とは異なる第二の評価値記憶部に出力する。これにより、1回の評価値算出処理の結果、評価値算出結果の干渉を防ぐことができると共に、1近傍を越えて評価値が算出されないよう制限することができるため、1近傍領域に含まれる領域の評価値のみを算出させることができる。従って、複数の評価値算出部による評価値算出処理のタイミングを同期させることができる。
【0012】
また、前記経路決定部は、前記移動始点に対応する領域から前記移動終点に対応する領域に向けて、算出された評価値のうち最も小さい評価値を有する近傍領域を選択してゆくようにしてもよい。このように、移動始点に対応する領域から移動終点に対応する領域に向けて、算出された評価値のうち最小の評価値を有する近傍領域を選択してゆくことで、簡単に経路を決定することができる。
【0013】
さらにまた、前記領域分割部により分割された前記領域について、自領域に対して隣接した領域を越えた領域を近傍領域として設定可能としてもよい。これにより、注目する領域に直接隣接していない領域についても近傍領域に含めることで、それら領域間を通過する経路を作成することができる。従って、移動始点から移動終点へと至る経路の角度分解能を柔軟に設定することができ、より滑らかな経路を作成することができる。
【0014】
また、前記経路探索システムは、前記評価値算出部による評価値算出処理を実行可能又は不能に設定する状態設定部を更に備えるようにしてもよい。これにより、所望の評価値算出部について、評価値算出処理を行うタイミングを調整することができる。例えば、環境に応じて、特定の評価値算出部の評価値算出処理を一定期間実行不能に設定することで、それら評価値算出部は待ち状態となり、対応する領域には評価値が算出されない。一定期間経過後に評価値算出処理が実行可能となった場合に、それら待ち状態を経た評価値算出部によって算出される評価値は、既に算出された他の領域の評価値に比べて、待ち時間の分だけ相対的に大きな評価値が算出される。即ち、評価値算出処理において、待ち時間を評価値に反映させることで、特定の領域の評価値を大きくすることができる。従って、評価値の高い領域は経路として選択されにくくなるため、特定の領域を避けるように柔軟に経路を作成することができる。
【0015】
また、本発明にかかる経路探索システムは、移動領域内に存在する移動始点より移動を開始し、前記移動領域内に存在する移動終点に到達する自律移動体の移動経路を探索する経路探索システムであって、前記移動領域を複数の領域に分割する領域分割部と、前記領域分割部により分割された複数の領域に対応し、近傍に存在する領域の評価値のうち最も小さい評価値と、当該近傍領域から自領域までの幾何学的な距離に応じた移動コストに基づいて、それぞれの領域における評価値算出処理を並列に実行する評価値算出部と、前記評価値算出部によって算出された評価値に基づいて経路を決定する経路決定部とを備え、前記移動領域内に複数の移動終点が存在する場合には、前記評価値算出部は当該移動終点を含む領域のそれぞれから評価値算出処理を開始し、前記経路決定部は当該評価値算出処理結果に基づいて任意の移動始点より経路決定処理を開始するものである。
【0016】
これにより、移動終点として複数の領域を指定する場合においても、評価値算出部が、それぞれ並列に評価値算出処理を実行すると共に、近傍領域における評価値の最小値及び自領域までの移動コストに基づいて評価値算出処理を実行する。このため、各領域における評価値は、複数の移動終点からの移動コストの総和が最小となる評価値が算出され、最も移動コストの少ない移動終点までの経路を探索することができる。従って、このような評価値によれば、複数の移動終点に対して同時に最適な経路を探索することができる。
【0017】
本発明にかかる経路探索方法は、移動領域内に存在する移動始点より移動を開始し、前記移動領域内に存在する移動終点に到達する自律移動体の移動経路を探索する経路探索方法であって、前記移動領域を複数の領域に分割する領域分割ステップと、前記領域分割部により分割された複数の領域における評価値算出処理を並列に実行する評価値算出ステップと、前記評価値算出ステップによって算出された評価値に基づいて経路を決定する経路決定ステップとを備え、前記評価値算出ステップでは、近傍に存在する領域の評価値と、当該近傍領域から自領域までの移動コストに基づいて評価値を算出するものである。
【0018】
これにより、移動領域を複数の領域に分割することで、経路探索のための移動コストを領域間の幾何学的な距離によって表現することができる。そして、複数の評価値算出ステップが、このような幾何学的な距離と近傍領域の評価値とに基づいて、それぞれの領域における評価値算出処理を並列に実行することで、逐次的に各領域の評価値を算出する場合に比べて、経路探索に要する計算コストを大きく削減することができる。従って、経路探索空間が広い場合であっても、最適な経路を高速で探索することができる。
【0019】
さらに、移動終点として複数の領域を指定する場合においても、評価値算出処理は複数の移動終点から開始され、それぞれ並列に実行されながらその近傍領域へと処理が伝わっていく。このため、移動終点を含まない他の領域において、最も早くその領域に伝わった処理は、その処理を最初に開始した移動終点から開始された処理によるものとなる。即ち、評価値算出処理の実行後に、各領域において算出される評価値は、複数の移動終点のうち、各領域に対して最も早く評価値算出処理を伝えることが可能な移動終点であって、その移動終点からの移動コストに基づいた評価値となる。従って、このような評価値によれば、複数の移動終点に対して同時に最適な経路を探索することができる。
【0020】
また、前記評価値算出ステップでは、近傍領域の評価値のうち最も小さい評価値と、当該近傍領域から自領域までの幾何学的な距離に応じた移動コストに基づいて評価値を算出するようにしてもよい。このように、近傍領域における最小の評価値と、その近傍領域から自領域までの幾何学的な距離に応じた移動コストに基づいて評価値を算出することで、容易に評価値を算出することができる。
【0021】
さらにまた、前記経路決定ステップでは、前記移動始点に対応する領域から前記移動終点に対応する領域に向けて、算出された評価値のうち最も小さい評価値を有する近傍領域を選択してゆくようにしてもよい。このように、移動始点に対応する領域から移動終点に対応する領域に向けて、算出された評価値のうち最小の評価値を有する近傍領域を選択してゆくことで、簡単に経路を決定することができる。
【0022】
また、前記領域分割ステップにより分割された前記領域について、自領域に対して隣接した領域を越えた領域を近傍領域として設定可能としてもよい。これにより、注目する領域に直接隣接していない領域についても近傍領域に含めることで、それら領域間を通過する経路を作成することができる。従って、移動始点から移動終点へと至る経路の角度分解能を柔軟に設定することができ、より滑らかな経路を作成することができる。
【0023】
さらにまた、前記経路探索方法は、前記評価値算出ステップによる評価値算出処理を実行可能又は不能に設定する状態設定ステップを更に備えるようにしてもよい。これにより、所望の領域について、評価値算出処理を行うタイミングを調整することができる。例えば、環境に応じて、特定の領域の評価値算出処理を一定期間実行不能に設定することで、それら評価値算出ステップは待ち状態となり、対応する領域には評価値が算出されない。一定期間経過後に評価値算出処理が実行可能となった場合に、それら待ち状態を経た評価値算出ステップによって算出される評価値は、既に算出された他の領域の評価値に比べて、待ち時間の分だけ相対的に大きな評価値が算出される。即ち、評価値算出処理において、待ち時間を評価値に反映させることで、特定の領域の評価値を大きくすることができる。従って、評価値の高い領域は経路として選択されにくくなるため、特定の領域を避けるように柔軟に経路を作成することができる。
【0024】
本発明にかかる経路探索プログラムは、移動領域内に存在する移動始点より移動を開始し、前記移動領域内に存在する移動終点に到達する自律移動体の移動経路を探索する経路探索プログラムであって、コンピュータに対して、前記移動領域を複数の領域に分割する領域分割ステップと、前記領域分割部により分割された複数の領域に対応し、近傍に存在する領域の評価値と、当該近傍領域から自領域までの移動コストに基づいて、それぞれの領域における評価値算出処理を並列に実行する評価値算出ステップと、前記評価値算出ステップによって算出された評価値に基づいて経路を決定する経路決定ステップとを実行させるものである。
【0025】
これにより、移動領域を複数の領域に分割することで、経路探索のための移動コストを領域間の幾何学的な距離によって表現することができる。そして、評価値算出ステップが、このような幾何学的な距離と近傍領域の評価値とに基づいて、それぞれの領域における評価値算出処理を並列に実行することで、逐次的に各領域の評価値を算出する場合に比べて、経路探索に要する計算コストを大きく削減することができる。従って、経路探索空間が広い場合であっても、最適な経路を高速で探索することができる。
【0026】
さらに、移動終点として複数の領域を指定する場合においても、評価値算出処理は複数の移動終点から開始され、それぞれ並列に実行されながらその近傍領域へと処理が伝わっていく。このため、移動終点を含まない他の領域において、最も早くその領域に伝わった処理は、その処理を最初に開始した移動終点から開始された処理によるものとなる。即ち、評価値算出処理の実行後に、各領域において算出される評価値は、複数の移動終点のうち、各領域に対して最も早く評価値算出処理を伝えることが可能な移動終点であって、その移動終点からの移動コストに基づいた評価値となる。従って、このような評価値によれば、複数の移動終点に対して同時に最適な経路を探索することができる。
【0027】
本発明にかかる自律移動体は、移動領域内に存在する移動始点より移動を開始し、前記移動領域内に存在する移動終点に到達する移動経路を探索可能な自律移動体であって、前記移動領域を複数の領域に分割する領域分割部と、前記領域分割部により分割された複数の領域に対応し、それぞれの領域の評価値を算出する複数の評価値算出部と、前記評価値算出部によって算出された評価値に基づいて経路を決定する経路決定部とを備え、前記評価値算出部が、近傍に存在する領域の評価値と、当該近傍領域から自領域までの移動コストに基づいて評価値を算出する評価値処理部を有するものである。
【0028】
これにより、移動領域を複数の領域に分割することで、経路探索のための移動コストを領域間の幾何学的な距離によって表現することができる。そして、複数の評価値算出部が、このような幾何学的な距離と近傍領域の評価値とに基づいて、それぞれの領域における評価値算出処理を並列に実行することで、逐次的に各領域の評価値を算出する場合に比べて、経路探索に要する計算コストを大きく削減することができる。従って、経路探索空間が広い場合であっても、最適な経路を高速で探索することができる。
【0029】
さらに、移動終点として複数の領域を指定する場合においても、評価値算出処理は複数の移動終点から開始され、それぞれ並列に実行されながらその近傍領域へと処理が伝わっていく。このため、移動終点を含まない他の領域において、最も早くその領域に伝わった処理は、その処理を最初に開始した移動終点から開始された処理によるものとなる。即ち、評価値算出処理の実行後に、各領域において算出される評価値は、複数の移動終点のうち、各領域に対して最も早く評価値算出処理を伝えることが可能な移動終点であって、その移動終点からの移動コストに基づいた評価値となる。従って、このような評価値によれば、複数の移動終点に対して同時に最適な経路を探索することができる。
【発明の効果】
【0030】
本発明によれば、経路探索空間が広い場合であっても、最適な経路を高速で探索することができる経路探索システム、経路探索方法、及び自律移動体を提供することを第一の目的とする。
【0031】
また、本発明によれば、複数の移動終点に対して、同時に最適な経路を探索することができる経路探索システム、経路探索方法、及び自律移動体を提供することを第二の目的とする。
【発明を実施するための最良の形態】
【0032】
以下、本発明を適用した具体的な実施の形態について、図面を参照しながら詳細に説明する。尚、各図面において、同一要素には同一の符号を付しており、説明の明確化のため、必要に応じて重複説明を省略する。
【0033】
発明の実施の形態1.
本発明の実施の形態1にかかる経路探索システムでは、自律移動体としてロボットを用いている。ロボットは、例えば、それぞれ独立して回転制御される二つの車輪を備えたものでもよく、2輪よりも多い、例えば4輪走行のロボットや、1輪走行のロボット、2足歩行・4足歩行のロボットであってもよい。また、ロボットに限らず、2輪走行や4輪走行の車両にも適用できる。本例におけるロボットは、障害物を検出するセンサやカメラを備え、検出された障害物に応じて、これを避けるように経路探索を行なう。
【0034】
当該経路探索システムは、移動領域を複数の格子状の領域に分割し、分割された複数の領域に対応する評価値算出部を備える。各評価値算出部は、独立した評価値処理部及び評価値記憶部を備え、各評価値算出部に対応するそれぞれの領域の評価値を算出し、その結果を格納する。評価値算出処理は、近傍に存在する領域の評価値と、その近傍領域から自領域までの移動コストに基づいて実行される。そして、経路探索システムは、各評価値算出部によって算出された評価値に基づいて経路決定処理を実行する。
【0035】
また、本実施の形態1にかかる経路探索システムは、経路探索問題を、離散化された移動領域において、その移動領域を伝播する仮想的なコストポテンシャル波の伝播履歴を求める問題と置き換えて解くものである。移動領域を構成する評価値算出部間の相互作用を利用することで、最短経路を高速に探索することができる。後述するように、移動領域の次元数をpとすると、従来手法ではO(np)の計算時間が必要であったが、本実施の形態1にかかる経路探索システムでは、O(n√p)の計算時間で最短経路を得ることができる。
【0036】
図1は、本実施の形態1にかかる経路探索システムの概略構成を示すブロック図である。図1に示されるように、経路探索システム1は、経路探索処理部11と経路探索記憶部12により構成されている。経路探索処理部11は、領域分割部111、複数の評価値算出ユニット112、及び経路決定部113を備えている。評価値算出部としての評価値算出ユニット112は、物理的に独立した評価値算出ユニットであって、評価値算出処理を並列に実行する。
【0037】
経路探索記憶部12には、ロボットが移動する移動領域全体の形状に、略一定間隔d(例えば10cm)に配置された格子点を結ぶグリッド線を仮想的に描写することで得られるグリッドマップが記憶されている。ロボットは、GPS等から得られた位置情報を、このグリッドマップ上における自己の位置に置き換えて、グリッドマップ上における自己位置を認識する。グリッドマップ上において、ロボットの自己位置に相当する場所、および目的地である移動終点、および移動終点におけるロボットの移動方向が特定される。ロボットは、グリッドマップ上において特定された自己位置を移動始点から、目的地である移動終点までの移動経路を作成し、作成された移動経路に従って移動を行う。
【0038】
領域分割部111は、ロボットが移動する移動領域を格子状の領域に分割する。ここでは、上述の略一定間隔d(例えば10cm)に配置された格子点を囲む複数の領域に分割する。図2は、移動領域を分割して、離散化された複数の領域Cnを示す概念図である。尚、領域分割部111による分割方法はこれに限定されない。例えば、上述の分割後の領域よりも大きな領域へと分割することで、経路探索に要する時間をより短縮することができる。また、グリッドマップが格子状に並んだノードと、各ノードを接続するリンクを備える場合には、分割された領域は、グリッドマップ上に配置されたノードに対応するものとして扱ってもよい(この場合には、近傍領域はリンクによって規定される)。即ち、各領域は各ノードを示し、各ノードに対する評価値を算出し、それらノードに付与された評価値に基づいて、経路を選択するようにしてもよい。
【0039】
領域分割部111により分割された領域間の接続関係が定められ、注目する領域に接続する領域を近傍領域とする。図3は、離散化された領域間の接続関係を説明するための概念図である。図3(a)では、注目する領域C0に対して、隣接領域C1乃至C8を近傍領域として定めるものである。また、図3(b)では、注目する領域C0に対して、隣接領域C1乃至C8に加えて、さらに領域C9乃至C16を近傍領域として定めるものである。このように、自領域に対して隣接した領域を越えた領域を近傍領域として設定可能とすることで、自領域及びそれら近傍領域間を通過する経路を作成することができる。このようにすれば、移動始点から移動終点へと至る経路の角度分解能を柔軟に設定することができ、より滑らかな経路を作成することができる。
【0040】
評価値算出ユニット112は、領域分割部111により分割された領域に対応し、それぞれの領域の評価値を算出する評価値処理部114を有する。図4は、評価値算出ユニット112の構成を示す概念図である。図4(a)に示すように、評価値算出ユニット112は、評価値処理部114と、第一の評価値記憶部及び第二の評価値記憶部としての、少なくとも2つの評価値記憶部32及び33を備える。評価値算出ユニット112には、状態設定部としての状態設定用信号線34が接続されている。
【0041】
尚、評価値算出ユニット112はいずれも同一の構成を有しており、簡易な構成により経路探索システム1を構成することができる。各評価値算出ユニット112は、分割された各領域に一対一で対応付けてもよいし、一つの評価値算出ユニット112が、複数の分割された領域に対応するようにしてもよい。また、評価値算出ユニット112は、例えばFPGA(Field Programmable Gate Array)等のプログラム可能な装置を用いることによって容易に構成することができる。そして、図4(b)に示すように、複数の評価値算出ユニット112Unが配列され、それぞれが分割された複数の領域に対応する。このような配列構造によれば、ロボットなどに対しても容易に実装化することができる。
【0042】
状態設定用信号線34は、評価値処理部114による評価値算出処理を実行可能状態又は実行不能状態に設定するための状態設定信号を評価値処理部114へと送信する。これにより、所望の評価値算出ユニット112について、評価値算出処理を行うタイミングを調整することができる。即ち、評価値算出処理を実行させる場合には、評価値算出ユニット112へと評価値算出処理を実行可能とする状態設定信号を送信し、評価値算出処理を実行させない場合には、評価値算出処理を実行不能とする状態設定信号を送信する。
【0043】
評価値算出ユニット112が評価値算出処理を実行可能とする状態設定信号を受信した場合には、評価値処理部114は、近傍領域の評価値のうち最も小さい評価値と、その近傍領域から自領域までの幾何学的な距離に応じた移動コストに基づいて評価値を算出し、その結果を評価値記憶部32及び33に格納する。尚、評価値算出処理の詳細については後述する。
【0044】
一方、評価値算出ユニット112が評価値算出処理を実行不能とする状態設定信号を受信した場合には、評価値処理部114は評価値算出処理を実行しない。例えば、環境に応じて、特定の評価値算出ユニット112の評価値算出処理を一定期間実行不能に設定することで、それら評価値算出ユニット112を待ち状態として、対応する領域における評価値を算出させないようにすることができる。一定期間経過後に評価値算出処理が実行可能となった場合に、それら待ち状態を経た評価値算出ユニット112によって算出される評価値は、既に算出された他の領域の評価値に比べて、待ち時間の分だけ相対的に大きな評価値が算出される。即ち、評価値算出処理において、待ち時間を評価値に反映させることで、特定の領域の評価値を大きくすることができる。従って、後述するように、評価値の大きな領域は経路として選択されにくくなるため、特定の領域を避けるように柔軟に経路を作成することができる。尚、状態設定用信号線34は、評価値記憶部32及び33に格納された評価値算出結果を初期化するための初期化信号を送信するようにしてもよい。
【0045】
経路決定部113は、評価値算出ユニット112によって算出された評価値に基づいて採用する経路を決定する。より詳細には、移動始点に対応する領域から移動終点に対応する領域に向けて、算出された評価値のうち最も小さい評価値を有する近傍領域を選択してゆく。選択された領域を通過する経路が、移動始点から移動終点へと至る最短経路となる。
【0046】
続いて、本実施の形態1にかかる経路探索システム1の具体的な処理について、図5に示すフローチャート、及び図6、7に示すグリッドマップを用いて説明する。ここで、図6及び7に示すグリッドマップは、ロボットの目標軌道となる目標経路を、グリッド状に離散化された領域の集合として表現するものである。グリッド座標を利用するメリットは、最短経路探索を容易に実行できる点や、確実に目的地に到達できる経路を得ることができる点にある。グリッドマップに関する情報は、経路探索システム1を構成するコンピュータの経路探索記憶部12に格納される。ここで、グリッドマップに関する情報には、各領域の座標情報、各領域の近傍領域を示す領域間の接続情報、及び各領域に関連付けられた評価値情報が含まれる。領域の評価値は、それぞれの領域に対応する評価値算出ユニット112によって算出される。
【0047】
まず、領域分割部111により、移動領域が複数の領域に分割され、分割されたそれぞれの領域に対して評価値算出ユニット112が対応付けられる(S101)。ここでは、移動領域は、グリッド数と等しい数の領域に分割される。例えば、移動領域が2次元平面である場合には、それぞれ10cm×10cmの広さを持つ離散的な複数の領域が分割生成される。分割された各領域に対して、それぞれの領域の評価値を算出する評価値算出ユニット112が対応付けられる。
【0048】
次に、全ての評価値算出ユニット112に対して初期値を代入する(S102)。各領域の状態として、進入が禁止される禁止状態、評価値が未計算である未計算状態、及び評価値を計算済みである計算済み状態からなる3状態を想定する。それぞれの状態に対応する初期値を評価値算出ユニット112に代入する。評価値算出処理の開始段階であるS102においては、経路探索対象となる領域のうち、進入禁止領域以外の領域に対応する評価値算出ユニット112の評価値記憶部32及び33には、初期値として十分大きな値(例えば1.0×10^7)を代入する。進入禁止領域に対応する評価値算出ユニット112の評価値記憶部32及び33には、初期値として十分大きな値(例えば1.0×10^9)を代入する。ここでは、初期値として、後述する評価値算出処理によって算出される評価値を十分上回る値を採用して代入する。尚、領域の状態をこのような初期値を設定することで判断してもよいし、領域の状態を示す状態情報を各評価値算出ユニット112に格納するようにしてもよい。
【0049】
次に、移動終点を指定して、その移動終点を含む領域に対応する評価値算出ユニット112について、その評価値記憶部32又は評価値記憶部33の少なくとも一方に評価値の最小値(例えば0)を代入する(S103)。以下では、評価値記憶部32のみに評価値の最小値が代入されたものとして説明する。
【0050】
次に、評価値算出処理を開始するための計算開始クロックC1を発生する(S104)。状態設定用信号線34を介して、CPUのクロックに相当するパルスが各評価値算出ユニット112へと送信され、各評価値算出ユニット112においてS105乃至108における処理が実行される。またこのとき、評価値算出処理を実行させる評価値算出ユニット112に対しては、評価値算出処理を実行可能とする状態設定信号が送信され、評価値算出処理を実行させない評価値算出ユニット112に対しては、評価値算出処理を実行不能とする状態設定信号が送信される。
【0051】
各評価値算出ユニット112は、対応する自領域の評価値及び近傍領域の評価値に基づいて、以下のようにして自領域の評価値を更新してゆく。まず、評価値記憶部32に格納されている値について、自領域の評価値である自己評価値が、初期値から更新されているか否かを判定する(S105)。
【0052】
ステップS105における判定の結果、自己評価値が初期値のままである場合(自領域の評価値が未計算である場合)には、近傍領域に対応する評価値算出ユニット112において、その評価値記憶部32に格納されている値として、初期値ではない評価値が存在しているか否かを判定する(S106)。
【0053】
ステップS106における判定の結果、近傍領域に初期値以外の値が存在する場合(近傍領域の評価値が計算済みである場合)には、近傍領域の評価値のうち最も小さい評価値と、その最小の評価値を持つ近傍領域から自領域までの幾何学的な距離に応じた移動コストに基づいて自己の領域の評価値を算出し、その結果を評価値記憶部33に格納する(S107)。ここでは、以下の式に基づいて自己の領域の評価値を算出する。
自己評価値=近傍領域の最小評価値+近傍領域から自領域までの移動コスト
【0054】
一方、ステップS105又はS106における判定の結果、評価値記憶部32に格納されている自己評価値が初期値から更新されている場合、又は近傍領域に初期値以外の値が存在しない場合には、現在の自己評価値を更新せずにそのまま維持する(S108)。ここでは、自己評価値を維持する処理として、評価値記憶部32に格納されている評価値を評価値記憶部33へと出力して格納する。このように処理することで、現在の自己評価値を簡易な処理によって維持することができる。尚、評価値記憶部32に格納されている評価値を評価値記憶部33へと出力せずに、何も処理を実行しないようにしてもよい。
【0055】
このように、全ての評価値算出ユニット112において、ステップS105乃至108における評価値算出処理の実行を、それぞれ評価値記憶部32に格納された評価値に基づいて判定し、評価値算出結果を、それぞれ評価値記憶部32とは異なる評価値記憶部33に出力する。これにより、1回の評価値算出処理の結果、評価値算出結果の干渉を防ぐことができると共に、1近傍を越えて評価値が算出されないよう制限することができるため、1近傍領域に含まれる領域の評価値のみを算出させることができる。従って、複数の評価値算出ユニット112による評価値算出処理のタイミングを同期させることができる。尚、次のクロックC2によってステップS105乃至108における処理が実行される場合には、ステップS105乃至S108の処理において、評価値記憶部33に格納されている評価値に基づいて評価値算出処理が実行され、その結果が評価値記憶部32に格納される。更には、クロックC3によってS105乃至108における処理が実行される場合には、評価値記憶部32に格納されている評価値に基づいて評価値算出処理が実行され、その結果が評価値記憶部33に格納される。
【0056】
移動始点を含む領域に対応する評価値算出ユニット112について、その評価値記憶部32又は評価値記憶部33のいずれか一方に初期値ではない評価値が存在しているか否かを判定する(S109)。ステップS109における判定の結果、評価値が存在していない場合には、移動始点を含む領域の評価値は未だに算出されていない未計算状態であるため、ステップS104へと戻り再び各評価値算出ユニット112により領域の評価値算出処理を実行する。
【0057】
一方、ステップS109における判定の結果、移動始点に評価値が存在している場合には、移動始点を含む領域の評価値が計算済みの状態となったことから、評価値算出処理を終了して、ステップS110以降の経路決定処理へと進む。
【0058】
尚、ステップS109における評価値算出処理を終了させる条件としては、全ての領域に対応する評価値が変化しなくなった場合に処理を終了させるようにしてもよい。即ち、全ての評価値算出ユニット112において、評価値記憶部32及び33に格納された評価値が同じ値のまま変化しなくなった場合に処理を終了させることができる。また、このような終了条件をステップS109における終了条件に加えて判定させるように構成することで、移動始点から移動終点までの経路が存在しない場合であっても評価値算出処理を終了させることができる。
【0059】
続いて、評価値算出処理を終了した後、経路決定部113は、分割された各領域の評価値に基づいて、移動始点を含む領域から開始し、その近傍領域において最小の評価値を持つ領域を経路として選択する(S110)。そして、ステップS110において選択した領域が、移動終点を含む領域であるか否かを判定する(S111)。ステップS111における判定の結果、選択された領域が移動終点を含む領域に到達していない場合には、ステップS110へと戻り、次の経路として選択した領域の近傍領域を選択する。一方、ステップS111における判定の結果、選択された領域が移動終点を含む領域に到達した場合には、ステップS110において選択された領域の系列を経路として出力し、経路決定処理を終了する(S111)。このように、移動始点に対応する領域から移動終点に対応する領域に向けて、領域の評価値のうち最も小さい評価値を有する近傍領域を順次選択してゆくことで、選択された領域を通過する経路を最短経路として決定することができる。
【0060】
図6は、評価値算出処理を説明するための一例を示す図である。図6では、移動領域を横16個、縦13個の領域に分割し、各領域の近傍領域を各領域に隣接した前後左右4方向に隣接する領域とした。図において斜線領域は進入禁止領域を示し、外周上の領域は経路探索対象外である領域を示す。図に示す領域Gを移動終点とし、領域Gの初期値を0に設定した場合に、評価値算出ユニット112による評価値算出結果を各領域に示す。尚、ここでは、近傍領域から自領域までの移動コストの値を5とした。分割された208個の領域のうち、39個の領域が進入禁止領域であり、169個の領域が経路探索対象領域である。従来手法では、領域の個数相当の計算ステップが必要となるため、計169回の計算が必要となる。一方、本実施の形態1にかかる経路探索システム1によれば、各評価値算出ユニット112がそれぞれ並列に評価値を算出するため、計22回の計算によって評価値を算出することができる。従って、従来手法と比較して、凡そ8分の1の計算時間によって経路探索のための評価値算出処理を実行することができ、移動領域が広くなる程、計算時間短縮による効果は顕著なものとなる。
【0061】
図7は、経路決定処理を説明するための一例を示す図である。図7では、図6に示した評価値算出後の領域について、図に示す領域Sを移動始点とし、移動始点Sから移動終点Gまでの経路決定処理の結果を示している。移動始点Sから移動終点Gへと向かって選択された領域の系列について、それら領域を通過する白抜き矢印が移動始点Sから移動終点Gまでの最短経路を示している(同時に、移動終点Gから移動始点Sまでの最短経路を意味する)。また、移動始点Sにおける評価値110は、移動始点Sから移動終点Gまでに要する移動コストの総コストを意味している。
【0062】
以上に説明したように、本実施の形態1にかかる経路探索システム1は、移動領域を複数の領域に分割することで、経路探索のための移動コストを領域間の幾何学的な距離によって表現することができる。そして、複数の評価値算出ユニット112が、このような幾何学的な距離と近傍領域の評価値とに基づいて、それぞれの領域における評価値算出処理を並列に実行することで、逐次的に各領域の評価値を算出する場合に比べて、経路探索に要する計算コストを大きく削減することができる。
【0063】
図8は、本実施の形態1にかかる経路探索システム1(発明手法)による計算時間短縮効果を説明するためのグラフを示す図である。図では、一辺L個のグリッドからなるn次元正立方体探索空間において、その対角要素間の経路(最長経路)を探索するために必要な計算ステップの見積もり(最大の計算ステップ数)を示す。L=正立方体の一辺のグリッド数[grid]、n=探索空間の次元数[1]とした場合に、経路探索に要する計算の繰り返し回数(steps)は以下の式に基づいて見積もることができる。
従来手法:steps=Ln
発明手法:steps=L×√n
例えば、一辺が20[grid]の7次元正立方体探索空間内において最短経路探索を行った場合、従来の経路探索手法と、本実施の形態1にかかる経路探索システム1による計算ステップとを比較すると、経路探索システム1は、従来手法に対しておよそ1億分の1のステップ数によって経路探索を実行することができる。
【0064】
また、本実施の形態1にかかる経路探索システム1では、近傍とする領域を変更することで、評価値を算出するタイミングを環境に応じて調整することができる。例えば、接続関係をより広範囲の領域間に広げ、遠方に存在する領域を近傍領域とすることで、遠方の領域に基づいて自領域の評価値を算出することができる。即ち、接続関係を有する遠方の領域における評価値が算出された場合には、次のタイミングにおいて自領域の評価値を算出することができるため、直接隣接する領域を近傍領域とした場合と比べて、評価値算出処理をより早くに実行させることができる。従って、経路探索処理をより短時間で実行させることができるため、環境において動的な障害物が存在する場合であっても効果的に障害物に対処することが可能となる。
【0065】
発明の実施の形態2.
本実施の形態2にかかる経路探索システムは、移動領域内に複数の移動終点を指定した場合には、当該移動終点を含む領域のそれぞれから評価値算出処理を開始し、当該評価値算出処理結果に基づいて任意の移動始点より経路を探索する。評価値算出部は、いずれかの移動始点を含む領域において評価値が算出された場合に、評価値算出処理を終了させることができる。経路決定部は、移動領域内の任意の領域を移動始点として指定し、算出された領域の評価値に基づいて、移動始点に対応する領域から、算出された評価値のうち最も小さい評価値を有する近傍領域を選択してゆく。このとき、複数の移動終点に対応する領域のうち、当該移動始点から最短の移動コストで到達可能な移動終点に向けて経路を決定することができる。尚、以下で説明しない構成及び処理に関しては、本実施の形態1における図1乃至図5で説明した構成及び処理と基本的に同一である。
【0066】
図9は、複数の移動終点が指定された場合に、評価値算出処理を説明するための一例を示す図である。図9では、移動領域を横16個、縦13個の領域に分割し、近傍領域は各領域の前後左右方向に直接隣接する領域とした。図において斜線領域は進入禁止領域を示し、外周上の領域は経路探索対象外である探索領域外を示す。図に示す領域G1及びG2を移動終点とし、領域G1及びG2の初期値を0に設定した場合に、評価値算出ユニット112による評価値算出結果を各領域に示す。尚、ここでは近傍領域から自領域までの移動コストの値は5とした。また、複数の移動終点は上述した図5のステップS103において、複数の移動終点を含む領域に対応する評価値算出ユニット112について、その評価値記憶部32又は評価値記憶部33の少なくとも一方に評価値の最小値(例えば0)を代入すればよい。
【0067】
図10は、複数の移動終点が指定された場合に、経路決定処理を説明するための一例を示す図である。図10では、図9に示した評価値算出後の領域について、図に示す領域S1を移動始点とし、移動始点S1から経路決定処理を実行した。その結果、決定された経路は、移動始点S1から移動終点G1へと到達する経路であった。また、移動始点S1における評価値60は、移動始点S1から移動終点G1までに要する移動コストの総コストを意味している。これにより、移動終点G2に比べて、移動終点G1へと到達する経路長のほうがより短いものであり、移動始点S1からは、移動終点G1へと移動するほうがより少ない移動コストで済むことを示している。
【0068】
このように、複数の領域について、評価値算出ユニット112が、それぞれ並列に評価値算出処理を実行すると共に、近傍領域における評価値の最小値及び自領域までの移動コストに基づいて評価値算出処理を実行する。このため、各領域における評価値は、複数の移動終点からの移動コストの総和が最小となる評価値が算出され、最も移動コストの少ない移動終点までの経路を探索することができる。従って、このような評価値によれば、複数の移動終点に対して同時に最適な経路を探索することができる。例えば、移動領域内に複数のゴミ箱が存在し、それらゴミ箱を含む領域を移動終点とした場合、ロボットは現在位置である移動始点から、移動コストが最小となる移動終点を選択し、その移動終点へと到達する最短経路を移動することが好ましい。また、マニピュレータによる軌道計画を行う場合には、対象物を把持する際に最も把持しやすい位置・姿勢へと至るマニュピレータの軌道を計画することが好ましい。そのため、現在の位置・姿勢から、目標となる位置・姿勢へと到達する最適な軌道計画が必要となるが、そのような目標位置・姿勢は複数存在するものと考えられる。従って、このような場合においても本実施の形態2にかかる経路探索システムを適用することによって、複数の移動終点に対して、同時に最適な移動経路及び軌道を作成することができる。
【0069】
また、本実施の形態2にかかる経路探索システムによれば、複数の移動終点に対して同時に最適な経路を探索することができるため、複数の領域からなる領域範囲を、移動終点エリアとして指定することもできる。これにより、ひとつの領域のみを正確に移動終点として指定する必要がなく、移動終点として指定したい凡その範囲を指定するだけで経路を探索することができ、環境に応じてより柔軟に経路探索を実行させることができる。尚、複数の移動終点に対して、従来手法を用いてそれぞれの移動終点への経路を探索した場合には、算出される最短経路は同じ経路長となるものの、従来手法ではそれぞれの移動終点に対して別々に経路を探索するため、移動終点の個数に応じた計算時間を要する。一方、本実施の形態2にかかる経路探索システムによれば、それぞれの評価値算出ユニット112が並列に評価値を算出してゆくため、移動終点の個数に応じて計算時間が増加することはなく、移動終点の個数が増加した場合であっても、従来手法と比較してより高速に経路探索処理を実行することができる。
【0070】
発明の実施の形態3.
本実施の形態3にかかる経路探索システムは、移動領域内に存在する移動始点より移動を開始し、移動領域内に存在する移動終点に到達する自律移動体の移動経路を探索する経路探索システムであって、移動領域を複数の領域に分割する領域分割部と、領域分割部により分割された複数の領域に対応し、それぞれの領域の評価値を算出する評価値算出部と、評価値算出部によって算出された評価値に基づいて経路を決定する経路決定部とを備え、評価値算出部が、近傍領域の評価値と、その近傍領域から自領域までの移動コストに基づいて評価値を算出するものである。本実施の形態3にかかる経路探索システムでは、上述した実施の形態とは異なり、複数の評価値算出ユニットを用いずに、1つ又は少数の演算処理装置(CPUなど)を用いて各領域における評価値算出処理を逐次的に実行する。尚、以下で説明しない構成及び処理に関しては、本実施の形態1における図1乃至図5で説明した構成及び処理と基本的に同一である。
【0071】
本実施の形態3にかかる経路探索システムは、例えば、ロボットに搭載されたコンピュータやロボットとは別に設けられたコンピュータにより実現される。このコンピュータは、例えば、中央処理装置(CPU)、ROM、RAM、ハードディスク等の補助記憶装置、CD−ROM等の可搬型記憶媒体が挿入される記憶媒体駆動装置、入力手段や出力手段を備えている。ROM、補助記憶装置、可搬型記憶媒体等の記憶媒体には、オペレーティングシステムと協働してCPU等に命令を与え、アプリケーションプログラムを記録することができる。アプリケーションプログラムはRAMにロードされることによって実行される。このアプリケーションプログラムは、本発明にかかる経路探索システムを実現する特有の経路探索プログラムを含む。経路探索システムによる経路探索は、中央処理装置がアプリケーションプログラムをRAM上に展開した上で当該アプリケーションプログラムに従った処理を補助記憶装置に格納されたデータを読み出し、また格納を行なうことにより、実行される。
【0072】
本実施の形態3にかかる経路探索システムによれば、従来手法と同様に1つ又は少数の演算処理装置(CPUなど)を有するコンピュータに容易に実装することできる。また、1つ又は少数の演算処理装置(CPUなど)を用いて評価値算出処理を実行するため、計算時間は従来手法と変わらないものの、複数の移動終点に対して同時に最短経路を探索することができる。
【0073】
その他の実施の形態.
上述した実施の形態では、指定された移動終点から評価値算出処理を開始して、経路決定処理においては任意の移動始点から経路を決定するものとして説明したが本発明はこれに限定されない。例えば、指定された移動始点から評価値算出処理を開始して、経路決定処理においては任意の移動終点から経路を決定するものとしてもよい。また、本発明によれば移動領域内の指定された2領域間の最短経路を算出することができるため、移動始点及び移動終点として指定する領域数が、多対一、一対多、多対多である場合においても本発明を応用することができる。
また、上述した実施の形態では、移動領域が2次元である場合の例を説明したが、移動領域が例えばx、y、z軸によって規定される3次元空間の場合でもよく、さらに、ロボットの姿勢(1次元)を併せて4次元の探索空間とした場合であっても本発明を適用することができる。
【0074】
さらにまた、上述した実施の形態では、移動手段として車輪などを有するロボットに本発明を適用した一例を示したが、これに限定されず、ロボットは足を有し、自律歩行可能な移動ロボットであってもよい。
【0075】
また、本発明は上述した実施の形態のみに限定されるものではなく、既に述べた本発明の要旨を逸脱しない範囲において種々の変更が可能であることは勿論である。
【図面の簡単な説明】
【0076】
【図1】本発明の実施の形態にかかる経路探索システムの構成を示す構成図である。
【図2】本発明の実施の形態にかかる移動領域を分割した複数の領域を示す概念図である。
【図3】本発明の実施の形態にかかる離散化された領域間の接続関係を説明するための概念図である。
【図4】本発明の実施の形態にかかる評価値算出ユニットの構成を示す概念図である。
【図5】本発明の実施の形態にかかる経路探索システムによる経路探索処理を示すフローチャートである。
【図6】本発明の実施の形態にかかる経路探索システムによる評価値算出処理を説明するための一例を示す図である。
【図7】本発明の実施の形態にかかる経路探索システムによる経路決定処理を説明するための一例を示す図である。
【図8】本発明の実施の形態にかかる経路探索システムによる計算時間短縮効果を説明するためのグラフを示す図である
【図9】本発明の実施の形態にかかる経路探索システムによる評価値算出処理を説明するための一例を示す図である。
【図10】本発明の実施の形態にかかる経路探索システムによる経路決定処理を説明するための一例を示す図である。
【符号の説明】
【0077】
1 経路探索システム、
11 経路探索処理部、12 経路探索記憶部、
111 領域分割部、112 評価値算出ユニット、113 経路決定部、
114 評価値処理部、
32 評価値記憶部、33 評価値記憶部、34 状態設定用信号線、
Cn 領域、G 移動終点、S 移動始点
【特許請求の範囲】
【請求項1】
移動領域内に存在する移動始点より移動を開始し、前記移動領域内に存在する移動終点に到達する自律移動体の移動経路を探索する経路探索システムであって、
前記移動領域を複数の領域に分割する領域分割部と、
前記領域分割部により分割された複数の領域に対応し、それぞれの領域の評価値を算出する複数の評価値算出部と、
前記評価値算出部によって算出された評価値に基づいて経路を決定する経路決定部とを備え、
前記評価値算出部が、
近傍に存在する領域の評価値と、当該近傍領域から自領域までの移動コストに基づいて評価値を算出する評価値処理部を有する
経路探索システム。
【請求項2】
前記評価値算出部は、
前記近傍領域の評価値のうち最も小さい評価値と、当該近傍領域から自領域までの幾何学的な距離に応じた移動コストに基づいて評価値を算出する
ことを特徴とする請求項1記載の経路探索システム。
【請求項3】
前記評価値算出部は、前記評価値処理部による評価値算出結果を格納する第一の評価値記憶部及び第二の評価値記憶部を更に備え、
前記評価値処理部が、
第一の評価値記憶部に格納された自領域の評価値、及び近傍領域の評価値に基づいて評価値算出処理を実行するか否かを判定し、判定の結果、評価値算出処理を実行する場合には、当該近傍領域の評価値と、当該近傍領域から自領域までの移動コストに基づいて自領域の評価値を算出し、当該評価値算出結果を第二の評価値記憶部に出力する
ことを特徴とする請求項1又は2記載の経路探索システム。
【請求項4】
前記経路決定部は、
前記移動始点に対応する領域から前記移動終点に対応する領域に向けて、算出された評価値のうち最も小さい評価値を有する近傍領域を選択してゆく
ことを特徴とする請求項1記載の経路探索システム。
【請求項5】
前記領域分割部により分割された前記領域について、自領域に対して隣接した領域を越えた領域を近傍領域として設定可能とした
ことを特徴とする請求項1乃至4いずれか1項記載の経路探索システム。
【請求項6】
前記経路探索システムは、
前記評価値算出部による評価値算出処理を実行可能又は不能に設定する状態設定部を更に備える
ことを特徴とする請求項1乃至5いずれか1項記載の経路探索システム。
【請求項7】
移動領域内に存在する移動始点より移動を開始し、前記移動領域内に存在する移動終点に到達する自律移動体の移動経路を探索する経路探索システムであって、
前記移動領域を複数の領域に分割する領域分割部と、
前記領域分割部により分割された複数の領域に対応し、近傍に存在する領域の評価値のうち最も小さい評価値と、当該近傍領域から自領域までの幾何学的な距離に応じた移動コストに基づいて、それぞれの領域における評価値算出処理を並列に実行する評価値算出部と、
前記評価値算出部によって算出された評価値に基づいて経路を決定する経路決定部とを備え、
前記移動領域内に複数の移動終点が存在する場合には、前記評価値算出部は当該移動終点を含む領域のそれぞれから評価値算出処理を開始し、前記経路決定部は当該評価値算出処理結果に基づいて任意の移動始点より経路決定処理を開始する
経路探索システム。
【請求項8】
移動領域内に存在する移動始点より移動を開始し、前記移動領域内に存在する移動終点に到達する自律移動体の移動経路を探索する経路探索方法であって、
前記移動領域を複数の領域に分割する領域分割ステップと、
前記領域分割部により分割された複数の領域における評価値算出処理を並列に実行する評価値算出ステップと、
前記評価値算出ステップによって算出された評価値に基づいて経路を決定する経路決定ステップとを備え、
前記評価値算出ステップでは、
近傍に存在する領域の評価値と、当該近傍領域から自領域までの移動コストに基づいて評価値を算出する
経路探索方法。
【請求項9】
前記評価値算出ステップでは、
前記近傍領域の評価値のうち最も小さい評価値と、当該近傍領域から自領域までの幾何学的な距離に応じた移動コストに基づいて評価値を算出する
ことを特徴とする請求項8記載の経路探索方法。
【請求項10】
前記経路決定ステップでは、
前記移動始点に対応する領域から前記移動終点に対応する領域に向けて、算出された評価値のうち最も小さい評価値を有する近傍領域を選択してゆく
ことを特徴とする請求項8記載の経路探索方法。
【請求項11】
前記領域分割ステップにより分割された前記領域について、自領域に対して隣接した領域を越えた領域を近傍領域として設定可能とした
ことを特徴とする請求項8乃至10いずれか1項記載の経路探索方法。
【請求項12】
前記経路探索方法は、
前記評価値算出ステップによる評価値算出処理を実行可能又は不能に設定する状態設定ステップを更に備える
ことを特徴とする請求項8乃至11いずれか1項記載の経路探索方法。
【請求項13】
移動領域内に存在する移動始点より移動を開始し、前記移動領域内に存在する移動終点に到達する自律移動体の移動経路を探索する経路探索プログラムであって、
コンピュータに対して、
前記移動領域を複数の領域に分割する領域分割ステップと、
前記領域分割部により分割された複数の領域に対応し、近傍に存在する領域の評価値と、当該近傍領域から自領域までの移動コストに基づいて、それぞれの領域における評価値算出処理を並列に実行する評価値算出ステップと、
前記評価値算出ステップによって算出された評価値に基づいて経路を決定する経路決定ステップとを実行させる
経路探索プログラム。
【請求項14】
移動領域内に存在する移動始点より移動を開始し、前記移動領域内に存在する移動終点に到達する移動経路を探索可能な自律移動体であって、
前記移動領域を複数の領域に分割する領域分割部と、
前記領域分割部により分割された複数の領域に対応し、それぞれの領域の評価値を算出する複数の評価値算出部と、
前記評価値算出部によって算出された評価値に基づいて経路を決定する経路決定部とを備え、
前記評価値算出部が、
近傍に存在する領域の評価値と、当該近傍領域から自領域までの移動コストに基づいて評価値を算出する評価値処理部を有する
自律移動体。
【請求項1】
移動領域内に存在する移動始点より移動を開始し、前記移動領域内に存在する移動終点に到達する自律移動体の移動経路を探索する経路探索システムであって、
前記移動領域を複数の領域に分割する領域分割部と、
前記領域分割部により分割された複数の領域に対応し、それぞれの領域の評価値を算出する複数の評価値算出部と、
前記評価値算出部によって算出された評価値に基づいて経路を決定する経路決定部とを備え、
前記評価値算出部が、
近傍に存在する領域の評価値と、当該近傍領域から自領域までの移動コストに基づいて評価値を算出する評価値処理部を有する
経路探索システム。
【請求項2】
前記評価値算出部は、
前記近傍領域の評価値のうち最も小さい評価値と、当該近傍領域から自領域までの幾何学的な距離に応じた移動コストに基づいて評価値を算出する
ことを特徴とする請求項1記載の経路探索システム。
【請求項3】
前記評価値算出部は、前記評価値処理部による評価値算出結果を格納する第一の評価値記憶部及び第二の評価値記憶部を更に備え、
前記評価値処理部が、
第一の評価値記憶部に格納された自領域の評価値、及び近傍領域の評価値に基づいて評価値算出処理を実行するか否かを判定し、判定の結果、評価値算出処理を実行する場合には、当該近傍領域の評価値と、当該近傍領域から自領域までの移動コストに基づいて自領域の評価値を算出し、当該評価値算出結果を第二の評価値記憶部に出力する
ことを特徴とする請求項1又は2記載の経路探索システム。
【請求項4】
前記経路決定部は、
前記移動始点に対応する領域から前記移動終点に対応する領域に向けて、算出された評価値のうち最も小さい評価値を有する近傍領域を選択してゆく
ことを特徴とする請求項1記載の経路探索システム。
【請求項5】
前記領域分割部により分割された前記領域について、自領域に対して隣接した領域を越えた領域を近傍領域として設定可能とした
ことを特徴とする請求項1乃至4いずれか1項記載の経路探索システム。
【請求項6】
前記経路探索システムは、
前記評価値算出部による評価値算出処理を実行可能又は不能に設定する状態設定部を更に備える
ことを特徴とする請求項1乃至5いずれか1項記載の経路探索システム。
【請求項7】
移動領域内に存在する移動始点より移動を開始し、前記移動領域内に存在する移動終点に到達する自律移動体の移動経路を探索する経路探索システムであって、
前記移動領域を複数の領域に分割する領域分割部と、
前記領域分割部により分割された複数の領域に対応し、近傍に存在する領域の評価値のうち最も小さい評価値と、当該近傍領域から自領域までの幾何学的な距離に応じた移動コストに基づいて、それぞれの領域における評価値算出処理を並列に実行する評価値算出部と、
前記評価値算出部によって算出された評価値に基づいて経路を決定する経路決定部とを備え、
前記移動領域内に複数の移動終点が存在する場合には、前記評価値算出部は当該移動終点を含む領域のそれぞれから評価値算出処理を開始し、前記経路決定部は当該評価値算出処理結果に基づいて任意の移動始点より経路決定処理を開始する
経路探索システム。
【請求項8】
移動領域内に存在する移動始点より移動を開始し、前記移動領域内に存在する移動終点に到達する自律移動体の移動経路を探索する経路探索方法であって、
前記移動領域を複数の領域に分割する領域分割ステップと、
前記領域分割部により分割された複数の領域における評価値算出処理を並列に実行する評価値算出ステップと、
前記評価値算出ステップによって算出された評価値に基づいて経路を決定する経路決定ステップとを備え、
前記評価値算出ステップでは、
近傍に存在する領域の評価値と、当該近傍領域から自領域までの移動コストに基づいて評価値を算出する
経路探索方法。
【請求項9】
前記評価値算出ステップでは、
前記近傍領域の評価値のうち最も小さい評価値と、当該近傍領域から自領域までの幾何学的な距離に応じた移動コストに基づいて評価値を算出する
ことを特徴とする請求項8記載の経路探索方法。
【請求項10】
前記経路決定ステップでは、
前記移動始点に対応する領域から前記移動終点に対応する領域に向けて、算出された評価値のうち最も小さい評価値を有する近傍領域を選択してゆく
ことを特徴とする請求項8記載の経路探索方法。
【請求項11】
前記領域分割ステップにより分割された前記領域について、自領域に対して隣接した領域を越えた領域を近傍領域として設定可能とした
ことを特徴とする請求項8乃至10いずれか1項記載の経路探索方法。
【請求項12】
前記経路探索方法は、
前記評価値算出ステップによる評価値算出処理を実行可能又は不能に設定する状態設定ステップを更に備える
ことを特徴とする請求項8乃至11いずれか1項記載の経路探索方法。
【請求項13】
移動領域内に存在する移動始点より移動を開始し、前記移動領域内に存在する移動終点に到達する自律移動体の移動経路を探索する経路探索プログラムであって、
コンピュータに対して、
前記移動領域を複数の領域に分割する領域分割ステップと、
前記領域分割部により分割された複数の領域に対応し、近傍に存在する領域の評価値と、当該近傍領域から自領域までの移動コストに基づいて、それぞれの領域における評価値算出処理を並列に実行する評価値算出ステップと、
前記評価値算出ステップによって算出された評価値に基づいて経路を決定する経路決定ステップとを実行させる
経路探索プログラム。
【請求項14】
移動領域内に存在する移動始点より移動を開始し、前記移動領域内に存在する移動終点に到達する移動経路を探索可能な自律移動体であって、
前記移動領域を複数の領域に分割する領域分割部と、
前記領域分割部により分割された複数の領域に対応し、それぞれの領域の評価値を算出する複数の評価値算出部と、
前記評価値算出部によって算出された評価値に基づいて経路を決定する経路決定部とを備え、
前記評価値算出部が、
近傍に存在する領域の評価値と、当該近傍領域から自領域までの移動コストに基づいて評価値を算出する評価値処理部を有する
自律移動体。
【図1】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【公開番号】特開2009−19932(P2009−19932A)
【公開日】平成21年1月29日(2009.1.29)
【国際特許分類】
【出願番号】特願2007−181438(P2007−181438)
【出願日】平成19年7月10日(2007.7.10)
【出願人】(000003207)トヨタ自動車株式会社 (59,920)
【Fターム(参考)】
【公開日】平成21年1月29日(2009.1.29)
【国際特許分類】
【出願日】平成19年7月10日(2007.7.10)
【出願人】(000003207)トヨタ自動車株式会社 (59,920)
【Fターム(参考)】
[ Back to top ]