( )

(1)

NAIST-IS-MT0751005

修士論文

移動ロボットの速度と安全性を両立する経路探索のた

めの地図情報に関する研究

荒井優輝

2009年 2 月 5 日奈良先端科学技術大学院大学情報科学研究科情報システム学専攻

(2)

本論文は奈良先端科学技術大学院大学情報科学研究科に修士 (工学) 授与の要件として提出した修士論文である。荒井優輝審査委員：小笠原司教授（主指導教員）木戸出正繼教授（副指導教員）金出武雄客員教授（副指導教員）加賀美聡客員准教授（副指導教員）

(3)

移動ロボットの速度と安全性を両立する経路探索のた

めの地図情報に関する研究

∗

荒井優輝

内容梗概近年，人と同じ環境で案内，警備，介護などの仕事を行うサービスロボットが発表され話題となっている．これらのサービスロボットはサービスを提供するにあたって自律移動する機能が必要となる．自律移動の機能には地図作成，自己位置同定，経路探索が必要である．その中の経路探索の手法では地図上の通りやすさを表すコストマップが用いられており，コストマップの値によって探索される経路は大きく変化する．一般にコストマップの生成は障害物からの距離に応じて与えられるが，その生成方法はあまり深い議論がされていない．そこで本研究では地図にコストを与える手法として新たに速度マップ，ソナーマップ，環境変化マップを提案しその有効性を移動ロボットアプリケーション Carmen Tookitと移動ロボット Pioneer-2 を用いてシミュレーションと実機における提案手法の有効性を示した．その結果，速度マップはシミュレーション上で移動時間の短縮が達成できた．また環境変化マップを用いた実環境における実験では，危険な場所を回避し障害物と衝突しない経路を生成することに成功した．キーワード移動ロボット, レーザー距離センサ，ソナー, コストマップ, 経路探索 ∗_{奈良先端科学技術大学院大学情報科学研究科情報システム学専攻修士論文,} NAIST-IS-MT0751005, 2009年 2 月 5 日.

(4)

A study of map information for path planning

which combine velocity and safety

∗

Yuki Arai

Abstract

Recently, the service robot that does the work of the guide, guard, the guide, and nursing in an environment the same as human is a topic. These service robots need the function that autonomous mobile when they provide service. Mapping,localization and path planning are necessary for the function of the autonomous mobile. A cost map expressing easiness of street in the map by path ﬁnding is used, and the path varies with the value of the cost map. Generally the generation of the cost map is given depending on the distance from an obstacle, but, as for the generation method, a too deep argument is not done. Therefore We suggested sonar map, speed map, environment change map as technique newly to allot the cost to a map in this study. I showed the eﬀectiveness of the proposal technique with simulation and an actual machine with mobile robot application Carmen Tookit and mobile robot Pioneer-2. As a result, the speed map was able to achieve shortening of movement time on simulation. In addition, by the experiment in the true environment where I used an environmental variation map for, Robot avoid dangerous places and succeeded in an obstacle and the path planning that did not collide.

Keywords:

mobile robot, laser range sensor, sonar, cost map, pathplaning

∗_{Master’s Thesis, Department of Information Systems, Graduate School of Information}

(5)

1. 序論 1 1.1 背景 . . . . 1 1.2 関連研究 . . . . 1 1.3 研究の目的 . . . . 3 1.4 本論文の構成 . . . . 3 2. 環境情報統合マップ 4 2.1 はじめに . . . . 4 2.2 背景となる地図生成，位置認識，経路計画手法 . . . . 5 2.2.1 地図作成 . . . . 5 2.2.2 自己位置同定 . . . . 9 2.2.3 経路探索法 . . . . 10 2.3 速度マップ . . . . 14 2.3.1 生成アルゴリズム . . . . 14 2.3.2 速度分布からコストへの変換 . . . . 14 2.4 ソナーマップ . . . . 15 2.4.1 ソナーマップの生成アルゴリズム . . . . 15 2.5 環境変化マップ . . . . 16 2.5.1 レーザマップ生成アルゴリズム . . . . 17 2.5.2 環境変化マップ生成アルゴリズム . . . . 17 2.6 まとめ . . . . 18 3. 実験 19 3.1 実験環境 . . . . 19 3.1.1 Carmenの概要 . . . . 19 3.1.2 ロボットの仕様 . . . . 19 3.1.3 実験環境 . . . . 22 3.2 基本機能の実験 . . . . 22

(6)

3.2.1 地図の評価 . . . . 22 3.3 速度分布マップ実験 . . . . 24 3.3.1 速度マップ評価実験 . . . . 24 3.3.2 シミュレーション結果と考察 . . . . 26 3.4 ソナーマップ実験 . . . . 30 3.4.1 検出実験 . . . . 30 3.4.2 走行実験 . . . . 30 3.5 環境変化マップ実験 . . . . 34 3.6 統合実験 . . . . 36 3.6.1 ソナーマップと環境変化マップ統合実験 . . . . 36 3.6.2 ソナーマップ環境変化マップ統合実験 . . . . 42 4. 結論 43 謝辞 44 参考文献 46 付録 48 A. CARMEN Toolkit 48 A.1 概要 . . . . 48 A.2 インストール . . . . 48 A.2.1 インストール環境 . . . . 48 A.2.2 必要パッケージ . . . . 48 A.2.3 バグ . . . . 49 A.3 モジュール解説 . . . . 49 A.4 実行手順 . . . . 51 A.4.1 シミュレーションでの実行 . . . . 51 A.4.2 実機での実行 . . . . 51 A.5 マップ作成 . . . . 52

(7)

図目次

1 EMIEW . . . . 1 2 レーザスキャンデータ . . . . 6 3 ICPアルゴリズム . . . . 7 4 オドメトリベースの地図 . . . . 8 5 スキャンマッチング . . . . 8 6 モンテカルロ位置推定 . . . . 11 7 Waverront アルゴリズム . . . . 12 8 セルのアップデート . . . . 13 9 ポテンシャル場の生成 . . . . 13 10 lpn . . . . 13 11 速度分布マップ . . . . 15 12 ソナーのモデル . . . . 16 13 ソナーの多重反射の例 . . . . 17 14 レーザーのモデル . . . . 18 15 Pioneer3 . . . . 20 16 実験環境 . . . . 21 17 地図と CAD データとの比較 . . . . 23 18 速度マップ . . . . 25 19 コストマップの比較 . . . . 27 20 パスの比較 . . . . 27 21 グラデーションマップ+速度マップの軌跡 . . . . 28 22 グラデーションマップの軌跡 . . . . 28 23 速度マップの軌跡 . . . . 29 24 コストマップ無しの軌跡 . . . . 29 25 ソナーマップ . . . . 31 26 ソナーマップ寸法評価 . . . . 31 27 ソナーマップ . . . . 32 28 ソナーマップ経路比較 . . . . 33

