足立法


マイクロマウス競技では,エージェントが未知の格子区画状迷路を解きゴール区画へ到達するアルゴリズムが必要である.これに対し,左手法,拡張左手法,求心法,足立法等が広く使われている.中でも足立が提案した足立法は近年のマイクロマウス競技において最も使われているアルゴリズムである.

しかし,足立法に関する文献は著者の知りうる限り存在しない.そこで,本稿では足立法の定式化と,正当性の証明を行う.

概要

足立法ではまず最初に最短経路を求め,その最短経路に沿って走行しながら壁の情報を集める.この時未探索区域には壁がないと仮定する.求めた最短経路通りに進めなくなると既知の壁を考慮して最短経路を求め直す.これをくりかえし,最短経路に未探索の区画が無くなると,目的地点に到達することができる.

本稿では足立法が数学的に本当に成立しているかどうかを検討する.

なお,より直感的な足立法の説明は外部サイトを参照していただきたい.Micromouse_zero @WikiロボコンやっぺしBROKEN's Advanced Vehicle Laboratoryなどを参考にするとよい.シミュレーションを使ったアルゴリズムの説明はよしたろー's Webページ Ver.2などで公開されている.

問題設定

前提条件

マイクロマウス競技では,以下の図のように,N×Nマスからなる格子区画状の迷路を考える.ただし,N\in \mathbb{N}\displaystyleはあらかじめ公開されており,既知である.
Target2exp
Target

この迷路は格子状にサイズが一様な柱が挿入されており,柱と柱の間を壁がつなぐ構造となっている.それぞれの柱からは少なくとも1本の壁が接続されており,また,迷路の外周には必ず柱が接続されているとする.

この迷路には目的区画と,ロボットが初期地点として置かれる初期区画が与えられており,初期区画と目的区画の間には少なくとも1つの経路が存在するとする.

ロボットは迷路のサイズ・初期区画と目的区画の座標が既知であり,壁の接続状況は未知であるとする.また,現在存在する区画と隣接する区画の間に壁が存在するかどうかを測定可能であるとする.

ロボットは隣接する区画との間に壁がない場合,いつも同じ時間コストで隣接区画へ到達可能であるとする.さらに,任意の与えられた有限無向グラフに対し,2点間の最短経路を有限時間で求めることができるとする.この時,初期区画におかれたロボットの位置から目的区画までの移動するアルゴリズムを考える.

定式化

このような仮定のもと,与えられた問題をモデル化する.

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

このグラフはノード数が有限であり,エッジの重みが等しい無向グラフG=(f,V,E)\displaystyleであると言える.また,目的ノードと初期ノード間に少なくとも1つの経路が存在することになる.

また,ロボットは以下のようなエージェントとしてモデル化できる.

  • エージェントは初期状態としてグラフG=(f,V,E)\displaystyleを構成する要素のうち,ノードV\displaystyleのみ既知
  • エージェントは目的ノードと初期ノードを与えられる.
  • エージェントは現在存在するノードから接続されているエッジを計測可能
  • エージェントはグラフG=(f,V,E)\displaystyleをエッジに沿って移動可能
  • エージェントは与えられた任意のグラフに対し,2点間の最短経路問題をある定数時間K\in (0,\infty)\displaystyle以内に解くことができる.

これ以降,実際のグラフと,エージェントが記憶しているグラフをそれぞれG=(f,V,E),G'=(f',V,E')\displaystyleの記号で表す.エージェントはグラフを構成しているノード(迷路でいえば,北から数えて3マス目,東からかぞえて5マス目の区画など)は初期情報として知っている.そのため,グラフG,G'を構成する要素であるノードVは同じ集合であることに注意する.また,エージェントは初期状態では壁の接続状況を知らないため,グラフを構成するエッジVと,エッジとノードの対応関係fは違うもので構成されている点に注意する.

この時,初期ノードから目的ノードまでエージェントを移動させるアルゴリズムを求めることが問題である.

足立法とは

足立法は以下のアルゴリズムで構成される.

  1. 初期情報として,全区画間に壁がない迷路をモデル化したグラフG'=(f',V,E')\displaystyleを記憶容量の中で構築する.
  2. G'\displaystyleに対し,現在存在するノードからゴールノードまでの最短経路を計算する.
  3. 現在存在するノードv_{now}\displaystyleに対し,「測定」を行う.
  4. *実際のグラフGにおいて現在存在するノードv_{now}\displaystyleから隣接するノードの集合V_{measure}\displaystyleを得たとする.
  5. *記憶しているグラフG'においてv_{now}\displaystyleから隣接するノードの集合V_{memory}\displaystyleを得たとする.
  6. *集合\{ v|v\in V_{memory},v\not\in V_{measure}\}\displaystyleの要素であるノードv\displaystyleに対し,v_{now}\displaystyleからv\displaystyleへと伸びるエッジを縮約する作業をG'\displaystyle上で行う.
  7. 測定の結果に基づく場合分け
  8. *与えられた経路にそって移動できる場合
  9. **G'\displaystyle上で求められた経路にそって,1ステップだけエッジ上を移動する.
  10. **現在存在するノードv_{now}\displaystyleがゴールノードであれば終了.
  11. **ステップ3へ戻る
  12. *与えられた経路にそって移動できない場合
  13. **ステップ2へ戻る.

