DATE: 2017/03/12(日)   CATEGORY: 未分類
探索シミュレータVer.2報告会(2)

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

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


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

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

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




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

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

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

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

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

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

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

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




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

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

[広告] VPS


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

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

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

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

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

[広告] VPS

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

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

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

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

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

かなしいな~

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

おしまい

スポンサーサイト
Copyright © うむ夫の歩み. all rights reserved.