カブトガニ野郎 - マシン情報
迷路探索シミュレータの製作 - マイクロマウス †
最新バージョン(2014年1月〜) †
経過 †
目標 †
- GUIベースのシミュレータにするため，Qtを使用してみる
- 斜め走行などの実装を行うため，グラフ生成部分を大幅に変更する
- 前回同様最短経路探索はA* algorithm
- 迷路探索部分とシミュレータの表示部分を分離することで，移植を簡単にする
方針 †
迷路に対して下の図のようなグラフを生成すれば斜め走行も簡単に考えられるのでは・・・？
ノード数は$2n(n-1)$，エッジ数は$6n^2-12n+4\ (n\geq 2)$
進捗どうですか †
27th Jul. †
コミットログ
メモリ消費を極力減らすためにデータ構造を大幅に変更した．
動作はほとんど変わりなしだが，軽微な修正や若干動作の怪しい部分も含まれている．
当初目標にしていたロジックの分離が完了，マイコンへの移植もできたので，そろそろAgentクラスとセンサ情報とをつなげるための仕組みづくりをしようと思う．
1st Feb. †
コミットログ
エージェントを実装した．それと同時に数カ所に埋まっていたバグを取り除いた．
ステップ実行のほか，QTimerを使った自動実行もできるようにした．
さらに，地味にWindowsでも動くようにコードを書き換えた．
11th Jan. †
コミットログ
A*アルゴリズムっぽい何かを実装した．
これによって，特にエッジの個数が多い状態，すなわち32x32の迷路内を探索走行中の際，経路決定にかかる時間の大幅な短縮が期待できる．
次はエージェント(迷路内の探索を行うAI)の実装を行う．
- Dijkstra法による初期状態での最短経路導出(従来方式)
6th Jan. †
コミットログ
とりあえず重み付けも何もなしで，真の迷路情報から最短経路の導出だけさせるようにした．
何もしてないのに比較的良好な結果が得られた．
過去のバージョン(2013年1月〜11月) †
経過 †
目標 †
- 足立法を利用した迷路探索アルゴリズムの検証を行いたい
- 単純な歩数マップではなく，汎用性を確保するためDijkstra法による最短経路探索を行う
- 探索フェーズと最短走行フェーズをシミュレートできるようにする
足立法とは? †
Micromouse_zero @Wiki 足立法(歩数マップを使った分かりやすい説明)
足立法 - マイクロマウス委員会関西支部(正当性・停止性の証明アリ)
足立法は，マイクロマウスのようにスタートとゴールの位置のみがわかっている迷路を探索しながら解くアルゴリズムの一つである．
まずは壁がどこにもないと仮定して，スタート地点からゴールに向かって進む最短経路を導く．
その経路に沿って壁を検出しながら進み，進行方向に壁を見つけた場合，それまでに得た壁情報を利用して再度最短経路を導出する．
これを繰り返し行うことによって，比較的高速に，かつ確実にゴールに到達することができる(証明は上記2番めのリンクを参照)．
歩数マップとDijkstra法 †
以下，ノード(マス)の総数を$V$，エッジ(隣接2マス間の通路)の総数を$E$とする．
歩数マップ †
歩数マップの作成は非常に簡単なアルゴリズムで実現できる．
ゴールからスタートに遡るようにして，かかる歩数を順に計算していくだけでよい．
簡単なアルゴリズムであるが，曲がり角に対する重み付け(旋回にかかる時間を考慮)や危険区画(環境光が局所的に強いなど)の回避などを実現することも容易であり，汎用性は高い．
最も基本的な歩数マップ作成にかかるオーダーは$O(V)$である．(最悪の場合でもマスをすべて調べ上げればよい)
ただし，斜め走行や進入する方向などを考慮したときや，長い直線に対する重み付けなどを考えた際に，最終的にアルゴリズム全体として複雑なものになってしまうのが難点である．
Dijkstra法 †
そこで，グラフの概念を導入して最短経路問題を解くことを考える．
グラフは，ノード(節)とそれを結ぶエッジ(枝)によって構成される構造である．
迷路においては，マスをノード，隣接2マス間の通路をエッジとして考えることができる．
Dijkstra法は，グラフ上の2つのノード間の最短経路を求めるアルゴリズムである．
ダイクストラ法 - Wikipediaに，アニメーションによる図解がある．
アルゴリズム自体の解説はダイクストラ法(最短経路問題) - deq notesが分かりやすいので割愛する．
Dijkstra法のオーダーは，単純な実装では$O(V^2)$であるが，優先度付きキューを用いた実装では$O((V+E)logV)$となる(要検討)．
斜め走行等を考えない場合，$V=16\times16=256$マスに対して，最悪のエッジの数を考えると$E=15\times16+16\times15=480<2^9=512$なので，5000〜10000回ほどのループで実行できるため，マイコンでも十分に計算が可能である．
(ただし，メモリの容量やグラフの縮約の処理，データ構造そのものの処理にかかる時間などは考慮されていないため，実際には厳しい部分もある)
エッジのコストを変化させる処理を加えるだけで，様々な重み付けに対応できる．
また，隣接しているマスのみならず，斜め方向や遠くのマスへのエッジを作ることによって，斜め走行や長い直線を考慮した最短経路(最速経路)を導出することができるのも大きなメリットである．
実装の方針 †
- Dijkstra法を使うため，グラフ関係のクラスを実装する．Node，Edge，それらを統合したGraphの3つのクラスを作成する．
- 迷路のデータは座標系・迷路表現の定義 - マイクロマウス関西支部をもとに拡張したデータを，グラフとは別のMazeクラスで持っておく
- 最短経路導出のたびにMazeオブジェクトからGraphオブジェクトを生成しなければならないためどうにかしたい(未解決)
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
astar_emptymaze.png
dijkstra_emptymaze.png
