昨日の記事はジャッジー先輩の「富士山登頂記」でした。
山頂まで登頂したのですね。さすがです。高純度の達成感が得られそうですね。ちなみに私は学生大会で工芸大の2階から4階の移動すらエレベータを使う人間なので登山は無理です。
はじめに
学生大会でもリクエストの多そうだった経路導出について書きます。
といっても内容全部書いてしまってみんな同じようになってしまったら面白くないのと、斜めやっている人たちはそれなりにデバッグの体力あると思うので、ここでは私の考え方の指針について伝えるにとどめます。経路導出といっても、やってること自体は結構簡単なことであることが伝われば、狙い通りという感じです。
足立法について
マイクロマウスにおいて主流とされる探索手法に足立法と呼ばれるものがあります。
考え方としては、ゴールから今の自分のマスまでの最小歩数となる経路を、壁情報の更新が行われるたびにたどり続けることでゴールに辿り着くことができるというものです。足立法についてよくわかっていない人はこちらとかを見ればわかるんじゃないですかね(今「マイクロマウス 足立法」でgoogle検索して一番上のリンク貼ってるだけなのでこのくらいは調べてほしいですが...)。
探索を終えた後に最短経路を導出するといったときは、この足立法で用いる歩数マップとよばれるマップを探索で見ていない壁はあるものとして作成し、辿ることで最小歩数の経路を出せる、というのがとりあえず初めてマイクロマウスで最短走行を行うときによく使われるやり方のように思います。
歩数マップで経路導出をするという意味
さて、ここからが私の視点での考え方なのですが、とどのつまり歩数マップを用いて経路導出をするというのはどういうことなのでしょう？確かに「最小の歩数が出る」というのはそうなのですが、マウスの走りにおいて、これを用いる旨みはどこにあるのでしょう。
私は、この歩数マップで出す経路は「1区画ずつ進んでは止まり、旋回時は超信地旋回を行う、という走り方をするマウスが、基本的に必ず最もよいタイムの出る経路を導出することのできる経路導出方法」だと捉えています。
言われてみれば、まあそれはそうでしょうね。という感想の人も多いかもしれません。ここで伝えたいポイントは、歩数マップにおいてこのような結論が得られるのはマップの更新の仕方とマウスの動き方が同じだからというところにあります。
しかし現在の大会で、こういった走りで最短走行をするマシンはほとんど見かけません。1区画進んでは止まっていては、探索で時間切れになってしまうのがオチでしょう。実際は直進は速度を緩めずに走りますし、旋回時にも速度を緩めないでカーブする(スラローム)わけで、さらに旋回半径を大きくしたり斜め走行を行ったり、原形をとどめないところまで走行の内容が変わっているわけです。
歩数マップしか用いないというのは、動き方の部分はどんどん進化しているのに、肝心の経路の部分の考え方は初歩のころから変わっていないということになります。マウスは基本的に構成要素の一番弱い部分に性能が引っ張られてしまうので、このままでは経路の不出来でタイムを落とすことがあるというのは、ある種必然です。
ではどうしましょうか。やることは単純です。経路導出の仕方を、実際の動きに合わせる。これだけです。
実際にやってみよう
では、今回の学生大会の迷路を例に、考えていきましょう。マウスの動きをベースに考えていくことが肝です。
歩数マップの場合、更新されるのは1区画進んだところなので、下の図のように、1区画進んだところのみ情報が更新されますよね。
しかし、実際問題はどうでしょうか。斜め走行を行うマシンの場合、長いストレートは1つのモーションとしてつないだり、なるべく短い距離になるようにターンしたりしますよね。そう考えると、スタートしてから一息ついた段階でマウスは、開幕ターンとストレートを加味すると下図に示す位置にいる可能性があるといえます。
赤い矢印がマウス、矢印の先端がマウスの頭です
スタートから一息つきました。足立法の場合、次に歩数マップの値が少ないところを起点として更新しますね。では、斜め走行を行うときも同様にそこに到達するまでにかかった時間の短そうなところを起点としてみましょうか。どこでしょうかね。
おそらく上図の黒丸の矢印ではないでしょうか。1区画進んだところですね。ここから更新しましょう。と思いますが、そこから先のストレートはすべてスタートを起点としたときに更新済みでした。1区画進んでからn区画進むより、n+1区画進んだ方がさすがに速いでしょうから、ここでの更新はなく、次に行きます。
次は細かい順番はマウスの速さによるでしょうが、大体2区画進んだところと最初のIn45ターンしたところ、Big90ターンしたところあたりが起点の候補になるでしょう。しかし、2区画進んだところは1区画進んだところと同様の理由で、ほか2つについてはその後の行き先が壁に阻まれて見当たらないので、ここでも更新はできなさそうです。
その次はIn135ターンで来た下図黒丸の矢印を起点にします。ここからは次のストレートに復帰するOut45ターンをしたところ、もしかしたら複合ターン(マウス用語: こじまターン)をする場合はその先までマウスが行っているかもしれません。これらを反映してマウスがいる可能性があるところを、青矢印で示します。
もう大体わかってきたのではないでしょうか。この要領で更新を続けていけば、やがてゴールに近づいていくでしょう。そして更新する際に時間が短くなる時のみ更新し続けていれば、必然的にかかる時間の短い経路が出ているはずです。
あとはこれを実装するだけです。やろうとしていること自体は、結構シンプルなんですよ。
ダイクストラ法について
この手の話をすると二言目くらいに「ダイクストラ法」というワードが出てきます。ダイクストラ法の説明は、ネット上に多くの記事があるので検索してください。今回の考え方でいうと、マウスがいる可能性のある地点を「ノード」、起点から次の位置に行くまでの道のりを「エッジ」と捉えてあげれば、読みやすいと思います。
より詳しい話を知りたければ、私なんかよりAtcoder(競技プログラミング)をやっている人の方がはるかに詳しいので、近くにいる人で該当する人をとっ捕まえて聞いてください。
終わりに
いかがでしたでしょうか。とっかかりは掴めましたかね。
もちろんこの考え方はあくまで私個人の考え方で一般解であるかは私も知らないので、これにこだわらず各自でこれが正しい、と思える導出法を模索してデバッグしてもらえたらと思います。走行パターンがそこそこあるので息が切れそうになるかもしれませんが、時間をかけて頑張ってください。
最後に少しだけ。私が大学に入ってからマウスを作る際に意識していることとして「難しく考えようとしない、なるべくシンプルに正しい形に持っていく」ことを意識しています。
経路導出についても、やれ高級なダイクストラだ最適問題だといった難しいものを難しく使いこなそうとしていると、少なくとも私は何をやってるのかよくわからなくなってしまいます。そうではなくて、とどのつまり何がしたいの、と考えてみると全体像や指針は意外とあっさりしていることが多いです。そこが見えたらそれに沿って実装をしていきます。実装をしていく中で、先に挙げたダイクストラのような話がツールとして出てきます。はじめにシンプルにとらえられていると、ツールの使いどころがよく見えるので、多少煩雑になっても実装しきることができるという感じです。
と、偉そうなことを言いましたが何か話した内容でおかしそうなところがあったらあとで(こっそり)教えてください(笑)。
また、今後も技術系の記事は「マイクロマウスTips」として、不定期に出していこうと思います。
明日はの記事は卓輝くんの「なんか書きます。」です。