(8)

29 環境変化マップ実験の経路の比較 . . . . 34 30 環境変化マップ . . . . 35 31 実験環境 . . . . 36 32 Aの経路の比較 . . . . 38 33 Bの経路の比較 . . . . 39 34 Cの経路の比較 . . . . 40 35 Dの経路の比較 . . . . 40 36 Eの経路の比較 . . . . 41 37 統合実験の経路 . . . . 42 38 carmenモジュール構成 . . . . 50 39 navigatorgui . . . . 51 40 robotgui . . . . 52

表目次

1 ガウシアンフィルター . . . . 14 2 Pioneer-3の仕様 . . . . 19 3 レーザレンジセンサの仕様 . . . . 20 4 実験結果 . . . . 26 5 ソナーマップの精度比較 . . . . 30 6 ソナーマップの実験結果 . . . . 33 7 環境変化マップの実験結果 . . . . 34 8 Aの結果 . . . . 38 9 Bの結果 . . . . 38 10 Cの結果 . . . . 39 11 Dの結果 . . . . 39 12 Eの結果 . . . . 41

(9)

1. 序論

1.1 背景

近年，少子高齢化の影響により労働人口の減少が危惧されており 2030 年には 2006年と比較し 1037 万人減少するとの報告もある [14]．そこ案内，警備，福祉，介護，アミューズメントといった仕事を人間に代わって行うサービスロボットが必要とされつつある．現在，トヨタ自動車のロビーナ，ALSOK のガードロボ [10]，三菱重工の wakamaru[11], 富士通の enon，日立の EMIEW Fig.1 [3] といったロボットたちがいる．上記のロボットたちのうちいくつかは実際の商業施設で活躍している．これらのサービスロボットは，作業の内容や環境が限定されている産業用ロボットとは異なり，人間と同じ環境で動き回るため，周囲の環境を認識しながら移動する機能が必要となる．この様な機能を持つロボットを移動ロボットと呼びロボット自身の移動する環境の地図生成，環境中におけるロボット自身の位置を知る自己位置同定，目的地まで移動する経路を生成する経路探索の機能が必要となる． Fig. 1 EMIEW

1.2

1.3 研究の目的

本研究では，環境の様々な情報を経路探索で使用するコストマップに反映させることで，経路探索の際の計算コストを増加させることなく，経路探索の安全性と走行時間の短縮を実現することが目的である．移動ロボットの経路計画はゴールまでの最短経路を求める問題であるがそれらが地図上において最短経路であってもその経路がロボットの走行時において最短時間で走れる経路とは限らない. そこで，地図の各点における走りやすさを求めコストマップへ変化する．また近年の移動ロボット研究において周囲の環境の認識にはレーザー距離センサを用いた物が主流である．むろん本研究においてもレーザ距離センサは使用しているがそれだけでは取得困難な環境の情報が数多くある．例えば，レーザーは高速に高精度なデータが得られるが，レーザを吸収，透過してしまうような物体，計測データが 2 次元形状しかとらえられないといった欠点がある．そのためレーザー距離センサのみで構成された地図では情報が不足してしまう．場合によってはこの不足データがロボットを危険にさらしてしまう場合がある．レーザ以外のセンサから取得したデータもコストマップへ反映する．これらを組み合わせサンプリングベースのコストマップを用いることによって安全かつ迅速な経路探索の実現を目指す．

1.4 本論文の構成

本論文ではこの章以降，2 章では井戸ロボットの基本的な機能と本研究で提案するマップの生成手法について述べる 3 章では前章で作った各種マップについての評価実験を行った結果を述べる．4 章では、現状と今後の課題について述べる。また、付録 A には今回使用した Carmen を解説した物を添付する．

(12)

2. 環境情報統合マップ

2.1 はじめに

本章では自律移動ロボットに必要となる基本的な機能を説明した上で，本研究の目的であるコストマップの生成方法について述べる．初めに，自律移動ロボットでは次の機能が必要となる．地図生成自己位置同定経路探索移動ロボットにおいて地図とは自己位置同定や経路探索を行うのに必要となる物である．本研究では地図生成に ICP アルゴリズムを使用し，実験環境のグリッドベースな地図を生成する．次にロボットは地図とセンサを用いて地図上の自己位置を知る必要がある．この自己位置同体にはパーティクルフィルタを用いたモンテカルロ位置推定 (MCL)[8] を用いる．次にロボットは求めた自己位置からゴールまでの経路を探索する．ロボットが現在位置から目的地へ移動するには目的地までの経路を生成する必要がある．ロボットの経路探索方法には主にポテンシャル法 [6] と A*[2] ベースな方法がある．本研究では経路探索に [4] の方法を用いる．また経路探索では探索時に与えるコストマップによって生成される経路が大きく変化する．地図に与えるコストとして最も考え付くのが障害物との距離であり，多くの研究では障害物からの距離を基にコストマップを生成している．そこで経路計画に用いるコストマップを工夫することでロボットの経路探索時の計算量を増加させることなく経路探索の性能向をはかる．本研究で生成するコストマップの種類は以下の通りである速度マップソナーマップ環境変化率マップ

(13)

まず速度マップは地図のセルごとの平均速度を記録したものである．この値を基にコストにマップを生成し平均速度の高い場所を優先的に選択して経路探索することで移動時間の短縮を図るソナーマップはロボットに搭載されているレーザ距離センサで認識困難なガラスなどの検出に用いて，より安全な経路探索を目指す．環境は日々変化しておりロボットがプランニングを行う際に保有している地図情報と実際の環境が異なっている場合がある．このような想定外の環境の変化によってロボットが危険にさらされたり，経路の再探索が必要となってしまう場合がある．そこで環境の変化しやすい場所を事前に知っておくことでこの様な事態を避け，移動にかかるリスクやコストを下げることを目的とする．そしてこれらのマップを統合し，より安全で高速な探索を可能とするコストマップを生成することを目的とする．マップの定義を述べる．

