(57)【要約】【課題】自律移動装置が屋外を自律移動するときに生成する環境地図のデータ量を削減する。【解決手段】自律移動ロボットは、移動環境を計測して所定の高さ以上の障害物の存在位置を示す環境地図を生成する地図生成部１１１と、地図生成部１１１により生成された環境地図から移動可能な経路を生成する経路生成部１１２と、経路生成部１１２により生成された経路から目的地までの自律移動経路を生成する経路計画部１１３と、経路計画部１１３により生成された自律移動経路を移動するように制御する駆動制御部１１４とを有する。【選択図】図２
2016149090.tif 000002
【特許請求の範囲】
【請求項１】
移動環境を計測して３次元位置データを生成する３次元計測センサと、
前記３次元計測センサで生成された３次元位置データから、所定の閾値以上の高さを有する障害物の位置を示す環境地図を生成する地図生成手段と、
前記地図生成手段により生成された環境地図から通行可能な移動経路を生成する経路生成手段と、
前記経路生成手段により生成された移動経路から目的地までの自律移動経路を生成する経路計画手段と、
前記経路計画手段により生成された自律移動経路を自装置が移動するように制御する移動制御手段と、
を有する自律移動装置。
【請求項２】
請求項１に記載された自律移動装置において、
前記地図生成手段は、前記３次元計測センサで生成された３次元位置データのうち、所定の閾値未満の高さを持つ３次元位置データを削除する手段と、前記３次元位置データを、その高さデータを保持したまま２次元地図へ写像する手段と、を有する、自律移動装置。
【請求項３】
請求項１または２に記載された自律移動装置において、
前記経路生成手段は、前記障害物の高さに応じて経由地点を設定する経由地点設定手段を有する、自律移動装置。
【請求項４】
請求項３に記載された自律移動装置において、
前記経路生成手段は、前記障害物の高さ、および複数の前記障害物の間の距離から、前記経由地点の安全度をラベリングする手段を有する、自律移動装置。
【請求項５】
請求項１乃至４のいずれかに記載された自律移動装置において、
前記経路生成手段は、経由地点を線で結ぶネットワーク化手段を有する、自律移動装置。
【請求項６】
請求項４または５に記載された自律移動装置において、
前記経路計画手段は、前記経由地点の安全度を考慮して、スタート地点からゴール地点までの自律移動経路を生成する、自律移動装置。
【請求項７】
自律移動装置の移動環境を計測して３次元位置データを生成する３次元計測センサと、
前記３次元計測センサで生成された３次元位置データから、所定の閾値以上の高さを有する障害物の位置を示す環境地図を生成する地図生成手段と、
前記地図生成手段により生成された環境地図から通行可能な移動経路を生成する経路生成手段と、
前記経路生成手段により生成された移動経路から目的地までの自律移動経路を生成する経路計画手段と、
前記経路計画手段により生成された自律移動経路を前記自律移動装置が移動するように制御する移動制御手段と、
を有する自律移動システム。
【請求項８】
自律移動装置の移動環境を計測して所定の高さ以上の障害物の位置を示す環境地図を生成する地図生成工程と、
前記地図生成工程により生成された環境地図から通行可能な移動経路を生成する経路生成工程と、
前記経路生成工程により生成された移動経路から目的地までの自律移動経路を生成する経路計画工程と、
前記経路計画工程により生成された自律移動経路を前記自律移動装置が移動する自律移動工程と、
を有する自律移動方法。
【請求項９】
コンピュータを請求項１に記載された自律移動装置の各手段として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、自律移動装置、自律移動システム、自律移動方法、およびプログラムに関する。
【背景技術】
【０００２】
人の操作によらず自律的に移動する自律移動装置として自律移動ロボットがある。また、自律移動ロボットの移動方法として、レーザーやステレオカメラなどのセンサによって、外部の環境の特徴（ランドマーク）を把握しながら、ロボット自身が未知環境の地図生成と自己位置推定を行って、自律的に移動するＳＬＡＭ（Simultaneous Localization And Mapping）と呼ばれる方法がある。
【０００３】
ＳＬＡＭを用いる自律移動ロボットは、あらかじめレーザーやステレオカメラなどで移動環境（移動する環境）を計測して環境地図（障害物が存在する領域と存在しない領域とを表す地図）を生成し、その環境地図を記憶する。そして、その環境地図から通行可能領域（移動可能領域）を抽出して障害物を回避する移動経路を作成し、自己位置を推定しつつ自律移動する方法が一般的である。
【０００４】
ＳＬＡＭを用いる自律移動装置としては特許文献１に記載された自律移動装置がある。この自律移動装置は、ｘｙ平面をグリッド分割した環境地図を生成し、その環境地図から通行可能領域を抽出し、その通行可能領域に沿ってユーザから与えられたスタート位置とゴール位置との間をつなぐことにより移動経路を計画する。
【０００５】
また、この自律移動装置は、環境地図から通行可能領域を抽出する際、自装置の半径だけ障害物領域（障害物が存在する領域）の輪郭を拡張することで、拡張された障害物領域に対して自装置の大きさを点とみなせるようにしている。
【０００６】
さらに、この自律移動装置は、自装置の半径だけ拡張された障害物領域を自装置の半径の幅で段階的に拡張することで、移動経路上の通過地点の経路余裕をあらかじめ把握している。
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかしながら、特許文献１に記載された自律移動装置では、移動環境全体にわたって障害物領域を計測して詳細に記憶しているため、屋外を自律移動する場合、環境地図が大規模になり、地図のデータ量が膨大になるという問題がある。その結果、ロボットが自己位置を推定する際に非常に時間がかかることになる。
【０００８】
本発明は、このような問題を解決するためになされたものであり、その目的は、自律移動装置が屋外を自律移動するときに生成する環境地図のデータ量を削減することである。
【課題を解決するための手段】
【０００９】
本発明に係る自律移動装置は、移動環境を計測して３次元位置データを生成する３次元計測センサと、前記３次元計測センサで生成された３次元位置データから、所定の閾値以上の高さを有する障害物の位置を示す環境地図を生成する地図生成手段と、前記地図生成手段により生成された環境地図から通行可能な移動経路を生成する経路生成手段と、前記経路生成手段により生成された移動経路から目的地までの自律移動経路を生成する経路計画手段と、前記経路計画手段により生成された自律移動経路を自装置が移動するように制御する移動制御手段と、を有する自律移動装置である。
【発明の効果】
【００１０】
本発明によれば、自律移動装置が屋外を自律移動するときに生成する環境地図のデータ量を削減することができる。
【図面の簡単な説明】
【００１１】
【図１】本発明の実施形態に係る経路生成方法の全体の流れの概略を示す図である。
【図２】本発明の実施形態に係る自律移動装置としての自律移動ロボットのハードウェア構成の概略を示すブロック図である。
【図３】本発明の実施形態に係る自律移動装置により実行されるランドマーク選定処理の詳細を示すフローチャートである。
【図４】本発明の実施形態に係る自律移動装置により実行されるランドマーク選定処理について説明するための模式図である。
【図５】３次元格子地図と２．５Ｄ地図との関係を示す模式図である。
【図６】本発明の実施形態に係る自律移動装置の経路生成部により実行される経由地点設置処理の詳細を示すフローチャートである。
【図７】本発明の実施形態に係る自律移動装置の経路生成部により実行される経由地点設置処理および安全度ラベリング処理について説明するための模式図である。
【図８】本発明の実施形態に係る自律移動装置の経路生成部で生成されたネットワーク構造の経路データを示す図である。
【図９】経由地点の安全度を考慮した経路計画について説明するための図である。
【図１０】経路データにおける移動距離のみを考慮した経路計画について説明するための図である。
【図１１】経由地点の危険度を考慮した経路計画について説明するための図である。
【発明を実施するための形態】
【００１２】
以下、本発明の実施形態について詳細に説明する。
〈経路生成方法の全体の流れ〉
図１は、本発明の実施形態に係る経路生成方法の全体の流れの概略を示す図である。この方法は、後述する本発明の実施形態に係る自律移動装置としての自律移動ロボットにより実行される。各工程の詳細については後述する。
【００１３】
図示のように、この経路生成方法は、３次元点群データ計測工程１、地図生成工程２、経路生成工程３、および経路計画工程４を有する。そして、地図生成工程２は、ランドマーク選別工程２１、ノイズ除去工程２２、クラスタリング工程２３、および２．５Ｄ地図写像工程２４を有し、経路生成工程３は、経由地点設置工程３１、安全度ラベリング工程３２、および経路ネットワーク化工程３３を有する。
【００１４】
３次元点群データ計測工程１では、レーザーレンジファインダーやステレオカメラなど、ロボットから物体までの距離を３次元的に測距可能なセンサと、ＧＰＳ（Global Positioning System）などロボット自身の自己位置を計測可能なセンサとを用いて、移動環境をスキャンして、３次元位置データとしての３次元点群データを取得する。
【００１５】
ランドマーク選別工程２１では、３次元点群データ計測工程１で取得された３次元の点群データから、ある閾値以上の高さを持ったデータのみを記録し、それ以外（ある閾値未満の高さを持ったデータ）を削除する。
【００１６】
ノイズ除去工程２２では、ランドマーク選別工程２１で選別された３次元の点群データからのノイズを除去する。一般に、計測した点群データにはノイズ（外れ値）が多く含まれるので、公知のＲＡＮＳＡＣ（Random Sample Consensus）などのノイズ除去アルゴリズムでノイズを取り除く。
【００１７】
クラスタリング工程２３では、後の経由地点設置工程３１における通行可能領域の処理の前処理として、障害物を一つの塊としてグループ化（クラスタ化）する。
【００１８】
２．５Ｄ地図写像工程２４では、３次元点群データから２．５次元の地図への変換、すなわち高さ情報を保持したまま２次元地図へと写像を行う。この工程で環境地図の生成が終了する。
【００１９】
経由地点設置工程３１では、生成された環境地図における各々の障害物の高さに応じて、できるだけ障害物から離れるような地点を計算し、自律移動の経由地点としてそのｘ，ｙ座標を記憶する。
【００２０】
安全度ラベリング工程３２では、経由地点設置工程３１で設置された経由地点において、障害物と障害物の間のスペースがあまりにも狭いときは、その経由地点を通行不可能地点として削除する。また、障害物間の距離（移動経路の幅）と障害物の高さを考慮して、その経由地点における自己位置推定の安全度（もしくは危険度）なるものを各地点に対して数値でラベリングする。
【００２１】
経路ネットワーク化工程３３では、安全度ラベリング工程３２によるラベリングが終了した経由地点に対して、経由地点同士をドロネー三角領域分割によって直線で結び、通行可能な移動経路のネットワークを完成させる。
【００２２】
経路計画工程４では、経路生成工程３で完成した経路ネットワークを用いて、経由地点の安全度を考慮しながら目的地までの自律移動経路を計算する。
【００２３】
〈自律移動ロボットのハードウェア構成〉
図２は、本発明の実施形態に係る自律移動装置としての自律移動ロボット（以下、本実施形態に係る自律移動ロボット）のハードウェア構成の概略を示すブロック図である。
【００２４】
図示のように、本実施形態に係る自律移動ロボットは、演算装置１００と、それぞれが演算装置１００に接続された３次元計測センサ１０１、自己位置推定センサ１０２、ＨＤＤなどの記録媒体１０３、この自律移動ロボット（自装置）を駆動するモータなどの駆動部１０４、およびコントローラ１０５を有する。演算装置１００とコントローラ１０５との間の接続は無線（ワイヤレス）でもよい。
【００２５】
３次元計測センサ１０１は、レーザーレンジファインダーやステレオカメラなど、ロボットから物体までの距離を３次元的に測距可能なセンサである。自己位置推定センサ１０２は、ＧＰＳやＩＭＵ（Inertial Measurement Unit：慣性計測装置）など、ロボット自身の自己位置を計測可能なセンサである。
【００２６】
演算装置１００は、ＣＰＵ、ＲＯＭ、およびＲＡＭを有するマイクロコンピュータなどで構成されており、ＣＰＵがＲＯＭに格納されているプログラムをＲＡＭに読み込んで処理することにより実現される機能を表すブロックとして、地図生成部１１１、経路生成部１１２、経路計画部１１３、および駆動制御部１１４を備えている。
【００２７】
地図生成部１１１、経路生成部１１２、経路計画部１１３は、それぞれ図１における地図生成工程２、経路生成工程３、経路計画工程４を実行するブロックである。駆動制御部１１４は、駆動部１０４の動作を制御するブロックである。
【００２８】
〈自律移動ロボットの動作の概略〉
次に、本実施形態に係る自律移動ロボットの動作の概略について説明する。
本実施形態に係る自律移動ロボットの動作状態には、地図生成フェーズと自律移動フェーズという２つの動作状態がある。
【００２９】
地図生成フェーズは、図１に示した３次元点群計測工程１、地図生成工程２、および経路生成工程３を実行するフェーズであり、自律移動フェーズは図１に示した経路計画工程４を実行しながらロボットを移動させるフェーズである。これらのフェーズは、ユーザがコントローラ１０５により手動で切り換えることができる。
【００３０】
地図生成フェーズでは、ユーザがコントローラ１０５から遠隔で指令を送ることで移動環境内においてロボットを動かして回り、３次元計測センサ１０１によりロボットから周囲の物体までの距離を計測するとともに、自己位置推定センサ１０２を用いて、移動環境を移動しながらスキャンして、環境地図のデータを生成する。生成された環境地図のデータは記録媒体１０３に一時的に蓄えられる。
【００３１】
また、地図生成フェーズでは、生成された環境地図における各々の障害物の高さに応じて、できるだけ障害物から離れるような地点を計算し、自律移動の経由地点の位置および安全度を記録媒体１０３に蓄積する。
【００３２】
自律移動フェーズでは、地図生成フェーズで生成された地図データおよび移動環境全体の移動経路を記録媒体１０３から読み出して、ロボットの現在位置から目的地の自律移動経路を計画する。
【００３３】
その後、計画した自律移動経路に従い、現在位置から計画した自律移動経路の各経由地点を経由するように、駆動制御部１１４から駆動部１０４に動作の指令を送る。したがって、ロボットはユーザからのコントローラ指令なしに自律移動を行う。
【００３４】
経路計画および自律移動中には、ロボットは現在位置を推定する必要があるので、自律移動フェーズにおいても自己位置推定センサ１０２を使用する。しかしながら、一度生成した環境地図および自律移動経路自体は更新しないので、３次元計測センサ１０１は自律移動フェーズでは使用せず、地図生成部１１１および経路生成部１１２は動作しない。
【００３５】
〈ランドマーク選定処理〉
図３は、本実施形態に係る自律移動ロボットにより実行されるランドマーク選定処理の詳細を示すフローチャートであり、図４は、本実施形態に係る自律移動ロボットにより実行されるランドマーク選定処理について説明するための模式図である。これらの図を用いて、ランドマーク選定処理について説明する。なお、このランドマーク選定処理は、図１における３次元点群データ計測工程１およびランドマーク選別工程２１に対応する。
【００３６】
まず、上記図２の説明でも述べたとおり、地図生成フェーズにおいて、ロボットはユーザがコントローラ１０５で遠隔操作しながら移動環境内を移動して回ると同時に、３次元スキャンを行う（図３のステップＳ１、図４Ａ）。スキャンしたデータは３次元座標の点群として保持される（ステップＳ２、図４Ｂ）。
【００３７】
それら点群の点ひとつひとつはｘ，ｙ，ｚの３次元座標で与えられるが、ｚ座標の値が高さに関するユーザ設定の閾値H_thresh未満であった場合、その点を保持せずに削除する（ステップＳ３：Yes→Ｓ４、図４Ｃ）。
【００３８】
これは、高さの低い障害物は、そもそも自己位置推定を失敗させる原因にはならないため、高さの高い障害物の位置だけを残すことにする。この処理をある時刻でスキャンした点群データ全ての点に対して行う（ステップＳ５：No→Ｓ３）。
【００３９】
次に、データ量削減およびマッチングの高速化のため、残った点群を３次元の格子座標で量子化する（ステップＳ６、図４Ｄ)。その後、全ての領域をスキャンしたか否かを判定し（ステップＳ７）、スキャンしていない場合は（ステップＳ７：No）、ＩＣＰ(Interactive Closest Points)マッチングのような公知の既存手法により、それまでに取得した点群とのマッチングを行って、段階的に地図を拡張する（ステップＳ８、図４Ｅ）。
【００４０】
そして、ロボットを少し前進させ（ステップＳ９）、ロボットの自己位置をマッピングした後（図３のステップＳ１０）、再びスキャンする（ステップＳ１）。この処理を繰り返し、全ての領域をスキャンしたら（ステップＳ７：Yes）、この図に示すフローを終了し、移動環境全体の環境地図を完成させる。
【００４１】
最終的に完成した環境地図は、後述する図５Ａに示すような格子状の地図となる。各グリッドで仕切られた範囲に存在する点群はまとめてひとつの格子として表される。ひとつの格子はそのｘ，ｙ座標と障害物の存在の有無、および障害物（点群）の最大高さh_maxを示したデータとなる。
【００４２】
〈２．５Ｄ地図の生成〉
図５は、３次元格子地図と２．５Ｄ地図との関係を示す模式図である。ここで、図５Ａは３次元格子地図を表し、図５Ｂは２．５Ｄ地図を表す。この図を用いて、ランドマーク選定後から２．５Ｄ地図生成までの処理の流れ、すなわち図１におけるノイズ除去工程２２、クラスタリング工程２３、および２．５Ｄ地図写像工程２４の内容について説明する。
【００４３】
ランドマーク選定後のデータは、図５Ａのようにある一定以上の高さをもった３次元格子状の地図で表され、木などの障害物が存在する空間は立方体で表される。
【００４４】
取得した３次元点群データはノイズを多く含んでいることが多いので、次のステップでは、公知のＲＡＮＳＡＣに代表されるような外れ値手法でノイズを除去する（ノイズ除去工程２２）。
【００４５】
さらに、k-meansクラスタリングなどに代表されるようなクラスタリング手法によって、これら障害物の３次元点群をクラスタ化し、それらひとつひとつのクラスタを障害物クラスタとして定義する（クラスタリング工程２３）。
【００４６】
なお、既存手法によっては、ノイズ除去をクラスタリングと同時に、もしくはランドマーク選別の点群マッチング処理で同時に行うことも可能な場合があり、その際は個別のノイズ除去は不要である。
【００４７】
最後に、上記３次元点群について、高さ情報を保存したまま２次元の地図として平面射影する（２．５Ｄ地図写像工程２４）。その様子を図５に示す。図５Ｂに示す２．５次元格子地図において黒い部分が障害物の存在する領域を示している。このひとつの格子は、そこに障害物が存在すればそのｘ，ｙ座標に加え、最大高さ情報(h_max)、およびその格子が属するクラスタＩＤ情報(c_id)も含んでいる。最大高さ情報とクラスタＩＤ情報は、後の経路生成工程３で使用される。
【００４８】
〈移動経路の生成〉
図６は、本実施形態に係る自律移動ロボットの経路生成部により実行される経由地点設置処理の詳細を示すフローチャートであり、図７は、本実施形態に係る自律移動ロボットの経路生成部により実行される経由地点設置処理および安全度ラベリング処理について説明するための模式図である。
【００４９】
《経由地点設置処理》
木などの高い障害物は、その高さが高いほどＧＰＳ電波の遮蔽の影響を受ける範囲が広くなる。そこで、障害物の高さが高くなるほど遠い地点を経由するように、経由地点を設置する。その処理の全体フローを示したのが図６である。以下、具体的な処理内容について説明する。
【００５０】
最初に障害物クラスタの最大高さ（高さの最大値）をそれぞれの障害物クラスタに対して計算する（ステップＳ１１）。次に、障害物クラスタの重心位置を計算する（ステップＳ１２）。ここでは、そのクラスタに含まれる格子ブロックのｘ座標およびｙ座標の平均値を計算して重心位置を求める。
【００５１】
全ての障害物クラスタについてチェック（最大高さおよび重心位置の計算）するまで（ステップＳ１３：No）、ステップＳ１１およびＳ１２を繰り返し、全ての障害物クラスタをチェックしたら（ステップＳ１３：Yes）、次に、その障害物クラスタの近傍にあるクラスタを計算するため、各クラスタの重心位置をノードとして公知のドロネー三角形領域分割によって各ノードを線で結ぶ（ステップＳ１４）。
【００５２】
さらに、各ノードを結ぶ線分上に経由地点を設定するため、線分で結ばれたクラスタの最大高さの比率を計算し（ステップＳ１５）、その比率をとった位置に経由地点のｘ，ｙ座標を設定する（ステップＳ１６）。
【００５３】
図７の場合、障害物クラスタＯiの高さがｈ1、障害物クラスタＯjの高さがｈ2、それらの重心位置を結ぶ線分の長さがｄである。そして、障害物クラスタＯiの重心から｛ｄ×ｈ1／（ｈ1＋ｈ2）｝であり、かつ障害物クラスタＯjの重心から｛ｄ×ｈ2／（ｈ1＋ｈ2）｝である位置に経由地点が設定されている。
【００５４】
全ての障害物クラスタのペアについて同様の処理を実行し（ステップＳ１７：No→Ｓ１５→Ｓ１６）、それが終了したら（ステップＳ１７：Yes）、この図に示す経由地点設置処理が終了する。
【００５５】
《安全度ラベリング処理》
次に図７を用いて安全度ラベリング処理について説明する。
上記までの処理で述べた手法は、障害物の高さを考慮して、できるだけそのような障害物から遠い地点を経由する方法であった。しかし、同じ地点であっても常に安定してＧＰＳの電波を受信可能であるとは限らない。また、空撮による自己位置推定の場合は、日の当たり方によっては障害物の影が発生し、そのような場所ではロボットの位置が捕らえにくい。したがって、多少遠回りしてでも自己位置を見失うことなく安全に移動したい場合がある。また、障害物と障害物の隙間があまりにも狭い場合、どこを通ってもＧＰＳの電波遮断の影響を受ける。加えて、そもそもロボットが通れる分だけのスペースがない場合もある。
【００５６】
そこで、具体的な処理として、まず２つの障害物クラスタ間の距離を計算する。距離は、図７に示すように、そのクラスタの最短距離ｗで定義する。次に、その障害物クラスタ間の最短距離がある閾値以下ならば、その障害物クラスタの間に設置された経由地点を削除する。
【００５７】
次のステップとして、残った経由地点については、２つの障害物クラスタ間の最短距離、およびそれぞれのクラスタにおける最大高さを考慮して、その経由地点がどれだけ電波遮蔽などといった高い障害物の影響を受けやすいか（安全度、もしくは危険度）を数値でラベリングする。
【００５８】
危険度に関しては、例えば以下の式〔１〕によって計算する。
Danger(Ｏi,Ｏj)＝１／（ｈ1＊ｈ2＊１／ｗ(Ｏi,Ｏj))    …式〔１〕
ここで、Danger(Oi,Ｏj)は障害物ＯiとＯj間の経由地点の危険度、ｗ(Ｏi,Ｏj)は障害物ＯiとＯj間の距離を表す。
【００５９】
また、人手によってロボットの通行を許可する閾値を設定し、障害物と障害物の間の距離（移動経路の幅）がその閾値以下であった場合は、危険度∞（もしくは安全度０）としてロボットがその地点を経由しないように設定することを行う。この閾値は、ロボット本体の大きさや高さに応じてユーザが決定することができる。
【００６０】
最後に、これらの処理を前記の経由地点設置処理で結ばれた全てのクラスタのペア同士に関して行う。
【００６１】
ここで生成される移動経路は、経由地点を直線で結んだネットワークで表現されている。こうすることで、ロボットが記憶すべきデータ量を削減できるとともに、ロボットが自律移動の計画を行う際にかかる計算時間を短縮することができる。
【００６２】
〈経路計画工程〉
図８は、本実施形態に係る自律移動ロボットの経路生成部で生成されたネットワーク構造の経路データを示す図であり、図９は、経由地点の安全度を考慮した経路計画について説明するための図である。これらの図を用いて、経路計画の手法について説明する。
【００６３】
経路生成部１１２によって得られた経路データは図８のようなネットワーク構造になる。この図において、楕円や円は障害物クラスタ、星形は経由地点、経由地点を結ぶ点線は通行可能な移動経路を表す。このようなネットワーク構造に対する経路計画の既存手法として、代表的なものにA＊探索やダイクストラ法などが挙げられる。
【００６４】
A＊探索やダイクストラ法のような既存の経路計画手法では、目的地までの最短経路を探索する。したがって、ネットワークにおけるエッジの長さのみが評価の対象である。これに対して、本実施形態に係る経路計画工程では、背の高い障害物に起因する外乱を軽減するため、目的地まで遠回りすることを許可する点が異なる。
【００６５】
すなわち、本実施形態に係る経路計画工程では、上記従来手法において、図８に示すような経由地点の安全度で重み付けたものをエッジの長さ（経路の長さ）に加えて拡張する。具体的には、例として以下の式〔２〕で移動コストを計算する。
Cost(Ｖi,Ｖj)＝Dist(Ｖi,Ｖj)＋α＊Danger(Ｖj)    …式〔２〕
【００６６】
ここで、Cost(Ｖi,Ｖj)は経由地点ＶiからＶjに至る移動コストを表し、Dist(Ｖi,Ｖj)はＶiとＶj間の距離、Danger(Ｖj)はＶjにおける危険度（または安全度）、αはユーザがどれだけ安全度を考慮するかのスケーリングパラメータである。
【００６７】
図９の計算例では、経由地点ＶiからＶjへ至る移動コストであるCost(Ｖi,Ｖj)は、Dist(Ｖi,Ｖj)＝１０、Danger(Ｖj)＝３０であるから、α＝1.0とした場合、Cost(Ｖi,Ｖj)＝４０となる。
【００６８】
なお、目的地の座標はユーザ自身で与えるが、目的地を含めた自律移動経路は自動で生成する。ユーザから与えられた目的地から各経由地点までの距離を計算し、目的地とそれに最も近い経由地点を線で結ぶことで、目的地までの経路を生成する。同様にして、自律移動のスタート地点に関しても、それに最も近い経由地点とスタート地点を線で結ぶことで経路を生成する。
【００６９】
〈既存の経路計画の手法と本実施形態に係る経路計画の手法〉
図１０は、経路データにおける移動距離のみを考慮した経路計画について説明するための図であり、図１１は、経由地点の危険度を考慮した経路計画について説明するための図である。これらの図において、星形は地点（スタート地点、経由地点、ゴール地点）であり、地点を結ぶ点線は通行可能な移動経路であり、実線の矢印は探索された自律移動経路である。また、通行可能な移動経路および探索された自律移動経路に付された数値は地点間の距離である。
【００７０】
前述したように、A＊探索やダイクストラ法のような既存の経路計画手法では、目的地までの最短経路を探索するため、図１０の例のように、スタート地点Ｓからゴール地点Ｇまでの最短経路（Ｓ→Ｖ2→Ｖ5→Ｇ、経路長の合計：５＋５＋５＝１５）が生成される。しかし、このときの危険度は合計で「１０＋９０＋１００＋１０＝２１０」にもなり、特に危険度の高い地点Ｖ2とＶ5を経由することになる。
【００７１】
一方、本実施形態のように安全度を重視する経路計画方法では、図１１のようにゴールまで多少遠回りする自律移動経路を計画することも許可するので（Ｓ→Ｖ3→Ｖ6→Ｇ、経路長の合計：１５＋８０＋８０＝１７５）、移動距離や移動時間は既存手法よりも増加する。
【００７２】
しかしながら、危険度は合計で「１０＋１０＋５＋１０＝３５」であり、図１０の例よりも安全な経路を通ることがわかる。そのため、本手法のほうが自己位置推定に失敗する可能性の低い自律移動経路を計画できていることがわかる。
【００７３】
また、本実施形態においても、α＝０として安全度を無視すれば、移動経路のコストだけを考慮した既存手法と等価な経路計画を行うこともできる。
【００７４】
以上詳細に説明したように、本実施形態に係る自律移動ロボットは、下記（１）〜（３）の特徴を備えている。
（１）ランドマーク（標識）として所定の高さ以上の障害物のみを選別してその存在位置を環境地図のデータとして記録するので、障害物が存在する屋外環境において、記録する環境地図のデータ量を少なくすることができる。
（２）環境地図における障害物の高さに応じて自律移動の経由地点を設定してネットワーク構造で移動経路を表現するので、移動経路のデータ量を削減することができる。その結果、自己位置を推定する際の経路計画の処理時間を短縮することができる。
（３）各経由地点における自己位置を見失う危険性を考慮した経路計画を行うので、高さの高い障害物が存在する屋外環境において、ロボット自身が自己位置を見失うことなく自律移動することができる。
【００７５】
なお、本発明は、以上説明した実施形態に限定されるものではなく、例えば図１の地図生成工程２、経路生成工程３、および経路計画工程４をロボットと通信するサーバが実行するようにした自律移動システムを構成することもできる。また、ロボットが自律移動経路上の経由地点を通過したことを検出する手段を設けることもできる。
【符号の説明】
【００７６】
１…３次元点群データ計測工程、２…地図生成工程、３…経路生成工程、４…経路計画工程、２１…ランドマーク選別工程、２２…ノイズ除去工程、２３…クラスタリング工程、２４…２．５Ｄ地図写像工程、３１…経由地点設置工程、３２…安全度ラベリング工程、３３…経路ネットワーク化工程、１００…演算装置、１０１…３次元計測センサ、１０２…自己位置推定センサ、１０３…記録媒体、１０４…駆動部、１０５…コントローラ、１１１…地図生成部、１１２…経路生成部、１１３…経路計画部、１１４…駆動制御部。
【先行技術文献】
【特許文献】
【００７７】
【特許文献１】特開２０１０−６１３５５号公報
【図１】
2016149090.tif 000003
【図２】
2016149090.tif 000004
【図３】
2016149090.tif 000005
【図４】
2016149090.tif 000006
【図５】
2016149090.tif 000007
【図６】
2016149090.tif 000008
【図７】
2016149090.tif 000009
【図８】
2016149090.tif 000010
【図９】
2016149090.tif 000011
【図１０】
2016149090.tif 000012
【図１１】
2016149090.tif 000013