Monday, 20 June 2011

Lego Mindstorms – Rubik’s Cube Solver

Lego  Mindstorms – Rubik’s Cube Solver
Alexandru Safcencu


The Swedish programmer Hans Anderssen has designed in 2008 a robot, using Lego Mindstorms NXT 1 kit, that solved a Rubik’s cube autonomously via Herbert Kociemba’s Two-Phase Algorithm. Over the time, other programmers attempted to build robots such as his and have proven to be faster and better at detecting the colors of the cube.
Inspired by Anderssen’s creation, the author of this dissertation took the challenge of  improving Andersson’s initial project so that it could match the performances of other similar projects, only using original Lego hardware.
To reach that goal, the author of this dissertation proposed to swap the Lego light sensor, used by Anderssen, with Lego’s latest color sensor. After doing some research, the author of this dissertation realised that the color sensor would indeed solve the color detection problem and thus it would be a useful implementation.

While Anderssen’s robot was able to solve a cube in approximately five minutes, his competition managed to build robots that would do it in less than a minute. To solve that problem, the author of this dissertation proposed that he would build a Java application which would make computing a solution considerably faster. The author also suggested that he would base the Java application on the Bluetooth connectivity.

While Anderssen’s robot could not calculate a solution for a cube using heuristic methods due the limited computing power available, building a Java solution that would run on a computer would allow the implementation of a more optimal algorithm. This approach would lower the time it takes the robot to solve the cube in two ways:

1) The java application on the computer can make use of the powerful processor and compute a solution in a couple of seconds.
2) Because the java application has a heuristic algorithm implemented (still based in Two-Phase algorithm) it could compute a shorter solution of up to twenty moves. A shorter solution would mean less moves for the robot to perform and a shorter overall time of execution.
Out of these objectives, the author of the dissertation has managed to fully implement the Lego color sensor and partially implement the Java application. The robot can solve a Rubik’s cube autonomously using the color sensor but it cannot receive a solution from the Java Application. Up to this point, the author of this dissertation has managed to implement the Bluetooth connectivity within the Java application which successfully connects the computer to the robot. 




BSc and HND Computing Provision (click on the links below for more details of the courses)
The University of Northampton's, Department of Computing and Immersive Technologies offers five courses within the MSc Computing postgraduate provision (shown below) all available either part-time or full-time.