プロジェクト / Basic Mouse 2003

３．迷路探索アルゴリズム

迷路探索アルゴリズムには、左手法、求心法、トレモー法、足立法、その他様々なアルゴリズムが提案されている。しかし、私はそんなアルゴリズムを知らないし、調りゃわかるだろうけど、アルゴリズムを考えるのが面白いので、自分で好き勝手に探索アルゴリズムを考えることにした。

私が好き勝手に考えたアルゴリズム、とはいっても、世の中にすでにありそうな感じ。分類から言えば、等高線マップ法とか、フロントウェーブ・アルゴリズムあたりがそれらしい。名前はともかく、数理計画問題でよく出てくる最適化手法と同じように、「ポテンシャルが小さくなる方向に向かって移動する」という考え方を基本として最短経路を計画することにした。

（その名称が正しいかどうかは知らないが）仮に本探索アルゴリズムを等高線マップ法とよぶことにして、アルゴリズムの基本的な考え方を説明する。本アルゴリズムは、簡単に言えば、

「壁が存在せずポテンシャルが小さくなる方向を選択してそちらの方向に進み、センサが壁を検知したら壁情報のマップとポテンシャル情報のマップを更新する。」

という単純なものである。

　例えば図3.1 のような４×４迷路の左下隅S（０，０）からスタートして、右上隅G（３，３）まで走行するとする。

走行前は、マウスは迷路の壁情報を知らないので、外周以外は壁が存在しないものとしてマップを用意しておく。そのマップを元に、ゴール位置からの距離（歩数）を記録したマップを生成すると、図3.2 のようになる。（歩数だけでなく、折れ数も数えてマップを生成してもよい。）

マウスは「壁が存在せず、ポテンシャルが小さくなる方向」を選択してそちらの方向に進み、センサが壁を検知したら壁情報のマップとポテンシャル情報のマップを更新する。　例えばマウスが迷路中を（０，１）、（０，２）、（０，３）、（１，３）と進んだとすると、マップは図3.3 のようになる。

さらに進むと、次は（１，２）に進むことになる。マウスが（１，２）に進むと、マップは図3.4のようになる。

図3.4 の状態から本アルゴリズムにしたがってさらに探索を進めると、（１，３）、（０，３）、（０，２）、（０，１）を通って（１，１）に到達する。（図3.5）

さらに歩を進めて（１，０）、（２，０）、（３，０）を通って（３，１）に到達すると、マップは図3.6 のようになる。

さらにさらに歩を進めて（３，０）、（２，０）、（２，１）、（２，２）を通って（２，３）に到達すると、マップは図3.7 のようになる。

（さらに）＾３探索を続けると、マウスは（２，２）、（３，２）を経てゴールの（３，３）に到達する。

以上のように、壁が無くてポテンシャルが小さい方向に進み、新しい壁を検出したらマップを更新するという作業を繰り返すことで、常に最短経路でゴールに向かうように探索を進めることができる。（ただし、帰り道はポテンシャルが大きくなる方向に探索しても、スタート地点には戻れないことに注意）

また、一度ゴールに辿り着いた後で迷路の全区画探索を行う場合も、現在位置から最も近い未探索区画をゴールに見立てて探索を繰り返すことで、最短経路で全区画探索を行うことができる。　

マウスが左下隅Sまで戻っていれば、図3.5 の水色で示したポテンシャルが小さくなる方向に辿って行くコースが最短経路であることがわかる。したがって、最速走行時はこの経路を走行すればよく、迷路探索と同じアルゴリズムで最短経路計画も一緒にこなすことが可能である。

以上が本探索アルゴリズムの基本的な考え方である。

（書いた後で気づきましたが、ロボコンマガジンNo.13のpp60-64 に、等高線マップ法の説明がバッチリ書いてありますね。私のアルゴリズムは、等高線マップ法そのものなようです。）

マイクロマウス制御プログラムの要求仕様を収集する際にリスク管理表を作成したが、探索アルゴリズムもリスクに入っていた。そのリスク回避策として、制御プログラムを設計する前にシミュレータで探索アルゴリズムの検証を行い、第1回〜第21回の（エキスパートクラスの）迷路でゴールまで到達できることを確認した。

（シミュレータは谷口氏作のマイクロマウスシミュレータを使用した。http://www.kit.hi-ho.ne.jp/stack/index.html、　シェアウエア\1,280-）