最短経路の求め方


マイクロマウス競技では,探索走行で迷路の状態を特定し,ロボットにとって都合のよい経路で最短走行を行うことが重要である.

本稿では,グラフ理論を使った最短経路の求め方を解説する.

設計方針

本稿では簡単のため,4×4迷路に対する最短経路の求め方を解説する.

前提条件

マイクロマウス競技では,以下の図のように,格子区画状の迷路を考える.
Target2expTarget

ロボットは迷路の壁情報,初期区画と目的区画の座標を知っているとする.この時,初期区画から目的区画までの最短経路を求めることが問題である.ただし,初期区画と目的区画の間には少なくとも1つの経路が存在するとする.

最短経路の求め方

迷路上でロボットが取りえる行動(直進・回転など)を全て列挙し,各行動の遷移可能性をグラフとして表現する.そして,グラフに対して最短経路問題を解くことで,最短経路を導出すれば良い.

グラフ表現法は,ロボットの性能(スラロームできるか,斜め走行できるかなど)によってさまざまなものが考えられる.また,そのグラフの性質によって,適用可能な最短経路アルゴリズムも変化する.そこで,本稿では,いくつかのグラフの構築とそれに対する最短経路導出アルゴリズムの適用例を紹介しよう.

最も簡単な例

最も簡単な例として,ロボットは以下のような仮定を満たすとする

  • ロボットは隣接する区画にいつも同じ時間コストで到達する

すると,以下のようなグラフとして迷路をモデル化することができる.
Graph1

このグラフは,全エッジの重みが等しく,ノードが16本,エッジが16本ある無向グラフである.このようなグラフに対しては,例えば,幅優先探索を使うことで最短経路を求めることができる.幅優先探索の時間計算量はO(|V| + |E|),空間計算量はO(|V| + |E|)である.ただし,|V| はグラフのノード数,|E|はエッジ数である.時間計算量は計算時間,空間計算量は必要なメモリの量と思えばよい.

ゆえに,この例の場合はO(32)の時間計算量,O(32)の空間計算量で最短経路を求めることができる.

向きを考慮した走行の例

次に簡単な例として,ロボットは以下のような仮定を満たすとする.

  • ロボットは東西南北の向きを持つ
  • ロボットは,2単位時間で自分が向いている方向にある区画へ移動可能
  • ロボットは,1単位時間で,その場で向きを90度変更可能.

すると,以下のようなグラフとして迷路をモデル化することができる.
Graph2

先ほどの例では1つの区画を1つのノードとしてモデル化したが,この例ではどの区画にどの方向でいるのかということを一つのノードとしてモデル化している.

このグラフは,全エッジの重みが等しくない,有向グラフである.このようなグラフに対しては,幅優先探索を適用することができない.例えば,ダイクストラ法を使う必要がある.ダイクストラ法は,ヒープを使った実装を行えば,O((V + E) log V)の時間計算量で最短経路を求めることができる.このことから,計算量のオーダー・グラフのノードとエッジはともに,先ほどの例より増えていることが分かる.これは,新しく機体の方向を考慮したためにおきた,計算量の増加といえる.

速度を考慮した走行の例

最後の例として,以下のような仮定を満たすロボットを考えよう.

  • ロボットは東西南北の向きを持つ
  • ロボットは,1単位時間で,その場で向きを90度変更可能.
  • ロボットは,2単位時間で自分が向いている方向に1区画だけ移動可能
  • ロボットは,3単位時間で自分が向いている方向に2区画まとめて移動可能(壁がなければ)
  • ロボットは,4単位時間で自分が向いている方向に3区画まとめて移動可能(壁がなければ)

この仮定は,1区画ごとに加減速をするのではなく,長い直線上はまとめ加減速をするロボットのモデル化といえる.

この仮定のもとでは,迷路を以下のようなグラフとしてモデル化できる.
Graph3

大分複雑になってきたが,このグラフもダイクストラ法で最短経路を求めることができる.これまでに上げてきた例では,2通りある目的区画への経路のどちらを選んでも「最短」と言えたが,このグラフの場合では最短経路は1通りになる点に注意しよう.

さらに,エッジの具体的なコストを調整することで,加速度を考慮した最短経路を求めていると言える.例えば,加速度一定で走るロボットを考えると,ある一定距離直進走行するため,あるいは,その場回転にかかる時間を求めることができる.その数値が,その場回転に200msec,1区画進むために300msec,2区画進むために400msec,3区画進むために500msecかかるとしよう.この場合は仮定を以下のようにおきかえれば良い.

  • ロボットは東西南北の向きを持つ
  • ロボットは,200単位時間で,その場で向きを90度変更可能.
  • ロボットは,300単位時間で自分が向いている方向に1区画だけ移動可能
  • ロボットは,400単位時間で自分が向いている方向に2区画まとめて移動可能(壁がなければ)
  • ロボットは,500単位時間で自分が向いている方向に3区画まとめて移動可能(壁がなければ)

ノード数を節約する例

ここまでで,モデル化に仮定を加えれば加えるほどグラフは巨大化してきた.しかし,多くのマイクロマウスロボットの持つ一次記憶容量は少ない.そのため,ノード数を減らす工夫も必要である.機体の前後方向を問わないことにすればノード数を節約することができる.すなわち,向きを考慮した走行の例に対し,南向きノード・北向きノードを同値類としてみなして以下のようなグラフを作る手法が考えられる.
Setuyaku
また,与えられたグラフに対して明らかに不要なノード(袋小路)を枝狩りする手法も考えられる.この手法は実際の競技において,計算を素早く終了させる利点がある.

斜め走行の例

これまでの例では,区画の中央部分をノードとみなしてきた.ななめ走行の場合は区画と区画の間部分をノードとみなす手法が考えられる.
Nanamenode

  • ロボットの回転直前速度はいつも一定

という仮定を取れば,以下の図のように,グラフのエッジを5パターンを考えれば良い.
Nanamearc

グラフの図示はここでは行わない.2次元の紙に描こうとするにはあまりにも複雑だからである.もちろん,実装にはノードの接続情報のみが必要だから,これは問題にならない.経験上,ノードの数が10万~100万を超えない限り,図示が難しい問題でも,コンピュータは簡単に解いてしまう.

このモデル化の場合,迷路サイズが32x32の場合は3(1マスあたりのノード数)*2*32*31(壁の最大数)=5952ノードを持つ無向グラフに対し,グラフ問題を解くことになる.これは大きいグラフとはいえないため,Ramを外部に増設したマウスなら実装可能である.

すなわち,1ノードあたり,4byteのfloatを使ってノードの重みを保持すると仮定すると,20kbyte以上のRamを持つロボットに対して実装可能である.

まとめ

以上のように,迷路をグラフとしてモデル化すると,ロボットの性能に合わせた最短経路を簡単に求めることができる.求めることができる経路の種類も豊富で,本稿で述べた例以外に,旋回半径を考慮した最短経路,2番目に短い経路(k-最短路)なども導出可能である.さらに,迷路の最大サイズと,採用するアルゴリズムによって,最悪計算量も見積もることもできる.これは,意図的に意地悪な迷路が出題された場合に有効である.

参考文献

  • Edsger W. Dijkstra, "A Note on Two Problems in Connexion with Graphs" Numerische Mathematik, vol.1, pp.269-271 (1959)

外部リンク