2.2 背景となる地図生成，位置認識，経路計画手法

2.2.1 地図作成まず始めにロボットは移動する環境の地図を保持している必要がある．地図を作るには Fig2 に示すような測域センサなどで得た周囲環境の局所的な形状を結合して全体の地図を作る必要がある．データの結合には各データの正確な計測位置が必要となる．通常，ロボットの位置を知る GPS やロボットのエンコーダから得られるオドメトリが用いられるがこれらは誤差を含んでおり補正が必要である．そこで測域センサなどの計測値をもとに自己位置の補正を行う．この様に自己位置と地図の両者を同時に推定することを SLAM(Simultaneous Localization and Mapping) と呼ぶ．

SLAMには大きくわけて，ベイズの定理を用いて確率的に行う方法，スキャンマッチングの 2 種類がある．本論文では Carmen で使用している [1] の方について触れる．

ICPアルゴリズム (Iterative Closet Point アルゴリズム)

(14)

Fig. 2 レーザスキャンのデータ白色の部分が空き空間，赤色部分は物体を感知した場所，薄い青は不明領域データ間の誤差が最小最小となる相対位置を繰り返し計算で求める方法であり，式 2 を最小にする問題である．また前提条件として 2 個のデータ間にある程度の位置合わせができている必要がある． Mk = C(Sk, T ) (1) E(T ) =∑ i+1 N (Mi− (Rsi+ T )) 2→ min (2) M モデルデータのベクトル s 計測データのベクトル N 計測データの数 R 回転行列 T 平行移動ベクトル ICPの処理の具体的な手順を説明する 1. モデルデータと計測データ (Fig.3(a)) に対して，計測データの各点とモデルデータ各点の最も近い点同士を対応点とする (Fig.3(b))．

(15)

2. 計測データとモデルデータの誤差を近づけるような変換行列を求める (Fig.3(c))．．この作業には最急降下法やニュートン法が用いられる． 3. (b)と (c) を 2 個のデータの誤差が閾値以下になるまで繰り返すことで 2 個のデータの対応関係が求まる (Fig.3(d))． Fig. 3 ICPアルゴリズム SLAMに ICP を用いる場合は測域センサ siのデータと，モデルデータ Miに ICPを行い，求められた R, t の値を用いてオドメトリを補正すればよい．参考にオドメトリと測域センサから構成した地図 Fig.4 に対して ICP アルゴリズムをほどした物を Fig.5 示す．

(16)

Fig. 4 オドメトリベースの地図ロボットの得たオドメトリの上にレーザデータをかぶせた物．大きくずれているのが分かる．

Fig. 5 スキャンマッチング; Fig.4 にスキャンマッチングを施しオドメトリの誤差を修正した物.

(17)

2.2.2 自己位置同定自己一同定とは与えられた環境中の地図に対してロボットの位置と姿勢を推定する問題である．パーティクルフィルタノンパラメトリックなベイズフィルターの実装方法の一つである．事後信念を有限個のパラメータで比較する． 事後信念の状態から状態をランダムにサンプリングして事後信念 bel(xt)を表現すると言うものである．パーティクルフィルタでは事故確率分布の標本はパーティクルと呼ばれ式 (3) で表される． Xt= x[1]t , x [2] t , . . . x [M ] t (3) 各パーティクル xt [m]は時刻 t における状態の推定値である．M はパーティクル の数を表し，M が大きいほど真の状態を推定しやすくなる． 1. 初期状態パーティクルの初期値 X0を設定する． 2. 予測各パーティクルについて前状態から現状態の予測を行う．パーティク ルと制御値から現在の状態の推定値を行う．制御データ utと，時刻 Xt− 1 のパーティクル Xtの推定値 ¯Xt を求める． 3. 重み付け現状態における各パーティクルの尤度を求める．次式で尤度の計算を行う w_t[m] = p(zt|x [m] t ) (4) この係数はパーティクル x[m]t で計測値 ztを得られる確率である．重み付け られたパーティクルの集合はベイズフィルタの事後信念 brl(xt)を表す．次にリサンプリングもしくは重み付きサンプリングを行い 信念 bel(xt)を bel(xt−1)から再帰的に構築する． 4. リサンプリング ¯Xtから M 個のパーティクルを選択しなおす，各パーティ クルが選ばれる確率は各パーティクルの重み w[m]t によって決定される．

(18)

2から 5 を繰り返すことで状態を推定できる．

モンテカルロ位置推定 (Monte Carlo Localization MCL)

前節で説明したパーティクルフィルタを自己位置同定に用いたのが，モンテカルロ位置推定 (Monte Carlo Localization MCL) である．Fig.6 は通路を用いて MCL の例を示したものである．p(z|x) 計測確率を示し，現在の位置 x からどのような 計測値 z が得られるかを示す確率法則である．初期の大域的な不確かさは Fig.6(a) のように，姿勢空間全体で一様にランダム選ばれたパーティクルで表現されている．ロボットが移動しドアを感知したときに，MCL はパーティクルの重みを変更する．その結果が Fig.6(b) である．各パーティクルの高さはパーティクルの重みを示している．ここではパーティクルの場所は変化せず重みのみの更新に止まる． Fig.6(c)はロボットが移動してリサンプリングした後のパーティクルの様子である．この仮定では同じ重みを持つ新しいパーティクルののセットが生成される．ロボットのいる確率が高いと思われるドアの付近のパーティクルの密度が増加していることが分かる．新たに計測した後は Fig.6(d) のようにパーティクルの重みは不均一になる．この時点でほとんどの存在確率が 2 番目のドアに集まっている．この後，ロボットが動くともう一度リサンプリングが行われ，新たなパーティクルのセットが動作モデルにしたがって生成される．Fig.6(e). この例から明らかなようにパーティクルのセットは事後信念を正しく近似している． 2.2.3 経路探索法本研究では経路探索に Konolige らのポテンシャル法ベースの手法 [4] を用いた．パスコスト 地図上のの経路を点の純序列で表し，k からスタートするパスを Pkとおく． P ={p1, p2, . . .} (5) 点の集合は隣り合う 8 近傍のグリッドであり，重複する点は含まれない．また，経路の最後はゴールでなければならない．

(19)

(20)

