ソナー情報を用いて経路生成を行うための幾何学手法に関する研究

Path generation by a geometrical method based on sonar
information
石井卓良、武田英明

Takayoshi Ishii, Hideaki Takeda
奈良先端科学技術大学院大学 情報科学研究科
Nara Institute of Science and Technology
In this paper, we proposed an environment recognition method with the sensor data of a real world agent
by using a geometrical method. We propose a geometrical method to generate a topological map thatconsists nodes as corners and diverging points, and arcs as paths between them. In our method, weﬁrstly remove the noise data from the points measured by the sonar of a real world agent. Secondly,
there points are transformed to B-Spline curves. Thirdly, we generate a polygon by connecting curves.
Forthly, we divide the generated polygon into triangles by using the Delaunay method. Finally,we candiscover the path by connecting each side of triangles in accordance with some rules. Then it can be usedfor environment recognition.

1

はじめに火災現場での救助を行なうロボット達を考える。
火災はどこで起きるか分からない。当然ロボット達が建物に入るのはその時が最初である。もちろん、建物の見取図などは手に入らない。建物にはロボッ
トが動きやすいようにマーカをつけてある訳でもなく、移動しやすいように整地されている訳でもない。環境がロボットに合わせるのではなく、ロボットが環境に合わせなくては行けない。また、災害救助を行なうようなロボットはマルチエージェントとして行動できなければならない。しかし、災害救助現場のような動的環境では、現在のロボット技術だけでは到底協調作業を行なうことはできない。マルチエージェントで災害救助を行なうとしたら、まず始めに必要なことは「手分けして生存者を発見する」ということだろう。これを行なうためには、エージェントが環境を理解でき、理解したものをエージェント間での知識共有が必要である。現在ロボットのソナー等を用いて、グリッドマップを作成する研究は数多く行われているが、グリッドマップ
では、環境を理解したことにはならない。この段階で作成された「地図」はただのデータであり、人間が見ればどのような環境なのか理解は可能だが、コンピュータに取ってみればただの点の集合であり、これを使って何かを行なうには不十分である。このような視点から、ソナーやレンジファインダーを用いて、実環境でマルチエージェントが活動できるために必要なことは、まず、環境中の経路図を理解できる形でもてるようにすることである。そこで本研
究では、移動ロボットのリアルタイムで環境認識を行なって行くためのシステムを構築し、その実験と評価を行った。

2

実環境中の特徴

人間が人に場所を説明する場合、「真っ直ぐ行って２つ目の角を右」や、「赤い看板の前」などのように、環境中の特徴となる部分とその相対的な関係のみを教えて説明する。また、地図を書いて場所を説明する場合でも、かなりいいかげんな地図を書いても相手に理解してもらえる。おそらく、人間の記憶している地図は、非常に曖昧でいいかげんな形をしているのであろう。環境中において、もっとも特徴的な部分のみを記憶し、それらがどのような順序で連結しているのかと言う形でも十分に地図の役割を果たす。実際の環境中の特徴は、分岐や曲り角であり、どのように連結しているかとは経路のことである。このように、環境中の特徴を連結したトポロジカルマップを作成することにより環境を理解することができる。

3

グリッドマップとトポロジカルマップ

本研究でグリッドマップを用いずにトポロジカ
ルマップを用いた理由は、トポロジカルマップは、前者に比べて以下の利点を持つからである。

• 3 次元に拡張可能• 経路計画が立てやすい• 計算機資源の節約• エンコーダエラーに強い
CMU RHINO[1][2] では、一度グリッドマップを作成し、それを用いて経路を作成しているが、グリッドマップにエンコーダエラーが入り、これを修正するために環境中を何度も往復してマップに修正を加えている。

特徴抽出

5

トポロジカルマップを作成する上で、環境中の特徴を認識する事が重要な課題となる。ここでは、ソナーとエンコーダによって得られたデータに幾何学的処理を加える事で、経路を抽出しトポロジカルマップを作成する。
手順としては、以下の要領で行う。

