クラシックマウスを作ろう！（14）終 〜探索と経路導出〜
初めましての方は初めまして。
そうでない方はお疲れ様です。
いよいよ最終回です。割と間延びしてる感もありますが、完走までの必要要素を大まかにさらってこれたと思います。
（ぱわぷろ本人もそろそろ上を目指して修行を積まねばならないので…）
最後はマイクロマウスの探索と経路導出の手法と解釈について触れて終わりたいと思います。探索法自体は完走に必要ですが、経路導出は必ずしも必要ではありません。でも、経路導出までやってしまえば、あとは速度などの追求によって更なる発展へつながると思い、触れておきます。
「迷路を探索、取得した迷路情報から最短経路を導出、最短経路を通るように走行を計画し、実行する。」
上位の方々もこのフローをできるだけ緻密に、かつ精度良く実行しており、このフローを実装してこそマイクロマウスとしての一区切りであり、スタートともいえるのではないかと思っています。
本日の内容はコチラ。
足立法という探索法
マイクロマウスの迷路は1区画が正方形で、それらが隣接して16×16, 32×32のマップを形成しています。隣接する際に壁が存在するか否か、で迷路パターンが定まるわけですね。
迷路の探索法としては足立法が広く用いられています。
参考:
雰囲気を掴む：いわゆる足立法① : あやしい製作所「takayanagi work space」
具体的な感覚を掴む：マイクロマウス研修（kora編）[15] 迷路探索の解説 | アールティ 移動型ロボットブログ
解釈を一般的に拡張：python マイクロマウス tkinerのアニメーションで見せる，足立法歩数マップの最短経路は最短経路探索A*（A-Star）アルゴリズムと同じ
ほとんど概略だけ書きます。
迷路の区画を格子点として考え、座標系で区画を表します。
ゴール座標の格子点を0、そこから1回で行ける区画には1、2回で行ける区画には2,,,という風にマップを埋めていきます。これが歩数マップです。
もし壁の位置が全て分かっていたなら、数字が小さい方へ辿ればゴールできます。
でもマウスは壁情報を取得しながら逐次的にマップを生成しているため、最初は完璧なルートを出すことができません。
その場合、見ていない壁は全てないものとして計算してます。
途中経路で壁があった場合はそこまでで得た壁情報を考慮して、経路を再計算します。これを繰り返せばゴールに辿り着けます。これが足立法です。
実は歩数マップと足立法の基本を抑えていれば、これらを拡張することでかなりの部分の探索と経路導出をカバーできます。
弄りがいがあるテーマです。ここからは「歩数マップと足立法の拡張」とも言える部分について述べていきます。
経路導出と走行計画
探索が終わった後の経路導出ですが、足立法の場合は比較的簡単に出すことができます。未知区画の壁は全てあると仮定して足立法の経路導出をするだけです。
1度ゴールしていればこれだけで経路の導出はできます。
…もちろん、良い経路を出すには充分な探索と歩数マップの工夫が必要です。
その前に「良い経路」っていう曖昧な言葉にこの記事における定義づけをします。
「良い経路」＝「走行時間が短い経路」とします。（人によって違ったりします）
走行時間が短い、もしくは短くなりうる経路が「良い」という事は納得してもらえる考え方かと思います。
では車輪走行ロボットで走行時間を短くするにはどんな経路が良いのでしょうか？
タイムの短縮を目的とするならば、「直線が多い経路」と言えるでしょう。
直線が多いと、加速度を攻めることができ、最大速度を出すことができます。
車輪走行ロボットの速度を縛っている大きな要因の1つにスリップ、滑りというものがあります。これは急激な加速度によるスリップもありますし、ターンで生じる遠心力によるタイヤのスリップも存在します。
スリップするとクラッシュしやすいため、速度と加速度を落とさざるを得ず、ゆえに経路導出ではターンはできるだけ避けたいって考えです。
この横滑りについては「スリップ角」として知られる概念を導入し、モデル化することも行われています。主に自動車工学分野で用いられる概念とのこと。
参考：
２輪差動式移動ロボットの横滑り運動について - 理系的な戯れ
話を経路導出に戻します。
ターンを避ける経路のために、歩数マップ生成では曲がる際に増加する数を増やして、「曲がりたくない」意思を歩数マップに反映させます。
こうして作成した歩数マップは、数字を辿るだけでかなり「良い経路」が出るでしょう。実装に際しては各変数の大きさなどに注意してください。特に8bit変数を多用しがちな際にやらかすことが多いです。
歩数マップを追うことで、経路としては
「(1,3) -> (1,4) -> (2,4) -> (2,5) -> ... (7,7)」
のような形で出ます。
これをマウスの走行計画に反映することで次のような行動計画に直します。
「直進 -> 右折 -> 左折 ... etc」
配列化して各行動に番号付けするなど方法は色々あります。
また、斜め状態の保存ができれば、斜め直進などの走行計画も可能となります。
斜めの動きのパターンは以下のブログを参考にしてください。
参考：
本当に良い経路を求めていくと、足立法ベースの歩数マップで斜めを考慮するには工夫が必要です。
これを考慮するために、より一般的なダイクストラ法などの経路計画法を導入することが多いです。
ダイクストラ法
ダイクストラ法自体は足立法をより一般的な形で表現している（と自分は解釈している）ので、原則は足立法の言葉で紹介していきます。
ダイクストラ法の考え方はイラスト含めて滅茶苦茶分かりやすいのがあるので、概略はわざわざ書かなくてよさそう…？
参考：
これをマイクロマウスに当てはめていきます。
主な3要素についてマウスの言葉に置き換えていきます。
- ノード ー＞ 区画
- エッジ ー＞ 次に移動できる区画
- コスト ー＞ 歩数増加量
まずノードについてです。
ここまで説明した足立法だと区画の中心が「ノード」です。
現在位置であり、目標位置であり、到達するまでの歩数が保存されています。
斜めを考慮するために、このノードを柱と柱の間に追加します。
これによって、1区画あたりに5つのノードが見えることになります。
次にエッジについて。
ノードとノードを繋ぐのがエッジなので、以前のノード設定だと上下左右の4方向でした。ノードを拡張したことにより、エッジは斜めも含めた8方向になりました。
したがって、90度のターンと斜めを分けることが可能となりました。
最後にコストについてです。
「良い経路」の基準は直線が多いことでした。これは姿勢の変化が少ない経路を選びやすくすることで実現可能です。したがって、コストの基準は「姿勢変化が少ないエッジのコストを低くする」ことと考えています。
どれくらい変化させるかは個人の裁量でしょう。（自分も実装までは行けてませんし…）
これらをマウスの経路導出に適用することでかなり良い経路が出るようになると思います。
上記のノード計算においては壁の存在を考慮して、通行不可能なノードを潰す処理が必要です。また、ノード番号の管理など、統合や実装に向けてはやらなければならない細々としたことが多くあります。
でも、やっぱり書いて実際に動かすのが1番大事かと思います。（自戒を込めて）
シリーズの最後に
これにて「クラシックマウスを作ろう」シリーズは終わりになります。
ステッパーで完走経験を持つ人がDCモータでクラシックマウスを自作するために（自分なりに）必要な要素は概ね書いてきましたが、製作に必要な知識を全体的にさらってきたつもりです。
ほぼ全分野において、さらに技術的に追求し高められることが沢山あります。
でも追求するだけだと機体が動く前に疲弊しきってしまうので、まずは完走できるようにしましょう。その後からいくらでも戻って追求できます。
ぱわぷろ自身もこれからも精進していきます。
これが誰かの一助になれれば、それに勝る嬉しさはないです。
では、皆様の良き開発生活を祈って。
