佐倉です。
今回から何回か、マイクロマウスで使われているor使えそうなアルゴリズムについて紹介して行きます。
まず、今回は全体を見渡していこうと思います。
イントロダクション
マイクロマウスの迷路の例(2012年度、クラシックサイズ決勝)
出典：公益財団法人ニューテクノロジー振興財団
上の迷路、どの経路で行くのが一番速いかわかりますか？
ハーフサイズではマスの数で上の迷路の4倍の迷路が出題され、人間が見ただけではどこにゴールに通じる経路があるのかわからないような状況になっています。
こんな感じで、マイクロマウスにはアルゴリズムという楽しみ方もあります。
マウスで使われるアルゴリズムの特徴
マイクロマウスでは、様々な所でアルゴリズムが利用されています。
言語固有のイディオムや、数値計算の効率化のような物から、探索アルゴリズムのような複雑な物、
さらにはハーフサイズマウスの巨大な迷路(32×32=1024マス)のサイズに対応するために確率的なアルゴリズムも検討され始めています。
全てのアルゴリズムに共通している特徴は、記憶容量の節約です。
マイクロマウスに使われているマイコンに内蔵されているRAMは非常に小さな容量です。
具体的には、5，6年前まではRAM容量2kB～8kBほどのマイコンが主流でした。
ほとんどの人はその中でやりくりしていて、一部の上位層がアドレス16bitのRAMをつなぎ、64kBもRAMが使える！というような状況でした。
近年はARM-CortexMシリーズコアのマイコンには大容量のRAM(それでも20kB～200kBほど)が搭載されるようになって来て、これくらいでもマイクロマウサーにとってはとんでもなくありがたい流れとなっています。
つまり、現在のマイクロマウスに搭載されているRAMは多くて数百kBなのです。
これは、PCで使う事を想定された経路探索のアルゴリズムなどを直接実装するにはかなりギリギリの所です。
だからといって、RAM容量が少なく、効率が悪いアルゴリズムを使うと、想定外の演算量となり、競技時間中に計算が終わらないというような事もあり得ます。
具体例として、私のロボットで、たったの16×8＝128マスの迷路の最速経路を愚直に深さ優先探索で計算させ、計算だけで5分以上かかった事があります。
迷路のマスの数は少なくても経路はたくさん作れるため、組み合わせ爆発が起こってしまうのです。
つまり、マイクロマウスのアルゴリズムには、RAMの使用量を減らしつつ速度もそこそこ出す事が要求されます。
マイクロマウス特有の楽しみ方
上の章で挙げたのは、あくまで一例です。
Android端末を載せたマイクロマウスや、最近流行りのRaspberryPiを載せたマイクロマウスなども見かけるようになりました。
何が言いたいかと云うと、マイクロマウスでは試したいいアルゴリズムに併せてハードウェアを作り上げる という楽しみ方ができます。
ハードウェアといってもプロセッサだけではありません。
センサも、駆動系も、はたまた私が思いついていない何らかの要素も、アルゴリズムのために全てを思い通りにつくり上げる事ができるのです。
※残念ながら、競技中に外部と通信する事は禁止されているのでクラウドマウスはできません。
マイクロマウスの花型、探索アルゴリズム
迷路探索ロボットの競技であるマイクロマウスの花型は、やはり、迷路探索アルゴリズムです。
探索アルゴリズムといってもマイクロマウスには大きく分けて2種類の探索アルゴリズムが存在します。
- 未知の迷路を探索するアルゴリズム
- 既知の迷路から最速経路を導くアルゴリズム
の2種類です。
アルゴリズムの本などを読むと、ほとんどは後者について説明されています。
前者は世間で、「右手法」、終了！みたいな扱いを受けていますが、右手法にはゴールできないパターンがある上にその欠点を補う拡張右手法は非常に効率が悪く、長所は5分もかからず実装できる事くらいなので、マイクロマウス界隈では動作確認専用アルゴリズムみたいな扱いだったりします。
こんな感じで、アルゴリズムについて書いていこうと思います。
次回以降はより具体的に、まずは探索アルゴリズムから話していきます。
 迷路 |
 柱 |
 壁 |