スターと点から現在の点経路ののコストは F (P ) の関数 (離散系) で表されれる． F (P ) =∑ i I(pi) + ∑ i A(pi, pi+1) (6) Iと A どちらとも任意のコストを与えられる．I は通過時のコストを示し，与えられた領域の特性に応じて設定される．例えば，障害物の近くや不明な領域，滑 りやすい場所は高いコストが与えられる．A はロボットが移動する piと pi+1の 2 点間の距離に比例したコストを割り当てる．A の合計は経路の長さに比例したコストが与えられる． Fig．8 を説明すると，現在地が中央のセルで，次の目的地が左上のセルとす る．現在の移動コストの合計 (ポテンシャル)C = 20 であるとすると．次のセルの コスト I = 5，移動距離のコスト A14であることから次の目的地のポテンシャルは 20 + 14 + 5 = 39 となる．この処理をすべてのセルに施し，生成されたポテンシャル場を降っていくことで最良な経路散策が実現される．また場のコストは障害物からの距離に応じて与える．このアルゴリズムを実際に用いた様子が Fig.10 である． Fig. 7 Waverront アルゴリズム

(21)

Fig. 8 セルのアップデート

Fig. 9 ポテンシャル場の生成

(22)

2.3 速度マップ

通常の経路探索は計算幾何学な部分しか考慮されていないため，生成された経路長が距離が最短であっても，走行時間が最短である保証はない．すなわち，走行時の周囲の障害物の位置によって加減速，旋回が求められトータルの走行時間がかさむ場合がある．そこで，あらかじめ地図上に各地点で出せる速度を持たせ，移動コストに反映させることでより最適な経路を生成可能にする． 2.3.1 生成アルゴリズム速度マップの生成にはシミュレーション上でランダムにスタートとゴールをあ たえ自律走行を行うことを繰り返す．任意のセル mpを通過した距離 ∆l と通過に かかった時間 ∆t とセルを通過した回数 n を用いて，任意のセル任意のセル mp の値を式 (7) の用に定義する． mp = 1 n n ∑ i=0 ( ∆li ∆ti ) (7) 生成した速度分布マップは Fig11(a) で示されるが，このままではデータの存在しないセルが存在するので，補間処理が必要となる．データの補間は周囲 8 近傍の内値を持っているセルの最小値を用いる．最後に補間を行ったセルに対して Table1 のガウシアンフィルタを掛けたものが Fig11(b) となる． Table. 1 ガウシアンフィルター 1 16 2 16 1 16 2 16 4 16 2 16 1 16 2 16 1 16 2.3.2 速度分布からコストへの変換得られた速度分布からコストマップへ変化することが必要となる．いくつかの変換式を定義し，それらを用いて生成したコストマップを用いてシミュレーショ

(23)

(a) (b) Fig. 11 速度分布マップ: (a) は補間前，(b) は補間後である．ンを行った．100 個のスタートとゴールのセットを用意し各コストとマップを用いた自律走行のテスト行い最も移動時間の短かったものをコストへの変換パラメータとして用いる．

2.4 ソナーマップ

ロボットのセンサにはレーザ距離センサを用いている．レーザ距離センサは高速，高精度であるがその特性上ガラス等の透明な物体や，センサを設置している高さ以外の障害物の認識が不可能である．ソナーを用いて生成した地図を用いることでガラス等の透明な物体を地図に記すことでレーザーで見えない障害物を検出ガラスを主とした透明な物体の検出 2.4.1 ソナーマップの生成アルゴリズム基本的なアルゴリズムは 2.5.1 節と同様に各グリッドの障害物の存在率を求めることで生成するしかし，ソナーはその特性上距離に比例して計測範囲が広がる 12ことから遠距離にある障害物ほど正確な位置を取るのが困難である．そこで障 害物領域のグリッドに距離に反比例したポイントを与え，マップ m の障害物の存

(24)

在確率を式 (8) で与え任意の閾値値以上のセルを障害物とみなす． mi = 1 n n ∑ i=0 ( 1 l2 i ) (8) Fig. 12 ソナーのモデルまたソナーは吸音，鏡面反射や多重反射 (Fig.13) などの影響から真値から大きく異なる値を出すことがある．吸音や鏡面反射はソナーの返答が応答が存在しないだけであるため異常値であるかの判定は容易であるが，多重反射はその判断が困難である．特に狭い通路などではその影響を顕著に受ける．そこで，ソナーの計測回数が一定数以下の領域についてはノイズとして処理する．

2.5 環境変化マップ

移動ロボットは人の生活環境は日々変化しており，ロボットが使用する地図の更新が必要である．しかしロボットが常に最新の地図を保持することは困難であり，実際の環境と異なった地図は自己位置同定や経路探索に悪影響を与える．得に環境の変化が激しい場所ではロボットにとって危険な場所であるといえる．自己位置同定は環境の変化に対してある程度ロバストに対応できるが経路探索は地

(25)

Fig. 13 ソナーの多重反射の例図の変化によって大きな影響を受ける場合がある．そこで地図の更新時に環境の変化の起こった場所を記録し，環境の変化が起こりやすい場所を発見することでロボットがそのような場所に近づく可能性を下げるように試みる， 2.5.1 レーザマップ生成アルゴリズムこの節では地図の更新を行うアルゴリズムを説明する．まず正方形に区切ったグリッド地図を用意しその上にレーザの計測データをに基づき各グリッドに値を振り分ける．Fig.14 はレーザ一本分をモデル化した物である．ここでグリッドは占有領域と非占有領域と未計測領域に分けられる．占有領域は障害物が計測され た場所をとる．またレーザーには計測誤差が含まれるため誤差 ∆d の幅分も加え て占有領域とする．非占有領域はレーザが通過した占有領域以外のグリッドをとる．各グリッドごとに占有領域と非占有領域と判定された回数を計測回数とし，計測回数と，占有領域と判定された回数から各セルごとに障害物が計測された確率を計算する．一定の確率以上のセルを障害物の存在するグリッドとして地図を更新する．またこの際のロボットの自己位置は取得出来ている前提で行う． 2.5.2 環境変化マップ生成アルゴリズム先ほど述べた手法で地図の更新を繰り返し地図の変化を保存していき，環境変化マップのコストを次式で与える．現在の障害物の有無，過去に渡っての障害物

(26)

