Monday, March 24, 2008

Amazing - Robot Solves Cube



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 of the cube. 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 lightsensor. Thus Tilted Twister.



Color recognition

While rotating the cube, the top face colors are scanned using the lightsensor. It is actually possible to see difference between colors using only the lightsensor. But some of the colors on the standard Rubik’s cube were hard to distinguish from one another. The blue and the green colors of the cube were very close to each other. Likewise were the red and the orange ones. To avoid confusion I replaced some of the colors on the cube. (Cubesmith.com has replacement stickers in all sorts of colors.) After that, it reads the colors of the cube perfectly. Only if you have a strong lightsource right above the robot it might fail.

Tilting, turning and twisting the cube
The tilter arm pushes the side of the cube until it tilts over and slides back. The construction of the tilter arm along with the sloping turntable enables this in one moment. The cube is turned by the motor connected to the turntable. Lego Mindstorm’s servo motor is very accurate, and the built in tacho counter makes shure it doesn’t ”hesitate”. There is no need for other easurements to align the turntable after turning it. To twist the bottom face, the tilter arm holds stil the upper and middle layers of the cube while the turntable rotates the bottom face.

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 to 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
[via - tiltedtwister]

Enjoy the Amazing Video Below -

No comments:

Post a Comment