マイクロマウスの壁情報を安全にバックアップする

説明記事
マイクロマウス, 迷路

はじめに

こんにちは。
社会人2年目となり「新人なので…」と言い訳ができなくなって困っている けり です。

最近はマウス進捗がほとんどできていないのですが、モチベーションを高めるためにも頑張って記事を書きました。

マイクロマウス Advent Calendar 2021

この記事は マイクロマウス Advent Calendar 2021 の 12 日目の記事です。

昨日の記事はなおフィスさんの「1ヶ月で新作を作った話」でした。

使用されているマイコン ESP32-S3 は、無印の ESP32 からピン数が増えたりUSBペリフェラルが追加されたりしていて結構よさそうですね。

私は以前からマイクロマウスに ESP32 シリーズを使用してきているので適当なタイミングで差し替えをしたいところです。

それにしても、なおフィスさん、新しいマイコンを導入しつつこのクオリティのマウスを1ヶ月でプロトタイプするとは、さすがです。

この記事で紹介すること

さて、この記事では少し工夫した迷路の壁情報のバックアップ方法について紹介します。

実際に私のマイクロマウス KERISE に搭載されている方法です。

書き込み時間の短縮 や 迷路情報の破壊の防止 など、いつくかの課題を解決しました。

マイクロマウス KERISE

マイクロマウス KERISE

迷路情報を不揮発メモリに保存する上での課題

マイクロマウスの競技中、マイコンをリセットしても探索済みの壁情報が消えてしまわないように、壁情報を不揮発メモリにバックアップすることがあると思います。

迷路の壁情報をバックアップする際、以下のことがしばしば問題になります。

  • バックアップするタイミング
  • 不揮発メモリに書き込むときの書き込み時間

それぞれについて、下記で補足します。

バックアップするタイミング

クラッシュなどでいつリセットがかかっても大丈夫なように、できるだけ高頻度でバックアップはしておきたいものです。

しかし、探索中にクラッシュした際、フェールセーフ停止が働かないまま迷路がバックアップされてしまうと誤った情報に上書きされてしまうというリスクがあります。

対策としては、ゴールしたときのスナップショットや往復探索後のスナップショットなど、複数のデータをバックアップする方法もありますが、それでも直近の探索結果は失われてしまいます。

さらに、不揮発メモリには書き換え回数寿命があるため、あまり高頻度で書き換えを行うと意外と早く書き換え寿命が来てしまう、という問題点もあります。

フラッシュの書き換え寿命に達したときの挙動は厄介で、エラーにならずにデータ不一致になることもあるらしく恐ろしいです。

不揮発メモリへの書き込み時間

次に、迷路情報を不揮発メモリ領域に保存する際の書き込み時間についてです。

一般に、不揮発メモリへの書き込みには時間がかかります。

32x32 迷路だとおよそ 500Bytes 程度をデータを書き込む必要があり、マイコンやメモリの種類にもよりますが数百ミリ秒程度かかることもあります。

これらの処理を走行中に行おうとした場合、他の処理を妨げないように工夫する必要があったり、1区画の走行中に収まるか検証したり、注意すべきことが多いです。

そのため、ゴールやスタートなど特定の条件だけで保存しているという人が多いのではないでしょうか。

壁ログ方式による課題解決

さて、上記課題を解決するため、私は下記の方法で迷路情報のバックアップをしています。

  • 探索中に認識した壁の位置と有無をログのように順番に記録していく

迷路全体を一括で保存するのではなく、発見した壁単位でインクリメンタルに保存するわけです。

この方法を 壁ログ方式 と呼ぶことにします。

バックアップした迷路を復元する際には、未知壁で埋めた迷路に対して壁ログを1枚ずつ適用すればOKです。

壁ログの例

例えば、下記のような迷路を考えてみます。

+---+---+---+---+
|       |       |
+   +   +   +   +
|   |   |   |   |
+   +   +   +   +
|   |       |   |
+   +---+---+   +
| S | G         |
+---+---+---+---+

これを探索すると以下のように壁ログが得られます。 (スタート区画(0,0)と外周は予め既知に設定してあるため、記録されていません。)

壁ログの例 (ここをクリックして展開)
( x座標, y座標, 壁の方向, 壁の有無)
(    0,    1,       ^,   false)
(    0,    1,       >,   true )
(    0,    2,       ^,   false)
(    0,    2,       >,   true )
(    0,    3,       ^,   true )
(    0,    3,       >,   false)
(    1,    3,       ^,   true )
(    1,    3,       >,   true )
(    1,    3,       v,   false)
(    1,    2,       >,   true )
(    1,    2,       v,   false)
(    1,    1,       >,   false)
(    1,    1,       v,   true )
(    2,    1,       ^,   false)
(    2,    1,       >,   true )
(    2,    1,       v,   true )
(    2,    2,       ^,   false)
(    2,    2,       >,   true )
(    2,    3,       ^,   true )
(    2,    3,       >,   false)
(    3,    3,       ^,   true )
(    3,    3,       >,   true )
(    3,    3,       v,   false)
(    3,    2,       >,   true )
(    3,    2,       v,   false)
(    3,    1,       >,   true )
(    3,    1,       v,   false)
(    3,    0,       >,   true )
(    3,    0,       <,   false)
(    2,    0,       <,   false)

下記のようなすべて未知壁に設定した迷路に対して、上記の壁ログを適用すると探索済みの迷路が完成することがわかります。 (実際は32x32ですがここでは左下の4x4部分だけ記載しています)

+ . + . + . + . +
|   .   .   .   .
+ . + . + . + . +
|   .   .   .   .
+ . + . + . + . +
|   .   .   .   .
+   + . + . + . +
| S | G .   .   .
+---+---+---+---+

