本記事は「マイクロマウス Advent Calendar 2023」の9日目になります。
8日目は”ニシキ 新型多脚機＆新型全方向移動機製作中”さんの「マシン紹介および特有課題の解決方法」でした。
特殊な移動機構を搭載しているライントレースロボットを紹介してくれています。いや、ほんと凄いですよこれ。現地で実際に動いているロボットをみて、近くでその構造を見せてもらうとびっくりします。ブログにロボットが動いている動画を載せてくれているので、是非とも”普通でない動き”のロボットを見てみてください。
さて、本記事では自律移動ロボット「マイクロマウス」で、迷路を賢く探索するアイデアの一つ「最短経路に影響しない袋小路を閉じ、ロボットが探索しないようにする方法」について書きたいと思います。
マイクロマウスとは
マイクロマウスは小型の自律移動ロボットで走行しながら迷路を記録します。複数回走行することができスタートからゴールまでのタイムを競う競技です。
ロボットを走行させることができる時間は決められています。迷路のサイズが大きくなると時間内にすべてを探索することが難しくなってくるため、いかに早く迷路を解ける（迷路を探索しきる）かは競技として重要な項目の一つです。
ロボットが最短経路に関係しないエリアをできるだけ通らないようにすると、探索する時間を短縮する（稼ぐ）ことができます。
地方大会は持ち時間5分（7分）で、その中で5回走行できる。迷路サイズは16×16。
全国大会は持ち時間10分で、その中で5回走行できる。迷路サイズは32×32。
迷路を全面探索し、最も短い経路を見つけ、かつ5回走行をしようとすると、ロボットをきびきび動かすようにスピードを上げるか、探索に工夫を凝らさないと難しくなってきます。
特に全国大会の32×32の迷路は、スタートからゴールまでの道筋が一目見ただけではわからないレベルになってきます。全ての区画を無策で見切るのは時間的に厳しいでしょう。
走行しなくていい未探索の袋小路エリアを閉じる
ロボットが迷路を探索しているうちに徐々に迷路の全貌（壁の有無）が明らかになってきます。
ロボットにどのように探索させるかによりますが、まずは第1走目にスタート区画からゴールに向かって迷路を探索するのが一般的です。この段階では迷路の一部を通ってゴールしているため、壁の有無がわかっていない区画が多く残っている状態になります。
シミュレータの壁表示の意味
- 赤：既知の壁
- 白：既知の壁なし
- 黒（太い）：未知の壁
- 黒（細い）：未知の壁なし
- 水色：仮想壁
- 灰色（太い）：情報なし
探索する区画を増やす方法として最も簡単なものは「ゴールした後に、ゴールからスタート区画に帰ってくるようにすること」です。（設定しているゴール座標をスタートに置き換える）
この時、すでに行き（スタート->ゴール）で一部の壁の情報を持っているため、異なる経路を通って帰ってくる（ゴール->スタート）可能性があり、行きよりもより短い経路を見つけることができるかもしれません。
迷路のすべてを見にいけるわけではないので、さらに短い経路が残っている可能性があります。そこで未探索の区画をしらみつぶしにしようと全面探索を行うようになってきます。しかし全ての区画を探索するには時間かかるため、最短経路で走行する2回目以降の走行時間が少なくなってしまいます。
そのため探索不要な区画を排除して、効率的に短い時間で探索走行することが求められます。一つのアイデアとして最短経路に関係しない袋小路となる区画（エリア）を閉じる方法を紹介します。
袋小路エリアの検出と探索しなくする方法
このアイデアは私のロボット（ARROWEHAD）に実装されており、全国大会・地方大会で走行しています。この記事では考え方について記載します。（コードは結構前に書きなぐったものなのでもうスパゲッチー）
ただ通常の探索動作（足立法での歩数マップ作成、壁情報の確認・書き換え）ができれば、それらの機能を使って実現できる方法なので比較的とっつきやすいのではないかと思います。
袋小路となるエリアなのかどうかは、ロボットのいる位置から最も近い分岐区画（未知の区画につながる既知の区画）で評価することにします。
1.最も近い分岐区画を探す
まずはロボットのいる位置から最も近い分岐区画を検出です。
- ロボットのいる区画の歩数を”0″として、迷路全体の歩数マップを作成すること
- 既知の区画（4つの壁がわかっている区画）で壁がない方向が未知の区画（知らない壁情報がある区画）であることを確認する
- 歩数マップから最も歩数が小さい分岐区画を検出・記録する
2.袋小路エリアなのかを確認する
検出した分岐区画に対して、未探索の区画の先が袋小路（最短経路に関係なく、出入り口がこの分岐しかない）かを確認します。
- 検出した分岐区画の上下左右それぞれの壁で、「壁無し」かつ「隣の区画が未知」の場合、「壁無し -> 壁有り（仮想の壁を立てる。仮想壁）」とすること
- ゴール座標を歩数0として、迷路の歩数マップを作成すること
- 1で壁有りにした先の区画の歩数が更新されているかを確認すること
- 歩数が更新されず最大歩数のままの場合、その区画は分岐区画のみに出入口を持つ袋小路エリアと判断すること。
3.袋小路エリアを探索しなくする
最後に次に従い、壁情報確定させます。分岐区画の先が袋小路の場合、探索する必要がないので壁で閉じたままとします。（上記のフローチャートの最後）
- 壁有り（仮想壁）とした先が袋小路でない場合、元の壁無しに戻す。（探索する必要があるため）
- 壁有り（仮想壁）とした先が袋小路の場合、壁有り（仮想壁）のままとする。
ただし、ロボットのいる位置によっては袋小路内に閉じ込められてしまうことがあるため、その場合は元の壁無しに戻します。
どれだけ袋小路を閉じることができるかの実例
この機能を入れたロボットで迷路を探索した時の結果です。このロボットは袋小路を閉じる機能のほかに全面を探索する等のプログラムが組み込まれています。また未知の分岐区画だけでなく、既知の分岐区画もクローズするように表示しています。
右上の（15,10）区画がわかりやすいですが、仮想壁（水色）を立てて袋小路と判定し、袋小路の中を探索しないようにできています。
右上の（15,15）のような小さな袋小路を閉じるのみの場合も、袋小路を調べるために既知の区画を長々と走ることが減るため、ロボットが移動する歩数（時間）を抑制することができます。
他の迷路も見てみましょう。
迷路によっては、未探索エリアを大きく閉じることができることもあれば、小さな袋小路を閉じるのみになる迷路もあります。
未知区画を閉じる区画数に大小はありますが、探索しなくてよい領域・区画を検出して走行時間を短くすることができます。
迷路の探索を賢くする実践面での難しさ
袋小路を閉じるアイデアを紹介しましたが、他にも迷路の探索を賢くする方法は多々あります。例えば、いくつか未知の区画があったとしても、歩数的に検出できている経路が最も短いルートあることを判断することなどです。
アイデアとしては思いつきますが、難しいことは、そのアイデアをバグなくコーディングすること、そしてアイデアが本当に効果的なのか確認することです。（これはいける！と思ったことも、実際にやってみると全然効果ない！！など、よくあることです。。。）
迷路の探索方法を考えるうえで、迷路探索を検討するためのシミュレータは必須だと思います。シミュレータを使うことで、短時間でいろいろな迷路を探索し試すことができます。というよりも実機を書き換えて走るなど時間がかかってやっていられません。大きな迷路も自宅に無いので試せません。
マイクロマウス本体を作るのも大変なのに、さらにシミュレータを作るとなると、、、なかなか大変です。こういったところが迷路探索方法を改良しようとするとハードルになってきてしまうかと思います。
マイクロマウスの上位陣は自前のシミュレータ（迷路の探索に限りません）を結構作っている印象です。やり方・言語などは様々でC#、Python、MATLABなどなど。作り込まれているシミュレータは本当にすごいです。ぜひ大会で見せてもらってください。
私は拙いながらもQtを使い、C,C++で迷路探索のシミュレータを作っています。Qtでシミュレータを作るやり方は、同じくマイクロマウスの競技者であるsoraさんがブログに書いてくださっている「Qtを使用した迷路シミュレーターを作る (Qtのことはじめ編)」がとても参考になります。
またC,C++でコーディングするときに、書き方を実機と統一すれば、シミュレータで書いたコードをそのまま実機のソースにコピペすることで、とても楽にロボットへの実装ができます。
ハードルはありますが、シミュレータを作れるようになると迷路探索だけでなく、走行ログを表示するなど応用がききますので学習・実践することを勧めます。
まとめ・終わりに
マイクロマウスの探索で、袋小路を探しだし、未知の区画（エリア）を探索しないようにする方法を紹介しました。意外と簡単に袋小路を探し出すことができます。
マイクロマウスは競技として、最短の速さを競っているので吸引などのアイテムを先に実装したくなってくると思いますが、ぜひ探索にも目を向けて、自分のロボットをもっと賢くしてみましょう。（私自身まだまだうまく探索はできていませんが、ロボットの探索を効率化するよう励んでいます）
以上で本記事は終わりです。明日の「マイクロマウス Advent Calendar 2023」は、kerikun11さんの「今年のマウス進捗について」です。kerikun11さんのマイクロマウスも、とても賢いロボットです。今年はどのようなアイデアを入れてくるのか楽しみです。見逃せません！
