経路探索装置、経路探索方法、及び自律移動体
【課題】並列演算を用いて経路探索を行う際に、経路情報を効率的に取得すること。
【解決手段】本発明に係る経路探索装置１は、並列演算部１１２と、コントローラ部１１１と、を備える。並列演算部１１２は並列演算により領域の評価値を算出する。並列演算器１１２＿ｎは、各領域の評価値に基づいて近傍に存在する領域から一の選択領域を選択する領域選択部１１４、自領域から選択領域への方向を示す経路方向情報を生成する経路方向情報生成部１１５、経路方向情報を受信する受信部１１６、選択領域の並列演算器１１２＿ｎに経路方向情報を送信した後に、生成した経路方向情報を送信する送信部１１８を備える。コントローラ部１１１は、移動終点の並列演算器１１２＿ｎから経路方向情報の送信を最初に開始させた後に、並列演算部１１２内で伝播した経路方向情報の系列を移動始点の並列演算器１１２＿ｎから取得する。
【解決手段】本発明に係る経路探索装置１は、並列演算部１１２と、コントローラ部１１１と、を備える。並列演算部１１２は並列演算により領域の評価値を算出する。並列演算器１１２＿ｎは、各領域の評価値に基づいて近傍に存在する領域から一の選択領域を選択する領域選択部１１４、自領域から選択領域への方向を示す経路方向情報を生成する経路方向情報生成部１１５、経路方向情報を受信する受信部１１６、選択領域の並列演算器１１２＿ｎに経路方向情報を送信した後に、生成した経路方向情報を送信する送信部１１８を備える。コントローラ部１１１は、移動終点の並列演算器１１２＿ｎから経路方向情報の送信を最初に開始させた後に、並列演算部１１２内で伝播した経路方向情報の系列を移動始点の並列演算器１１２＿ｎから取得する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は経路探索装置、経路探索方法、及び自律移動体に関し、特に、並列演算を用いて経路探索を行う際に、探索した経路情報を効率的に取得可能な経路探索装置、経路探索方法、及び自律移動体に関する。
【背景技術】
【０００２】
近年、始点から終点へと至る経路を探索し、その探索した経路に従って自律的に移動する自律移動体が開発されている。経路を探索する手法としては、Ａ＊（エースター）アルゴリズムやダイキストラ法を用いる手法が良く知られている。
【０００３】
このような経路探索手法は、通常、ノイマン型コンピュータを用いて実現される。ノイマン型コンピュータは、互いに独立したユニットとしてのメモリ及び演算部を搭載し、メモリ上に経路探索に係る計算過程を保存しながら処理を行う。すなわち、演算部はメモリへとアクセスを行う際に、経路探索処理に係る処理データをメモリとの間で逐次通信する必要がある。
【０００４】
一方、ノイマン型コンピュータを用いた場合と比較して、相互に接続された複数の演算器を用いて並列計算を行うことで、高速に経路探索を行う手法が提案されている（例えば、特許文献１乃至３）。
【０００５】
特許文献１には、並列計算機を用いた巡回セールスマン問題解法処理システムが開示されている。特許文献１に開示される解法処理システムでは、巡回対象の都市に対応させた各セルは、メッセージを受信した際にセル情報を追加し、ネットワークを介して隣接セルへメッセージを送信するメッセージ送信手段を備えている。また、最初にメッセージを送信するスタートセルは、受信したメッセージが全ての都市を経由して一番早くスタートセルに戻ってきたメッセージを検出すると、そのメッセージが最短経路を経由したメッセージであるとして経路探索処理を終了させるメッセージ監視手段を備えている。
【０００６】
特許文献２には、巡回セールスマン問題処理装置が開示されている。特許文献２では、並列計算による巡回セールスマン問題処理装置において、都市座標をセル数に応じて分割・割り当てる全体問題処理手段と、階層化した都市データを各セルに割り当てた部分問題を処理して解を求める部分問題処理手段を有する。
【０００７】
特許文献３には、経路探索システムが開示されている。特許文献４に開示される経路探索システムは、移動領域を複数の領域に分割する領域分割部と、分割された複数の領域に対応し、それぞれの領域の評価値を算出する複数の評価値算出部と、算出された評価値に基づいて経路を決定する経路決定部とを備えている。評価値算出部は、近傍に存在する領域の評価値と、その近傍領域から自領域までの移動コストに基づいて評価値を算出する評価値処理部を有している。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】特開平８−２７８８８９号公報
【特許文献２】特開平８−２８６９２０号公報
【特許文献３】特開２００９−１９９３２号公報
【発明の概要】
【発明が解決しようとする課題】
【０００９】
しかしながら、逐次的に処理を行うノイマン型コンピュータを用いて経路探索を行う場合には、演算部がメインメモリへと頻繁にアクセスする必要があり、経路探索自体に要する処理ではなく、メモリへのデータ参照のために多くの計算コストを消費するという問題がある。ノイマン型のコンピュータでは、メモリ及び演算部というそれぞれ独立したユニット構成であるために、両者間のアクセスが発生する。このため、メインメモリへのアクセス速度が遅い場合や、メインメモリへのアクセス頻度が多くなる場合、さらには、メインメモリに保持するデータ量が多くなる場合などには、コンピュータのプロセッサ自体の計算速度に比してメモリアクセス速度が低速なものとなり、メモリアクセス速度が、経路探索処理全体に係る処理能力の制約条件となってしまう。
【００１０】
また、特許文献１及び２に開示される技術では、全都市を一巡する経路のうちで最短な経路を探索する巡回セールスマン問題を対象とするものである。このため、特許文献１及び２に開示される経路探索手法を用いては、任意の二地点間で最適な経路を探索することはできない。さらに、例えば特許文献１に開示される巡回セールスマン問題解法処理システムでは、各セルが当該セルまでの経路探索の履歴を保持して、保持する履歴情報をメッセージとして隣接セルに送信する。このため、巡回対象となる都市数の増加に伴って保持及び送信するメッセージ量が増加し、システム全体の処理が遅延するという問題がある。
【００１１】
特許文献３に開示される技術では、各領域の評価値処理部がそれぞれ評価値を算出することで、経路探索空間が広大な場合においても、高速に最適な経路を探索することができる。しかし、特許文献３に開示される技術では、経路探索に係る処理のうち、各領域の評価値を高速に算出することは可能であるが、算出した評価値に基づいて決定される経路情報を効率よく取得することができないという問題がある。具体的には、特許文献３に開示される技術では、並列演算を行う各評価値算出ユニットにより各領域の評価値を算出した後に、移動始点を含む領域から開始して、隣接する近傍領域において最小の評価値を持つ領域を経路として選択していく（段落００５９など参照。）。ここで、選択された領域の系列である経路情報を取得するためには、経路上の全ての領域に逐次的にアクセスを行う必要があり、さらに、各領域にアクセスを行う都度、近傍領域の選択処理を行う必要があるため、効率よく経路情報を取得することができない。
【００１２】
従って、本発明は、互いに接続された複数の並列演算器から構成される並列演算部を用いて経路探索を行う技術において、並列演算部を統括する上位のコントローラ部が、探索した経路情報を効率的に取得することができる経路探索装置、経路探索方法、及び自律移動体を提供することを目的とする。
【課題を解決するための手段】
【００１３】
本発明に係る経路探索装置は、経路探索領域内に存在する第１の地点から第２の地点に到達する経路を探索する経路探索装置であって、前記経路探索領域が複数の領域に分割され、分割されたそれぞれの領域に対応する複数の並列演算器から構成される並列演算部と、前記並列演算部を統括するコントローラ部と、を備え、前記並列演算部は、前記複数の並列演算器が並列演算することで、対応するそれぞれの領域の評価値を算出し、前記並列演算器は、前記並列演算することで算出した各領域の評価値に基づいて、近傍に存在する領域から一の選択領域を選択する領域選択手段と、自身に対応する領域から前記選択領域への方向を示す経路方向情報を生成する経路方向情報生成手段と、他の前記並列演算器から送信された経路方向情報を受信する受信手段と、前記選択領域に対応する前記並列演算器に対して、前記受信手段で受信した前記経路方向情報を送信した後に、前記経路方向情報生成手段で生成した前記経路方向情報を送信する送信手段と、を備え、前記コントローラ部は、
前記第２の地点を含む領域に対応する第２の並列演算器から前記経路方向情報の送信を最初に開始させた後に、前記並列演算部内で伝播した前記経路方向情報の系列を、前記第１の地点を含む領域に対応する第１の並列演算器から取得することで、前記経路を探索するものである。
【００１４】
このように、各並列演算器間で局所的に経路方向情報を送受信することで、並列演算部内において、第２の地点の並列演算器から第１の地点の並列演算器へと向けて経路方向情報を伝播することができるため、上位のコントローラ部は、第１の地点の並列演算器のみにアクセスすることで、経路である経路方向情報の系列を取得することができる。従って、並列演算を用いて経路探索を行う際に、探索した経路情報を効率的に取得することができる。
【００１５】
また、前記並列演算器は、前記受信手段で受信した他の前記並列演算器から送信された経路方向情報を保持する受信バッファと、前記受信バッファに保持した前記経路方向情報又は前記経路方向情報生成手段で生成した前記経路方向情報を送信するために保持する送信バッファと、を更に備え、前記送信手段は、他の前記並列演算器から送信された経路方向情報を受信した場合には、前記受信バッファに保持した前記経路方向情報を、前記送信バッファを介して前記選択領域に対応する前記並列演算器に送信し、他の前記並列演算器から送信された経路方向情報を所定の期間受信しなかった場合には、前記経路方向情報生成手段で生成した前記経路方向情報を、前記送信バッファを介して前記選択領域に対応する前記並列演算器に送信するようにしてもよい。このように、各並列演算器は、他の並列演算器から受信した経路方向情報の転送と、自ら生成した経路方向情報を送信するため、受信バッファには、経路方向情報の系列全体を保持せずに、受信した経路方向情報のみを保持すればよい。
【００１６】
さらにまた、前記領域選択手段は、前記並列演算することで算出した各領域の評価値に基づいて、近傍に存在する領域から、前記第１の地点を含む領域により近づく方向の一の選択領域を選択するようにしてもよい。
【００１７】
また、前記並列演算器は、近傍に存在する領域の評価値と、当該近傍領域から自身に対応する領域までの移動コストに基づいて評価値を算出する評価値処理部を更に備えるようにしてもよい。
【００１８】
本発明に係る経路探索方法は、経路探索領域が複数の領域に分割され、分割されたそれぞれの領域に対応する複数の並列演算器から構成される並列演算部と、前記並列演算部を統括するコントローラ部と、を備える移動体が、前記経路探索領域内に存在する第１の地点から第２の地点に到達する経路を探索する経路探索方法であって、前記並列演算部が、前記複数の並列演算器が並列演算することで、対応するそれぞれの領域の評価値を算出し、前記並列演算器が、前記並列演算することで算出した各領域の評価値に基づいて、近傍に存在する領域から一の選択領域を選択する領域選択ステップと、自身に対応する領域から前記選択領域への方向を示す経路方向情報を生成する経路方向情報生成ステップと、他の前記並列演算器から送信された経路方向情報を受信する受信ステップと、前記選択領域に対応する前記並列演算器に対して、前記受信した前記経路方向情報を送信した後に、前記生成した前記経路方向情報を送信する送信ステップと、を有し、前記コントローラ部が、前記第２の地点を含む領域に対応する第２の並列演算器から前記経路方向情報の送信を最初に開始させた後に、前記並列演算部内で伝播した前記経路方向情報の系列を、前記第１の地点を含む領域に対応する第１の並列演算器から取得することで、前記経路を探索するものである。
【００１９】
本発明に係る自律移動体は、経路探索領域内に存在する第１の地点から第２の地点に到達する経路を探索する自律移動体であって、前記経路探索領域が複数の領域に分割され、分割されたそれぞれの領域に対応する複数の並列演算器から構成される並列演算部と、前記並列演算部を統括するコントローラ部と、を備え、前記並列演算部は、近傍に存在する領域の評価値と、当該近傍領域から自身に対応する領域までの移動コストに基づいて、対応するそれぞれの領域の評価値を算出し、前記並列演算器は、前記並列演算することで算出した各領域の評価値に基づいて、近傍に存在する領域のうち最も小さい評価値を有する一の選択領域を選択する領域選択部と、自身に対応する領域から前記選択領域への方向を示す経路方向情報を生成する経路方向情報生成部と、他の前記並列演算器から送信された経路方向情報を受信する受信部と、前記選択領域に対応する前記並列演算器に対して、前記受信部で受信した前記経路方向情報を送信した後に、前記経路方向情報生成部で生成した前記経路方向情報を送信する送信部と、を備え、前記コントローラ部は、前記第２の地点を含む領域に対応する第２の並列演算器から前記経路方向情報の送信を最初に開始させた後に、前記並列演算部内で伝播した前記経路方向情報の系列を、前記第１の地点を含む領域に対応する第１の並列演算器から取得することで、前記経路を探索するものである。
【発明の効果】
【００２０】
本発明によれば、並列演算を用いて経路探索を行う際に、探索した経路情報を効率的に取得可能な経路探索装置、経路探索方法、及び自律移動体を提供することができる。
【図面の簡単な説明】
【００２１】
【図１】本発明の実施の形態１に係る経路探索装置の構成を示すブロック図である。
【図２】本発明の実施の形態１に係る経路探索領域を分割した複数の領域を示す概念図である。
【図３】本発明の実施の形態１に係る離散化された領域間の接続関係を説明するための概念図である。
【図４】本発明の実施の形態１に係る並列演算器の構成を示す概念図である。
【図５】本発明の実施の形態１に係る経路探索装置による経路探索処理の全体構成を示すフローチャートである。
【図６】本発明の実施の形態１に係る経路探索装置領域の評価値の算出処理を示すフローチャートである。
【図７】本発明の実施の形態１に係る経路探索装置による評価値算出処理の一例を説明するための図である。
【図８】本発明の実施の形態１に係る経路探索装置による経路探索結果の一例を説明するための図である。
【図９】本発明の実施の形態１に係る並列演算器における処理を説明するためのフローチャート図である。
【図１０】本発明の実施の形態１に係る経路探索装置の並列演算器間で送受信されるデータ構造の一例を示す図である。
【図１１】本発明の実施の形態１に係る経路探索装置による経路方向情報を説明するための図である。
【図１２】本発明の実施の形態１に係る経路探索装置による経路方向情報の伝播の様子を説明するための図である。
【図１３】本発明の実施の形態１に係る経路探索装置による経路方向情報の伝播の様子を説明するための図である。
【発明を実施するための形態】
【００２２】
実施の形態１．
本実施の形態１では、自律移動体としてのロボットに経路探索機能を搭載した場合を例に説明する。ロボットは、例えば、それぞれ独立して回転制御される二つの車輪を備えたものでもよく、２輪よりも多い、例えば４輪走行のロボットや、１輪走行のロボット、２足歩行・４足歩行のロボットであってもよい。また、ロボットに限らず、２輪走行や４輪走行の車両にも適用できる。ロボットは、障害物を検出するセンサやカメラを備え、検出された障害物に応じて、これを避けるように経路探索を行なうようにしてもよい。
【００２３】
本実施の形態１に係るロボットが備える経路探索機能によれば、並列演算することで経路探索処理を行う並列演算部内において、各並列演算器間で局所的に経路方向情報を送受信し、第２の地点の並列演算器から第１の地点の並列演算器へと向けて経路方向情報を伝播することができる。このため、並列演算部を統括する上位のコントローラ部は、第１の地点の並列演算器のみにアクセスすることで、経路である経路方向情報の系列を取得することができる。従って、並列演算を用いて経路探索を行う際に、探索した経路情報を効率的に取得することができる。尚、以下では、第１の地点をロボットが移動を開始する移動始点とし、第２の地点を移動目標地点である移動終点として説明するが、本実施の形態１に係る経路探索装置は任意の二点間の最適な経路を探索するものであり、第１の地点を移動終点とし、第２の地点を移動始点としてもよい。以下、図面を参照して本発明の実施の形態１について説明する。
【００２４】
図１は、本実施の形態１に係る経路探索装置の概略構成を示すブロック図である。図１に示されるように、経路探索装置１は、経路探索処理部１１と経路探索記憶部１２により構成されている。経路探索処理部１１は、コントローラ部１１１と、並列演算部１１２から構成されている。並列演算部１１２は、複数の並列演算器１１２＿１、１１２＿２、・・・（以下、単に並列演算器１１２＿ｎと称する場合がある。）を備えている。並列演算器１１２＿ｎは、それぞれ物理的に独立した演算器であって、後述する評価値算出処理などを並列に実行する。
【００２５】
経路探索記憶部１２には、ロボットが移動する経路探索領域全体の形状に、略一定間隔ｄ（例えば１０ｃｍ）に配置された格子点を結ぶグリッド線を仮想的に描写することで得られるグリッドマップが記憶されている。ロボットは、ＧＰＳ等から得られた位置情報を、このグリッドマップ上における自己の位置に置き換えて、グリッドマップ上における自己位置を認識する。グリッドマップ上において、ロボットの自己位置に相当する場所、および目的地である移動終点、及び移動終点におけるロボットの移動方向が特定される。ロボットは、グリッドマップ上において特定された自己位置を移動始点から、目的地である移動終点までの経路を探索し、探索した経路に従って移動を行う。
【００２６】
コントローラ部１１１は、並列演算部１１２を統括して制御処理を行い、経路方向情報の系列からなる経路を、並列演算部１１２から取得する。尚、コントローラ部１１１による並列演算部１１２の制御処理の詳細については後述する。
【００２７】
また、コントローラ部１１１は、ロボットが移動する経路探索領域を格子状の領域に分割する分割処理を行う。ここでは、上述の略一定間隔ｄ（例えば１０ｃｍ）に配置された格子点を囲む複数の領域に分割する。図２は、経路探索領域を分割して、離散化された複数の領域Ｃｎを示す概念図である。尚、コントローラ部１１１による分割方法はこれに限定されない。例えば、上述の分割後の領域よりも大きな領域へと分割することで、経路探索に要する時間をより短縮することができる。
【００２８】
そして、コントローラ部１１１は、分割した領域間の接続関係を定める。以下では、注目する領域に接続する領域を近傍領域と称する。図３は、離散化された領域間の接続関係を説明するための概念図である。図３（ａ）では、注目する領域Ｃ０に対して、隣接領域Ｃ１乃至Ｃ８を近傍領域として定めるものである。また、図３（ｂ）では、注目する領域Ｃ０に対して、隣接領域Ｃ１乃至Ｃ８に加えて、さらに領域Ｃ９乃至Ｃ１６を近傍領域として定めるものである。このように、自領域に対して隣接した領域を越えた領域を近傍領域として設定可能とすることで、自領域及びそれら近傍領域間を通過する経路を作成することができる。このようにすれば、移動始点から移動終点へと至る経路の角度分解能を柔軟に設定することができ、より滑らかな経路を作成することができる。
【００２９】
並列演算部１１２は、複数の並列演算器１１２＿１、１１２＿２、・・・から構成される。複数の並列演算器１１２＿１、１１２＿２、・・・は、コントローラ部１１１により分割された各領域にそれぞれ対応する。図４は、並列演算器１１２＿ｎの構成を示す概念図である。図４（ａ）に示すように、並列演算器１１２＿ｎには、少なくとも２つの評価値記憶部３２＿ｎ及び評価値記憶部３３＿ｎと、状態設定用信号線３４＿ｎとが接続されている。
【００３０】
尚、複数の並列演算器１１２＿１、１１２＿２、・・・はいずれも同一の構成を有しており、簡易な構成により経路探索装置１を構成することができる。各並列演算器１１２＿ｎは、分割された各領域に一対一で対応付けてもよいし、一つの並列演算器１１２＿ｎが、複数の分割された領域に対応するようにしてもよい。また、並列演算器１１２＿ｎは、例えばＦＰＧＡ（Field Programmable Gate Array）等のプログラム可能な装置を用いることによって容易に構成することができる。そして、図４（ｂ）に示すように、複数の並列演算器１１２＿ｎが配列され、それぞれが分割された複数の領域に対応する。このような配列構造によれば、ロボットなどに対しても容易に実装化することができる。
【００３１】
状態設定用信号線３４＿ｎは、コントローラ部１１１からの指令を受けて、並列演算器１１２＿ｎによる処理を実行可能状態又は実行不能状態に設定するための状態設定信号を並列演算器１１２＿ｎへと送信する。これにより、所望の並列演算器１１２＿ｎについて、評価値算出処理などを行うタイミングを調整することができる。即ち、評価値算出処理などを実行させる場合には、並列演算器１１２＿ｎへと評価値算出処理を実行可能とする状態設定信号を送信し、評価値算出処理を実行させない場合には、評価値算出処理を実行不能とする状態設定信号を送信する。
【００３２】
図１に戻り再び説明を続ける。並列演算器１１２ｎは、評価値処理部１１３と、領域選択部１１４と、経路方向情報生成部１１５と、受信部１１６と、受信バッファ１１７と、送信部１１８と、送信バッファ１１９と、を備えている。
【００３３】
評価値処理部１１３は、近傍に存在する領域の評価値と、その近傍領域から自身に対応する領域までの移動コストとに基づいて評価値を算出する。
【００３４】
領域選択部１１４は、並列演算することで算出した各領域の評価値に基づいて、近傍に存在する領域から一の選択領域を選択する。ここでは、領域選択部１１４は、近傍に存在する領域から、移動始点を含む領域により近づく方向の一の選択領域を選択する。例えば、移動が禁止される禁止領域を除く他の領域において、移動始点を含む領域の評価値を基準として、移動始点から距離が離れる領域ほど大きな値の評価値を算出した場合には、領域選択部１１４は、近傍に存在する領域のうち、最も小さな評価値を有する一の選択領域を選択する。尚、以下では、自領域から、移動始点を含む領域により近づく方向を上流方向と称し、また、自領域から、移動終点を含む領域により近づく方向を下流方向と称する場合がある。
【００３５】
経路方向情報生成部１１５は、自身に対応する領域から選択領域への方向を示す経路方向情報を生成する。経路探索装置１により探索される経路は、経路方向情報の系列から構成される。
【００３６】
受信部１１６は、他の並列演算器１１２＿ｎから送信された経路方向情報を受信する。受信バッファ１１７は、受信部１１６で受信した経路方向情報を保持する。尚、受信バッファ１１７で保持するデータは経路方向情報に限定されず、並列演算器１１２＿ｎ間で送受信される他のデータの受信及び保持に利用してもよい。
【００３７】
送信部１１８は、選択領域に対応する並列演算器１１２＿ｎに対して、受信部１１６で受信した経路方向情報を送信した後に、経路方向情報生成部１１５で生成した経路方向情報を送信する。ここでは、送信部１１８は、他の並列演算器１１２＿ｎから受信した経路方向情報を転送し終えた後に、その転送処理に続いて、経路方向情報生成部１１５で生成した経路方向情報を、送信バッファ１１９を介して選択領域に対応する並列演算器１１２＿ｎに送信する。このため、送信部１１８は、他の並列演算器１１２＿ｎから経路方向情報を受信した場合には、受信バッファ１１７に保持した経路方向情報を、送信バッファ１１９を介して選択領域に対応する並列演算器１１２＿ｎに送信し、他の並列演算器１１２＿ｎから経路方向情報を所定の期間受信しなかった場合には、経路方向情報生成部１１５で生成した経路方向情報を、送信バッファ１１９を介して選択領域に対応する並列演算器１１２＿ｎに送信する。
【００３８】
送信バッファ１１９は、受信バッファ１１７に保持した経路方向情報又は経路方向情報生成部１１５で生成した経路方向情報を送信するために保持する。尚、送信バッファ１１９で保持するデータは経路方向情報に限定されず、並列演算器１１２＿ｎ間で送受信される他のデータの送信及び保持に利用してもよい。
【００３９】
続いて、本実施の形態１に係る経路探索装置１による経路探索処理について、図５乃至１３を参照して説明する。図５は、本実施の形態１に係る経路探索装置１による経路探索処理の全体構成を示すフローチャート図である。
【００４０】
まず、コントローラ部１１１は、グリッドマップ上において、移動始点と移動終点を設定する（ステップＳ１０１）。そして、グリッドマップ上において、環境内に存在する障害物の登録（ステップＳ１０２）や、禁止領域（ステップＳ１０３）の作成を行う。
【００４１】
次いで、並列演算部１１２は、複数の並列演算器１０２＿ｎが並列演算することで、対応するそれぞれの領域の評価値を算出する（ステップＳ１０４）。このため、コントローラ部１１１は、グリッドマップを複数の領域に分割し、各領域を並列演算器１１２＿ｎに対応付けた後に、下位の並列演算部１１２の各並列演算器１１２＿ｎに対して評価値算出処理の開始を指示する。尚、並列演算部１１２における評価値算出処理の詳細については後述する。
【００４２】
次いで、コントローラ部１１１は、ステップＳ１０４で算出した評価値から各領域の経路方向情報を並列演算器１１２＿ｎにより生成させて、並列演算部１１２内で伝播させた経路方向情報を取得する（ステップＳ１０５）。尚、並列演算部１１２からの経路方向情報の取得処理の詳細については後述する。
【００４３】
本実施の形態１に係る経路探索装置１は、ステップＳ１０１〜Ｓ１０５に係る経路探索処理のうち、特に、Ｓ１０５に係る経路方向情報の効率的な取得処理を可能とする。即ち、本実施の形態１に係る経路探索装置１によれば、並列演算部１１２の各並列演算器１１２＿ｎから、経路方向情報を効率よく取得することができる。
【００４４】
まず、図６乃至８を参照して図５に示したＳ１０４に係る評価値の算出処理について具体的に説明する。図６は、各領域の評価値の算出処理を具体的に示すフローチャートである。
【００４５】
まず、コントローラ部１１１が、経路探索領域を複数の領域に分割し、分割したそれぞれの領域に対して並列演算器１１２＿ｎを対応付ける（Ｓ２０１）。ここでは、経路探索領域は、グリッド数と等しい数の領域に分割される。例えば、経路探索領域が２次元平面である場合には、それぞれ１０ｃｍ×１０ｃｍの広さを持つ離散的な複数の領域が分割生成される。
【００４６】
次に、コントローラ部１１１は、全ての並列演算器１１２＿ｎに対して初期値を代入する（Ｓ２０２）。各領域の状態として、進入が禁止される禁止状態、評価値が未計算である未計算状態、及び評価値を計算済みである計算済み状態からなる３状態を想定する。それぞれの状態に対応する初期値を並列演算器１１２＿ｎに代入する。評価値算出処理の開始段階であるＳ２０２では、経路探索対象となる領域のうち、進入禁止領域以外の領域に対応する並列演算器１１２＿ｎの評価値記憶部３２＿ｎ及び評価値記憶部３３＿ｎには、初期値として十分大きな値（例えば１．０×１０＾７）を代入する。進入禁止領域に対応する並列演算器１１２＿ｎの評価値記憶部３２＿ｎ及び評価値記憶部３３＿ｎには、初期値として十分大きな値（例えば１．０×１０＾９）を代入する。ここでは、初期値として、後述する評価値算出処理によって算出される評価値を十分上回る値を採用して代入する。尚、領域の状態をこのような初期値を設定することで判断してもよいし、領域の状態を示す状態情報を各並列演算器１１２＿ｎに格納するようにしてもよい。
【００４７】
次に、コントローラ部１１１は、移動始点を指定して、その移動始点を含む領域に対応する並列演算器１１２＿ｎについて、その評価値記憶部３２＿ｎ又は評価値記憶部３３＿ｎの少なくとも一方に、評価値の最小値（例えば０）を代入する（Ｓ２０３）。以下では、その評価値記憶部３２＿ｎのみに評価値の最小値が代入されたものとして説明する。
【００４８】
次に、コントローラ部１１１は、評価値算出処理を開始するための計算開始クロックＣ１を発生する（Ｓ２０４）。状態設定用信号線３４＿ｎを介して、CPUのクロックに相当するパルスが各並列演算器１１２＿ｎへと送信され、各並列演算器１１２＿ｎでＳ２０５乃至２０８における処理が実行される。またこのとき、評価値算出処理を実行させる並列演算器１１２＿ｎに対しては、評価値算出処理を実行可能とする状態設定信号が送信され、評価値算出処理を実行させない並列演算器１１２＿ｎに対しては、評価値算出処理を実行不能とする状態設定信号が送信される。
【００４９】
各並列演算器１１２＿ｎは、対応する自領域の評価値及び近傍領域の評価値に基づいて、以下のようにして自領域の評価値を更新してゆく。まず、評価値記憶部３２＿ｎに格納されている値について、自領域の評価値である自己評価値が、初期値から更新されているか否かを判定する（Ｓ２０５）。
【００５０】
ステップＳ２０５における判定の結果、自己評価値が初期値のままである場合（自領域の評価値が未計算である場合）には、近傍領域に対応する並列演算器１１２＿ｎで、その評価値記憶部３２＿ｎに格納されている値として、初期値ではない評価値が存在しているか否かを判定する（Ｓ２０６）。
【００５１】
ステップＳ２０６における判定の結果、近傍領域に初期値以外の値が存在する場合（近傍領域の評価値が計算済みである場合）には、近傍領域の評価値のうち最も小さい評価値と、その最小の評価値を持つ近傍領域から自領域までの幾何学的な距離に応じた移動コストに基づいて自己の領域の評価値を算出し、その結果を評価値記憶部３３＿ｎに格納する（Ｓ２０７）。ここでは、以下の式に基づいて自己の領域の評価値を算出する。
自己評価値＝近傍領域の最小評価値＋近傍領域から自領域までの移動コスト
【００５２】
一方、ステップＳ２０５又はＳ２０６における判定の結果、評価値記憶部３２＿ｎに格納されている自己評価値が初期値から更新されている場合、又は近傍領域に初期値以外の値が存在しない場合には、現在の自己評価値を更新せずにそのまま維持する（Ｓ２０８）。ここでは、自己評価値を維持する処理として、評価値記憶部３２に格納されている評価値を評価値記憶部３３＿ｎへと出力して格納する。このように処理することで、現在の自己評価値を簡易な処理によって維持することができる。尚、評価値記憶部３２＿ｎに格納されている評価値を評価値記憶部３３＿ｎへと出力せずに、何も処理を実行しないようにしてもよい。
【００５３】
全ての並列演算器１１２＿ｎで、ステップＳ２０５乃至２０８における評価値算出処理の実行を、それぞれ評価値記憶部３２＿ｎに格納された評価値に基づいて判定し、評価値算出結果を、それぞれ評価値記憶部３２＿ｎとは異なる評価値記憶部３３＿ｎに出力する。これにより、１回の評価値算出処理の結果、評価値算出結果の干渉を防ぐことができると共に、１近傍領域を越えて評価値が算出されないよう制限することができるため、１近傍領域に含まれる領域の評価値のみを算出させることができる。従って、複数の並列演算器１１２＿ｎによる評価値算出処理のタイミングを同期させることができる。尚、クロックＣ１の次のクロックＣ２によってステップＳ２０５乃至２０８における処理が実行される場合には、ステップＳ２０５乃至Ｓ２０８の処理において、評価値記憶部３３＿ｎに格納されている評価値に基づいて評価値算出処理が実行され、その結果が評価値記憶部３２に格納される。更には、クロックＣ２の次のクロックＣ３によってＳ２０５乃至２０８における処理が実行される場合には、評価値記憶部３２＿ｎに格納されている評価値に基づいて評価値算出処理が実行され、その結果が評価値記憶部３３＿ｎに格納される。
【００５４】
コントローラ部１１１は、移動終点を含む領域に対応する並列演算器１１２＿ｎについて、その評価値記憶部３２＿ｎ又は評価値記憶部３３＿ｎのいずれか一方に初期値ではない評価値が存在しているか否かを判定する（Ｓ２０９）。ステップＳ２０９における判定の結果、評価値が存在していない場合には、移動終点を含む領域の評価値は未だに算出されていない未計算状態であるため、ステップＳ２０４へと戻り再び各並列演算器１１２＿ｎにより領域の評価値算出処理を実行する。
【００５５】
一方、ステップＳ２０９における判定の結果、移動終点に評価値が存在している場合には、移動終点を含む領域の評価値が計算済みの状態となったことから、評価値算出処理を終了して、図５に示したＳ１０５に係る経路方向情報の取得処理に進む。
【００５６】
尚、ステップＳ２０９における評価値算出処理を終了させる条件としては、全ての領域に対応する評価値が変化しなくなった場合に処理を終了させるようにしてもよい。即ち、全ての並列演算器１１２＿ｎで、評価値記憶部３２＿ｎ及び３３＿ｎに格納された評価値が同じ値のまま変化しなくなった場合に処理を終了させることができる。また、このような終了条件をステップＳ２０９における終了条件に加えて判定させるように構成することで、移動始点から移動終点までの経路が存在しない場合であっても評価値算出処理を終了させることができる。
【００５７】
以下、図７及び図８に示すグリッドマップを参照して、図６に示した各領域の評価値算出処理に係る具体例について説明する。尚、図７及び図８に示すグリッドマップは、ロボットの目標軌道となる目標経路を、グリッド状に離散化された領域の集合として表現するものである。経路探索装置１を構成するコンピュータの経路探索記憶部１２は、グリッドマップに関する情報を格納している。ここで、グリッドマップに関する情報には、各領域の座標情報、各領域の近傍領域を示す領域間の接続情報、及び各領域に関連付けられた評価値情報が含まれる。領域の評価値は、それぞれの領域に対応する並列演算器１１２＿ｎによって算出される。
【００５８】
図７は、評価値算出処理の一例を説明するための図である。図７では、経路探索領域を横１６個、縦１３個の領域に分割し、評価他値算出処理を簡単に行わせるため、各領域の近傍領域を、各領域に隣接した前後左右４方向に隣接する領域とした。図８では、各領域から斜め４方向に位置する領域についても近傍領域に含めるものとし、各領域から８方向に隣接する領域を近傍領域とした。図において斜線領域は進入禁止領域を示し、外周上の領域は経路探索対象外である領域を示す。図に示す移動始点の領域の初期値を０に設定した場合に、並列演算器１１２＿ｎによる評価値算出結果を各領域に示す。尚、ここでは、近傍領域から自領域までの移動コストの値を５とした。分割された２０８個の領域のうち、３９個の領域が進入禁止領域であり、１６９個の領域が経路探索対象領域である。本実施の形態１に係る経路探索装置１によれば、各並列演算器１１２＿ｎがそれぞれ並列に評価値を算出するため、計２２回の計算によって評価値を算出することができる。
【００５９】
コントローラ部１１１は、並列演算部１１２における各領域の評価値算出処理が終了した後、並列演算部１１２内の特定の並列演算器１１２＿ｎから経路方向情報を取得することで、経路方向情報の系列から構成される経路を効率的に取得する。例えば、図８に、生成される経路方向情報を白抜き矢印で示す（各領域間に示す白抜き矢印が、各領域で生成される経路方向情報を示している）。これら経路方向情報の系列が、経路を構成する。移動終点から移動始点へと向かって、これら経路方向情報に沿って規定される経路が、移動終点から移動始点までの最短経路を示している（同時に、移動終点から移動始点までの最短経路を意味する）。尚、移動終点における評価値１１０は、移動始点から移動終点までに要する移動コストの総コストを意味している。後述するように、並列演算部１１２は、各領域における経路方向情報を上流方向である移動始点へと向けて伝播させる。コントローラ部１１１は、移動始点を含む領域に対応する並列演算器１１２＿ｎから、これら経路方向情報を順次取得する。コントローラ部１１１は、グリッドマップ上における移動始点又は移動終点の座標と、取得した経路方向情報の系列とから、グリッドマップ上における経路（即ち、経路を構成する座標値の点列）を構成する。これにより、経路探索装置１は、移動始点から移動終点へと至る経路を探索する。
【００６０】
続いて、図９乃至１３を参照して、図５に示したＳ１０５に係る経路方向情報の取得処理について具体的に説明する。コントローラ部１１１は、評価値算出処理が終了した後、移動終点を含む領域に対応する並列演算器１１２＿ｎから、経路方向情報の送信を最初に開始させる。並列演算部１１２内において、分割された各領域の評価値に基づいて、移動終点に対応する領域から上流方向の領域に向けて、各領域の経路方向情報が伝播される。そして、コントローラ部１１１は、移動始点を含む領域に対応する並列演算器１１２＿ｎから、伝播した経路方向情報を順次取得してゆく。
【００６１】
図９を参照して、並列演算部１１２内における経路方向情報の伝播処理について説明する。図９は、各並列演算器１１２＿ｎの処理を説明するためのフローチャート図である。まず、並列演算器１１２＿ｎの受信部１１６は、下流方向の並列演算器１１２＿ｎから送信された受信データを受信して、受信データを受信バッファ１１７に保持する（ステップＳ３０１）。並列演算器１１２＿ｎ間で送受信されるデータは、図１０に示すような構造のデータとすることができる。例えば、経路探索処理のモードを示すｍｏｄｅ部分と、そのモードにおいて処理されるｄａｔａ部分とから構成する。例えば、ｍｏｄｅ部分には、評価値算出処理中には評価値算出モードを設定し、経路方向情報の取得中には経路方向情報取得モードを設定することができる。また、ｄａｔａ部分には、近傍領域の評価値や、経路方向情報の値が設定される。受信データのデータ構造をこのように構成することで、受信データのｍｏｄｅ部分が経路方向情報取得モードを示す場合にのみ、ｄａｔａ部分に設定された経路方向情報を用いて、以下の処理を行えばよい。
【００６２】
次に、並列演算器１１２＿ｎは、受信データを所定の期間内に受信したか否かを判定する（ステップＳ３０２）。並列演算器１１２＿ｎは、下流方向の他の並列演算器１１２＿ｎから受信した経路方向情報を、上流方向の他の並列演算器１１２＿ｎへと転送する。ここで、並列演算器１１２＿ｎは、自身よりも下流方向の他の複数の並列演算器１１２＿ｎからそれぞれ送信された経路方向情報を全て転送した後に、これら複数の経路方向情報に続けて、後述するようにして生成した経路方向情報を上流方向の他の並列演算器１１２＿ｎへと送信する。このため、ここでは、下流方向の他の並列演算器１１２＿ｎから連続して送信される経路方向情報の受信が途絶えた場合（即ち、所定の期間内に受信しなかった場合）には、下流方向からの経路方向情報の送信は終了したものと判断する。
【００６３】
ステップＳ３０２での判定の結果、所定の期間内に受信した場合には、送信部１１８は、下流方向の他の並列演算器１１２＿ｎから受信した経路方向情報を、送信バッファ１１９にセットし（ステップＳ３０３）、上流方向の他の並列演算器１１２＿ｎへと送信する（ステップＳ３０４）。
【００６４】
ステップＳ３０２での判定の結果、所定の期間内に受信しなかった場合には、経路方向情報生成部１１５は、上流方向の領域への方向を示す経路方向情報を生成する（ステップＳ３０５）。
【００６５】
ここで、図１１を参照して、経路方向情報の生成処理について説明する。まず、領域選択部１１４が、近傍に存在する領域から、移動始点を含む領域により近づく方向の一の選択領域を選択する。ここでは、領域選択部１１４は、近傍に存在する領域のうち、最も小さな評価値を有する一の選択領域を選択する。そして、経路方向情報生成部１１５は、自身の領域から選択された領域へと向かう方向の情報を、経路方向情報として生成する。例えば、図１１に示すように、自身の領域を示す中央の領域から、隣接する近傍の８領域へと向かう白抜き矢印を経路方向とし、これら８方向を、０〜７の番号によりそれぞれ対応付ける。そして、例えば、経路方向情報を８ビットの情報を用いて示す場合には、８ビットの値のうちで、対応するビットの値のみを１とすることで、近傍の８領域のいずれの方向への経路方向情報であるかを示すことができる。具体的には、例えば、下方向（番号４）への経路方向情報を、"００００１０００"により示すことができる。
【００６６】
尚、ここでは、経路方向情報の取得中に、近傍領域から選択領域を選択して経路方向情報を生成するものとして説明したが、上述した評価値算出処理中に経路方向情報を生成して、各並列演算器１１２＿ｎに予め格納するものとしてもよい。
【００６７】
次に、送信部１１８は、経路方向情報生成部１１５で生成した経路方向情報を、送信バッファ１１９にセットし（ステップＳ３０６）、上流方向の他の並列演算器１１２＿ｎへと送信する（ステップＳ３０４）。
【００６８】
図１２及び図１３は、経路方向情報の伝播の様子を説明するための図である。図１２において、移動始点の領域名をＡとし、移動終点の領域名をＩとして示す。図１２に示す各領域において生成された経路方向情報が、移動始点の領域Ａへと向けて伝播する。具体的には、図１３に示すように、まず、領域Ｉに対応する並列演算器１１２＿ｎにより下方向を示す経路方向情報Ｉ（４）が生成され、評価値に基づいて選択された領域Ｈに対応する並列演算器１１２＿ｎへと、経路方向情報Ｉ（４）が送信される。領域Ｈに対応する並列演算器１１２＿ｎは、受信した経路方向情報Ｉ（４）を、下流方向の領域Ｇに対応する並列演算器１１２＿ｎに転送する。さらに、領域Ｈに対応する並列演算器１１２＿ｎは、右下方向を示す経路方向情報Ｈ（３）を生成して、領域Ｇに対応する並列演算器１１２＿ｎへと経路方向情報Ｈ（３）を送信する。以下、領域Ｇから領域Ａにかけて同様の処理を繰り返し、領域Ａに対応する並列演算器１１２＿ｎに対して、経路方向情報Ｉ（４）、経路方向情報Ｈ（３）、経路方向情報Ｇ（４）、経路方向情報Ｆ（５）、経路方向情報Ｅ（４）、経路方向情報Ｄ（５）、経路方向情報Ｃ（６）、経路方向情報Ｂ（５）が連続して送信される。
【００６９】
このように、各領域において生成された経路方向情報が移動始点の領域Ａに対応する並列演算器１１２＿ｎへと伝播する。コントローラ部１１１は、移動始点の領域Ａに対応する並列演算器１１２＿ｎへとアクセスし、経路方向情報を順次取得する。すなわち、コントローラ部１１１は、移動始点の領域Ａに対応する並列演算器１１２＿ｎのみにアクセスすることで、経路方向情報の系列を効率的に取得することができる。
【００７０】
ここで、並列演算部１１２内において、移動始点の領域Ａに対する並列演算器１１２＿ｎに全ての経路方向情報を集めるために必要な計算ステップは、経路を構成する領域の個数をｎとした場合に、２ｎ−１となる。並列演算部１１２内で経路方向情報を伝播させずに、コントローラ部１１１が各並列演算器１１２＿ｎに直接アクセスして経路方向情報を取得した場合には、コントローラ部１１１は、各領域にアクセスした都度、上流方向へと向かう領域を選択する処理を全ての領域で行う必要がある。これに対して、本実施の形態１に係る経路方向情報の取得処理では、並列演算部１１２内において、移動始点の領域に対応する並列演算器１１２＿ｎへ向けて各領域の経路方向情報が伝播するために、コントローラ部１１１は、該当の領域のみにアクセスして経路方向情報を取得すれば足りる。すなわち、コントローラ部１１１が並列演算器１１２＿ｎにアクセスして経路方向情報を取得する際に、アクセスした領域から上流方向へと向かう領域を選択する処理を行わずに済むために、コントローラ部１１１が並列演算部１１２にアクセスする際の計算量を削減することができる。
【００７１】
また、コントローラ部１１１は移動始点に対応する並列演算器１１２＿ｎのみから経路方向情報を取得すればよいため、上位のコントローラ部１１１が下位の並列演算部１１２にアクセスするための接続線の本数を抑制することができる。また、複数の並列演算器１１２＿ｎに対して一つの接続線を設け、その接続線を切替えて使用する構成とすることで、必要とする接続線の本数をより抑制することができる。さらに、各並列演算器１１２＿ｎの受信バッファ１１７には、一つの経路方向情報のみを保持しておけばよいため、受信バッファ１１７のコストを抑制することができる。
【００７２】
尚、移動始点に対応する並列演算器１１２＿ｎの受信バッファ１１７のサイズを、経路を構成する経路方向情報の系列全体を保持可能なサイズとした場合には、各並列演算器１１２＿ｎが搭載する受信バッファ１１７のコストは増加するものの、コントローラ部１１１は１度のアクセスにより、経路方向情報の系列全体を取得することができる。このため、並列演算部１１２とコントローラ部１１１との間のアクセス量を削減して、より効率的に経路探索処理を実行することができる。
【００７３】
以上説明したように、本発明は、並列演算を用いて経路探索を高速に計算する手法において、特に、経路を構成する経路方向情報を、各並列演算器１１２＿ｎから効率よく取得する手法に関する。本発明によれば、並列演算器１１２＿ｎ間の局所通信のみを利用することで、コントローラ部１１１は、経路方向情報の系列を効率的に取得することができる。これにより、上位のコントローラ部１１１と下位の並列演算部１１２との間の通信コストを削減することができ、経路探索装置１に係る製造コスト及び計算コストを低減することができる。
【００７４】
尚、上述した各実施の形態では、ロボットが移動する移動領域を経路探索領域として、移動始点から移動終点へと至る経路を探索するものとして説明したが、本発明はこれに限定されない。すなわち、ロボットが移動する移動領域に限らず、通信ネットワークや動力学モデル場において、任意の二点間の最適な経路を探索するための並列演算などに対しても本発明を適用することができる。
【００７５】
尚、本発明は上述した各実施の形態に限定されず、趣旨を逸脱しない範囲で適宜変更することが可能である。
【符号の説明】
【００７６】
１ 経路探索装置、
１１ 経路探索処理部、１２ 経路探索記憶部、
１１１ コントローラ部、１１２＿ｎ 並列演算器、
１１３ 評価値処理部、１１４ 領域選択部、１１５ 経路方向情報生成部、
１１６ 受信部、１１７ 受信バッファ、１１８ 送信部、
１１９ 送信バッファ、
３２＿ｎ 評価値記憶部、３３＿ｎ 評価値記憶部、３４＿ｎ 状態設定用信号線、
Ｃｎ 領域
【技術分野】
【０００１】
本発明は経路探索装置、経路探索方法、及び自律移動体に関し、特に、並列演算を用いて経路探索を行う際に、探索した経路情報を効率的に取得可能な経路探索装置、経路探索方法、及び自律移動体に関する。
【背景技術】
【０００２】
近年、始点から終点へと至る経路を探索し、その探索した経路に従って自律的に移動する自律移動体が開発されている。経路を探索する手法としては、Ａ＊（エースター）アルゴリズムやダイキストラ法を用いる手法が良く知られている。
【０００３】
このような経路探索手法は、通常、ノイマン型コンピュータを用いて実現される。ノイマン型コンピュータは、互いに独立したユニットとしてのメモリ及び演算部を搭載し、メモリ上に経路探索に係る計算過程を保存しながら処理を行う。すなわち、演算部はメモリへとアクセスを行う際に、経路探索処理に係る処理データをメモリとの間で逐次通信する必要がある。
【０００４】
一方、ノイマン型コンピュータを用いた場合と比較して、相互に接続された複数の演算器を用いて並列計算を行うことで、高速に経路探索を行う手法が提案されている（例えば、特許文献１乃至３）。
【０００５】
特許文献１には、並列計算機を用いた巡回セールスマン問題解法処理システムが開示されている。特許文献１に開示される解法処理システムでは、巡回対象の都市に対応させた各セルは、メッセージを受信した際にセル情報を追加し、ネットワークを介して隣接セルへメッセージを送信するメッセージ送信手段を備えている。また、最初にメッセージを送信するスタートセルは、受信したメッセージが全ての都市を経由して一番早くスタートセルに戻ってきたメッセージを検出すると、そのメッセージが最短経路を経由したメッセージであるとして経路探索処理を終了させるメッセージ監視手段を備えている。
【０００６】
特許文献２には、巡回セールスマン問題処理装置が開示されている。特許文献２では、並列計算による巡回セールスマン問題処理装置において、都市座標をセル数に応じて分割・割り当てる全体問題処理手段と、階層化した都市データを各セルに割り当てた部分問題を処理して解を求める部分問題処理手段を有する。
【０００７】
特許文献３には、経路探索システムが開示されている。特許文献４に開示される経路探索システムは、移動領域を複数の領域に分割する領域分割部と、分割された複数の領域に対応し、それぞれの領域の評価値を算出する複数の評価値算出部と、算出された評価値に基づいて経路を決定する経路決定部とを備えている。評価値算出部は、近傍に存在する領域の評価値と、その近傍領域から自領域までの移動コストに基づいて評価値を算出する評価値処理部を有している。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】特開平８−２７８８８９号公報
【特許文献２】特開平８−２８６９２０号公報
【特許文献３】特開２００９−１９９３２号公報
【発明の概要】
【発明が解決しようとする課題】
【０００９】
しかしながら、逐次的に処理を行うノイマン型コンピュータを用いて経路探索を行う場合には、演算部がメインメモリへと頻繁にアクセスする必要があり、経路探索自体に要する処理ではなく、メモリへのデータ参照のために多くの計算コストを消費するという問題がある。ノイマン型のコンピュータでは、メモリ及び演算部というそれぞれ独立したユニット構成であるために、両者間のアクセスが発生する。このため、メインメモリへのアクセス速度が遅い場合や、メインメモリへのアクセス頻度が多くなる場合、さらには、メインメモリに保持するデータ量が多くなる場合などには、コンピュータのプロセッサ自体の計算速度に比してメモリアクセス速度が低速なものとなり、メモリアクセス速度が、経路探索処理全体に係る処理能力の制約条件となってしまう。
【００１０】
また、特許文献１及び２に開示される技術では、全都市を一巡する経路のうちで最短な経路を探索する巡回セールスマン問題を対象とするものである。このため、特許文献１及び２に開示される経路探索手法を用いては、任意の二地点間で最適な経路を探索することはできない。さらに、例えば特許文献１に開示される巡回セールスマン問題解法処理システムでは、各セルが当該セルまでの経路探索の履歴を保持して、保持する履歴情報をメッセージとして隣接セルに送信する。このため、巡回対象となる都市数の増加に伴って保持及び送信するメッセージ量が増加し、システム全体の処理が遅延するという問題がある。
【００１１】
特許文献３に開示される技術では、各領域の評価値処理部がそれぞれ評価値を算出することで、経路探索空間が広大な場合においても、高速に最適な経路を探索することができる。しかし、特許文献３に開示される技術では、経路探索に係る処理のうち、各領域の評価値を高速に算出することは可能であるが、算出した評価値に基づいて決定される経路情報を効率よく取得することができないという問題がある。具体的には、特許文献３に開示される技術では、並列演算を行う各評価値算出ユニットにより各領域の評価値を算出した後に、移動始点を含む領域から開始して、隣接する近傍領域において最小の評価値を持つ領域を経路として選択していく（段落００５９など参照。）。ここで、選択された領域の系列である経路情報を取得するためには、経路上の全ての領域に逐次的にアクセスを行う必要があり、さらに、各領域にアクセスを行う都度、近傍領域の選択処理を行う必要があるため、効率よく経路情報を取得することができない。
【００１２】
従って、本発明は、互いに接続された複数の並列演算器から構成される並列演算部を用いて経路探索を行う技術において、並列演算部を統括する上位のコントローラ部が、探索した経路情報を効率的に取得することができる経路探索装置、経路探索方法、及び自律移動体を提供することを目的とする。
【課題を解決するための手段】
【００１３】
本発明に係る経路探索装置は、経路探索領域内に存在する第１の地点から第２の地点に到達する経路を探索する経路探索装置であって、前記経路探索領域が複数の領域に分割され、分割されたそれぞれの領域に対応する複数の並列演算器から構成される並列演算部と、前記並列演算部を統括するコントローラ部と、を備え、前記並列演算部は、前記複数の並列演算器が並列演算することで、対応するそれぞれの領域の評価値を算出し、前記並列演算器は、前記並列演算することで算出した各領域の評価値に基づいて、近傍に存在する領域から一の選択領域を選択する領域選択手段と、自身に対応する領域から前記選択領域への方向を示す経路方向情報を生成する経路方向情報生成手段と、他の前記並列演算器から送信された経路方向情報を受信する受信手段と、前記選択領域に対応する前記並列演算器に対して、前記受信手段で受信した前記経路方向情報を送信した後に、前記経路方向情報生成手段で生成した前記経路方向情報を送信する送信手段と、を備え、前記コントローラ部は、
前記第２の地点を含む領域に対応する第２の並列演算器から前記経路方向情報の送信を最初に開始させた後に、前記並列演算部内で伝播した前記経路方向情報の系列を、前記第１の地点を含む領域に対応する第１の並列演算器から取得することで、前記経路を探索するものである。
【００１４】
このように、各並列演算器間で局所的に経路方向情報を送受信することで、並列演算部内において、第２の地点の並列演算器から第１の地点の並列演算器へと向けて経路方向情報を伝播することができるため、上位のコントローラ部は、第１の地点の並列演算器のみにアクセスすることで、経路である経路方向情報の系列を取得することができる。従って、並列演算を用いて経路探索を行う際に、探索した経路情報を効率的に取得することができる。
【００１５】
また、前記並列演算器は、前記受信手段で受信した他の前記並列演算器から送信された経路方向情報を保持する受信バッファと、前記受信バッファに保持した前記経路方向情報又は前記経路方向情報生成手段で生成した前記経路方向情報を送信するために保持する送信バッファと、を更に備え、前記送信手段は、他の前記並列演算器から送信された経路方向情報を受信した場合には、前記受信バッファに保持した前記経路方向情報を、前記送信バッファを介して前記選択領域に対応する前記並列演算器に送信し、他の前記並列演算器から送信された経路方向情報を所定の期間受信しなかった場合には、前記経路方向情報生成手段で生成した前記経路方向情報を、前記送信バッファを介して前記選択領域に対応する前記並列演算器に送信するようにしてもよい。このように、各並列演算器は、他の並列演算器から受信した経路方向情報の転送と、自ら生成した経路方向情報を送信するため、受信バッファには、経路方向情報の系列全体を保持せずに、受信した経路方向情報のみを保持すればよい。
【００１６】
さらにまた、前記領域選択手段は、前記並列演算することで算出した各領域の評価値に基づいて、近傍に存在する領域から、前記第１の地点を含む領域により近づく方向の一の選択領域を選択するようにしてもよい。
【００１７】
また、前記並列演算器は、近傍に存在する領域の評価値と、当該近傍領域から自身に対応する領域までの移動コストに基づいて評価値を算出する評価値処理部を更に備えるようにしてもよい。
【００１８】
本発明に係る経路探索方法は、経路探索領域が複数の領域に分割され、分割されたそれぞれの領域に対応する複数の並列演算器から構成される並列演算部と、前記並列演算部を統括するコントローラ部と、を備える移動体が、前記経路探索領域内に存在する第１の地点から第２の地点に到達する経路を探索する経路探索方法であって、前記並列演算部が、前記複数の並列演算器が並列演算することで、対応するそれぞれの領域の評価値を算出し、前記並列演算器が、前記並列演算することで算出した各領域の評価値に基づいて、近傍に存在する領域から一の選択領域を選択する領域選択ステップと、自身に対応する領域から前記選択領域への方向を示す経路方向情報を生成する経路方向情報生成ステップと、他の前記並列演算器から送信された経路方向情報を受信する受信ステップと、前記選択領域に対応する前記並列演算器に対して、前記受信した前記経路方向情報を送信した後に、前記生成した前記経路方向情報を送信する送信ステップと、を有し、前記コントローラ部が、前記第２の地点を含む領域に対応する第２の並列演算器から前記経路方向情報の送信を最初に開始させた後に、前記並列演算部内で伝播した前記経路方向情報の系列を、前記第１の地点を含む領域に対応する第１の並列演算器から取得することで、前記経路を探索するものである。
【００１９】
本発明に係る自律移動体は、経路探索領域内に存在する第１の地点から第２の地点に到達する経路を探索する自律移動体であって、前記経路探索領域が複数の領域に分割され、分割されたそれぞれの領域に対応する複数の並列演算器から構成される並列演算部と、前記並列演算部を統括するコントローラ部と、を備え、前記並列演算部は、近傍に存在する領域の評価値と、当該近傍領域から自身に対応する領域までの移動コストに基づいて、対応するそれぞれの領域の評価値を算出し、前記並列演算器は、前記並列演算することで算出した各領域の評価値に基づいて、近傍に存在する領域のうち最も小さい評価値を有する一の選択領域を選択する領域選択部と、自身に対応する領域から前記選択領域への方向を示す経路方向情報を生成する経路方向情報生成部と、他の前記並列演算器から送信された経路方向情報を受信する受信部と、前記選択領域に対応する前記並列演算器に対して、前記受信部で受信した前記経路方向情報を送信した後に、前記経路方向情報生成部で生成した前記経路方向情報を送信する送信部と、を備え、前記コントローラ部は、前記第２の地点を含む領域に対応する第２の並列演算器から前記経路方向情報の送信を最初に開始させた後に、前記並列演算部内で伝播した前記経路方向情報の系列を、前記第１の地点を含む領域に対応する第１の並列演算器から取得することで、前記経路を探索するものである。
【発明の効果】
【００２０】
本発明によれば、並列演算を用いて経路探索を行う際に、探索した経路情報を効率的に取得可能な経路探索装置、経路探索方法、及び自律移動体を提供することができる。
【図面の簡単な説明】
【００２１】
【図１】本発明の実施の形態１に係る経路探索装置の構成を示すブロック図である。
【図２】本発明の実施の形態１に係る経路探索領域を分割した複数の領域を示す概念図である。
【図３】本発明の実施の形態１に係る離散化された領域間の接続関係を説明するための概念図である。
【図４】本発明の実施の形態１に係る並列演算器の構成を示す概念図である。
【図５】本発明の実施の形態１に係る経路探索装置による経路探索処理の全体構成を示すフローチャートである。
【図６】本発明の実施の形態１に係る経路探索装置領域の評価値の算出処理を示すフローチャートである。
【図７】本発明の実施の形態１に係る経路探索装置による評価値算出処理の一例を説明するための図である。
【図８】本発明の実施の形態１に係る経路探索装置による経路探索結果の一例を説明するための図である。
【図９】本発明の実施の形態１に係る並列演算器における処理を説明するためのフローチャート図である。
【図１０】本発明の実施の形態１に係る経路探索装置の並列演算器間で送受信されるデータ構造の一例を示す図である。
【図１１】本発明の実施の形態１に係る経路探索装置による経路方向情報を説明するための図である。
【図１２】本発明の実施の形態１に係る経路探索装置による経路方向情報の伝播の様子を説明するための図である。
【図１３】本発明の実施の形態１に係る経路探索装置による経路方向情報の伝播の様子を説明するための図である。
【発明を実施するための形態】
【００２２】
実施の形態１．
本実施の形態１では、自律移動体としてのロボットに経路探索機能を搭載した場合を例に説明する。ロボットは、例えば、それぞれ独立して回転制御される二つの車輪を備えたものでもよく、２輪よりも多い、例えば４輪走行のロボットや、１輪走行のロボット、２足歩行・４足歩行のロボットであってもよい。また、ロボットに限らず、２輪走行や４輪走行の車両にも適用できる。ロボットは、障害物を検出するセンサやカメラを備え、検出された障害物に応じて、これを避けるように経路探索を行なうようにしてもよい。
【００２３】
本実施の形態１に係るロボットが備える経路探索機能によれば、並列演算することで経路探索処理を行う並列演算部内において、各並列演算器間で局所的に経路方向情報を送受信し、第２の地点の並列演算器から第１の地点の並列演算器へと向けて経路方向情報を伝播することができる。このため、並列演算部を統括する上位のコントローラ部は、第１の地点の並列演算器のみにアクセスすることで、経路である経路方向情報の系列を取得することができる。従って、並列演算を用いて経路探索を行う際に、探索した経路情報を効率的に取得することができる。尚、以下では、第１の地点をロボットが移動を開始する移動始点とし、第２の地点を移動目標地点である移動終点として説明するが、本実施の形態１に係る経路探索装置は任意の二点間の最適な経路を探索するものであり、第１の地点を移動終点とし、第２の地点を移動始点としてもよい。以下、図面を参照して本発明の実施の形態１について説明する。
【００２４】
図１は、本実施の形態１に係る経路探索装置の概略構成を示すブロック図である。図１に示されるように、経路探索装置１は、経路探索処理部１１と経路探索記憶部１２により構成されている。経路探索処理部１１は、コントローラ部１１１と、並列演算部１１２から構成されている。並列演算部１１２は、複数の並列演算器１１２＿１、１１２＿２、・・・（以下、単に並列演算器１１２＿ｎと称する場合がある。）を備えている。並列演算器１１２＿ｎは、それぞれ物理的に独立した演算器であって、後述する評価値算出処理などを並列に実行する。
【００２５】
経路探索記憶部１２には、ロボットが移動する経路探索領域全体の形状に、略一定間隔ｄ（例えば１０ｃｍ）に配置された格子点を結ぶグリッド線を仮想的に描写することで得られるグリッドマップが記憶されている。ロボットは、ＧＰＳ等から得られた位置情報を、このグリッドマップ上における自己の位置に置き換えて、グリッドマップ上における自己位置を認識する。グリッドマップ上において、ロボットの自己位置に相当する場所、および目的地である移動終点、及び移動終点におけるロボットの移動方向が特定される。ロボットは、グリッドマップ上において特定された自己位置を移動始点から、目的地である移動終点までの経路を探索し、探索した経路に従って移動を行う。
【００２６】
コントローラ部１１１は、並列演算部１１２を統括して制御処理を行い、経路方向情報の系列からなる経路を、並列演算部１１２から取得する。尚、コントローラ部１１１による並列演算部１１２の制御処理の詳細については後述する。
【００２７】
また、コントローラ部１１１は、ロボットが移動する経路探索領域を格子状の領域に分割する分割処理を行う。ここでは、上述の略一定間隔ｄ（例えば１０ｃｍ）に配置された格子点を囲む複数の領域に分割する。図２は、経路探索領域を分割して、離散化された複数の領域Ｃｎを示す概念図である。尚、コントローラ部１１１による分割方法はこれに限定されない。例えば、上述の分割後の領域よりも大きな領域へと分割することで、経路探索に要する時間をより短縮することができる。
【００２８】
そして、コントローラ部１１１は、分割した領域間の接続関係を定める。以下では、注目する領域に接続する領域を近傍領域と称する。図３は、離散化された領域間の接続関係を説明するための概念図である。図３（ａ）では、注目する領域Ｃ０に対して、隣接領域Ｃ１乃至Ｃ８を近傍領域として定めるものである。また、図３（ｂ）では、注目する領域Ｃ０に対して、隣接領域Ｃ１乃至Ｃ８に加えて、さらに領域Ｃ９乃至Ｃ１６を近傍領域として定めるものである。このように、自領域に対して隣接した領域を越えた領域を近傍領域として設定可能とすることで、自領域及びそれら近傍領域間を通過する経路を作成することができる。このようにすれば、移動始点から移動終点へと至る経路の角度分解能を柔軟に設定することができ、より滑らかな経路を作成することができる。
【００２９】
並列演算部１１２は、複数の並列演算器１１２＿１、１１２＿２、・・・から構成される。複数の並列演算器１１２＿１、１１２＿２、・・・は、コントローラ部１１１により分割された各領域にそれぞれ対応する。図４は、並列演算器１１２＿ｎの構成を示す概念図である。図４（ａ）に示すように、並列演算器１１２＿ｎには、少なくとも２つの評価値記憶部３２＿ｎ及び評価値記憶部３３＿ｎと、状態設定用信号線３４＿ｎとが接続されている。
【００３０】
尚、複数の並列演算器１１２＿１、１１２＿２、・・・はいずれも同一の構成を有しており、簡易な構成により経路探索装置１を構成することができる。各並列演算器１１２＿ｎは、分割された各領域に一対一で対応付けてもよいし、一つの並列演算器１１２＿ｎが、複数の分割された領域に対応するようにしてもよい。また、並列演算器１１２＿ｎは、例えばＦＰＧＡ（Field Programmable Gate Array）等のプログラム可能な装置を用いることによって容易に構成することができる。そして、図４（ｂ）に示すように、複数の並列演算器１１２＿ｎが配列され、それぞれが分割された複数の領域に対応する。このような配列構造によれば、ロボットなどに対しても容易に実装化することができる。
【００３１】
状態設定用信号線３４＿ｎは、コントローラ部１１１からの指令を受けて、並列演算器１１２＿ｎによる処理を実行可能状態又は実行不能状態に設定するための状態設定信号を並列演算器１１２＿ｎへと送信する。これにより、所望の並列演算器１１２＿ｎについて、評価値算出処理などを行うタイミングを調整することができる。即ち、評価値算出処理などを実行させる場合には、並列演算器１１２＿ｎへと評価値算出処理を実行可能とする状態設定信号を送信し、評価値算出処理を実行させない場合には、評価値算出処理を実行不能とする状態設定信号を送信する。
【００３２】
図１に戻り再び説明を続ける。並列演算器１１２ｎは、評価値処理部１１３と、領域選択部１１４と、経路方向情報生成部１１５と、受信部１１６と、受信バッファ１１７と、送信部１１８と、送信バッファ１１９と、を備えている。
【００３３】
評価値処理部１１３は、近傍に存在する領域の評価値と、その近傍領域から自身に対応する領域までの移動コストとに基づいて評価値を算出する。
【００３４】
領域選択部１１４は、並列演算することで算出した各領域の評価値に基づいて、近傍に存在する領域から一の選択領域を選択する。ここでは、領域選択部１１４は、近傍に存在する領域から、移動始点を含む領域により近づく方向の一の選択領域を選択する。例えば、移動が禁止される禁止領域を除く他の領域において、移動始点を含む領域の評価値を基準として、移動始点から距離が離れる領域ほど大きな値の評価値を算出した場合には、領域選択部１１４は、近傍に存在する領域のうち、最も小さな評価値を有する一の選択領域を選択する。尚、以下では、自領域から、移動始点を含む領域により近づく方向を上流方向と称し、また、自領域から、移動終点を含む領域により近づく方向を下流方向と称する場合がある。
【００３５】
経路方向情報生成部１１５は、自身に対応する領域から選択領域への方向を示す経路方向情報を生成する。経路探索装置１により探索される経路は、経路方向情報の系列から構成される。
【００３６】
受信部１１６は、他の並列演算器１１２＿ｎから送信された経路方向情報を受信する。受信バッファ１１７は、受信部１１６で受信した経路方向情報を保持する。尚、受信バッファ１１７で保持するデータは経路方向情報に限定されず、並列演算器１１２＿ｎ間で送受信される他のデータの受信及び保持に利用してもよい。
【００３７】
送信部１１８は、選択領域に対応する並列演算器１１２＿ｎに対して、受信部１１６で受信した経路方向情報を送信した後に、経路方向情報生成部１１５で生成した経路方向情報を送信する。ここでは、送信部１１８は、他の並列演算器１１２＿ｎから受信した経路方向情報を転送し終えた後に、その転送処理に続いて、経路方向情報生成部１１５で生成した経路方向情報を、送信バッファ１１９を介して選択領域に対応する並列演算器１１２＿ｎに送信する。このため、送信部１１８は、他の並列演算器１１２＿ｎから経路方向情報を受信した場合には、受信バッファ１１７に保持した経路方向情報を、送信バッファ１１９を介して選択領域に対応する並列演算器１１２＿ｎに送信し、他の並列演算器１１２＿ｎから経路方向情報を所定の期間受信しなかった場合には、経路方向情報生成部１１５で生成した経路方向情報を、送信バッファ１１９を介して選択領域に対応する並列演算器１１２＿ｎに送信する。
【００３８】
送信バッファ１１９は、受信バッファ１１７に保持した経路方向情報又は経路方向情報生成部１１５で生成した経路方向情報を送信するために保持する。尚、送信バッファ１１９で保持するデータは経路方向情報に限定されず、並列演算器１１２＿ｎ間で送受信される他のデータの送信及び保持に利用してもよい。
【００３９】
続いて、本実施の形態１に係る経路探索装置１による経路探索処理について、図５乃至１３を参照して説明する。図５は、本実施の形態１に係る経路探索装置１による経路探索処理の全体構成を示すフローチャート図である。
【００４０】
まず、コントローラ部１１１は、グリッドマップ上において、移動始点と移動終点を設定する（ステップＳ１０１）。そして、グリッドマップ上において、環境内に存在する障害物の登録（ステップＳ１０２）や、禁止領域（ステップＳ１０３）の作成を行う。
【００４１】
次いで、並列演算部１１２は、複数の並列演算器１０２＿ｎが並列演算することで、対応するそれぞれの領域の評価値を算出する（ステップＳ１０４）。このため、コントローラ部１１１は、グリッドマップを複数の領域に分割し、各領域を並列演算器１１２＿ｎに対応付けた後に、下位の並列演算部１１２の各並列演算器１１２＿ｎに対して評価値算出処理の開始を指示する。尚、並列演算部１１２における評価値算出処理の詳細については後述する。
【００４２】
次いで、コントローラ部１１１は、ステップＳ１０４で算出した評価値から各領域の経路方向情報を並列演算器１１２＿ｎにより生成させて、並列演算部１１２内で伝播させた経路方向情報を取得する（ステップＳ１０５）。尚、並列演算部１１２からの経路方向情報の取得処理の詳細については後述する。
【００４３】
本実施の形態１に係る経路探索装置１は、ステップＳ１０１〜Ｓ１０５に係る経路探索処理のうち、特に、Ｓ１０５に係る経路方向情報の効率的な取得処理を可能とする。即ち、本実施の形態１に係る経路探索装置１によれば、並列演算部１１２の各並列演算器１１２＿ｎから、経路方向情報を効率よく取得することができる。
【００４４】
まず、図６乃至８を参照して図５に示したＳ１０４に係る評価値の算出処理について具体的に説明する。図６は、各領域の評価値の算出処理を具体的に示すフローチャートである。
【００４５】
まず、コントローラ部１１１が、経路探索領域を複数の領域に分割し、分割したそれぞれの領域に対して並列演算器１１２＿ｎを対応付ける（Ｓ２０１）。ここでは、経路探索領域は、グリッド数と等しい数の領域に分割される。例えば、経路探索領域が２次元平面である場合には、それぞれ１０ｃｍ×１０ｃｍの広さを持つ離散的な複数の領域が分割生成される。
【００４６】
次に、コントローラ部１１１は、全ての並列演算器１１２＿ｎに対して初期値を代入する（Ｓ２０２）。各領域の状態として、進入が禁止される禁止状態、評価値が未計算である未計算状態、及び評価値を計算済みである計算済み状態からなる３状態を想定する。それぞれの状態に対応する初期値を並列演算器１１２＿ｎに代入する。評価値算出処理の開始段階であるＳ２０２では、経路探索対象となる領域のうち、進入禁止領域以外の領域に対応する並列演算器１１２＿ｎの評価値記憶部３２＿ｎ及び評価値記憶部３３＿ｎには、初期値として十分大きな値（例えば１．０×１０＾７）を代入する。進入禁止領域に対応する並列演算器１１２＿ｎの評価値記憶部３２＿ｎ及び評価値記憶部３３＿ｎには、初期値として十分大きな値（例えば１．０×１０＾９）を代入する。ここでは、初期値として、後述する評価値算出処理によって算出される評価値を十分上回る値を採用して代入する。尚、領域の状態をこのような初期値を設定することで判断してもよいし、領域の状態を示す状態情報を各並列演算器１１２＿ｎに格納するようにしてもよい。
【００４７】
次に、コントローラ部１１１は、移動始点を指定して、その移動始点を含む領域に対応する並列演算器１１２＿ｎについて、その評価値記憶部３２＿ｎ又は評価値記憶部３３＿ｎの少なくとも一方に、評価値の最小値（例えば０）を代入する（Ｓ２０３）。以下では、その評価値記憶部３２＿ｎのみに評価値の最小値が代入されたものとして説明する。
【００４８】
次に、コントローラ部１１１は、評価値算出処理を開始するための計算開始クロックＣ１を発生する（Ｓ２０４）。状態設定用信号線３４＿ｎを介して、CPUのクロックに相当するパルスが各並列演算器１１２＿ｎへと送信され、各並列演算器１１２＿ｎでＳ２０５乃至２０８における処理が実行される。またこのとき、評価値算出処理を実行させる並列演算器１１２＿ｎに対しては、評価値算出処理を実行可能とする状態設定信号が送信され、評価値算出処理を実行させない並列演算器１１２＿ｎに対しては、評価値算出処理を実行不能とする状態設定信号が送信される。
【００４９】
各並列演算器１１２＿ｎは、対応する自領域の評価値及び近傍領域の評価値に基づいて、以下のようにして自領域の評価値を更新してゆく。まず、評価値記憶部３２＿ｎに格納されている値について、自領域の評価値である自己評価値が、初期値から更新されているか否かを判定する（Ｓ２０５）。
【００５０】
ステップＳ２０５における判定の結果、自己評価値が初期値のままである場合（自領域の評価値が未計算である場合）には、近傍領域に対応する並列演算器１１２＿ｎで、その評価値記憶部３２＿ｎに格納されている値として、初期値ではない評価値が存在しているか否かを判定する（Ｓ２０６）。
【００５１】
ステップＳ２０６における判定の結果、近傍領域に初期値以外の値が存在する場合（近傍領域の評価値が計算済みである場合）には、近傍領域の評価値のうち最も小さい評価値と、その最小の評価値を持つ近傍領域から自領域までの幾何学的な距離に応じた移動コストに基づいて自己の領域の評価値を算出し、その結果を評価値記憶部３３＿ｎに格納する（Ｓ２０７）。ここでは、以下の式に基づいて自己の領域の評価値を算出する。
自己評価値＝近傍領域の最小評価値＋近傍領域から自領域までの移動コスト
【００５２】
一方、ステップＳ２０５又はＳ２０６における判定の結果、評価値記憶部３２＿ｎに格納されている自己評価値が初期値から更新されている場合、又は近傍領域に初期値以外の値が存在しない場合には、現在の自己評価値を更新せずにそのまま維持する（Ｓ２０８）。ここでは、自己評価値を維持する処理として、評価値記憶部３２に格納されている評価値を評価値記憶部３３＿ｎへと出力して格納する。このように処理することで、現在の自己評価値を簡易な処理によって維持することができる。尚、評価値記憶部３２＿ｎに格納されている評価値を評価値記憶部３３＿ｎへと出力せずに、何も処理を実行しないようにしてもよい。
【００５３】
全ての並列演算器１１２＿ｎで、ステップＳ２０５乃至２０８における評価値算出処理の実行を、それぞれ評価値記憶部３２＿ｎに格納された評価値に基づいて判定し、評価値算出結果を、それぞれ評価値記憶部３２＿ｎとは異なる評価値記憶部３３＿ｎに出力する。これにより、１回の評価値算出処理の結果、評価値算出結果の干渉を防ぐことができると共に、１近傍領域を越えて評価値が算出されないよう制限することができるため、１近傍領域に含まれる領域の評価値のみを算出させることができる。従って、複数の並列演算器１１２＿ｎによる評価値算出処理のタイミングを同期させることができる。尚、クロックＣ１の次のクロックＣ２によってステップＳ２０５乃至２０８における処理が実行される場合には、ステップＳ２０５乃至Ｓ２０８の処理において、評価値記憶部３３＿ｎに格納されている評価値に基づいて評価値算出処理が実行され、その結果が評価値記憶部３２に格納される。更には、クロックＣ２の次のクロックＣ３によってＳ２０５乃至２０８における処理が実行される場合には、評価値記憶部３２＿ｎに格納されている評価値に基づいて評価値算出処理が実行され、その結果が評価値記憶部３３＿ｎに格納される。
【００５４】
コントローラ部１１１は、移動終点を含む領域に対応する並列演算器１１２＿ｎについて、その評価値記憶部３２＿ｎ又は評価値記憶部３３＿ｎのいずれか一方に初期値ではない評価値が存在しているか否かを判定する（Ｓ２０９）。ステップＳ２０９における判定の結果、評価値が存在していない場合には、移動終点を含む領域の評価値は未だに算出されていない未計算状態であるため、ステップＳ２０４へと戻り再び各並列演算器１１２＿ｎにより領域の評価値算出処理を実行する。
【００５５】
一方、ステップＳ２０９における判定の結果、移動終点に評価値が存在している場合には、移動終点を含む領域の評価値が計算済みの状態となったことから、評価値算出処理を終了して、図５に示したＳ１０５に係る経路方向情報の取得処理に進む。
【００５６】
尚、ステップＳ２０９における評価値算出処理を終了させる条件としては、全ての領域に対応する評価値が変化しなくなった場合に処理を終了させるようにしてもよい。即ち、全ての並列演算器１１２＿ｎで、評価値記憶部３２＿ｎ及び３３＿ｎに格納された評価値が同じ値のまま変化しなくなった場合に処理を終了させることができる。また、このような終了条件をステップＳ２０９における終了条件に加えて判定させるように構成することで、移動始点から移動終点までの経路が存在しない場合であっても評価値算出処理を終了させることができる。
【００５７】
以下、図７及び図８に示すグリッドマップを参照して、図６に示した各領域の評価値算出処理に係る具体例について説明する。尚、図７及び図８に示すグリッドマップは、ロボットの目標軌道となる目標経路を、グリッド状に離散化された領域の集合として表現するものである。経路探索装置１を構成するコンピュータの経路探索記憶部１２は、グリッドマップに関する情報を格納している。ここで、グリッドマップに関する情報には、各領域の座標情報、各領域の近傍領域を示す領域間の接続情報、及び各領域に関連付けられた評価値情報が含まれる。領域の評価値は、それぞれの領域に対応する並列演算器１１２＿ｎによって算出される。
【００５８】
図７は、評価値算出処理の一例を説明するための図である。図７では、経路探索領域を横１６個、縦１３個の領域に分割し、評価他値算出処理を簡単に行わせるため、各領域の近傍領域を、各領域に隣接した前後左右４方向に隣接する領域とした。図８では、各領域から斜め４方向に位置する領域についても近傍領域に含めるものとし、各領域から８方向に隣接する領域を近傍領域とした。図において斜線領域は進入禁止領域を示し、外周上の領域は経路探索対象外である領域を示す。図に示す移動始点の領域の初期値を０に設定した場合に、並列演算器１１２＿ｎによる評価値算出結果を各領域に示す。尚、ここでは、近傍領域から自領域までの移動コストの値を５とした。分割された２０８個の領域のうち、３９個の領域が進入禁止領域であり、１６９個の領域が経路探索対象領域である。本実施の形態１に係る経路探索装置１によれば、各並列演算器１１２＿ｎがそれぞれ並列に評価値を算出するため、計２２回の計算によって評価値を算出することができる。
【００５９】
コントローラ部１１１は、並列演算部１１２における各領域の評価値算出処理が終了した後、並列演算部１１２内の特定の並列演算器１１２＿ｎから経路方向情報を取得することで、経路方向情報の系列から構成される経路を効率的に取得する。例えば、図８に、生成される経路方向情報を白抜き矢印で示す（各領域間に示す白抜き矢印が、各領域で生成される経路方向情報を示している）。これら経路方向情報の系列が、経路を構成する。移動終点から移動始点へと向かって、これら経路方向情報に沿って規定される経路が、移動終点から移動始点までの最短経路を示している（同時に、移動終点から移動始点までの最短経路を意味する）。尚、移動終点における評価値１１０は、移動始点から移動終点までに要する移動コストの総コストを意味している。後述するように、並列演算部１１２は、各領域における経路方向情報を上流方向である移動始点へと向けて伝播させる。コントローラ部１１１は、移動始点を含む領域に対応する並列演算器１１２＿ｎから、これら経路方向情報を順次取得する。コントローラ部１１１は、グリッドマップ上における移動始点又は移動終点の座標と、取得した経路方向情報の系列とから、グリッドマップ上における経路（即ち、経路を構成する座標値の点列）を構成する。これにより、経路探索装置１は、移動始点から移動終点へと至る経路を探索する。
【００６０】
続いて、図９乃至１３を参照して、図５に示したＳ１０５に係る経路方向情報の取得処理について具体的に説明する。コントローラ部１１１は、評価値算出処理が終了した後、移動終点を含む領域に対応する並列演算器１１２＿ｎから、経路方向情報の送信を最初に開始させる。並列演算部１１２内において、分割された各領域の評価値に基づいて、移動終点に対応する領域から上流方向の領域に向けて、各領域の経路方向情報が伝播される。そして、コントローラ部１１１は、移動始点を含む領域に対応する並列演算器１１２＿ｎから、伝播した経路方向情報を順次取得してゆく。
【００６１】
図９を参照して、並列演算部１１２内における経路方向情報の伝播処理について説明する。図９は、各並列演算器１１２＿ｎの処理を説明するためのフローチャート図である。まず、並列演算器１１２＿ｎの受信部１１６は、下流方向の並列演算器１１２＿ｎから送信された受信データを受信して、受信データを受信バッファ１１７に保持する（ステップＳ３０１）。並列演算器１１２＿ｎ間で送受信されるデータは、図１０に示すような構造のデータとすることができる。例えば、経路探索処理のモードを示すｍｏｄｅ部分と、そのモードにおいて処理されるｄａｔａ部分とから構成する。例えば、ｍｏｄｅ部分には、評価値算出処理中には評価値算出モードを設定し、経路方向情報の取得中には経路方向情報取得モードを設定することができる。また、ｄａｔａ部分には、近傍領域の評価値や、経路方向情報の値が設定される。受信データのデータ構造をこのように構成することで、受信データのｍｏｄｅ部分が経路方向情報取得モードを示す場合にのみ、ｄａｔａ部分に設定された経路方向情報を用いて、以下の処理を行えばよい。
【００６２】
次に、並列演算器１１２＿ｎは、受信データを所定の期間内に受信したか否かを判定する（ステップＳ３０２）。並列演算器１１２＿ｎは、下流方向の他の並列演算器１１２＿ｎから受信した経路方向情報を、上流方向の他の並列演算器１１２＿ｎへと転送する。ここで、並列演算器１１２＿ｎは、自身よりも下流方向の他の複数の並列演算器１１２＿ｎからそれぞれ送信された経路方向情報を全て転送した後に、これら複数の経路方向情報に続けて、後述するようにして生成した経路方向情報を上流方向の他の並列演算器１１２＿ｎへと送信する。このため、ここでは、下流方向の他の並列演算器１１２＿ｎから連続して送信される経路方向情報の受信が途絶えた場合（即ち、所定の期間内に受信しなかった場合）には、下流方向からの経路方向情報の送信は終了したものと判断する。
【００６３】
ステップＳ３０２での判定の結果、所定の期間内に受信した場合には、送信部１１８は、下流方向の他の並列演算器１１２＿ｎから受信した経路方向情報を、送信バッファ１１９にセットし（ステップＳ３０３）、上流方向の他の並列演算器１１２＿ｎへと送信する（ステップＳ３０４）。
【００６４】
ステップＳ３０２での判定の結果、所定の期間内に受信しなかった場合には、経路方向情報生成部１１５は、上流方向の領域への方向を示す経路方向情報を生成する（ステップＳ３０５）。
【００６５】
ここで、図１１を参照して、経路方向情報の生成処理について説明する。まず、領域選択部１１４が、近傍に存在する領域から、移動始点を含む領域により近づく方向の一の選択領域を選択する。ここでは、領域選択部１１４は、近傍に存在する領域のうち、最も小さな評価値を有する一の選択領域を選択する。そして、経路方向情報生成部１１５は、自身の領域から選択された領域へと向かう方向の情報を、経路方向情報として生成する。例えば、図１１に示すように、自身の領域を示す中央の領域から、隣接する近傍の８領域へと向かう白抜き矢印を経路方向とし、これら８方向を、０〜７の番号によりそれぞれ対応付ける。そして、例えば、経路方向情報を８ビットの情報を用いて示す場合には、８ビットの値のうちで、対応するビットの値のみを１とすることで、近傍の８領域のいずれの方向への経路方向情報であるかを示すことができる。具体的には、例えば、下方向（番号４）への経路方向情報を、"００００１０００"により示すことができる。
【００６６】
尚、ここでは、経路方向情報の取得中に、近傍領域から選択領域を選択して経路方向情報を生成するものとして説明したが、上述した評価値算出処理中に経路方向情報を生成して、各並列演算器１１２＿ｎに予め格納するものとしてもよい。
【００６７】
次に、送信部１１８は、経路方向情報生成部１１５で生成した経路方向情報を、送信バッファ１１９にセットし（ステップＳ３０６）、上流方向の他の並列演算器１１２＿ｎへと送信する（ステップＳ３０４）。
【００６８】
図１２及び図１３は、経路方向情報の伝播の様子を説明するための図である。図１２において、移動始点の領域名をＡとし、移動終点の領域名をＩとして示す。図１２に示す各領域において生成された経路方向情報が、移動始点の領域Ａへと向けて伝播する。具体的には、図１３に示すように、まず、領域Ｉに対応する並列演算器１１２＿ｎにより下方向を示す経路方向情報Ｉ（４）が生成され、評価値に基づいて選択された領域Ｈに対応する並列演算器１１２＿ｎへと、経路方向情報Ｉ（４）が送信される。領域Ｈに対応する並列演算器１１２＿ｎは、受信した経路方向情報Ｉ（４）を、下流方向の領域Ｇに対応する並列演算器１１２＿ｎに転送する。さらに、領域Ｈに対応する並列演算器１１２＿ｎは、右下方向を示す経路方向情報Ｈ（３）を生成して、領域Ｇに対応する並列演算器１１２＿ｎへと経路方向情報Ｈ（３）を送信する。以下、領域Ｇから領域Ａにかけて同様の処理を繰り返し、領域Ａに対応する並列演算器１１２＿ｎに対して、経路方向情報Ｉ（４）、経路方向情報Ｈ（３）、経路方向情報Ｇ（４）、経路方向情報Ｆ（５）、経路方向情報Ｅ（４）、経路方向情報Ｄ（５）、経路方向情報Ｃ（６）、経路方向情報Ｂ（５）が連続して送信される。
【００６９】
このように、各領域において生成された経路方向情報が移動始点の領域Ａに対応する並列演算器１１２＿ｎへと伝播する。コントローラ部１１１は、移動始点の領域Ａに対応する並列演算器１１２＿ｎへとアクセスし、経路方向情報を順次取得する。すなわち、コントローラ部１１１は、移動始点の領域Ａに対応する並列演算器１１２＿ｎのみにアクセスすることで、経路方向情報の系列を効率的に取得することができる。
【００７０】
ここで、並列演算部１１２内において、移動始点の領域Ａに対する並列演算器１１２＿ｎに全ての経路方向情報を集めるために必要な計算ステップは、経路を構成する領域の個数をｎとした場合に、２ｎ−１となる。並列演算部１１２内で経路方向情報を伝播させずに、コントローラ部１１１が各並列演算器１１２＿ｎに直接アクセスして経路方向情報を取得した場合には、コントローラ部１１１は、各領域にアクセスした都度、上流方向へと向かう領域を選択する処理を全ての領域で行う必要がある。これに対して、本実施の形態１に係る経路方向情報の取得処理では、並列演算部１１２内において、移動始点の領域に対応する並列演算器１１２＿ｎへ向けて各領域の経路方向情報が伝播するために、コントローラ部１１１は、該当の領域のみにアクセスして経路方向情報を取得すれば足りる。すなわち、コントローラ部１１１が並列演算器１１２＿ｎにアクセスして経路方向情報を取得する際に、アクセスした領域から上流方向へと向かう領域を選択する処理を行わずに済むために、コントローラ部１１１が並列演算部１１２にアクセスする際の計算量を削減することができる。
【００７１】
また、コントローラ部１１１は移動始点に対応する並列演算器１１２＿ｎのみから経路方向情報を取得すればよいため、上位のコントローラ部１１１が下位の並列演算部１１２にアクセスするための接続線の本数を抑制することができる。また、複数の並列演算器１１２＿ｎに対して一つの接続線を設け、その接続線を切替えて使用する構成とすることで、必要とする接続線の本数をより抑制することができる。さらに、各並列演算器１１２＿ｎの受信バッファ１１７には、一つの経路方向情報のみを保持しておけばよいため、受信バッファ１１７のコストを抑制することができる。
【００７２】
尚、移動始点に対応する並列演算器１１２＿ｎの受信バッファ１１７のサイズを、経路を構成する経路方向情報の系列全体を保持可能なサイズとした場合には、各並列演算器１１２＿ｎが搭載する受信バッファ１１７のコストは増加するものの、コントローラ部１１１は１度のアクセスにより、経路方向情報の系列全体を取得することができる。このため、並列演算部１１２とコントローラ部１１１との間のアクセス量を削減して、より効率的に経路探索処理を実行することができる。
【００７３】
以上説明したように、本発明は、並列演算を用いて経路探索を高速に計算する手法において、特に、経路を構成する経路方向情報を、各並列演算器１１２＿ｎから効率よく取得する手法に関する。本発明によれば、並列演算器１１２＿ｎ間の局所通信のみを利用することで、コントローラ部１１１は、経路方向情報の系列を効率的に取得することができる。これにより、上位のコントローラ部１１１と下位の並列演算部１１２との間の通信コストを削減することができ、経路探索装置１に係る製造コスト及び計算コストを低減することができる。
【００７４】
尚、上述した各実施の形態では、ロボットが移動する移動領域を経路探索領域として、移動始点から移動終点へと至る経路を探索するものとして説明したが、本発明はこれに限定されない。すなわち、ロボットが移動する移動領域に限らず、通信ネットワークや動力学モデル場において、任意の二点間の最適な経路を探索するための並列演算などに対しても本発明を適用することができる。
【００７５】
尚、本発明は上述した各実施の形態に限定されず、趣旨を逸脱しない範囲で適宜変更することが可能である。
【符号の説明】
【００７６】
１ 経路探索装置、
１１ 経路探索処理部、１２ 経路探索記憶部、
１１１ コントローラ部、１１２＿ｎ 並列演算器、
１１３ 評価値処理部、１１４ 領域選択部、１１５ 経路方向情報生成部、
１１６ 受信部、１１７ 受信バッファ、１１８ 送信部、
１１９ 送信バッファ、
３２＿ｎ 評価値記憶部、３３＿ｎ 評価値記憶部、３４＿ｎ 状態設定用信号線、
Ｃｎ 領域
【特許請求の範囲】
【請求項１】
経路探索領域内に存在する第１の地点から第２の地点に到達する経路を探索する経路探索装置であって、
前記経路探索領域が複数の領域に分割され、分割されたそれぞれの領域に対応する複数の並列演算器から構成される並列演算部と、
前記並列演算部を統括するコントローラ部と、を備え、
前記並列演算部は、
前記複数の並列演算器が並列演算することで、対応するそれぞれの領域の評価値を算出し、
前記並列演算器は、
前記並列演算することで算出した各領域の評価値に基づいて、近傍に存在する領域から一の選択領域を選択する領域選択手段と、
自身に対応する領域から前記選択領域への方向を示す経路方向情報を生成する経路方向情報生成手段と、
他の前記並列演算器から送信された経路方向情報を受信する受信手段と、
前記選択領域に対応する前記並列演算器に対して、前記受信手段で受信した前記経路方向情報を送信した後に、前記経路方向情報生成手段で生成した前記経路方向情報を送信する送信手段と、を備え、
前記コントローラ部は、
前記第２の地点を含む領域に対応する第２の並列演算器から前記経路方向情報の送信を最初に開始させた後に、前記並列演算部内で伝播した前記経路方向情報の系列を、前記第１の地点を含む領域に対応する第１の並列演算器から取得することで、前記経路を探索する
ことを特徴とする経路探索装置。
【請求項２】
前記並列演算器は、
前記受信手段で受信した他の前記並列演算器から送信された経路方向情報を保持する受信バッファと、
前記受信バッファに保持した前記経路方向情報又は前記経路方向情報生成手段で生成した前記経路方向情報を送信するために保持する送信バッファと、を更に備え、
前記送信手段は、
他の前記並列演算器から送信された経路方向情報を受信した場合には、前記受信バッファに保持した前記経路方向情報を、前記送信バッファを介して前記選択領域に対応する前記並列演算器に送信し、
他の前記並列演算器から送信された経路方向情報を所定の期間受信しなかった場合には、前記経路方向情報生成手段で生成した前記経路方向情報を、前記送信バッファを介して前記選択領域に対応する前記並列演算器に送信する
ことを特徴とする請求項１に記載の経路探索装置。
【請求項３】
前記領域選択手段は、
前記並列演算することで算出した各領域の評価値に基づいて、近傍に存在する領域から、前記第１の地点を含む領域により近づく方向の一の選択領域を選択する
ことを特徴とする請求項１に記載の経路探索装置。
【請求項４】
前記並列演算器は、
近傍に存在する領域の評価値と、当該近傍領域から自身に対応する領域までの移動コストに基づいて評価値を算出する評価値処理部を更に備える
ことを特徴とする請求項１に記載の経路探索装置。
【請求項５】
経路探索領域が複数の領域に分割され、分割されたそれぞれの領域に対応する複数の並列演算器から構成される並列演算部と、前記並列演算部を統括するコントローラ部と、を備える移動体が、前記経路探索領域内に存在する第１の地点から第２の地点に到達する経路を探索する経路探索方法であって、
前記並列演算部が、
前記複数の並列演算器が並列演算することで、対応するそれぞれの領域の評価値を算出し、
前記並列演算器が、
前記並列演算することで算出した各領域の評価値に基づいて、近傍に存在する領域から一の選択領域を選択する領域選択ステップと、
自身に対応する領域から前記選択領域への方向を示す経路方向情報を生成する経路方向情報生成ステップと、
他の前記並列演算器から送信された経路方向情報を受信する受信ステップと、
前記選択領域に対応する前記並列演算器に対して、前記受信した前記経路方向情報を送信した後に、前記生成した前記経路方向情報を送信する送信ステップと、を有し、
前記コントローラ部が、
前記第２の地点を含む領域に対応する第２の並列演算器から前記経路方向情報の送信を最初に開始させた後に、前記並列演算部内で伝播した前記経路方向情報の系列を、前記第１の地点を含む領域に対応する第１の並列演算器から取得することで、前記経路を探索する
ことを特徴とする経路探索方法。
【請求項６】
経路探索領域内に存在する第１の地点から第２の地点に到達する経路を探索する自律移動体であって、
前記経路探索領域が複数の領域に分割され、分割されたそれぞれの領域に対応する複数の並列演算器から構成される並列演算部と、
前記並列演算部を統括するコントローラ部と、を備え、
前記並列演算部は、
近傍に存在する領域の評価値と、当該近傍領域から自身に対応する領域までの移動コストに基づいて、対応するそれぞれの領域の評価値を算出し、
前記並列演算器は、
前記並列演算することで算出した各領域の評価値に基づいて、近傍に存在する領域のうち最も小さい評価値を有する一の選択領域を選択する領域選択部と、
自身に対応する領域から前記選択領域への方向を示す経路方向情報を生成する経路方向情報生成部と、
他の前記並列演算器から送信された経路方向情報を受信する受信部と、
前記選択領域に対応する前記並列演算器に対して、前記受信部で受信した前記経路方向情報を送信した後に、前記経路方向情報生成部で生成した前記経路方向情報を送信する送信部と、を備え、
前記コントローラ部は、
前記第２の地点を含む領域に対応する第２の並列演算器から前記経路方向情報の送信を最初に開始させた後に、前記並列演算部内で伝播した前記経路方向情報の系列を、前記第１の地点を含む領域に対応する第１の並列演算器から取得することで、前記経路を探索する
ことを特徴とする自律移動体。
【請求項１】
経路探索領域内に存在する第１の地点から第２の地点に到達する経路を探索する経路探索装置であって、
前記経路探索領域が複数の領域に分割され、分割されたそれぞれの領域に対応する複数の並列演算器から構成される並列演算部と、
前記並列演算部を統括するコントローラ部と、を備え、
前記並列演算部は、
前記複数の並列演算器が並列演算することで、対応するそれぞれの領域の評価値を算出し、
前記並列演算器は、
前記並列演算することで算出した各領域の評価値に基づいて、近傍に存在する領域から一の選択領域を選択する領域選択手段と、
自身に対応する領域から前記選択領域への方向を示す経路方向情報を生成する経路方向情報生成手段と、
他の前記並列演算器から送信された経路方向情報を受信する受信手段と、
前記選択領域に対応する前記並列演算器に対して、前記受信手段で受信した前記経路方向情報を送信した後に、前記経路方向情報生成手段で生成した前記経路方向情報を送信する送信手段と、を備え、
前記コントローラ部は、
前記第２の地点を含む領域に対応する第２の並列演算器から前記経路方向情報の送信を最初に開始させた後に、前記並列演算部内で伝播した前記経路方向情報の系列を、前記第１の地点を含む領域に対応する第１の並列演算器から取得することで、前記経路を探索する
ことを特徴とする経路探索装置。
【請求項２】
前記並列演算器は、
前記受信手段で受信した他の前記並列演算器から送信された経路方向情報を保持する受信バッファと、
前記受信バッファに保持した前記経路方向情報又は前記経路方向情報生成手段で生成した前記経路方向情報を送信するために保持する送信バッファと、を更に備え、
前記送信手段は、
他の前記並列演算器から送信された経路方向情報を受信した場合には、前記受信バッファに保持した前記経路方向情報を、前記送信バッファを介して前記選択領域に対応する前記並列演算器に送信し、
他の前記並列演算器から送信された経路方向情報を所定の期間受信しなかった場合には、前記経路方向情報生成手段で生成した前記経路方向情報を、前記送信バッファを介して前記選択領域に対応する前記並列演算器に送信する
ことを特徴とする請求項１に記載の経路探索装置。
【請求項３】
前記領域選択手段は、
前記並列演算することで算出した各領域の評価値に基づいて、近傍に存在する領域から、前記第１の地点を含む領域により近づく方向の一の選択領域を選択する
ことを特徴とする請求項１に記載の経路探索装置。
【請求項４】
前記並列演算器は、
近傍に存在する領域の評価値と、当該近傍領域から自身に対応する領域までの移動コストに基づいて評価値を算出する評価値処理部を更に備える
ことを特徴とする請求項１に記載の経路探索装置。
【請求項５】
経路探索領域が複数の領域に分割され、分割されたそれぞれの領域に対応する複数の並列演算器から構成される並列演算部と、前記並列演算部を統括するコントローラ部と、を備える移動体が、前記経路探索領域内に存在する第１の地点から第２の地点に到達する経路を探索する経路探索方法であって、
前記並列演算部が、
前記複数の並列演算器が並列演算することで、対応するそれぞれの領域の評価値を算出し、
前記並列演算器が、
前記並列演算することで算出した各領域の評価値に基づいて、近傍に存在する領域から一の選択領域を選択する領域選択ステップと、
自身に対応する領域から前記選択領域への方向を示す経路方向情報を生成する経路方向情報生成ステップと、
他の前記並列演算器から送信された経路方向情報を受信する受信ステップと、
前記選択領域に対応する前記並列演算器に対して、前記受信した前記経路方向情報を送信した後に、前記生成した前記経路方向情報を送信する送信ステップと、を有し、
前記コントローラ部が、
前記第２の地点を含む領域に対応する第２の並列演算器から前記経路方向情報の送信を最初に開始させた後に、前記並列演算部内で伝播した前記経路方向情報の系列を、前記第１の地点を含む領域に対応する第１の並列演算器から取得することで、前記経路を探索する
ことを特徴とする経路探索方法。
【請求項６】
経路探索領域内に存在する第１の地点から第２の地点に到達する経路を探索する自律移動体であって、
前記経路探索領域が複数の領域に分割され、分割されたそれぞれの領域に対応する複数の並列演算器から構成される並列演算部と、
前記並列演算部を統括するコントローラ部と、を備え、
前記並列演算部は、
近傍に存在する領域の評価値と、当該近傍領域から自身に対応する領域までの移動コストに基づいて、対応するそれぞれの領域の評価値を算出し、
前記並列演算器は、
前記並列演算することで算出した各領域の評価値に基づいて、近傍に存在する領域のうち最も小さい評価値を有する一の選択領域を選択する領域選択部と、
自身に対応する領域から前記選択領域への方向を示す経路方向情報を生成する経路方向情報生成部と、
他の前記並列演算器から送信された経路方向情報を受信する受信部と、
前記選択領域に対応する前記並列演算器に対して、前記受信部で受信した前記経路方向情報を送信した後に、前記経路方向情報生成部で生成した前記経路方向情報を送信する送信部と、を備え、
前記コントローラ部は、
前記第２の地点を含む領域に対応する第２の並列演算器から前記経路方向情報の送信を最初に開始させた後に、前記並列演算部内で伝播した前記経路方向情報の系列を、前記第１の地点を含む領域に対応する第１の並列演算器から取得することで、前記経路を探索する
ことを特徴とする自律移動体。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【公開番号】特開２０１０−２５７１１５（Ｐ２０１０−２５７１１５Ａ）
【公開日】平成２２年１１月１１日（２０１０．１１．１１）
【国際特許分類】
【出願番号】特願２００９−１０５０４７（Ｐ２００９−１０５０４７）
【出願日】平成２１年４月２３日（２００９．４．２３）
【出願人】（０００００３２０７）トヨタ自動車株式会社 (59,920)
【Ｆターム（参考）】
【公開日】平成２２年１１月１１日（２０１０．１１．１１）
【国際特許分類】
【出願日】平成２１年４月２３日（２００９．４．２３）
【出願人】（０００００３２０７）トヨタ自動車株式会社 (59,920)
【Ｆターム（参考）】
[ Back to top ]