迷路最短経路
こんにちは。エヌがのです。
とうとう今年度もマウスシーズンが始まりましたね。自分はというと、大学院試験に合格し、とりあえず一息しているところです。マウスの方は、ハーフのほうがそろそろ動くかなといったところです。現役時代とは違って手元に迷路が無いので調整をどうしようかと考えています
今回は、そろそろ本格的に最短経路について、距離ベースのものから離れようと考えまして、最短経路導出プログラムの改良を行いました
改良した結果がこちらです
これは去年の全日本のエキスパート決勝です
速度は、
直進:3500mm/s, 加速度12000mm/ss, Turn90: 1200mm/s, Turn180: 1200mm/s, Turn45: 1200mm/s, Turn135: 1200mm/s, Turn90V:1200mm/s
となってます
去年の迷路は右回りの経路が距離的に長く、右回りを選択している人はいなかった覚えがあるのですが、このシミュレータでも速度パラメータをどう変えても右回りに行くことはありませんでした。ルート的にはとてもおもしろいので少しもったいないと思いました
アルゴリズム自体ですが、ダイクストラ法を参考にして組んでみました。正直言いますと、ダイクストラ法自体理解できていないので、参考になっているのかどうか怪しいです。ただ、ノードとエッジとコストで色々管理するという手法をとっているだけです
最短経路導出の手法については、特にこれといって特別なことはしておらず、ただ、初期座標からゴール座標までエッジをつなげていって、最もコストが低いルートが最短であるとしているだけです
このアルゴリズム、ルートを作成する時点でかなりの計算量になるのですが、面白いことに、総計算時間はおよそ1秒程度となりました。
さらに、PCで1秒かかるのだからRXマイコンなら10秒ほどかかるのではないかと危惧していましたが、実際に実装して同じ迷路で最短導出の計算をさせるとPCと同じ1秒ほどで終わりました。PCの内部処理には疎いため理由はわかりませんが、PCのほうがきっと本気を出していなかったからではないかと(適当)。
ということで、実装には十分なアルゴリズムと分かったので、今シーズンはこれを使っていこうと思います
色々な迷路の最短経路を導出してみました
2013年度全日本大会クラシックエキスパート決勝
2012年度全日本大会クラシックエキスパート決勝
2011年度全日本大会クラシックエキスパート決勝
2014年度東日本大会クラシック
2013年度東日本大会クラシック
これを見ると、個人的には全日本の迷路より東日本の方がアルゴリズム的には面白いと思ってます。難易度は全日本のほうが高いのですが、東日本は距離が同程度のルートが多く、さらに斜めのルートが隠されていることが多いためシミュレートしがいがあって楽しい。
現在は各ターン等のコストが固定なので、これを実際の走行と同じようにコストもシミュレートしながら経路導出が出来ればと考えています。