1. 一定時間内のソナー情報を得る。

4ソナーの欠点本研究では環境中特徴として、分岐や曲り角に着目しその抽出を行うに当たって最も利用しやすいソナーを使用した。他、使用するセンサーはエンコーダとコンパスとである。
カメラによる画像処理は用いない。カメラ画像のみで認識するには現在の技術では難しく、処理時間もかかってしまう。エッジ検出や領域分割等の技術はあるが、例えば机の上におかれた一枚の大きなポスターを考えた場合、これをポスターと認識することは現在は不可能だろう。材質を認識する方法がないからである。
対してソナーの欠点は、可能測定範囲の狭さ、精度の悪さが挙げられる。
音波は乱反射しにくいために、図 1のように壁に対して垂直以外の音波はまっすぐ跳ね返って来ないために測定できない。また、図 2のように複数回の反射によって、別のソナーが反応してしまい、結果としてそれがノイズとなることもある。
ソナーを用いる以上は、ノイズ除去を行う事が必要となる。

2. 測定点群からノイズを除去する。
3. 測定点群を曲線へと変換する。
4. 曲線上の点をサンプリングし直す。
5. 曲線同士を連結してロボットを中心とする多角形を作成する。
6. Delaunay 三角形分割を行う。
7. 多角形の辺と共有されない辺の中点同士を連結する。
8. 枝刈りを行う。
ロボットは ActivMedia 社の Pioneer2 を使用した。

5.1

ノイズ除去

一定時間ロボットを動かして測定されたソナー情報からノイズを少なくするために、前もって２つの処理を行う。
ソナーによる即定点は、重複して測定されることがあるため、ある程度以上近い点は統合しておく。

dij = |Pi − Pj |(1)

dij が一定値よりも小さければ、Pi と Pj は同じ測定点と見なして統合する。またソナーのノイズにより、障害物がない部分に測定点が現れる場合がある。この部分の除去を行うために以下の処理を行う。
図 1: 壁に対して斜めのソナーは反応しにくい

Ei = Σj f(|Pi − Pj |)(2)

関数 f(x) はガウス関数である。
このとき Ei が一定値以下ならば、Pi をノイズとみなしてデータから消去する。
以上の処理により、大きなノイズは除去される。
この部分は閾値処理を行っているため、ロボットの大きさ、移動速度、ソナーの精度を考慮したパラメータのチューニングが必要となる部分である。
図 2: 複数回の反射によるノイズ

5.2点群連結

点群を連結し、B-Spline 曲線化する。ある点 Pi0に対して距離が一定値以下の最近傍点 Pi1 を見つけ出し連結する。次に Pi1 に対して Pi0 を除く最近傍点を見つけ、連結する。最近傍点までの距離がこの作業をすべての点 (すでに連結された点を除く) に対して再帰的に行うことで、点群を連結した線に変換し、整列する。
この時、ベクトル Pin −Pi(n+1) とベクトル Pi(n+1) −Pi(n+2) との内積を計算し、ある程度以上である場合のみ連結を行うルールを加える。これにより、連結する方向を限定してやる (図 3)。

図 3: 内積判定で除去を行った図
このままでも十分利用できる形になってはいるが、測定点が多いと以下の処理が重くなり、また、ソナー特有のノイズが入っているため、これを除去する意味でも、連結した点群を、B-Spline 曲線に変換する。
B-Spline 曲線化することでノイズを除去し、また曲線から一定間隔ごとに点を取り出し、点群を減らす (図 4)。

図 5: 多角形化した様子の直線が交わる」ということから、この点では、元の点 3 つからの距離が等しいとして、三角形を作ってゆく。
このようにして作成された三角形は、三角形の最小角の和が最大になるという性質がある。このため、つぶれた三角形が生成されにくい。
以上の手法を用いて、整った三角形を作成する。
三角形の重心が、多角形の中になければ不要な三角形として削除する。
判定方法は、三角形の重心から充分遠くまで線分を引き、多角形の各辺との交差判定を行なう。交差回数が奇数であれば内側、偶数であれば外側となる。
Delaynay 分割を行い、内外判定により多角形外の三角形を除去した様子を図 6に示す。

