IEEJ Transactions on Industry Applications Vol.131 No.1 pp.1–9 DOI: 10.1541/ieejias.131.1
論 文
未知環境下の移動ロボットによる可変分解能グラフ地図の自律生成
非会員
項
警宇
∗ 非会員田崎
勇一
∗非会員
稲垣
伸吉
∗ 正 員鈴木
達也
∗Autonomous Variable-Resolution Map Building
for Mobile Robots in Unknown Environments
Jingyu Xiang∗, Non-member, Yuichi Tazaki∗, Non-member, Shinkichi Inagaki∗, Non-member, Tatsuya Suzuki∗, Member
This paper presents a method that allows simultaneous map building and path planning for mobile robots in unknown environments. A graphical representation of a workspace in variable resolutions is constructed using measurement data obtained by omnidirectional distance sensors. At the same time, a search for a feasible path to the target destination is executed using the constructed graph map. The proposed method is evaluated by performing simulations and experi-ments using an omni directional mobile robot equipped with laser range finders.
キーワード：センサベーストナビゲーション，グラフ地図，経路計画，可変分解能
Keywords:Sensor-based Navigation, Graph Map, Path Planning, Variable-Resolution
1. はじめに 近年，医療福祉，公共分野などでロボットへの需要が高 まっている。従来，産業用ロボットが活躍してきた生産現 場では，レールやガイド上を移動するロボットや，机上に 固定されたロボットが主である。しかしながら，オフィス や病院などの多くの場所では，レールなどの専用インフラ を整備することが困難である。そのため，ロボットが自ら 環境を認識し，経路を自律的に計画して安全に移動する必 要がある。特に，作業空間が未知な状況で指定された目標 位置への到達を目的とする問題をセンサベーストナビゲー ションと呼ぶ(1)。 自律移動を行うためには，対象とする環境をモデル化した 地図が必要となる。地図を用いないナビゲーション手法(1) (2) もあるが，同じ作業空間上を繰り返し移動する場合は，情 報の再利用の観点から地図を用いる方が有利である。地図 を利用する目的には主として経路計画と自己位置推定が挙 げられる。未知環境において地図生成と自己位置推定を同
時並行的に行う問題はSimultaneous Localization and Map
Building（SLAM）と呼ばれ，多くの研究成果が報告され ている(3)∼(5)。しかしながら，SLAMの枠組みにはロボット の移動経路の決定は含まれておらず，操作者により外部か ら指示される場合が多い。これに対して，本論文では未知 ∗名古屋大学工学研究科機械理工学専攻 〒464-8603名古屋市千種区不老町
Dept. of Mech. Sci. & Eng., Nagoya University Furo-cho, Chikusa-ku , Nagoya, 464-8603
環境において移動ロボットが自律的に目的地へ到達するた めに地図生成と経路計画を並行して行う問題について議論 する。この問題においてロボットは不完全な地図を用いて ゴールへの経路を計画すると同時に，センサ情報にもとづ いて地図を拡充していく必要がある。 未知環境で移動ロボットが地図生成と経路計画を並行し て行うには，グラフ探索手法が適用可能なグラフ状の地図 表現(6)∼(8)が有効であり，その中でもノードやリンクを継ぎ 足して拡張できるロードマップ法が適している(9)∼(12)。 一般に地図は環境の複雑さに合わせて適切な分解能で表 現される必要がある。ロードマップ法における地図の分解 能とは隣り合うノード間の距離である。分解能の高い領域 ほどノードが密に分布し，逆に分解能の低い領域ほど分布 が疎となる。従来のロードマップ法では，環境の局所的な 特徴に合わせて地図の分解能を変化させることについて， 深く議論されていない。環境表現の分解能（以降，環境表 現分解能）を変化させる要因として，移動の安全性，メモ リ消費，計算時間及びセンサ分解能が挙げられる。ここで， 安全な移動とは移動誤差を考慮しつつ障害物に衝突せずに 移動することを指す。これはロボットにとっての安全性の みならず周囲の人間や周辺環境にとっての安全性にもつな がる。安全な移動を実現するには，障害物に近い領域ほど 地図の分解能を高め，正確な移動を行う必要がある。しか しながら，環境表現分解能を一様に高くすると，地図の保 持に必要なメモリ消費量が過大になるばかりか，経路計画 を実時間で行うことが困難になる。また，地図を生成する 際に用いるセンサ情報は設定した環境表現分解能よりも高
い分解能を必要とするが，センサの分解能はセンサの近辺 から遠方にむかうに従って低下するという性質を有するた めに，一様に高い分解能の地図を生成する場合，センサ情 報の有効範囲が狭まり，地図生成に必要な観測回数が増加 することになる。以上の考察から，移動の安全性を考慮し つつ必要最低限度の分解能で地図を作成することが望まし いと言える。 ロードマップとは異なる地図表現において分解能を可変 とする手法がいくつか提案されているが(13)∼(15)，これらは主 にメモリ消費量の削減を目的としており，移動ロボットの 安全性を考慮したものではない。一方，経路設計において 障害物との距離を考慮して経由点の個数や間隔を調整する 手法にElastic Band法（もしくはBubble Band法）と呼ば
れる手法がある(16)。しかしながら，この手法は事前に得ら れた経路に対して適用するものであり，自律的な地図生成 に適用された例はない。このように，逐次的に観測により 得られた情報を基にして実時間で環境表現分解能を変更し ながら地図生成と経路計画を同時に行う手法は未だ提案さ れていない。 以上の背景をふまえ，本研究では，移動ロボットがセン サ情報のみに基づいて適切な分解能を持つロードマップ地 図を自律的に生成する手法の提案と検証を行う。具体的に は，移動ロボットが障害物の置かれた平面状の作業空間に おいて，指示されたゴール地点へ向かいつつ，同時に環境 の地図を作成する問題について考える。自己位置推定問題 を切り分けて議論を簡潔にするために，ロボットは作業空 間上の自身の位置を取得可能であるとする。この問題に対 して，本論文では全方位距離情報を用いた可変分解能処理 によるグラフ地図生成法を提案する。提案するグラフ地図 生成法は，障害物の近くでは高い環境表現分解能を用い， 障害物が近くにない開かれた場所では低い環境表現分解能 を用いてグラフ地図を生成する。これは障害物の近くでは 安全性を考慮した正確な移動と高精度な計測が必要とされ るという要求を反映している。さらに，提案手法はいくつ かのルールセットから成り立っており，加えて経路計画に Real-Time A∗（RTA∗）探索(17)を用いるため，実時間での処 理が十分に可能である。提案手法をシミュレーション環境
とレーザレンジファインダ（Laser Range Finder: LRF）が
取り付けられた全方向移動ロボットの実機に実装し，実験 を通してその有用性を検証する。 以下に本論文の構成を示す。第2章にて問題設定及び提 案手法の流れについて述べる。第3章にて空間の可変分解 能処理に基づく空間のセル分割手法とルールベースのグラ フ地図生成手法について述べ，第4章にてReal-Time A* 探索に基づく経路計画手法について述べる。第5章にてシ ミュレーションと実機実験の結果から提案手法の有用性を 検証する。最後に第6章にてまとめと今後の課題について 述べる。 Omni-wheel ×3 Personal computer Omni-directional camera Laser range finder ×2
(L×W×H)=(420×400×630) DC motor ×3
Fig. 1. Mobile robot for experiment
Fig. 2. Illustration of workspace and proposed graph-map 2. 問題設定及び提案手法の概要 本研究で使用したロボット（Fig. 1）と問題設定について 説明する。ロボットは三個のDCモータとオムニホイール による三輪駆動で，全方向移動が可能である。定格速度は 約500mm/sである。ロボットの前後にはLRF，中央には 全方位カメラが装着されており，全方位観測が可能である。 Fig. 2に作業空間の例を示す。空間は有界な閉空間であ り，障害物と自由空間に分けることができる。ロボットは 自由空間内を自由に移動することはできるが，障害物に触 れることはできない。オペレータは作業空間に関する大ま かな情報に基づいてロボットにゴール地点を指示する。た だしロボットにとって詳細な障害物配置は未知であるため， ロボットは移動中に得られるセンサ情報をもとに近傍の地 図を作成し，経路計画を行うことでゴールへ到達すること が求められる。加えて，オペレータによって適切に指示さ れた複数のゴール地点を巡回することで，最終的に空間全 体の地図を獲得することが期待される。 上記の問題設定に対して提案手法では，グラフ探索手法を 実空間での経路探索問題に適用するため，LRFの観測デー タを基にコンフィギュレーション空間（以降，C-space）上 にグラフ構造の地図を生成する。C-spaceとはロボットの
Table 1. Definitions of terms and symbols 提案手法における用語定義 ノード： C-space上の経由点 (x, y) リンク： ノードとノードを接続する線分 セル： ノードを中心とした C-space 上の移動可能領域の部分集合 未到達ノード： セルを保持していないノード 到達済ノード： セルを保持しているノード 仮想リンク： 未到達ノードと nGを接続するリンク 記号定義 p(n): C-space上のノード n の位置 pS: スタート地点 nS: pSの位置を持つノード pG: ゴール地点 nG: pGの位置を持つノード 位置及び姿勢を表す空間である。なお，本研究ではロボッ トの重心位置をロボットの位置(x, y)と定義し，ロボット の正面の向きを姿勢θと定義する。C-spaceでは， •実空間において障害物と干渉するロボットの位置及び 姿勢から成るC-space上の集合をC-space上の障害物 （Configuration Obstacle）と呼ぶ。 • C-space上の障害物の補集合をC-space上の移動可能 領域と呼ぶ。 本論文では2次元平面上を全方向に移動可能なロボットを 対象とするため，C-spaceは実空間上の位置(x, y)からなる 2次元空間である。また，円形状で近似可能なロボットを 対象とするため，実空間で矩形状の障害物はC-space上で は角の丸い矩形状の障害物となる（Fig. 2）。C-space上の 移動可能領域をノードとリンクの集合で構成されるグラフ で表現することで，グラフ探索を適用することができる。 Table 1に用語と記号を示す。グラフ地図はノード，リンク 及びセルによって構成される（Fig. 2）： •ノードはC-space上の経由点を表し，C-space上の(x, y) 座標を持つ。 •リンクはノード間の接続関係を表す線分である。 •各ノードnのセルは，p(n)を中心とした所定の距離以 内の障害物と干渉しない領域である。ただしセンサの 死角となる部分を含まない。 なお，ノードのセルはそのノード上でのセンシングの結果 を基に作られるため，生成後未到達のノードはセルを持た ない。これらのノードを未到達ノードと呼び，それ以外の ノードを到達済ノードと呼ぶ。提案するグラフ地図は一般 的なトポロジカルマップ(18) (19)と異なり，リンクはノード間 の幾何学的な接続のみならず，ロボットがノード間を直線 移動可能であることを表す。この性質により，グラフ上で 計画した経路から直接的にロボットの移動軌跡が得られる。 その上，ノードを適切に配置することで移動時の安全性が 考慮できる。提案手法では未完成な地図を用いてゴールへ の経路を計画するために，各未到達ノードはnGと「仮想的 なリンク」で接続される。未到達ノードを初めて訪れる際 に，当該ノードからnGへ移動不能であることが判明すれ ば，仮想リンクは取り除かれる。 提案手法の全体の流れをFig. 3に示す。なお，経路計画 Yes No No Yes Chap.4 Cell generation Sensing Node generation Link generation
A: Decide next node
B: Update heuristic cost RTA* search
Sec.3.1
Sec.3.2
Has current node been arrived at before?
C: Move to next node Clear heuristic cost
Initiate searching at Start node
Goal in cell?
Move to Goal
End
Fig. 3. Flowchart of overall procedure
には既存手法であるRTA∗探索(17)を用いる。RTA∗探索の 具体的な適用方法については第4章で説明する。スタート 時，RTA∗探索に用いるヒューリスティックコストを初期 化し，未到達ノードであるnSに対して，〈3・1〉節に示す手 法により，センサ情報をもとにセル半径を決定し，セル生 成を行う。次に〈3・2〉節に示す手法により，現在ノードの周 囲に新たなノードを生成し，ノード間にリンクを生成する。 なお，セル内にpGが含まれていればnGを生成し，nGに移 動して処理を終了する。セル内にpGが含まれていなけれ ば，第4章に示す処理により，グラフ探索を用いて次に向 かうノードを決定し，ヒューリスティックコストを更新す る。次のノードに到達後，以上の処理を繰り返す。この時， もしも現在ノードとnGの間に仮想的なリンクが存在して いれば，探索を行う前にそのリンクを取り去る。なお，移 動先のノードが到達済ノードであれば，セルとノード，リ ンクの生成を行わない。 3. 可変分解能グラフ地図の構築 本章では，全方位の距離計測能力を有するロボットに適 した，ルールベースのグラフ生成手法を提案する。まず， 〈3・1〉節で可変分解能処理に基づくセル半径決定手法につい て説明する。この手法では状況に合わせたセル半径を反復 的手続きから求める。次に〈3・2〉節でグラフのノードとリ ンクの生成手法について説明する。この手法はいくつかの 簡単なルールセットから成り立っている。これらの理由に より，提案手法は計算コストが抑えられ，実時間処理に適 している。最後に〈3・3〉節で提案手法に含まれるパラメー タについて考察する。 〈3・1〉 可変分解能処理に基づくセル半径の決定 Fig. 4のように，Rmaxをセンサ性能に基づくC-space上での測
Configuration obstacle Blind spot Cell of node n Node n Mobile robot Cell boundary
Fig. 4. Measured distance D(n)(θ) and cell radius R(n)
定可能距離の最大値，R(n) をノードnにおけるセル半径， θ ∈ R1(0≤ θ < 2π)をロボットの右方向から反時計回りの 対象点の角度，D(n)(θ)をC-space内でノードnからθ方向 の障害物までの距離とする。ただし，測定可能距離内に障 害物が検知されない場合はD(n)(θ) := R maxとする。なお， Fig. 4の三角形はロボットの形状ではなく，ロボットの向 きを指示するものである。これらを用いると，ノードnの セルC(n)は次式で表される領域と定義される： C(n)={p| ∥ p−p(n)∥≤ min(D(n)(arg(p−p(n))), R(n))}. (1) ただし，arg(·)はベクトルの角度を表す。すなわち，セルと は位置p(n)から直線移動可能かつ距離R(n)以下の点の集合 である。この時，セル半径R(n)は次のように決定する：
R(n)= max(Rmin, min(Rmax, ˆR(n))
), (2) ˆ R(n)= max r s.t. 1 2π ∫ 2π 0 max(r− D(n)(θ), 0)dθ ≤ Rth. (3) (3)式は半径Rˆ(n)の円と障害物との交差する深さの平均値が 閾値Rth以下に収まることを表す。ここで，θ方向における 障害物との交差する深さは(3)式右辺のmax(r− D(n)(θ), 0) が表す。(3)式を満たす最大のRˆ(n)を基に(2)式でR(n)を 決定する。この時，Rminはセルの大きさの下限を決定する パラメータである。また，Rthは障害物との交差度合を決定 するパラメータであり，Rth = 0とすればRˆ(n)は最近接障害 物までの距離となる。なお，良好なRminとRthについては 〈3・3〉節で議論する。決められたRthに対して(3)式を満た すRˆ(n)を直接的に求めるのは困難であるため，反復的手続 きにより近似的に求める。そのために，(3)式の左辺を次式 のように近似して書きなおす： 1 m m−1 ∑ k=0 max(Rˆ(n)− D(n)(k∆θ), 0)≤ Rth. (4) ここで，mはサンプリング点数である。∆θは距離計測に おける角度θに関するサンプリング間隔である。また，[∗] は∗を超えない最大の整数を表す。サンプリング点数mは m= [2π/∆θ]で与えられる。そして，(4)式を用いて(2)式 を満たすR(n)を次のSTEP1∼3にしたがって決定する：
Algorithm: Cell generation
STEP1（初期化）：R(n)i に対して，i← 0とし，次式によ りR(n)0 にRmaxを代入して初期化する： R(n)0 := Rmax. (5) STEP2（終了条件）：次の二式のいずれかが真であるな らば，STEP4へ。そうでないならばSTEP3へ： 1 m m−1 ∑ k=0 max(R(n)i − D(n)(k∆θ), 0) ≤ Rth, (6) R(n)i ≤ Rmin. (7) STEP3（更新）：i← i + 1とし，次式によりR(n)i を更新 し，STEP2へ： R(n)i = 1 m m−1 ∑ k=0 min(D(n)(k∆θ), R(n)i−1). (8) STEP4（決定）： R(n)= max(R(n)i , Rmin). (9) この時， min(D(n)(0), D(n)(∆θ), ..., D(n)((m− 1)∆θ))≤ R(n)i ≤ R(n)i−1 (10) の関係が満たされるので，R(n)i は単調減少する。よって， R(n)i の収束性は保証される。終了条件(6)式は，半径R(n)i の円と障害物との交差する深さの平均値が閾値Rth以下に 収まったときに更新を終了することを意味する。終了条件 (7)式は，R(n)i があらかじめ定めた最小値Rmin以下になっ たときに更新を終了することを意味する。 上記の手順によりR(n)が決定すると，ノードnを中心に セルが生成される。Fig. 4に示すように，セルの境界は半 径R(n)の円弧，障害物の境界および死角の端点を結ぶ線分 の3つの要素から成る。 〈3・2〉 ノードとリンクの生成手法 セルが生成され たノードに対し，次のルールA–1∼3にしたがってノード を生成する(Fig. 5)：
Rule: Node generation
A–1 ノードとゴールを結ぶ線分とセルの境界の交点が 障害物と面していない時にその点にノードを生成する。 A–2 セルの境界線の角点にノードを生成する。 A–3 他のセルと交差する部分にはノードを生成しない。 ここでルール A–2における境界線の角点とは，ノード からセル境界までの距離を角度 θの関数として f (θ) = min(D(n)(θ), R(n))としたときに f (θ)が微分不可能である点 を指す。A–3は他のルールよりも優先して適用する禁止事
Rule A-3: Node generation prohibited region Current node Current node Cell Rule A-1: Node
generation point Goal
Rule A-2: Node generation points Configuration obstacle Current node p g Existing node Fig. 5. Node generation rules
(a) A node is inside the cell of another node.
(b) Two cells overlap, no obstacle in-between.
(c) Obstacles exist between two nodes.
Existing node Current node
Fig. 6. Link generation rule
項であり，ノードが無限に生成されることを防ぐ。これに より，グラフ構造が永久的に変化し続けることはない。新 しく生成されたノードは未到達状態である。上記のルール
でノードを生成した後に，次のルールBにしたがってリン
クを生成する(Fig. 6)：
Rule: Link generation
B 二つのノードを結ぶ線分上のすべての点が，二つ のノードのセルのどちらかに含まれている時に，その ノード間にリンクを生成する。 このルールにより，Fig. 6(a),(b)のような状況ではリンクが 生成されるが，（c）のような状況ではリンクが生成されな い。これにより，リンクで結ばれたノード間は障害物に衝 突せずに直線移動できることが保証される。なお，C-space 上でConfiguration obstacleと交差しない軌道は，実空間に おいて（ロボットの大きさを考慮して）障害物と衝突しな い軌道を表すことに注意されたい。以上のようにして，計 四つのルールを用いてC-space内にグラフ地図を逐次的に 生成していく。 〈3・3〉 パラメータに関する考察 提案手法に含まれ
Configuration obstacle Width at entrance of narrowest path
(a) bad case (b) Good case
Fig. 7. Decision indicator of Rminand Rth
(a) Search phase (b) Update and move
Fig. 8. Image of path planning using RTA∗
ているパラメータのRmin とRth の決定指針について考察 する。提案手法に対する要求事項の一つに，ロボットが走 行可能な通路を見落とさず，通路の内部もしくは入り口に ノードを生成することが挙げられる。特に環境に関する事 前知識が無い場合は，ロボットの直径と等しい幅の通路ま で考慮に入れる必要がある。ここではFig. 7のように直線 状の壁から直角に細い通路が伸びている状況に限定してパ ラメータに対する必要条件を求める。今，drを空間内の最 も細い通路の入り口の幅とする。Fig. 7のようにロボット がC-space上の障害物境界上にいる状況を考えると，セル は半円になるため，(3)式から次式が得られる： ˆ R(n) = 2Rth. (11) そして，セル半径R(n)は(2)式より次式のように得られる： R(n)= max(Rmin, 2Rth). (12) この時，通路の入り口にノードを生成するためには，R(n)< dr となる必要がある。よって，以下の条件が得られる： Rmin< dr, (13) 2Rth< dr. (14) 上記で求めたRminとRthの条件の妥当性については，〈5・1〉 節で検証する。 4. 経路探索 前述の通り，経路計画においてその時点までに構築され たグラフ地図に未到達ノードからゴールへの仮想リンクを 加えたものを用いてゴールへの最短経路を計画する。移動
ロボットの経路計画には実時間性が求められるため，探索 深さが限られる。しかし探索深さが不十分だとサイクルを 持つグラフで無限ループに陥る可能性が生じる。この時， グラフのサイズが小さい場合には探索深さを気にせずにA∗ 探索(20)などのグラフ探索手法を用いても実時間性を保てる が，グラフのサイズが大きい場合には実時間性を保つため に，有限の探索深さでゴールへの到達性を保証するオンラ イングラフ探索手法を用いる必要がある(17) (21)∼(24)。そこで 今回はアルゴリズムが単純であり，ノード数及び各ノード の保持しているリンク数が有限な空間であれば一定先読み 深さの探索結果を基に解を実行することで実時間性が保証 されているRTA∗探索(17)を用いるとする。RTA∗探索では 各ノードのゴールまでの推定経路コストであるヒューリス ティックコストを各ノードが保持し，ノードを訪問するた びにそのノードのヒューリスティックコストを更新するた め，先読み深さが有限であってもゴールへの到達性が保証 されている。 RTA∗探索を以下のようにして提案手法に組み込む。ま ず，グラフ地図内の全リンクをL，ノードnとノードn′間 のリンクをl(n, n′)として，Nk(n)(k≥ 0)を次式のように定 義する： N(n) 0 := n, N(n) k = {n′| l(ˆn, n′)∈ L, ˆn ∈ N (n) k−1, n′< k−1 ∪ i=0 N(n) i }. (15) これは，ノードnからkステップで初めて到達できるノー ドの集合を意味する： Algorithm: RTA* search
nc ： 現在ノード d ： 先読み深さ g(n, n′) ： nからn′までのグラフ上の最短経路距離 h(n) ： nのヒューリスティックコスト f (n, n′) ： n′を経由するnの評価値 STEP1（初期化）：存在する全てのノードのh(n)を削除 し，スタート地点のノードnSをncにセットする。 STEP2（先読み探索）：全てのn(∈ N(nc) 1 )について次式 より評価値 f (nc, n)を計算し，f (nc, n)を最小とするn∗ を求める(Fig. 8(a))： f (nc, n) = g(nc, n) + h(n), n∗= arg min n∈N1(nc) f (nc, n). (16) なお，h(n) がnに登録されていない場合は次式で計算 する： h(n) = min nd+1∈Nd(nc)+1 { g(n, nd+1)+ h(nd+1) } . · · · ·(17) この時，h(nd+1)がn d+1に登録されていない場合はh(nd+1)= ∥nd+1− pG∥2とする。なお，nから先読み可能なステッ プ数がd未満の場合は，nからdステップ未満で先読み 可能な最大ステップ数をdとして，(17)式を計算する。 もしd= 0ならばh(n)= ∥n − p G∥2とする。また，nから dステップ以内にnGが存在する場合は，h(n)= g(n, nG) とする。 STEP3（コスト更新）：h(nc)の値を次式に従い，二番目 に最小なコスト値に更新する(Fig. 8(b))： h(nc)= min n∈N1(nc)\{n∗} f (nc, n). (18) STEP4（移動）：ncからn∗へ移動し，n∗をncにセット する。
STEP2∼4がFig. 3のRTA∗search枠のA,B及びCの
それぞれに該当する。STEP3のコスト更新により，ノード を訪れるたびにコスト関数は単調増加し，エージェントが 無限ループや行き止まりに陥ることはない。 移動するたびに新たにノードが生成されるが，Rminのお かげで作業空間が有界ならば生成され得るノード数も有限 であるため，RTA∗探索を提案手法に組み込むことができ る。また，実時間性については先読み深さのみならずリン ク数の有限性も必要となるが，この点については次章で検 証する。 5. 検証実験 〈5・1〉 数値シミュレーションによる検証 提案手法を シミュレーションと実機により検証する。初めに，シミュ レーションを通じて，〈3・3〉節で得られたグラフ地図生成ア ルゴリズムに含まれるパラメータの条件とゴールへの到達 性との関係を定量的に考察する。そこでTable 2,3に示す それぞれの設定を組み合わせた計15通りの設定でシミュ レーションを行う。ただし，考察に用いた結果のみ載せる。 また，RTA∗探索の実時間性はノード数及び各ノードが保 持しているリンク数が有限であれば保証されるため，ノー ド数及び各ノードが保持しているリンク数が有限であると いうことを確認する。なお，Table 2のdrは空間内の最も 狭い通路の入り口の幅を表し，RminとRthはグラフ地図生 成アルゴリズムに含まれるパラメータである。 一般に，RTA∗探索は先読み深さdを大きくすることで 良い解が得られる傾向にあるが，グラフ地図を生成しなが ら探索を行う段階では，N(nc) 1 に未到達ノードが存在してい ればdの大きさによらずに未到達ノードが選択される傾向 にあるため，ここではd = 0とする。距離測定器の角度分 解能を∆θ ≃ 0.36◦とし，測定可能距離を4000mmとする。 Table 2はRminに関する５種類の設定のそれぞれにおい て，Fig. 9に示す形状の環境にてスタート地点（pS），ゴー ル地点（pG），Rmin及びRthをそれぞれ100回変更して試 行した結果である。Fig. 9では濃い灰色が障害物を，点が ノードを，淡い灰色がセルで覆われた領域をそれぞれ表す。 ただし，0 < Rth < Rmin/2である。その結果として，Rmin
Table 2. Condition settings for Rminwith 0< Rth< dr/2
Case Parameter setting
Success rate Average of di ffe-rence to Case 1-2 1-1 0< Rmin < dr/2 100% +3.1 (steps) 1-2 dr/2 ≤ Rmin < dr 100% − 1-3 Rmin = dr 87% −0.9 (steps) 1-4 dr< Rmin < 3dr/2 76% −2.1 (steps) 1-5 3dr/2 ≤ Rmin ≤ 2dr 70% −4.3 (steps)
Table 3. Condition settings for Rthwith dr/2 ≤ Rmin <
dr
Case Parameter setting Success rate
2-1 0< Rth < dr/2 100% 2-2 dr/2 ≤ Rth < dr 92% 2-3 dr≤ Rth < 3dr/2 71% S
p
Gp
(a)Case 1-1 rd
Sp
Gp
(b)Case 1-3Fig. 9. Result of simulation
が次の条件を満たす時に全ての試行で pGへ到達すること が確認された： 0< Rmin< dr. (19) これにより(13)式の妥当性が確認された。pG到達に要す る移動回数についての比較も行った。比較は同じ pS，pG に対して，それぞれの設定で pG到達に要する移動回数と Case 1-2で要した移動回数との差の平均で行った。この時， (19)式を満たしていても，Rminが過小だと必要な移動回数が 多くなることが確認された。Case 1-1の結果の一例をFig. 9(a)に示す。移動回数は環境の大きさに依存するものであ り，環境が拡大すればこの差はさらに広がることが予想さ れる。また，Fig. 9(a)においてもしもセル半径を一様に小 さく設定した場合，障害物から遠いpSとpG付近でも一度 の移動距離が減り，全体の移動回数が多くなることが予想 される。一方，Rminが大きくなるにつれて一度当たりの移 動量が増え，必要な移動回数が少なくなった。しかしなが ら，到達回数が減少することが確認された。Case 1-3にお いてRmin= drとしたことで，狭い通路の内側にノードが生 成されずにpGに到達できなかった一例を（Fig. 9(b)）に示 す。このことより，もしもセル半径を一様に大きく設定し た場合，目標地点へ到達できなくなることが予想される。 Table 3はRthに関する３種類の設定のそれぞれにおいて， Fig. 9に示す形状の環境にてスタート地点（pS），ゴール地 点（pG），Rmin及びRthをそれぞれ100回変更して試行し
Fig. 10. Graph-map constructed by simulation in large environment
6000
1st. Start 1st.Goal 2nd.Start2400
)
(mm
Obstacle 2 Obstacle 1 Obstacle 3 Landmark Landmark×
×
2nd.Goal 1st. trial 2nd. trialFig. 11. Environment for experiment
た結果である。ただし，dr/2 ≤ Rmin < drである。その結 果として，Rthが以下の条件を満たす時に全ての試行でpG へ到達することが確認された： 0< Rth< dr/2. (20) これにより(14)式の妥当性が確認された。Case 2-2, 3で は，障害物の周囲にいながらもセル半径R(n)がR minになら ずに，Fig. 9(a)と同様に狭い通路の内側にノードが生成さ れない試行があった。 上記で求めた条件を満たし，より実環境に近い環境（20m× 20m）で行ったシミュレーション結果をFig. 10に示す。Fig. 10では二つの袋小路が存在するが，ゴールに到達できてい る。可変分解能の効果により，自由空間が広い場所ではノー ド数が少なく，狭い場所ではノード数が多くなっている。 また，シミュレーション実験の結果を通して，どのノード も保持しているリンク数が最大で21本であり，上限を持つ ことが確認された。これによりRTA∗探索の実時間性が裏 付けられた。 〈5・2〉 実機実験 シミュレーションで求めた条件を満 たす環境の元で行った実機(Fig. 1)による実験について述 べる。有限空間内のスタート地点とゴール地点に対して本
Goal
Start
(a) First trial
Start
Goal
G
(b) Second trialGoal
Start
(c) Third trialFig. 12. Graph-map constructed by the mobile robot (a,b) and path of the mobile robot using path-planning on the graph-map with the search depth set as 5 (c)
手法を二回試行し，グラフ地図を生成する。次に生成した グラフ地図を用いて，経路計画のみを一回試行する。ノー ド間の移動は，加速度500mm/s2，最高速度500mm/sの 台形制御で行う。自己位置は事前に設置した位置が既知の ランドマークを観測して計算する。RTA∗探索の先読み深 さはd= 0とする。ただし，一度グラフ地図が生成された あとで，経路計画を行う場合はd≥ 1とする。LRFの角度 分解能は∆θ ≃ 0.36◦ である。可変分解能セルの半径を決 める時のパラメータのRmaxをLRFの測定可能距離の最大 値4000mm，Rminは環境と(19)式を考慮して300mm，Rth は(20)式を考慮して40mmとする。走行環境をFig. 11に 示す。問題設定で有限の広さを持つ閉じた環境を想定して いるため，周囲には壁を配置する。ランダムに決めたいか なるスタート地点とゴール地点に対しても，経路が最低一 本は存在するように障害物を設置する。なお，未知環境を 想定しているため，ロボットには障害物に関しての情報を 与えない。なお，提案手法はC-space内にグラフを構築す るものであるため，実際にはLRFの観測データをもとに C-space上の可視領域を計算する必要があるが，紙面の都 合上説明を割愛する。 一連の実機実験の結果，得られた走行軌跡とグラフ地図
を可視化したものをFig. 12に示す。Fig. 12(a)は一回目の
走行後に生成されたC-space内のグラフ地図である。濃い 灰色の点はグラフ地図のノードであり，濃い線はリンクで ある。薄く塗りつぶされた部分はセルである。また，矢印 は移動ロボットの移動軌跡である。セルの半径を可変にし たことにより，スタート後やObstacle3を越えた後は，セ ル半径R(n)が大きくなっていき，効率良くゴールへ向かう ことができている。また，障害物が密集している領域では， セル半径R(n)が小さくなり，安全に進むことができている。 Obstacle1,3によって作られた袋小路内では，ルールA–2と Bにより新しいノードを生成しつつ，既存のノードとの間 にリンクを生成する。RTA∗探索のメカニズムにより数ス テップ後に袋小路から脱出する。脱出後はObstacle2,3に よって作られた細道を通ってゴールへ向かっている。この とき，セル半径R(n)は最小値であるR minとなっている。 一回目の試行後に新たなスタート地点とゴール地点で二 回目の試行を行うため，RTA∗探索のヒューリスティック コストを初期化する。二回目の試行では一回目の試行で生 成したグラフ地図を利用しつつ，さらにグラフ地図を拡充 している（Fig. 12(b)）。 次に二回の試行で生成したグラフ地図（Fig. 12(b)）を利 用して，先読み深さをd= 5とした経路計画のみの試行を 行う。三回目の試行でのスタート地点とゴール地点は，一 回目の試行と同様に設定する（Fig. 12(c)）。一回目の試行 ではロボットは地図を保持していなかったために，袋小路 に迷い込んでからゴールに向っているが，この試行では地 図を保持し，さらに先読み深さを大きくすることで分岐路 でゴールまでの経路を先読みできているために，最適な経 路を選択している。これにより，地図の逐次的な構築に加 えて，獲得した地図を利用した効率的な経路計画が可能で あることが確認された。 以上の実験結果から，試行を繰り返すことで，既存のグ ラフ地図を利用しつつ，グラフ地図を拡充する本手法の特 性が確認された。 6. まとめと今後の課題 本論文では，未知環境において逐次的にグラフ地図を生 成し，実時間で経路計画を行う手法を提案し，さらにその 有用性をシミュレーションと実機実験にて検証した。提案 手法は，単純な計算による可変分解能処理と，ルールベー スのグラフ地図生成手法から成り立っているために，実時 間処理に適している。可変分解能処理では，障害物との距 離に応じてセル分割の細かさを変化させることで，移動時 の安全性と効率に対する重視度の比重を連続的に切り替え ることができる。今後の課題としては，本手法のゴールへ の可到達性に関する解析的条件を導出することや，本手法 で生成した分解能情報と自由空間の形状情報を含んだグラ フ地図を利用した自己位置推定手法を考案することが挙げ られる。
文 献
（ 1 ） 吉岡 孝，登尾 啓史，徳永 昌治: “移動ロボットのセンサベーストナビ ゲーションについて”, 日本ロボット学会誌，Vol.19, No.8, pp.991-1002, 2001.
（ 2 ） I.Kamon and E.Rivlin: “Sensory-Based Motion Planning with Global Proofs”, IEEE Trans. on Robotics and Automation, Vol.13, No.6, pp.814-822, 1997.
（ 3 ） M.W.G.Dissanayake, P.Newman, S.Clark, H.F.Durrant-Whyte and M.Csorba: “A Solution to the Simultaneous Localization and Map Buliding(SLAM) Problem”, IEEE Trans. on Robotics and Automation, Vol.17, No.3, pp.229-241, 2001.
（ 4 ） L.M.Paz, P.Pini´es, J.D.Tardos, and J.neira: “Large-Scale 6-DOF SLAM With Stereo-in-Hand”, IEEE Trans. on Robotics, Vol24, No.5, pp.946-957,2008.
（ 5 ） A.Angeli, D.Filiiat, S.Doncieux, and J-A.Meyer: “Fast and Incremental Method for Loop-Closure Detection Using Bags of Visual Words”, IEEE Trans. on Robotics, Vol24, No.5, pp.1027-1037,2008.
（ 6 ） 太田 順，倉林 大輔，新井 民夫：“知能ロボット入門―動作計画問題 の解法―”，コロナ社，2001
（ 7 ） R.Brooks and T.Lozano-Perez: “A subdivision algorithm in configuration space for findpath with rotation”, Proceedings of the 8th International Con-ference on Artifical Intelligence, pp.799-806, 1983.
（ 8 ） S.Kambhampati and L.S.Davis: “ Multiresolution path planning for mobile robots”, IEEE Journal of Robotics and Automatiion, Vol.2, No.3, pp.135-145, 1986.
（ 9 ） C.O’Dunlaing and C.K.Yap: “ A ’retracion’ method for planning the motion of a disk”, J.Algorithms, No.6, pp.104-111, 1985.
（10） V. Boor, M. H. Overmars, A. F. van der Stappen: “The Gaussian Sampling strategy for probabilisitic roadmap planners”, IEEE Int. Conf. Robotics and Automation, pp.1018-1023, 1999.
（11） R.Bohlin, L.E.Kavaraki: “Path Planning Using Lazy PRM”, IEEE Int. Conf. Robotics and Automation, pp.521-528, 2000.
（12） L.E.Kavraki, P.Svestka, J.-C.Latombe, M.H.Overmars: “Probabilistic Roadmaps for Path Planning in High-Dimensional Configuration Spaces”, IEEE Trans. Robotices and Automation, Vol.12, No.4, pp.566-580, 1996. （13） S.Behnke: “ Local Multiresolution Path Planning”, Robot Soccer World Cup
VII, LNCS 3020, pp.332-343, Springer, 2004.
（14） H.Noborio, T.Naniwa, S.Arimoto: “A Quadtree-Based Path-Planning Al-gorithm for a Mobile Robot”, Journal of Robotics Systems, Vol.7, No.4, pp.555-574, 1990.
（15） G.K.Kraetzschmar, G.P.Gassull, K.Uhl: “Probabilistic Quad-trees for Variable-Resolution Mapping of Large Envrionments”, Proceedings of the 5th IFAC/EURON Symposium on Intelligent Autonomous Vehicles, 2004. （16） S.Quinlan and O.Khatib: “Elastic Bands:Connecting Path Planning and
Control”. In Proceedings of IEEE International Conference on Robotics and Automation, Atlanta, Georgia vol.2, pp.802-807,1993.
（17） R.Korf: “Real-time heuristic search”, Artificial Inteligence, Vol.42, No.2-3, pp.189-211, 1990.
（18） B.Kuipers, J.Modayil, P.Beeson, M.Macmaho and F.Savelli: “Local Metri-cal and Global TopologiMetri-cal Maps in the Hybrid Spatial Semantic Hierarchy”, In Proceedings of IEEE International Conference on Robotics and Automa-tion, pp.4845-4851, 2004.
（19） T.B.Kwon, J.B.Song: “Real-time building of a thinning-based topological map”, Intelligent Service Robotics, Vol.1, No.3, pp211-220, 2008. （20） P.E.Hart, N.J.Nilsson and B.Raphael: “A Formal Basis for the Heuristic
De-termination of Minimum Cost Paths”, IEEE Trans. Systems Sci. Cybernet., Vol.4, No,2, pp100-107, 1968.
（21） A.Stentz: “Optimal and efficient path planning for unknown and dynamic environments”, In Proceedings of the IEEE International Conference on Robotics and Automation, pp.3310-3317, 1994.
（22） A.Stentz: “The Focussed D∗Algorithm for Real-Time Replanning”. In Pro-ceedings of the International Joint Conference on Artificial Intelligence, pp.1652-1659, 1995.
（23） S.Koenig and M.Likhachev: “D∗Lite”. In Proceedings of the National Con-ference on Artificial Intelligence, pp.476-483,2002
（24） R.Phillippsen: “A Light Formulation of the E∗Interpolated Path Replanner”. Technical Report. Autonomous Systems Lab. Ecole Polytechnique Federale de Lausanne. 2006. 項 警宇 （非会員） 1985 年 9 月 8 日生。2010 年名古屋大学大学 院工学研究科電子機械工学専攻博士課程前期課程 修了。2010 年同大学大学院工学研究科電子機械 工学専攻博士課程後期課程入学，現在に至る。自 律移動ロボットに関する研究に従事。日本ロボッ ト学会，IEEE 会員。 田崎 勇一 （非会員） 1980 年 5 月 21 日生。2008 年東京工業大 学大学院情報理工学研究科情報環境学専攻博士課 程修了。工学博士。2007 年∼2009 年 日本学術振 興会特別研究員。2008 年 Honda Research Institute Europe (Germany)客員研究員。2009 年より名古 屋大学大学院工学研究科助教，現在に至る。ハイ ブリッドシステム理論や動的システムの離散抽象 化，多自由度ロボットの動作計画等に関する研究 に従事。計測自動制御学会，日本ロボット学会，IEEE 会員。 稲垣 伸吉 （非会員） 1975 年 11 月生まれ。2003 年東京大学大学 院工学系研究科博士課程修了。博士（工学）。同 年名古屋大学大学院工学研究科助手。2007 年同 助教。2008 年同講師。現在に至る。分散・自律分 散システム，歩行ロボット，人間−機械系に関す る研究に従事。2007 年 Finalist of the SICE Annual Conference Young Author’s Award，2009 年 計測自 動制御学会論文賞・友田賞，2009 年 計測自動制 御学会システム・情報部門賞奨励賞などを受賞。計測自動制御学会， 日本機械学会，日本ロボット学会，IEEE の各会員。 鈴木 達也 （正員） 1964 年 1 月 3 日生。1991 年名古屋大学大学 院博士課程後期課程電子機械工学専攻修了。工学 博士。同年名古屋大学工学部助手。2000 年同助 教授。2006 年同教授，現在に至る。この間，1998 年から 1 年間，U.C.Berkeley 客員研究員。ハイブ リッドシステム論や離散事象システム論に基づい たメカトロニクスの制御，診断，行動解析等に関 する研究に従事。1995 年 電気学会論文賞，2008 年 ICCAS Outstanding paper award, 2009 年 計測自動制御学会論文賞・ 友田賞，2010 年 自動車技術会論文賞などを受賞。計測自動制御学会， システム制御情報学会，自動車技術会，電子情報通信学会，日本機械 学会，IEEE 等の各会員。