Fig. 14 レーザーのモデルのあった確率と障害物の有無の変化をもとに現時刻でのマップの信頼性を求めコストに反映する．グリッドに変化が生じた確率を式)9) で表しこれをコストとし用いる．また移動ロボットは経路探索時に自身を円と仮定して障害物ロボットのサイズの半径分膨張させる処理を行っている．このコストをロボットの半径分だけ膨張させる作業を行う． cost = 1 t t ∑ i=0 kMi− Mi−1k (9) M 地図データ (値は 1 もしくは 0) t 地図の更新回数

2.6 まとめ

本章では移動ロボットの基本的な機能であるである地図作成，自己位置同定，経路探索を述べた上で，本研究のメインとなる環境情報統合マップの各要素である，速度マップ，ソナーマップ，環境変化マップの生成アルゴリズムについて述べた．

(27)

3. 実験

3.1 実験環境

3.1.1 Carmenの概要

本研究ではベースシステムとして Carmen Tool Kit [5] を用いる．

Carmenの使い方の詳細については A 章で述べる．以下の実験を行うに当たって以下の 2 点は既知とする．

ロボットの自己位置

レーザ距離センサを用いて生成した実験環境の地図

3.1.2 ロボットの仕様

本研究において ActivMEDIA ROBOTICS 製ロボット，Pioneer3 Fig.15 を使用した．使用したレーザ距離センサは SCIK 社の LMS 200 を使用した．センサの仕様を Fig.3 に示す． Table. 2 Pioneer-3の仕様車体サイズ 0.51[m] x 0.42[m] 車輪サイズ 190mm 最大速度 0.5 [m/s] 最大角速度 40[deg/s] 重量 16.5[kg] 制御方法シリアル通信ソナーの数 8 ソナー角度分解能 20 [deg] ソナー最大レンジ 4.0 [m]

(28)

Fig. 15 Pioneer3 Table. 3 レーザレンジセンサの仕様視野 180° 角度分解能 1°∼ 0.25° 応答時間 13 ∼ 53 ms 分解能 10 mm システム誤差 15 mm 統計的誤差 (1σ) 5 mm レーザクラス 1 最大測定距離 80 m 測定可能距離 ≦ 10 m（黒色無光沢）

(29)

(A) (B) (C) (D) (E) (F) (G) (H) (I) (J) (K) (M) Fig. 16 実験環境:本研究で実験を行った環境地図上の記号と写真が対応している．写真は矢印の方向へ見たものである．

(30)

3.1.3 実験環境

3.2 基本機能の実験

3.2.1 地図の評価実験の基本となるラボのマップを生成した．臨海副都心センターの 3F の地図である Fig.17 は生成したマップを建物の CAD 図面と比較したものである．これより生成した地図と CAD 図面とがほぼ一致していることが分かる．また地図の左右の廊下の終端が実際よりも短くなっているがこれは特徴点が少ないため ICP アルゴリズムがミスマッチングを起こしたためである．

(31)

Fig. 17 地図と CAD データとの比較 ;赤色で示すのが CAD データ

(32)

3.3 速度分布マップ実験

3.3.1 速度マップ評価実験本項目では，2.3 節で説明した速度分布マップの有用性を実験する．実験は生成した速度分布マップ (Fig.18) と 2.2.3 節で説明した経路計画を組み合わせて評価を行った．をそうでない場合において同じスタートとゴールのセットを与え，その際の走行距離と走行時間を比較した．実験条件は最大速度 0.5[m/s]，最大旋回速度 40[deg/s], リプラン条件はロボットが目標パスから 0.5[m] 離れた場合のみとした．ランダムに設定したスタートとゴールのデータセットを 200 種類生成し各コストマップ 100 個のスタートとゴールの組み合わせをそれぞれのコストマップを用いて経路探索のシミュレーションを行った．

(33)

Fig.

18

(34)

3.3.2 シミュレーション結果と考察その結果が Table.4 である．移動に必要とした時間はコストマップを用いない物がもっとも多いが，経路探索の失敗が最も多く実用性にかける．次に良いのが速度マップのみを用いた物である．この結果は衝突回数も 0 回と安全性も確保されていることが分かる． Table. 4 実験結果コストマップの種類時間 [s] 走行距離 [m] 総角度変化量 [deg] 衝突回数 [回] グラデーションマップ + 速度マップ 9481.19 3285.27 69335.67 0 グラデーションマップ 9597.00 3201.09 59086.09 1 速度マップ 7317.94 3058.46 78101.27 0 なし 6463.36 2812.68 47682.20 6 速度マップとグラデーションマップに大きな差が現れた結果と理由として次のことが上げられる．Fig.20 パスの速度マップを用いた場合とグラデーションマップを用いた場合の走行の軌跡を表した物である．走行軌跡に大きな差が現れている．また同じ場所のコストマップは 19 であるが， Fig19(b)は下の方の通路は障害物に挟まれ障害物の距離応じたグラデーションによってコストが非常に高くなっている．これに対して Fig19(a) は通路は細いもののここを通過するのに減速や衝突がなかったため危険はないとしてコストが低めに設定されている．以上のことから障害物の距離から機械的にコストを求めたグラデーションマップは障害物からの距離をとった安全な経路を生成するのには有効だが場合によっては安全に走れる最短経路を探索できない場合がある．これに対し速度マップは，速度が速い場所はロボットがトラブルなく走れていることを結果的に示している物であるため，見掛け上危険に見える経路でも安全であるかどうかを判別できる．また，本当に危険な場所は衝突や減速が発生し速度マップのコストが上昇するため危険な場所を回避できる．この点については 4 速度マップとコストマップ無しの衝突回数から分かる．

(35)

よって単に幾何的に生成したグラデーションマップよりその場所の危険度と通りやすさを正しく表しているものと言える．また「グラデーションマップ+速度マップ」の結果に有意差が出ていないのはグラデーションマップによって速度マップのコストが上書きされてしまった結果だといえる． (a) 速度マップによるコスト (b)グラデーショーンマップによるコスト Fig. 19 コストマップの比較 (a) 速度マップ (b) グラデーショーンマップ Fig. 20 パスの比較

(36)

Fig. 21 グラデーションマップ + 速度マップの軌跡 Fig. 22 グラデーションマップの軌跡

(37)

Fig. 23 速度マップの軌跡 Fig. 24 コストマップ無しの軌跡

