JP4241673B2 - 移動体の経路生成装置 - Google Patents

Description

本発明は、移動体の移動経路を自動的に生成する装置に関する。より詳細には、本発明は、対象空間内のオブジェクトの位置関係およびローカルミニマム判別に基づく人工ポテンシャルを利用した経路生成装置に関する。

移動体のナビゲーション技術の一つとして、人工ポテンシャル法が知られている（たとえば非特許文献１を参照）。この手法は、ナビゲーションを行う対象空間内にポテンシャル場を形成し、そのポテンシャル場の勾配に基づく目標点までの全体経路を獲得する。移動経路は、現在位置近傍のポテンシャル最小点を探索する処理を繰り返すことにより生成される。人工ポテンシャル法は、対象空間内において、自動的かつ柔軟な経路を生成できるという点で、グラフ探索法などの従来手法よりも優れている。

しかし、人工ポテンシャル法は、その原理上、ナビゲーションを行う対象空間のポテンシャル場の構造によっては、移動経路の探索が途中でローカルミニマムに収束してしまい、最終目標点までの移動経路が生成できない場合がある。

このようなローカルミニマムの問題を回避するために、ラプラスポテンシャルを用いた経路計画法も知られている（たとえば非特許文献２を参照）。ラプラスポテンシャル法では、ナビゲーションを行う対象空間に対して、ポテンシャル計算のための複数のセルをグリッド状に設定し、各セルに対してラプラス微分方程式を用いた計算を行う。

しかし、ラプラスポテンシャル法は、ポテンシャル場全体で極小点が１つになり、その極小点が目標点と一致するまで繰り返し計算を行う必要がある。そのため、対象空間の構造によって、計算処理に非常に時間がかかってしまい、高速な経路計画、移動体の誘導、および経路変更ができないという問題がある。
O. Khatib, "Real-Time Obstacle Avoidance for manipulators and Mobile Robots", International Journal of Robotics Research, 51, pp. 90-98, 1986 E. Rimon, D. E. Koditscheck, "Exact Robot Navigation using Artificial Potential Functions", IEEE Transactions Robotic and Automation, Vol. 8, No. 5, pp. 501-518, 1992

本発明の目的は、人工ポテンシャル法におけるローカルミニマムの問題を回避し、高速な経路計画を実現するための経路生成装置を提供することである。

本発明は、移動空間内で移動体の移動経路を自律的に生成するための経路生成装置を提供する。この装置は、移動体の初期位置および目標とする位置、並びに障害物の位置および形状を含む情報に基づき移動空間内のマップを生成するマップ生成部と、マップを用いて、移動体、障害物、および目標とする位置の相対位置関係に基づく引力ポテンシャルおよび斥力ポテンシャルを計算し、該引力ポテンシャルおよび該斥力ポテンシャルの和である合成ポテンシャルを生成する合成ポテンシャル生成部と、合成ポテンシャルに基づいてマップ内の経路探索を行い、該経路探索の収束位置が目標とする位置ではないローカルミニマムかどうかを判別するローカルミニマム判別部と、収束位置がローカルミニマムであると判別された場合、該収束位置のポテンシャルを所定値だけ増加させた仮想ポテンシャルを生成する仮想ポテンシャル生成部と、収束位置がローカルミニマムではなく目標とする位置であると判別された場合、経路探索の結果に基づいて移動体の移動経路を生成する経路生成部と、を備える。なお、仮想ポテンシャル生成部で生成された仮想ポテンシャルは、合成ポテンシャルに加算される。

この発明により、ローカルミニマム問題を回避することができ、局所的な領域の比較演算だけで探索ができるので、高速な経路探索が可能となる。

本発明の一実施形態では、経路生成装置は、移動体、障害物および目標とする位置にある目標物に取り付けられたタグの信号からこれらの位置および形状の情報を識別するタグ情報検出装置をさらに備える。

本発明の一実施形態では、タグは、目標物および移動可能な障害物に適用されるＲＦ−ＩＤタグと、移動体および固定された障害物に適用される超音波タグとを含む。

また、本発明は、さらに移動空間内で移動体の移動経路を自律的に生成するためのプログラムを提供する。このプログラムは、メモリに記憶され、移動体の初期位置および目標とする位置、並びに障害物の位置および形状を含む情報に基づき移動空間内のマップを生成する機能と、マップを用いて、移動体、障害物、および目標とする位置の相対位置関係に基づく引力ポテンシャルおよび斥力ポテンシャルを計算し、該引力ポテンシャルおよび該斥力ポテンシャルの和である合成ポテンシャルを生成する機能と、合成ポテンシャルに基づいてマップ内の経路探索を行い、該経路探索の収束位置が目標とする位置ではないローカルミニマムかどうかを判別する機能と、収束位置がローカルミニマムであると判別された場合、該収束位置のポテンシャルを所定値だけ増加させた仮想ポテンシャルを生成し、合成ポテンシャルに足し合わせる機能と、収束位置がローカルミニマムではなく目標とする位置であると判別された場合、経路探索の結果に基づいて移動体の移動経路を生成する機能と、をコンピュータに実行させる。