図 4: B-Spline 化

5.3

多角形化

点群が減り、複数本の線分が抽出されているので、線分の端点同士を連結し閉じた多角形を作成する (図 5)。
連結ルールは基本的に最近傍との連結だが、同じ線分同士との連結は優先度を下げる必要がある。
また、連結して作成された線分と、他の線分が交差した場合は、次の候補と連結するようにする。
この多角形は、次の Delaunay 分割時に外側の三角形省くための内外判定用に使用する。また、ここで連結した時に作成された線分で、ロボットの大きさよりも線分のほうが大きいならば、そこはロボット通過可能のフラグを立てておく。

5.4

Delaunay 分割

作成した多角形を Delaunay 三角形分割する。
Delaunay 三角形分割は、ボロノイ多角形を元にして、各点を結ぶ三角形メッシュを作る手法である。ボロノイ多角形の性質「多角形の頂点では 3 つ

図 6: Delaunay 分割

5.5

経路抽出

Delaunay 分割によって得られた三角形の各辺の中点を次のルールにしたがって結ぶことにより経路が抽出される。
• 多角形の辺を構成する辺には線を引かない。
ただし、5.3 で多角形化した時に追加した辺で、かつロボットの大きさより大きい部分は、辺の中点に向かって線を引く。
• 三角形のすべての辺が多角形を構成しない辺であれば三角形の重心から線を引く。

• 2 辺以上が多角形の辺 (5.3で多角形化した時に追加した辺は除く) と共有されている三角形は取り扱わない。
ただし、この方法だけでは、角となっている部分にも経路が引かれてしまう場合がある。図 7のように角を認識しなければならない場所に経路が伸びてしまう。これを除去するためには、検出された経路の端点同士を線分で結び、一定値以上であれば多角形の外周と交差するかを判定する。交差したならば経路として残し、交差していないならば、取り除く。

6

実験

図 9がロボットの周囲の環境であり、図 10が得られたソナー情報、図 11が認識された経路である。
ロッカー (図 9の B) があり、その前に壁の開けたところ (図 9の A) がある環境での実験を行った。
通路の幅は実験 1 と同様に約 2m である。
A を通りすぎたので、その部分が分岐点 (図 11cross) として確実に認識されて事が分かる。また、ロッカーの影響は少し径路がカーブする程度の影響を受けるが、処理上は何の問題もない。
長い廊下なので、ロボット前後には径路が続いておいるが、径路の端点がそれぞれ外周多角形に接しているので、この場合どちらも行き止まりではないことが分かる。
ソナー情報には細かいノイズが多少混じっているが、作成された径路はその影響を受けていない。
この結果から、この環境には一つの分岐点が有り、それぞれ径路の先は行き止まりではないという分析が可能である。

A
図 7: 枝苅り前の経路

BN

図 9: 実験 2 実際の環境

図 8: 枝苅り後の経路以上の操作により経路が抽出される。図 8は、経路が抽出された様子であり、コーナーと T 字路が検出されている。実際の環境は、T 字路に近い形をしているが、右側はすぐ行き止まりとなっている。
しかし祖の部分はセンサーの範囲外であるので検出されていない。ロボットは右に行こうとして始めてそこが行き止まりであると言うことを認識する。このまま左に曲がってロボットが進んだ場合は未探査の経路として扱われることとなる。
また、実際の環境では角は直角だが、多角形化した段階では、ノイズやエラーの影響で直角にはなっていない。しかしながら、２次元のグリッドマップを作るのであればこれは深刻な問題であるが、トポロジカルマップを作成する上ではまったく問題がない。
実際にロボットを動かしながらトポロジカルマッ
プを作成して行く場合は、現時点での経路と、一時点前の経路の端点の近いもの同士を連結することで大きなトポロジカルマップを作成して行く。

