ししかわのマウス研修マウス自作研修

迷路探索の実装 – ししかわのマウス研修 Part.45

ししかわのマウス研修

ししかわです。

社員研修の一環で、マイクロマウスを自作して大会に出場しました

記事一覧

全日本大会2020は終わりましたが、ブログはもうちょっとだけ続きます。

今回は迷路探索(図中赤枠)の実装です。

参考にしたサイト

迷路の表現

実装箇所:maze.hmaze.c

マイクロマウスにおいて迷路をどのように表現するかは、迷路探索の性能にもつながる重要な関心事です。M5Mouseでは次のようなオーソドックスな方法で迷路をモデル化しました。

迷路

 

  • 迷路の1マス分をセルと呼びます。
  • 迷路はセルの二次元配列として表現します。
  • 迷路の南西端が原点(0, 0)です。
  • 迷路の東方向にX座標、北方向にY座標を取ります。
  • たとえば図中の赤いセルの座標は(0, 0)、黄色いセルの座標は(2, 1)となります。

セル

  • セルは東西南北に壁を持つことができます。
  •  セルの情報を8個のビット列=1バイトで表現します。
    • 上位4ビットは北東南西の壁の有無を表します。
    • 下位4ビットは北東南西の探索済みフラグを表します。

  • 上図のように、あるセルに対して南からマウスが進入した場合の、セル情報の更新を考えます。このセルの上位4ビットは北と西に壁があるので1001、下位4ビットは、進入してきた南方向を含めてすべてのセルが探索済みとなるため1111となります。

 

  • また、このとき隣接するセルも同じ壁を持っているため、壁を挟んだ2つのセルの壁情報は同時に更新する必要があります。
  • 複数のセルで同じ壁の情報を重複して持っているのはある意味冗長な表現方法ですが、あるセルに着目したときの壁や探索の有無が1バイト読むだけで分かるので便利です。

迷路とセルのコードは次のようになります。

迷路探索

実装箇所:agent.hagent.c

探索アルゴリズムはマウス競技で実績ある足立法を使います。足立法の説明は弊社のブログに詳しいのでここでは割愛します。

迷路の探索では以下を繰り返します。

  1. 周囲の壁情報を取得する
  2. 迷路の壁情報を更新する
  3. 歩数マップを更新する
  4. 次に進む方向を決める
  5. マウスを進める

これを関数で表現すると次のようになります。

TIPS:オブジェクト指向風の実装

今回、マウスモジュールの実装に初学者でも分かるようにとC言語を使いましたが、C言語自体にはクラスの仕組みがありません。オブジェクト指向風の実装ができるよう、幾つかの制約を設けてクラスっぽくコードを書いてみました。

  • クラスとして扱いたい対象の構造体を次のように定義する
    • 構造体の名前はクラス名+Recordとする
    • 構造体へのポインタに対してクラス名を付与する

  •  クラスのメソッドとして扱いたい関数を次のように定義する
    • 関数名の先頭にクラス名をつける
    • 関数の第一引数をクラスの構造体へのポインタ(上でクラス名を付けたもの)を渡す

この仕組みはModdableの実装を参考にしました。ただし、これはごく簡易なものであり、例えばパブリックとプライベート変数の区別もありませんし、コンストラクタ、デストラクタも自分でそういうメソッドを作って忘れずに呼ぶしかありません。ですがM5Mouseくらいの規模であればそこまで問題にはなりませんでした。

TIPS:シミュレーション

迷路探索アルゴリズムのデバッグのために毎回実際のマウスを走らせていては非効率なので、シミュレーションができるようにしました。

実装を説明するために足立法の探索アルゴリズムを再掲します。

  1. 周囲の壁情報を取得する
  2. 迷路の壁情報を更新する
  3. 歩数マップを更新する
  4. 次に進む方向を決める
  5. マウスを進める

シミュレーションをするためには、1.で「センサを使わずとも(仮想の)壁情報を取得できる」こと、5.で「車輪を回さなくてもマウスを一歩進めたことにできる」ことが必要です。

1.については次のようにして実現できます。

5.については単にシミュレーションフラグで分岐させて、エージェントの現在の座標のみ更新し、マウスへの前進や旋回指令は出さないようにすればOKです。

最後に各ステップでの歩数マップと壁情報を出力する関数を作れば、シミュレーションができるようになります。

 


 

以上です。次回はドライバとコントローラの実装の説明です。

タイトルとURLをコピーしました