DATE: --/--/--(--)   CATEGORY: スポンサー広告
スポンサーサイト
上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。
page top
DATE: 2017/03/12(日)   CATEGORY: 未分類
探索シミュレータVer.2報告会(2)

5.探索アルゴリズムの改良
ここからは備忘録を兼ねた試行錯誤の記録。
基本的に使っている探索アルゴリズムは以下のような方法。
① 既存の壁情報で経路導出を行う
② 経路上の一番ゴールに近い未知壁のある区画を仮ゴールに設定
③ 仮ゴールに向けて探索
④ 既知壁のみの経路が導出されるまで①~③を繰り返す

既知壁だけの経路=残りの未知壁部は行く必要のない経路であるという
仮定の下(重要)この探索アルゴリズムを用いている。


とりあえず昨シーズンからの変更点として、
経路導出の部分を通常歩数マップから
斜め対応直進優先歩数マップに変更しました。

この方法での問題は
探索しているうちに経路が変更された場合に大きく振り回されることでした。

たぶんこんな感じ(当時はバグあり)




いろいろ考えた結果、
経路上の一番ゴールに近い未知壁のある区画を仮ゴールに設定する
部分に原因があるのでは?となりました。
そしてこれを解決するために、
経路上の今一番近い未知壁のある区画を仮ゴールに設定する
方法を考え始めました。

経路上の未知壁のある区画(仮ゴール候補)の中で一番近い区画
を探す方法…?

①全ての仮ゴール候補から歩数マップを展開してその歩数を比較?
→計算時間がかかり過ぎるため却下

②今の地点から歩数マップを展開して最初に当たった位置を仮ゴール?
→よさそう。やってみよう
→でもそれって経路導出、仮ゴール決定、探索用歩数マップの計3回する必要?
→うーん…

と悩み続けていました。しかし、とある日最高の考えを思いつく。

"全部ゴールにして歩数マップにしてしまえばいいのでは!?"

そこで手にしたのが複数の任意区画をゴールにできる探索用歩数マップ。
これを使えば、経路導出、探索用歩数マップの計2回の展開で済む。
完璧である。

実際にやってみたのがこちら(当時はバグあり)




結局振り回される。
しかし成果はあった。おそらく原因としては、
探索が行えていない領域は一旦候補から外れても
後で最候補になる可能性があるからだという結論になった。

それならば話は早い。
ゴール候補の履歴をとってすべてをゴールにしよう!
それで完成した探索がこちら。

[広告] VPS


無理に振り回されることが減り、じわじわと探索領域が広がっている。
僕は満足した。

後は無駄なゴール候補が残ったままになってしまう場合があるので
それを解消する方法を考えればいいだろ(ヘラヘラ
と思いながらいろいろな迷路でデバッグを行っていった。

誰もが知っている通り、世の中そんなにうまくはいかない。
しばらくすると不思議な光景を目にする。
ん?探索情報と全面情報でパスが違う迷路があるぞ?

2016年の迷路では2つ。
全日本クラシック・フレッシュマン決勝とクラシック・エキスパート決勝
ちなみにこちら。

2016全日本フレッシュマン経路比較

[広告] VPS

歩数マップを出力し確認してみたところ
展開アルゴリズムのバグではなく仕様のようである。

これが意味することは、
「斜め対応直進優先歩数マップでは
迷路条件によっては未知壁=壁が無いとして生成した
既知区間のみの経路でも完全な経路が出ているわけではない」
ということである。

そう、既知壁だけの経路=残りの未知壁部は行く必要のない経路であるという
仮定は間違っていました。

未知壁の無いエリアは歩数マップのコストを低下させることは
あっても上げることはないと思っていましたがそんなことはありませんでした。

廃案とまではいかないが、より高度な改良の必要が出てきたところで
今年の探索シミュレータ開発は諦めました。

かなしいな~

対策を今シーズンを通して考えていきたいです

おしまい

スポンサーサイト
DATE: 2017/03/12(日)   CATEGORY: 未分類
探索シミュレータVer.2報告会(1)

2017年になり今年もマウスを頑張っていこうと思っていたら
気がつけば3月になっていました。

時が進むのが早過ぎる。

先日今年になってから行っていた
探索シミュレータVer.2が完成したのでその報告です。
シミュレータ合宿(非公式)などもして楽しかったです。
マウス本体の方はもう少し時間がかかりそう。

主にやったことは以下の通り。

1.壁情報の保存方法の変更
2.全体的なソースコードの整理
3.アイコンをかわいくした
4.昨年マウスに実装したアルゴリズムのシミュレータ実装
5.探索アルゴリズムの改良

1.壁情報の保存方法の変更について
昨年のシーズンにかつて元部長が言っていた方法を取り入れてみた。
理由はフレッシュマン世代に教えるためであったが、
やってみると個人的にはこっちの方が使いやすい。
メリットなどは参考記事を読みましょう。

元部長の参考記事はこちら

Miceでは多数派であった1区画あたり8 bitを割り当てる方法
を使っている人は新作で変えてみるのはありかもしれないです。

自分はこんな感じで壁情報保存配列を用意しています。

壁情報

bitがx座標、配列の番号がy座標というイメージ。
入れるときは、壁情報[y]|(1<< x)
消すときは、壁情報[y]&(~(1<< x))
壁情報にアクセスできる関数を作っておけば気持ちがいいですよ。


2.全体的なソースコードの整理
前回の探索シミュレータはフレッシュマンを終えて
テンションに身を任せて作成したものでした。
今年読んでみたらあらわからない。
まあ壁情報の変更も兼ねて整理するよね。

探索シミュレータはマイクロマウスをやる上で
必ず必要なものではないけれどあると便利です。
真面目な顔をしてPCを開いていれば、堂々とマウスをやれる。

また、自分みたいな初心者にはプログラムを書く練習だったり、
シーズンで学んだことを一度整理するいい機会になるので
まだ作ってない人は挑戦してみては?


3.アイコンをかわいくした
(・8・)

アイコン紹介


4.昨年マウスに実装したアルゴリズムのシミュレータ実装
昨年実装したもので特別な物は
おそらく直進優先歩数マップと斜め対応直進優先歩数マップ。
前者については以前書いたので省略。今回は後者について解説です。

ベースとなる考え方はこちら

これについて直線的に展開を行っている。
通常の直進優先歩数マップは4方向のみの展開でした。
斜め対応直進優先歩数マップは8方向について展開しています。
以下に出力例を示します。重みの参考値として、直進14減少2,斜め10減少2。
迷路は2016年全日本クラシック・エキスパート決勝

2016全日本斜め優先歩数マップ


これの良いところはこれだけで"簡単に""ある程度"良い経路が見つかるところです。
例えば、2016年東日本地区大会クラシック迷路の経路比較。

2016東日本経路

こちらは、2016年九州地区大会クラシック迷路の経路比較。

2016九州経路

経路の違いによる走行タイムのシミュレーションを行っていないため
正確な差はわかりませんが、
速度を出せそうな経路を通れていると思います(願望)

また、重みのバランスを変更することにより
斜めを避けたり逆に斜めを優先させたり
マウスの特徴に合わせた経路選択が手軽に行えます。
重みパラメータを変更して経路比較はやってみたいですね。
簡単に上位陣の経路に近い経路を探せます。

現状の欠点は、単純に直進を優先して展開しているだけなので
効率の良いターンの選択が行えないことが挙げられます。
これは2017年の課題ですね。

一旦ここで区切って5についてはもう1つ記事で書こうと思います。
続く…

Copyright © うむ夫の歩み. all rights reserved.
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。