計測自動制御学会東北支部 第 218 回研究集会 (2004.10.9)
資料番号 218-3

トポロジカルマップを用いた自律移動ロボットのナビゲーション
Navigation of the Autonomous Mobile Robot Using theTopological Map○中嶋崇夫，大久保重範，及川一美，高橋達也○ Takao Nakajima, Shigenori Okubo, Kazumi Oikawa, Tatuya Takahashi
山形大学

Yamagata University
キーワード : トポロジカルマップ (topological map)，自律移動ロボット (autonomous mobile robot)，ナビゲーション (navigation)，ランドマーク (landmark)，グラフ (graph)

連絡先 : 〒 992-8510 山形県米沢市城南 4-3-16
山形大学 工学部 機械システム工学科 大久保研究室
中嶋崇夫，Tel.: (0238)26-3245，Fax.: (0238)26-3245，E-mail: g03129@dipfr.dip.yz.yamagata-u.ac.jp

1.

緒言

2.

作業環境

本研究ではトポロジカルマップをもとに，ロボッ

作業環境は，通路と転回点によって構成された街トをナビゲーションすることを目的としている．のような通路状環境(1) である．通路の行き止まり

普段我々が，荷物を搬送する時やお使いに行くと転回点には識別を容易にするためにランドマー

時などに，目的地への行き方がわからない場合はクが用意され，整備された環境となっている．環地図を見るなり人に道を聞くなりして仕事をこな境を整備することによって，低級な認識技術でもしている．ロボットに同様のことを行わせようと環境を識別することが可能となるが，その手間がすると，環境や経路を絶対座表現で与えなければ利用者の大きな負担となればこの研究の意義がなならず，正確な地図が必要となる．しかし，人間くなってしまう．そこで，本研究では作業環境にの場合は誰かに簡易な地図を描いてもらい，それはランドマークのみを設置することとした．

をもとに目的地にたどり着くことができる．同様に，簡易な地図をもとにし，ロボットを目的地へのナビゲーションすることが本研究の目的である．

3.

自律移動ロボット

3.1

アプローチ方法

