LEGO Mindstorms Rubik's Cube Solver
Since I first made Tilted Twister, LEGO has released a
new version of LEGO Mindstorms which is not compatible with Tilted
Twister. I have received loads of email
with questions about Tilted Twister and LEGO Mindstorms 2.0. I'm really
sorry I haven't been able to answer all.
I am therefore very pleased to announce
Tilted Twister 2.0
Features
- Solves a standard Rubik's cube No need to replace any color stickers
- Can be built from a single LEGO Mindstorms NXT 2.0 set
- Completely stand-alone No need to connect a computer
- No web cam needed It detects the colors using the LEGO Mindstorms color sensor
- Support for
Herbert Kociemba's Two-Phase Algorithm
- Free programs and building instructions
The
challenge was to build the robot using a single LEGO Mindstorms
NXT-kit. And to make it completely independent, without need of being
connected to a computer.
The Lego Mindstorms NXT kit contains
three servo motors and a set of sensors (touch, color and ultrasonic).
How should I build the robot using only theese items?
After a lot
of experimenting I came up with a solution - If I tilted the whole
robot, it would be possible for it to tilt the cube using only one
motor, leaving the other two motors for twisting the cube and for
positioning the color sensor. Thus Tilted Twister.
Color recognition
Even if the LEGO Mindstorms color sensor is very accurate, it is hard to distinguish between the red and the orange colors. The corners are no problem, there is redundancy in that it is possible to use the colors of two sides to determine the color of the third. The center cubies have even more redundancy. The only thing I had to consider was the Rubik's logo on the white center cubie, which gives undefined color readings. The edge pieces are hardest to resolve. For example to determine whether an instance of a cubie is red/blue or orange/blue. By converting RGB values to hue and saturation and comparing them (orange has a somewhat higher hue/saturation compared to red) it is possible to resolve even these.
Calculating a solution
I
wanted the robot to be completely independent, without the need to
connect to a computer. This puts some demands on the program. Of the
size of the program and memory usage. And not least of performance. The
performance of NXT’s processor is quite sufficient for typical
robot-tasks. But when it comes to heavy calculations it is
significantly slower than an ordinary computer. This rules out
heuristic-algorithms (which generates near optimum solutions, with
approximately 20 face turns). Instead I tried to find a method to solve
the cube, whith limited number of algorithms but that still would
generate a solution with not too many moves. First I implemented a
quite simple layer by layer algorithm. This gave a solution with an
average of almost 100 face turns.
I have then implemented a
corners-first
method
which generates a significantly shorter solution.
The average is about 60 face turns (which I think is pretty good for a
general solution). As a matter of fact, the program
calculates
three solutions with different starting points, and picks the shortest.
Herbert Kociemba's Two-Phase algorithm
To
get an even quicker solve, it is possible to connect Tilted Twister
to a computer via Bluetooth to calculate a shorter solution. I have
used
Herbert Kociemba's fantastic Two-Phase algorithm which I use in
a Java Application. This produces a solution of typically 21 face turns
in just a second.
Performance
Stand-alone:
Scanning the cube: 45 seconds
Calculating a solution: 20 - 40 seconds
Executing the moves: 1 - 5 minutes
Average total time: 6 minutes
Connected to computer:
Scanning the cube: 45 seconds
Calculating a solution: 1 second
Executing the moves: 1 - 2 minutes
Average total time: 2.5 minutes