本発明の一実施形態では、このプログラムは、移動体、障害物および目標とする位置にある目標物に取り付けられたタグの信号から、移動体の初期位置および目標とする位置、並びに障害物の位置および形状を含む情報を識別する機能をさらに備える。

本発明は、従来の人工ポテンシャル法におけるローカルミニマムの問題を解消するために提案されているラプラスポテンシャル法とは異なり、探索空間に設定された全セルにおいてラプラス微分方程式を計算し収束させる必要がない。本発明による装置またはプログラムは、限定された探索域（現在位置近傍の８点）だけの比較演算の繰り返しで収束させることができるので、移動経路の高速な探索が可能である。

以下、図面を参照して本発明の実施形態を説明する。図１は、本発明の一実施形態による経路生成装置２９を含む移動ロボット１１のナビゲーションシステムを示す概略図である。

このシステムは、住居内を模擬した移動空間１０において、移動ロボット１１が目標物１７に到達できる最適な移動経路を生成して移動ロボット１１を案内する。移動ロボット１１と目標物１７との間には通行の妨げになる障害物が存在している。目標物１７および障害物には２種類あり、一方は、例えば椅子やコップなどの日常生活において頻繁にその位置が移動させられる移動物１３であり、他方は、例えば箪笥や食器棚などの通常は移動しない固定物１５である。

ここで、目標物１７および障害物は相対的な表現であり、特定のオブジェクトへの移動やそれに対する作業指示などのタスクが移動ロボット１１に与えられた場合、当該オブジェクトは目標物１７として認識される。また、移動ロボット１１の移動や作業動作に障害となる移動空間内１０のオブジェクトは障害物１３，１５と認識される。

移動ロボット１１は、2足歩行または車輪走行などの移動手段を備えており自律移動が可能である。また、移動ロボット１１は、通信装置３１と無線ＬＡＮで接続されており、通信装置３１から受け取った移動経路の情報に基づいて移動空間１０内を移動する。

移動空間１０内に配置された全てのオブジェクト（移動障害物１３、固定障害物１５、移動ロボット１１、および目標物１７が含まれる）には、オブジェクトの種類、形状および重量などの当該オブジェクトに関する情報を、ＩＤを介して提供／認識するためのタグ１９，２１が取り付けられている。タグ１９，２１は、オブジェクトの種類によって超音波タグ１９とＲＦ−ＩＤタグ２１の２種類を使い分ける。

超音波タグ１９は、タグから発信する超音波によってタグの３次元位置を高精度（cmオーダー）で算出することができる。タグ自体からアクティブに超音波を発信するため、超音波タグ１９は電源を備えるか外部電源に接続できる環境が必要である。また、超音波タグ１９自体のサイズも比較的大きなものとなりがちである。このため、超音波タグ１９は、外部電源に接続しやすい固定障害物１５と、自己電源を有し、かつ、経路追従のために高精度な自己位置検知が必要な移動ロボット１１に適用されている。超音波タグシステムは、20kHz以上の周波数帯域を使用する（例えば40kHz程度）。この周波数帯域は、通信環境などに応じて良好な位置検出ができるように適宜選択されたものが使用される。

ＲＦ−ＩＤタグ２１は、天井に取り付けられたＲＦ−ＩＤアンテナ２５から受けた電波により起電し、そのＩＤ情報をアンテナ２５に返すパッシブ型のタグである。ＲＦ−ＩＤタグ２１は、電源を必要としないので超音波タグ１９に比べてはるかに小型な装置で構成可能であり、利便性に優れるが、システムの性質上、位置検知の精度は超音波タグシステムに比して低くなる傾向にある。したがって、ＲＦ−ＩＤタグ２１は、設置可能領域が小さく、電源が取りづらい移動障害物１３と目標物１７に適用されている。なお、ＲＦ−ＩＤタグシステムに用いる周波数帯域としては、例えば13.56MHzや950MHz、2.45GHz等が考えられる。

ここで一般に超音波は直進性に優れるが、間に障害物が存在する場合に通信が困難となってしまうというオクルージョンの問題を有し、オクルージョン問題に対応可能という点ではＲＦ−ＩＤシステムの方が優れている。したがって、タグとして超音波タグ１９を用いるかＲＦ−ＩＤタグ２１を用いるかは、電源取得の容易性、移動頻度、使用位置などに応じて適宜選択されるものとする。また、各タグの取り付け位置や取り付け数は、オブジェクトのサイズや形状、各位置における通信の質などを考慮して決定される。例えば、壁に面して設置された食器棚については、壁から離れた四隅にそれぞれ超音波タグ１９を設置すれば、移動ロボット１１がその近傍を通過する際に、障害物エリアを良好に確認できる。

移動空間１０の天井には、超音波タグ１９の電波を受信するための超音波受信機２３と、ＲＦ−ＩＤタグ２１の電波を受信するＲＦ−ＩＤアンテナ２５が、グリッド状に配置されている。これらの間隔は移動空間１０のサイズや形状、超音波タグシステムおよびＲＦ−ＩＤタグシステムの送受信可能距離、移動空間１０内のオブジェクトの数などに応じて、漏れなく高効率に位置検出や経路生成ができるように適宜決定される。本実施形態では、超音波受信機２３とＲＦ−ＩＤアンテナ２５が、５０cm間隔のグリッド状に交互に配置されている。