自律移動ロボットとは，センサ情報から環境を知覚し，それに応じて行動を選択し環境とインタ{1{ラクションをとる機械である．自律移動ロボット

うに，両方の特徴を利用するべきであると考えてを実現するためには，以下のようなアプローチ方いる．

法がある．

4.

è Model-Based Robotics

環境地図獲得手法

ロボットに対して環境を記号や形状などで人間が誰かにお使いを頼むようなときは，目的地表現したモデルを与え，このモデルに基づいまでの簡易な地図を描いてこれを相手に渡すことてプラニングし行動を選択するという方法でによって目的地までの道のりを教えている（Fig.1）．

ある．モデルを精度良くつくることが難しい

本研究の環境地図獲得方法では，人間が普段簡単などの問題もあるが，正確なモデルを与えるに道の教示を行っていることに着目し，この方法，ことが出来れば効率よくナビゲーションを行

つまり簡易な地図による教示を利用して，自律移動うことができる．

ロボットへ環境地図を与えることを考えた（Fig.2）．

è Behavior-Based Robotics(2)OKModel-Based Robotics と対する方法で，環境を内部にモデルとして持つことはしない．
この方法は，センサ情報に対する反射的な行動を単位としており，この反射行動に切り替え可能な階層構造を持たせ，行動決定規則とFig. 1

Human to Human

している．内部モデルによるプラニングを行わないため，ロボットがすばやく行動を起こOKせ，また行動規則を追加することが出来るた
めに拡張が容易という特徴がある．

3.2

本研究での立場

本研究では，環境地図が必要であるという立場

Fig. 2をとる．単に，壁に当たらずに動き続けるロボッ

Human to Robot

トを作るのであればモデルは必要ないが，本研究で考えている問題は，目的地到達問題であるため

4.1

お使いタスクの実現

地図は必要である．しかし，自律移動ロボットのユーザーへの負担を減らすには環境地図自動生一般社会への普及を前提としているので，環境地成手法がある．しかし，この手法は地図を獲得す図は誰にでも作成可能な簡易なものでなくてはなるためにタスクをこなす前に作業環境内を少なくらない．

とも一度探索する必要がある(3) ．ロボットが作業

また，本研究では，簡易な環境地図を持つことをする環境が工場やオフィスのように固定され，長前提としているが，Behavior-Based Robotics の考

時間地図を作り直す必要が無い場合はこの方法でえ方も取り入れている．衝突回避などに対しては，問題ないと思われるが，ユーザーの求めるお使い

Behavior-Based Robotics の手法を取り入れ，効率のようなタスクには対応することが出来ないと考のよい経路計画は Model-Based Robotics というよえられる．つまり，お使いのように目的地が次々と{2{変化し，しかも，目的地まで一度到達すればよい

Step 2. ID 設定
ランドマークに識別番号（ID）を与える．というタスクに対しては，長い時間をかけて探索により環境地図を作成するということがユーザー

Step 3. グラフ探索の意に反するからである．

4.2

ノードオブジェクトを展開して目的地をトポロジカルマップ教示型による特徴探す．

Step 4. 経路計画

従来の環境地図獲得手法では，ユーザーへの負出発地から目的地までの経路を計画する．

担の大きさが問題となっていた．しかし，本手法ではトポロジカルマップに着目することにより，専5.2

ノードオブジェクトの生成

門知識を必要とせず，あたかも人間に地図を教え生成したノードオブジェクトを qi とし，隣接するかのようにロボットへ地図を教示することが出るノードオブジェクトを代入する配列 direction を来る点が優れていると考えられる．また，自動生用意する．配列要素数は 4 で，隣接ノードオブジェ成型での環境地図獲得方法では，お使いタスクにクトがどの方向にあるかによってどの配列要素に対応する難しさが問題であった．しかし，本手法代入するかを以下のように決める（Fig.3，Table

では教示型であるためすばやくロボットへ地図を1）．

与えることが出来，このことからお使いタスクをN[3]実現することが可能となる．

90°

本研究のメリット・重要性をまとめると次のよ90°

90°

うになる．

[2]
è 専門知識を必要とせず簡単に利用すること

qi[0]90°[1]が出来る

Fig. 3

è すばやく環境地図を作成することが出来る

Node Object

è お使いタスクに対応することが出来る

5.

インターフェイス

5.1

処理の流れ

Table 1 Adjacent Node Object
隣接ノードの方向
配列要素

ここでは，ユーザーが描く地図からトポロジカ
ルマップを生成し，ナビゲーション経路を計画すEAST

direction[0]

SOUTH
WEST
NORTH

direction[1]direction[2]direction[3]るまでの処理手順について述べる．
以上の操作により，グラフが完成する．

Step 1. ノードオブジェクトの生成
出発地や目的地を含むノードオブジェクト

5.3を生成する．ノードオブジェクトにはランドマークが配置される．

ID 設定

ランドマークに識別番号（ID）を与える．本研
究では環境の中でランドマークが ID を発信し，ロ{3{ボットがそれを受信することにより自己位置同定

Step 6. trace に qe が格納されたら探索終了．そうでなけば Step 4 へ．

を行っている．

5.4

グラフ探索

5.5

グラフ探索でよく用いられる幅優先探索を利用した．特徴としては，

経路計画

グラフ探索アルゴリズムの Step 5 に以下のアルゴリズムを追加する．

è 解があるならば，必ず解を見つける

trace と queue の両方に格納することが出来た A(qo )è 複数の解がある場合は，最も浅いゴールを最を C(qo ) とし，qo を親ノードオブジェクトとする．

初に見つける以上により，目的地から出発地まで親ノードオなどがあげられる．簡易な地図を利用するため，ブジェクトを辿れば経路を計画することが出来る．

ノードの深さは問題にならないと考えられる．

6.

ナビゲーション方法

ナビゲーション方法は以下の通りである．

Step 1. 環境地図と経路をロボットに与える．
Step 2. 現在向いている方向を次のランドマークのある方向と設定・記憶し，その方向へ前進

Fig. 4する．

Graph Search

Step 3. ランドマークの ID を認識した時に，計画ランドマークに ID が設定された（Fig.4）後，グ通りの ID か確認する．

ラフ探索を行う．アルゴリズムは以下の通りであStep 4. 環境地図により，次に向かうべきランドる．

マークの方向へロボットが向きを変え，Step

Step 1. グラフを表す隣接ノードオブジェクト関

2 へ．もし目的地ならナビゲーションは終了．

数を A とする．また，出発地と目的地を決め，出発地を qs ，目的地を qe とする．

7.

Step 2. 辿ったノードオブジェクトを格納していく配列 trace と待ち行列 queue を用意し，それらを空にする．

シミュレーション結果

シミュレーションにて本手法の実現可能性と有用性を検証する．作業環境として Fig.5 に示すものを与え，ランドマークは天井に配置されているもStep 3. qs を trace と queue に格納する．のとし，ID は 16 進数にて与えた．出発地は ID7 で，Step 4. queue から一番古いノードオブジェクト

目的地は ID5 である．

qo を取り出す．
Step 5. A(qo ) に属するノードオブジェクトで，traceに入っていないものがあれば，それらをすべて trace と queue の両方に格納する．

{4{の問題をいかに解決し，ユーザーの負担を減らし
03

01

GOALてナビゲーションを行うかが今後の課題である．

05

START

0907

Fig. 50bWork Environment

Fig.6 に示すような環境地図を与えた場合，経路Fig. 8

は ID7 → ID9 → ID3 → ID5 である．シミュレーショ

Simple Topological Map

ン結果を Fig.7 に示す．

8.

結言

今回は環境地図としてトポロジカルマップを与え，自律移動ロボットのナビゲーションを行った．
シミュレーション結果より本手法の有用性を検証できたが，課題も浮かび上がってきた．また，今回はシミュレーションのみで，実際にロボットに環Fig. 6

Topological Map

境地図を与えてナビゲーションを行ったわけではない．今後は問題点を解決していくとともに，実機にてナビゲーションを行って行きたい．

参考文献
1) 及川一美:自律移動ロボットのためのトポロジカルマ
ップを用いた環境表現，計測自動制御学会東北支部
第 190 回研究会講演資料，資料番号 190-6 (2000)

Fig. 72) Rodney A. Brooks: A Robustlayered Control
System For A Mobile Robot, IEEE Journal ofRobotics and Automation, vol.RA-2, no.1, pp.1423 (1986)

Simulation Sesult

今回は作業環境全体の環境地図を与えたため，ナビゲーションを行うことが出来た．しかし，ユーザーの手間がより少なくなればそれに越したことはない．
現在のままでも，環境地図を簡略化し，一部分のみを与えてナビゲーションを行うことは可能である．しかし，未登録 ID を検出した時のエラーリ
カバリーが未実装であるため，Fig.8 に示す環境地図を与えた場合，ID1 や IDb など他のランドマークへ向かってしまった時には対処が出来ない．こ{5{3) 寺林賢司: 手書き地図による自律移動ロボットのためのトポロジカルマップ作成インターフェイス，
北大卒業論文，pp.13-15 (2001)