移動ロボットの格子マップ作成方法及び装置及び媒体とこれを利用した領域分離方法及び装置及び媒体
【課題】 移動ロボットの格子マップ作成方法及び装置及び媒体とこれを利用した領域分離方法及び装置及び媒体を提供する。
【解決手段】 外部空間または障害物との距離を感知して格子点を獲得して格子マップを作成する格子マップ作成部と、格子点から特徴点を抽出する特徴点抽出部と、ロボットが移動した後にロボット自身の位置を推定して特徴点を再抽出することによって特徴点を更新する特徴点更新部と、特徴点抽出部により抽出された特徴点から特徴点更新部により更新された特徴点に変換する変換式計算部と、求められた変換式によって格子マップを更新する格子マップ更新部とを備える。
【解決手段】 外部空間または障害物との距離を感知して格子点を獲得して格子マップを作成する格子マップ作成部と、格子点から特徴点を抽出する特徴点抽出部と、ロボットが移動した後にロボット自身の位置を推定して特徴点を再抽出することによって特徴点を更新する特徴点更新部と、特徴点抽出部により抽出された特徴点から特徴点更新部により更新された特徴点に変換する変換式計算部と、求められた変換式によって格子マップを更新する格子マップ更新部とを備える。
【発明の詳細な説明】
【技術分野】
【0001】
本発明は、移動ロボットの格子マップ作成方法及び装置及び媒体とこれを利用した領域分離方法及び装置及び媒体に係り、さらに詳細には、ロボットが走行しつつ広い領域の格子マップを作成する方法及び装置と、作成された格子マップを一箇所以上の領域に分離する方法及び装置及び媒体に関する。
【背景技術】
【0002】
一般的に、ロボットは工場や産業で自動化工程に対する方案として開発された。自動制御技術及び遠隔操縦技術などが進歩するにつれて高温、低温などの極限の環境や宇宙や海底などの危険な環境で作業するか、単調な業を反復する場合にロボットが主に応用された。
【0003】
最近には、産業で利用される産業用ロボットだけでなく一般家庭や事務室などで家事や事務補助としてロボットが実用化されている。これに該当する代表的な例として、掃除用ロボット、案内ロボット、防犯ロボットなどを挙げることができる。
【0004】
掃除用ロボットなどの移動ロボットにおいて、ロボットが移動する経路やロボットが活動する区域を指定するためには、まずロボットが認識するマップが必要である。一般的にロボットが認識するマップは、ユーザによりあらかじめ準備されたマップをロボットに入力するか、底や天井でロボットが認識できる標識を利用してロボットをして周囲情報及び自分の位置を認識させるか、ロボット自身が自律走行を通じて活動区域のマップを作成する方案がある。
【0005】
ロボットが自律走行を行いつつマップを作成する方法に多様な試みがなされてきたが、大部分複数のセンサを使用してセンサの誤差による不確実性及び誤差も持っていた。また、ロボットがセンサで認識する範囲は、マップを作成する領域で限定された一部分であるため、このような限定された領域で良質の格子マップを得るとしても、全体としてマップを完成する場合には格子マップの全体的構成が実際マップと差を示すという問題があった。
【0006】
図1は、従来技術によってロボットが格子マップを作成した概略図を示す。
例えば、図1で図示するように元来のマップが方形の部屋ならば、ロボットが部屋を回転して完成した格子マップがそれぞれの面では直線に該当できるが、全体的に格子マップを完成する場合には、方形の形状を認識できない場合があった。したがって、不正確な格子マップによってロボットが自身が行おうとする役割を指定された位置で行えないという問題があった。
【0007】
このように格子マップをなす空間については、複数の領域に分離する方案が好まれている。例えば、掃除用ロボットにおいては、広い空間で一度に掃除を行うよりはそれぞれの部屋や居間のいくつかの領域に分離して掃除させることによって、掃除用ロボットに全体を均一に掃除させ、ロボットが走行しつつ重なる位置や方向などの誤差を低減できる。このような領域分離においても、ロボットをして掃除を行わせる方向に鑑みて領域を分離せねばならないために、単純に面積や距離などに基づいて領域を分離できず、同じ面積であってもロボットが効率的に掃除を行えるように領域を分離せねばならないという問題があった。
【0008】
また、不正確なセンサを使用して格子マップを構成する場合には、障害物枠の屈曲が激しくて、従来の臨界点(Critical point)により領域を分離する方式によっては領域に分離し難かった。
【非特許文献1】IEEE Transactions on Robotics and Automation,Vol 17,No.3,June 2001の‘A Solution to the Simultaneous Localization and Map Building Problem’
【発明の開示】
【発明が解決しようとする課題】
【0009】
本発明は、前記のような問題点に鑑みてなされたものであり、特徴点を格子マップと一致させて相対的に正確な格子マップを得た後に、特徴点を臨界点として見なして領域分離を行うことで、広い空間に対して良質の格子マップを作成し、ロボットが行おうとする機能に合う領域分離を行うことを目的とする。
【0010】
本発明の目的は、以上で言及した目的に制限されず、言及されていない他の目的は下の記載から当業者に明確に理解されうる。
【課題を解決するための手段】
【0011】
前述した目的を達成するために、本発明の一実施形態による移動ロボットの格子マップ作成方法は、(a)外部空間または障害物との距離を感知して格子点を獲得して格子マップを作成するステップと、(b)前記格子点から特徴点を抽出するステップと、(c)ロボットが移動した後にロボット自身の位置を推定して特徴点を再抽出することによって前記特徴点を更新するステップと、(d)前記(b)ステップで抽出された特徴点から、前記(c)ステップで更新された特徴点に変換する変換式を求めるステップと、(e)前記求められた変換式によって格子マップを更新するステップと、を含む。
【0012】
前述した目的を達成するために、本発明の一実施形態による移動ロボットの格子マップ作成方法は、(a)移動ロボットから物体(object)までの距離を感知して獲得した格子点(Grid points)に基づいて格子マップを作成するステップと、(b)前記格子点から特徴点を抽出するステップと、(c)前記移動ロボットが移動した後に前記移動ロボットの位置を推定し、SLAM(Simulatneous Local And Map building)アルゴリズムを利用して前記特徴点を更新するステップと、(d)前記(b)ステップで抽出された特徴点から前記(c)ステップで更新された特徴点に変換する変換式を求めるステップと、(e)前記求められた変換式により格子マップを更新するステップと、を含む。
【0013】
前述した目的を達成するために、本発明の一実施形態によるコンピュータ媒体は、前記方法を行うためにコンピュータが読取可能な命令語を保存したコンピュータ媒体である。
【0014】
前述した目的を達成するために、本発明の一実施形態による移動ロボットの格子マップを利用した領域分離方法は、前述した移動ロボットの格子マップ作成方法である(a)、(b)、(c)、(d)、(e)ステップと、(f)前記更新された格子マップから最多頻度のスイープラインの角度を抽出するステップと、(g)前記抽出されたスイープライン角度によって前記格子マップをスキャンし、前記スイープラインが特徴点を通る地点で前記スイープラインにより領域を分離するステップと、を含む。
【0015】
前述した目的を達成するために、本発明の一実施形態による格子マップ作成移動ロボットは、外部空間または障害物との距離を感知して格子点を獲得して格子マップを作成する格子マップ作成部と、前記格子点から特徴点を抽出する特徴点抽出部と、ロボットが移動した後にロボット自身の位置を推定して特徴点を再抽出することによって前記特徴点を更新する特徴点更新部と、前記特徴点抽出部により抽出された特徴点から前記特徴点更新部により更新された特徴点に変換する変換式計算部と、前記求められた変換式によって格子マップを更新する格子マップ更新部と、を備える。
【0016】
前述した目的を達成するために、本発明の一実施形態による格子マップ作成移動ロボットは移動ロボットから物体までの距離を感知して獲得した格子点に基づいて格子マップを作成する格子マップ作成部と、前記格子点から特徴点を抽出する特徴点抽出部と、ロボットが移動した後にロボット自身の位置を推定し、SLAMアルゴリズムを利用して前記特徴点を更新する特徴点更新部と、前記特徴点抽出部により抽出された特徴点から前記特徴点更新部により更新された特徴点に変換する変換式計算部と、前記求められた変換式により格子マップを更新する格子マップ更新部と、を備える。
【0017】
前述した目的を達成するために、本発明の一実施形態による格子マップを利用した領域分離移動ロボットは、格子マップ作成部、特徴点抽出部、特徴点更新部、変換式計算部、格子マップ更新部と、前記更新された格子マップから最多頻度のスイープラインの角度を抽出するスイープライン角度抽出部と、前記抽出されたスイープライン角度によって前記格子マップをスキャンし、前記スイープラインが特徴点を通る地点で前記スイープラインにより領域分離部と、をさらに備える。
【発明の効果】
【0018】
本発明は、次のような効果が一つあるいはそれ以上ある。
第1に、格子マップと特徴点マップとをマッチングさせて実際に類似する格子マップを作成できる。
第2に、特徴点とスイープラインとによって領域分離を行ってロボットが機能を行うのに適して領域を分離できる。
第3に、各領域ごとに走行方向を各領域に合わせて決定することによって、領域分離後のロボットが領域内で効率的な作業を行える。
【0019】
本発明の効果は、以上で言及した効果に制限されず、言及されていない他の効果は請求の範囲の記載から当業者に明確に理解されうる。
【発明を実施するための最良の形態】
【0020】
その他の実施例の具体的な事項は詳細な説明及び図面に含まれている。
【0021】
本発明の利点及び特徴、そしてこれを達成する方法は添付された図面に基づいて詳細に後述されている実施例を参照すれば明確になる。しかし、本発明は以下で開示される実施例に限定されるものではなく、この実施例から外れて多様な形に具現でき、本明細書で説明する実施例は本発明の開示を完全にし、本発明が属する技術分野で当業者に発明の範ちゅうを完全に報せるために提供されるものであり、本発明は請求項及び発明の詳細な説明によってのみ定義される。一方、明細書全体に亙って同一な参照符号は同一な構成要素を示す。
【0022】
以下、本発明の望ましい実施形態について、添付された図面を参照してさらに詳細に説明する。
【0023】
図2は、本発明の一実施形態による移動ロボットの格子マップを利用した領域分離方法を示すフローチャートである。
【0024】
前述した目的を達成するために、本発明の一実施形態による移動ロボットの格子マップを利用した領域分離方法は、(a)外部空間または障害物との距離を感知して格子点を獲得して格子マップを作成するステップと、(b)前記格子点から特徴点を抽出するステップと、(c)ロボットが移動した後にロボット自身の位置を推定して特徴点を再抽出することによって前記特徴点を更新するステップと、(d)前記(b)ステップで抽出された特徴点から、前記(c)ステップで更新された特徴点に変換する変換式を求めるステップと、(e)前記求められた変換式によって格子マップを更新するステップと、(f)前記更新された格子マップから最多頻度のスイープラインの角度を抽出するステップと、(g)前記抽出されたスイープライン角度によって前記格子マップをスキャンし、前記スイープラインが特徴点を通る地点で前記スイープラインにより領域を分離するステップと、をさらに含む。
【0025】
まず、移動ロボットは、探索しようとする地域に対して自律的に走行を行う。移動ロボットは、距離を感知できる一つ以上のセンサを装着して移動ロボットの前方にある障害物を感知できる。このように移動ロボットは、超音波、赤外線またはレーザーセンサなどの距離感知センサを利用して、障害物や建物内壁の構造をロボット自身を基準に認識できる。このような構造認識方法では、ロボットから構造物または壁面までの距離を感知して複数の点で構成させる格子点330を獲得できる(S205)。ロボットが走行しつつ認識した複数の格子点330を繋げて完成する空間情報が格子マップである。したがって、ロボットは格子点を獲得してデータとして保存して格子マップを作成できる(S205)。感知された複数の格子点から特徴点310、320を抽出できる(S210)。特徴点とは、事物の角またはコーナーのように形状を特定付ける点を意味する。
【0026】
特徴点310、320を抽出するために建物の角部位のようなコーナーまたは角ポインタを抽出するものとして、RANSAC(Random Sample Consensus)または分離と結合(Split and Merge)アルゴリズムを使用できる。RANSACアルゴリズムは、距離データにより獲得された格子点に基づいて、獲得された格子点の一致するセットをランダムに抽出して誤差範囲内を満足する複数の直線を検出する方法であって、検出された複数の直線によって直線と直線とが会う点などを認識してコーナーまたは角を検出し、これを特徴点と見なす。分離及び結合アルゴリズムは、極大点を探してラインに連結し、ラインから外れる点がエラー値より大きい場合には細部ラインに分離でき、隣接したラインでは、一つのラインと認識されうる場合には、結合して全体的な形状のラインを抽出しつつコーナーまたは角を抽出してこれを特徴点とすることができる。
【0027】
ロボットは、走行し続けて自身の位置を把握しつつ周囲に対するマップを作成する。ロボットの位置追跡とマップ作成とを同時に行える方法であるSLAM(Simultaneous Localization And Mapbuilding)アルゴリズムを使用できる。SLAMは、ある位置で周辺環境のマップを作成し、作成されたマップに基づいて再び動いたロボットの位置を把握できる反復を通じて、ロボットの位置と周辺環境のマップとを同時に推定する技術である。それにより、ロボットが走行しつつSLAMアルゴリズムによって特徴点を更新できる(S215)。
例えば、次のようにEKF(Extended Kalman Filter)に基づいたSLAMアルゴリズムを使用できる。
【0028】
【数1】
【0029】
【数2】
式(1)は、ロボットの走行モデル式を示す。ここで、x(k)は、時間ステップkでのロボットの位置、u(k+1)は、制御ベクトル、v(k+1)は、ノイズベクトル、F(k)は、時間ステップkでの状態変換行列である。式(2)は、ロボットが走行しつつi番目特徴点の距離を感知する観察モデル式を示す。ここで、w(k)は、測定値のノイズ、Hはロボットの走行による観察行列である。
【0030】
SLAMアルゴリズムはまず制御ベクトルからロボットの位置を推定する。以後、特徴点に対するセンサの測定値を利用して共分散行列(Covariance matrix)を計算できる。これに基づいてカルマンゲインを計算し、ロボットの位置及び特徴点の位置を更新し、共分散行列を更新する。SLAMアルゴリズムについての説明は、論文IEEE Transactions on Robotics and Automation,Vol 17,No.3,June 2001の‘A Solution to the Simultaneous Localization and Map Building Problem’らに掲示されているので、詳細な説明は省略する。
【0031】
SLAMを行った後には、各特徴点を変化させることができる変換行列(T;Transform Matrix)を探すことができる(S220)。SLAM実行前の特徴点の位置を(x,y)とし、SLAM実行後の各特徴点の位置をそれぞれ(x’,y’)と仮定しよう。SLAM実行後の特徴点の位置(x’,y’)は、補正された特徴点の位置と見なされうる。換言すれば、特徴点の位置を更新することで相対的に正確な特徴点の位置を認識できる。
【0032】
したがって、補正前の特徴点の位置(x,y)を補正された特徴点の位置(x’,y’)に変換するための変換行列Tを求めることができる。変換行列Tを求めるためには多様な変換方法が使われうる。一例として、補正された特徴点の位置を補正前特徴点の位置と1:1にマッピングさせるアフィン変換または線形等角変換が使われうる。もし、変換方式としてアフィン変換を使用する場合には、次の式により変換行列Tを求めることができる。
【0033】
【数3】
式(3)により求められた変換行列Tに基づいて、格子マップの全体領域で変換を行えば格子マップ全体を更新できる。したがって、更新された格子マップは既に補正された特徴点に合わせて更新されることができ、格子マップと特徴点マップとが相互マッチングされうる。
【0034】
図3は、本発明の一実施形態による移動ロボットの格子マップ作成方法で特徴点の位置を示す概略図である。図4Aは、本発明の一実施形態による移動ロボットの格子マップ作成方法で変換前に作成された格子マップであり、図4Bは、本発明の一実施形態による移動ロボットの格子マップ作成方法でアフィン変換により更新された格子マップを示す。
【0035】
例えば、移動ロボットが走行して図3で図示するような格子マップを得たと仮定する。図4Aは、移動ロボットが走行しつつSLAM補正を行う前にロボットのセンサから得られた格子マップを示す。格子マップでは、空間内の概略的な区域は示しており、各特徴点も空間内の区域から抽出されている。例えば、図4Aで図示するように、特徴点が7個に抽出される場合に、移動ロボットは走行しつつ各特徴点を更新し続けられる。特徴点を更新しつつ、更新前の特徴点と更新後の特徴点とを1:1にマッピングさせる変換を求めることができる。例えば、図3の変換式を利用して変換行列Tを求めた場合には、全体格子マップを変換行列Tを利用して変換することによって、図4Bで図示するように更新された格子マップを得ることができる(S225)。更新された格子マップは、更新前の格子マップに比べて区域内の境界を歪めず、全体的に構成した時に相対的に優秀な格子マップを得ることができる。
【0036】
前記のように、格子マップを更新しつつ格子マップ作成を行える(S225)。例えば、アパートの内部でロボットが格子マップを作成する場合には、まず部屋内の格子マップを完成し、続けて他の部屋や居間に移動して特徴点を抽出し、変換行列を求めて格子マップを更新する。それにより、アパート内部の全体区域に対する格子マップ更新を行った後に初めて全体的な格子マップを完成できる。ただし、場合によっては、ロボットが一つの部屋または居間などの一部分に対しても前述した方法による格子マップを作成することができる。
【0037】
図5Aは、障害物550がある平面空間500で臨界点の定義により臨界点を得た概略図であり、図5Bは、図5Aの右側壁面をロボットがセンサにより感知した壁面の格子マップを示す概略図である。図6は、本発明の一実施形態による移動ロボットの格子マップを利用した領域分離方法により、障害物がある平面空間で特徴点を得た概略図であり、図7は、本発明の一実施形態による移動ロボットの格子マップを利用した領域分離方法で、スイープラインにより領域を分離することを示す。
【0038】
格子マップを作成した後には、格子マップに基づいて一つ以上の領域に分離する。一般的にロボットは、スイープライン700方向を決定した後に、スイープラインに沿って合う臨界点510を基準に領域710を分離できる。臨界点についての詳細な内容は、2000 IEEE International Conference on Robotics and Automationに発表されたH.Choset,E.Acar,A.Rizzi,and J.Luntz.の論文‘Exact cellular decompositions interms of critical points of Morse functions’に掲示されている。
【0039】
一般的に、臨界点510は、スイープラインの区域内で一定方向に進行しつつ障害物に合って上下に障害物のない地点を意味する。例えば、図5Aで図示するように、方形の部屋の中に障害物がある場合において、臨界点510は8つに抽出されうる。ただし、図6に示すように、前述した特徴点の抽出によって抽出された特徴点は、空間上の角とコーナーとをいずれも含むものであって10つに抽出できる。しかし、図5Bに示すように、図5Aの右側部分520を拡大すれば、従来の格子マップでは、センサの誤差による屈曲によって不要な臨界点570が生成されて、図5Aとは違って8つより多くの複数の臨界点570を生成するという問題があった。
【0040】
本発明では、臨界点を探す試みなしに前述した格子マップ作成方法で抽出された特徴点を臨界点と見なすことができる。それにより、センサの誤差により発生する不要な臨界点570を考慮せず、領域分離に必要な特徴点310、320のみを利用して領域分離を行える。このように、スイープラインを格子マップ内でスキャンしつつ一つ以上の領域に分離できる。
【0041】
したがって、全体の格子マップに対してスイープラインの角度を決定する(S235)。格子マップの領域内で多様な方法を使用して全体領域内で優勢な頻度を持つラインの角度を求めることができる。例えば、このためにまず領域内に存在する一つ以上のラインを検出した後に、これを角度の同じグループに分けて、そのうち最も加重値の高いライングループの角度をスイープラインがなす角度と決定できる。これを具現するためには、ハフ変換(Hough Transform)、ラドン変換(Radon Transform)またはヒストグラム技法を使用できる。それにより、算出された角度を、全体格子マップ領域で領域分離時のスイープラインの角度と使用できる。
【0042】
前記で得られたスイープラインと特徴点とを利用して全体格子マップ領域から領域を分離できる(S240)。例えば、図7で図示するようにスイープライン角度が90°で得られた場合に表示されたスイープラインのスキャンにより、特徴点と合う地点で領域を分離できる。スイープラインが90°状態で左側から右側に格子マップの内部をスキャンする場合には、5個の領域に分けられうる。格子マップの内部をスキャンしつつスイープラインが一つ以上の特徴点に合うことができ、したがって、一つ以上の領域に分離されうる。ただし、スイープラインがスキャンしつつ同時に一つ以上の特徴点に合う場合には一つの特徴点に合ったと見なして、一回の領域分離がなされうる。
【0043】
図8A及び図8Bに示したように、本発明の一実施形態による移動ロボットの格子マップを利用した領域分離方法で領域を結合することを示す。
【0044】
領域を分離した後には各領域ごとにロボットが走行する方向を決定できる(S245)。例えば、掃除用ロボットの場合には掃除方向を決定するが、本発明のように領域別に掃除しようとする場合には、領域別に掃除方向を決定できる。一般的に掃除方向は、図8Aに図示するように前後(Back and forth)とする。したがって、ロボットが領域内で直線走行を多く行いつつ、回転を少なくする走行方向を掃除方向と決定できる。
【0045】
基本的に領域内で掃除方向を決定するためには、領域内の最も優勢なラインに従うことができる。このために、全体格子マップ領域で最も優勢なスイープラインの角度を決定するのに使用した方法であるハフ変換、ラドン変換またはヒストグラム技法を使用できる。したがって、例えば、図8Aで図示するように、各領域での掃除方向では、I領域は90°、II領域は90°、III領域は0°、IV領域は90°、V領域は0°である。
【0046】
このように、各領域を基準に隣接する領域で掃除方向が同一ならば、ロボットの立場では領域のみ分離されているだけで、掃除するパターン及び方向は同一である。したがって、隣接する領域で掃除方向が同一ならば、一つの領域と見なして領域を合わせる(Pruning)ことができる(S250)。すなわち、図8AではI、II領域が隣接して掃除方向が同一であるので、I、II領域を合わせて一つの領域に見なすことができる。したがって、図8Bで示すように最終的に4つの領域に領域分離されうる。
【0047】
図9では、本発明の一実施形態による格子マップを利用する領域分離移動ロボットのブロック図である。
本発明の一実施形態による格子マップ作成移動ロボットは、ロボットの機能を行う空間の格子マップを作成し、作成された格子マップを一箇所以上の領域に領域分離するために、格子マップ作成部900、特徴点抽出部910、特徴点更新部920、変換式計算部930、格子マップ更新部940を備えることができる。
【0048】
格子マップ作成部900は、ロボットに装着された一つ以上の距離センサを通じてロボットが占める空間の内部壁または障害物までの距離を測定して格子点を獲得し、これをデータとして処理して格子マップを作成する役割を行う。ロボットは、格子マップを作成しようとする領域に対してロボットが走行しつつ距離を感知して格子点を獲得することによって、格子マップを作成することができる。
【0049】
ロボットが周囲環境に対する距離を測定して複数の格子点330を構成することによって、一種の外形をもつ格子マップを形成できる。それにより、複数の格子点から事物の角またはコーナーのように形状を特定させうる点である特徴点310、320を抽出できる。特徴点を抽出するために、距離データにより獲得された格子点に基づいて複数の直線を認識し、直線と直線とが合う点などを認識してコーナーまたは角を検出するRANSACまたは分離及び結合アルゴリズムを使用できる。
【0050】
特徴点更新部920は、移動ロボットが走行しつつSLAMアルゴリズムによりロボットの位置及び特徴点の位置を更新できる。例えば、拡張されたカルマンフィルタに基づいてSLAMアルゴリズムを使用することによって特徴点の位置を補正できる。
【0051】
したがって、変換式計算部930は、特徴点の補正された位置と補正前の位置とを1:1にマッピングさせる変換式を計算する役割を行う。マッピングさせる変換には、アフィン変換または線形等角変換を使用できる。例えば、アフィン変換を使用する場合には、式3を満足させる変換行列Tを求めることができる。
【0052】
格子マップ更新部940は、変換行列Tが求められれば、あらゆる格子マップ領域に変換を行って格子マップ全体を更新する役割を行う。格子マップ更新部940は、特徴点を補正させる変換行列Tを格子マップ全体に適用することによって、特徴点マップと格子マップとをマッチングさせることによって格子マップを更新できる。したがって、更新された格子マップが一定領域に収斂する場合には、更新された格子マップが移動ロボットが作業を行う空間の格子マップになりうる。
【0053】
前記のように構成要素により、移動ロボットは格子マップを作成することができる。本発明の一実施形態による格子マップを利用する領域分離移動ロボットは、作成された格子マップから一つ以上の領域に分離するために、格子マップ作成部900、特徴点抽出部910、特徴点更新部920、変換式計算部930、格子マップ更新部940と、スイープライン角度抽出部950、領域分離部960、走行方向決定部970、領域結合部980を備えることができる。
【0054】
スイープライン角度抽出部950は、格子マップを領域に分離するために、格子マップをスキャンするスイープラインの方向を決定する役割を行う。したがって、スイープライン角度抽出部は、作成された格子マップから優勢なラインの角度を決定できる。これは、格子マップで最も多くの頻度を持つラインをスイープライン方向に決定することによって、格子マップを領域に簡便に分離できる。スイープライン角度を決定するために、格子マップでハフ変換、ラドン変換またはヒストグラム技法を使用して複数のラインを抽出し、これより頻度の最も大きいラインの方向をスイープライン角度方向に抽出できる。
【0055】
領域分離部960は、スイープラインと特徴点を利用して格子マップを領域に分離する役割を行う。領域分離部は、スイープライン角度抽出部により抽出された角度でスイープラインを格子マップでスキャンしつつ特徴点と合う位置を検索する。特徴点と合う位置でスイープラインに格子マップが一つ以上の領域に分離されうる。したがって、スイープラインが複数の特徴点と合う場合には複数の領域が形成されうる。
【0056】
走行方向決定部970は、格子マップ内で領域に分離されたそれぞれの領域内で移動ロボットの走行方向を決定する役割を行う。例えば、移動ロボットが掃除用ロボットであれば、掃除を進行する方向を決定できる。したがって、掃除用ロボットが分離された領域内で効率的な掃除を行うためには、分離された領域内で回転の少ない掃除方向を選択する必要がある。したがって、走行方向決定部は分離された領域内でハフ変換、ラドン変換またはヒストグラム技法を使用してラインを抽出し、抽出されたラインの頻度が最も大きいライン方向を走行方向と決定できる。この場合、分離された領域を特定する境界線もラインと認識して走行方向を決定するところに使われうる。
【0057】
領域結合部980は、一つ以上の分離された領域を一定の基準によって領域を結合する役割を行う。分離された領域を結合する基準は、走行方向決定部により決定された各領域の走行方向を比較して、隣接した領域の走行方向が一致する場合には隣接した領域を一つの領域と結合できる。これは、走行方向が一致するならば、移動ロボットをして隣接した領域であっても一つの領域と見なして作業を行うことがさらに効果的であるためである。
【0058】
以上、添付図を参照して本発明の実施例を説明したが、本発明が属する技術分野で当業者ならば本発明がその技術的思想や必須特徴を変更せずとも他の具体的な形に実施されうるということが理解できるであろう。したがって、前述した実施例は全ての面で例示的なものであって、限定的なものではないと理解せねばならない。
【産業上の利用可能性】
【0059】
本発明は、移動ロボットの関連技術分野に好適に用いられる。
【図面の簡単な説明】
【0060】
【図1】従来技術によってロボットが格子マップを作成した概略図である。
【図2】本発明の一実施形態による移動ロボットの格子マップを利用した領域分離方法を示すフローチャートである。
【図3】本発明の一実施形態による移動ロボットの格子マップ作成方法で特徴点の位置を示す概略図である。
【図4A】本発明の一実施形態による移動ロボットの格子マップ作成方法で変換前に作成された格子マップを示す図である。
【図4B】本発明の一実施形態による移動ロボットの格子マップ作成方法でアフィン変換により更新された格子マップを示す図である。
【図5A】障害物を持つ平面空間で臨界点の定義により臨界点を得た概略図である。
【図5B】図5Aの右側壁面をロボットがセンサにより感知した壁面の格子マップを示す概略図である。
【図6】本発明の一実施形態による移動ロボットの格子マップを利用した領域分離方法により障害物を持つ平面空間で特徴点を得た概略図である。
【図7】本発明の一実施形態による移動ロボットの格子マップを利用した領域分離方法でスイープラインにより領域を分離することを示す図である。
【図8A】本発明の一実施形態による移動ロボットの格子マップを利用した領域分離方法により各領域でロボットの走行方向を示す図である。
【図8B】本発明の一実施形態による移動ロボットの格子マップを利用した領域分離方法で領域を結合することを示す図である。
【図9】本発明の一実施形態による格子マップを利用する領域分離移動ロボットのブロック図である。
【符号の説明】
【0061】
900 格子マップ作成部
910 特徴点抽出部
920 特徴点更新部
930 変換式計算部
940 格子マップ更新部
950 スイープライン角度抽出部
960 領域分離部
970 走行方向決定部
980 領域結合部
【技術分野】
【0001】
本発明は、移動ロボットの格子マップ作成方法及び装置及び媒体とこれを利用した領域分離方法及び装置及び媒体に係り、さらに詳細には、ロボットが走行しつつ広い領域の格子マップを作成する方法及び装置と、作成された格子マップを一箇所以上の領域に分離する方法及び装置及び媒体に関する。
【背景技術】
【0002】
一般的に、ロボットは工場や産業で自動化工程に対する方案として開発された。自動制御技術及び遠隔操縦技術などが進歩するにつれて高温、低温などの極限の環境や宇宙や海底などの危険な環境で作業するか、単調な業を反復する場合にロボットが主に応用された。
【0003】
最近には、産業で利用される産業用ロボットだけでなく一般家庭や事務室などで家事や事務補助としてロボットが実用化されている。これに該当する代表的な例として、掃除用ロボット、案内ロボット、防犯ロボットなどを挙げることができる。
【0004】
掃除用ロボットなどの移動ロボットにおいて、ロボットが移動する経路やロボットが活動する区域を指定するためには、まずロボットが認識するマップが必要である。一般的にロボットが認識するマップは、ユーザによりあらかじめ準備されたマップをロボットに入力するか、底や天井でロボットが認識できる標識を利用してロボットをして周囲情報及び自分の位置を認識させるか、ロボット自身が自律走行を通じて活動区域のマップを作成する方案がある。
【0005】
ロボットが自律走行を行いつつマップを作成する方法に多様な試みがなされてきたが、大部分複数のセンサを使用してセンサの誤差による不確実性及び誤差も持っていた。また、ロボットがセンサで認識する範囲は、マップを作成する領域で限定された一部分であるため、このような限定された領域で良質の格子マップを得るとしても、全体としてマップを完成する場合には格子マップの全体的構成が実際マップと差を示すという問題があった。
【0006】
図1は、従来技術によってロボットが格子マップを作成した概略図を示す。
例えば、図1で図示するように元来のマップが方形の部屋ならば、ロボットが部屋を回転して完成した格子マップがそれぞれの面では直線に該当できるが、全体的に格子マップを完成する場合には、方形の形状を認識できない場合があった。したがって、不正確な格子マップによってロボットが自身が行おうとする役割を指定された位置で行えないという問題があった。
【0007】
このように格子マップをなす空間については、複数の領域に分離する方案が好まれている。例えば、掃除用ロボットにおいては、広い空間で一度に掃除を行うよりはそれぞれの部屋や居間のいくつかの領域に分離して掃除させることによって、掃除用ロボットに全体を均一に掃除させ、ロボットが走行しつつ重なる位置や方向などの誤差を低減できる。このような領域分離においても、ロボットをして掃除を行わせる方向に鑑みて領域を分離せねばならないために、単純に面積や距離などに基づいて領域を分離できず、同じ面積であってもロボットが効率的に掃除を行えるように領域を分離せねばならないという問題があった。
【0008】
また、不正確なセンサを使用して格子マップを構成する場合には、障害物枠の屈曲が激しくて、従来の臨界点(Critical point)により領域を分離する方式によっては領域に分離し難かった。
【非特許文献1】IEEE Transactions on Robotics and Automation,Vol 17,No.3,June 2001の‘A Solution to the Simultaneous Localization and Map Building Problem’
【発明の開示】
【発明が解決しようとする課題】
【0009】
本発明は、前記のような問題点に鑑みてなされたものであり、特徴点を格子マップと一致させて相対的に正確な格子マップを得た後に、特徴点を臨界点として見なして領域分離を行うことで、広い空間に対して良質の格子マップを作成し、ロボットが行おうとする機能に合う領域分離を行うことを目的とする。
【0010】
本発明の目的は、以上で言及した目的に制限されず、言及されていない他の目的は下の記載から当業者に明確に理解されうる。
【課題を解決するための手段】
【0011】
前述した目的を達成するために、本発明の一実施形態による移動ロボットの格子マップ作成方法は、(a)外部空間または障害物との距離を感知して格子点を獲得して格子マップを作成するステップと、(b)前記格子点から特徴点を抽出するステップと、(c)ロボットが移動した後にロボット自身の位置を推定して特徴点を再抽出することによって前記特徴点を更新するステップと、(d)前記(b)ステップで抽出された特徴点から、前記(c)ステップで更新された特徴点に変換する変換式を求めるステップと、(e)前記求められた変換式によって格子マップを更新するステップと、を含む。
【0012】
前述した目的を達成するために、本発明の一実施形態による移動ロボットの格子マップ作成方法は、(a)移動ロボットから物体(object)までの距離を感知して獲得した格子点(Grid points)に基づいて格子マップを作成するステップと、(b)前記格子点から特徴点を抽出するステップと、(c)前記移動ロボットが移動した後に前記移動ロボットの位置を推定し、SLAM(Simulatneous Local And Map building)アルゴリズムを利用して前記特徴点を更新するステップと、(d)前記(b)ステップで抽出された特徴点から前記(c)ステップで更新された特徴点に変換する変換式を求めるステップと、(e)前記求められた変換式により格子マップを更新するステップと、を含む。
【0013】
前述した目的を達成するために、本発明の一実施形態によるコンピュータ媒体は、前記方法を行うためにコンピュータが読取可能な命令語を保存したコンピュータ媒体である。
【0014】
前述した目的を達成するために、本発明の一実施形態による移動ロボットの格子マップを利用した領域分離方法は、前述した移動ロボットの格子マップ作成方法である(a)、(b)、(c)、(d)、(e)ステップと、(f)前記更新された格子マップから最多頻度のスイープラインの角度を抽出するステップと、(g)前記抽出されたスイープライン角度によって前記格子マップをスキャンし、前記スイープラインが特徴点を通る地点で前記スイープラインにより領域を分離するステップと、を含む。
【0015】
前述した目的を達成するために、本発明の一実施形態による格子マップ作成移動ロボットは、外部空間または障害物との距離を感知して格子点を獲得して格子マップを作成する格子マップ作成部と、前記格子点から特徴点を抽出する特徴点抽出部と、ロボットが移動した後にロボット自身の位置を推定して特徴点を再抽出することによって前記特徴点を更新する特徴点更新部と、前記特徴点抽出部により抽出された特徴点から前記特徴点更新部により更新された特徴点に変換する変換式計算部と、前記求められた変換式によって格子マップを更新する格子マップ更新部と、を備える。
【0016】
前述した目的を達成するために、本発明の一実施形態による格子マップ作成移動ロボットは移動ロボットから物体までの距離を感知して獲得した格子点に基づいて格子マップを作成する格子マップ作成部と、前記格子点から特徴点を抽出する特徴点抽出部と、ロボットが移動した後にロボット自身の位置を推定し、SLAMアルゴリズムを利用して前記特徴点を更新する特徴点更新部と、前記特徴点抽出部により抽出された特徴点から前記特徴点更新部により更新された特徴点に変換する変換式計算部と、前記求められた変換式により格子マップを更新する格子マップ更新部と、を備える。
【0017】
前述した目的を達成するために、本発明の一実施形態による格子マップを利用した領域分離移動ロボットは、格子マップ作成部、特徴点抽出部、特徴点更新部、変換式計算部、格子マップ更新部と、前記更新された格子マップから最多頻度のスイープラインの角度を抽出するスイープライン角度抽出部と、前記抽出されたスイープライン角度によって前記格子マップをスキャンし、前記スイープラインが特徴点を通る地点で前記スイープラインにより領域分離部と、をさらに備える。
【発明の効果】
【0018】
本発明は、次のような効果が一つあるいはそれ以上ある。
第1に、格子マップと特徴点マップとをマッチングさせて実際に類似する格子マップを作成できる。
第2に、特徴点とスイープラインとによって領域分離を行ってロボットが機能を行うのに適して領域を分離できる。
第3に、各領域ごとに走行方向を各領域に合わせて決定することによって、領域分離後のロボットが領域内で効率的な作業を行える。
【0019】
本発明の効果は、以上で言及した効果に制限されず、言及されていない他の効果は請求の範囲の記載から当業者に明確に理解されうる。
【発明を実施するための最良の形態】
【0020】
その他の実施例の具体的な事項は詳細な説明及び図面に含まれている。
【0021】
本発明の利点及び特徴、そしてこれを達成する方法は添付された図面に基づいて詳細に後述されている実施例を参照すれば明確になる。しかし、本発明は以下で開示される実施例に限定されるものではなく、この実施例から外れて多様な形に具現でき、本明細書で説明する実施例は本発明の開示を完全にし、本発明が属する技術分野で当業者に発明の範ちゅうを完全に報せるために提供されるものであり、本発明は請求項及び発明の詳細な説明によってのみ定義される。一方、明細書全体に亙って同一な参照符号は同一な構成要素を示す。
【0022】
以下、本発明の望ましい実施形態について、添付された図面を参照してさらに詳細に説明する。
【0023】
図2は、本発明の一実施形態による移動ロボットの格子マップを利用した領域分離方法を示すフローチャートである。
【0024】
前述した目的を達成するために、本発明の一実施形態による移動ロボットの格子マップを利用した領域分離方法は、(a)外部空間または障害物との距離を感知して格子点を獲得して格子マップを作成するステップと、(b)前記格子点から特徴点を抽出するステップと、(c)ロボットが移動した後にロボット自身の位置を推定して特徴点を再抽出することによって前記特徴点を更新するステップと、(d)前記(b)ステップで抽出された特徴点から、前記(c)ステップで更新された特徴点に変換する変換式を求めるステップと、(e)前記求められた変換式によって格子マップを更新するステップと、(f)前記更新された格子マップから最多頻度のスイープラインの角度を抽出するステップと、(g)前記抽出されたスイープライン角度によって前記格子マップをスキャンし、前記スイープラインが特徴点を通る地点で前記スイープラインにより領域を分離するステップと、をさらに含む。
【0025】
まず、移動ロボットは、探索しようとする地域に対して自律的に走行を行う。移動ロボットは、距離を感知できる一つ以上のセンサを装着して移動ロボットの前方にある障害物を感知できる。このように移動ロボットは、超音波、赤外線またはレーザーセンサなどの距離感知センサを利用して、障害物や建物内壁の構造をロボット自身を基準に認識できる。このような構造認識方法では、ロボットから構造物または壁面までの距離を感知して複数の点で構成させる格子点330を獲得できる(S205)。ロボットが走行しつつ認識した複数の格子点330を繋げて完成する空間情報が格子マップである。したがって、ロボットは格子点を獲得してデータとして保存して格子マップを作成できる(S205)。感知された複数の格子点から特徴点310、320を抽出できる(S210)。特徴点とは、事物の角またはコーナーのように形状を特定付ける点を意味する。
【0026】
特徴点310、320を抽出するために建物の角部位のようなコーナーまたは角ポインタを抽出するものとして、RANSAC(Random Sample Consensus)または分離と結合(Split and Merge)アルゴリズムを使用できる。RANSACアルゴリズムは、距離データにより獲得された格子点に基づいて、獲得された格子点の一致するセットをランダムに抽出して誤差範囲内を満足する複数の直線を検出する方法であって、検出された複数の直線によって直線と直線とが会う点などを認識してコーナーまたは角を検出し、これを特徴点と見なす。分離及び結合アルゴリズムは、極大点を探してラインに連結し、ラインから外れる点がエラー値より大きい場合には細部ラインに分離でき、隣接したラインでは、一つのラインと認識されうる場合には、結合して全体的な形状のラインを抽出しつつコーナーまたは角を抽出してこれを特徴点とすることができる。
【0027】
ロボットは、走行し続けて自身の位置を把握しつつ周囲に対するマップを作成する。ロボットの位置追跡とマップ作成とを同時に行える方法であるSLAM(Simultaneous Localization And Mapbuilding)アルゴリズムを使用できる。SLAMは、ある位置で周辺環境のマップを作成し、作成されたマップに基づいて再び動いたロボットの位置を把握できる反復を通じて、ロボットの位置と周辺環境のマップとを同時に推定する技術である。それにより、ロボットが走行しつつSLAMアルゴリズムによって特徴点を更新できる(S215)。
例えば、次のようにEKF(Extended Kalman Filter)に基づいたSLAMアルゴリズムを使用できる。
【0028】
【数1】
【0029】
【数2】
式(1)は、ロボットの走行モデル式を示す。ここで、x(k)は、時間ステップkでのロボットの位置、u(k+1)は、制御ベクトル、v(k+1)は、ノイズベクトル、F(k)は、時間ステップkでの状態変換行列である。式(2)は、ロボットが走行しつつi番目特徴点の距離を感知する観察モデル式を示す。ここで、w(k)は、測定値のノイズ、Hはロボットの走行による観察行列である。
【0030】
SLAMアルゴリズムはまず制御ベクトルからロボットの位置を推定する。以後、特徴点に対するセンサの測定値を利用して共分散行列(Covariance matrix)を計算できる。これに基づいてカルマンゲインを計算し、ロボットの位置及び特徴点の位置を更新し、共分散行列を更新する。SLAMアルゴリズムについての説明は、論文IEEE Transactions on Robotics and Automation,Vol 17,No.3,June 2001の‘A Solution to the Simultaneous Localization and Map Building Problem’らに掲示されているので、詳細な説明は省略する。
【0031】
SLAMを行った後には、各特徴点を変化させることができる変換行列(T;Transform Matrix)を探すことができる(S220)。SLAM実行前の特徴点の位置を(x,y)とし、SLAM実行後の各特徴点の位置をそれぞれ(x’,y’)と仮定しよう。SLAM実行後の特徴点の位置(x’,y’)は、補正された特徴点の位置と見なされうる。換言すれば、特徴点の位置を更新することで相対的に正確な特徴点の位置を認識できる。
【0032】
したがって、補正前の特徴点の位置(x,y)を補正された特徴点の位置(x’,y’)に変換するための変換行列Tを求めることができる。変換行列Tを求めるためには多様な変換方法が使われうる。一例として、補正された特徴点の位置を補正前特徴点の位置と1:1にマッピングさせるアフィン変換または線形等角変換が使われうる。もし、変換方式としてアフィン変換を使用する場合には、次の式により変換行列Tを求めることができる。
【0033】
【数3】
式(3)により求められた変換行列Tに基づいて、格子マップの全体領域で変換を行えば格子マップ全体を更新できる。したがって、更新された格子マップは既に補正された特徴点に合わせて更新されることができ、格子マップと特徴点マップとが相互マッチングされうる。
【0034】
図3は、本発明の一実施形態による移動ロボットの格子マップ作成方法で特徴点の位置を示す概略図である。図4Aは、本発明の一実施形態による移動ロボットの格子マップ作成方法で変換前に作成された格子マップであり、図4Bは、本発明の一実施形態による移動ロボットの格子マップ作成方法でアフィン変換により更新された格子マップを示す。
【0035】
例えば、移動ロボットが走行して図3で図示するような格子マップを得たと仮定する。図4Aは、移動ロボットが走行しつつSLAM補正を行う前にロボットのセンサから得られた格子マップを示す。格子マップでは、空間内の概略的な区域は示しており、各特徴点も空間内の区域から抽出されている。例えば、図4Aで図示するように、特徴点が7個に抽出される場合に、移動ロボットは走行しつつ各特徴点を更新し続けられる。特徴点を更新しつつ、更新前の特徴点と更新後の特徴点とを1:1にマッピングさせる変換を求めることができる。例えば、図3の変換式を利用して変換行列Tを求めた場合には、全体格子マップを変換行列Tを利用して変換することによって、図4Bで図示するように更新された格子マップを得ることができる(S225)。更新された格子マップは、更新前の格子マップに比べて区域内の境界を歪めず、全体的に構成した時に相対的に優秀な格子マップを得ることができる。
【0036】
前記のように、格子マップを更新しつつ格子マップ作成を行える(S225)。例えば、アパートの内部でロボットが格子マップを作成する場合には、まず部屋内の格子マップを完成し、続けて他の部屋や居間に移動して特徴点を抽出し、変換行列を求めて格子マップを更新する。それにより、アパート内部の全体区域に対する格子マップ更新を行った後に初めて全体的な格子マップを完成できる。ただし、場合によっては、ロボットが一つの部屋または居間などの一部分に対しても前述した方法による格子マップを作成することができる。
【0037】
図5Aは、障害物550がある平面空間500で臨界点の定義により臨界点を得た概略図であり、図5Bは、図5Aの右側壁面をロボットがセンサにより感知した壁面の格子マップを示す概略図である。図6は、本発明の一実施形態による移動ロボットの格子マップを利用した領域分離方法により、障害物がある平面空間で特徴点を得た概略図であり、図7は、本発明の一実施形態による移動ロボットの格子マップを利用した領域分離方法で、スイープラインにより領域を分離することを示す。
【0038】
格子マップを作成した後には、格子マップに基づいて一つ以上の領域に分離する。一般的にロボットは、スイープライン700方向を決定した後に、スイープラインに沿って合う臨界点510を基準に領域710を分離できる。臨界点についての詳細な内容は、2000 IEEE International Conference on Robotics and Automationに発表されたH.Choset,E.Acar,A.Rizzi,and J.Luntz.の論文‘Exact cellular decompositions interms of critical points of Morse functions’に掲示されている。
【0039】
一般的に、臨界点510は、スイープラインの区域内で一定方向に進行しつつ障害物に合って上下に障害物のない地点を意味する。例えば、図5Aで図示するように、方形の部屋の中に障害物がある場合において、臨界点510は8つに抽出されうる。ただし、図6に示すように、前述した特徴点の抽出によって抽出された特徴点は、空間上の角とコーナーとをいずれも含むものであって10つに抽出できる。しかし、図5Bに示すように、図5Aの右側部分520を拡大すれば、従来の格子マップでは、センサの誤差による屈曲によって不要な臨界点570が生成されて、図5Aとは違って8つより多くの複数の臨界点570を生成するという問題があった。
【0040】
本発明では、臨界点を探す試みなしに前述した格子マップ作成方法で抽出された特徴点を臨界点と見なすことができる。それにより、センサの誤差により発生する不要な臨界点570を考慮せず、領域分離に必要な特徴点310、320のみを利用して領域分離を行える。このように、スイープラインを格子マップ内でスキャンしつつ一つ以上の領域に分離できる。
【0041】
したがって、全体の格子マップに対してスイープラインの角度を決定する(S235)。格子マップの領域内で多様な方法を使用して全体領域内で優勢な頻度を持つラインの角度を求めることができる。例えば、このためにまず領域内に存在する一つ以上のラインを検出した後に、これを角度の同じグループに分けて、そのうち最も加重値の高いライングループの角度をスイープラインがなす角度と決定できる。これを具現するためには、ハフ変換(Hough Transform)、ラドン変換(Radon Transform)またはヒストグラム技法を使用できる。それにより、算出された角度を、全体格子マップ領域で領域分離時のスイープラインの角度と使用できる。
【0042】
前記で得られたスイープラインと特徴点とを利用して全体格子マップ領域から領域を分離できる(S240)。例えば、図7で図示するようにスイープライン角度が90°で得られた場合に表示されたスイープラインのスキャンにより、特徴点と合う地点で領域を分離できる。スイープラインが90°状態で左側から右側に格子マップの内部をスキャンする場合には、5個の領域に分けられうる。格子マップの内部をスキャンしつつスイープラインが一つ以上の特徴点に合うことができ、したがって、一つ以上の領域に分離されうる。ただし、スイープラインがスキャンしつつ同時に一つ以上の特徴点に合う場合には一つの特徴点に合ったと見なして、一回の領域分離がなされうる。
【0043】
図8A及び図8Bに示したように、本発明の一実施形態による移動ロボットの格子マップを利用した領域分離方法で領域を結合することを示す。
【0044】
領域を分離した後には各領域ごとにロボットが走行する方向を決定できる(S245)。例えば、掃除用ロボットの場合には掃除方向を決定するが、本発明のように領域別に掃除しようとする場合には、領域別に掃除方向を決定できる。一般的に掃除方向は、図8Aに図示するように前後(Back and forth)とする。したがって、ロボットが領域内で直線走行を多く行いつつ、回転を少なくする走行方向を掃除方向と決定できる。
【0045】
基本的に領域内で掃除方向を決定するためには、領域内の最も優勢なラインに従うことができる。このために、全体格子マップ領域で最も優勢なスイープラインの角度を決定するのに使用した方法であるハフ変換、ラドン変換またはヒストグラム技法を使用できる。したがって、例えば、図8Aで図示するように、各領域での掃除方向では、I領域は90°、II領域は90°、III領域は0°、IV領域は90°、V領域は0°である。
【0046】
このように、各領域を基準に隣接する領域で掃除方向が同一ならば、ロボットの立場では領域のみ分離されているだけで、掃除するパターン及び方向は同一である。したがって、隣接する領域で掃除方向が同一ならば、一つの領域と見なして領域を合わせる(Pruning)ことができる(S250)。すなわち、図8AではI、II領域が隣接して掃除方向が同一であるので、I、II領域を合わせて一つの領域に見なすことができる。したがって、図8Bで示すように最終的に4つの領域に領域分離されうる。
【0047】
図9では、本発明の一実施形態による格子マップを利用する領域分離移動ロボットのブロック図である。
本発明の一実施形態による格子マップ作成移動ロボットは、ロボットの機能を行う空間の格子マップを作成し、作成された格子マップを一箇所以上の領域に領域分離するために、格子マップ作成部900、特徴点抽出部910、特徴点更新部920、変換式計算部930、格子マップ更新部940を備えることができる。
【0048】
格子マップ作成部900は、ロボットに装着された一つ以上の距離センサを通じてロボットが占める空間の内部壁または障害物までの距離を測定して格子点を獲得し、これをデータとして処理して格子マップを作成する役割を行う。ロボットは、格子マップを作成しようとする領域に対してロボットが走行しつつ距離を感知して格子点を獲得することによって、格子マップを作成することができる。
【0049】
ロボットが周囲環境に対する距離を測定して複数の格子点330を構成することによって、一種の外形をもつ格子マップを形成できる。それにより、複数の格子点から事物の角またはコーナーのように形状を特定させうる点である特徴点310、320を抽出できる。特徴点を抽出するために、距離データにより獲得された格子点に基づいて複数の直線を認識し、直線と直線とが合う点などを認識してコーナーまたは角を検出するRANSACまたは分離及び結合アルゴリズムを使用できる。
【0050】
特徴点更新部920は、移動ロボットが走行しつつSLAMアルゴリズムによりロボットの位置及び特徴点の位置を更新できる。例えば、拡張されたカルマンフィルタに基づいてSLAMアルゴリズムを使用することによって特徴点の位置を補正できる。
【0051】
したがって、変換式計算部930は、特徴点の補正された位置と補正前の位置とを1:1にマッピングさせる変換式を計算する役割を行う。マッピングさせる変換には、アフィン変換または線形等角変換を使用できる。例えば、アフィン変換を使用する場合には、式3を満足させる変換行列Tを求めることができる。
【0052】
格子マップ更新部940は、変換行列Tが求められれば、あらゆる格子マップ領域に変換を行って格子マップ全体を更新する役割を行う。格子マップ更新部940は、特徴点を補正させる変換行列Tを格子マップ全体に適用することによって、特徴点マップと格子マップとをマッチングさせることによって格子マップを更新できる。したがって、更新された格子マップが一定領域に収斂する場合には、更新された格子マップが移動ロボットが作業を行う空間の格子マップになりうる。
【0053】
前記のように構成要素により、移動ロボットは格子マップを作成することができる。本発明の一実施形態による格子マップを利用する領域分離移動ロボットは、作成された格子マップから一つ以上の領域に分離するために、格子マップ作成部900、特徴点抽出部910、特徴点更新部920、変換式計算部930、格子マップ更新部940と、スイープライン角度抽出部950、領域分離部960、走行方向決定部970、領域結合部980を備えることができる。
【0054】
スイープライン角度抽出部950は、格子マップを領域に分離するために、格子マップをスキャンするスイープラインの方向を決定する役割を行う。したがって、スイープライン角度抽出部は、作成された格子マップから優勢なラインの角度を決定できる。これは、格子マップで最も多くの頻度を持つラインをスイープライン方向に決定することによって、格子マップを領域に簡便に分離できる。スイープライン角度を決定するために、格子マップでハフ変換、ラドン変換またはヒストグラム技法を使用して複数のラインを抽出し、これより頻度の最も大きいラインの方向をスイープライン角度方向に抽出できる。
【0055】
領域分離部960は、スイープラインと特徴点を利用して格子マップを領域に分離する役割を行う。領域分離部は、スイープライン角度抽出部により抽出された角度でスイープラインを格子マップでスキャンしつつ特徴点と合う位置を検索する。特徴点と合う位置でスイープラインに格子マップが一つ以上の領域に分離されうる。したがって、スイープラインが複数の特徴点と合う場合には複数の領域が形成されうる。
【0056】
走行方向決定部970は、格子マップ内で領域に分離されたそれぞれの領域内で移動ロボットの走行方向を決定する役割を行う。例えば、移動ロボットが掃除用ロボットであれば、掃除を進行する方向を決定できる。したがって、掃除用ロボットが分離された領域内で効率的な掃除を行うためには、分離された領域内で回転の少ない掃除方向を選択する必要がある。したがって、走行方向決定部は分離された領域内でハフ変換、ラドン変換またはヒストグラム技法を使用してラインを抽出し、抽出されたラインの頻度が最も大きいライン方向を走行方向と決定できる。この場合、分離された領域を特定する境界線もラインと認識して走行方向を決定するところに使われうる。
【0057】
領域結合部980は、一つ以上の分離された領域を一定の基準によって領域を結合する役割を行う。分離された領域を結合する基準は、走行方向決定部により決定された各領域の走行方向を比較して、隣接した領域の走行方向が一致する場合には隣接した領域を一つの領域と結合できる。これは、走行方向が一致するならば、移動ロボットをして隣接した領域であっても一つの領域と見なして作業を行うことがさらに効果的であるためである。
【0058】
以上、添付図を参照して本発明の実施例を説明したが、本発明が属する技術分野で当業者ならば本発明がその技術的思想や必須特徴を変更せずとも他の具体的な形に実施されうるということが理解できるであろう。したがって、前述した実施例は全ての面で例示的なものであって、限定的なものではないと理解せねばならない。
【産業上の利用可能性】
【0059】
本発明は、移動ロボットの関連技術分野に好適に用いられる。
【図面の簡単な説明】
【0060】
【図1】従来技術によってロボットが格子マップを作成した概略図である。
【図2】本発明の一実施形態による移動ロボットの格子マップを利用した領域分離方法を示すフローチャートである。
【図3】本発明の一実施形態による移動ロボットの格子マップ作成方法で特徴点の位置を示す概略図である。
【図4A】本発明の一実施形態による移動ロボットの格子マップ作成方法で変換前に作成された格子マップを示す図である。
【図4B】本発明の一実施形態による移動ロボットの格子マップ作成方法でアフィン変換により更新された格子マップを示す図である。
【図5A】障害物を持つ平面空間で臨界点の定義により臨界点を得た概略図である。
【図5B】図5Aの右側壁面をロボットがセンサにより感知した壁面の格子マップを示す概略図である。
【図6】本発明の一実施形態による移動ロボットの格子マップを利用した領域分離方法により障害物を持つ平面空間で特徴点を得た概略図である。
【図7】本発明の一実施形態による移動ロボットの格子マップを利用した領域分離方法でスイープラインにより領域を分離することを示す図である。
【図8A】本発明の一実施形態による移動ロボットの格子マップを利用した領域分離方法により各領域でロボットの走行方向を示す図である。
【図8B】本発明の一実施形態による移動ロボットの格子マップを利用した領域分離方法で領域を結合することを示す図である。
【図9】本発明の一実施形態による格子マップを利用する領域分離移動ロボットのブロック図である。
【符号の説明】
【0061】
900 格子マップ作成部
910 特徴点抽出部
920 特徴点更新部
930 変換式計算部
940 格子マップ更新部
950 スイープライン角度抽出部
960 領域分離部
970 走行方向決定部
980 領域結合部
【特許請求の範囲】
【請求項1】
(a)外部空間または前記外部空間内の障害物との距離を感知して格子点を獲得して格子マップを作成するステップと、
(b)前記格子点から特徴点を抽出するステップと、
(c)ロボットが移動した後にロボット自身の位置を推定して特徴点を再抽出することによって前記特徴点を更新するステップと、
(d)前記(b)ステップで抽出された特徴点から、前記(c)ステップで更新された特徴点に変換する変換式を求めるステップと、
(e)前記求められた変換式によって格子マップを更新するステップと、を含む移動ロボットの格子マップ作成方法。
【請求項2】
前記距離感知は、距離測定センサを利用して行う請求項1に記載の移動ロボットの格子マップ作成方法。
【請求項3】
前記(b)ステップは、RANSACまたは分離及び結合アルゴリズムを使用して前記特徴点を抽出するステップを含む請求項1に記載の移動ロボットの格子マップ作成方法。
【請求項4】
前記(c)ステップは、前記抽出された特徴点をカルマンフィルタを基盤にしたSLAMアルゴリズムにより更新するステップを含む請求項1に記載の移動ロボットの格子マップ作成方法。
【請求項5】
前記(d)ステップは、アフィン変換または線形等角変換を利用して前記抽出された特徴点を更新された特徴点に変換する前記変換式を求めるステップを含む請求項1に記載の移動ロボットの格子マップ作成方法。
【請求項6】
(f)前記更新された格子マップから最多頻度のスイープラインの角度を抽出するステップと、
(g)前記抽出されたスイープライン角度によって前記格子マップをスキャンし、前記スイープラインが特徴点を通る地点で前記スイープラインにより領域を分離するステップと、をさらに含む請求項1に記載の移動ロボットの格子マップを利用した領域分離方法。
【請求項7】
前記(f)ステップは、ハフ変換、ラドン変換及びヒストグラム技法のうちいずれか一つを使用して、前記更新された格子マップから最多頻度の前記スイープラインの角度を抽出するステップを含む請求項6に記載の移動ロボットの格子マップを利用した領域分離方法。
【請求項8】
分離された領域で最多頻度のスイープラインの角度を抽出してロボットの走行方向に決定するステップをさらに含む請求項6に記載の移動ロボットの格子マップを利用した領域分離方法。
【請求項9】
分離された領域のうちロボットの走行方向が一致する隣接した領域を一つの領域に合わせるステップをさらに含む請求項8に記載の移動ロボットの格子マップを利用した領域分離方法。
【請求項10】
外部空間または前記外部空間内の障害物との距離を感知して格子点を獲得して格子マップを作成する格子マップ作成部と、
前記格子点から特徴点を抽出する特徴点抽出部と、
ロボットが移動した後にロボット自身の位置を推定して特徴点を再抽出することによって前記特徴点を更新する特徴点更新部と、
前記特徴点抽出部により抽出された特徴点から前記特徴点更新部により更新された特徴点に変換する変換式計算部と、
前記求められた変換式によって格子マップを更新する格子マップ更新部と、を備える格子マップ作成移動ロボット。
【請求項11】
前記格子マップ作成部は、超音波、赤外線またはレーザーセンサのような距離測定センサを利用して行う請求項10に記載の格子マップ作成移動ロボット。
【請求項12】
前記特徴点抽出部は、RANSACまたは分離及び結合アルゴリズムを使用して前記特徴点を抽出する請求項10に記載の格子マップ作成移動ロボット。
【請求項13】
前記特徴点更新部は、前記抽出された特徴点をカルマンフィルタを基盤にしたSLAMアルゴリズムにより更新する請求項10に記載の格子マップ作成移動ロボット。
【請求項14】
前記変換式計算部は、アフィン変換または線形等角変換を利用して前記抽出された特徴点を更新された特徴点に変換する前記変換式を求める請求項10に記載の格子マップ作成移動ロボット。
【請求項15】
前記更新された格子マップから最多頻度のスイープラインの角度を抽出するスイープライン角度抽出部と、
前記抽出されたスイープライン角度によって前記格子マップをスキャンし、前記スイープラインが特徴点を通る地点で前記スイープラインにより領域を分離する領域分離部と、をさらに含む請求項10に記載の格子マップを利用した領域分離移動ロボット。
【請求項16】
前記スイープライン角度抽出部は、ハフ変換、ラドン変換及びヒストグラム技法のうちいずれか一つを使用して、前記更新された格子マップから最多頻度の前記スイープラインの角度を抽出する請求項15に記載の格子マップを利用した領域分離移動ロボット。
【請求項17】
分離された領域で最多頻度のスイープラインの角度を抽出してロボットの走行方向に決定する走行方向決定部をさらに含む請求項15に記載の格子マップを利用した領域分離移動ロボット。
【請求項18】
分離された領域のうちロボットの走行方向が一致する隣接した領域を一つの領域に合わせる領域結合部をさらに含む請求項17に記載の格子マップを利用した領域分離移動ロボット。
【請求項19】
前記距離測定センサは超音波、赤外線またはレーザーセンサのうち1つである請求項2に記載の移動ロボットの格子マップ作成方法。
【請求項20】
請求項1に記載の方法を行うためにコンピュータが読取可能な命令語を保存したコンピュータ媒体。
【請求項21】
(a)移動ロボットから物体までの距離を感知して獲得した格子点に基づいて格子マップを作成するステップと、
(b)前記格子点から特徴点を抽出するステップと、
(c)前記移動ロボットが移動した後に前記移動ロボットの位置を推定し、SLAMアルゴリズムを利用して前記特徴点を更新するステップと、
(d)前記(b)ステップで抽出された特徴点から前記(c)ステップで更新された特徴点に変換する変換式を求めるステップと、
(e)前記求められた変換式により格子マップを更新するステップと、を含む移動ロボットの格子マップ作成方法。
【請求項22】
請求項21に記載の方法を行うためにコンピュータが読取可能な命令語を保存したコンピュータ媒体。
【請求項23】
移動ロボットから物体までの距離を感知して獲得した格子点に基づいて格子マップを作成する格子マップ作成部と、
前記格子点から特徴点を抽出する特徴点抽出部と、
ロボットが移動した後にロボット自身の位置を推定し、SLAMアルゴリズムを利用して前記特徴点を更新する特徴点更新部と、
前記特徴点抽出部により抽出された特徴点から前記特徴点更新部により更新された特徴点に変換する変換式計算部と、
前記求められた変換式により格子マップを更新する格子マップ更新部と、を備える格子マップ作成移動ロボット。
【請求項1】
(a)外部空間または前記外部空間内の障害物との距離を感知して格子点を獲得して格子マップを作成するステップと、
(b)前記格子点から特徴点を抽出するステップと、
(c)ロボットが移動した後にロボット自身の位置を推定して特徴点を再抽出することによって前記特徴点を更新するステップと、
(d)前記(b)ステップで抽出された特徴点から、前記(c)ステップで更新された特徴点に変換する変換式を求めるステップと、
(e)前記求められた変換式によって格子マップを更新するステップと、を含む移動ロボットの格子マップ作成方法。
【請求項2】
前記距離感知は、距離測定センサを利用して行う請求項1に記載の移動ロボットの格子マップ作成方法。
【請求項3】
前記(b)ステップは、RANSACまたは分離及び結合アルゴリズムを使用して前記特徴点を抽出するステップを含む請求項1に記載の移動ロボットの格子マップ作成方法。
【請求項4】
前記(c)ステップは、前記抽出された特徴点をカルマンフィルタを基盤にしたSLAMアルゴリズムにより更新するステップを含む請求項1に記載の移動ロボットの格子マップ作成方法。
【請求項5】
前記(d)ステップは、アフィン変換または線形等角変換を利用して前記抽出された特徴点を更新された特徴点に変換する前記変換式を求めるステップを含む請求項1に記載の移動ロボットの格子マップ作成方法。
【請求項6】
(f)前記更新された格子マップから最多頻度のスイープラインの角度を抽出するステップと、
(g)前記抽出されたスイープライン角度によって前記格子マップをスキャンし、前記スイープラインが特徴点を通る地点で前記スイープラインにより領域を分離するステップと、をさらに含む請求項1に記載の移動ロボットの格子マップを利用した領域分離方法。
【請求項7】
前記(f)ステップは、ハフ変換、ラドン変換及びヒストグラム技法のうちいずれか一つを使用して、前記更新された格子マップから最多頻度の前記スイープラインの角度を抽出するステップを含む請求項6に記載の移動ロボットの格子マップを利用した領域分離方法。
【請求項8】
分離された領域で最多頻度のスイープラインの角度を抽出してロボットの走行方向に決定するステップをさらに含む請求項6に記載の移動ロボットの格子マップを利用した領域分離方法。
【請求項9】
分離された領域のうちロボットの走行方向が一致する隣接した領域を一つの領域に合わせるステップをさらに含む請求項8に記載の移動ロボットの格子マップを利用した領域分離方法。
【請求項10】
外部空間または前記外部空間内の障害物との距離を感知して格子点を獲得して格子マップを作成する格子マップ作成部と、
前記格子点から特徴点を抽出する特徴点抽出部と、
ロボットが移動した後にロボット自身の位置を推定して特徴点を再抽出することによって前記特徴点を更新する特徴点更新部と、
前記特徴点抽出部により抽出された特徴点から前記特徴点更新部により更新された特徴点に変換する変換式計算部と、
前記求められた変換式によって格子マップを更新する格子マップ更新部と、を備える格子マップ作成移動ロボット。
【請求項11】
前記格子マップ作成部は、超音波、赤外線またはレーザーセンサのような距離測定センサを利用して行う請求項10に記載の格子マップ作成移動ロボット。
【請求項12】
前記特徴点抽出部は、RANSACまたは分離及び結合アルゴリズムを使用して前記特徴点を抽出する請求項10に記載の格子マップ作成移動ロボット。
【請求項13】
前記特徴点更新部は、前記抽出された特徴点をカルマンフィルタを基盤にしたSLAMアルゴリズムにより更新する請求項10に記載の格子マップ作成移動ロボット。
【請求項14】
前記変換式計算部は、アフィン変換または線形等角変換を利用して前記抽出された特徴点を更新された特徴点に変換する前記変換式を求める請求項10に記載の格子マップ作成移動ロボット。
【請求項15】
前記更新された格子マップから最多頻度のスイープラインの角度を抽出するスイープライン角度抽出部と、
前記抽出されたスイープライン角度によって前記格子マップをスキャンし、前記スイープラインが特徴点を通る地点で前記スイープラインにより領域を分離する領域分離部と、をさらに含む請求項10に記載の格子マップを利用した領域分離移動ロボット。
【請求項16】
前記スイープライン角度抽出部は、ハフ変換、ラドン変換及びヒストグラム技法のうちいずれか一つを使用して、前記更新された格子マップから最多頻度の前記スイープラインの角度を抽出する請求項15に記載の格子マップを利用した領域分離移動ロボット。
【請求項17】
分離された領域で最多頻度のスイープラインの角度を抽出してロボットの走行方向に決定する走行方向決定部をさらに含む請求項15に記載の格子マップを利用した領域分離移動ロボット。
【請求項18】
分離された領域のうちロボットの走行方向が一致する隣接した領域を一つの領域に合わせる領域結合部をさらに含む請求項17に記載の格子マップを利用した領域分離移動ロボット。
【請求項19】
前記距離測定センサは超音波、赤外線またはレーザーセンサのうち1つである請求項2に記載の移動ロボットの格子マップ作成方法。
【請求項20】
請求項1に記載の方法を行うためにコンピュータが読取可能な命令語を保存したコンピュータ媒体。
【請求項21】
(a)移動ロボットから物体までの距離を感知して獲得した格子点に基づいて格子マップを作成するステップと、
(b)前記格子点から特徴点を抽出するステップと、
(c)前記移動ロボットが移動した後に前記移動ロボットの位置を推定し、SLAMアルゴリズムを利用して前記特徴点を更新するステップと、
(d)前記(b)ステップで抽出された特徴点から前記(c)ステップで更新された特徴点に変換する変換式を求めるステップと、
(e)前記求められた変換式により格子マップを更新するステップと、を含む移動ロボットの格子マップ作成方法。
【請求項22】
請求項21に記載の方法を行うためにコンピュータが読取可能な命令語を保存したコンピュータ媒体。
【請求項23】
移動ロボットから物体までの距離を感知して獲得した格子点に基づいて格子マップを作成する格子マップ作成部と、
前記格子点から特徴点を抽出する特徴点抽出部と、
ロボットが移動した後にロボット自身の位置を推定し、SLAMアルゴリズムを利用して前記特徴点を更新する特徴点更新部と、
前記特徴点抽出部により抽出された特徴点から前記特徴点更新部により更新された特徴点に変換する変換式計算部と、
前記求められた変換式により格子マップを更新する格子マップ更新部と、を備える格子マップ作成移動ロボット。
【図1】
【図2】
【図3】
【図4A】
【図4B】
【図5A】
【図5B】
【図6】
【図7】
【図8A】
【図8B】
【図9】
【図2】
【図3】
【図4A】
【図4B】
【図5A】
【図5B】
【図6】
【図7】
【図8A】
【図8B】
【図9】
【公開番号】特開2008−4078(P2008−4078A)
【公開日】平成20年1月10日(2008.1.10)
【国際特許分類】
【出願番号】特願2007−123400(P2007−123400)
【出願日】平成19年5月8日(2007.5.8)
【出願人】(390019839)三星電子株式会社 (8,520)
【氏名又は名称原語表記】Samsung Electronics Co.,Ltd.
【Fターム(参考)】
【公開日】平成20年1月10日(2008.1.10)
【国際特許分類】
【出願日】平成19年5月8日(2007.5.8)
【出願人】(390019839)三星電子株式会社 (8,520)
【氏名又は名称原語表記】Samsung Electronics Co.,Ltd.
【Fターム(参考)】
[ Back to top ]