過去の全日本マイクロマウス大会32x32迷路の分析

2020-03-08

説明記事

マイクロマウス, 迷路

はじめに

こんにちは。けりです。
今回はマイクロマウスの迷路探索のお話です。

過去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年分の迷路の最短経路の例を以下に示します。

色	評価方法
黄色	台形加速とスラロームの時間を考慮した斜めありの最短経路
シアン	台形加速とスラロームの時間を考慮した斜めなしの最短経路
青色	区画の中心を頂点とした足立法最短経路(参考)
マゼンタ	壁の中心を頂点とした足立法最短経路(参考)