Mindstormsはアイデアと工夫で様々なロボットや機械を作ることができるLEGOの商品で、世界中で楽しまれています。そのMindstormsで作られた作品がいろいろと公開されていてYoutube等で見ることができますが、以前ルービック・キューブを解くロボットが作られているのを見て、こんなものを自分も作ってみたいと思うようになりました。しかし、どこから手を付ければいいか方針が立たずになかなか取り掛かれずにいました。
それを始めるきっかけができたのは、事情で札幌に2ヶ月程度滞在することになったときです。暇つぶしに持参したルービック・キューブで遊んでいて、スピード・キューブと呼ばれる速さを競う世界ではLBL法と呼ばれる解法が広く使われているのを知り、その方法を使えば実現できそうだということが分かったからです。
その後、LBL法をベースにした解法のプログラム化、キューブを回転させる機構の製作、AIを使った色の識別方法の開発を進めました。そしてそれらを統合することにより任意に崩したキューブを解いて整列させるロボットを完成させることができました。
アルゴリズムがすこし冗長なのと機構の自由度に制限があるので時間がかかりますが、それでも解けます。スピード・キューブの競技者たちがあっという間に完成させるのと比較すると呆れるほど遅いですが、とにかく解けるものを作ることが目標だったのでこの成果には一応満足しています。
その経過をここに記録しておくことにします。
- 初めに
- ステップ１ ｘ軸周りの回転機構の検討（習作１）
- ステップ２ ｙ軸周りの回転機構の検討（習作２）
- ステップ３ 解法のアルゴリズムをJavaで実装
- ステップ４ Mindstorms EV3に実装するためのJava開発環境を構築
- ステップ５ 機械学習のためのデータ収集
- ステップ６ 3層のニューラル・ネットワークによる色の識別１
- ステップ７ 3層のニューラル・ネットワークによる色の識別２
- ステップ８ キューブの初期状態を認識
- ステップ９ キューブの整列
初めに
最初に記事の中に登場する言葉の定義をします。キューブを体の前に両手で持った時、手前にくる面をF面とし、6つの面、回転の軸を図のように呼ぶことにします。
また、各面の中心の6つのキューブをセンター・キューブ、8個の角のキューブをコーナー・キューブ、12個の辺のキューブをエッジ・キューブと呼ぶことにすると、6個のセンター・キューブは写真のように固定されていてそれぞれの相対位置は変わりません。
そこで、ルービック・キューブを整列させるということは、センター・キューブの色にコーナー・キューブとエッジ・キューブの色を合わせていく作業だということになります。
現在のMindstormsはEV3と呼ばれる第3世代です。これまでRCX→NXT→EV3と7，8年おきに進化してきているのでそろそろ次を期待するのですが、そういう噂は聞こえてきません。コンピュータとしてはスマートフォンやRaspberry Piには及びませんし、バッテリーの性能もよくないし、それほど個数が売れるわけでもないので価格が高い、ということでこれといった売りがなくなってきているのも事実です。アッと驚くような新商品の開発は難しいかもしれません。
ここで使ったEV3のセットは下の写真のようにブリックと呼ばれるコンピュータとモーター、各種センサー、機構部品で構成されています。これらを自由に組み合わせて何を作るかはアイデア次第です。
ステップ１ ｘ軸周りの回転機構の検討（習作１）
キューブを動かす機構は人間の操作をモデルにして考えることにして、最初に右手でｘ軸周りに回転させる操作に対応する動きを2個のモーターでつくってみました。Mindstormsのモーターは時計回り、反時計回りに1°刻みで任意の角度だけ回転させることができるので、これでｘ軸周りに正確に±90°ずつ回す操作が実現できそうです。
ステップ２ ｙ軸周りの回転機構の検討（習作２）
キューブをy軸周りに回転させることができれば、それとx軸周りの回転を組み合わせることにより、F、R、B、Lの4面を回転させることができます。そこで写真のようなターンテーブルを使ってy軸周りの回転機構をつくりました。これにより、y軸周りに正確に±90°の整数倍だけ回転させることができます。この部品は実はNTXのセットに付属しているもので、EV3のセットには付属していません。このようにここではEV3セットにないパーツをいくつか使っていることをお断りしておきます。
ビデオで示しているように、キューブの上2層を固定してy軸周りに回転させるとD面の回転ができます。LBL法を使うと5面の回転で解くことができるので、ステップ１と２を組み合わせることで機構的には解くことができるようになりました。
ステップ３ 解法のアルゴリズムをJavaで実装
LEGO Mindstormsにはビジュアル・プログラミングの環境が標準で用意されていますが、複雑なアルゴリズムを実装するには不向きです。 Mindstorms用に開発されているプログラミング言語のなかでleJOSというJavaが使いやすいのでこれまで使ってきました。そこで、今回もLBL法を使ったプログラムをまずはPC上でJavaで実装しそのアルゴリズムを検証することにしました。最終的にはそのプログラムをMindstormsのleJOSに移植してロボットを動かすことになるわけです。
ビデオは、任意の初期状態のキューブの面の色を読み取り、F、R、B、L、D面の回転操作の組み合わせで整列させるのをEclipseの上でシミュレートしている様子です。ランダム操作で作った10種類の初期パターンでテストして問題なく解けることが確認できたのでこれで進めることにしました。
ステップ４ Mindstorms EV3に実装するためのJava開発環境を構築
EV3は第三世代のMindstormsで、それまでのモデルと違ってOSがlinuxになり十分なメモリ空間が利用できるので自由にプログラミングできます。それ以前の機種同様、多くのプログラミング言語が開発されていますが、ここではleJOSというJavaを使うことにしました。leJOSのプログラムは図のような環境を使ってPC上でクロス開発します。久しぶりに扱ったので、当初、コンパイルできない、実行できない、デバッガーが動かないという基本的なことで悩まされましたが、その都度、ネット上の情報に助けられました。マイナーな趣味の世界ですが、世界中には同じようなことを考えている人が結構いるもので、その知識をネットで共有させてもらえるのは本当にありがたいことです。つくづくいい時代になったと思います。開発環境の詳細については次に使うときにまた手こずることがないように別の記事で書くことにします。
今回使用するH/Wはモーターとカラーセンサーですが、それらをEV3に繋いでコントロールできるようになったので、次のステップはキューブ面の色を検出できるようにすることです。
ステップ５ 機械学習のためのデータ収集
今回のルービックキューブ・ソルバ―の開発において最も不確定な要素はキューブ面の色の識別方法でした。その色の読み込みにはLEGO純正のカラーセンサーを使うことにして写真の位置に配置することにしました。今回の機構ではこの位置がベストだと判断したのですが、この位置ではセンター・キューブの色を読み取ることができません。そこでセットするときに、白のセンター・キューブをU面、青のセンター・キューブをR面に向けるという制約をつけることにしました。
この位置で面の色の読み取り実験をしたところ、leJOSの既存のライブラリではキューブ面の６色（白、黄、赤、青、橙、緑）を確実に識別できないという致命的な問題があることがわかりました。ただ、カラーセンサーには測定値をRGB値で返すモードがあるので、機械学習を使ってRGB値から色を識別することができるかもしれません。
機械学習を実行するためには、キューブの色とそれに対するRGB測定値のデータを多数用意する必要があります。そこで、大量のデータを自動的に採取するためにビデオに示すようにソルバーの機構全体を形作りました。このときキューブをL面側から抑える機構を加えたので、R面、D面の回転動作を安定化することもできました。そして自動的にすべての面のRGB値を読みとるプログラムを実行して、学習用：960個、評価用：240個のデータを用意しました。
ステップ６ 3層のニューラル・ネットワークによる色の識別１
ステップ７ 3層のニューラル・ネットワークによる色の識別２
ステップ８ キューブの初期状態を認識
ここまでくると、あとはそれまでモジュール毎に確認したことをEV3の実機に移植していく作業です。最初にAIによる色の識別処理を実装してキューブの初期状態を認識できるようにしました。そして、キューブの上段を揃えるところまで作りました。（ビデオは作った本人以外には退屈な内容なので途中8倍速で再生しています。）
ステップ９ キューブの整列
残りは、すでにステップ３で確認しているLBL法による中段、下段の整列のアルゴリズムをEV3に移植することです。
それを完成させて、任意の状態に崩されたルービック・キューブを自動的に解くロボットが完成しました。
下のビデオはそのデモンストレーションで、任意に崩したルービック・キューブを本装置にセットすると、最初に面の色を識別し、その後、LBL法で上段から順に整列させていく様子をご覧いただけると思います。