この時,以下の定理が成立する.

前節で述べた問題に対して,本節で述べたアルゴリズムを適用すると,エージェントは有限時間内に初期ノードから目的ノードへ移動する.

証明

まず,明らかに任意のステップにおいてエージェントが存在するノードv_{now}\displaystyleと目的ノード間に経路が存在する.

仮定・ステップ1の初期化設定より,e\in E ,e\not\in E'\displaystyleは起こり得ないため,|E|\leq |E'|\displaystyleが常に成立する.G,G'\displaystyleはともに有限グラフであるため,|E'|-|E|\displaystyleは有限である.

計算された経路\{v_1,e_1',v_2,e_2',...,e_{n-1}',v_n\}\displaystyleを考える.あるステップでe_1',e_2',...,e_{n-1}'\displaystyleのうちのいずれかがE\displaystyleの要素でない場合,その中で添え字が最も若いエッジe_i'\displaystyleG'\displaystyleから縮約され,|E'|-|E|\displaystyleが1減る.|E'|-|E|\displaystyleは有限であるため,ある有限のループ数k\displaystyleがあって,それ以降はe_1',e_2',...,e_{n-1}'\in E\displaystyleとなる.ゆえに,エージェントは目的ノードへ有限時間で到達する.

考察

制御空間が離散の場合は足立法は理論上も成立することが分かる.
ただし,制御空間が連続空間となった場合は成立するかどうかは不明である.

探索アルゴリズムの工夫

(そのうち分かりやすくなるかも)

これらの工夫を行うことで,アルゴリズムの性能向上が期待できる.ただし,最悪計算時間は変わらないので注意.マシンのスペック選定は,あくまで最悪のケースでも動くことが保証できるように設定すべき.

重みコストの更新に関する工夫

1歩進むごとに新たな壁情報が判明する.すなわち,ゴールまでの重みコストが変化する.現在位置の重みコストがnとすると,重みコストが変化する部分は,n以上のノードだけである.そのため,1から重みコストを計算しなおすのではなく,n以上のノードだけ重みコストの計算しなおしを行えば,必要計算時間の期待値が明らかに減少する.

仮想壁による袋小路の打ち切り

袋小路部分は最短経路・移動用経路として採用されることはない.そんな袋小路部分に仮想壁を張ることで,その部分にかかる計算量を削減する.

渦型の袋小路に有効と思われる.仮想壁情報を記録するため,メモリ使用量は増加する.

推論による壁情報の確定

ルールより,ゴール区画を除くすべての柱から少なくとも1本の柱が存在する.すなわち,柱まわりの4箇所中,3箇所が既知で壁がないと分かれば,残りの1箇所は壁が存在することが確定する.串部分の探索に有効.

壁の誤検知に弱い.姿勢制御・壁検知に自信のある人向け.

危険区画に対する重みづけ

十字路やT字路ではクラッシュする危険性が高まる.そのため,これらの分岐点は通常より高コストとみなせば安全な経路で探索してくれる確率が高まる.

やってみたがコードが複雑になるので,グラフアルゴリズム部分に自信がなければおすすめしない.(ダイクストラアルゴリズム必須.これは幅優先サーチよりコーディングが複雑)それよりかは姿勢制御部分をしっかり作ったほうが良い.

クラッシュした区画付近の重みコストをあげることも面白い.これは特定の部位に照明が強く当たっているときに有効と思われる.シミュレーション実験していないので有効性は不明.

実装例

以下に足立法の実装例を示す.以下のプログラムをコンパイル・実行すると,ターミナル(DOSプロンプト)で足立法を使って迷路を探索している様子を観察することができる.C言語をコンパイルする環境を持っていない人は,C言語を始めよう!ヘルプページなどを参考にコンパイル環境を構築すると良い.なお,実行する際は,ターミナルの横幅を大きく設定して使うこと.(コマンドプロンプトのプロパティ→レイアウトタブ→画面バッファーのサイズ・ウィンドウのサイズ欄を変更すればよい)

maze.datの内容は以下の通り.
必要に応じて探索したい迷路に書き換えると良い.違う迷路での挙動を観察することができる.
迷路の表現は座標系・迷路表現の定義#迷路表現の例で解説しているものを採用している.

参考文献

  • 加納: 情報科学のためのグラフ理論, 朝倉書店(2001)

外部リンク