過去の全日本マイクロマウス大会32x32迷路の分析
はじめに
こんにちは。けりです。
今回はマイクロマウスの迷路探索のお話です。
過去10年分のマイクロマウス全日本大会の32x32迷路を比較してみました。
まずは探索走行の比較を、次に最短経路の比較を紹介します。
対象とする迷路
今回対象とする迷路は、 過去の全日本大会のマイクロマウス(旧ハーフサイズ)競技決勝、32x32の迷路です。
2010年から始まった競技なので、現在は合計10個の過去迷路が存在します。
それら10個の迷路について比較を行っていきます。
探索の比較
まずはじめに、探索走行についてみていきます。
最短経路を探索するために要した歩数などを評価します。
探索アルゴリズム
今回使用するアルゴリズムは、 スタート直後から、 常にスタート区画からゴール区画への最短経路上の未知壁を 潰していく探索アルゴリズムです。
これは、私がマイクロマウスに実装している探索アルゴリズムです。
いろいろな探索アルゴリズムを試した中で一番効率がよかったアルゴリズムを用いています。
探索走行時間の見積
探索の際の前進、右左折、転回などにかかる時間を加算することで、探索走行時間を見積もることができます。
今回は以下のようにパラメータを設定しました。
| 項目 | 値 | 備考 |
|---|---|---|
| 未知の直進 | 300 [ms] | 速度 300 [mm/s] |
| 既知の直進の最初 | 300 [ms] | 速度 300 [mm/s] |
| 既知の直進の連続 | 150 [ms] | 速度 600 [mm/s] |
| 右折・左折 | 237 [ms] | 速度 300 [mm/s] |
| 転回 | 3000 [ms] | 前壁補正に時間がかかるので |
既知区間加速を考慮して、 既知の直線が連続する場合は2番目以降のコストを半減させています。
結果
結果は次の表のようになりました。
| 年 | 見積時間 | 総歩数 | 直進 | 左折 | 右折 | 転回 |
|---|---|---|---|---|---|---|
| 2010 | 6:24 | 962 | 514 | 200 | 194 | 54 |
| 2011 | 6:03 | 1064 | 535 | 250 | 238 | 41 |
| 2012 | 4:07 | 938 | 595 | 159 | 167 | 17 |
| 2013 | 4:07 | 956 | 669 | 129 | 141 | 17 |
| 2014 | 5:11 | 1186 | 703 | 246 | 218 | 19 |
| 2015 | 4:25 | 1056 | 699 | 175 | 167 | 15 |
| 2016 | 6:46 | 1210 | 577 | 305 | 285 | 43 |
| 2017 | 5:05 | 1046 | 596 | 216 | 210 | 24 |
| 2018 | 5:35 | 1268 | 957 | 144 | 140 | 27 |
| 2019 | 6:31 | 1330 | 791 | 265 | 241 | 33 |
探索時間の傾向
年々著しく増加していると思いきや、 初回の2010年でも結構時間がかかる迷路だったようです。
探索時間の目安
ばらつきが多いのでなんともいえませんが、 短いときだと4分ほど、 長いときだと6分半ほどかかるようです。
マイクロマウス競技は持ち時間が10分なので、これでは最短走行の時間に残された時間が少なめです。
やはり途中でタイマーなどで打ち切ってスタートへ戻るのがよいでしょう。
まとめ
普段私はこの見積探索時間を短くするべくアルゴリズムの改良を行っています。
したがって、この結果は平均的に探索時間が短くなるようなアルゴリズムを使用した結果です。
探索アルゴリズムには得意な迷路と苦手な迷路があり、 どんな迷路に対しても有効な最強アルゴリズムはおそらくないように思えます。
過去迷路で有効だったアルゴリズムも新たな迷路では最悪ケースを引き当てるかもしれません…
なので、なるべく多くの迷路で評価を行うと良いでしょう。
ちょっとした工夫次第でかなりの時間短縮になったりするので、 今後も改良をしていきたいと思っています。
最短経路の比較
次に最短経路の比較をみていきます。
コスト
今回は、次のようなコストを設定し、走行時間ベースの最短経路を導出しました。
| 項目 | 値 | 単位 | 備考 |
|---|---|---|---|
| 基本速度 | 420 | [mm/s] | ターン速度の平均値 |
| 飽和速度(壁沿) | 1500 | [mm/s] | |
| 飽和速度(斜め) | 1200 | [mm/s] | |
| 加速度(壁沿) | 4200 | [mm/s/s] | |
| 加速度(斜め) | 3600 | [mm/s/s] | |
| 最短45度 | 249 | [ms] | #1 にかかる時間 |
| 最短90度 | 375 | [ms] | #2 にかかる時間 |
| 最短135度 | 465 | [ms] | #3 にかかる時間 |
| 最短180度 | 563 | [ms] | #4 にかかる時間 |
| 最短斜め90度 | 388 | [ms] | #5 にかかる時間 |
| 最短小回り90度 | 287 | [ms] | #0 にかかる時間、斜めなしで使用 |
各ターンについて詳しくは過去の記事・マイクロマウスのターン一覧 をご覧ください。
結果
以下に各年毎の最短走行の時間を示します。
最短走行時間
最短走行時間を表示する都合上、横向きのグラフになりました。
最短経路の傾向
やはり、最短経路の走行時間は年々増加傾向にあります。
16x16の迷路では経路長にも限界がありますが、
32x32の迷路ではこれらよりずっと長い経路を作ることができるので、
今後も増加傾向は続くと思われます。
斜め走行の効果
斜めありと斜めなしで大きく差が出る年もあれば、 ほとんど変わらない年もあります。
ただ、やはり斜めありのほうが圧倒的に早くなることがよくわかります。
斜め走行、頑張りましょう…
経路
最後に、過去10年分の迷路の最短経路の例を以下に示します。
| 色 | 評価方法 |
|---|---|
| 黄色 | 台形加速とスラロームの時間を考慮した斜めありの最短経路 |
| シアン | 台形加速とスラロームの時間を考慮した斜めなしの最短経路 |
| 青色 | 区画の中心を頂点とした足立法最短経路(参考) |
| マゼンタ | 壁の中心を頂点とした足立法最短経路(参考) |
全日本マイクロマウス大会2019
全日本マイクロマウス大会2018
全日本マイクロマウス大会2017
全日本マイクロマウス大会2016
全日本マイクロマウス大会2015
全日本マイクロマウス大会2014
全日本マイクロマウス大会2013
全日本マイクロマウス大会2012
全日本マイクロマウス大会2011
全日本マイクロマウス大会2010
台形加速を考慮することで、直線の多いルートが選択されていることがわかります。
おわりに
今回は過去10年分の迷路の探索走行時間および最短走行時間を比較しました。
最短経路の計算に使用した走行パラメータは、 KERISE v4 のものなので、 絶対値は当てにならないかもしれませんが、 最短ルートや年毎の推移などは参考になると思います。
もっと効率のよい探索アルゴリズム求む
今回使用した探索アルゴリズムは現時点での自信作です。
是非、あなたの探索アルゴリズムと比較してみてください。
そして、もっと効率のよい探索やいいルートをご存知の方は是非共有してください！！
お待ちしております。