2013年3月4日月曜日

全面探索

とりあえず今年作ったマウスも去年のマウスもある程度走行性能が確保できました。

次に考えるのはより良いルート選択ということになりますが、これは主に2つの要素が絡みます。

①最短経路導出プログラム
②迷路壁情報の必要十分数取得

①については現行のプログラム上の定数を変更すれば対応できると考えています。
今のところ不当に直線の重みづけが小さいので、それを変更すればもっと良くできます。

②については基本的に全面探索を行うのが良いと考えています。
そこで、効率はともかく全面探索するソフトウェアを作成しました。
シミュレータ的なものを作れないので実際に走行して、それっぽいことができることを確認しています。

video


袋小路カットとか1柱に壁が3か所無ければ勝手に壁入れるとか細かな工夫もそうですが、あとはいつ打ち切るかというのが重要な気がしますね。

絶対に入れるべきなのはタイムアップ処理で、とりあえず3分経っても終わらなかったらスタートを目指すようにしています。全日本では終わるわけがないですが、これ以上安定して迷路を走り続けられるか不明で、2回探索できるくらいのタイムということで、、、

本当は未探索区画の壁がなかった場合とあった場合で最短経路を割り出し一致するまでとかにしたいですが、探索走行中に最短経路導出は厳しいですね、、、
いちいち停止してもいられませんし。