(57)【特許請求の範囲】
【請求項１】
自律して走行する移動ロボットの前方側の領域を走行可能領域及び走行不能領域に区分けする走行領域判別装置であって、
レーザ光を走査して前記移動ロボットの前方側のプロファイルデータを取得するレーザレンジファインダを具備した外界計測部と、
この外界計測部のレーザレンジファインダで得たプロファイルデータを構成する（Ｎ）個の計測点データ間における（Ｎ−１）個の境界点位置に、互いに隣接する計測点データ同士が同一領域であるか否かに応じた２状態の状態変数を定義することで、前記プロファイルデータの任意の領域分割状態を２（Ｎ−１）の状態空間のうちの一状態として表現し、互いに異なる幾何的特徴を有する領域を評価する値として、前記一状態における領域分割した計測点データ群を最小自乗近似して得た近似線からのばらつき、及び、類似する幾何的特徴を有する領域の連続性を加味した評価関数を用いて、前記２（Ｎ−１）の状態空間の中から前記評価関数を最大とする領域分割状態をマルコフ連鎖モンテカルロ法により求め、分割後の該領域内の計測点データから、勾配や表面粗さを評価することにより、前記移動ロボットの前方側の領域を走行可能領域及び走行不能領域に区分け処理する処理部を備えた移動ロボットの走行領域判別装置において、
前記処理部では、前記プロファイルデータを構成する（Ｎ）個の計測点データ間における前記移動ロボットの進行するｘ方向と直交するｙ方向の間隔が閾値を超える部位が存在する場合に、前記マルコフ連鎖モンテカルロ法による前記プロファイルデータの領域分割前、領域分割時及び領域分割後のいずれかの時点で、前記閾値を超える部位を境にした領域分割を行う
ことを特徴とする移動ロボットの走行領域判別装置。
【請求項２】
自律して走行する移動ロボットの前方側の領域を走行可能領域及び走行不能領域に区分けする走行領域判別方法であって、
前記移動ロボットに搭載したレーザレンジファインダからレーザ光を走査して該移動ロボットの前方側のプロファイルデータを取得した後、
前記移動ロボットのレーザレンジファインダで得たプロファイルデータを構成する（Ｎ）個の計測点データ間における（Ｎ−１）個の境界点位置に、互いに隣接する計測点データ同士が同一領域にあるか否かに応じた２状態の状態変数を定義することで、前記プロファイルデータの任意の領域分割状態を２（Ｎ−１）の状態空間のうちの一状態として表現し、
互いに異なる幾何的特徴を有する領域を評価する値として、前記一状態における領域分割した計測点データ群を最小自乗近似して得た近似線からのばらつき、及び、類似する幾何的特徴を有する領域の連続性を加味した評価関数を用いて、
前記２（Ｎ−１）の状態空間の中から前記評価関数を最大とする領域分割状態をマルコフ連鎖モンテカルロ法により求め、分割後の該領域内の計測点データから、勾配や表面粗さを評価することにより、前記移動ロボットの前方側の領域を走行可能領域及び走行不能領域に区分けするに際して、
前記プロファイルデータを構成する（Ｎ）個の計測点データ間における前記移動ロボットの進行するｘ方向と直交するｙ方向の間隔が閾値を超える部位が存在する場合に、前記マルコフ連鎖モンテカルロ法による前記プロファイルデータの領域分割前、領域分割時及び領域分割後のいずれかの時点で、前記閾値を超える部位を境にして領域を分割する
ことを特徴とする移動ロボットの走行領域判別方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、自律して走行する移動ロボットの走行経路を決める段階において、移動ロボットの前方側の領域を走行可能領域及び障害などによる走行不能領域に区分けするのに用いられる走行領域判別装置及び走行領域判別方法に関するものである。
【背景技術】
【０００２】
従来、上記したような移動ロボットの走行領域判別方法としては、例えば、特許文献１に開示された手法がある。
この移動ロボットの走行領域判別方法では、移動ロボットに搭載した1軸スキャンタイプのレーザレンジファインダを用いて移動ロボットの前方側のプロファイルデータを取得し、このプロファイルデータにおける幾何的特徴などから領域の分割を行ったうえで、分割後の領域内の計測点データから勾配や表面粗さを評価して、これらの分割した領域を走行可能領域及び走行不能領域に区分けするようにしている。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開2009-229394号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
ところが、上記した従来の走行領域判別方法では、移動ロボットの前方領域を分割するに際して、レーザレンジファインダで取得したプロファイルデータに基づいて行っているが、この分割に用いるプロファイルデータを構成する計測点データが、連続的に取得されることを前提としている。
【０００５】
つまり、レーザレンジファインダによる計測時において、移動ロボットの前方に水溜りなどのレーザ光を反射しない要因によって、計測データを取得できないデータの抜けが生じた場合には、実際に取得した計測データだけを用いて領域の分割を行うことになる。
【０００６】
したがって、上記データの抜けの幅がかなり大きい場合であったとしても、データの抜けの両側の計測データが同一の領域に存在するものとして処理してしまうことがあり、走行可能領域と判定したとしても、この領域に移動ロボットの円滑な走行に支障を来たす未計測部分を含んでしまう場合がある、すなわち、領域を正しく評価することができない場合があるという問題を有しており、この問題を解決することが従来の課題となっていた。
【０００７】
本発明は、上述した従来の課題に着目してなされたもので、整地環境や舗装道路は勿論のこと、不整地環境や未舗装道路で移動ロボットを自律走行させる場合において、レーザレンジファインダにより取得した任意の位置及び任意の方向からのデータに基づいて、走行可能領域であるか否かの判別を安定して行うことが可能であり、加えて、計測データの抜けが生じたとしても、走行領域を正確に評価することができ、その結果、移動ロボットにスムーズな走行を行わせることが可能になる走行領域判別装置及び走行領域判別方法を提供することを目的としている。
【課題を解決するための手段】
【０００８】
ここで、ラインスキャンタイプの1軸レーザレンジファインダは、１回のスキャンで計測対象のプロファイルデータを取得可能であり、この際、スキャンレートが１００Ｈｚ程度なので、この1軸レーザレンジファインダが激しく揺動したとしても、得られるプロファイルデータは揺動の影響を受け難い。
【０００９】
このようなラインスキャンタイプの1軸レーザレンジファインダによる水平方向のスキャンラインＳＬを図９に模式的に示し、不整地環境や未舗装路で取得される路面のプロファイルデータＰＤを図１０に模式的に示す。なお、図９，図１０及び以下に示す図１１〜図１４中、ｚ方向は鉛直方向（上向き）であり、ｙ方向は移動ロボットの進行するｘ方向と直交する方向である。
【００１０】
図１０に示すように、不整地環境や未舗装路で取得される路面のプロファイルデータＰＤは、（Ｎ）個の計測点データＰ（Ｐ＝ｐ１，ｐ２，…，ｐＮ）から構成されており、この場合、中央部分が走行可能領域、その左右の部分が走行不能領域を模擬している。
【００１１】
図１１に示すように、上記プロファイルデータＰＤを走行可能領域Ｂ及び走行不能領域Ａ，Ｃに正しく分割することができれば、それぞれの領域Ａ〜Ｃ内のデータに基づいて、低次の最小自乗近似等の簡便な手法により、勾配や表面粗さを正しく評価することができる。
【００１２】
しかし、図１２に示すように、上記プロファイルデータＰＤの分割箇所を間違えると、領域Ａ〜Ｃ内のデータをサンプルデータとした場合には、勾配や表面粗さを正しく評価することができないため、その結果、走行可能領域及び走行不能領域を正しく評価することができない。
【００１３】
そこで、図１３に示すように、上記プロファイルデータＰＤを構成する（Ｎ）個の計測点データＰ（Ｐ＝ｐ１，ｐ２，…，ｐＮ）間における（Ｎ−１）個の境界点位置に、新たに状態変数Ｂ（Ｂ＝ｂ１，ｂ２，…，ｂｉ，…，ｂ（Ｎ−１））を定義し、この際、境界点ｂｉがとり得る値を（１）又は（−１）の２状態として、互いに隣接する計測点データＰ同士が同一領域であるか否かに応じて、図１４に示すように、該境界点ｂｉを（１）又は（−１）で表すことで、プロファイルデータの任意の領域分割状態を、２（Ｎ−１）の状態空間のうちの一状態として表現すことができる。
【００１４】
この際、上記領域分割を行う指針として、以下のような評価関数を用いることとする。
すなわち、走行可能領域及び走行不能領域は、互いに異なる表面粗さを有すると推測できるので、各々の表面粗さを評価する値として、上記一状態における領域分割した計測点データ群を最小自乗近似し、これで得た近似線からのばらつきを加味した評価関数を用いることとした。この際、各領域はできるだけ連続性を持つことが望ましいので、類似する幾何的特徴を有する領域の連続性も評価関数に加味することとした。
【００１５】
これにより、如何にして正しい領域分割を行うかという上記した問題は、２（Ｎ−１）の状態空間の中から上記評価関数を最大化させる分割状態を見つけ出す、という最適化問題に帰着することとなる。
上記した問題は、２（Ｎ−１）の状態空間のうちの一状態が２値の離散値であって微分が定義できないことから、ニュートン法などの適用が困難であるうえ、計測点データＰの数が数百個程度になるので、すべての状態を探索すると計算コストが膨大になる。
【００１６】
したがって、本発明において、マルコフ連鎖モンテカルロ法（ＭＣＭＣ）を用いて最適解を求めることとした。このマルコフ連鎖モンテカルロ法は、ランダムサンプリングによる状態空間の探索時において、状態の確率分布に基づいて、よりもっともらしいと思われる状態の探索とサンプリングを行う手法である。なお、このマルコフ連鎖モンテカルロ法については、［伊庭幸人  他５名著  ２００５統計科学のフロンティア１２計算系統IIマルコフ連鎖モンテカルロ法とその周辺  岩波書店発行］にその詳細な説明が記載されている。
【００１７】
具体的に説明すれば、逐次的に異なる領域分割を試行して、評価関数が最大となる領域分割状態を探索することとなる。
上記試行におけるモンテカルロステップ動作の理解のため、ダミーデータを用いた領域分割結果を図１５（ａ）〜（ｄ）に示し、図１６（ａ）〜（ｇ）には、モンテカルロステップの回数（０，１００，１０００，２０００，３０００，４０００，５０００）毎のスナップショットを示す。
【００１８】
図１５（ａ）〜（ｄ）に示す各例において、いずれも左側がモンテカルロステップを開始する初期状態であり、右側がモンテカルロステップの終了状態である。また、各図中、点は計測点データであり、互いに隣接する計測点データ同士が同じ領域であれば隣と同じ色（白又は黒）で表示し、一方、互いに隣接する計測点データ同士が同じ領域でなければ隣と異なる色で表示していて、色自体は意味をもっていない。
【００１９】
このように、マルコフ連鎖モンテカルロ法を用いることで、上記した２（Ｎ−１）の状態空間の中から評価関数を最大化させる分割状態を見つけ出すことが可能となる。さらに、分割された領域内のデータに対し、低次の最小自乗近似を適用することにより、勾配や表面粗さを正しく評価することができ、走行可能領域であるか否かの判別を安定して行うことが可能となる。
【００２０】
ここで、レーザレンジファインダによる計測時において、図１７に示すように、水溜りなどのレーザ光を反射しない要因により、計測データを取得することができない未計測領域が移動ロボットの前方に生じた場合には、実際に取得した計測データだけを用いて領域の分割を行うことになる。
【００２１】
つまり、未計測領域のｙ方向（移動ロボットの進行するｘ方向と直交する方向）の幅がかなり大きい場合において、図１８に示すように、未計測領域の両側の計測領域における計測データを同一の領域に存在するものとして処理して、全体が上記ｙ方向に緩やかに傾斜する領域としてしまうことがある、すなわち、領域を正しく評価することができない場合がある。
【００２２】
そこで、このような場合には、閾値を設定して、隣接する計測点データ間における移動ロボットの進行するｘ方向と直交するｙ方向の間隔がこの閾値を超える部位を未計測領域として扱い、この未計測領域を境にした領域分割処理を行って、図１９に示すように、未計測領域の図示左側に位置する傾斜のほとんどない平坦な領域と、未計測領域の図示右側に位置する上記ｙ方向の傾斜のきつい急勾配な領域とに分ける、すなわち、領域を正しく評価する。
上記閾値は、移動ロボットの車体幅に基づいて決定され、その幅の半分程度とすることが望ましい。
【００２３】
したがって、自律して走行する移動ロボットの前方側の領域を走行可能領域及び走行不能領域に区分けする本発明に係る走行領域判別装置では、レーザ光を走査して前記移動ロボットの前方側のプロファイルデータを取得するレーザレンジファインダを具備した外界計測部と、この外界計測部のレーザレンジファインダで得たプロファイルデータを構成する（Ｎ）個の計測点データ間における（Ｎ−１）個の境界点位置に、互いに隣接する計測点データ同士が同一領域であるか否かに応じた２状態の状態変数を定義することで、前記プロファイルデータの任意の領域分割状態を２（Ｎ−１）の状態空間のうちの一状態として表現し、互いに異なる幾何的特徴を有する領域を評価する値として、前記一状態における領域分割した計測点データ群を最小自乗近似して得た近似線からのばらつき、及び、類似する幾何的特徴を有する領域の連続性を加味した評価関数を用いて、前記２（Ｎ−１）の状態空間の中から前記評価関数を最大とする領域分割状態をマルコフ連鎖モンテカルロ法により求め、分割後の該領域内の計測点データから、勾配や表面粗さを評価することにより、前記移動ロボットの前方側の領域を走行可能領域及び走行不能領域に区分け処理する処理部を備えた移動ロボットの走行領域判別装置において、前記処理部では、前記プロファイルデータを構成する（Ｎ）個の計測点データ間における前記移動ロボットの進行するｘ方向と直交するｙ方向の間隔が閾値を超える部位が存在する場合に、前記マルコフ連鎖モンテカルロ法による前記プロファイルデータの領域分割前、領域分割時及び領域分割後のいずれかの時点で、前記閾値を超える部位を境にした領域分割を行う構成としており、この走行領域判別装置の構成を課題を解決するための手段としている。
【００２４】
一方、自律して走行する移動ロボットの前方側の領域を走行可能領域及び走行不能領域に区分けする本発明に係る走行領域判別方法にあっては、前記移動ロボットに搭載したレーザレンジファインダからレーザ光を走査して該移動ロボットの前方側のプロファイルデータを取得した後、前記移動ロボットのレーザレンジファインダで得たプロファイルデータを構成する（Ｎ）個の計測点データ間における（Ｎ−１）個の境界点位置に、互いに隣接する計測点データ同士が同一領域にあるか否かに応じた２状態の状態変数を定義することで、前記プロファイルデータの任意の領域分割状態を２（Ｎ−１）の状態空間のうちの一状態として表現し、互いに異なる幾何的特徴を有する領域を評価する値として、前記一状態における領域分割した計測点データ群を最小自乗近似して得た近似線からのばらつき、及び、類似する幾何的特徴を有する領域の連続性を加味した評価関数を用いて、前記２（Ｎ−１）の状態空間の中から前記評価関数を最大とする領域分割状態をマルコフ連鎖モンテカルロ法により求め、分割後の該領域内の計測点データから、勾配や表面粗さを評価することにより、前記移動ロボットの前方側の領域を走行可能領域及び走行不能領域に区分けするに際して、前記プロファイルデータを構成する（Ｎ）個の計測点データ間における前記移動ロボットの進行するｘ方向と直交するｙ方向の間隔が閾値を超える部位が存在する場合に、前記マルコフ連鎖モンテカルロ法による前記プロファイルデータの領域分割前、領域分割時及び領域分割後のいずれかの時点で、前記閾値を超える部位を境にして領域を分割する構成としており、この走行領域判別方法の構成を課題を解決するための手段としている。
【００２５】
本発明において、上記評価関数をエネルギに見立て、評価が高い場合をエネルギが低いとし、一方、評価が低い場合をエネルギが高いとした。
また、状態の確率分布には、統計物理のアナロジより、評価関数をエネルギに見立てたボルツマン分布を適用し、遷移確率の決定には、状態の確率分布をもとにメトロポリス法を適用した。
さらに、本発明において、効率的な最適化を行うために、シミュレーテッドアニーリングを適用した。
【００２６】
そして、上記のようにして正しい領域分割を行った後、それぞれの領域に含まれる計測点群に対して、図１１に示すように、幾何的特徴である勾配や表面粗さ等の物理量（幾何的特徴量）を推定すれば、走行可能領域及び走行不能領域が決定され、この結果を自律走行の経路計画地図の生成に供し得ることとなる。
【００２７】
加えて、レーザレンジファインダによる計測時において、図１７に示すように、隣接する計測点データ間のｙ方向（移動ロボットＲの進行するｘ方向と直交する方向）の間隔が、あらかじめ設定した閾値を超える部位（未計測領域）が移動ロボットの前方に生じた場合には、図１９に示すように、この閾値を超える部位を境にした領域分割を行えば、未計測領域の図示左側に位置する傾斜のほとんどない平坦な領域と、未計測領域の図示右側に位置する上記ｙ方向の傾斜のきつい急勾配な領域とに分けられることとなり、すなわち、領域を正しく評価し得ることとなり、この評価結果も自律走行の経路計画地図の生成に供すれば、より一層有益な自律走行の経路計画地図を作成し得ることとなる。
【００２８】
なお、外界計測部としては、移動ロボットの前方側のプロファイルデータを取得する水平ラインスキャンタイプの１軸レーザレンジファインダが少なくとも一組あれば事足りるが、断面的な勾配データしか得ることができないデメリットを補うべく、垂直ラインスキャンタイプなどの水平とは異なる方向のラインスキャンタイプの１軸レーザレンジファインダを少なくとも一組使用することが望ましい。
【００２９】
また、移動ロボットの自己位置を求めて上記外界計測部による計測地点を明確化する自己位置計測手段として、例えば、デッドレコニングやＧＰＳ（グローバル・ポジショニング・システム）を用いることができる。
【発明の効果】
【００３０】
本発明に係る移動ロボットの走行領域判別装置及び移動ロボットの走行領域判別方法では、それぞれ上記した構成としたから、整地環境や舗装道路のみならず、不整地環境や未舗装道路で移動ロボットを自律走行させる場合において、レーザレンジファインダにより取得した任意の位置及び任意の方向からのデータに基づいて、走行可能領域及び走行不能領域の判別を安定して行うことが可能であり、加えて、走行可能領域及び走行不能領域のそれぞれの領域における勾配や凹凸の度合いなどの物理量を精度良く得られるため、移動ロボットの走破性能に合わせた効率のよい経路計画が可能になり、さらに、計測データの抜けが生じたとしても、走行領域を正確に評価することができ、その結果、移動ロボットにスムーズな走行を行わせることが可能になるという非常に優れた効果がもたらされる。
【図面の簡単な説明】
【００３１】
【図１】本発明に係る移動ロボットの走行領域判別装置の一実施形態を示すブロック図である。
【図２】図１における走行領域判別装置を搭載した移動ロボットの側面説明図（ａ）及び外界計測部のレイアウト説明図（ｂ）である。
【図３】図２における外界計測部のレーザレンジファインダによるスキャン状況を示す平面説明図である。
【図４】図１における走行領域判別装置の制御フローを示すブロック図である。
【図５】図１に示した走行領域判別装置の処理部におけるマルコフ連鎖モンテカルロ法を用いた領域分割アルゴリズムを示すフローチャートである。
【図６】図１における走行領域判別装置のデータ入力から地図生成までの流れを示すフローチャートである。
【図７】図１に示した走行領域判別装置による走行領域判別処理が予想される領域に水溜りなどの未計測領域が存在する一状況のイメージ図である。
【図８】図２の外界計測部とは異なる構成例の外界計測部におけるレーザレンジファインダによるスキャン状況を示す平面説明図である。
【図９】レーザレンジファインダによる水平方向のスキャンラインを示す模式図である。
【図１０】不整地環境や未舗装路で取得される路面のプロファイルデータを示す模式図である。
【図１１】図１０のプロファイルデータを走行可能領域及び走行不能領域に正しく分割した状態を示す模式図である。
【図１２】図１０のプロファイルデータを走行可能領域及び走行不能領域に正しく分割できなかった状態を示す模式図である。
【図１３】プロファイルデータを構成する複数個の計測点データ間における境界点を新たな状態変数とした状態を示す模式図である。
【図１４】プロファイルデータの任意の領域分割状態を状態空間のうちの一状態として示す模式図である。
【図１５】モンテカルロステップ動作の理解のためにダミーデータを用いた際の領域分割結果を示す説明図（ａ）〜（ｄ）である。
【図１６】モンテカルロステップの回数毎のスナップショットを示す説明図（ａ）〜（ｇ）である。
【図１７】未計測部位を含む路面のプロファイルデータを示す模式図である。
【図１８】図１７のプロファイルデータにおいて未計測部位を走行可能領域として評価した場合の模式図である。
【図１９】図１７のプロファイルデータにおいて未計測部位を境にして領域分割した場合の模式図である。
【図２０】本発明の他の実施形態に係る走行領域判別装置のデータ入力から地図生成までの流れを示すフローチャートである。
【図２１】本発明のさらに他の実施形態に係る走行領域判別装置のデータ入力から地図生成までの流れを示すフローチャートである。
【発明を実施するための形態】
【００３２】
以下、本発明に係る移動ロボットの走行領域判別装置及び走行領域判別方法を図面に基づいて説明する。
図１〜図７は、本発明に係る移動ロボットの走行領域判別装置の一実施形態を示しており、この実施形態では、移動ロボットが車両タイプである場合を例に挙げて説明する。
【００３３】
図１〜図２に示すように、この走行領域判別装置１は、レーザ光を走査して移動ロボットＲの前方側のプロファイルデータを取得する水平ラインスキャンタイプの1軸レーザレンジファインダ１１，垂直ラインスキャンタイプの1軸レーザレンジファインダ１２及びこれらのレーザレンジファインダ１１，１２で得たセンサ座標系データを鉛直上向きを１軸とする直交座標系データへ変換するデータを供するバーチカルジャイロ１３を具備した外界計測部１０と、デッドレコニング用のホイルオドメータ２１，ヨーレートセンサ２２及びＧＰＳ２３を具備して、移動ロボットＲの自己位置を求める自己位置計測部２０と、外界計測部１０で得た外界データ及び自己位置計測部２０で得た自己位置データが入出力回路２を介して入力される処理部３０と、この処理部３０とＬＡＮ３を介して接続する地図作成部４０を備えており、外界計測部１０の1軸レーザレンジファインダ１１では、図３に模式的に示すように、水平スキャンラインＳＬに沿う水平方向のプロファイルデータを取得し、一方、1軸レーザレンジファインダ１２では、垂直スキャン位置ＶＬにおける上下方向のプロファイルデータを取得するものとなっている。
【００３４】
この場合、外界計測部１０は移動ロボットＲの前端部（図２（ａ）左端部）に搭載され、一方、自己位置計測部２０は処理部３０，地図作成部４０及び後述する車体制御部６０とともに移動ロボットＲの後端部（図２（ａ）右端部）に搭載されており、この移動ロボットＲの後端部にはＧＰＳ２３用のアンテナ２４が配置してある。
【００３５】
そして、移動ロボットＲにおける車体駆動部５０の操舵手段５１は、ドライバ５２及び入出力回路４を介して車体制御部６０と接続していると共に、車体駆動部５０の車速制御手段５３は、コンバータ５４及び入出力回路４を介して車体制御部６０と接続しており、この車体制御部６０には、地図作成部４０からの制御信号がＬＡＮ３を介して入力されるようになっている。
【００３６】
上記処理部３０は、図４にも示すように、移動ロボットＲの前方側の領域を走行可能領域及び走行不能領域に区分け処理する走行可否領域分割処理モジュール３０Ａを有していると共に、自己位置計測部２０で得た車速やヨーレート等による自己位置データに基づいて自己位置推定結果を生成する自己位置情報生成モジュール３０Ｂを有している。
【００３７】
この処理部３０では、外界計測部１０のレーザレンジファインダ１１，１２で得たプロファイルデータを構成する（Ｎ）個の計測点データ間における（Ｎ−１）個の境界点位置に、互いに隣接する計測点データ同士が同じ領域に属するか否かに応じた２状態の状態変数を定義して（１）又は（−１）で表すことで、プロファイルデータの任意の領域分割状態を２（Ｎ−１）の状態空間のうちの一状態として表現する処理と、この一状態における領域分割した計測点データ群を最小自乗近似して得た近似線からのばらつき、及び、類似する幾何的特徴を有する領域の連続性を加味した評価関数を用いて、この評価関数を最大とする領域分割状態を上記２（Ｎ−１）の状態空間の中からマルコフ連鎖モンテカルロ法により求める処理とを行って、分割後の該領域内の計測点データから、勾配や表面粗さなどの幾何的特徴量を評価することで、移動ロボットＲの前方側の領域を走行可能領域及び走行不能領域に区分けするようにしている。
【００３８】
加えて、この処理部３０では、走行可能領域において、隣接する計測点データ間のｙ方向（移動ロボットＲの進行するｘ方向と直交する方向）の間隔が、あらかじめ設定した閾値を超える水溜りなどのレーザ光を反射しない部位（未計測領域）が生じた場合には、この未計測領域を境にした領域分割処理を行うことにより、領域を正しく評価するようにしている。
【００３９】
ここで、上記マルコフ連鎖モンテカルロ法を用いた領域分割アルゴリズムを具体的に説明すると、図５に示すように、ステップＳ１でモンテカルロステップｔ＝０の初期状態にある状態変数Ｂ（０）（Ｂ＝ｂ１，ｂ２，…，ｂｉ，…，ｂ（Ｎ−１））に対して、ステップＳ２において、初期エネルギＥ（０）を計算してこの初期状態の評価を行う。
【００４０】
次いで、ステップＳ３において、状態Ｂのインデックスｉをランダムに決めてｂｉの値を（１）→（−１）或いは（−１）→（１）に変更して状態Ｂ´を生成し、ステップＳ４において、状態Ｂ´に基づいてエネルギＥ（Ｂ´）を計算してこの状態の評価を行う。
【００４１】
次に、ステップＳ５において、変更前のエネルギＥ（Ｂ（ｔ））及び変更後のエネルギＥ´に基づいて、確率Ｐ（Ｂ（ｔ）β）及びＰ（Ｂ´β）を計算するのに続いて、ステップＳ６において、遷移確率を決定するために、メトロポリス法に用いる一様乱数０≦ｒ＜１を生成する。
【００４２】
この後、ステップＳ７において、上記で求めた確率Ｐ（Ｂ（ｔ）β）及びＰ（Ｂ´β）の比であるＰ（Ｂ（ｔ）β）／Ｐ（Ｂ´β）と一様乱数ｒとを比較して、一様乱数ｒがＰ（Ｂ（ｔ）β）／Ｐ（Ｂ´β）よりも小さければ、ステップＳ８において、変更した状態Ｂ´を次の状態とし、一方、一様乱数ｒがＰ（Ｂ（ｔ）β）／Ｐ（Ｂ´β）よりも大きければ、ステップＳ９において、変更前の状態Ｂ（ｔ）を次の状態として、ステップＳ１０において、モンテカルロステップｔが所定回数（５０００回程度）に達するまで上記ステップＳ３以降の操作を繰り返すと、移動ロボットＲの前方側の領域が類似した幾何的特徴を有する連続領域に区分けされることとなる。
【００４３】
この区分けの後、領域内の計測点データから、勾配や表面粗さを評価することにより、走行可能領域及び走行不能領域に区分けすることができる。
【００４４】
この実施形態では、上記ステップＳ３以降の操作を繰り返す過程のステップＳ１１において、シミュレーテッドアニーリングを適用しており、モンテカルロステップｔを増す毎に、パラメータβをあらかじめ決定しておいたΔβ分ずつ増加させている。これにより、状態がローカルミニマムに陥るのを防ぎつつモンテカルロステップｔを実行して、全体最適解を効率よく求め得るようにしている。
【００４５】
また、上記地図作成部４０は、処理部３０から得た走行可能領域及び走行不能領域の判別情報や、境界部分の走行の可否判定情報に基づいてベース地図を作成する地図作成モジュール４０Ａを有していると共に、この地図作成モジュール４０Ａで作成されたベース地図に基づいて移動ロボットＲの走行経路を決める走行経路決定モジュール４０Ｂを有している。
【００４６】
次に、上記した移動ロボットＲの走行経路決定用地図の作成要領を説明する。
まず、図６に示すように、ステップＳ２１において、走行領域判別装置１の処理部３０に対して、外界計測部１０からのプロファイルデータ及び自己位置計測部２０からの車速やヨーレート等による自己位置データが入力され、ステップＳ２２において、バーチカルジャイロ１３によりレーザレンジファインダ１１，１２で得たセンサ座標系データが鉛直上向きを１軸とする直交座標系データへ変換される。
【００４７】
続いて、ステップＳ２３において、処理部３０の走行可否領域分割処理モジュール３０Ａにおける上記マルコフ連鎖モンテカルロ法（ＭＣＭＣ）を用いた走行可能領域及び走行不能領域の分割処理が成される。
【００４８】
この後、ステップＳ２４において、上記マルコフ連鎖モンテカルロ法により分割処理された同一の走行可能領域内のプロファイルデータに対して、計測点間のｙ方向（移動ロボットＲの進行するｘ方向と直交する方向）の間隔を用いた領域分割処理が成される。すなわち、図７に示すように、走行可能と判定された走行可能領域Ｇ内に、隣接する計測点データ間の上記ｙ方向の間隔があらかじめ設定した閾値を超える未計測領域ＮＧ（例えば、かなり幅の広い水溜り）が存在する場合に、この閾値を超える未計測領域ＮＧを境にした領域分割が成されて、未計測領域ＮＧの図示左側に位置する走行可能領域Ｇ１と、未計測領域ＮＧの図示右側に位置する走行可能領域Ｇ２とに分けられる。
【００４９】
次いで、ステップＳ２５において、分割された走行可能領域Ｇ１，Ｇ２の各々のプロファイルデータに対して、幾何的特徴である勾配及び表面粗さなどの物理量（幾何的特徴量）の計算が成され、続いて、ステップＳ２６において、処理部３０の走行可否領域分割処理モジュール３０Ａから得た走行可能領域及び走行不能領域の判別情報や境界部分Ｎでの走行の可否判定情報と、自己位置情報生成モジュール３０Ｂから得たデッドレコ情報などの自己位置情報とに基づいて、地図作成部４０の地図作成モジュール４０Ａによって整合性のあるベース地図が連続的に作成される。
【００５０】
上記したように、この実施形態に係る移動ロボットの走行領域判別装置１によれば、マルコフ連鎖モンテカルロ法（ＭＣＭＣ）を用いて走行可能領域及び走行不能領域の分割を行った後、それぞれの領域に含まれる計測点群に対して、幾何的特徴である勾配や表面粗さ等の幾何的特徴量を評価することで、走行可能領域及び走行不能領域を決定することができるので、この結果を自律走行の経路計画地図の生成に供すれば、有益な自律走行の経路計画地図を作成し得ることとなる。
【００５１】
加えて、上記のようにして分割された走行可能領域において、隣接する計測点データ間における移動ロボットＲの進行するｘ方向と直交するｙ方向の間隔があらかじめ設定した閾値を超える未計測領域ＮＧがあったとしても、この閾値を超える部位を境にした領域分割を行えば、領域を正しく評価し得ることとなり、この評価結果も自律走行の経路計画地図の生成に供すれば、より一層有益な自律走行の経路計画地図を作成し得ることとなる。
【００５２】
また、この実施形態に係る移動ロボットの走行領域判別装置１では、マルコフ連鎖モンテカルロ法により分割処理された同一の走行可能領域内のプロファイルデータに対して、計測点間における移動ロボットＲの進行するｘ方向と直交するｙ方向の間隔を用いた領域分割処理を行うので、処理時間の短縮化も図られることとなる。
【００５３】
図２０は、上記した走行領域判別装置１による移動ロボットＲの走行経路決定用地図の他の作成要領を示している。
この実施形態に係る走行経路決定用地図の作成要領が先の実施形態における走行経路決定用地図の作成要領と相違するところは、ステップＳ３３において、ステップＳ２１，Ｓ２２で得られたプロファイルデータに、計測点間の移動ロボットＲの進行するｘ方向と直交するｙ方向の間隔を用いた領域分割処理を施した後、ステップＳ３４において、分割された領域の各プロファイルデータに対して、上記マルコフ連鎖モンテカルロ法を用いた走行可能領域及び走行不能領域の分割処理が成されるようにした点にあり、このステップＳ３４以降のステップＳ２５，Ｓ２６の処理は先の実施例と同じである。
【００５４】
上記したように、この実施形態に係る移動ロボットの走行領域判別装置１によっても、隣接する計測点データ間の移動ロボットＲの進行するｘ方向と直交するｙ方向の間隔があらかじめ設定した閾値を超える未計測領域ＮＧが存在する場合には、マルコフ連鎖モンテカルロ法を用いた領域分割の前に、この閾値を超える部位を境にした領域分割を行えば、領域を正しく評価し得ることとなり、この評価結果も自律走行の経路計画地図の生成に供すれば、より一層有益な自律走行の経路計画地図を作成し得ることとなる。
【００５５】
図２１は、上記した走行領域判別装置１による移動ロボットＲの走行経路決定用地図のさらに他の作成要領を示している。
この実施形態に係る走行経路決定用地図の作成要領が先の実施形態における走行経路決定用地図の作成要領と相違するところは、ステップＳ４３において、ステップＳ２１，Ｓ２２で得られたプロファイルデータに上記マルコフ連鎖モンテカルロ法を用いた領域分割を行う際にも、エネルギに見立てた評価関数の一つ（エネルギ要素の一つ）として、計測点間の移動ロボットＲの進行するｘ方向と直交するｙ方向の間隔を用いるようにした点にあり、このステップＳ４３以降のステップＳ２５，Ｓ２６の処理は先の実施例と同じである。
【００５６】
上記したように、この実施形態に係る移動ロボットの走行領域判別装置１によっても、隣接する計測点データ間の移動ロボットＲの進行するｘ方向と直交するｙ方向の間隔があらかじめ設定した閾値を超える未計測領域ＮＧが存在する場合には、マルコフ連鎖モンテカルロ法を用いた領域分割時に、エネルギ要素の一つとして計測点データ間のｙ方向の間隔を加えて領域分割を行えば、領域をより一層正しく評価し得ることとなり、この評価結果も自律走行の経路計画地図の生成に供すれば、極めて有益な自律走行の経路計画地図を作成し得ることとなる。
【００５７】
また、上記した走行領域判別装置１では、外界計測部１０が、１軸レーザレンジファインダ１１，１２及びバーチカルジャイロ１３を具備している場合を示したが、外界計測部１０の1軸レーザレンジファインダ１１以外の構成や配置はこれに限定されるものではない。
【００５８】
他の構成として、例えば、垂直ラインスキャンタイプの1軸レーザレンジファインダ１２に代えて水平ラインスキャンタイプの1軸レーザレンジファインダ１１をもう一組配置して、図８に模式的に示すように、両1軸レーザレンジファインダ１１の各水平スキャンラインＳＬ同士が互いに交差するようにしてもよい。
【００５９】
さらに、上記した一実施形態では、移動ロボットが車両タイプである場合を示したが、これに限定されるものではない。
【符号の説明】
【００６０】
１  移動ロボットの走行領域判別装置
１０  外界計測部
１１  １軸レーザレンジファインダ
３０  処理部
Ｇ１，Ｇ２  走行可能領域
Ｎ  隣接する走行可能領域間の境界部分
Ｈ  境界部分の段差
Ｒ  移動ロボット
【図１】
0005414618.tif 000002
【図２】
0005414618.tif 000003
【図３】
0005414618.tif 000004
【図４】
0005414618.tif 000005
【図５】
0005414618.tif 000006
【図６】
0005414618.tif 000007
【図７】
0005414618.tif 000008
【図８】
0005414618.tif 000009
【図９】
0005414618.tif 000010
【図１０】
0005414618.tif 000011
【図１１】
0005414618.tif 000012
【図１２】
0005414618.tif 000013
【図１３】
0005414618.tif 000014
【図１４】
0005414618.tif 000015
【図１７】
0005414618.tif 000016
【図１８】
0005414618.tif 000017
【図１９】
0005414618.tif 000018
【図２０】
0005414618.tif 000019
【図２１】
0005414618.tif 000020
【図１５】
0005414618.tif 000021
【図１６】
0005414618.tif 000022