The Fool In The Valleyの雑記帳

-- 好奇心いっぱいのおじいちゃんが綴るよしなし事 --

ルービック・キューブ・ソルバ―

 Mindstormsはアイデアと工夫で様々なロボットや機械を作ることができるLEGOの商品で、世界中で楽しまれています。そのMindstormsで作られた作品がいろいろと公開されていてYoutube等で見ることができますが、以前ルービック・キューブを解くロボットが作られているのを見て、こんなものを自分も作ってみたいと思うようになりました。しかし、どこから手を付ければいいか方針が立たずになかなか取り掛かれずにいました。 

それを始めるきっかけができたのは、事情で札幌に2ヶ月程度滞在することになったときです。暇つぶしに持参したルービック・キューブで遊んでいて、スピード・キューブと呼ばれる速さを競う世界ではLBL法と呼ばれる解法が広く使われているのを知り、その方法を使えば実現できそうだということが分かったからです。

その後、LBL法をベースにした解法のプログラム化、キューブを回転させる機構の製作、AIを使った色の識別方法の開発を進めました。そしてそれらを統合することにより任意に崩したキューブを解いて整列させるロボットを完成させることができました。

アルゴリズムがすこし冗長なのと機構の自由度に制限があるので時間がかかりますが、それでも解けます。スピード・キューブの競技者たちがあっという間に完成させるのと比較すると呆れるほど遅いですが、とにかく解けるものを作ることが目標だったのでこの成果には一応満足しています。

その経過をここに記録しておくことにします。

 

 

初めに

 最初に記事の中に登場する言葉の定義をします。キューブを体の前に両手で持った時、手前にくる面をF面とし、6つの面、回転の軸を図のように呼ぶことにします。

f:id:tfitv:20200607143913p:plain

また、各面の中心の6つのキューブをセンター・キューブ、8個の角のキューブをコーナー・キューブ、12個の辺のキューブをエッジ・キューブと呼ぶことにすると、6個のセンター・キューブは写真のように固定されていてそれぞれの相対位置は変わりません。

f:id:tfitv:20200609075443j:plain
そこで、ルービック・キューブを整列させるということは、センター・キューブの色にコーナー・キューブとエッジ・キューブの色を合わせていく作業だということになります。

現在のMindstormsはEV3と呼ばれる第3世代です。これまでRCX→NXT→EV3と7,8年おきに進化してきているのでそろそろ次を期待するのですが、そういう噂は聞こえてきません。コンピュータとしてはスマートフォンRaspberry Piには及びませんし、バッテリーの性能もよくないし、それほど個数が売れるわけでもないので価格が高い、ということでこれといった売りがなくなってきているのも事実です。アッと驚くような新商品の開発は難しいかもしれません。

f:id:tfitv:20200609093820j:plain

ここで使ったEV3のセットは下の写真のようにブリックと呼ばれるコンピュータとモーター、各種センサー、機構部品で構成されています。これらを自由に組み合わせて何を作るかはアイデア次第です。

f:id:tfitv:20200609093755j:plain

 

 

ステップ1 x軸周りの回転機構の検討(習作1)

キューブを動かす機構は人間の操作をモデルにして考えることにして、最初に右手でx軸周りに回転させる操作に対応する動きを2個のモーターでつくってみました。Mindstormsのモーターは時計回り、反時計回りに1°刻みで任意の角度だけ回転させることができるので、これでx軸周りに正確に±90°ずつ回す操作が実現できそうです。


習作1 

ステップ2 y軸周りの回転機構の検討(習作2)

キューブをy軸周りに回転させることができれば、それとx軸周りの回転を組み合わせることにより、F、R、B、Lの4面を回転させることができます。そこで写真のようなターンテーブルを使ってy軸周りの回転機構をつくりました。これにより、y軸周りに正確に±90°の整数倍だけ回転させることができます。この部品は実はNTXのセットに付属しているもので、EV3のセットには付属していません。このようにここではEV3セットにないパーツをいくつか使っていることをお断りしておきます。

f:id:tfitv:20200608112215p:plain
ビデオで示しているように、キューブの上2層を固定してy軸周りに回転させるとD面の回転ができます。LBL法を使うと5面の回転で解くことができるので、ステップ1と2を組み合わせることで機構的には解くことができるようになりました。


習作2

ステップ3 解法のアルゴリズムJavaで実装

LEGO Mindstormsにはビジュアル・プログラミングの環境が標準で用意されていますが、複雑なアルゴリズムを実装するには不向きです。 Mindstorms用に開発されているプログラミング言語のなかでleJOSというJavaが使いやすいのでこれまで使ってきました。そこで、今回もLBL法を使ったプログラムをまずはPC上でJavaで実装しそのアルゴリズムを検証することにしました。最終的にはそのプログラムをMindstormsのleJOSに移植してロボットを動かすことになるわけです。
ビデオは、任意の初期状態のキューブの面の色を読み取り、F、R、B、L、D面の回転操作の組み合わせで整列させるのをEclipseの上でシミュレートしている様子です。ランダム操作で作った10種類の初期パターンでテストして問題なく解けることが確認できたのでこれで進めることにしました。