壁ログ方式の利点と注意

迷路全体を一括で保存する方法と比較して、壁ログ方式には以下の利点と注意があります。

利点1: 高頻度でのバックアップに適している

探索中、直近で認識した壁の分だけ保存すればいいので1回に書き込むデータサイズはかなり小さくなります。

壁ログのデータ構造は後述しますが1壁あたりのデータサイズ 2Bytes です。

1マス進むごとに新たに発見する壁は最大3個なので、最大 6Bytes の保存で済みます。

ちなみに、32x32 の迷路全体の壁情報を一括で保存する場合は 500 Bytes 程度を書き込む必要があるので、それと比べると圧倒的に少ないことがわかります。

これならば短時間で書き込みが終わるため毎区画バックアップをとることが可能となり、いつリセットがかかっても大丈夫です。

利点2: データの上書きではなく、追記なのでさらに高速

フラッシュメモリによっては削除に時間がかかる場合があります。

例えばSTM32マイコンのフラッシュメモリの場合、メモリ領域をすべて1で埋めておいて、書き込みするときに必要な部分だけ0にするという処理が入ります。

迷路全体を保存する場合は毎回全削除してから書き込みなおす必要がありますが、壁ログ方式ならば追記なので削除する必要がなく、超高速です。

さらに、迷路全体の壁情報を書き込む場合は保存回数分の書き換え寿命を消費しますが、壁ログ方式では上書きではなく追記となるので削除の必要がなく、1探索あたり実質1回分しか書き換え寿命を消費しないという利点もあります。

利点3: クラッシュ後の壁情報の欠損が最小限

探索中にクラッシュした場合は、最後に追加した壁ログをいくつか削除するだけで誤認識した可能性のある壁をキャンセルすることができます。

探索終了直前にクラッシュしても、迷路情報の大部分は残されていて、損失が最低限に抑えられます。

注意1: 壁ログはあくまでバックアップ用であり、経路計算には一般的な迷路全体の壁マップを使用

壁ログとして壁情報を管理すれば、迷路全体の壁マップを作成する必要がなくなるようにも思えますが、最短経路の計算の際にいちいち壁ログをたどって壁の有無を判定すると無駄に時間がかかってしまいます。

そこで、探索中に壁を認識したときには、壁ログと同時に迷路全体の壁マップを更新します。

探索アルゴリズムからの参照用には通常通り迷路全体の壁マップを使用して、バックアップの際に壁ログを使用しています。

注意2: 保存サイズが大きくなる可能性がある

迷路全体を一括で保存する場合に比べて、壁ログを保存する方法では最大2倍程度データサイズが大きくなります。

ただし、スナップショットなどで複数パターンをバックアップする必要性などを考えると、特にデメリットではなく、むしろサイズの節約とも言えるでしょう。

参考: 必要なメモリサイズ

迷路サイズをNとしたとき、外周の壁を除くと、保存すべき壁の個数は下記のとおりです。

壁の数: N*(N-1)*2

それをもとに計算すると下記の表のようになりました。

迷路サイズ各区画1Byte表現 [Bytes]最小表現 [Bytes]壁ログ方式 [Bytes]
N x NN^2N*(N-1)/2最大 N*(N-1)*2
8 x 86428最大 112
16 x 16256120最大 480
32 x 321024496最大 1984

最小表現とは、各区画1Byte表現の冗長表現を除去した表現形式です。こちらの記事 で解説しています。

今回紹介した壁ログ方式を使用する際は、不揮発データの保存領域として 2kB のメモリを確保しておけばいいようですね。

ちなみに、迷路全体を保存する場合は壁の有無だけでなく既知/未知の情報も保存する必要があるのに対して、壁ログ方式では既知壁のみ記録すればよいという違いがあります。

その他: 競技の終了後にマウスの動きなどをシミュレーションできる

ところで、壁ログ方式にはちょっとおもしろいところがあります。

完成した迷路だけでなく、迷路の探索過程が記録として残るので、歩数の把握や、どこで壁を読み間違えたのかなどがわかって解析に役立ちます。

撮影した動画と一緒に見比べて、「あ、ここで半区画ずれて壁を読み間違えたのか！」などの分析ができます。

壁ログのデータ構造

さて、今回の壁ログに使用する壁情報の構造体(共用体)は下記のように定義できます。

/* 区画位置、方向、壁の有無を保持する構造体。迷路探索の記録に使用する。 */
union WallRecord {
    struct {
      unsigned int x : 6;          /*< 区画のx座標 (0-63) */
      unsigned int y : 6;          /*< 区画のy座標 (0-63) */
      unsigned int d : 3;          /*< 壁の方向 (0-7) */
      unsigned int b : 1;          /*< 壁の有無 (0-1) */
    } __attribute__((__packed__)); /*< アライメント防止のおまじない */
    uint16_t data;                 /*< データ全体へのアクセス用 */
};

ビットフィールドを用いることで、区画の位置と壁の方向・有無を 2Bytes で表現しています。

なお、壁の方向は8方位で定義していますが、壁ログでは4方位しか使っていません。

KERISE の実装で使用している最新版は GitHub に公開しています。 こちらは結構複雑になってしまったので、興味がある方は解読してみてください。

以前の記事 迷路クラスの紹介 で紹介したものからいろいろ改良が重ねられています。

おわりに

今回の記事では少し変わった発想の壁情報の保存方法を紹介しました。

保存サイズは多少大きくなってしまいますが、それ以上のメリットがあると思っています。

マイクロマウスのソフトウェア設計の参考になれば幸いです。

明日の マイクロマウス Advent Calendar 2021 はもすさんです。お楽しみに！