(57)【特許請求の範囲】
【請求項１】
移動領域内に存在する移動始点より移動を開始し、前記移動領域内に存在する移動終点に到達する自律移動体の移動経路を探索する経路探索システムであって、
前記移動領域を複数の領域に分割する領域分割部と、
前記領域分割部により分割された複数の領域に対応し、それぞれの領域の評価値を算出する複数の評価値算出部と、
前記移動始点に対応する領域から前記移動終点に対応する領域に向けて、前記評価値算出部によって算出された評価値のうち最も小さい評価値を有する近傍領域を選択し、該選択された領域を通過する経路を決定する経路決定部とを備え、
前記評価値算出部が、
近傍に存在する領域の評価値と、当該近傍領域から自領域までの移動コストに基づいて自領域の評価値を算出する評価値処理部を有する
経路探索システム。
【請求項２】
前記評価値算出部は、
前記近傍領域の評価値のうち最も小さい評価値と、当該近傍領域から自領域までの幾何学的な距離に応じた移動コストに基づいて自領域の評価値を算出する
ことを特徴とする請求項１記載の経路探索システム。
【請求項３】
前記評価値算出部は、前記評価値処理部による評価値算出結果を格納する第一の評価値記憶部及び第二の評価値記憶部を更に備え、
前記評価値処理部が、
第一の評価値記憶部に格納された自領域の評価値、及び近傍領域の評価値に基づいて評価値算出処理を実行するか否かを判定し、判定の結果、評価値算出処理を実行する場合には、当該近傍領域の評価値と、当該近傍領域から自領域までの移動コストに基づいて自領域の評価値を算出し、当該評価値算出結果を第二の評価値記憶部に出力する
ことを特徴とする請求項１又は２記載の経路探索システム。
【請求項４】
前記領域分割部により分割された前記領域について、自領域に対して隣接した領域を越えた領域を近傍領域として設定可能とした
ことを特徴とする請求項１乃至３いずれか１項記載の経路探索システム。
【請求項５】
前記経路探索システムは、
前記評価値算出部による評価値算出処理を実行可能又は不能に設定する状態設定部を更に備える
ことを特徴とする請求項１乃至４いずれか１項記載の経路探索システム。
【請求項６】
移動領域内に存在する移動始点より移動を開始し、前記移動領域内に存在する移動終点に到達する自律移動体の移動経路を探索する経路探索システムであって、
前記移動領域を複数の領域に分割する領域分割部と、
前記領域分割部により分割された複数の領域に対応し、近傍に存在する領域の評価値のうち最も小さい評価値と、当該近傍領域から自領域までの幾何学的な距離に応じた移動コストに基づいて、それぞれの領域における評価値算出処理を並列に実行する評価値算出部と、
前記移動始点に対応する領域から前記移動終点に対応する領域に向けて、前記評価値算出部によって算出された評価値のうち最も小さい評価値を有する近傍領域を選択し、該選択された領域を通過する経路を決定する経路決定部とを備え、
前記移動領域内に複数の移動終点が存在する場合には、前記評価値算出部は当該移動終点を含む領域のそれぞれから評価値算出処理を開始し、前記経路決定部は当該評価値算出処理結果に基づいて任意の移動始点より経路決定処理を開始する
経路探索システム。
【請求項７】
移動領域内に存在する移動始点より移動を開始し、前記移動領域内に存在する移動終点に到達する自律移動体の移動経路を探索する経路探索方法であって、
前記移動領域を複数の領域に分割する領域分割ステップと、
前記領域分割部により分割された複数の領域における評価値算出処理を並列に実行する評価値算出ステップと、
前記移動始点に対応する領域から前記移動終点に対応する領域に向けて、前記評価値算出ステップによって算出された評価値のうち最も小さい評価値を有する近傍領域を選択し、該選択された領域を通過する経路を決定する経路決定ステップとを備え、
前記評価値算出ステップでは、
近傍に存在する領域の評価値と、当該近傍領域から自領域までの移動コストに基づいて自領域の評価値を算出する
経路探索方法。
【請求項８】
前記評価値算出ステップでは、
前記近傍領域の評価値のうち最も小さい評価値と、当該近傍領域から自領域までの幾何学的な距離に応じた移動コストに基づいて自領域の評価値を算出する
ことを特徴とする請求項７記載の経路探索方法。
【請求項９】
前記領域分割ステップにより分割された前記領域について、自領域に対して隣接した領域を越えた領域を近傍領域として設定可能とした
ことを特徴とする請求項７乃至８いずれか１項記載の経路探索方法。
【請求項１０】
前記経路探索方法は、
前記評価値算出ステップによる評価値算出処理を実行可能又は不能に設定する状態設定ステップを更に備える
ことを特徴とする請求項７乃至９いずれか１項記載の経路探索方法。
【請求項１１】
移動領域内に存在する移動始点より移動を開始し、前記移動領域内に存在する移動終点に到達する自律移動体の移動経路を探索する経路探索プログラムであって、
コンピュータに対して、
前記移動領域を複数の領域に分割する領域分割ステップと、
前記領域分割部により分割された複数の領域に対応し、近傍に存在する領域の評価値と、当該近傍領域から自領域までの移動コストに基づいて、それぞれの領域における評価値算出処理を並列に実行する評価値算出ステップと、
前記移動始点に対応する領域から前記移動終点に対応する領域に向けて、前記評価値算出ステップによって算出された評価値のうち最も小さい評価値を有する近傍領域を選択し、該選択された領域を通過する経路を決定する経路決定ステップとを実行させる
経路探索プログラム。
【請求項１２】
移動領域内に存在する移動始点より移動を開始し、前記移動領域内に存在する移動終点に到達する移動経路を探索可能な自律移動体であって、
前記移動領域を複数の領域に分割する領域分割部と、
前記領域分割部により分割された複数の領域に対応し、それぞれの領域の評価値を算出する複数の評価値算出部と、
前記移動始点に対応する領域から前記移動終点に対応する領域に向けて、前記評価値算出部によって算出された評価値のうち最も小さい評価値を有する近傍領域を選択し、該選択された領域を通過する経路を決定する経路決定部とを備え、
前記評価値算出部が、
近傍に存在する領域の評価値と、当該近傍領域から自領域までの移動コストに基づいて自領域の評価値を算出する評価値処理部を有する
自律移動体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は移動経路を探索する経路探索システム、経路探索方法、及び自律移動体に関する。
【背景技術】
【０００２】
従来より、ロボットや車両などの移動体が、移動始点から移動終点へと到達するための移動経路を探索する技術が提案されている。移動経路探索手法としては、Ａ＊（エースター）アルゴリズムやダイキストラ法を用いる手法が良く知られている（例えば特許文献１、２）。
【特許文献１】特開平９−２２９７０４号公報
【特許文献２】特開２００３−２３３７６８号公報
【発明の開示】
【発明が解決しようとする課題】
【０００３】
しかしながら、従来の経路探索手法では、１つ又は少数の演算処理装置（ＣＰＵなど）によって逐次的に経路探索処理を行うため、経路探索に要する計算コストが高くなるという問題がある。特に、Ａ＊アルゴリズムなどの幅優先探索アルゴリズムでは、コストが最小である経路候補を順々に延長してゆくため、探索空間が広くなるにつれて、経路候補数が指数的に急増する。これにより、演算対象となる経路候補数の増大によって、移動経路を算出するための演算量が多くなるため、演算を行うためのメモリ使用量が多くなると共に、移動経路を算出するための演算時間が長くなる。従って、このような従来手法では、探索空間が広い場合には非常に大きな計算コストを要することになり、ロボットへの実装が現実的には困難である。
また、ダイキストラ法などの従来手法は、ある時点における計算について、それ以前の計算結果を利用しているため並列処理が困難であり、一般的には、１つ又は少数の演算処理装置（ＣＰＵなど）によって別個独立に最短経路を探索する。このため、複数の移動終点に対して同時に最短経路を探索することができないという問題がある。
【０００４】
このように、従来の移動経路探索方法では逐次的に経路探索処理を行うため、経路探索空間が広い場合には、短時間で最適な経路を探索することができないという問題があった。
また、複数の移動終点に対して、同時に最適な経路を探索することができないという問題があった。
【０００５】
本発明は、かかる課題を解決するためになされたものであり、経路探索空間が広い場合であっても、最適な経路を高速で探索することができる経路探索システム、経路探索方法、及び自律移動体を提供することを第一の目的とする。
【０００６】
また、本発明は、複数の移動終点に対して、同時に最適な経路を探索することができる経路探索システム、経路探索方法、及び自律移動体を提供することを第二の目的とする。
【課題を解決するための手段】
【０００７】
本発明にかかる経路探索システムは、移動領域内に存在する移動始点より移動を開始し、前記移動領域内に存在する移動終点に到達する自律移動体の移動経路を探索する経路探索システムであって、前記移動領域を複数の領域に分割する領域分割部と、前記領域分割部により分割された複数の領域に対応し、それぞれの領域の評価値を算出する複数の評価値算出部と、前記移動始点に対応する領域から前記移動終点に対応する領域に向けて、前記評価値算出部によって算出された評価値のうち最も小さい評価値を有する近傍領域を選択し、該選択された領域を通過する経路を決定する経路決定部とを備え、前記評価値算出部が、近傍に存在する領域の評価値と、当該近傍領域から自領域までの移動コストに基づいて自領域の評価値を算出する評価値処理部を有するものである。
【０００８】
これにより、移動領域を複数の領域に分割することで、経路探索のための移動コストを領域間の幾何学的な距離によって表現することができる。そして、複数の評価値算出部が、このような幾何学的な距離と近傍領域の評価値とに基づいて、それぞれの領域における評価値算出処理を並列に実行することで、逐次的に各領域の評価値を算出する場合に比べて、経路探索に要する計算コストを大きく削減することができる。従って、経路探索空間が広い場合であっても、最適な経路を高速で探索することができる。
【０００９】
さらに、移動終点として複数の領域を指定する場合においても、複数の移動終点から評価値算出処理がそれぞれ開始されて、それぞれの処理が並列に実行されながらその近傍領域へと伝わっていく。このため、移動終点でない他の領域を注目する領域としたとき、その注目する領域に最初に伝わった処理は、複数の移動終点のうちでそれぞれの移動終点からその近傍領域を介して最初にその注目する領域へと処理を伝えることができた移動終点から開始された処理となる。即ち、評価値算出処理の実行後に、各領域において算出される評価値は、複数の移動終点のうちで最も早く評価値算出処理を各領域に対して伝えることが可能な移動終点であって、その移動終点からの移動コストに基づいた評価値となる。従って、このような評価値によれば、複数の移動終点に対して同時に最適な経路を探索することができる。
【００１０】
また、評価値算出部は、近傍領域の評価値のうち最も小さい評価値と、その近傍領域から自領域までの幾何学的な距離に応じた移動コストに基づいて自領域の評価値を算出してもよい。このように、近傍領域における最小の評価値と、その近傍領域から自領域までの幾何学的な距離に応じた移動コストに基づいて評価値を算出することで、容易に評価値を算出することができる。
【００１１】
さらにまた、前記評価値算出部は、前記評価値処理部による評価値算出結果を格納する第一の評価値記憶部及び第二の評価値記憶部を更に備え、前記評価値処理部が、第一の評価値記憶部に格納された自領域の評価値、及び近傍に存在する領域の評価値に基づいて評価値算出処理を実行するか否かを判定し、判定の結果、評価値算出処理を実行する場合には、当該近傍領域の評価値と、当該近傍領域から自領域までの移動コストに基づいて自領域の評価値を算出し、当該評価値算出結果を第二の評価値記憶部に出力するようにしてもよい。このように、全ての評価値算出部において、評価値算出処理を実行するか否かを、それぞれ第一の評価値記憶部に格納された評価値に基づいて判定し、評価値算出結果を、それぞれ第一の評価値記憶部とは異なる第二の評価値記憶部に出力する。これにより、１回の評価値算出処理の結果、評価値算出結果の干渉を防ぐことができると共に、１近傍を越えて評価値が算出されないよう制限することができるため、１近傍領域に含まれる領域の評価値のみを算出させることができる。従って、複数の評価値算出部による評価値算出処理のタイミングを同期させることができる。
【００１２】
また、前記経路決定部は、前記移動始点に対応する領域から前記移動終点に対応する領域に向けて、算出された評価値のうち最も小さい評価値を有する近傍領域を選択してゆくようにしてもよい。このように、移動始点に対応する領域から移動終点に対応する領域に向けて、算出された評価値のうち最小の評価値を有する近傍領域を選択してゆくことで、簡単に経路を決定することができる。
【００１３】
さらにまた、前記領域分割部により分割された前記領域について、自領域に対して隣接した領域を越えた領域を近傍領域として設定可能としてもよい。これにより、注目する領域に直接隣接していない領域についても近傍領域に含めることで、それら領域間を通過する経路を作成することができる。従って、移動始点から移動終点へと至る経路の角度分解能を柔軟に設定することができ、より滑らかな経路を作成することができる。
【００１４】
また、前記経路探索システムは、前記評価値算出部による評価値算出処理を実行可能又は不能に設定する状態設定部を更に備えるようにしてもよい。これにより、所望の評価値算出部について、評価値算出処理を行うタイミングを調整することができる。例えば、環境に応じて、特定の評価値算出部の評価値算出処理を一定期間実行不能に設定することで、それら評価値算出部は待ち状態となり、対応する領域には評価値が算出されない。一定期間経過後に評価値算出処理が実行可能となった場合に、それら待ち状態を経た評価値算出部によって算出される評価値は、既に算出された他の領域の評価値に比べて、待ち時間の分だけ相対的に大きな評価値が算出される。即ち、評価値算出処理において、待ち時間を評価値に反映させることで、特定の領域の評価値を大きくすることができる。従って、評価値の高い領域は経路として選択されにくくなるため、特定の領域を避けるように柔軟に経路を作成することができる。
【００１５】
また、本発明にかかる経路探索システムは、移動領域内に存在する移動始点より移動を開始し、前記移動領域内に存在する移動終点に到達する自律移動体の移動経路を探索する経路探索システムであって、前記移動領域を複数の領域に分割する領域分割部と、前記領域分割部により分割された複数の領域に対応し、近傍に存在する領域の評価値のうち最も小さい評価値と、当該近傍領域から自領域までの幾何学的な距離に応じた移動コストに基づいて、それぞれの領域における評価値算出処理を並列に実行する評価値算出部と、前記移動始点に対応する領域から前記移動終点に対応する領域に向けて、前記評価値算出部によって算出された評価値のうち最も小さい評価値を有する近傍領域を選択し、該選択された領域を通過する経路を決定する経路決定部とを備え、前記移動領域内に複数の移動終点が存在する場合には、前記評価値算出部は当該移動終点を含む領域のそれぞれから評価値算出処理を開始し、前記経路決定部は当該評価値算出処理結果に基づいて任意の移動始点より経路決定処理を開始するものである。
【００１６】
これにより、移動終点として複数の領域を指定する場合においても、評価値算出部が、それぞれ並列に評価値算出処理を実行すると共に、近傍領域における評価値の最小値及び自領域までの移動コストに基づいて評価値算出処理を実行する。このため、各領域における評価値は、複数の移動終点からの移動コストの総和が最小となる評価値が算出され、最も移動コストの少ない移動終点までの経路を探索することができる。従って、このような評価値によれば、複数の移動終点に対して同時に最適な経路を探索することができる。
【００１７】
本発明にかかる経路探索方法は、移動領域内に存在する移動始点より移動を開始し、前記移動領域内に存在する移動終点に到達する自律移動体の移動経路を探索する経路探索方法であって、前記移動領域を複数の領域に分割する領域分割ステップと、前記領域分割部により分割された複数の領域における評価値算出処理を並列に実行する評価値算出ステップと、前記移動始点に対応する領域から前記移動終点に対応する領域に向けて、前記評価値算出ステップによって算出された評価値のうち最も小さい評価値を有する近傍領域を選択し、該選択された領域を通過する経路を決定する経路決定ステップとを備え、前記評価値算出ステップでは、近傍に存在する領域の評価値と、当該近傍領域から自領域までの移動コストに基づいて自領域の評価値を算出するものである。
【００１８】
これにより、移動領域を複数の領域に分割することで、経路探索のための移動コストを領域間の幾何学的な距離によって表現することができる。そして、複数の評価値算出ステップが、このような幾何学的な距離と近傍領域の評価値とに基づいて、それぞれの領域における評価値算出処理を並列に実行することで、逐次的に各領域の評価値を算出する場合に比べて、経路探索に要する計算コストを大きく削減することができる。従って、経路探索空間が広い場合であっても、最適な経路を高速で探索することができる。
【００１９】
さらに、移動終点として複数の領域を指定する場合においても、評価値算出処理は複数の移動終点から開始され、それぞれ並列に実行されながらその近傍領域へと処理が伝わっていく。このため、移動終点を含まない他の領域において、最も早くその領域に伝わった処理は、その処理を最初に開始した移動終点から開始された処理によるものとなる。即ち、評価値算出処理の実行後に、各領域において算出される評価値は、複数の移動終点のうち、各領域に対して最も早く評価値算出処理を伝えることが可能な移動終点であって、その移動終点からの移動コストに基づいた評価値となる。従って、このような評価値によれば、複数の移動終点に対して同時に最適な経路を探索することができる。
【００２０】
また、前記評価値算出ステップでは、近傍領域の評価値のうち最も小さい評価値と、当該近傍領域から自領域までの幾何学的な距離に応じた移動コストに基づいて自領域の評価値を算出するようにしてもよい。このように、近傍領域における最小の評価値と、その近傍領域から自領域までの幾何学的な距離に応じた移動コストに基づいて評価値を算出することで、容易に評価値を算出することができる。
【００２１】
さらにまた、前記経路決定ステップでは、前記移動始点に対応する領域から前記移動終点に対応する領域に向けて、算出された評価値のうち最も小さい評価値を有する近傍領域を選択してゆくようにしてもよい。このように、移動始点に対応する領域から移動終点に対応する領域に向けて、算出された評価値のうち最小の評価値を有する近傍領域を選択してゆくことで、簡単に経路を決定することができる。
【００２２】
また、前記領域分割ステップにより分割された前記領域について、自領域に対して隣接した領域を越えた領域を近傍領域として設定可能としてもよい。これにより、注目する領域に直接隣接していない領域についても近傍領域に含めることで、それら領域間を通過する経路を作成することができる。従って、移動始点から移動終点へと至る経路の角度分解能を柔軟に設定することができ、より滑らかな経路を作成することができる。
【００２３】
さらにまた、前記経路探索方法は、前記評価値算出ステップによる評価値算出処理を実行可能又は不能に設定する状態設定ステップを更に備えるようにしてもよい。これにより、所望の領域について、評価値算出処理を行うタイミングを調整することができる。例えば、環境に応じて、特定の領域の評価値算出処理を一定期間実行不能に設定することで、それら評価値算出ステップは待ち状態となり、対応する領域には評価値が算出されない。一定期間経過後に評価値算出処理が実行可能となった場合に、それら待ち状態を経た評価値算出ステップによって算出される評価値は、既に算出された他の領域の評価値に比べて、待ち時間の分だけ相対的に大きな評価値が算出される。即ち、評価値算出処理において、待ち時間を評価値に反映させることで、特定の領域の評価値を大きくすることができる。従って、評価値の高い領域は経路として選択されにくくなるため、特定の領域を避けるように柔軟に経路を作成することができる。
【００２４】
本発明にかかる経路探索プログラムは、移動領域内に存在する移動始点より移動を開始し、前記移動領域内に存在する移動終点に到達する自律移動体の移動経路を探索する経路探索プログラムであって、コンピュータに対して、前記移動領域を複数の領域に分割する領域分割ステップと、前記領域分割部により分割された複数の領域に対応し、近傍に存在する領域の評価値と、当該近傍領域から自領域までの移動コストに基づいて、それぞれの領域における評価値算出処理を並列に実行する評価値算出ステップと、前記移動始点に対応する領域から前記移動終点に対応する領域に向けて、前記評価値算出ステップによって算出された評価値のうち最も小さい評価値を有する近傍領域を選択し、該選択された領域を通過する経路を決定する経路決定ステップとを実行させるものである。
【００２５】
これにより、移動領域を複数の領域に分割することで、経路探索のための移動コストを領域間の幾何学的な距離によって表現することができる。そして、評価値算出ステップが、このような幾何学的な距離と近傍領域の評価値とに基づいて、それぞれの領域における評価値算出処理を並列に実行することで、逐次的に各領域の評価値を算出する場合に比べて、経路探索に要する計算コストを大きく削減することができる。従って、経路探索空間が広い場合であっても、最適な経路を高速で探索することができる。
【００２６】
さらに、移動終点として複数の領域を指定する場合においても、評価値算出処理は複数の移動終点から開始され、それぞれ並列に実行されながらその近傍領域へと処理が伝わっていく。このため、移動終点を含まない他の領域において、最も早くその領域に伝わった処理は、その処理を最初に開始した移動終点から開始された処理によるものとなる。即ち、評価値算出処理の実行後に、各領域において算出される評価値は、複数の移動終点のうち、各領域に対して最も早く評価値算出処理を伝えることが可能な移動終点であって、その移動終点からの移動コストに基づいた評価値となる。従って、このような評価値によれば、複数の移動終点に対して同時に最適な経路を探索することができる。
【００２７】
本発明にかかる自律移動体は、移動領域内に存在する移動始点より移動を開始し、前記移動領域内に存在する移動終点に到達する移動経路を探索可能な自律移動体であって、前記移動領域を複数の領域に分割する領域分割部と、前記領域分割部により分割された複数の領域に対応し、それぞれの領域の評価値を算出する複数の評価値算出部と、前記移動始点に対応する領域から前記移動終点に対応する領域に向けて、前記評価値算出部によって算出された評価値のうち最も小さい評価値を有する近傍領域を選択し、該選択された領域を通過する経路を決定する経路決定部とを備え、前記評価値算出部が、近傍に存在する領域の評価値と、当該近傍領域から自領域までの移動コストに基づいて自領域の評価値を算出する評価値処理部を有するものである。
【００２８】
これにより、移動領域を複数の領域に分割することで、経路探索のための移動コストを領域間の幾何学的な距離によって表現することができる。そして、複数の評価値算出部が、このような幾何学的な距離と近傍領域の評価値とに基づいて、それぞれの領域における評価値算出処理を並列に実行することで、逐次的に各領域の評価値を算出する場合に比べて、経路探索に要する計算コストを大きく削減することができる。従って、経路探索空間が広い場合であっても、最適な経路を高速で探索することができる。
【００２９】
さらに、移動終点として複数の領域を指定する場合においても、評価値算出処理は複数の移動終点から開始され、それぞれ並列に実行されながらその近傍領域へと処理が伝わっていく。このため、移動終点を含まない他の領域において、最も早くその領域に伝わった処理は、その処理を最初に開始した移動終点から開始された処理によるものとなる。即ち、評価値算出処理の実行後に、各領域において算出される評価値は、複数の移動終点のうち、各領域に対して最も早く評価値算出処理を伝えることが可能な移動終点であって、その移動終点からの移動コストに基づいた評価値となる。従って、このような評価値によれば、複数の移動終点に対して同時に最適な経路を探索することができる。
【発明の効果】
【００３０】
本発明によれば、経路探索空間が広い場合であっても、最適な経路を高速で探索することができる経路探索システム、経路探索方法、及び自律移動体を提供することを第一の目的とする。
【００３１】
また、本発明によれば、複数の移動終点に対して、同時に最適な経路を探索することができる経路探索システム、経路探索方法、及び自律移動体を提供することを第二の目的とする。
【発明を実施するための最良の形態】
【００３２】
以下、本発明を適用した具体的な実施の形態について、図面を参照しながら詳細に説明する。尚、各図面において、同一要素には同一の符号を付しており、説明の明確化のため、必要に応じて重複説明を省略する。
【００３３】
発明の実施の形態１．
本発明の実施の形態１にかかる経路探索システムでは、自律移動体としてロボットを用いている。ロボットは、例えば、それぞれ独立して回転制御される二つの車輪を備えたものでもよく、２輪よりも多い、例えば４輪走行のロボットや、１輪走行のロボット、２足歩行・４足歩行のロボットであってもよい。また、ロボットに限らず、２輪走行や４輪走行の車両にも適用できる。本例におけるロボットは、障害物を検出するセンサやカメラを備え、検出された障害物に応じて、これを避けるように経路探索を行なう。
【００３４】
当該経路探索システムは、移動領域を複数の格子状の領域に分割し、分割された複数の領域に対応する評価値算出部を備える。各評価値算出部は、独立した評価値処理部及び評価値記憶部を備え、各評価値算出部に対応するそれぞれの領域の評価値を算出し、その結果を格納する。評価値算出処理は、近傍に存在する領域の評価値と、その近傍領域から自領域までの移動コストに基づいて実行される。そして、経路探索システムは、各評価値算出部によって算出された評価値に基づいて経路決定処理を実行する。
【００３５】
また、本実施の形態１にかかる経路探索システムは、経路探索問題を、離散化された移動領域において、その移動領域を伝播する仮想的なコストポテンシャル波の伝播履歴を求める問題と置き換えて解くものである。移動領域を構成する評価値算出部間の相互作用を利用することで、最短経路を高速に探索することができる。後述するように、移動領域の次元数をｐとすると、従来手法ではＯ（ｎｐ）の計算時間が必要であったが、本実施の形態１にかかる経路探索システムでは、Ｏ（ｎ√ｐ）の計算時間で最短経路を得ることができる。
【００３６】
図１は、本実施の形態１にかかる経路探索システムの概略構成を示すブロック図である。図１に示されるように、経路探索システム１は、経路探索処理部１１と経路探索記憶部１２により構成されている。経路探索処理部１１は、領域分割部１１１、複数の評価値算出ユニット１１２、及び経路決定部１１３を備えている。評価値算出部としての評価値算出ユニット１１２は、物理的に独立した評価値算出ユニットであって、評価値算出処理を並列に実行する。
【００３７】
経路探索記憶部１２には、ロボットが移動する移動領域全体の形状に、略一定間隔ｄ（例えば１０ｃｍ）に配置された格子点を結ぶグリッド線を仮想的に描写することで得られるグリッドマップが記憶されている。ロボットは、ＧＰＳ等から得られた位置情報を、このグリッドマップ上における自己の位置に置き換えて、グリッドマップ上における自己位置を認識する。グリッドマップ上において、ロボットの自己位置に相当する場所、および目的地である移動終点、および移動終点におけるロボットの移動方向が特定される。ロボットは、グリッドマップ上において特定された自己位置を移動始点から、目的地である移動終点までの移動経路を作成し、作成された移動経路に従って移動を行う。
【００３８】
領域分割部１１１は、ロボットが移動する移動領域を格子状の領域に分割する。ここでは、上述の略一定間隔ｄ（例えば１０ｃｍ）に配置された格子点を囲む複数の領域に分割する。図２は、移動領域を分割して、離散化された複数の領域Ｃｎを示す概念図である。尚、領域分割部１１１による分割方法はこれに限定されない。例えば、上述の分割後の領域よりも大きな領域へと分割することで、経路探索に要する時間をより短縮することができる。また、グリッドマップが格子状に並んだノードと、各ノードを接続するリンクを備える場合には、分割された領域は、グリッドマップ上に配置されたノードに対応するものとして扱ってもよい（この場合には、近傍領域はリンクによって規定される）。即ち、各領域は各ノードを示し、各ノードに対する評価値を算出し、それらノードに付与された評価値に基づいて、経路を選択するようにしてもよい。
【００３９】
領域分割部１１１により分割された領域間の接続関係が定められ、注目する領域に接続する領域を近傍領域とする。図３は、離散化された領域間の接続関係を説明するための概念図である。図３（ａ）では、注目する領域Ｃ０に対して、隣接領域Ｃ１乃至Ｃ８を近傍領域として定めるものである。また、図３（ｂ）では、注目する領域Ｃ０に対して、隣接領域Ｃ１乃至Ｃ８に加えて、さらに領域Ｃ９乃至Ｃ１６を近傍領域として定めるものである。このように、自領域に対して隣接した領域を越えた領域を近傍領域として設定可能とすることで、自領域及びそれら近傍領域間を通過する経路を作成することができる。このようにすれば、移動始点から移動終点へと至る経路の角度分解能を柔軟に設定することができ、より滑らかな経路を作成することができる。
【００４０】
評価値算出ユニット１１２は、領域分割部１１１により分割された領域に対応し、それぞれの領域の評価値を算出する評価値処理部１１４を有する。図４は、評価値算出ユニット１１２の構成を示す概念図である。図４（ａ）に示すように、評価値算出ユニット１１２は、評価値処理部１１４と、第一の評価値記憶部及び第二の評価値記憶部としての、少なくとも２つの評価値記憶部３２及び３３を備える。評価値算出ユニット１１２には、状態設定部としての状態設定用信号線３４が接続されている。
【００４１】
尚、評価値算出ユニット１１２はいずれも同一の構成を有しており、簡易な構成により経路探索システム１を構成することができる。各評価値算出ユニット１１２は、分割された各領域に一対一で対応付けてもよいし、一つの評価値算出ユニット１１２が、複数の分割された領域に対応するようにしてもよい。また、評価値算出ユニット１１２は、例えばＦＰＧＡ（Field Programmable Gate Array）等のプログラム可能な装置を用いることによって容易に構成することができる。そして、図４（ｂ）に示すように、複数の評価値算出ユニット１１２Ｕｎが配列され、それぞれが分割された複数の領域に対応する。このような配列構造によれば、ロボットなどに対しても容易に実装化することができる。
【００４２】
状態設定用信号線３４は、評価値処理部１１４による評価値算出処理を実行可能状態又は実行不能状態に設定するための状態設定信号を評価値処理部１１４へと送信する。これにより、所望の評価値算出ユニット１１２について、評価値算出処理を行うタイミングを調整することができる。即ち、評価値算出処理を実行させる場合には、評価値算出ユニット１１２へと評価値算出処理を実行可能とする状態設定信号を送信し、評価値算出処理を実行させない場合には、評価値算出処理を実行不能とする状態設定信号を送信する。
【００４３】
評価値算出ユニット１１２が評価値算出処理を実行可能とする状態設定信号を受信した場合には、評価値処理部１１４は、近傍領域の評価値のうち最も小さい評価値と、その近傍領域から自領域までの幾何学的な距離に応じた移動コストに基づいて評価値を算出し、その結果を評価値記憶部３２及び３３に格納する。尚、評価値算出処理の詳細については後述する。
【００４４】
一方、評価値算出ユニット１１２が評価値算出処理を実行不能とする状態設定信号を受信した場合には、評価値処理部１１４は評価値算出処理を実行しない。例えば、環境に応じて、特定の評価値算出ユニット１１２の評価値算出処理を一定期間実行不能に設定することで、それら評価値算出ユニット１１２を待ち状態として、対応する領域における評価値を算出させないようにすることができる。一定期間経過後に評価値算出処理が実行可能となった場合に、それら待ち状態を経た評価値算出ユニット１１２によって算出される評価値は、既に算出された他の領域の評価値に比べて、待ち時間の分だけ相対的に大きな評価値が算出される。即ち、評価値算出処理において、待ち時間を評価値に反映させることで、特定の領域の評価値を大きくすることができる。従って、後述するように、評価値の大きな領域は経路として選択されにくくなるため、特定の領域を避けるように柔軟に経路を作成することができる。尚、状態設定用信号線３４は、評価値記憶部３２及び３３に格納された評価値算出結果を初期化するための初期化信号を送信するようにしてもよい。
【００４５】
経路決定部１１３は、評価値算出ユニット１１２によって算出された評価値に基づいて採用する経路を決定する。より詳細には、移動始点に対応する領域から移動終点に対応する領域に向けて、算出された評価値のうち最も小さい評価値を有する近傍領域を選択してゆく。選択された領域を通過する経路が、移動始点から移動終点へと至る最短経路となる。
【００４６】
続いて、本実施の形態１にかかる経路探索システム１の具体的な処理について、図５に示すフローチャート、及び図６、７に示すグリッドマップを用いて説明する。ここで、図６及び７に示すグリッドマップは、ロボットの目標軌道となる目標経路を、グリッド状に離散化された領域の集合として表現するものである。グリッド座標を利用するメリットは、最短経路探索を容易に実行できる点や、確実に目的地に到達できる経路を得ることができる点にある。グリッドマップに関する情報は、経路探索システム１を構成するコンピュータの経路探索記憶部１２に格納される。ここで、グリッドマップに関する情報には、各領域の座標情報、各領域の近傍領域を示す領域間の接続情報、及び各領域に関連付けられた評価値情報が含まれる。領域の評価値は、それぞれの領域に対応する評価値算出ユニット１１２によって算出される。
【００４７】
まず、領域分割部１１１により、移動領域が複数の領域に分割され、分割されたそれぞれの領域に対して評価値算出ユニット１１２が対応付けられる（Ｓ１０１）。ここでは、移動領域は、グリッド数と等しい数の領域に分割される。例えば、移動領域が２次元平面である場合には、それぞれ１０ｃｍ×１０ｃｍの広さを持つ離散的な複数の領域が分割生成される。分割された各領域に対して、それぞれの領域の評価値を算出する評価値算出ユニット１１２が対応付けられる。
【００４８】
次に、全ての評価値算出ユニット１１２に対して初期値を代入する（Ｓ１０２）。各領域の状態として、進入が禁止される禁止状態、評価値が未計算である未計算状態、及び評価値を計算済みである計算済み状態からなる３状態を想定する。それぞれの状態に対応する初期値を評価値算出ユニット１１２に代入する。評価値算出処理の開始段階であるＳ１０２においては、経路探索対象となる領域のうち、進入禁止領域以外の領域に対応する評価値算出ユニット１１２の評価値記憶部３２及び３３には、初期値として十分大きな値（例えば１．０×１０＾７）を代入する。進入禁止領域に対応する評価値算出ユニット１１２の評価値記憶部３２及び３３には、初期値として十分大きな値（例えば１．０×１０＾９）を代入する。ここでは、初期値として、後述する評価値算出処理によって算出される評価値を十分上回る値を採用して代入する。尚、領域の状態をこのような初期値を設定することで判断してもよいし、領域の状態を示す状態情報を各評価値算出ユニット１１２に格納するようにしてもよい。
【００４９】
次に、移動終点を指定して、その移動終点を含む領域に対応する評価値算出ユニット１１２について、その評価値記憶部３２又は評価値記憶部３３の少なくとも一方に評価値の最小値（例えば０）を代入する（Ｓ１０３）。以下では、評価値記憶部３２のみに評価値の最小値が代入されたものとして説明する。
【００５０】
次に、評価値算出処理を開始するための計算開始クロックＣ１を発生する（Ｓ１０４）。状態設定用信号線３４を介して、CPUのクロックに相当するパルスが各評価値算出ユニット１１２へと送信され、各評価値算出ユニット１１２においてＳ１０５乃至１０８における処理が実行される。またこのとき、評価値算出処理を実行させる評価値算出ユニット１１２に対しては、評価値算出処理を実行可能とする状態設定信号が送信され、評価値算出処理を実行させない評価値算出ユニット１１２に対しては、評価値算出処理を実行不能とする状態設定信号が送信される。
【００５１】
各評価値算出ユニット１１２は、対応する自領域の評価値及び近傍領域の評価値に基づいて、以下のようにして自領域の評価値を更新してゆく。まず、評価値記憶部３２に格納されている値について、自領域の評価値である自己評価値が、初期値から更新されているか否かを判定する（Ｓ１０５）。
【００５２】
ステップＳ１０５における判定の結果、自己評価値が初期値のままである場合（自領域の評価値が未計算である場合）には、近傍領域に対応する評価値算出ユニット１１２において、その評価値記憶部３２に格納されている値として、初期値ではない評価値が存在しているか否かを判定する（Ｓ１０６）。
【００５３】
ステップＳ１０６における判定の結果、近傍領域に初期値以外の値が存在する場合（近傍領域の評価値が計算済みである場合）には、近傍領域の評価値のうち最も小さい評価値と、その最小の評価値を持つ近傍領域から自領域までの幾何学的な距離に応じた移動コストに基づいて自己の領域の評価値を算出し、その結果を評価値記憶部３３に格納する（Ｓ１０７）。ここでは、以下の式に基づいて自己の領域の評価値を算出する。
自己評価値＝近傍領域の最小評価値＋近傍領域から自領域までの移動コスト
【００５４】
一方、ステップＳ１０５又はＳ１０６における判定の結果、評価値記憶部３２に格納されている自己評価値が初期値から更新されている場合、又は近傍領域に初期値以外の値が存在しない場合には、現在の自己評価値を更新せずにそのまま維持する（Ｓ１０８）。ここでは、自己評価値を維持する処理として、評価値記憶部３２に格納されている評価値を評価値記憶部３３へと出力して格納する。このように処理することで、現在の自己評価値を簡易な処理によって維持することができる。尚、評価値記憶部３２に格納されている評価値を評価値記憶部３３へと出力せずに、何も処理を実行しないようにしてもよい。
【００５５】
このように、全ての評価値算出ユニット１１２において、ステップＳ１０５乃至１０８における評価値算出処理の実行を、それぞれ評価値記憶部３２に格納された評価値に基づいて判定し、評価値算出結果を、それぞれ評価値記憶部３２とは異なる評価値記憶部３３に出力する。これにより、１回の評価値算出処理の結果、評価値算出結果の干渉を防ぐことができると共に、１近傍を越えて評価値が算出されないよう制限することができるため、１近傍領域に含まれる領域の評価値のみを算出させることができる。従って、複数の評価値算出ユニット１１２による評価値算出処理のタイミングを同期させることができる。尚、次のクロックＣ２によってステップＳ１０５乃至１０８における処理が実行される場合には、ステップＳ１０５乃至Ｓ１０８の処理において、評価値記憶部３３に格納されている評価値に基づいて評価値算出処理が実行され、その結果が評価値記憶部３２に格納される。更には、クロックＣ３によってＳ１０５乃至１０８における処理が実行される場合には、評価値記憶部３２に格納されている評価値に基づいて評価値算出処理が実行され、その結果が評価値記憶部３３に格納される。
【００５６】
移動始点を含む領域に対応する評価値算出ユニット１１２について、その評価値記憶部３２又は評価値記憶部３３のいずれか一方に初期値ではない評価値が存在しているか否かを判定する（Ｓ１０９）。ステップＳ１０９における判定の結果、評価値が存在していない場合には、移動始点を含む領域の評価値は未だに算出されていない未計算状態であるため、ステップＳ１０４へと戻り再び各評価値算出ユニット１１２により領域の評価値算出処理を実行する。
【００５７】
一方、ステップＳ１０９における判定の結果、移動始点に評価値が存在している場合には、移動始点を含む領域の評価値が計算済みの状態となったことから、評価値算出処理を終了して、ステップＳ１１０以降の経路決定処理へと進む。
【００５８】
尚、ステップＳ１０９における評価値算出処理を終了させる条件としては、全ての領域に対応する評価値が変化しなくなった場合に処理を終了させるようにしてもよい。即ち、全ての評価値算出ユニット１１２において、評価値記憶部３２及び３３に格納された評価値が同じ値のまま変化しなくなった場合に処理を終了させることができる。また、このような終了条件をステップＳ１０９における終了条件に加えて判定させるように構成することで、移動始点から移動終点までの経路が存在しない場合であっても評価値算出処理を終了させることができる。
【００５９】
続いて、評価値算出処理を終了した後、経路決定部１１３は、分割された各領域の評価値に基づいて、移動始点を含む領域から開始し、その近傍領域において最小の評価値を持つ領域を経路として選択する（Ｓ１１０）。そして、ステップＳ１１０において選択した領域が、移動終点を含む領域であるか否かを判定する（Ｓ１１１）。ステップＳ１１１における判定の結果、選択された領域が移動終点を含む領域に到達していない場合には、ステップＳ１１０へと戻り、次の経路として選択した領域の近傍領域を選択する。一方、ステップＳ１１１における判定の結果、選択された領域が移動終点を含む領域に到達した場合には、ステップＳ１１０において選択された領域の系列を経路として出力し、経路決定処理を終了する（Ｓ１１１）。このように、移動始点に対応する領域から移動終点に対応する領域に向けて、領域の評価値のうち最も小さい評価値を有する近傍領域を順次選択してゆくことで、選択された領域を通過する経路を最短経路として決定することができる。
【００６０】
図６は、評価値算出処理を説明するための一例を示す図である。図６では、移動領域を横１６個、縦１３個の領域に分割し、各領域の近傍領域を各領域に隣接した前後左右４方向に隣接する領域とした。図において斜線領域は進入禁止領域を示し、外周上の領域は経路探索対象外である領域を示す。図に示す領域Ｇを移動終点とし、領域Ｇの初期値を０に設定した場合に、評価値算出ユニット１１２による評価値算出結果を各領域に示す。尚、ここでは、近傍領域から自領域までの移動コストの値を５とした。分割された２０８個の領域のうち、３９個の領域が進入禁止領域であり、１６９個の領域が経路探索対象領域である。従来手法では、領域の個数相当の計算ステップが必要となるため、計１６９回の計算が必要となる。一方、本実施の形態１にかかる経路探索システム１によれば、各評価値算出ユニット１１２がそれぞれ並列に評価値を算出するため、計２２回の計算によって評価値を算出することができる。従って、従来手法と比較して、凡そ８分の１の計算時間によって経路探索のための評価値算出処理を実行することができ、移動領域が広くなる程、計算時間短縮による効果は顕著なものとなる。
【００６１】
図７は、経路決定処理を説明するための一例を示す図である。図７では、図６に示した評価値算出後の領域について、図に示す領域Ｓを移動始点とし、移動始点Ｓから移動終点Ｇまでの経路決定処理の結果を示している。移動始点Ｓから移動終点Ｇへと向かって選択された領域の系列について、それら領域を通過する白抜き矢印が移動始点Ｓから移動終点Ｇまでの最短経路を示している（同時に、移動終点Ｇから移動始点Ｓまでの最短経路を意味する）。また、移動始点Ｓにおける評価値１１０は、移動始点Ｓから移動終点Ｇまでに要する移動コストの総コストを意味している。
【００６２】
以上に説明したように、本実施の形態１にかかる経路探索システム１は、移動領域を複数の領域に分割することで、経路探索のための移動コストを領域間の幾何学的な距離によって表現することができる。そして、複数の評価値算出ユニット１１２が、このような幾何学的な距離と近傍領域の評価値とに基づいて、それぞれの領域における評価値算出処理を並列に実行することで、逐次的に各領域の評価値を算出する場合に比べて、経路探索に要する計算コストを大きく削減することができる。
【００６３】
図８は、本実施の形態１にかかる経路探索システム１（発明手法）による計算時間短縮効果を説明するためのグラフを示す図である。図では、一辺Ｌ個のグリッドからなるｎ次元正立方体探索空間において、その対角要素間の経路（最長経路）を探索するために必要な計算ステップの見積もり（最大の計算ステップ数）を示す。Ｌ＝正立方体の一辺のグリッド数[ｇｒｉｄ]、ｎ＝探索空間の次元数[１]とした場合に、経路探索に要する計算の繰り返し回数（ｓｔｅｐｓ）は以下の式に基づいて見積もることができる。
従来手法：ｓｔｅｐｓ＝Ｌｎ
発明手法：ｓｔｅｐｓ＝Ｌ×√ｎ
例えば、一辺が２０[ｇｒｉｄ]の７次元正立方体探索空間内において最短経路探索を行った場合、従来の経路探索手法と、本実施の形態１にかかる経路探索システム１による計算ステップとを比較すると、経路探索システム１は、従来手法に対しておよそ１億分の１のステップ数によって経路探索を実行することができる。
【００６４】
また、本実施の形態１にかかる経路探索システム１では、近傍とする領域を変更することで、評価値を算出するタイミングを環境に応じて調整することができる。例えば、接続関係をより広範囲の領域間に広げ、遠方に存在する領域を近傍領域とすることで、遠方の領域に基づいて自領域の評価値を算出することができる。即ち、接続関係を有する遠方の領域における評価値が算出された場合には、次のタイミングにおいて自領域の評価値を算出することができるため、直接隣接する領域を近傍領域とした場合と比べて、評価値算出処理をより早くに実行させることができる。従って、経路探索処理をより短時間で実行させることができるため、環境において動的な障害物が存在する場合であっても効果的に障害物に対処することが可能となる。
【００６５】
発明の実施の形態２．
本実施の形態２にかかる経路探索システムは、移動領域内に複数の移動終点を指定した場合には、当該移動終点を含む領域のそれぞれから評価値算出処理を開始し、当該評価値算出処理結果に基づいて任意の移動始点より経路を探索する。評価値算出部は、いずれかの移動始点を含む領域において評価値が算出された場合に、評価値算出処理を終了させることができる。経路決定部は、移動領域内の任意の領域を移動始点として指定し、算出された領域の評価値に基づいて、移動始点に対応する領域から、算出された評価値のうち最も小さい評価値を有する近傍領域を選択してゆく。このとき、複数の移動終点に対応する領域のうち、当該移動始点から最短の移動コストで到達可能な移動終点に向けて経路を決定することができる。尚、以下で説明しない構成及び処理に関しては、本実施の形態１における図１乃至図５で説明した構成及び処理と基本的に同一である。
【００６６】
図９は、複数の移動終点が指定された場合に、評価値算出処理を説明するための一例を示す図である。図９では、移動領域を横１６個、縦１３個の領域に分割し、近傍領域は各領域の前後左右方向に直接隣接する領域とした。図において斜線領域は進入禁止領域を示し、外周上の領域は経路探索対象外である探索領域外を示す。図に示す領域Ｇ１及びＧ２を移動終点とし、領域Ｇ１及びＧ２の初期値を０に設定した場合に、評価値算出ユニット１１２による評価値算出結果を各領域に示す。尚、ここでは近傍領域から自領域までの移動コストの値は５とした。また、複数の移動終点は上述した図５のステップＳ１０３において、複数の移動終点を含む領域に対応する評価値算出ユニット１１２について、その評価値記憶部３２又は評価値記憶部３３の少なくとも一方に評価値の最小値（例えば０）を代入すればよい。
【００６７】
図１０は、複数の移動終点が指定された場合に、経路決定処理を説明するための一例を示す図である。図１０では、図９に示した評価値算出後の領域について、図に示す領域Ｓ１を移動始点とし、移動始点Ｓ１から経路決定処理を実行した。その結果、決定された経路は、移動始点Ｓ１から移動終点Ｇ１へと到達する経路であった。また、移動始点Ｓ１における評価値６０は、移動始点Ｓ１から移動終点Ｇ１までに要する移動コストの総コストを意味している。これにより、移動終点Ｇ２に比べて、移動終点Ｇ１へと到達する経路長のほうがより短いものであり、移動始点Ｓ１からは、移動終点Ｇ１へと移動するほうがより少ない移動コストで済むことを示している。
【００６８】
このように、複数の領域について、評価値算出ユニット１１２が、それぞれ並列に評価値算出処理を実行すると共に、近傍領域における評価値の最小値及び自領域までの移動コストに基づいて評価値算出処理を実行する。このため、各領域における評価値は、複数の移動終点からの移動コストの総和が最小となる評価値が算出され、最も移動コストの少ない移動終点までの経路を探索することができる。従って、このような評価値によれば、複数の移動終点に対して同時に最適な経路を探索することができる。例えば、移動領域内に複数のゴミ箱が存在し、それらゴミ箱を含む領域を移動終点とした場合、ロボットは現在位置である移動始点から、移動コストが最小となる移動終点を選択し、その移動終点へと到達する最短経路を移動することが好ましい。また、マニピュレータによる軌道計画を行う場合には、対象物を把持する際に最も把持しやすい位置・姿勢へと至るマニュピレータの軌道を計画することが好ましい。そのため、現在の位置・姿勢から、目標となる位置・姿勢へと到達する最適な軌道計画が必要となるが、そのような目標位置・姿勢は複数存在するものと考えられる。従って、このような場合においても本実施の形態２にかかる経路探索システムを適用することによって、複数の移動終点に対して、同時に最適な移動経路及び軌道を作成することができる。
【００６９】
また、本実施の形態２にかかる経路探索システムによれば、複数の移動終点に対して同時に最適な経路を探索することができるため、複数の領域からなる領域範囲を、移動終点エリアとして指定することもできる。これにより、ひとつの領域のみを正確に移動終点として指定する必要がなく、移動終点として指定したい凡その範囲を指定するだけで経路を探索することができ、環境に応じてより柔軟に経路探索を実行させることができる。尚、複数の移動終点に対して、従来手法を用いてそれぞれの移動終点への経路を探索した場合には、算出される最短経路は同じ経路長となるものの、従来手法ではそれぞれの移動終点に対して別々に経路を探索するため、移動終点の個数に応じた計算時間を要する。一方、本実施の形態２にかかる経路探索システムによれば、それぞれの評価値算出ユニット１１２が並列に評価値を算出してゆくため、移動終点の個数に応じて計算時間が増加することはなく、移動終点の個数が増加した場合であっても、従来手法と比較してより高速に経路探索処理を実行することができる。
【００７０】
発明の実施の形態３．
本実施の形態３にかかる経路探索システムは、移動領域内に存在する移動始点より移動を開始し、移動領域内に存在する移動終点に到達する自律移動体の移動経路を探索する経路探索システムであって、移動領域を複数の領域に分割する領域分割部と、領域分割部により分割された複数の領域に対応し、それぞれの領域の評価値を算出する評価値算出部と、評価値算出部によって算出された評価値に基づいて経路を決定する経路決定部とを備え、評価値算出部が、近傍領域の評価値と、その近傍領域から自領域までの移動コストに基づいて評価値を算出するものである。本実施の形態３にかかる経路探索システムでは、上述した実施の形態とは異なり、複数の評価値算出ユニットを用いずに、１つ又は少数の演算処理装置（ＣＰＵなど）を用いて各領域における評価値算出処理を逐次的に実行する。尚、以下で説明しない構成及び処理に関しては、本実施の形態１における図１乃至図５で説明した構成及び処理と基本的に同一である。
【００７１】
本実施の形態３にかかる経路探索システムは、例えば、ロボットに搭載されたコンピュータやロボットとは別に設けられたコンピュータにより実現される。このコンピュータは、例えば、中央処理装置（ＣＰＵ）、ＲＯＭ、ＲＡＭ、ハードディスク等の補助記憶装置、ＣＤ−ＲＯＭ等の可搬型記憶媒体が挿入される記憶媒体駆動装置、入力手段や出力手段を備えている。ＲＯＭ、補助記憶装置、可搬型記憶媒体等の記憶媒体には、オペレーティングシステムと協働してＣＰＵ等に命令を与え、アプリケーションプログラムを記録することができる。アプリケーションプログラムはＲＡＭにロードされることによって実行される。このアプリケーションプログラムは、本発明にかかる経路探索システムを実現する特有の経路探索プログラムを含む。経路探索システムによる経路探索は、中央処理装置がアプリケーションプログラムをＲＡＭ上に展開した上で当該アプリケーションプログラムに従った処理を補助記憶装置に格納されたデータを読み出し、また格納を行なうことにより、実行される。
【００７２】
本実施の形態３にかかる経路探索システムによれば、従来手法と同様に１つ又は少数の演算処理装置（ＣＰＵなど）を有するコンピュータに容易に実装することできる。また、１つ又は少数の演算処理装置（ＣＰＵなど）を用いて評価値算出処理を実行するため、計算時間は従来手法と変わらないものの、複数の移動終点に対して同時に最短経路を探索することができる。
【００７３】
その他の実施の形態．
上述した実施の形態では、指定された移動終点から評価値算出処理を開始して、経路決定処理においては任意の移動始点から経路を決定するものとして説明したが本発明はこれに限定されない。例えば、指定された移動始点から評価値算出処理を開始して、経路決定処理においては任意の移動終点から経路を決定するものとしてもよい。また、本発明によれば移動領域内の指定された２領域間の最短経路を算出することができるため、移動始点及び移動終点として指定する領域数が、多対一、一対多、多対多である場合においても本発明を応用することができる。
また、上述した実施の形態では、移動領域が２次元である場合の例を説明したが、移動領域が例えばｘ、ｙ、ｚ軸によって規定される３次元空間の場合でもよく、さらに、ロボットの姿勢（１次元）を併せて４次元の探索空間とした場合であっても本発明を適用することができる。
【００７４】
さらにまた、上述した実施の形態では、移動手段として車輪などを有するロボットに本発明を適用した一例を示したが、これに限定されず、ロボットは足を有し、自律歩行可能な移動ロボットであってもよい。
【００７５】
また、本発明は上述した実施の形態のみに限定されるものではなく、既に述べた本発明の要旨を逸脱しない範囲において種々の変更が可能であることは勿論である。
【図面の簡単な説明】
【００７６】
【図１】本発明の実施の形態にかかる経路探索システムの構成を示す構成図である。
【図２】本発明の実施の形態にかかる移動領域を分割した複数の領域を示す概念図である。
【図３】本発明の実施の形態にかかる離散化された領域間の接続関係を説明するための概念図である。
【図４】本発明の実施の形態にかかる評価値算出ユニットの構成を示す概念図である。
【図５】本発明の実施の形態にかかる経路探索システムによる経路探索処理を示すフローチャートである。
【図６】本発明の実施の形態にかかる経路探索システムによる評価値算出処理を説明するための一例を示す図である。
【図７】本発明の実施の形態にかかる経路探索システムによる経路決定処理を説明するための一例を示す図である。
【図８】本発明の実施の形態にかかる経路探索システムによる計算時間短縮効果を説明するためのグラフを示す図である
【図９】本発明の実施の形態にかかる経路探索システムによる評価値算出処理を説明するための一例を示す図である。
【図１０】本発明の実施の形態にかかる経路探索システムによる経路決定処理を説明するための一例を示す図である。
【符号の説明】
【００７７】
１  経路探索システム、
１１  経路探索処理部、１２  経路探索記憶部、
１１１  領域分割部、１１２  評価値算出ユニット、１１３  経路決定部、
１１４  評価値処理部、
３２  評価値記憶部、３３  評価値記憶部、３４  状態設定用信号線、
Ｃｎ  領域、Ｇ  移動終点、Ｓ  移動始点
【図１】
0004985163.tif 000002
【図２】
0004985163.tif 000003
【図３】
0004985163.tif 000004
【図４】
0004985163.tif 000005
【図５】
0004985163.tif 000006
【図６】
0004985163.tif 000007
【図７】
0004985163.tif 000008
【図８】
0004985163.tif 000009
【図９】
0004985163.tif 000010
【図１０】
0004985163.tif 000011