RubikCubeSolverSimulator

ステップ4 Mindstorms EV3に実装するためのJava開発環境を構築 

EV3は第三世代のMindstormsで、それまでのモデルと違ってOSがlinuxになり十分なメモリ空間が利用できるので自由にプログラミングできます。それ以前の機種同様、多くのプログラミング言語が開発されていますが、ここではleJOSというJavaを使うことにしました。leJOSのプログラムは図のような環境を使ってPC上でクロス開発します。久しぶりに扱ったので、当初、コンパイルできない、実行できない、デバッガーが動かないという基本的なことで悩まされましたが、その都度、ネット上の情報に助けられました。マイナーな趣味の世界ですが、世界中には同じようなことを考えている人が結構いるもので、その知識をネットで共有させてもらえるのは本当にありがたいことです。つくづくいい時代になったと思います。開発環境の詳細については次に使うときにまた手こずることがないように別の記事で書くことにします。
今回使用するH/Wはモーターとカラーセンサーですが、それらをEV3に繋いでコントロールできるようになったので、次のステップはキューブ面の色を検出できるようにすることです。

 

f:id:tfitv:20200607161718p:plain

ステップ5 機械学習のためのデータ収集

今回のルービックキューブ・ソルバ―の開発において最も不確定な要素はキューブ面の色の識別方法でした。その色の読み込みにはLEGO純正のカラーセンサーを使うことにして写真の位置に配置することにしました。今回の機構ではこの位置がベストだと判断したのですが、この位置ではセンター・キューブの色を読み取ることができません。そこでセットするときに、白のセンター・キューブをU面、青のセンター・キューブをR面に向けるという制約をつけることにしました。

f:id:tfitv:20200610154757j:plain

 

この位置で面の色の読み取り実験をしたところ、leJOSの既存のライブラリではキューブ面の6色(白、黄、赤、青、橙、緑)を確実に識別できないという致命的な問題があることがわかりました。ただ、カラーセンサーには測定値をRGB値で返すモードがあるので、機械学習を使ってRGB値から色を識別することができるかもしれません。
機械学習を実行するためには、キューブの色とそれに対するRGB測定値のデータを多数用意する必要があります。そこで、大量のデータを自動的に採取するためにビデオに示すようにソルバーの機構全体を形作りました。このときキューブをL面側から抑える機構を加えたので、R面、D面の回転動作を安定化することもできました。そして自動的にすべての面のRGB値を読みとるプログラムを実行して、学習用:960個、評価用:240個のデータを用意しました。


RCS ColorDataAcq

ステップ6 3層のニューラル・ネットワークによる色の識別1

ステップ5で取り込んだデータを使って、最初に入力層と出力層で構成される単純なニューラル・ネットワーク(NN)で面の色の識別実験を試みましたが、赤と橙がどうしても分離できません。つまり、線形分離はできないのです。そこで、非線形に対応できるように入力層、隠れ層、出力層からなるNNに拡張し、試行錯誤を重ねた結果、正解率を98%まで向上させることができました。(写真) しかし、それでは不十分で、100%にしなければ先には進めません。

f:id:tfitv:20200607155015j:plain

ステップ7 3層のニューラル・ネットワークによる色の識別2

その後、カラーセンサーの位置、機構、アルゴリズムを見直し、学習用のデータを取り直して、入力層、隠れ層、出力層からなるNNでの実験を重ねた結果、キューブ面の色の識別実験において、240個のテストデータに対して100%の正解率を得られるようになりました。色の識別が最大の懸念事項だったので、これで大きなヤマを越えることができました。


機械学習実験20190816

ステップ8 キューブの初期状態を認識

ここまでくると、あとはそれまでモジュール毎に確認したことをEV3の実機に移植していく作業です。最初にAIによる色の識別処理を実装してキューブの初期状態を認識できるようにしました。そして、キューブの上段を揃えるところまで作りました。(ビデオは作った本人以外には退屈な内容なので途中8倍速で再生しています。)

 

ステップ9 キューブの整列

残りは、すでにステップ3で確認しているLBL法による中段、下段の整列のアルゴリズムをEV3に移植することです。
それを完成させて、任意の状態に崩されたルービック・キューブを自動的に解くロボットが完成しました。 

下のビデオはそのデモンストレーションで、任意に崩したルービック・キューブを本装置にセットすると、最初に面の色を識別し、その後、LBL法で上段から順に整列させていく様子をご覧いただけると思います。

 


Rubik's Cube Solver