タグ１９，２１から発信される電波は微弱であったり、指向性があったりするため、特定のタグ１９，２１の信号を天井に設置されている全ての超音波受信機２３またはＲＦ−ＩＤアンテナ２５で検知することはできない。各々のタグ１９，２１の信号は、そのタグ１９，２１の位置近傍の超音波受信機２３またはＲＦ−ＩＤアンテナ２５により受信され、これらの超音波受信機２３またはＲＦ−ＩＤアンテナ２５の位置関係に基づき当該タグ１９，２１が設置されたオブジェクトの位置が算出される。なお、超音波タグシステムおよびＲＦ−ＩＤタグシステムによるオブジェクトの位置算出手法は周知であり、本発明の要部ではないのでその詳細な説明は省略する。

タグ情報検出装置２７は、超音波受信機２３およびＲＦ−ＩＤアンテナ２５が検知したタグ信号を受け取り、タグ信号の受信状況からタグ１９，２１の位置を特定し、タグ信号に含まれるＩＤ情報から対象オブジェクトの種類、形状などのオブジェクト固有情報を読み取る。タグ１９，２１の位置情報およびＩＤに基づくオブジェクトの固有情報は、後述する経路生成装置２９が有するタグデータベース４５に格納され、必要に応じてマップ生成部４１に与えられる。

本発明である経路生成装置２９は、移動空間１０内のタグ１９，２１の位置情報およびＩＤに基づくオブジェクトの固有情報を受け取ると、移動ロボット１１が障害物１３，１５を回避して目標物１７のある目標位置に到達する最適な経路を生成する。このとき、何らかのタスクが移動ロボット１１に与えられることをトリガとして、経路生成装置２９は、目標位置までの最適経路の探索を開始する。

例えば、移動ロボット１１に目標物１７まで移動しろ、とのタスクが与えられた場合、移動ロボット１１はタスクの指令の中から当該タスクの目標物１７となるオブジェクトのタグIDの情報を抽出し、通信装置３１を介して経路生成装置２９に目標物１７のタグIDの情報を伝達する。本発明の要部である経路生成装置２９は、目標物１７のタグIDの情報をロボット１１から受け取ると、タグ情報検出装置２７から得た各オブジェクトのタグ情報に基づき、移動ロボット１１の最適な移動経路を探索／決定する。そして、経路生成装置２９が決定した経路が通信装置３１を介して移動ロボット１１に伝えられると、移動ロボット１１は、超音波タグシステムと自己の視覚システムを利用しながら、その移動経路に沿って目標物１７の位置まで移動する。

なお、本実施形態では、目標物１７のタグIDの情報はタスク指令に含まれているが、他の手段で移動ロボット１１に目標物１７のタグIDの情報を与える構成にしても良い。例えば、ユーザがタッチパネルなどを利用して目標物１７となるオブジェクトを指定したり、目標物１７の特徴（色、形状、名称など）を音声でロボット１１に与えてその特徴に適合するオブジェクトをデータベースから検索するなどの手段で、目標物１７となるオブジェクトのタグIDの情報をロボット１１に獲得させることも可能である。

また、本発明では、経路探索法として従来技術である人工ポテンシャル法を改良した手法を用いる。詳細については後述する。

通信装置３１は、経路生成装置２９によって生成された最適な移動経路の情報を移動ロボット１１に送信する。情報の送信手法としては、例えば無線LANが適用される。移動ロボット１１は、受け取った経路情報に従って目標位置へ移動する。

タグ情報検出装置２７、経路生成装置２９、および通信装置３１は、ハードウェアで実現することができる。また、タグ情報検出装置２７および経路生成装置２９は、ソフトウェアプログラムで当該機能を実現することも可能である。タグ情報検出装置２７、および通信装置３１は、経路生成装置２９に含まれても良い。また、タグ情報検出装置２７と経路生成装置２９の少なくとも一方が、移動ロボット１１に一体化された構成としても良い。

続いて図２を参照して、本発明である経路生成装置２９による移動ロボット１１の最適経路の探索手法について説明する。図２は、本実施形態による経路生成装置２９の構成を示す機能ブロック図である。

マップ生成部４１は、タグ情報検出装置２７で求められた移動空間１０内のオブジェクト（移動ロボット１１、目標物１７、移動障害物１３、および固定障害物１５）のタグ情報（位置情報およびタグＩＤに基づくオブジェクト固有情報）を利用して、移動空間１０のオブジェクトマップを生成する。オブジェクトマップは、移動空間１０内の各オブジェクトの存在状況を２次元的に投影してグリッド表現したマップである。オブジェクトマップにおけるグリッドの間隔は、ＲＦ−ＩＤタグ２１の位置検出の精度に影響を与える移動空間１０の天井の高さ、移動空間１０内のオブジェクトの形状の複雑さ、超音波タグシステムおよびＲＦ−ＩＤタグシステムの通信能力、移動ロボット１１の移動速度および行動制御精度、経路生成装置２９の計算能力、などに応じて適宜設定され、本実施例では例えば５０cm間隔である。

