2013年3月4日月曜日

全面探索

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

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

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

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

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

video


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

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

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

5 件のコメント:

  1. 「1柱に壁が3か所無ければ勝手に壁入れる」はハーフではやっちゃだめですよ.

    返信削除
    返信
    1. ゴール付近のことをおっしゃってるんでしょうか?

      削除
  2. すみません.2012年にこっそりルールが改定されていました.それ以前は2-4の規定がなかったはずです.

    クラシックでは昔から規定2-4があったのにハーフの規定が作られたときに削除されていたので柱ばっかりの迷路がそのうち出るんだと思ってましたが,方針が変わったんですかね.

    返信削除
    返信
    1. よく見てみると,
      2009年1月16日制定では規定2-4あり,
      2010年5月6日改訂ではなし,
      2012年10月17日改定で復活,
      ですね.裏でいろいろあったんでしょうね.知りませんでした.わざわざ2-4を使わないようにしていたんですが,昨年の大会では実は使ってよかったなんて.ルール変更がないかは毎年確認していますが,さすがに10月に改定されるとは思ってないので見ていませんでした.

      削除
  3. 自律賞の変更とか、探索賞の廃止など、競技者間で取り沙汰される規定変更は知ってますが、微妙なところも結構入れ替わってるんですね。知りませんでした。

    返信削除