(38)

3.4 ソナーマップ実験

3.4.1 検出実験ソナーを用いたガラスの検出実験を行った．実験は Fig.16 の環境において行った．閾値を 0.15，ソナーの検出回数が 1 回以下のデータはノイズとして扱い，ソナーマップのしきい値処理を行った．得られたソナーの地図が Fig.25 で示される．このマップの精度評価として実際の環境と比較を行った．比較結果が Table.3.4.1 である．10cm 以下の精度でデータが取得できていることがわかる．また地図は 10cmx10cmのグリッドで構成されているため，ソナーマップの最小単位は 10cm である．またソナーマップの主な目的はレーザで認識不可能な障害物の認識であるため，既にレーザで認識でできている障害物がソナーで認識できていないことについては得に問題としない． Table. 5 ソナーマップの精度比較実測値 [cm] ソナーマップ [cm] A 140 150 B 123 120 C 210 210 3.4.2 走行実験ソナーマップから生成したコストマップを用いて走行実験を行った．実験環境風景は 16(a)(f) である．しきい値の条件は 3.4.1 と同じとし，得られた障害物をコストとして与えた実環境で走行実験を行った．その結果が 28 と 3.4.2 である．

(39)

Fig. 25 ソナーマップ; 黒色で描かれているのがレーザから生成した地図，赤色で示されているのがソナーから生成した地図，青色は不明な領域を示す．また図中のアルファベットは Fig．3.4.1 中の物と対応している

(a) (b)

(40)

Fig.

27

(41)

Table. 6 ソナーマップの実験結果コストマップ成功回数 [回] ソナーマップあり 10/10 ソナーマップなし 0/10 (a) ソナーマップあり (b) ソナーマップなし Fig. 28 ソナーマップ経路比較

(42)

3.5 環境変化マップ実験

環境変化マップの性能評価を行った．評価に行うために 1 週間の環境の変化を記録したデータを用いて環境変化マップ (Fig.30) を生成した．この結果よりドアの場所やテーブル近辺の変化率が高めに出ている．また計測誤差の影響から壁際部分の変化率も高めになっている．なおマップ上部と左下部の範囲はは環境変化の収集を行っていない．環境変化率からコストへの変換は 1 倍として．環境変化マップを用いた場合と用いなかった場合のコストマップにおいて実環境を走行した結果が Table.7 と Fig.29 である．環境変化マップありでは到達回数 10 回と良好な結果が得られているが，対する環境変化マップなしでは到達回数 2 回であり，平均到達時間も倍近く要している．この結果から環境変化マップを用いたコストマップがが有効であることがわかる． Table. 7 環境変化マップの実験結果コストマップ到達回数 [回] 平均到達時間 [s] 環境変化マップあり 10/10 58.7 環境変化マップあり 2/10 90.7 (a) 環境変化マップあり (b)環境変化マップなし Fig. 29 環境変化マップ実験の経路の比較

(43)

Fig.

30

(44)

3.6 統合実験

3.6.1 ソナーマップと環境変化マップ統合実験実験条件速度マップを除くコストマップの評価を Fig.16 の環境で行った．ソナーマップはラボ全域を計測した Fig.27 を用いた．環境変化マップは 1 週間分の環境の変化を記録したデータを用いて生成した，Fig.30 を用いる． 実験のゴールセットを Fig.31 に示す．スタートは S から各ゴール A ∼ E まで の走行を本研究で生成したコストマップを使用した場合とそうでない場合の比較を行った．また他の実験条件は以下の通りである．実験条件 1 経路の再検索はロボットが計算した経路から 0.5[m] 外れた場合にのみ行うコストマップは障害物の距離を元にしたグラデーションマップのみ実験条件 2 コストは環境変化マップが 0.5 倍コストはグラデーションマップの上に加算ソナーマップのしきい値 0.15 他は実験条件 1 と同じとする． Fig. 31 実験環境

(45)

実験結果と考察各ゴールに対して各実験条件を 3 セット行った経路探索の結果を Table.8∼12 に示す．またその時の走行した経路の軌跡を Fig.32∼36 に示す．また図中に実験条件 1 の軌跡を赤色，実験条件 2 の軌跡を緑色で示し，衝突した場所を× 印で記す． ゴール A の実験では条件 2 の走行のみが成功している．ソナーマップによって障害物が見えていたかどうかの差である Fig16(K) の緑色のマットがソナーで認識できていたので回避ができたのである．これはゴール E の場合も同じことが言える．こちら側もソナーマップによってガラスが認識されていたため衝突を回避できている．ゴールセット B についてはコストマップ無しでは Fig16(G) の真ん中部分を通る経路を選択した結果条件 1 では衝突している．衝突した付近は普段ロボットの実験スペースとして使用しており環境の変化が多い場所 (Fig.30) である．ゴールセット C とについては Fig16(M) に環境を含んでいる．どちらの条件も走行距離は同じだが走行時間については僅かだが差が現れている．これは環境変化マップ初期位置が環境変化マップの影響下にありその結果経路のスターと方向が初期姿勢と差が大きくなる方に向いてしまいその旋回動作によってタイムロスした影響である．ゴールセット D については経路と走行時間ともにあまり差が出ていない．これについては通貨場所の Fig16(F) 通路であり環境の変化があまりないことと， Fig16(E)が十分な広さがあるであるため環境の変化が経路探索にあまり影響を与えないためである．以上の結果より，実験結果 A と E よりソナーマップの有効性が，実験結果 B より環境変化マップの有効性が確認された．

(46)

Table. 8 Aの結果実験条件ゴール走行距離 [m] 走行時間 [s] 1 × 5.49 12.29 × 5.85 13.99 × 5.48 11.87 2 ° 17.09 40.29 ° 16.34 39.68 ° 16.33 39.54 Fig. 32 Aの経路の比較 Table. 9 Bの結果実験条件ゴール走行距離 [m] 走行時間 [s] 1 × 17.71 38.23 × 18.45 37.44 × 17.78 36.77 2 ° 27.81 63.89 ° 27.71 64.28 ° 27.89 65.50

(47)