例えば、図３（ａ）に示すように移動ロボット１１と目標物１７との間に２つの障害物３３および３５（移動障害物１３または固定障害物１５）がある移動空間１０を仮定する。マップ生成部４１は、はじめに移動空間１０の大きさおよび形状、壁の位置、間口の位置などの情報を記憶しているグローバルマップ４３から移動空間１０の情報を受け取り、オブジェクトマップの大きさを定める。

続いて、タグデータベース４５に格納されているタグ位置情報から移動空間１０内の各オブジェクトの位置をオブジェクトマップ上に定める。さらにタグＩＤに基づくオブジェクトの固有情報（形状および種類）をタグデータベース４５から読み出し、オブジェクト固有情報に応じた形状をオブジェクトの領域としてオブジェクトマップにプロットする。

図３（ｂ）はオブジェクトマップの一例である。オブジェクトマップにおいて色の付けられている領域が、オブジェクト（移動ロボット１１，目標物１７、障害物３３，３５）が存在すると認識される領域である。なお、図３（ｂ）に示すように、オブジェクトマップは、複数の小さな矩形領域（セル）がグリッド状に配置されており、このセルを一単位としてオブジェクト存在領域を認識する。例えば障害物３３が、あるセルの一部分に重なっていた場合、当該セルの全体が障害物３３の存在領域として認識される。これによって、移動ロボット１１が移動時に障害物３３と接触してしまうといった不具合が回避される。

また、オブジェクトの存在領域の範囲は、実際のオブジェクトの領域から所定分だけ外側にマージンを取るようにオブジェクトマップを設定しても良い。この場合、オブジェクトからの距離が十分に確保されるので、移動ロボット１１の移動時の接触が確実に回避される。マージンの幅は、移動空間１０内のオブジェクトの数や形状、移動ロボット１１の移動態様などを考慮して決定すれば良い。

マップ生成部４１は、２次元のオブジェクトマップを構成する全てのセルに対してセル値を付与してオブジェクトマップを完成させる。このとき、図３（ｂ）の障害物３３および３５が存在すると認識された領域に対してはセル値「１」が付与され、その他の領域に対してはセル値「０」が付与される。セル値は、後述するポテンシャル場を算出する処理において、オブジェクトの存在領域であるか否かの判別指標として利用される。

図２に示すタグデータベース４５内の情報は、所定のタイミング（例えば１０msec毎）で逐次更新される。

なお、図２においてグローバルマップ４３およびタグデータベース４５は、本発明の経路生成装置２９の外部に設け、必要に応じてグローバルマップ４３およびタグデータベース４５内の情報がマップ生成部４１に供給されるように構成しても良い。

再び図２を参照すると、合成ポテンシャル生成部４７は、マップ生成部４１で生成された移動空間１０のオブジェクトマップに基づき、合成ポテンシャルU(x, y)を算出して移動空間１０全体のポテンシャル場を生成する。合成ポテンシャルU(x, y)は、従来の人工ポテンシャル法でも用いられる斥力ポテンシャルU₀(x, y)および引力ポテンシャルU_xd(x, y)に、ローカルミニマムを回避するために用意された仮想ポテンシャルU_v(x, y)を加算したものである。本発明の特徴点の一つである仮想ポテンシャルU_v(x, y)の作り方については後述する。

斥力ポテンシャルU₀(x, y)は、移動ロボット１１を障害物１３，１５に近づかせないために設定されたポテンシャルである。斥力ポテンシャルU₀(x, y)の値は、オブジェクトマップ上の任意のセルの座標(x, y)から障害物１３，１５への距離が所定値（ｐ₀）以上のとき「０」であり、座標(x, y)が障害物１３，１５に近づくにつれて増大する。すなわち、斥力ポテンシャルU₀(x, y)は、障害物から離れる傾向の経路生成に貢献するポテンシャル場を生成する。斥力ポテンシャルU₀(x, y)は、各障害物に対して次式で算出される。

ここでηは正の重み定数である。ｐ₀は正の定数であり、斥力ポテンシャルU₀(x, y)が発生するしきい値である。

ここでｐ₀は、どの程度の距離まで斥力ポテンシャルU₀(x, y)の計算を行うかを決める値であり、定数ηは、斥力ポテンシャルU₀(x, y)の大きさを調整するための値である。定数ｐ₀および定数ηは、移動空間１０内のオブジェクトの数、経路生成装置２９の計算能力、斥力ポテンシャル計算の収束までの要求時間などに応じて適宜決定される。移動ロボット１１の自己位置検出精度にもよるが、例えば、定数ηが大きければ移動ロボット１１は移動中に障害物に接触する可能性が低くなり、定数ηが小さければ移動ロボット１１は狭い部分を通過できるようになる。

また、（１）式におけるｐ(x, y)は、オブジェクトマップ上の任意のセルの座標(x, y)から、障害物があると認識される各セルの座標までの最近接距離を表し、次式で算出される。

