ESOMを用いた自律ロボットにおける実時間トポロジカル地図 構築法の提案

SOM2009-08
ESOMを用いた自律ロボットにおける実時間グラフベース地図の構築
ESOM を用いた自律ロボットにおける実時間トポロジカル地図
構築法の提案
† ○古賀公次郎，‡ 徳永憲洋，‡ 古川徹生
†[email protected]， ‡{tokunaga, furukawa}@brain.kyutech.ac.jp
†‡ 九州工業大学大学院 生命体工学研究科
2009 年 3 月 10 日
1
る [2]．また Martinetz は TRN によってグラフベース
はじめに
の地図を自己組織的に形成できることを示している [3]．
オフィスや家庭内で自律的に動き回るロボットは， しかし，これらの手法はロボットが作業空間をまんべ
自ら作業環境を探索しながら地図を作成し，地図を基 んなく探索した後にオフラインで地図を作成する必要
に自律的に経路計画（セルフナビゲーション）できる
がある．探索しながらオンライン学習で地図を作成し
必要がある．さらに，模様替えや障害物の出現などの た場合，学習途中の地図を利用できない．また，学習
環境の変化に対応して地図を修正できる能力も不可欠 が終了した後に環境が変化した場合に地図を修正する
となる．
ことが困難である．
経路計画や自己位置同定を行うための地図として，
これに対し本研究で我々は，以下に示す（１）∼（４）
作業環境をグラフベースで抽象化した地図がよく用い の条件を満たす地図構築手法を提案する．
られる．つまり作業環境の局所領域をノードで表し，
ノード間を結ぶパスが局所領域間の経路を表わす．こ (1) ノードが担当する局所領域，パスを張る経路を自
己組織的に把握することが可能．
のグラフベースの地図は作業環境の地理的トポロジー
を保存するために一般的にトポロジカル地図と呼ばれ
(2) 実時間かつオンラインでの地図構築が可能．
ている．またノードは作業環境の局所領域を量子化し
(3) 学習のどの時点においても過去に通った場所に障
ていると考えることができ，グラフ全体では抽象化さ
害物をよけながら移動することが可能．
れた作業環境を表わす．作業環境をグラフベースに抽
象化することで，計算コストやメモリコストなどを抑
(4) 永久的な学習を可能とし，環境が変化してもいつ
えることができるだけでなく，ロボットの姿勢や行動
でも学習によって地図を修正できる．
の制御も単純化することができる．
具体的には，地図生成に Kasavob らが提案した進化型
グラフベースの地図で問題となるのが，どこの局所
SOM（Evolving SOM: ESOM） [6] を用いる．ESOM
は SOM を成長型ネットワークに拡張したものであり，
領域をノードで表現するか，どことどこの局所領域間
にパスを張るか，である．最も簡単な方法は設計者側
学習過程においてノードを増やす機能とノード間の
がノードにランドマークを設定し，ランドマーク間の
経路をパスとして与える方法である．しかしこれでは，
ロボットは自律的な地図作成を行えないし，環境の変
パスを動的に張る機能を持っている．ESOM は Grow-
ing Cell Structure（GCS） [4] や Growing Neural Gas
（GNG） [5] と同じようにグラフを成長させる機能を
化に対して地図を修正することも困難である．一方，
持っている．しかし，GNG や GCS に比べて ESOM
自動的にかつロボットが学習しながら地図を構築する
には，演算が高速なオンライン学習アルゴリズムであ
方法として，自己組織化マップやニューラルガス，あ
る，永久的に学習をし続けることが可能，といった利
るいはそれらに準ずる教師なし学習アルゴリズムを用
点がある [6]．これらのことから，上記条件を満たす地
いる方法が提案されている．伊達らは SOM と NG の
図作成においては GNG や GCS に比べて ESOM のほ
直積モデルを用いることで自己位置と姿勢の推定を行
うが適していると考えている．
うグラフベースの地図を構築している [1]．また田中ら
我々は，TRN，GNG，ESOM を用いた地図作成シ
は NG によって自己位置推定が行える地図を作成し，
ミュレーションを行い，ESOM は上記条件を満たす地
さらにノード間の経路を強化学習を用いて形成してい
図作成が可能であることを示した．また実機実験によ
- 39 1
第10回自己組織化マップ研究会2009 講演論文集 （2009年3月10日 名古屋大学）
Technical Reports of 10th Annual Meeting of Self-Organizing Maps in JAPAN 2009, March 10th 2009 at Nagoya University
り ESOM を用いたセルフナビゲーションも行った．本
（II-A）ユニットの追加
発表ではシミュレーションの結果と実機実験による結
K + 1 番目の新規ユニットの追加を以下の式で行う．
果を報告する．
wK+1 = x
2
ESOM について
2.1
（II-B）リファレンスベクトルの更新
アーキテクチャ
リファレンスベクトル wk は以下の式で更新される．
ESOM はグラフ構造を持つネットワークを成長させ
ただし勝者ユニットに結合されているユニットのみ更
ることで, 観測データベクトルのトポロジーを表現す
新を行う．
る能力を持つ．これにより入力の規模が未知であった
りトポロジーが変化しても対応することができる．ま
wk
た，オンライン学習のアルゴリズムであり観測データ
Δw k
ベクトルが入力される度にユニット（ノード）の追加
あるいは学習，およびパスの構成が行われるため，動
= w k + Δw k
ak (x)
(x − wk )
= k
k a (x)
(5)
ここで γ は学習率であり 0 < γ ≤ 1 である．また，
的な環境における観測データベクトルの分類や量子化
ak (x) は k-th ユニットの x に対する活性値を表し，以
下の式で定義される．
が可能である．
2.2
(4)
ak (x) = e−2x−w
アルゴリズム
k 2
/ε2
(6)
ESOM のアルゴリズムは大きく分けて，
（I）評価，
（II-B）リファレンスベクトル
（II-A）ユニットの追加，
（III）パスの強度更新
の更新，
（III）パスの強度更新，
（IV）パスの刈り込み
k, k -th ユニット間のパスの強度更新は以下の式で
定義される．
の 4 つのプロセスから成る．図 1 にアルゴリズムの流
れを示す．次に各プロセスごとの説明をする．
sk,k = (1 − β)ak ak + βsk,k
（I）評価
0 < β < 1.0
(7)
β は忘却定数であり，通常 0.8 程度に設定しておくと
よい．上式に従い勝者ユニットと勝者ユニットに結合
今，このネットワークにおいてデータベクトル x が
入力されたとする．このとき以下の式により各ユニッ
トのリファレンスベクトル wk とデータベクトル x の
しているユニットの間の結合強度を更新する．ただし，
（II-A）プロセスで新規ユニットを追加した場合は，新
規ユニットと k ∗ および k ∗2 間のパス強度だけを更新
距離 dk を評価する．
dk = wk − x
する．この場合は式（7）の右辺の sk,k は 0 とする．
∀wk ∈ W = {w1 , ..., wK }
(1)
すべてのユニットに対して dk > ε が成り立つならば
（IV）パスの刈り込み
（II-A）のプロセスに進みユニットを新規追加する．成
数ステップに一度の割合で最も強度の弱いパスを刈
り立たないならば（II-B）のプロセスに進み，リファ
りこむ（削除する）．
レンスベクトルの更新を行う．ここで ε は距離の閾値
を示す定数である．K = 0 ならば，
（I）のプロセスは
以上の 4 プロセスを繰り返すことで ESOM の学習
通らず（II-A）のプロセスに進む．
は進む．
また，x に対して最も距離の近いリファレンスベク
トルを実現しているユニットを勝者ユニット k ∗ ，2 番
目に距離の近いユニットを第 2 勝者ユニット k ∗2 とす
る．つまり，
k∗
=
arg min dk
∀k
(2)
k ∗2
=
arg min dk
∀k ∈
/ k∗
(3)
k
k
- 40 2
SOM2009-08
ESOMを用いた自律ロボットにおける実時間グラフベース地図の構築
(I)
⹏ଔࡊࡠ࠮ࠬ
(II-B)
(II-A)
ᦝᣂࡊࡠ࠮ࠬ
㧔ࡕࠫࡘ࡯࡞㧕
ㅊടࡊࡠ࠮ࠬ
(III)
ᦝᣂࡊࡠ࠮ࠬ
㧔ࡄࠬߩᒝᐲ㧕
(IV) ࡄࠬߩ೥㒰
㓚ኂ‛
図 1: ESOM のアルゴリズムの流れ
ࡠࡏ࠶࠻
10cm
図 3: Webots で作成した作業環境
4
シミュレーションによる TRN，
GNG，ESOM が構築する地図の
比較
4.1
枠組み
本シミュレーションの目的は TRN，GNG，ESOM
が構築する地図を比較することである．シミュレーショ
ンにはロボットシミュレータ Webots（Cyberbotics 社
図 2: Khepera
製）を用いる．図 3 に Webots で作成した仮想作業空
3
間を示す．この作業空間上にてロボットを動かしなが
問題設定
ら，作業空間の地図を TRN，GNG，ESOM で各々作
本研究で用いるロボットは小型移動ロボット Khep-
成する．
era(図 2) である．我々は Khepera に搭載されている
詳しい枠組みについて説明する．ロボットはランダ
視覚センサや距離センサを用いてオンラインでグラフ ムウォークで動かす．そして 1 ステップの行動毎に観
ベースの地図作成することを想定している．しかし， 測された GPS 情報が ESOM，TRN，GNG に入力さ
本研究の位置付けは ESOM による地図作成の有効性 れる．具体的にはロボットの行動ステップ t において
を示すことである．よって本研究では以下のように問 入力される GPS 情報は作業環境平面における 2 次元
題を設定する．
座標 x(t) = (x(t), y(t)) である．ロボットは 20000 ス
テップまで動かす．
1. 作業環境におけるロボットの正確な位置は GPS
等を用いることで把握できる．
4.2
2. ロボットの探索行動はランダムウォークあるいは
人間がコントロールする．
結果と考察
図 4（a）（
，b）（
，c）にそれぞれ TRN，GNG，ESOM
における地図構築結果を示す．各図ともに，ロボット
3. ナビゲーション時は構築したマップのみを利用し
の行動ステップ t = 1, 500, 2000, 20000 時において，
て行う．
各ネットワークが作成した地図を表示している．まず
また 2 における探索行動においてランダムウォークを TRN と GNG の結果（図 4（a），
（b））について述べ
させる場合は，ロボットにはあらかじめ壁を避ける行 る．t = 1 において TRN は，リファレンスベクトル
動アルゴリズム（例えば Braitenberg の壁避けアルゴ
の初期化がランダムに行われた状態からスタートする．
リズム [7]）を搭載させておく．
また GNG のネットワークは，t = 1 においてユニット
- 41 3
第10回自己組織化マップ研究会2009 講演論文集 （2009年3月10日 名古屋大学）
Technical Reports of 10th Annual Meeting of Self-Organizing Maps in JAPAN 2009, March 10th 2009 at Nagoya University
図 4: TRN, GNG，および ESOM による地図構築の結果．
（a）TRN，
（b）GNG，
（c）ESOM．
は 2 個から始まる（2 個のリファレンスベクトルの初
図を利用しセルフナビゲーションすることはできない．
期化はランダム）．TRN，GNG ともに t = 500, 2000
一方，ESOM は学習の途中過程においても作業環境の
を見ると，オンラインで GPS 情報が入力されるたびに
経路が表現されている．このことから，ESOM はオン
マップが広がっているのがわかる．しかし，障害物のあ
ラインでの地図構築に適することが示唆できる．
る場所にリファレンスベクトルが配置されたり，パス
が通ったりしているのがわかる．十分にロボットが行
動した t = 20000 の時点では作業環境の経路が TRN，
GNG の両方のネットワークで表現できていることが
5
実機実験
5.1
わかる．
次に ESOM の結果（図 4（c））について述べる．
枠組み
本実機実験では ESOM による地図構築と地図を用
t = 1 において ESOM は，ユニットが１個から始まる． いたセルフナビゲーションを行った．また環境が拡張
また t = 500, 2000 を見ると，ロボットが移動した経 しても，ESOM はネットワークを拡張することで対応
路に沿ってネットワークが構築されているのがわかる． が可能であることを確認した．実験環境を図 5 に示す．
t = 20000 の時点では，TRN，GNG と同じように作 実機ロボットはスイス連邦工科大学のマイクロ・エレ
クトロニクス研究所が作成した Khepera を使用した．
業環境の経路がネットワークで表現できている．
以上の結果を踏まえ考察をする．TRN，GNG は十
作業環境の上部に USB カメラを置き，ロボットの位
分に学習データが与えられれば，作業環境の経路を表 置・向き検出に使用した．カメラから観測された画像
例を図 5 右下に示す．ここでカメラ画像からロボット
現できる地図が構築される．しかし，学習の途中過程
においては障害物のある場所にユニットが配置された の位置・向き推定は，ロボットにつけておいた半円の
りパスが通ったりする．そのため学習途中において地 青と赤の色の割合を利用した．ESOM には推定された
- 42 4
SOM2009-08
ESOMを用いた自律ロボットにおける実時間グラフベース地図の構築
䉦䊜䊤
ᜰ઎
䊨䊗䉾䊃䈱
૏⟎䈫ⷺᐲ䉕ᬌ಴
䉶䊮䉰ᖱႎ
PC
䊨䊗䉾䊃
䉦䊜䊤↹௝
㓚ኂ‛
ࡠࡏ࠶࠻ߩ૏⟎ࠍ⴫ࠊߔ‫ޕ‬
౞ౝߩ✢ߪࡠࡏ࠶࠻ߩะ޿ߡ޿ࠆᣇะࠍ⴫ࠊߔ‫ޕ‬
図 5: 実験環境の概念図
⊕޿ㇱಽߪ㓚ኂ‛ߢ޽ࠆ‫ޕ‬
位置（2 次元座標）が入力され，それを基に地図を構
図 6: 拡張前作業環境：地図構築中のロボットの行動
築する．
軌跡
次にセルフナビゲーションの枠組みについて説明す
る．ナビゲーション時には ESOM の構築したグラフ
ネットワークを利用し，現在位置と目標位置に近い勝
者ユニットを決める．次にそれぞれの勝者ユニット間
をダイクストラ法を利用して最短経路を決定する．こ
の最短経路を利用してナビゲーションを行う．ノード
からノードへの移動は，ノード間の角度を利用してロ
ボットの向きを決定し行動を生成する．
実験は拡張前の作業環境（図 6）と拡張後の作業環
境（図 7）の 2 種類の環境で行う．まず拡張前の作業環
境でロボットを人間側がコントローラで操作しながら
地図を構築しセルフナビゲーションの検証を行う．こ
のときの地図構築中におけるロボットの軌跡を図 6 に
図 7: 拡張後作業環境：地図構築中のロボットの行動
示す．その後，拡張前の作業環境で学習した ESOM の
軌跡
ネットワークをそのまま利用して拡張後の作業環境上
で地図を構築しセルフナビゲーションを行う．このと
きの地図構築中におけるロボットの軌跡を図 7 に示す．
これにより作業環境の拡張にも ESOM は対応できる
ことを示す．
5.2
結果と考察
図 8， 9 に作業環境の拡張前と拡張後におけるナビ
ゲーションの結果を示す．結果よりロボットは現在地
から目標地までセルフナビゲーションすることができ
た．また作業環境が拡張してもロボットは地図を作る
ことができ，またセルフナビゲーションすることが可
⋡⊛࿾
能だった．
಴⊒࿾
図 8: 拡張前作業環境におけるセルフナビゲーション
結果
- 43 5
第10回自己組織化マップ研究会2009 講演論文集 （2009年3月10日 名古屋大学）
Technical Reports of 10th Annual Meeting of Self-Organizing Maps in JAPAN 2009, March 10th 2009 at Nagoya University
⋡⊛࿾
[5] B. Frizke, “A Growing Neural Gas Network Learns
Topologies,” Advances in Neural Information Processing Systems, Vol. 7, pp. 625–632, 1995.
[6] D. Deng, N. Kasabov, “On-line pattern analysis
by evolving self-organizing maps,” Neurocomputing,
Vol. 51, pp.87–103, 2003.
[7] V. Braitenberg, “Vehicles: Experiments in Synthetic
Psychology,” The MIT Press, Cambridge, MA, 1984.
಴⊒࿾
図 9: 拡張後作業環境におけるセルフナビゲーション
結果
6
終わりに
本研究では ESOM がグラフであらわされた地図をオ
ンラインで構築するのに適していることをシミュレー
ションおよび実機実験で示した．ESOM は永久的に学
習することができるため，作業環境が拡張しても常に
グラフネットワークの修正学習が可能である．この特
性は家庭やオフィスのように常に環境が変化する場所
において非常に実用性が高くなる．しかし，今回の実
験ではロボットの位置や向きが既知であることを前提
として ESOM を利用している．今後の研究では距離
センサや視覚センサのみから地図構築及びセルフナビ
ゲーションができるように改良を加える．
参考文献
[1] 伊達章，倉田耕治，“SOM とニューラルガスの直積モデ
ルによるロボットの位置と向きの情報の分離”，電子情報
通信学会論文誌，Vol.J87-D-II，No.7，pp.1529–1538，
2004.
[2] 田中敏雄，西田健次，栗田多喜夫，“場所細胞の位置
マップと強化学習を用いた移動ロボットのナビゲーショ
ン”，電子情報通信学会論文誌，Vol.J88-D-II，No.9，
pp.1866–1875， 2005.
[3] T. Martinetz, K. Schulten, “Topology Representing
Networks,” Neural Networks, Vol. 7, NO. 3 pp. 507522, 1994.
[4] B. Fritzke, “Growing Cell Structures - A Selforganizing Network for Unsupervised and Supervised Learning,” Neural Networks, Vol. 7, No. 9, pp.
1441–1460, 1994.
- 44 6