Fig. 33 Bの経路の比較 Table. 10 Cの結果実験条件ゴール走行距離 [m] 走行時間 [s] 1 ° 18.54 41.11 ° 18.50 40.47 ° 18.53 40.16 2 ° 18.55 45.59 ° 18.77 47.80 ° 18.63 45.09 Table. 11 Dの結果実験条件ゴール走行距離 [m] 走行時間 [s] 1 ° 21.38 50.22 ° 21.77 53.10 ° 21.46 51.20 2 ° 21.89 51.00 ° 21.77 51.14 ° 21.89 52.23

(48)

Fig. 34 Cの経路の比較

(49)

Table. 12 Eの結果実験条件ゴール走行距離 [m] 走行時間 [s] 1 × 41.98 85.59 × 14.78 34.53 × 14.74 35.74 2 ° 42.04 86.83 ° 41.97 85.41 ° 41.98 85.59 Fig. 36 Eの経路の比較

(50)

3.6.2 ソナーマップ環境変化マップ統合実験 3.3から 2.5 で生成したコストマップをすべて統合して実機の走行実験を行った．統合方法は各コストマップを同じ重みで合計したものを用いる．緑の点はサブゴールを示しロボットはサブゴールを通って黄色の点で示すゴールへの経路探索を行う．実験の結果障害物に衝突することなく走行距離 137.5[m]，走行時間 291.5[s]，平均速度 0.47[m/s] で完走した． Fig. 37 統合実験の経路

(51)

4. 結論

本論文ではロボットの速度と安全を両立する経路探索を実現するために移動ロボットを構成するのに必要な基本的なアルゴリズムを述べ，経路探索時に用いるコストマップを生成する手法を提案した．本研究では経路探索時に用いられるコストマップに様々な情報を付加することで経路探索の計算コストを増やすことなく性能の向上を目指した．ベースとなる環境の地図を生成しその地図を基にシミュレータ環境において速度マップを生成した．また移動ロボット Pioneer2 を使い環境のレーザ距離センサでの認識が困難なガラスなどの物体の位置を示すソナーマップを生成した．地図の更新機能を実装し環境の地図をできる限り新しい状態に保つともに環境の変化を記録し環境変化の起こりやすい地図の情報の信頼性が低い場所を示す環境変化マップを生成した．そしてこれらの地図をコストマップ変換し，速度マップをシミュレーションで，ソナーマップ，環境変化マップをロボットを用いて実環境で実験を行い提案するコストマップの有効性を確認した．その結果速度マップを用いたシミュレーションで安全性を保ったまま移動時間の短縮が達成できたまた環境変化マップとソナーマップ用いた実環境における実験では危険な場所を回避して安全な経路探索を行うことに成功した．また本手法はコストマップマップの生成には周囲の環境情報の蓄積などに多くの時間を必要としするがコストマップの生成後は経路探索の計算コストを増加させることなく性能のよい経路探索が可能となる．また本研究の手法はコストマップを用いる他の経路探索手法に適応できる可能性が高いと考える．今後の展望としては本研究で行っていた手動で行っていた各種マップからコストマップへの変換のパラメータを学習などによって最適にする方法が必要であると考える．

(52)

謝辞

本研究を遂行するにあたり, 研究生活において貴重かつ的確な御指導を賜わり研究を進めるにあたって最高の環境を与えてくださいました産業技術総合研究所デジタルヒューマン研究センターセンター長でありデジタルヒューマン学連携講座教授でもある金出武雄教授に対し, 心から感謝の意を表します. 研究方針について貴重なご指摘をいただきました本研究科木戸出正繼教授に深く御礼申し上げます. 奈良先端科学技術大学院大学で御指導いただき, また東京に着てからもお忙しい中御指導して頂きました本研究科小笠原司教授に深く感謝いたします. 研究方針, 論文執筆, 研究者としての考え方及び日常生活にいたる様々なサポートを主にして頂きました産業技術総合研究所デジタルヒューマン研究センター副センター長でデジタルヒューマン学連携講座准教授でもある加賀美聡准教授に深く感謝致します. 奈良先端科学技術大学院大学で研究方針についてご助言いただきました本研究高松淳准教授に深く感謝致します. 本研究の遂行にあたり様々な点において幅広い知識をもとに的確なご助言をくださった産業技術総合研究所デジタルヒューマン研究センター西脇光一氏に深く感謝いたします. デジタルヒューマン学連携講座の同期生として共に頑張った野村尚央君に心から感謝致します. 研究の進め方の研究に関する考え方や方針について有意義な助言をいただいた研究室 OB でトヨタ自動車の高岡豊氏に心から感謝します．研究の進め方の研究に関する考え方や方針について有意義な助言をいただいた博士後期課程 2 年の鈴木夢見子氏に心から感謝します．奈良先端科学技術大学院大学での学生生活から, 東京に来てからも大学との橋渡し役になってくれた君に荒木天外君に心から感謝いたします. 奈良先端科学技術大学院大学での楽しい学生生活をすごさせてくれたロボティクス講座の同期のみんなに心から感謝します. デジタルヒューマン研究センターでの研究生活でお世話になったチームの皆様に心から感謝します. 研究に関することはもちろん, それ以外でも大変にお世話になった産業技術総合研究所デジタルヒューマン研究センターの職員の方々, また他大学の学生の皆様に深く感謝致します. そして, 研究の様々な面で助言, 手助けしていただいたロボティクス講座のスタッフをはじめ, 諸先輩方, 後輩の皆様に心から感謝致します. 最後に, 好き勝手なことばかりしている私を陰ながら支えててくれた家

(53)

(54)

参考文献

[1] P.J. Besl and N.D. McKay. A method for registration of 3-d shapes. IEEE

Transactions on Pattern Analysis and Machine Intelligence, 14(2):239–256,

1992.

[2] PE Hart, NJ Nilsson, and B. Raphael. A Formal Basis for the Heuristic Determination of Minimum Cost Paths. Systems Science and Cybernetics,

IEEE Transactions on, 4(2):100–107, 1968.

[3] Y. Hosoda, S. Egawa, J. Tamamoto, K. Yamamoto, R. Nakamura, and M. Togami. Development of Human-Symbiotic Robot” EMIEW”-Design Concept and System Construction. JOURNAL OF ROBOTICS AND MECHATRONICS, 18(2):195, 2006.

[4] K. Konolige, SRI Int, and M. Park. A gradient method for realtime robot control. In Intelligent Robots and Systems, 2000.(IROS 2000). Proceedings.

2000 IEEE/RSJ International Conference on, volume 1, 2000.