ただし、座標(x_m, y_m)は、対象障害物の領域内の全てのセルの座標を表す。対象となる障害物の範囲は、オブジェクトマップに付与されたセル値に基づいて特定される。すなわち、セル値が「１」であるセル領域の集合が障害物の存在する範囲として扱われる。この集合に含まれる全てのセルの座標を(x_m, y_m)とする。

引力ポテンシャルU_xd(x, y)は、移動ロボット１１を目標物１７のある目標位置（x_d, y_d）へ近づけるために設定されたポテンシャルである。引力ポテンシャルU_xd(x, y)の値は、目標位置（x_d, y_d）で「０」となり、オブジェクトマップ上の任意の座標(x, y)が目標位置（x_d, y_d）から離れるほど増大する。引力ポテンシャルU_xd(x, y)は、具体的には次式で算出される。

ここで、(x_d, y_d)は目標物１７の座標である。Kpは正の重み係数である。Kpは例えば移動ロボット１１の移動前の初期位置の引力ポテンシャルU_xd(x, y)が「１」となるように定めることができる。

上述のように算出した引力ポテンシャルU_xd(x, y)および斥力ポテンシャルU₀(x, y)に仮想ポテンシャルU_v(x, y)を加算して合成ポテンシャルU(x,y)を生成する。仮想ポテンシャルU_v(x, y)の初期値は０とする。

合成ポテンシャルU(x, y)は、例えば図３に示した移動空間１０の一例の場合、図６（ａ）に示すようなセル毎のポテンシャル場を形成する。

ローカルミニマム判別部４９は、合成ポテンシャルU(x, y)による移動空間１０のポテンシャル場を利用して経路探索を行う。ポテンシャル場の勾配に基づき、ナビゲーションの始点から目標点まで近傍のポテンシャル最小点を探索しながら全体経路を得る。

図４（ａ）を参照すると、移動ロボット１１の初期位置のセル６１の近傍８点６３の合成ポテンシャルU(x, y)の値を比較して、最小の値を持つセル６５を選択し、選択したセル６５に参照先を移動させる。続いて図４（ｂ）を参照すると、セル６５の近傍８点６７の合成ポテンシャルU(x, y)値を比較して、最小の値を持つセル６９を選択し、選択したセル６９に参照先を移動させる。続いて図４（ｃ）を参照すると、セル６９の近傍８点７１の合成ポテンシャル値を比較して、最小の値を持つセル７３を選択し、選択したセル７３に参照先を移動させる。このようなステップを繰り返すことにより移動経路を探索する。

経路探索処理は、近傍８点の合成ポテンシャルU(x, y)の全てが移動ロボット１１の現在位置の合成ポテンシャルより大きい場合、探索を終了して収束位置(x_g, y_g)を確定する。続いて収束位置(x_g, y_g)が目標位置(x_d, y_d)と一致するかどうかをチェックする。両者が一致しない場合、収束位置はローカルミニマムと判定され、ローカルミニマムを解消するための仮想ポテンシャルU_v(x, y)を生成する。両者が一致した場合、目標物１７への経路が完成したと判断する。ここで、現実的には収束位置と目標位置が全く同一になることは、位置検出誤差などの原因のために稀である。従って、収束位置と目標位置との距離が予め設定した所定のしきい値以下になった場合に、目標位置への経路が完成したと判断するようにしても良い。

再び図２を参照すると、仮想ポテンシャル生成部５１は、ローカルミニマムと判定されたセル(x_g, y_g)のポテンシャルを所定量だけ増加させた仮想ポテンシャルU_v(x, y)を生成し、ローカルミニマムを解消するための処理を行う。仮想ポテンシャルU_v(x, y)の増加量は、作業空間の大きさや障害物の数、計算を収束させたい時間などに依存して適宜決定される値である。本実施例のように移動ロボット１１の初期位置のポテンシャルを「１」とし、目標位置のポテンシャルを「０」とした場合には、例えば０．１の仮想ポテンシャルの増加分とすることで、高速度で精度の良い経路生成が可能となることがシミュレーション上確認された。

仮想ポテンシャルU_v(x, y)の増加量は、移動ロボット１１の初期位置および目標位置のポテンシャル差やセルの数、本システムの計算能力、ユーザが本発明に要求する経路生成速度や精度などに応じて設定すると良い。また、ローカルミニマムと判定された収束位置の他に近傍８点のポテンシャルも予め定められた所定量だけ同時に増加させるように設定しても良い。仮想ポテンシャルU_v(x, y)は、前述の合成ポテンシャル生成部４７に入力され、合成ポテンシャルU(x, y)に加算される。そして、先の経路探索で陥ったローカルミニマムを回避するための新たなポテンシャル場が形成され、さらに経路探索が行われる。

本発明による経路生成装置２９は、ポテンシャル場に上述の仮想ポテンシャルU_v(x, y)を追加することにより、従来の人工ポテンシャル法に比べて非常に少ない計算コストでローカルミニマムを回避することができる。

