(57)【特許請求の範囲】
【請求項１】
障害物に関連する環境情報を検出するセンサと、
前記センサにより検出された環境情報に基づく障害物が示されたグリッドマップを生成する生成部と、
前記生成部により生成されたグリッドマップ上において自己位置候補点から前記障害物までの仮想距離を算出して自己の位置を推定する推定部とを備え、
前記グリッドマップは、複数のグリッド要素を含み、
各グリッド要素が、前記障害物を表す障害物情報と、前記障害物に隣接する隣接領域を表す隣接領域情報と、前記障害物から離れた遠隔領域を表す遠隔領域情報とのいずれかを保持しており、
前記隣接領域情報又は前記遠隔領域情報を保持する全てのグリッド要素が、前記隣接領域情報又は前記遠隔領域情報として整数のみを保持することを特徴とする自律移動装置。
【請求項２】
前記遠隔領域情報は、前記障害物との間に存在する他のグリッド要素の数に対応する情報のみを含む請求項１に記載の自律移動装置。
【請求項３】
前記推定部は、前記自己位置候補点から前記障害物に向かう複数の方向について、前記自己位置候補点から前記障害物に衝突した仮想光線が通過したグリッド要素ごとに、各グリッド要素が保持する前記障害物情報と、前記隣接領域情報と、前記遠隔領域情報とのいずれかを読出し、前記隣接領域情報を読み出したグリッド要素と前記障害物との間の衝突判定のための計算を実施する請求項１に記載の自律移動装置。
【請求項４】
前記推定部は、前記遠隔領域情報を読み出したグリッド要素と前記障害物との間の衝突判定のための計算を実施しない請求項１に記載の自律移動装置。
【請求項５】
前記推定部は、前記障害物情報を読み出したグリッド要素の位置と前記自己位置候補点を含むグリッド要素の位置とに基づいて、前記自己位置候補点から前記障害物に衝突した仮想光線に対応する直線の長さを求める請求項１に記載の自律移動装置。
【請求項６】
前記推定部は、前記自己位置候補点を含むグリッド要素が保持する遠隔領域情報をＮ１としたとき（Ｎ１は２以上の整数）、前記自己位置候補点から前記障害物に向かう仮想光線が通過するグリッド要素の（Ｎ１／２）個（但し、小数点以下切り下げ）については前記障害物との間の衝突判定のための計算を実施しない請求項１に記載の自律移動装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、清掃ロボット等の自律的に移動可能な自律移動装置に関する。
【背景技術】
【０００２】
近年、建物内部や屋外の限定された領域内を、周囲の環境情報に基づいて自律的に移動可能な自律移動型ロボット等の自律移動装置が開発されつつある。このような自律移動装置は、移動領域に関して予め記憶された移動マップ上において、現在の自己の位置から特定の目標地点までの移動経路を作成することで自律移動を可能とする。このため、一般的に、自律移動装置は移動領域内における自己位置を認識する機能を備えている。
【０００３】
このような自律移動装置を制御するために、自律移動装置に自己位置を認識させる技術として、例えば予め位置のわかっている反射板を周囲の環境に設置し、自律移動装置に設けたレーザレンジファインダで反射板を計測することによって、三角測量の原理により自己位置を算出するような方法が知られている。
【０００４】
しかしながら、前記の手法では、反射板を設置するために煩雑な作業が必要となり、自己位置推定のため大掛かりな設備工事が必要になるという問題がある。このため、大掛かりな設備工事を必要としないインフラレスの自己位置推定手法が求められている。
【０００５】
大掛かりな設備工事を必要とせずに自己位置を推定する手法としては、移動領域の地図情報と取得した環境情報との比較により自己位置を推定する手法が提案されている。例えば特許文献１に記載の自律移動装置は、レーザレンジファインダで取得した環境情報を地図情報と比較して、自己の位置を認識するものである。また、このような自己位置推定手法としては、グリッドマップを利用する手法が良く用いられている。グリッドマップは移動領域を模擬的に示す地図であり、マップ上には壁や障害物などの存在情報が登録されている（例えば、マップ上の所定のエリアが壁であるか否かを、０又は１のデジタル情報により登録している）。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開2009-223757号公報（2009年10月1日公開）
【発明の概要】
【発明が解決しようとする課題】
【０００７】
こうした、グリッドマップを利用した自己位置推定方法では、自律移動装置が実際の環境において計測したデータと、自律移動装置がグリッドマップ上において仮想的に計測したデータとを比較することにより、自律移動装置の実際の自己位置を推定する。自律移動装置がレーザレンジファインダを備えている場合には、レーザレンジファインダにより取得したデータと、グリッドマップ上で仮想的に計測したデータとを比較することで、自律移動装置の実際の自己位置を精度良く算出することができる。
【０００８】
ここで、グリッドマップ上において自律移動装置が仮想的に計測したデータの算出においては、実際の計測装置による自律移動装置から周囲の障害物までの距離計測を模擬する。前記のように自律移動装置がレーザレンジファインダを備えている場合は、グリッドマップによる自己位置推定計算のため、グリッドマップ上に仮想的に設定した自機の仮想位置から距離計測のためのレーザ光を模擬した直線を周囲の障害物まで伸ばしていき、その直線と障害物との間の衝突の有無を、衝突判定に基づくプログラム計算処理により判定し、自機の仮想位置から障害物までの距離を算出する。こうした計算においては、自機の位置から直線を、グリッドマップを構成するグリッド要素の１マス分伸ばし、当該グリッド要素１マスと障害物との間の衝突判定に基づくプログラム計算処理を行う。衝突判定により衝突が無く障害物が無いと判定されれば、次の１マス分直線を伸ばし、再度、当該グリッド要素１マスと障害物との間の衝突判定を行うことを繰り返す。
【０００９】
このため、１本のレーザ光を模擬した直線について障害物までの距離を仮想的に計測するだけでも、衝突判定に基づくプログラム計算処理を大量に繰り返すことが必要となる。さらに自己位置の推定計算のためにはこうした仮想の直線による距離計測を自機の仮想位置として配置した複数の仮想自己位置（自己位置候補点）の分だけ繰り返す必要があるため、衝突判定に基づくプログラム計算処理の計算量は膨大となる。このため、自律移動装置が実空間内を移動しながら前記のような自己位置の推定計算を行うためには高い演算性能をもつ演算装置が必要となってしまうという問題がある。
【００１０】
本発明の目的は、障害物との間の距離をグリッドマップ上で仮想的に計測するための計算量を削減することができる自律移動装置を提供することにある。
【課題を解決するための手段】
【００１１】
上記の課題を解決するために、本発明の一態様に係る自律移動装置は、障害物に関連する環境情報を検出するセンサと、前記センサにより検出された環境情報に基づく障害物が示されたグリッドマップを生成する生成部と、前記生成部により生成されたグリッドマップ上において自己位置候補点から前記障害物までの仮想距離を算出して自己の位置を推定する推定部とを備え、前記グリッドマップは、複数のグリッド要素を含み、各グリッド要素が、前記障害物を表す障害物情報と、前記障害物に隣接する隣接領域を表す隣接領域情報と、前記障害物から離れた遠隔領域を表す遠隔領域情報とのいずれかを保持していることを特徴とする。
【発明の効果】
【００１２】
本発明の一態様によれば、障害物との間の距離をグリッドマップ上で仮想的に計測するための計算量を削減することができるという効果を奏する。
【図面の簡単な説明】
【００１３】
【図１】実施形態１に係る自律移動装置と移動領域との間の関係を示す図である。
【図２】上記自律移動装置の構成を模式的に示す平面図である。
【図３】上記自律移動装置に搭載されるグリッドマップの構成を説明するための図である。
【図４】上記自律移動装置に設けられた演算部の構成を示すブロック図である。
【図５】上記演算部に設けられたグリッドマップ生成部により生成されるグリッドマップを説明するための図である。
【図６】上記自律移動装置に設けられたレーザレンジファインダによる計測状態を模式的に示した図である。
【図７】上記グリッドマップにより障害物までの距離の仮想計算を実施している状態を示した図である。
【図８】実施形態２に係るグリッドマップにより障害物までの距離の仮想計算を実施している状態を示した図である。
【図９】実施形態３に係るグリッドマップにより障害物までの距離の仮想計算を実施している状態を示した図である。
【図１０】実施形態４に係るグリッドマップにより障害物までの距離の仮想計算を実施している状態を示した図である。
【発明を実施するための形態】
【００１４】
以下、本発明の実施の形態について、詳細に説明する。
【００１５】
〔実施形態１〕
本発明の実施形態１における自律移動装置は、移動領域に存在する物体の位置・形状を示す環境情報を取得するセンサとして、レーザレンジファインダを備えており、移動領域に関する移動マップを用いて、前記レーザレンジファインダで取得した環境情報に基づいて自己位置を認識しつつ移動可能な自律移動装置である。
【００１６】
本発明の実施形態１にかかる自律移動装置について図面を参照しながら説明する。本実施形態における自律移動装置は、１対の車輪を駆動することで平面上を自律的に移動する装置である。
【００１７】
図１は、実施形態１に係る自律移動装置１と移動領域１０２との間の関係を示す図である。図１を参照すると、床部１０１上の限られた移動領域１０２（破線に囲まれた領域）内を、車両型の自律移動装置１が移動する。図１においては、床部１０１上の移動領域１０２内には特に障害物が設置されていない状態を示すものとし、自律移動装置１が移動領域１０２内を任意に移動することができるものとする。
【００１８】
図２は、自律移動装置１の構成を模式的に示す平面図である。図２に示すように、自律移動装置１は、箱型の本体２０１と、１対の対向する車輪２０２ａ・２０２ｂと、キャスタ２０３とを備える対向２輪型の移動装置である。これらの車輪２０２a・２０２ｂとキャスタ２０３とが本体２０１を水平に支持する。さらに、本体２０１の内部には、車輪２０２ａ・２０２ｂをそれぞれ駆動するモータ２０４ａ・２０４ｂと、車輪２０２ａ・２０２ｂの回転数をそれぞれ検出するためのエンコーダ２０５ａ・２０５ｂと、車輪２０２ａ・２０２ｂを駆動するための制御信号を作成し、モータ２０４ａ・２０４ｂにその制御信号を送信する演算部２０６と、及びこれらの構成要素に電力を供給するためのバッテリー２０７とが備えられている。そして、演算部２０６内部に備えられた記憶部としてのメモリなどの記憶領域２０６ａには、制御信号に基づいて自律移動装置１の移動速度や移動方向、移動距離などを制御するためのプログラムとともに、移動領域１０２の形状及び大きさがマップ情報として記憶されている。
【００１９】
さらに、本体２０１の前面には、自律移動装置１が移動する方向（前方）の環境情報を認識するためのレーザレンジファインダ２が設けられている。レーザレンジファインダ２は、詳細な構造については省略するが、本体２０１の前方に対して所定の広がり角度でレーザ光を照射するための光源と、光源より照射されたレーザ光の反射光を受光するための受光部とを備えている。そして、レーザ光を照射した角度と、反射するまでに要した時間とに基づいて、レーザ光を反射した障害物の位置を検出するという、いわゆるＴＯＦ（Time of flight）の原理による物体検知（センシング）が行われる。尚、レーザレンジファインダ２により環境情報（センシングされる物体の位置及び形状）を得る手順の詳細については後述する。
【００２０】
また、自律移動装置１は、自己の位置を取得するための自己位置取得部を備えている。この自己位置取得部は、前述したエンコーダ２０５ａ・２０５ｂ及び演算部２０６とから構成される。すなわち、エンコーダ２０５ａ・２０５ｂで検知された車輪２０２ａ・２０２ｂの回転数を演算部２０６において積算することで、自律移動装置１の移動した速度や距離などの情報を求め、これらの情報から、移動領域内における自律移動装置１の自己位置（オドメトリ位置）を算出する。
【００２１】
そして、これらの自己位置取得部より得られた自己位置候補としての位置情報は、後述するレーザレンジファンダ２０８により得られる環境情報に基づいて適宜修正される。なお、この位置情報を修正する手法の詳細については後述する。
【００２２】
このように構成された自律移動装置１は、１対の車輪２０２ａ・２０２ｂの駆動量をそれぞれ独立に制御することで、直進や曲線移動（旋回）、後退、その場回転（両車輪の中点を中心とした旋回）などの移動動作を行うことができる。そして、自律移動装置１は、移動場所を指定する外部に設けられたＰＣ（Personal Computer）等（図示せず）からの指令にしたがって、移動領域１０２内の指定された目的地までの移動経路を自律的に作成し、その移動経路に追従するように移動することで、目的地に到達する。なお、移動経路の自律的な作成は演算装置１５において実行されるが、ここでは説明を省略する。
【００２３】
次に、記憶領域２０６ａの内部に記憶された、移動領域１０２の形状や、その内部に含まれる物体（壁などの障害物）に基づいて作成される移動マップとしてのグリッドマップについて説明する。演算部２０６内部に備えられた記憶領域２０６ａには、床部１０１上の移動領域１０２全体の形状を外枠として、その内部に一定間隔ｍ（例えば５ｃｍ）で水平方向及び垂直方向に配置された格子点を結ぶグリッド線を仮想的に描写することで得られるグリッドマップが記憶されている。
【００２４】
図３に、前述のグリッドマップの一例を図示する。グリッドマップＧＭ１は、移動領域１０２の形状を模した外枠３０２の内部を、一定の間隔ｍで水平方向及び垂直方向に配置された格子点を水平方向及び垂直方向に結ぶグリッド線３０３を描写したものである。そして、このグリッド線３０３で囲まれたグリッド要素ＧＥにより、自律移動装置１の自己位置に相当する場所、及び目的地である移動終了点、及び移動終了点における自律移動装置１の移動方向が特定される。なお、間隔ｍは、自律移動装置１の移動可能な曲率や絶対位置を認識する精度などの条件に応じて、適宜変更可能である。スリップしたと判定される際の閾値としても間隔ｍを用いることができる。また、移動領域１０２内において、壁や障害物等の固定物体が存在していることが既知である場合は、それらの既知の物体の位置が予めグリッドマップＧＭ１上に登録された形で記憶領域２０６ａに記憶されているものとする。
【００２５】
図４は、自律移動装置１に設けられた演算部２０６の構成を示すブロック図である。演算部２０６には、グリッドマップ生成部３（生成部）と自己位置推定部４（推定部）とが設けられている。グリッドマップ生成部３は、レーザレンジファインダ２（センサ）により検出された環境情報に基づく障害物が示されたグリッドマップを生成する。自己位置推定部４は、グリッドマップ生成部３により生成されたグリッドマップ上において自己位置候補点から障害物までの仮想距離を算出して自己の位置を推定する。
【００２６】
ここで、グリッドマップの各グリッド要素における障害物からの距離情報について説明する。図５は、演算部２０６に設けられたグリッドマップ生成部３により生成されるグリッドマップＧＭ２を説明するための図である。グリッドマップＧＭ２は、障害物ＯＢが存在する領域と、自律移動装置１が走行可能な領域とに分けられる。こうしたグリッドマップＧＭ２のグリッド要素に、以下の手順で障害物ＯＢからの距離情報を付加する。
（１）各グリッド要素は、障害物ＯＢが存在する障害物領域Ｒ１であるか否かを示す障害物情報が予め書き込まれている。例えば、当該グリッド要素が障害物ＯＢの存在する障害物領域Ｒ１である場合には、当該グリッド要素に距離「０」（障害物情報）が書き込まれ、障害物ＯＢの存在する障害物領域Ｒ１でない場合には、当該グリッド要素に「−１」が書き込まれる。
（２）「−１」が書き込まれたグリッド要素の１つについて、隣のグリッド要素が障害物ＯＢの存在する障害物領域Ｒ１であれば、当該グリッド要素に距離「１」（隣接領域情報）が上書きされる。
（３）上記（２）を「−１」が書き込まれた全てのグリッド要素について繰り返す。
（４）「−１」が書き込まれたグリッド要素の１つについて、隣のグリッド要素に距離「１」が書き込まれていれば、当該グリッド要素に距離「２」（遠隔領域情報）が上書きされる。
（５）上記（４）を「−１」が書き込まれた全てのグリッド要素について繰り返す。
（６）以降同様に、「−１」が書き込まれたグリッド要素の１つについて、隣のグリッド要素に距離「ｎ−１」が書き込まれていれば、当該グリッド要素に距離「ｎ」を上書きし（ｎは３以上の整数）、それを、「−１」が書き込まれた全てのグリッド要素について繰り返す。
（７）上記（６）をグリッドマップの全てのグリッド要素に距離「０」以上が上書きされるまで繰り返す。
【００２７】
図５に示す例では、障害物ＯＢが存在するグリッド要素に対応する障害物領域Ｒ１に障害物情報を表す距離「０」が書き込まれる。そして、障害物領域Ｒ１に隣接するグリッド要素に対応する隣接領域Ｒ２に、障害物ＯＢに隣接する隣接領域Ｒ２を表す隣接領域情報の距離「１」が書き込まれる。障害物領域Ｒ１及び隣接領域Ｒ２に対応するグリッド要素以外のグリッド要素は、障害物ＯＢから離れた遠隔領域Ｒ３に含まれる。遠隔領域Ｒ３は、隣接領域Ｒ２に障害物ＯＢの反対側から隣接する第１遠隔隣接領域Ｒ４と、第１遠隔隣接領域Ｒ４に障害物ＯＢの反対側から隣接する第２遠隔隣接領域Ｒ５とを含む。
【００２８】
第１遠隔隣接領域Ｒ４には、障害物ＯＢから離れた遠隔領域を表す遠隔領域情報の距離「２」が書き込まれる。第２遠隔隣接領域Ｒ５には、遠隔領域情報の距離「３」が書き込まれる。遠隔領域情報の距離の値は、障害物ＯＢから離れるに従って大きくなり、障害物ＯＢとの間に存在する他のグリッド要素の数に対応する。
【００２９】
このグリッドマップＧＭ２に障害物ＯＢからの距離に関連する情報を与える作業は、自律移動装置１により移動マップが作成された直後に１回だけ実行されるだけでよく、以降は同じグリッドマップを使用することができる。なお、障害物ＯＢの種別、自律移動装置１の進入禁止エリアなどの付帯情報を各グリッド要素ＧＥに与える場合もあるが、説明をより簡潔にするため、これらの情報については説明を省略する。
【００３０】
図６は、自律移動装置１に設けられたレーザレンジファインダ２による計測状態を模式的に示した図である。次に、前述したレーザレンジファインダ２を用いて自律移動装置１の前面の環境情報を取得する手法について、簡単に説明する。まず、自律移動装置１のレーザレンジファインダ２から照射されたレーザによる実光線ＲＬの障害物ＯＢによる反射光がレーザレンジファインダ２により受光されると、実光線ＲＬを照射したときの自律移動装置１の自己位置と、レーザレンジファインダ２から照射される実光線ＲＬの照射方向と、実光線ＲＬを照射してから反射光を受光するまでの時間とから、照射した実光線ＲＬが反射した地点が特定される。
【００３１】
レーザレンジファインダ２によって計測されるデータは、レーザレンジファインダ２からの実測距離Ｒｄ及び実光線ＲＬの照射方向の角度φにより規定される極座標系として出力される。例えば自律移動装置１の進行方向前方２７０度を計測する際の分解能を１．０度とした場合には、一度のスキャンにより２７１個のデータを計測する。このようなレーザレンジファインダ２によるセンシング結果が記憶領域２０６ａに記憶される。
【００３２】
図６は、移動領域内において、自律移動装置１の前面に障害物ＯＢが設けられている様子を示している。図６に示すように、自律移動装置１はその前面にレーザレンジファインダ２から実光線ＲＬを照射している。このとき、レーザレンジファインダ２のセンシング領域内には障害物ＯＢが含まれている。このような場合、レーザレンジファインダ２によりセンシングされた障害物ＯＢまでの距離が記憶領域２０６ａに記憶される。このようにして取得された環境情報をもとにグリッドマップが生成され、記憶領域２０６ａに記憶される。
【００３３】
図７は、グリッドマップＧＭ２により障害物ＯＢまでの距離の仮想計算を実施している状態を示した図である。次に、レーザレンジファインダ２により取得した環境情報を用いて、オドメトリ法により算出した自己位置候補の中から現時点の自己位置を推定する手法として、本実施形態では、ＭＣＬ（Monte Carlo Localization）と呼ばれる手法を採用する。これは、ロボットの存在位置の確率表現を、パーティクルＰ（自己位置候補点）と呼ばれる位置候補点により表現する手法である。
【００３４】
ここでは、本実施形態に係るグリッド要素から障害物ＯＢまでの距離情報を用いた計算手法を説明する。本実施形態では、ＭＣＬの演算における自己位置の候補となるパーティクルＰからレーザによる仮想光線を周囲に向けて照射し、距離計算を行う時の距離計算手法を説明する。
【００３５】
まず、演算部２０６に設けられた自己位置推定部４は、グリッドマップＧＭ２上において、パーティクルＰの位置から、レーザレンジファインダ２の計測方向に沿って直線を延ばす。即ち、グリッドマップＧＭ２上において、パーティクルＰの位置から仮想光線ＶＬを仮想的に描写する。
【００３６】
ここで、図７を参照すると、１つのパーティクルＰから仮想光線ＶＬを伸ばして距離計算を行うとすると、パーティクルＰを含むグリッド要素を起点として、所定の角度で伸ばされる仮想光線ＶＬがグリッド要素を順に通過していく。ここで、グリッドマップＧＭ２に関して横方向をｘ方向、縦方向をｙ方向とする。グリッドマップＧＭ２のグリッド要素を仮想光線ＶＬが通過していくには、予め仮想光線ＶＬの傾きがわかっているため、１マス分ｘ方向、もしくはｙ方向に仮想光線ＶＬを進めた時にもう一つの軸、つまり、ｘ方向に仮想光線ＶＬのグリッド要素のマス目を進めた場合はｙ方向、ｙ方向にマス目を進めた場合はｘ方向に升目を進ませるかどうかを仮想光線ＶＬの傾きをもとに計算する手法をとる。こればブレゼンハムの直線描画アルゴリズムと呼ばれる手法である。
【００３７】
仮想光線ＶＬが通過するグリッド要素に書き込まれた距離の値が２以上である間は、当該グリッド要素が障害物ＯＢと衝突しているおそれは無いと判断されるから、衝突判定処理が不要になる。そして、仮想光線ＶＬが通過するグリッド要素に書き込まれた距離の値が１になった時以降に、衝突判定処理を実施すればよいと考えられる。
【００３８】
例えば、パーティクルＰを含むグリッド要素には、距離「５」が書き込まれている。そして、パーティクルＰからの仮想光線ＶＬが通過する上から７行目、右から３列目のグリッド要素には「２」以上である「５」が書き込まれているので、衝突判定処理を実施しない。同様に、仮想光線ＶＬが通過する上から６行目、右から３列目のグリッド要素には「５」が書き込まれており、上から５行目、右から３列目のグリッド要素には「４」が書き込まれており、上から４行目、右から３列目のグリッド要素には「３」が書き込まれている。そして、仮想光線ＶＬが通過する上から４行目、右から２列目のグリッド要素には「３」が書き込まれており、上から３行目、右から２列目のグリッド要素には「２」が書き込まれている。このため、「５」〜「２」が書き込まれたこれらのグリッド要素については、衝突判定処理を実施しない。そして、仮想光線ＶＬが通過する上から２行目、右から２列目のグリッド要素には「１」が書き込まれているため、衝突判定処理を実施する。
【００３９】
このように、「２」以上が書き込まれているグリッド要素については衝突判定処理を実施せず、「１」が書き込まれているグリッド要素について衝突判定処理を実施するので、パーティクルＰと障害物ＯＢとの間の距離をグリッドマップ上で仮想的に計測するための計算量を削減することができる。
【００４０】
グリッドマップの各グリッド要素に障害物ＯＢからの距離に対応する値が書き込まれていない場合は、グリッドマップ上のグリッド要素を仮想光線ＶＬが１マス進むたびに、グリッド要素の値を呼び出して、当該グリッド要素が障害物ＯＢかどうかを判断する衝突判定処理が必要になるが、本実施形態によれば、そうしたグリッド要素の値の読出しと衝突判定処理とを行うことなく、仮想光線ＶＬがグリッド要素を通過することができる。
【００４１】
前述したように、グリッド要素に書き込まれた距離の値が２以上である間は衝突判定をせずに仮想光線ＶＬがグリッド要素を通過することができるが、グリッド要素に書き込まれた距離の値が１になった時以降は仮想光線ＶＬがグリッド要素を１マス移動し、その移動後のグリッド要素で障害物ＯＢとの衝突判定を行う。そのグリッド要素が障害物ＯＢであれば、そのグリッド要素の位置とパーティクルＰを含むグリッド要素の位置とからパーティクルＰから障害物ＯＢに伸ばした直線の長さを求めることができる。このように、一つの仮想光線ＶＬによる計測を模したパーティクルＰと障害物ＯＢとの間の距離データを算出することができる。以降同様に各パーティクルについて障害物ＯＢとの間の距離計測を繰り返す。
【００４２】
このように本実施形態に係るパーティクルＰと障害物ＯＢとの間の距離計測は実行される。以降もＭＣＬの演算が続くがここでは説明を省略する。
【００４３】
本実施形態に係る計算方法はグリッドマップのグリッド要素の一つ一つについて障害物ＯＢとの衝突判定処理を実施する必要がないため、演算を高速に行うことができる。特に、ＭＣＬにおいては数百の各パーティクルに対して複数の角度について仮想光線ＶＬによる障害物ＯＢまでの距離計算を繰り返す。このため、衝突判定処理が一つ省略されるだけでも、１度の自己位置推定計算においては計算処理の軽減効果は大きい。さらに、ＭＣＬの演算は自律移動装置１が移動しながら繰り返し実行されるため、ＭＣＬの演算処理負荷が小さくなり、１回あたりの自己位置推定時間が短くなれば、より短い周期で自律移動装置１の自己位置推定が可能となり実際の移動位置の精度を高めることができる。
【００４４】
〔実施形態２〕
本発明の他の実施形態について、図８に基づいて説明すれば、以下のとおりである。なお、説明の便宜上、前記実施形態にて説明した部材と同じ機能を有する部材については、同じ符号を付記し、その説明を省略する。
【００４５】
実施形態２においては、前記したグリッドマップＧＭ２においてパーティクルＰから仮想光線ＶＬが各グリッド要素を通過していく過程の演算において、パーティクルＰを含むグリッド要素における障害物ＯＢからの距離に対応する値Ｎをもとに、仮想光線ＶＬがグリッド要素を順に通過していく際の演算の開始位置を以下の手順に沿って変更する。
（１）パーティクルＰを含むグリッド要素の位置の座標を（ｘｉ，ｙｉ）とする。
（２）パーティクルＰから発する仮想光線ＶＬの角度は既知であり、その値をφとする。
（３）仮想光線ＶＬがグリッド要素を通過する際の衝突判定処理に係る演算の開始位置ＳＰの座標を（ｘｊ，ｙｊ）とすると、
ｘｊ＝Ｎ×cosφ、ｙｊ＝Ｎ×sinφ
で衝突判定処理に係る演算の開始位置ＳＰの座標を求める。
【００４６】
このようにグリッドマップ上の衝突判定処理に係る演算の開始位置ＳＰを上記のようにパーティクルＰから障害物ＯＢに近い位置まで飛ばしてしまうことになる。このため、衝突判定処理は、パーティクルＰから開始位置ＳＰまでの間のグリッド要素については不要であり、開始位置ＳＰから障害物ＯＢまでの間のグリッド要素についてのみ実施すればよい。従って、仮想光線ＶＬがグリッド要素上で衝突判定処理を実施する演算量はさらに少なくなる。
【００４７】
〔実施形態３〕
実施形態３に係る自律移動装置について説明する。図９は、実施形態３に係るグリッドマップＧＭ３により障害物ＯＢまでの距離の仮想計算を実施している状態を示した図である。説明の便宜上、前記実施形態にて説明した部材と同じ機能を有する部材については、同じ符号を付記し、その説明を省略する。
【００４８】
実施形態３においては、前記した障害物ＯＢからの距離に対応する情報を各グリッド要素に与えるグリッドマップＧＭ３の生成について、以下の手順で障害物ＯＢからの距離に対応する情報を与える。
（１）各グリッド要素は、障害物ＯＢが存在する障害物領域Ｒ１であるか否かを示す障害物情報が予め書き込まれている。例えば、当該グリッド要素が障害物ＯＢの存在する障害物領域Ｒ１である場合には、当該グリッド要素に距離「０」（障害物情報）が書き込まれ、障害物ＯＢの存在する障害物領域Ｒ１でない場合には、当該グリッド要素に「−１」が書き込まれる。
（２）距離「０」が書き込まれたグリッド要素の位置をリスト化する。
（３）上記（２）で距離「０」が書き込まれた各グリッド要素の上下左右のグリッド要素について、「−１」が書き込まれていれば、距離「１」を書き込む。
（４）距離「１」が書き込まれたグリッド要素の位置をリスト化する。
（５）上記（３）〜（４）を、距離情報を１ずつ増やしながら距離情報を書き込むグリッド要素が無くなるまで繰り返す。
【００４９】
こうすれば、実施形態１のようにグリッドマップの全グリッド要素について繰り返し判定処理を行うことなく、障害物ＯＢからの距離に対応する情報をすべてのグリッド要素に書き込むことができるため、計算負荷の低減を図ることが可能となる。
【００５０】
〔実施形態４〕
実施形態４に係る自律移動装置について説明する。図１０は、実施形態４に係るグリッドマップＧＭ２により障害物ＯＢまでの距離の仮想計算を実施している状態を示した図である。説明の便宜上、前記実施形態にて説明した部材と同じ機能を有する部材については、同じ符号を付記し、その説明を省略する。
【００５１】
実施形態４においては、前記した障害物ＯＢからの距離に対応する情報をもとに、衝突判定を何回実施せずに済ませるかを以下のように処理する。
（１）あるパーティクルＰの位置のグリッド要素に書き込まれた距離情報をＮ１とする。
（２）仮想光線ＶＬが通過するグリッド要素の（Ｎ１／２）個については衝突判定をしない。
（３）上記（２）で衝突判定をせずに進んで到着したグリッド要素に書き込まれた距離情報をＮ２とする。
（４）そこから仮想光線ＶＬがさらに通過するグリッド要素の（Ｎ２／２）個については衝突判定をしない。
（５）上記（３）〜（４）を繰り返す。
【００５２】
例えば、図１０に示す例では、パーティクルＰのグリッド要素に距離「５」が書き込まれている。そして、仮想光線ＶＬが通過するグリッド要素の（Ｎ１／２＝５／２＝２）個（但し、小数点以下切り下げ）については衝突判定をしない。次に、衝突判定をせずに進んで到着した到着点Ｐ２のグリッド要素に距離「Ｎ２＝５」が書き込まれている。
【００５３】
その後、到着点Ｐ２から仮想光線ＶＬがさらに通過するグリッド要素の（Ｎ２／２＝５／２＝２）個（但し、小数点以下切り下げ）については衝突判定をしない。上記で衝突判定をせずに進んで到着した到着点Ｐ３のグリッド要素に距離「Ｎ２＝３」が書き込まれている。
【００５４】
そして、到着点Ｐ３から仮想光線ＶＬがさらに通過するグリッド要素の（Ｎ２／２＝３／２＝１）個（但し、小数点以下切り下げ）については衝突判定をしない。上記で衝突判定をせずに進んで到着した到着点Ｐ４のグリッド要素に距離「Ｎ２＝２」が書き込まれている。次に、到着点Ｐ４からは衝突判定処理に係る演算を実施する。従って、パーティクルＰから到着点Ｐ４までの間のグリッド要素については衝突判定処理が不要である。
【００５５】
このように処理することで、実施形態２（図８）のように三角関数のような計算が複雑になる処理を行うことなく、より単純な方法でパーティクルＰから伸ばした直線の衝突判定を行うことができる。
【００５６】
〔ソフトウェアによる実現例〕
自律移動装置１の演算部２０６（特にグリッドマップ生成部３および自己位置推定部４）は、集積回路（ＩＣチップ）等に形成された論理回路（ハードウェア）によって実現してもよいし、ＣＰＵ（Central Processing Unit）を用いてソフトウェアによって実現してもよい。
【００５７】
後者の場合、演算部２０６は、各機能を実現するソフトウェアであるプログラムの命令を実行するＣＰＵ、上記プログラムおよび各種データがコンピュータ（またはＣＰＵ）で読み取り可能に記録されたＲＯＭ（Read Only Memory）または記憶装置（これらを「記録媒体」と称する）、上記プログラムを展開するＲＡＭ（Random Access Memory）などを備えている。そして、コンピュータ（またはＣＰＵ）が上記プログラムを上記記録媒体から読み取って実行することにより、本発明の目的が達成される。上記記録媒体としては、「一時的でない有形の媒体」、例えば、テープ、ディスク、カード、半導体メモリ、プログラマブルな論理回路などを用いることができる。また、上記プログラムは、該プログラムを伝送可能な任意の伝送媒体（通信ネットワークや放送波等）を介して上記コンピュータに供給されてもよい。なお、本発明は、上記プログラムが電子的な伝送によって具現化された、搬送波に埋め込まれたデータ信号の形態でも実現され得る。
【００５８】
〔まとめ〕
本発明の態様１に係る自律移動装置１は、障害物ＯＢに関連する環境情報を検出するセンサ（レーザレンジファインダ２）と、前記センサ（レーザレンジファインダ２）により検出された環境情報に基づく障害物ＯＢが示されたグリッドマップＧＭ１〜ＧＭ３を生成する生成部（グリッドマップ生成部３）と、前記生成部（グリッドマップ生成部３）により生成されたグリッドマップＧＭ１〜ＧＭ３上において自己位置候補点（パーティクルＰ）から前記障害物ＯＢまでの仮想距離を算出して自己の位置を推定する推定部（自己位置推定部４）とを備え、前記グリッドマップＧＭ１〜ＧＭ３は、複数のグリッド要素ＧＥを含み、各グリッド要素ＧＥが、前記障害物ＯＢを表す障害物情報と、前記障害物ＯＢに隣接する隣接領域Ｒ２を表す隣接領域情報と、前記障害物ＯＢから離れた遠隔領域Ｒ３を表す遠隔領域情報とのいずれかを保持している。
【００５９】
上記の構成によれば、グリッドマップが遠隔領域を表す遠隔領域情報を有しているので、遠隔領域情報に対応する遠隔領域を仮想光線が仮想的に通過する際は、衝突判定処理に係る演算を実施する必要がなくなる。この結果、自己の位置を推定するために、障害物との間の距離をグリッドマップ上で仮想的に計測するための計算量を削減することができる。
【００６０】
本発明の態様２に係る自律移動装置１は、上記態様１において、前記遠隔領域Ｒ３が、前記隣接領域Ｒ２に前記障害物ＯＢの反対側から隣接する第１遠隔隣接領域Ｒ４と、前記第１遠隔隣接領域Ｒ４に前記障害物ＯＢの反対側から隣接する第２遠隔隣接領域Ｒ５とを含んでもよい。
【００６１】
上記の構成によれば、第２遠隔隣接領域が第１遠隔隣接領域よりも障害物ＯＢから離れている。このため、障害物ＯＢからの距離に対応する情報を第１遠隔隣接領域及び第２遠隔隣接領域に対応するグリッド要素に書き込むことができる。
【００６２】
本発明の態様３に係る自律移動装置１は、上記態様１において、前記遠隔領域情報は、前記障害物ＯＢとの間に存在する他のグリッド要素の数に対応する情報を含んでもよい。
【００６３】
上記の構成によれば、障害物ＯＢからの距離に対応する情報を遠隔領域に対応するグリッド要素に書き込むことができる。
【００６４】
本発明の態様４に係る自律移動装置１は、上記態様１において、前記センサ（レーザレンジファインダ２）により検出された環境情報は前記障害物ＯＢまでの実測距離を表す情報を含み、前記推定部（自己位置推定部４）は、各グリッド要素が保持する前記障害物情報、前記隣接領域情報、及び前記遠隔領域情報に基づいて、前記仮想距離を算出してもよい。
【００６５】
上記の構成によれば、遠隔領域情報に対応する遠隔領域では、衝突判定処理に係る演算を実施しないので、障害物との間の距離をグリッドマップ上で仮想的に計測するための計算量を削減することができる。
【００６６】
本発明の態様５に係る自律移動装置１は、上記態様１において、前記推定部（自己位置推定部４）は、前記自己位置候補点（パーティクルＰ）から前記障害物ＯＢに衝突した仮想光線ＶＬが通過したグリッド要素ごとに、各グリッド要素が保持する前記障害物情報と、前記隣接領域情報と、前記遠隔領域情報とのいずれかを読出し、前記隣接領域情報を読み出したグリッド要素と前記障害物ＯＢとの間の衝突判定のための計算を実施してもよい。
【００６７】
上記の構成によれば、遠隔領域情報を読出したグリッド要素で、当該グリッド要素と前記障害物ＯＢとの間の衝突判定のための計算を実施しないので、障害物との間の距離をグリッドマップ上で仮想的に計測するための計算量を削減することができる。
【００６８】
本発明の態様６に係る自律移動装置１は、上記態様１において、前記センサが、レーザレンジファインダ２であってもよい。
【００６９】
上記の構成によれば、簡単な構成により、障害物に関連する環境情報を検出することができる。
【００７０】
本発明の各態様に係る自律移動装置の演算部は、コンピュータによって実現してもよく、この場合には、コンピュータを上記演算部が備える各手段として動作させることにより上記演算部をコンピュータにて実現させる自律移動装置の演算部制御プログラム、およびそれを記録したコンピュータ読み取り可能な記録媒体も、本発明の範疇に入る。
【００７１】
本発明は上述した各実施形態に限定されるものではなく、請求項に示した範囲で種々の変更が可能であり、異なる実施形態にそれぞれ開示された技術的手段を適宜組み合わせて得られる実施形態についても本発明の技術的範囲に含まれる。さらに、各実施形態にそれぞれ開示された技術的手段を組み合わせることにより、新しい技術的特徴を形成することができる。
【産業上の利用可能性】
【００７２】
本発明は、清掃ロボット等の自律的に移動可能な自律移動装置に利用することができる。
【符号の説明】
【００７３】
１  自律移動装置
２  レーザレンジファインダ（センサ）
３  グリッドマップ生成部（生成部）
４  自己位置推定部（推定部）
ＯＢ  障害物
ＧＭ１  グリッドマップ
ＧＭ２  グリッドマップ
ＧＭ３  グリッドマップ
Ｐ  パーティクル（自己位置候補点）
Ｐ２  到着点
Ｐ３  到着点
Ｐ４  到着点
ＧＥ  グリッド要素
Ｒ１  障害物領域
Ｒ２  隣接領域
Ｒ３  遠隔領域
Ｒ４  第１遠隔隣接領域
Ｒ５  第２遠隔隣接領域
ＲＬ  実光線
ＶＬ  仮想光線
Ｒｄ  実測距離
Ｖｄ  仮想距離
ＳＰ  開始位置
【要約】
【課題】障害物との間の距離をグリッドマップ上で仮想的に計測するための計算量を削減する。
【解決手段】自律移動装置のグリッドマップ（ＧＭ２）が、複数のグリッド要素を含み、各グリッド要素が、障害物（ＯＢ）を表す障害物情報と、障害物（ＯＢ）に隣接する隣接領域（Ｒ２）を表す隣接領域情報と、障害物（ＯＢ）から離れた遠隔領域（Ｒ３）を表す遠隔領域情報とのいずれかを保持している。
【選択図】図７【図１】
0005902275.tif 000002
【図２】
0005902275.tif 000003
【図３】
0005902275.tif 000004
【図４】
0005902275.tif 000005
【図５】
0005902275.tif 000006
【図６】
0005902275.tif 000007
【図７】
0005902275.tif 000008
【図８】
0005902275.tif 000009
【図９】
0005902275.tif 000010
【図１０】
0005902275.tif 000011