Tilted Twister

Tilted Twister
a Lego Mindstorms robot that solves Rubik’s cube

Tilted Twister solves Rubik’s cube fully automatically.
Just place the scrambled cube on Tilted Twister’s turntable. An ultrasonic sensor detects its presence and starts to read the colors of the cube faces using a light sensor. The robot turns and tilts the cube in order to read all the faces. It then calculates a solution and executes the moves by turning, tilting and twisting the cube.

The challenge was to build the robot using only the Lego Mindstorms NXT Retail-kit. And to make it completely independent, without need of being connected to a PC.
The Lego Mindstorms NXT Retail-kit contains three servo motors and four sensors (touch, light, ultrasonic and sound). 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 turning the cube and for positioning the light sensor. Thus Tilted Twister.
Color recognition

While rotating the cube, the top face colors are scanned using the light sensor. It is actually possible to see difference between colors using only the light sensor. But unfortunately some of the colors of a standard Rubik’s cube are impossible to distinguish from one another. The white and the yellow colors of the cube gives the same light sensor readings. Likewise are the red and the orange ones very close to each other.
To avoid confusion I replaced some of the colors on the cube.
After that, it reads the colors of the cube perfectly. Only if you have a strong lightsource right above the robot it might fail.

Tilted Twister also supports HiTechnic color sensor. If replacing the light sensor with a color sensor, there's no need to replace any stickers.
Calculating a solution



I wanted the robot to be completely independent, without the need to connect to a PC. 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 PC. This rules out heuristic-algorithms (which generates sub 30-moves solutions). 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 moves.
I have now implemented a corners-first method which generates a significantly shorter solution. The average is just below 60 faceturns (which I think is pretty good for a general solution).
Performance

*
Scanning the cube: 1 minute
*
Calculating a solution: 20 - 40 seconds
*
Executing the moves: 1 - 5 minutes. Average 4.5 minutes (60 faceturns)
*
Average total time: 6 minutes