経路生成部５３は、ローカルミニマム判別部４９での経路探索が完了した後に、移動ロボット１１の初期位置から目標位置(x_d, y_d)までの移動経路の情報を生成して通信装置３１に送る。

次に、図５および図６を参照して本発明による移動経路生成手法と従来の人工ポテンシャル法を比較する。例示する移動空間１０は、図３に示したものと同様である。

図５（ａ）は、従来の人工ポテンシャル法で生成されたポテンシャル場を示す図である。そして、図５（ｂ）は、従来の人工ポテンシャル法で生成されたポテンシャル場に基づいて、オブジェクトマップ上に移動経路の探索結果８１を示した図である。図５（ａ）におけるｘ軸、ｙ軸は、図５（ｂ）のｘ軸、ｙ軸に対応しており、ｚ軸はオブジェクトマップの各セルのポテンシャルの値を表している。図５（ａ）を参照すると、人工ポテンシャル法では、引力ポテンシャルU_xd(x, y)の働きによって、移動ロボット１１の初期位置から目標位置１７へ傾斜するポテンシャル場が生成されており、斥力ポテンシャルU₀(x, y)の働きによって、障害物３３、３５に近いほど高い値となるポテンシャル場が生成されていることがわかる。

図５（ｂ）を参照すると、移動経路８１は障害物３３の手前で終了しており、目標位置１７には到達していない。図５（ａ）のポテンシャル場と比較すると、障害物３３に相当する高い値のポテンシャル場８３の影響のため、その近傍にできるローカルミニマムによって、目標物１７の方向への移動が妨げられてしまっている。すなわち、経路探索がローカルミニマムに収束している。このように、従来技術の人工ポテンシャル法は、障害物の配置などを原因として経路探索がローカルミニマムに収束するという問題点がある。

図６（ａ）は、本発明による移動経路生成手法によって生成されたポテンシャル場を示す図である。図６（ｂ）は、オブジェクトマップ上に移動経路の探索結果８５を示した図である。図５と同様に、図６（ａ）におけるｘ軸、ｙ軸は、図６（ｂ）のｘ軸、ｙ軸に対応しており、ｚ軸はオブジェクトマップの各セルのポテンシャルの値を表している。図６（ａ）を参照すると、本発明による移動経路生成手法は、仮想ポテンシャル生成部５１の働きにより、ローカルミニマムと判定されたセルのポテンシャル８７を増加させたポテンシャル場を形成している。図６（ｂ）を参照すると、移動経路８５は、仮想ポテンシャルU_v(x, y)によって増加したポテンシャル８７により、ローカルミニマムに陥ることなく目標位置１７に到達している。

このように、本発明による移動経路生成手法は、経路探索過程でローカルミニマムと判定されたセルのポテンシャルに所定量を逐次加算させることにより、従来の人工ポテンシャル法に比べ少ない計算コストで容易にローカルミニマムを回避することができる。また、本手法は、現在位置の近傍８点だけの非常に局所的な比較演算を繰り返すことにより移動経路を生成することできるので、移動経路の高速な探索が可能となる。

図７は、経路生成装置２９における移動経路生成処理の流れを示すフローチャートである。

ステップＳ１０１において、グローバルマップ４３から受け取る移動空間１０の情報に基づいてマップを設定し、タグ情報検出装置２７から受け取るタグ情報と、移動ロボット１１に与えられたタスクに応じた目標物１７の情報とに基づいて、オブジェクトマップを生成する。タグ情報には移動空間１０内の各オブジェクト（移動ロボット１１、目標物１７、移動障害物１３、および固定障害物１５）に取り付けられているタグ１９，２１の位置情報と、タグIDに基づくオブジェクト固有情報が含まれる。位置情報から各オブジェクトの座標を確定し、オブジェクト固有情報から各オブジェクトの形状を確定する。そして、各オブジェクトを示す領域を、所定のマージン分も含めてオブジェクトマップ上にプロットする。

ステップＳ１０３において、移動ロボット１１を障害物１３，１５に近づかせないための斥力ポテンシャルU₀(x, y)を（１）式により算出する。斥力ポテンシャルU₀(x, y)の値は、移動空間内で０以上であり、オブジェクトマップ上の座標(x, y)が障害物１３，１５に近いほど無限大に近く増大し、座標(x, y)から障害物１３，１５への距離が所定値以上のとき０となる。斥力ポテンシャルU₀(x, y)は、障害物１３，１５から離れるようにポテンシャル場を生成する。

ステップＳ１０５において、移動ロボット１１を目標物１７のある目標位置（x_d, y_d）へ近づけるための引力ポテンシャルU_xd(x, y)を（３）式により算出する。引力ポテンシャルU_xd(x, y)の値は、目標位置（x_d, y_d）で０であり、オブジェクトマップ上の座標(x, y)が目標位置（x_d, y_d）から離れるほど増大する。

ステップＳ１０７において、引力ポテンシャルU_xd(x, y)および斥力ポテンシャルU₀(x, y)に仮想ポテンシャルU_v(x, y)を加算して合成ポテンシャルU(x,y)を生成する。仮想ポテンシャルU_v(x, y)の初期値は０とする。

