(57)【特許請求の範囲】
【請求項１】
移動体の経路生成を行う移動体の経路生成装置であって、
移動体が移動する範囲を分割した複数のエリアにそれぞれ配置された複数の経路計算装置を備え、
該各経路計算装置は、前記経路生成の際に参照する自エリア情報を含む情報を有しており、隣接する他の経路計算装置と通信可能であり、
前記移動体は、最寄りの前記経路計算装置に探索信号を送り、探索信号は、該経路計算装置が配置されたエリアへの前記移動体の進入時刻を含み、
探索信号を受けた前記経路計算装置は、
該経路計算装置が配置されたエリアに該移動体が進入してから通過するまでの滞在時間を算出し、
探索信号に含まれる進入時刻と該滞在時間の合計値として設定された新たな進入時刻を含む探索信号を、隣接するエリアで直前のエリア以外のエリアに配置された前記経路計算装置へ送信し、
前記複数の経路計算装置の連携により前記移動体の目的地までの経路探索を実施して、経路探索結果を前記移動体に送信する、ことを特徴とする移動体の経路生成装置。
【請求項２】
前記経路計算装置は、対応するエリア内の状況を監視する外界センサを備え、
該外界センサからの情報を、前記経路探索を実施する前記自エリア情報に反映することが可能である、ことを特徴とする請求項１に記載の移動体の経路生成装置。
【請求項３】
前記経路計算装置は、対応するエリア内の状況について、人が入力できるインタフェースを有する、ことを特徴とする請求項１乃至請求項２のいずれかに記載の移動体の経路生成装置。
【請求項４】
前記経路探索結果は、最も先に前記経路探索が完了した経路を設定する、ことを特徴とする請求項１乃至請求項３のいずれかに記載の移動体の経路生成装置。
【請求項５】
前記経路探索結果は、設定時間内に完了した前記経路探索の中で最も目的地までの所要時間が短い経路を設定する、ことを特徴とする請求項１乃至請求項３のいずれかに記載の移動体の経路生成装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、広域を移動する移動体の移動経路についての指示を与える経路生成装置に関する。
【背景技術】
【０００２】
ロボットなどの移動体を特定の目的地に移動させる方法について、第１に、移動体が稼動するエリアの地図上で移動体の通過点となるノードと、各ノード間の連結関係を示すリンクを定義したグラフデータを作成し、第２に、そのグラフデータを使った経路探索により最短経路を算出する、といった方法が一般的に使用されている。具体的にはＡスター法やダイクストラ法などが知られている。
【０００３】
上記方法によって、最短経路を算出するにあたり、経路探索を行う度に、全てのグラフデータにアクセスする必要がある。
そのため、グラフデータは移動体や集中管理装置にまとめて保管されるのが一般的である。
【０００４】
ここで、経路探索は、「移動体が目的地に到達するまでの所要時間」が最も短い経路を探索するものである。
そのため、移動距離が短い経路であっても、旋回を多用する経路や、他の移動体とすれ違う経路は必ずしも最短とはならない。
かかる点を考慮した技術について、以下の特許文献１〜３が既に知られている。
【０００５】
特許文献１に記載の発明は、各ノードに旋回時間を加味した所要時間を定義しておく方法であり、特許文献２に記載の発明は、移動体が複数台存在することを想定して、移動体が計画した経路データ（各エリアへの進入予定時刻なども含む）を、全移動体の経路と比較し、移動体の干渉、すれ違いを極力回避するものである。
【０００６】
また、移動体の移動時間を左右する要因として、移動体の旋回やすれ違い等の移動体自身の事象だけでなく、ドア通過の有無やエレベータ使用の有無など、各エリア特有のものも存在する。そのため、特許文献３に記載の発明では、ドアの通過など、通過に必要な情報をリンクごとに設定できるようになっている。
【０００７】
【特許文献１】特開平１１−２４９７３８号公報、「自動搬送車の最短経路探索方法及びその装置」
【特許文献２】特開２００５−２４２４８９号公報、「自律移動体の運行制御システム及びプログラム」
【特許文献３】特開２００６−２５９９６３号公報、「移動ロボットの経路生成装置」
【発明の開示】
【発明が解決しようとする課題】
【０００８】
経路探索を行うにあたって、移動体がノード間を移動する方法として、移動体に搭載したセンサ（カメラやモータエンコーダなどが用いられる）によって、移動体の地図上の位置や姿勢を計測し、通過点となる次のノードに向かうように駆動させるのが一般的である。
ここで用いる地図は、エリアの形状やランドマークの配置を記載した環境地図と呼ばれるもので、移動体や集中管理装置に保持させる方法が一般的である。
【０００９】
しかし、従来技術においては、全体のグラフデータや環境地図を１ヶ所にまとめて保持しているため、データ構造を工夫した形で保持していても、地図の一部を変更する際の操作ミスや、メモリの不足などで、全てのデータが破壊される危険があった。
さらに、地図を記憶する装置に欠陥が生じた場合、原因究明及び問題解決作業のために、システム全体を停止する必要があった。
加えて、データ更新が正常になされたかどうかの確認作業も、全ての移動体で行う必要があり、地図情報の変更に膨大な手間がかかるという問題点があった。
【００１０】
また、各エリアを移動体が通過するための所要時間は、エリアの路面状況、人やその他障害物の有無などの影響を受けて、時間的に変化することが多いが、上記特許文献では、旋回にかかる時間などをあらかじめ設定しておく必要があり、路面状況の時間的な変化などに対応できないといった点や、移動体以外の要因について考慮されず、人やその他の機械が介在するエリアでは最短経路が得られない場合等には、エリア情報を逐次反映して柔軟に経路探索することができないといった問題点があった。
【００１１】
一方で、全体のグラフデータを１ヶ所で保持する理由は、探索時に最短経路を導出するためにあるが、場合によっては、必ずしも完全な最短経路を求める必要はなく、準最短経路であっても探索時間を短くする場合や、設定時間内で探索を完了させたいという要求がある場合も考えられる。
【００１２】
本発明は上述した問題点に鑑みて創案されたものである。すなわち、本発明の目的は、データ保全及びデータ修正の容易性を確保し、かつ、変化するエリア情報を逐次反映した形で柔軟な経路探索を行う経路生成装置を提供することにある。
【課題を解決するための手段】
【００１３】
本発明によれば、移動体の経路生成を行う移動体の経路生成装置であって、
移動体が移動する範囲を分割した複数のエリアごとに配置された複数の経路計算装置を備え、
該各経路計算装置は、前記経路生成の際に参照する自エリア情報を含む情報を有しており、
隣接する他の経路計算装置及び対応するエリア内の移動体と通信可能であり、
前記移動体からの経路探索依頼を受信し、
前記複数の経路計算装置の連携により前記移動体の目的地までの前記経路探索を実施して、経路探索結果を前記移動体に送信する、ことを特徴とする移動体の経路生成装置が提供される。
【００１４】
本発明によれば、前記経路計算装置は、対応するエリア内の状況を監視する外界センサを備え、
該外界センサからの情報を、前記経路探索を実施する前記自エリア情報に反映することが可能である。
【００１５】
本発明によれば、前記経路計算装置は、対応するエリア内の状況について、人が入力できるインタフェースを有する。
【００１６】
本発明によれば、前記経路探索結果は、最も先に前記経路探索が完了した経路を設定する。
【００１７】
また、別の実施例によれば、設定時間内に完了した前記経路探索の中で最も目的地までの所要時間が短い経路を設定する。
【発明の効果】
【００１８】
上記本発明によれば、必要なデータを分散管理することによって、データ保全及びデータ修正の容易性を確保し、かつ、エリアごとに配置された経路計算装置によって、エリア状況を常に監視可能であるため、変化するエリア情報を反映して柔軟に経路探索を行うことができる経路生成装置を提供することができる。
【図面の簡単な説明】
【００１９】
【図１】本発明における想定エリア及びグラフデータの模式図である。
【図２】本発明における自エリア情報の例による模式図である。
【発明を実施するための形態】
【００２０】
以下、本発明の好ましい実施例を図面を参照して説明する。なお、各図において共通する部分には同一の符号を付し、重複した説明を省略する。
【００２１】
図１は本発明における想定エリアの模式図である。
図１（Ａ）は、本発明におけるグラフデータの模式図であり、図１（Ｂ）は、本発明における経路生成装置の模式図である。
この図において、１はエリア、２はノード、３はリンク、４は移動体、５は経路生成装置、５ａは経路計算装置、５ｂは通信路である。
【００２２】
移動体が稼動する範囲をエリア１に分割して、各エリア１に対応してノード２を定義する。
ノード２を定義することによって、各エリア１を擬似的に点として扱うことができるため、プログラム等による計算を容易にすることができる。
そのため、最終的に得られる経路探索結果の精度を高めるためには、各エリア１をより詳細に分割して行う必要がある。
【００２３】
ノード２間について、移動体４が移動可能な経路が存在する場合に、リンク３として定義する。
リンク３は、各エリア１間を結ぶ擬似的な線として扱うことができるため、上記ノード２の定義と同様に、プログラム等による計算を容易にすることができる。
【００２４】
移動体４は、この例においては、ロボット等の自律稼動が可能な装置を想定している。
【００２５】
経路生成装置５は、移動体４からの要求に応じて、その時間における各エリア１の状況を考慮に含めた現在位置から目的位置までの経路を生成する。
詳細な経路生成手順については後述する。
さらに、ノード２として定義した各エリア１内に、それぞれ経路計算装置５ａを配置する。
経路計算装置５ａは、経路生成装置５をエリア１ごとに配置できるように分割したものである。各エリア１にそれぞれ経路計算装置５ａを配置することによって、それぞれの経路計算装置５ａが、各エリア１についての状況について監視を行い、経路生成に反映させることができる。
各エリア１に配置された経路計算装置５ａがそれぞれ隣接する経路計算装置５ａと連携を取ることによって、移動体４からの要求に従った経路生成を行うことになる。
【００２６】
経路計算装置５ａは、対応するエリアのノードＩＤである「ノードＩＤ」、隣接するノード２へ向かうリンク３が存在しているか否かの情報についての「リンク情報」、エリア内において移動に影響の出る凹凸等の形状や障害物等の情報についての「自エリア情報」、詳細については後述する「探索信号」及び「予約情報」のデータを有している。
なお、経路計算装置５ａは、隣接する全ての経路計算装置５ａと通信路５ｂによって接続しており、最低でも直接隣接する全ての経路計算装置５ａと通信することができる。
また、経路計算装置５ａは、対応するエリア内に存在する移動体４と通信できる。
なお、自エリア情報は、例えば、「環境地図」「エリア内の制限速度」「標準的なエリアの通過所要時間」「通過所要時間を左右するさまざま要因（障害物・人・路面状況など）」等からなる。
【００２７】
図２は、自エリア情報の例による模式図である。
この図において、１１は壁、１２は他の移動体、１３は障害物、１４はエリア入口、１５はエリア出口である。
経路計算装置５ａは、移動体４通過時において変更されることがないと考えられる壁１１、障害物１３、エリア入口１４、エリア出口１５の情報、及び移動体４通過時においては変更される可能性が考えられる他の移動体１２の情報について「自エリア情報」として保持している。
移動体４が、かかるエリア１を通過する際に、経路計算装置５ａから上記自エリア情報を受け取って、この情報を元にエリア内における移動方法を策定し、移動を行っていく。
【００２８】
なお、経路計算装置５ａは、外界センサ（図示しない）を有しており、対応するエリアの状況（路面状況、人の有無、障害物など）を監視し、移動体４の通過所要時間算出に反映させる形でもよい。
かかる場合には、環境地図や移動体の通過所要時間を自動更新するため、各エリアの状況に合わせた柔軟な経路探索ができるというメリットを有する。
【００２９】
さらに、上記対応するエリアの状況について、人が操作できる入力インタフェースを持ち、対応するエリアの情報（進入可否、センサで計測できない情報など）を人が簡単に更新できるようにする形でもよい。
かかる場合には、外界センサなどで計測するのが難しいエリア情報を、人手によって更新することができるというメリットがある。
【００３０】
移動体４が稼動する際における、経路の計画及び移動は以下の手順で行う。
（１）移動体４が最寄りの経路計算装置５ａに探索信号を送る。探索信号には、「信号ＩＤ」「探索開始ノード」「探索目標ノード」「自ノード前後の探索経路」「進入時刻」「滞在時間」が含まれる。
「信号ＩＤ」は、探索信号ごとに一意の値を設定した信号ＩＤである。
「探索開始ノード」は、移動体４が移動開始する際のエリアについてのノードＩＤである。
「探索目標ノード」は、移動体４の移動目的地のエリアについてのノードＩＤである。
「自ノード前後の探索経路」は、対応するエリアのノードＩＤを示す「自ノードＩＤ」、移動体４が直前に通過したエリアのノードＩＤを示す「直前ノードＩＤ」、移動体４が次に通過するエリアのノードＩＤを示す「直後ノードＩＤ」からなる。
「進入時刻」は、移動体４が対応するエリアに進入してきた時刻を示している。
「滞在時間」は、移動体４が対応するエリアに進入してから通過するまでの時刻を示している。
（２）探索信号を受け取った経路計算装置５ａは、新たに探索信号を作成する。
その際、各情報は以下のように設定を行う。
ア）「自ノード前後の探索経路」
「直前のノードＩＤ」には、受け取った探索信号に記載されている自ノードＩＤを設定する。
「自ノードＩＤ」には、自ノードＩＤを設定する。
「直後のノードＩＤ」には、隣接するノードで直前のノード以外のノードＩＤを、それぞれ新たに設定する。
なお、この場合において、直後のノードＩＤの候補が複数ある場合には、その数だけ探索信号を複製する。
イ）「進入時刻」
受け取った探索信号に記載されている「進入時刻」と「滞在時間」の合計値を、新たに「進入時刻」に設定する。
ウ）「滞在時間」
上記設定した「進入時刻」における、エリアに滞在する他の移動体や障害物有無の情報等を反映した「環境地図」を作成し、移動体４の通過をシミュレートし、「滞在時間」を算出する。
または、当該エリアにおける移動体の有無、移動体の滞在時間などと数値化した表を予め用意しておく方法、カメラに映っている人数を集計して移動体の走行速度を算出し、滞在時間を計算する方法、或いは、路面の状況（滑りやすさ等）を検出するセンサの情報を用いて、移動体の走行速度を算出し、滞在時間を計算する方法を採用する形でもよい。
（３）各経路計算装置５ａは、上記手順によって作成した新たな探索信号を、隣接するノードで直前のノード以外のノードに送信する。このようにして、探索信号がエリア全体に伝播していくことになる。
（４）「探索目標ノード」に指定されている生成装置は、直前のノードから探索信号を受け取った場合には、探索成功信号を返信する。
返信先は、探索信号の「自ノード前後の探索経路」中の直前のノードＩＤとする。同様に各装置が探索成功信号を探索元まで返信する。
探索成功信号には、「信号ＩＤ」と「全体所要時間」が含まれる。探索成功信号と対応する探索信号の関連付けには、探索信号ごとに一意の値に設定した信号ＩＤを使う。
（５）上記（２）において、直後のノードＩＤに指定する候補が無い場合、行き止まりとする。
「探索開始ノード」、「探索目標ノード」が同一で、「進入時刻」が異なる複数の探索信号を受信した場合、「進入時刻」の遅い探索経路は探索失敗とする。
行き止まりや、探索失敗を検出した経路計算装置５ａは、探索失敗信号を返信する。
探索失敗信号を受信した経路計算装置５ａは、該当する探索信号を削除する。次に、上記（２）で複製した全ての探索信号が削除された場合は、行き止まりと同じ扱いとして、探索失敗信号を返信する。
上記の探索失敗信号の返信先は、直前のノードＩＤとする。従って、探索成功信号と同様に、探索失敗信号も探索元まで伝播される。
（６）探索成功信号を受信した経路計算装置５ａは、該当する探索信号を「予約情報」として記録し、移動体４の進入時刻・滞在時間を、その後の上記（２）に反映させる。予約情報は、探索信号と同じ内容とする。
また、「信号ＩＤ」が同一で、「全体所要時間」が異なる探索成功信号を受信した場合は、全体所要時間の長い「予約情報」を削除し、直後のノードＩＤに対して「予約情報」のキャンセル信号を送信する。
【００３１】
上記の（１）〜（６）によって、探索開始ノードに探索成功信号が届くと、移動体４が「予約情報」に従って移動する。この時移動体４は、最寄りの経路計算装置５ａから「環境地図」を取得し、それを用いて移動する。
【００３２】
本発明において、各経路計算装置５ａは、エリアごとに固有の情報を設定できるため、それに応じた柔軟な経路探索ができる。
また、一部のエリア情報を変更する際、そのエリアを担当する経路計算装置５ａを変更するだけでよいので、他のエリア情報に影響を与えないことが保証されている。
さらに、一部の経路計算装置５ａが故障しても、他のエリアには影響がなく、他のエリアを通る経路探索は遂行されることになる。
【００３３】
なお、本発明は、ロボット以外の移動体（自動車や歩行者など）への移動支援（ナビゲーション）にも利用可能である。
【００３４】
なお、本発明は上述した実施の形態に限定されず、本発明の要旨を逸脱しない範囲で種々の変更を加え得ることは勿論である。
【符号の説明】
【００３５】
１  エリア、２  ノード、３  リンク、４  移動体、５  経路生成装置、
５ａ  経路計算装置、５ｂ  通信路、１１  壁、１２  他の移動体、
１３  障害物、１４  エリア入口、１５  エリア出口
【図１】
0005614156.tif 000002
【図２】
0005614156.tif 000003