BIJELAの探索アルゴリズムについて
この記事は
Mice Advent Calendar 2019 - Adventar
の15日目の記事です．
昨日の投稿はstarknighthoodさんの...あれ？
現在静岡逃亡中ということで更新されるのを心待ちにしましょう．
前回の投稿が8月で，そのあと大会に出ているのにブログ書いて無くて悲しくなっております．
もう少し頻繁に書きたいなと，毎度のことながら思います．
今回の内容
さて，今回は春に行われたMiceの技術交流会で紹介した探索アルゴリズムについて書きたいと思います．
はじめから書くと途中で力尽きてしまうので，この記事では壁情報の記録や更新，足立法が理解できている前提で話を進めさせていただきます。
まあ，足立法の解説はたくさんありますから問題ないでしょう．
今年初のハーフマウスであるTIGAを作成したにも関わらず，去年のクラシックマウスであるBIJELAの名前を使っているのは，TIGAで安定した探索ができるまで調整できなかったためです．
今回紹介する探索アルゴリズムは普通の足立法に比べ，1回の走行当たりの走行量が増えてしまうため，全日本ではコケてしまい走り切れませんでした．
不甲斐ねぇ...
足立法の改良案
去年のマウスであるBIJELAの探索アルゴリズムについて書く前に，足立法を少しいじって便利にする方法を考えます．
4マスゴール対応
まず一番に思いつくのが4マスゴール対応です．
4マスゴール対応とはその名の通り，2×2の4マスすべてをゴールとして認識することを意味します．
もちろん1マスゴールの足立法でも4マスのうちのどれかをゴールとして設定していれば必ずゴールすることができますが，ゴール内である特定のマスを目指して動くのは無駄であると思います．
また，探索のことを考えても4マスゴールにしてデメリットはないと思いますので，是非とも4マスゴール対応させましょう．
実装は簡単で，歩数マップ更新の際に1マスのゴールにセットしていた初期値を残りの3マスにもセットするだけです．
umuoumu.blog.fc2.com
Queueを用いた歩数マップ展開
一番簡単な歩数マップの更新方法は，ある歩数nを更新するために全区画の中からnを探して隣接するマスの歩数を更新，次はn+1を全区画の中から探して...という手法だと思います．
しかし，この方法ではある値を探すために全区画，16*16マスを探すためとても効率が悪く，時間がかかります．
BIJELAの場合，探索走行中に
- 区画中心で壁データの更新
- 新しい壁データを使って歩数マップを展開
- 歩数マップを用いて進路決定
- 直進orスラロームorUターン
という処理を繰り返し行っています．
BIJELAはマップの更新などの計算中も距離を加算しているため，次の動作が直進であれば，計算中に10mm進もうが100㎜進もうが問題ありません．
しかし，次の動作がスラロームである場合，3番の進路決定の段階でスラロームの前距離を超過しているとターンが崩れてしまいます．
BIJELAの600mm/s探索においてスラロームの前距離は約20mmでしたので，壁データの追加から進路決定までを33ms以内の時間で行う必要があります．
正直，そこそこのマイコンを使って計算すれば愚直にfor文を回しても34msもかからないと思います．
しかし，今後探索速度の向上や，より複雑な歩数マップ更新・進路決定を行う場合に困ることもあるかと思いますので，計算の高速化を行うに越したことはありません．
そのために紹介するアルゴリズムがQueue(キュー)というものです．
qiita.comQueueの詳細な解説は省略しますが，FIFO (First-In-First-Out)，つまり溜まっているデータを古いものから順々に処理していくアルゴリズムです．
これを歩数マップ展開に当てはめると，更新したマスの座標データを溜めて置き，そのデータを用いて更新されたマスの周辺のみ歩数の更新を行う処理が実現できます．
これによって更新されていないマスを探す，といった無駄が削減されるため，演算量の低減が可能となります．
初代のSH7125マイコンを使っていたステッパーではそこそこ計算時間が早くなった記憶があります(半分くらいとかだったかな？覚えてないですが)
詳しい実装までは書かないですが，データを追加するpush，取り出すpopの関数を丁寧に作成し，リングバッファとするためheadとtailの管理をうまく行えば実装できるはずです．
また，データをためるリングバッファとなる配列の数が少ないと簡単にtailがheadに追いつき，挙動がおかしくなってしまうため注意が必要です．
直線優先歩数マップ
これは斜めを走らない人や苦手な人，既知区間加速をたくさん使いたい，という人におすすめの話です．
ここでいう直線優先歩数マップとは，隣接するマスの歩数が同じ時に直線を選ぶ，というものではなく，直線となる方向への歩数更新を小さい値とし，ターンする方向への歩数更新を大きな値とするものを指します．
つまり，パターンに応じて更新する歩数の重みを変える必要があります．
(ちなみに，更新する歩数の値が大きくなると配列の型によってはオーバーフローが発生したりする可能性があると思いますので注意してください)
実装の方法はいくつかあると思いますが，BIJELAでは更新する方向とは反対方向の壁情報と歩数をもとに直進かどうか判定していました．
既知区間加速
既知区間加速とは探索走行中に既知区間(すでに通ったことある経路など)を通過する際に，加速して通過することで探索時間の短縮を図るものです．
これも実装の方法は何通りもあると思いますが，BIJELAは仮想的に座標を動かしていき，未知壁にヒットする座標まで早く移動する，という考えで実装しています．
基本的には直線のみ加速する人が多いですが，中には斜め走行も含めた既知区間斜めをするマウスもあるとか．
すごいです．
BIJELAの探索アルゴリズム
それでは本題としてBIJELAの探索アルゴリズムを紹介しようと思います．
このアルゴリズムのモチベーションとしては，5回しかない走行回数を何度も使って探索するのは嫌だ，という所です．
また，普通の往復足立法では「あの経路が出てたら最短したいけどあそこもう探索したっけ？」といったように最短経路が見つけられているかわからない，といった点も嫌でした．
(本記事において"最短経路=全迷路データを持っている状況での足立法ルート"とします)
つまり，1走目が終わった時点で必ず最短経路が見つけられていることが確約されるアルゴリズムを作成することを目指しました．
アルゴリズムの流れ
この探索アルゴリズムの目標はスタート座標(0,0)からゴール座標までの最短経路を出す過程で，未知壁がなくなることです．
そのため
- 未知壁は無いものとして歩数マップ展開
- 仮想的にスタートからゴールまで歩数マップを使って移動
- その過程で未知壁があったらその周辺マスを一時的なゴールとする(無ければ探索終了)
- 現在地から一時的なゴールまで足立法探索する
- 一時的なゴールについたら1に戻る
という流れをとればよいでしょう．
しかし，このアルゴリズムでは迷路の形状によっては一時的なゴールが更新されるたびに同じ経路を往復してしまい，時間を消費する割に，情報量が増えないという問題が発生します．
そこでこの問題を解決するため，未知区間優先歩数マップを作成し，この考え方を一時的なゴールへ向かう探索(4の動作)に適応させます．
するとすでに通っている区間を避けて移動しようとするため，同じ経路を取りづらくなり，多少遠回りしますが，新し壁データを収集しながら移動します．
この未知区間優先歩数マップの実装は直進優先のようにパターンに応じて更新する歩数を変更すればよいでしょう．
BIJELAでは一時的なゴールへの移動に使う歩数マップを直進優先と未知区間優先をハイブリットさせることで既知区間加速を有効に使いながら，無駄な往復を繰り返さないように工夫しています．
この直進優先と未知区間での重みをいじることで経路は変わってきます．
色々試してみる必要があると思います．
まとめ
さてこれでBIJELAに実装していた探索アルゴリズムの紹介は終了です．
このアルゴリズムの欠点としては，足立法の経路が出ることは確約されていますが，最短経路を別のアルゴリズムで出そうとしたときに，欲しい壁が未知だとその経路が走れなくなってしまいます．
そんな問題を解決できるのが全面探索ではないでしょうか．
僕は実装しないと思いますが....
便利であることは疑いようがありません．
一般的な足立法探索しか実装できていない方，ぜひ探索アルゴリズムいじってみてください．
楽しいですけれど辛かったです．
おわりに
去年の技術交流会の内容を書き直してみました．
なんとか読める記事になっているでしょうか？
間違いなどあればご指摘いただければ幸いです．
今年の機体や大会の振り返りもやりたいですが，あまり長くしたくないのでまたの機会としましょう．
また，この記事には自分が実装した機能しか書いていませんが，まだまだ工夫できる点はあると思います．
新しく実装したい機能もいくつかあるのですが，これらは実装してうまく動いたときにまた紹介できればと思います．
来年は最短経路導出もいじっていきたいと考えています．
そのためにも迷路シミュレータなど欲しいですが，卒論などですぐに身動きが取れず悲しい．
また，今年未知区間加速やクラッシュからの自動復帰を実装していた「けりさん」のマウスを見てすごいな，と心から感じました．
自分もけりさんのように頭のいいマウスを作れるよう努力していきたいな，と感じました．
明日の記事はayataka2591さんの「今年のマウスまとめ」です．
お楽しみに！
それでは