図 10: 実験 2 ソナー情報

図 11: 実験 2 認識された経路

7

考察

ソナー情報から環境中の局所的な経路を推定したが、経路情報は、内部的にはどこでどのように連結しているかを格納しており、局所的な情報をトポロジカルマップに変換することも可能となっている。
ソナーでは散乱した部屋の認識に限界があるた
め、代わりにレンジファインダーを用いても良いだろう。
トポロジカルマップを作成するためには、随時更新されていく経路に変化が生じた場合 (通路が T字路になった場合など)、そのトポロジカルマップに追加更新を行えば良い。
このシステムでは、ソナー情報を得る部分と経路を推定する部分は独立しており、推定はオフラインで行っているためロボットを動かしながら経路を随時作っていくことはできない。このためロボットに即座に組み込むことができない。移動ロボットへの組み込みを行うためには、ソナーやエンコーダ情報を受け取る部分と認識部分を統合する必要がある。
また、従来の Volonoi 図のみを用いた手法と比較した場合、経路がきれいに表示される点と、枝がでないという点において優れている。

8まとめ

本研究では、「災害救助で活躍できるようなロボット」という視点からマルチエージェントで災害救助を行えるロボットにとって最低限必要である局所的な経路を認識するための一法と、それを接続したトポロジカルマップによる環境のモデル化を提案した。また、ソナーだけでもある程度のノイズまでなら環境を認識できることを示した。
本研究で想定する環境では、高精度で緻密なグリッドマップを作り上げて行くよりも、雑ではあるが認識速度に優れ、エラーに対する強靭である事が要求される。オフィスロボットとの大きな違いは日々蓄積される情報を重視するのではなく、一番最初に得た情報だけで環境を認識することを重視している事である。
より汎用性のあるロボットを作成するためには環境の抽象化が大きな課題となる。トポロジカル
マップの経路の抽象化は有効であるが、複雑な実環境に真に対応するためには、経路の抽象化ばかりではなく、他のセンサーを駆使してロボットを取り巻くさまざまな部分の抽象化と認識が必要である。

参考文献[1] S. Thrun and A. Buecken: Learning Maps for Indoor
Mobile Robot Navigation, tech. report CMU-CS-96121, Computer Science Department, Carnegie Mellon
University, 1996.
[2] S. Thrun, A. Buecken, W. Burgard, D. Fox, T.
Froehlinghaus, D. Henning, T. Hofmann, M. Krell,and T. Schmidt: Map Learning and High-Speed Navigation in RHINO, AI-based Mobile Robots: Case Studies of Successful Robot Systems, Kortenkamp, D.
and Bonasso, R.P. and Murphy, R., ed., MIT Press,
1998.
[3] 松井俊浩: オフィスロボット Jijo-2, 工業技術、1999.4[4] T.Matsui, H.Asoh, I.Hara, and N.Otsu,: An event driven architecture for controlling behaviors of theoﬃce conversant mobile robot, Jijo-2, Proceedings ofthe 1997 IEEE International Conference on Robotics
and Automation (ICRA’97), pp.3367-3371, Apr. 1997.
[5] 麻生 英樹, 木村陽一, 松井 俊浩, 速水 悟, 原 功 対話ベース
学習によるオフィス環境での自律ロボットナビゲーション
人工知能学会研究会資料 SIG-J-9501-7, 1995-12.
[6] 重点領域研究「知能ロボット」: 日本ロボット学会誌,Vol16
No5, pp578-585 1998
[7] 山田 誠二, 室田 盛道: 自己組織化マップを用いた移動ロ
ボットによる行為系列からの環境認識, 日本ロボット学会
誌 Vol.17 No6,pp.855-862,1999[8] 石岡広治, 開一夫, 安西祐一郎: 複数の自律移動ロボットの固体差を考慮した地図獲得システムの設計と実装, 日本ロボット学会誌, vol.12, no.2, pp.282-290,1994.