ステッパーでも全面を走りたい！！

この記事はWMMC Advent Calendar 2025の13日目の記事です。
https://adventar.org/calendars/12322

謝罪

がっつり遅れてしまいました。書いている現在は既に12/20日の明け方です。
申し訳ございません。

概要

この記事はステッパーマウスでも全面探索を行いたいな～、いい経路を出したいな～というマウス1年目の素人によって書かれています。

はじめに

自分はこれまでに東北地区大会と全日本学生大会への出場経験があるのですが、そのどちらでも全面探索は行っておりません。ただ自分が大会へ出場している中で華麗に全面探索を決めて最適な経路を導出している先輩方を見て自分もやってみたいという欲求が生まれました。スタートとゴールの単純な足立法による往復では出しえない経路を導出できるというのは何とも魅力的です。

課題

そんな中で自分は東日本地区大会へ向けて全面探索を行う決意を固めたのですがここで大きな課題が生まれます。それは時間が足りないということです。これはかなり自分にとって深刻なことでした。なぜなら自分が持っているステッパーマウスでは安定して探索ができる速度は500mm/sであり、これではすべてのマスを回っていたら二次走行を行う時間は残りません。何なら効率の悪い全面探索を行えば一時走行だけでもかなり厳しくなってしまうかもしれない状況です。

解決策

そもそも全面探索を行わない　←　何を言ってるんだという話ではあるんですが自分がそもそも全面探索を行う目的はスタートとゴール間の単純な往復では出しえない良い経路を出すことであったため、それが達せられれば別に全面ではなくてもいいのではということです。
ではどうするのかというと最短経路、つまり良い経路が出そうな場所のみを見に行くということです。
このことはWMMCの同級生に教えてもらった以下のブログのおかげで出せた方針です。
https://titech-ssr.blog.jp/archives/1046800312.html
教えてくれた同級生とロボット技術研究会に感謝します。
このブログではYen's algorithmを用いた効率的な一時走行について分かりやすく述べられています。このアルゴリズムはまさに自分の求めていた一次走行の機能を実現するものであると考えたためこれを用いて実装を行うと決めました。

この探索は何と呼べばよいのでしょうかね？疑似全面探索？

Yen's algorithmってな～んだ？

まずはじめに

この時自分はダイクストラ法どころか幅優先もまともに理解をしておらずAtcoderのC問題を見ただけでめまいがする程度の実力であったため、そもそもこのアルゴリズムを理解するだけで相当時間がかかりました。まじで。むずかった。
結局同級生の力も借りてなんとなくぼんやりとは理解できたかな？という状況です。その同級生は私が高校生の時に競プロを勧めたのですが、あれよあれよという間に成長して最近水色になってて、尊敬。自分も今夜はABCに出たいですね。

概要

まずYen's algorithmとは何かというとK番目の最短経路を求める問題です。
以下の記事が参考になります。
https://qiita.com/nariaki3551/items/821dc6ffdc552d3d5f22
自分はこの記事を参考にして実装を行いました。非常にわかりやすく書かれているのでお勧めです。
簡単にこのアルゴリズムの流れを説明をすると。
まず経路が入るグループA,Bを作成します。
Aが決定した経路であり、Bは候補の経路です。

1. 最短経路を求め、Aに入れる
2. 最後にAへ追加した経路A[k]の各ノードの処理
   2.2 スタートからn(初期値0)番目のノードから進めるエッジのうちAに含まれているエッジを消す
   2.3 その状態でn番目のノードを通る最短経路を出し、Bに入れる。
   2.4 エッジを復元する
   2.5 2.2から2.4までをA[k]の最後まで繰り返す。
3. Bの中で最も短い経路をAに入れる。これがk+1番目の最短経路になる。
4. 2から3までを好きなだけ繰り返す。

といった流れになっています。意外と簡単そうですが実装しようと思うとかなり難しかったです。自分にとっては。

こんな感じで最短経路になりそうかつ未探索なマスをゴールにして運用しています。（これは三本の最短経路を出してるはず）

利点

ここでこのアルゴリズムの簡単な利点を述べます（間違ってるかもです）

• 袋小路対策ができる（最短経路を求める過程で既知の袋小路はルートに出てこないため自動的にはじけます。）
• 最短になりえないマスにはいかない
• 迷路内で既知区間を往復したりなどの無駄な移動が少ない（多分）
• なんか不思議な動きして面白い

