Andrew Wilson, Editor, [email protected]
In 1974, Erno Rubik, then a lecturer in the department of interior design at the Academy of Applied Arts and Crafts in Budapest, Hungary, invented what was to become a world phenomenon--the Rubik’s cube. More than three decades later, the invention has led to a number of world competitions, spin-off products, and Web sites, the best of which is www.rubiks.com.
For many, the challenge of the Rubik’s cube lies in how fast the toy can be unscrambled, a record currently held by 20-year-old California Institute of Technology student Leyan Lo, who last year solved the puzzle in 11.13 seconds. For students at the Carinthia University of Applied Sciences (Villach, Austria; www.fhkaernten.at/eng), however, the challenge was to build an autonomous robotic system that detects the state of the cube and computes and controls a robotic system to solve it. A group led by Thomas Klinger, along with Christian Madritsch and students in the department of electronic and electrical engineering at Carinthia, demonstrated the finished system at this year’s NIWeek conference and exhibition (August 2006; Austin, TX, USA).
“Initially,” says Christian Cemernjak, who demonstrated the robot at the show, “the task of solving the problem may seem daunting. In a Rubik’s cube, 26 individual cubes comprise a single large cube. Each layer of the nine smaller cubes can twist, and the layers can overlap. Any three squares in a row, except diagonally, can join a new layer. Because of this, a Rubik’s cube can have approximately 43 quantillion different solutions.” Despite this large combination, the puzzle can be solved using a maximum of 29 possible moves.
Three main subsystems comprise the robot’s design. First, an image-processing and analysis stage detects the scrambled state of the Rubik’s cube. Second, the number and types of rotation operations needed to unscramble the cube are computed. Last, these instructions are transmitted to a robot control subsystem consisting of three independent grippers with two degrees of freedom that unscramble the cube.
After a cube is placed in the system in a scrambled state, each of the colors on three sides of the cube must be analyzed. The patterns on the remaining three sides can then be calculated. To do this, a DFW-Vl500 FireWire camera from Sony (Park Ridge, NJ, USA; www.sony.com/videocameras) is mounted above the robot stage (see photo). Images from this camera are then transferred to a CVS1455 Compact Vision System from National Instruments (NI; Austin, TX, USA; www.ni.com) for image analysis.
“To properly compute all nine colors on each of the three sides of the cube,” says Cemernjak, “the range of all possible colors is first digitized as RGB information and translated into a hue, saturation, and luminance (HSL) model using NI Vision Builder software. The nine possible hue values are classified by thresholding the hue information, effectively building a nine-color classifier that is stored in the memory of the CVS.”
After a scrambled cube is placed in the robot, the camera digitizes an image of the cube, and an edge-detection algorithm locates each of the nine color elements in the field of view. After the image is scaled and rotated, a histogram equalization is performed on the hue value and the result compared to that in system memory. The cube is then rotated by the robot grippers until images of all three sides have been digitized and the color of each individual color elements is identified.
The output of this image analysis is a string containing all of the information in all of the 6 × 9 = 54 color planes. Using the format RGGRWRWY, each letter corresponds to a color, and the position of the letters corresponds to their position on the cube. After the string is computed, it is transferred over a serial interface to an NI cRIO-9004 real-time controller, where the necessary list of robot movements is calculated.
Several different algorithms currently exist to solve the Rubik’s cube (see table). “In comparing these different algorithms,” says Cemernjak, “it can be seen that the A* (A Star) algorithm requires a very long calculation time, and the “God’s algorithm” is not feasible since the cube has too many possible positions and the memory requirement is too high. Thistlethwaite’s algorithm also requires a lot of memory space, and the average solution takes longer than other algorithms. Although the best fast algorithm uses less memory, the calculation time is still too long.
Because of this, a “two phase” algorithm, originally developed by Herbert Kociemba (www.kociemba.homepage.t-online.de) best fits the problem of automated cube solving. This two-phase algorithm performs an iterative search on a unary tree using additional heuristical information. Using less than 20-Mbyte memory, the algorithm can compute a solution in about 20 moves.
Using NI’s cRIO-9004 real-time controller as target platform, the list of necessary movements is calculated in a few seconds. This list consists of rotation operations by 90° or 180° for each side of the cube. These results then drive digital output signals from the cRIO-9004 to a custom-built motor controller PCB, which drives motors and the three independent grippers of the robotic subsystem.
Under control of the cRIO-9004, these grippers can be opened, closed, and turned around their main axis using two dc motors. During cube movement, two grippers hold the cube, and the third gripper performs the rotation operation. A simple user interface controls start/stop buttons and an LCD displays output status information. During robot control, the list of movements from the solving algorithm is transformed into individual movements of each gripper. After all the required movements have been carried out, the solved Rubik’s Cube can then be removed from the system.