ステップＳ１０９において、合成ポテンシャルU(x,y)による移動空間１０のポテンシャル場を利用して移動ロボット１１の移動経路を探索する。経路探索処理は、移動ロボット１１の現在位置のセルの近傍8点の合成ポテンシャルU(x,y)を比較して、最小のポテンシャルを持つセルを選択する処理を繰り返して行う。近傍8点全ての合成ポテンシャルU(x,y)が現在位置のポテンシャルより大きい場合、探索を終了して収束位置(x_g, y_g)を確定する。

ステップＳ１１１において、経路探索処理の収束位置(x_g, y_g)が、目標位置(x_d, y_d)と一致するかどうかを点検する。両者が一致しない場合、経路探索がローカルミニマムに収束したと判定され、ステップＳ１１３に進む。両者が一致する場合、目標位置までの経路探索が達成されたと判定され、ステップＳ１１５に進む。

ステップＳ１１３において、ローカルミニマムを解消するための仮想ポテンシャルU_v(x, y)を生成する。ローカルミニマムと判定された経路探索の収束位置(x_g, y_g)の仮想ポテンシャルUv(x_g, y_g)に所定値を加算して、仮想ポテンシャルU_v(x, y)を更新する。仮想ポテンシャルU_v(x, y)の増加量は、作業空間の大きさや障害物の数などに依存する値であり、例えば０．１である。更新された仮想ポテンシャルU_v(x, y)は、ステップＳ１０７で合成ポテンシャルU(x,y)に加算され、新たな合成ポテンシャルU(x, y)を用いた移動経路の探索が再び実行される。

ステップＳ１１５において、移動ロボット１１の初期位置から目標位置(x_d, y_d)までの移動経路の情報を生成する。移動経路の情報は、通信装置３１に送られる。

生成された経路情報は、通信装置３１を介して移動ロボット１１に送信される。移動ロボット１１は、自身に取り付けられた超音波タグ１９を利用して現在位置を逐次確認しながら、経路情報に従って目標物１７まで移動する。

本発明の要部である図２のマップ生成部４１、合成ポテンシャル生成部４７、ローカルミニマム判別部４９、仮想ポテンシャル生成部５１および経路生成部５３の機能は、ハードウェアで実現しても良いし、ソフトウェアプログラムで実現しても良い。プログラムで上記の機能を実現する場合、予め本発明の経路生成装置２９に当該プログラムが格納されるように構成しても良く、また外部からCD-ROMのような記録媒体や無線または有線によってプログラムが必要に応じて供給されるような構成としても良い。

以上、本発明の実施形態について説明したが、本発明はこのような実施形態に限定されるものではない。例えば、オブジェクトマップにおけるオブジェクト領域のセル値「１」、ロボット１１の初期位置の引力ポテンシャル「１」、仮想ポテンシャルの増加分「０．１」などの値は、この実施形態の環境に依存して例示されたものである。これらの値は、移動空間１０内のオブジェクトの数、経路生成装置２９の計算能力、要求する計算速度などに応じて適宜決定されて良い。

本発明の一実施形態による経路生成装置を含む移動ロボットのナビゲーションシステムを示す概略図である。 本発明の一実施形態による経路生成装置の構成を示す機能ブロック図である。 目標物までの経路上に障害物がある移動空間の一例を示す斜視図と、対応するオブジェクトマップを示す図である。 移動経路の探索過程を示す図である。 人工ポテンシャル法で生成されたポテンシャル場および移動経路を示す図である。 本発明の一実施形態による移動経路生成手法で生成されたポテンシャル場および移動経路を示す図である。 本発明の一実施形態による移動ロボットの移動経路生成処理を示すフローチャートである。

符号の説明

１０ 移動空間
１１ 移動ロボット
１３ 移動障害物
１５ 固定障害物
１７ 目標物
２９ 経路生成装置
４１ マップ生成部
４７ 合成ポテンシャル生成部
４９ ローカルミニマム判別部
５１ 仮想ポテンシャル生成部

Claims (8)

1. 移動空間内で移動体の移動経路を自律的に生成するための経路生成装置であって、
   前記移動体の初期位置および目標とする位置、並びに障害物の位置および形状を含む情報に基づき前記移動空間内のマップを生成するマップ生成部と、
   前記マップを用いて、前記移動体、前記障害物、および前記目標とする位置の相対位置関係に基づく引力ポテンシャルおよび斥力ポテンシャルを計算し、該引力ポテンシャルおよび該斥力ポテンシャルの和である合成ポテンシャルを生成する合成ポテンシャル生成部と、を備え、
   前記引力ポテンシャルは、前記目標とする位置から離れるほど大きい値をとり、前記斥力ポテンシャルは、前記障害物に近いほど大きい値をとり、
   前記合成ポテンシャルに基づいて前記マップ内の経路探索を行い、前記移動体の近傍の複数の点のそれぞれにおける前記合成ポテンシャルが該移動体の現在位置の前記合成ポテンシャルより大きいとき、前記移動体の合成ポテンシャルがローカルミニマムにあると判別するローカルミニマム判別部を備え、
   前記経路生成装置は、前記ローカルミニマムの位置が前記目標とする位置と異なるとき、前記移動体が該ローカルミニマムから移動できるよう、該ローカルミニマムの位置のポテンシャルを増加させ、前記ローカルミニマムの位置が前記目標とする位置と一致するとき、前記経路探索の結果に基づいて前記移動体の移動経路を生成するよう構成されている、移動体の経路生成装置。