実装

自分はc++を用いて実装しました。いや～かなり苦戦しましたね。思い立ってから不具合なく動くまで一か月ぐらいかかっちゃいました。
自分が実装したYen's algorithmの内容としては最短経路を求める方法はA*法を用い、3~20本の経路を作成することができるものとなっています。正直A*の恩恵はあんまり受けられていないのですがなんか面白そうだったので入れました。ダイクストラさんまじリスペクト。

問題発生

　■╋■━━━━━━━━━━━━━━━━━━━━━━━━━━
　╋■┛　メモリが足りない！！！！！！！！！！！！！！！！！
　■┛━━━━━━━━━━━━━━━━━━━━━━━━━━━
え～何が起きたのかというとramが足りなくなりました。自分が使用しているマイコンはstm32-f303k8なのですがこのマイコンはramが公式によれば確か16kbyteしかありません。しかもなぜか12kbyteしか使えないです！！原因不明。
これが結構致命的でした。最初に実装した時自分は何とダイクストラ用のノード一つに10byte,Yen's algorithm用の経路一つに67byteも使う（何ならもう少し多かったかも）というぜいたくなメモリの使い方をしていたためま～じで一瞬でメモリを使い切ってしまってました。初めてこのアルゴリズムを動かしたときは、
お～コンパイルできた～　？？？なんかフリーズしてるんですか？？？
みたいな感じでしたね。自分は今までpc内で完結するものしか書いたことがなかったためramが足りないなんてことになったことがありがたいことになく、最初のうちはフリーズしたことにめっちゃ驚いてましたね。
一応最初からramが足りないのでは？みたいな懸念はあったのですが想像以上で驚きましたね。最初にサイズを計算しておけという話ではあるんですがまあそこは見逃してください。

解決編？

以下は素人が無理やり解決した経緯を示します。
まず最初にやったことはダイクストラ用のノードサイズを小さくすることです。ここで出てくるのがビットフィールドです。自分はこのタイミングで初めてこの存在を知りました。便利ですね～。とりあえずpriority queuに突っ込む変数をできるだけ減らし、ビットフィールドを使ってさらに小さくさせました。最終的にキューにれるのは3byteぐらい？になりました。
あとはYen's algorithmで候補の経路を入れておくグループBのサイズを詰めました。最初はグループBはpriority queuに入れることで素早く最も短い経路を出していたが、それではBに入る総サイズが大きくなりすぎる！！そこでmultisetを使うことにより最短経路になりえない長いルートをmultisetの後ろから取り出して消し、Bのサイズをできるだけ大きくなり過ぎないようにしました。
注意　この方法だと本来のYen's algorithmになりません。多分。多分精度落ちてる？
あとは実装の初めから行っていたことなのですが、作成したルートをスタートからの移動の差分を方角で保存しています。座標で持っていた方が便利だけど仕方ないね。あとこのルートは北:0b11、東:0b10、南:0b01、西:0b00のように設定し、1bitごとに敷き詰めて保存しています。これはビットシフトを行って取り出したり収納したりするのですが自分がいままでビットに触れることがなかったためかなり苦戦しました。

余談

実は計算時間の方も問題になっていたのですがそれは時間がないので簡単に。
大体5本の経路を出すのに300msぐらい？かかったはずです。そのため一区画走る間に計算をさせることで何とかしてます。

結論

楽しかった。
今日はもう眠いためこのアルゴリズムを使って行う探索が全面探索と比べてどれぐらい早く探索が終わるのかのデータはありません。すみません。でもなんか体感だとうまく行ってるのでヨシ。

感想とあとがき

書いてる間に東日本の試走会の時間が近づいてきましたね。変な探索をしてモーターからピロピロ音を鳴らしている人がいたら私です。よろしくお願いします。
感想としてはこのアルゴリズムを実装する流れで組み込みやc言語の基本が学べたので正直結構楽しかったです。

反省

読むと分かると思うのですがこの記事は後半に行くにつれて文章が崩れていってます。今度かくときはそんなことがないよう計画的にやりたいですね。あと本来はステッピングモーターで奏でるジングルベルでもやろうと思っていたのですが時間がなくて断念。来年はそれかな？

おわり

何かこの記事で間違ってることやアドバイスがあればコメントしていただくと、とてもうれしいです。