マイクロマウス2017HX決勝迷路の探索結果

先日、全日本マイクロマウス大会2017 が開催されました。結果報告の記事はこちら

ハーフサイズエキスパートクラス決勝の32x32迷路は、サイズが大きすぎて(私の知る限り)どの団体も所持しておらず、年に一回全日本大会でしか見ることができない激レア迷路となっています。

今回はその迷路の探索結果についてお話しします。

KERISE v3-2の探索アルゴリズム

KERISE v3-2 の迷路探索アルゴリズムの特徴は以下の通りです。

• 足立法を基にゴールを目指す
• ゴールについた後の追加探索ではステップマップ上の最短になり得る未知壁を潰していく
• 未探索壁があっても、最短になり得ないと判断した壁は見に行かない
• どんな迷路に対しても必ず歩数最短経路を導出することができる
• 直線加速やターンの曲がりやすさなどは考慮されておらず、あくまで歩数ベースなので、あまりよい最短経路は導出できない

今後ターンにコストを振った経路導出を実装したいと思っています。

課題迷路と探索結果

赤の点線で表された壁は、見切り壁で、最短になりえないと判断した壁です。

※迷路画像はマイクロマウス運営ページ から引用しました。

全日本2017ハーフサイズエキスパート決勝

小さくて見ずらいので、画像をクリックしてご覧ください。

近年のHX迷路の探索結果比較表

去年(2016年)の迷路は、ゴール区画がスタートに近いせいでほぼ全面探索になってしまい、探索歩数が明らかに多いですね。厳しいです。

まとめ

今年はハーフサイズ初挑戦ということもあり、時間超過にならないように、なるべく短時間で探索を終えるアルゴリズムにしました。

なので、未探索の壁が結構多くありますが、歩数最短のコースはしっかり導出できました。

来年は、歩数ベースではなく時間ベースの最短経路導出ができるアルゴリズムで臨みたいです。