2. 前記移動体、前記障害物および前記目標とする位置にある目標物に取り付けられたタグの信号から前記情報を識別するタグ情報検出装置をさらに備える、請求項１に記載の移動体の経路生成装置。
3. 前記タグは、前記目標物および移動可能な前記障害物に適用されるＲＦ−ＩＤタグと、前記移動体および固定された前記障害物に適用される超音波タグとを含む、請求項２に記載の移動体の経路生成装置。
4. 前記引力ポテンシャルは、
   

   

   で表される式により求められ、ここで、(x, y)は前記マップ内の任意の座標であり、(x_d, y_d)は前記目標とする位置の座標であり、Kpは正の重み係数であり、
   前記斥力ポテンシャルは、
   

   

   で表される式により求められ、ここでηは正の重み定数であり、ｐ₀は正の定数であって斥力ポテンシャルが発生するしきい値であり、ｐ(x, y)は、前記マップ内の任意の座標(x, y)から、前記障害物があると認識される座標までの最近接距離であり、該ｐ(x, y)は、
   

   

   で表される式により求められ、ここで、(x_m, y_m)は、前記前記マップ内で前記障害物の領域に含まれる全ての座標を表しており、
   前記合成ポテンシャルは、
   

   

   で表わされる式により求められ、ここで、U_xd(x, y) は引力ポテンシャルであり、U₀(x, y)は斥力ポテンシャルであり、U_v(x, y) は合成ポテンシャルを増加させるためのポテンシャルである、
   請求項１乃至請求項３のいずれかに記載の移動体の経路生成装置。
5. 移動空間内で移動体の移動経路を自律的に生成するためのプログラムであって、
   メモリに記憶された、前記移動体の初期位置および目標とする位置、並びに障害物の位置および形状を含む情報に基づき、前記移動空間内のマップを生成する機能と、
   前記マップを用いて、前記移動体、前記障害物、および前記目標とする位置の相対位置関係に基づく引力ポテンシャルおよび斥力ポテンシャルを計算し、該引力ポテンシャルおよび該斥力ポテンシャルの和である合成ポテンシャルを生成する機能と、
   を備え、前記引力ポテンシャルは、前記目標とする位置から離れるほど大きい値をとり、前記斥力ポテンシャルは、前記障害物に近いほど大きい値をとり、
   前記合成ポテンシャルに基づいて前記マップ内の経路探索を行い、前記移動体の近傍の複数の点のそれぞれにおける前記合成ポテンシャルが該移動体の現在位置の前記合成ポテンシャルより大きいとき、前記移動体の合成ポテンシャルがローカルミニマムにあると判別する機能と、
   前記ローカルミニマムの位置が前記目標とする位置と異なるとき、前記移動体が該ローカルミニマムから移動できるよう、該ローカルミニマムの位置のポテンシャルを増加させるためのポテンシャルを生成し、前記合成ポテンシャルに足し合わせる機能と、
   前記ローカルミニマムの位置が前記目標とする位置であると判別された場合、前記経路探索の結果に基づいて前記移動体の移動経路を生成する機能と、
   をコンピュータに実行させるためのプログラム。
6. 前記移動体、前記障害物および前記目標とする位置にある目標物に取り付けられたタグの信号から前記情報を識別する機能をさらに備える、請求項５に記載のプログラム。
7. 前記タグは、前記目標物および移動可能な前記障害物に適用されるＲＦ−ＩＤタグと、前記移動体および固定された前記障害物に適用される超音波タグとを含む、請求項６に記載のプログラム。
8. 前記引力ポテンシャルは、
   

   

   で表される式により求められ、ここで、(x, y)は前記マップ内の任意の座標であり、(x_d, y_d)は前記目標とする位置の座標であり、Kpは正の重み係数であり、
   前記斥力ポテンシャルは、
   

   

   で表される式により求められ、ここでηは正の重み定数であり、ｐ₀は正の定数であって斥力ポテンシャルが発生するしきい値であり、ｐ(x, y)は、前記マップ内の任意の座標(x, y)から、前記障害物があると認識される座標までの最近接距離であり、該ｐ(x, y)は、
   

   

   で表される式により求められ、ここで、(x_m, y_m)は、前記前記マップ内で前記障害物の領域に含まれる全ての座標を表しており、
   前記合成ポテンシャルは、
   

   

   で表わされる式により求められ、ここで、U_xd(x, y) は引力ポテンシャルであり、U₀(x, y)は斥力ポテンシャルであり、U_v(x, y) は合成ポテンシャルを増加させるためのポテンシャルである、
   請求項５乃至請求項７のいずれかに記載のプログラム。

Images