マイクロマウスのアルゴリズムについて②

お知らせ

佐倉です。
本日もマイクロマウスで使われているアルゴリズムについて話していこうと思います。


本日は探索アルゴリズムについて書いていきます。

探索アルゴリズムの種類

有名な探索アルゴリズムには次のような種類があります。

  • (拡張)右手法/左手法
  • トレモー法
  • 足立法(ポテンシャル法)

マイナーな物も含めれば、いろいろな種類があるのですが、
マイクロマウスでの扱いやすさ、拡張性で言うと、足立法一択です。
ということで今回から数回、拡張の例も含めて足立法を解説します。

足立法の概要

今知っている迷路情報から導き出されるゴールへの最短経路を進むという物です。

最初マイクロマウスが知っている迷路の情報は、迷路の外周を壁がぐるりと囲んでいる事と、スタート地点がコの字型になっている事、ゴールが中央の4マスである事です。
一歩進んだ後、ゴールに向かって斜めギザギザに行くのが最短経路になりますね。斜めに行くのが苦手なマウスであれば、8マス直進して、右折して8マス直進するのが最短経路という事になるでしょう。
adachi1

もちろん、このような経路が存在する迷路が出題されるとは限りません。競技の特性上、あり得ないと言っても良いでしょう。
すると、予定していた経路上に壁があって通れないという事が起こります。

こうなった場合には、最短経路を導き直します。最初に書いた、今知っている迷路情報から導き出されるゴールへの最短経路を進む
を実践します。

まとめると、

  1. ゴールへの最短経路に沿って1マス進む
  2. 壁を読み取る
  3. 最短経路を導き直す

この手順を、ゴールにつくまで繰り返す事が足立法になります。
足立法では、経路が存在すれば、必ずゴールまでたどり着くことができます。

次回は足立法のより詳しい解説を行います。


BeeClone保守部品 モータ (MK06-4.5)
スリックタイヤ (dnanoタイヤ10度、リア用) スリックタイヤ (dnanoタイヤ10度、フロント用)

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