[5] M. Montemerlo, N. Roy, and S. Thrun. Perspectives on standardization in mobile robot programming: the Carnegie Mellon Navigation (CARMEN) Toolkit. In Intelligent Robots and Systems, 2003.(IROS 2003). Proceedings.

2003 IEEE/RSJ International Conference on, volume 3, 2003.

[6] E. Rimon and DE Koditschek. Exact robot navigation using artiﬁcial poten-tial functions. Robotics and Automation, IEEE Transactions on, 8(5):501– 518, 1992.

[7] S. Thrun. Robotic Mapping: A Survey. Exploring Artificial Intelligence in

the New Millennium, 2002.

[8] S. Thrun, D. Fox, W. Burgard, and F. Dellaert. Robust Monte Carlo local-ization for mobile robots. Artificial Intelligence, 128(1-2):99–141, 2001.

(55)

[9] Sebastian Thrun, Wolfram Burgard, Dieter Fox, and (訳) 上田隆一. 確率ロボティクス. 毎日コミュニケーションズ, 2007. [10] 洋一下笹, 雄介菅原, 潔若林, 正則杉浦, 文夫小椎尾, 明博木村, 拓雄森口, 弘樹藤瀬, and 大剛末富. 1p2-n-036 屋外警備用ロボット「ガードロボ i」の紹介 (愛知万博ロボットの最先端技術, 生活を支援するロボメカ技術のメガインテグレーション). ロボティクス・メカトロニクス講演会講演概要集 , 2005:98, 20050609. [11] 大西献. ホームユースロボット「wakamaru」(家庭用・ペット・ホビー,[メカライフ特集] ロボット). 日本機械学会誌, 109(1051):448–449, 20060605. [12] 金原正朋, 加賀美聡, トンプソンサイモン, カフナージェームズ, and 溝口博. グリッドベース最短経路探索結果の障害物を考慮に入れた短縮化と平滑化. In ロボティクス・メカトロニクス講演会 2007 講演論文集, pages 2A1–D06(1)–(4),秋田, 5 2007. [13] 中宮正樹, 岸野泰恵, 寺田努, and 西尾章治郎. コストマップを用いた移動型センサノードの経路探索手法 (モバイルコンピューティング,¡ 特集¿ 新しいパラダイムの中での分散システム/インターネット運用・管理). 情報処理学会論文誌, 49(3):1374–1386, 2008. [14] 労働政策研究・研修機構編, editor. 労働力需給の推計労働力需給モデル (2007年版) による将来推計. Number 34 in JILPT 資料シリーズ. 労働政策 研究・研修機構, 2008.

(56)

付録

A. CARMEN Toolkit

A.1 概要

Carmenは CMU で開発された GPL ライセンスのロボットのツールキットである．移動ロボットに必要なマップ生成，自己位置同定，経路探索といった機能加えロボットのドライバーやシミュレータ環境が含まれている．2009 年 2 月段階での最新版は ver0.74 である．

A.2 インストール

A.2.1 インストール環境現在以下のディストリビューションで動作確認を行った．Debian 3.1 sarge Debian 4.0 etch Ubuntu 7.10 Ubuntu 8.04 Ubuntu 8.10

gccの ver4.1 以下を推奨する．ver4.2 以降の場合は-Werror オプションを外す．

A.2.2 必要パッケージ libgtk2.0-dev gdk-imlib11-dev libwrap0-dev libmagick++9-dev libmagic*-dev swig

(57)

pythonを使用する場合 python-all python-all-dev python-tcpwrap

python-cxx-dev

A.2.3 バグ

ジョイスティックパスの指定/src/joystick/joyctrl.h の 54 行目#deﬁne CAR-MEN JOYSTICK DEVICE ”/dev/js0”

#deﬁne CARMEN JOYSTICK DEVICE ”/dev/input/js0”

pioneer ドライバ/src/base/pioneerlib/pioneer lib˙c にバグオドメトリがオーバーフローによりリセットされる．

A.3 モジュール解説

central サーバーモジュール carmen に必要となるデータはここを介して各モジュールへ送られる． param deamon パラメータモジュール必要なデータ (マップ，ロボット・シミュレータのパラメータ等) を読み込む simulator シミュレータモジュール laser,pioneer とは排他的に起動すること laser レーザ距離センサのドライバ pioneer pioneer のドライバ localize 自己位置同定を行うモジュール． navigator パスプランニングを行うモジュール． robot ロボットの制御用モジュール

(58)

(59)

A.4 実行手順

A.4.1 シミュレーションでの実行 $ central

$ param daemon -r ROBOTNAME MAPFILE $ simulator $ localize $ navigator $ navigatorgui $ robot $ robotgui Fig. 39 navigatorgui A.4.2 実機での実行 $ central

$ param daemon -r ROBOTNAME MAPFILE $ laser

$ BASEDRIVER(使用するロボットのドライバー ex. pioneer) $ localize

(60)

Fig. 40 robotgui $ navigatorgui $ robot $ robotgui PCにジョイパッドをつないでおくと操作可能キーボードとマウスもでも操作可能

A.5 マップ作成

実機を実行手順を行ったのちに $ logger ¡ﬁle name.clf

*エンコーダとレーザのデータをとれている必要あり $ log2log

( )

修士論文

移動ロボットの速度と安全性を両立する経路探索のた

めの地図情報に関する研究

荒井 優輝

移動ロボットの速度と安全性を両立する経路探索のた

めの地図情報に関する研究

荒井 優輝

A study of map information for path planning

which combine velocity and safety

Yuki Arai

目 次

図 目 次

表 目 次

1.

序論

1.1

背景

1.2

関連研究

1.3

研究の目的

1.4

本論文の構成

2.

環境情報統合マップ

2.1

はじめに

2.2

背景となる地図生成，位置認識，経路計画手法

2.3

速度マップ

2.4

ソナーマップ

2.5

環境変化マップ

2.6

まとめ

3.

実験

3.1

実験環境

3.2

基本機能の実験

3.3

速度分布マップ実験

3.4

ソナーマップ実験

3.5

環境変化マップ実験

3.6

統合実験

4.

結論

謝辞

参考文献

付録

A. CARMEN Toolkit

A.1

概要

A.2

インストール

A.3

モジュール解説

A.4

実行手順

A.5

マップ作成

荒井優輝

荒井優輝

目次

図目次

表目次