Software apps and online services
Hello, my name is Daniel Walton. I am a computer engineer living in the southeastern United States. I like to build crazy EV3 projects using ev3dev so this challenge was a lot of fun :) My entry is called CraneCuber. It is a voice controlled robot that solves 2x2x2, 3x3x3, 4x4x4, 5x5x5 and 6x6x6 rubiks cubes! It is a mashup of a LEGO crane, EV3 Mindstorms and Alexa.
Here is a video of CraneCuber in action:
The original version of this robot did not use Alexa but I think it was a nice addition. My favorite part was using Alexa to tell the user facts about the Rubik's Cube being solved. The 5x5x5 for instance has a huge number of possible states but without Alexa this wasn't something the robot could easily convey to the user.
The story of this robot goes back a few years. Like many other owners of an EV3 Mindstorms and an old Rubik's Cube, I built MindCub3r. Here is a video of my MindCub3r build in action, this was running on ev3dev.
MindCub3r was designed by David Gilday, he published build instructions and the software. MindCub3r is very cool but it is limited in that it can only solve a 3x3x3 Rubik's Cube. I decided that I wanted to build a LEGO robot that could solve larger cubes. David Gilday built such a robot called MultiCuber but he did not release build instructions or software for it.
I contacted David to try to talk him into open sourcing the project but he decided to keep it close sourced. I thought to myself "well, I guess I'll just do this on my own then". Had I known how much time this would end up taking I am not sure I would have tackled the project. I learned a ton along the way though and I even ended up using CraneCuber to help land my current engineering job (I gave a presentation on it as part of my interview) so it was well worth it in the end.
It took me 2 or 3 weeks to design the initial build of CraneCuber. It used three motors:
- The Elevator - moves the entire cube up and down
- The Flipper - rotates the entire cube one quarter turn forward or backward
- The Turntable - rotates a single face of the cube
The main challenge was making the robot strong enough to avoid flexing and twisting when the Turntable was attempting to rotate a cube face. If the robot flexed too much the Turntable would end up under-rotating the cube face which would later cause the cube to jam up.
I did some research on trusses and found that a Brown Truss worked best for this robot. A Brown Truss looks like a big X. You can see the Brown Trusses used for the main frame on the left and right sides of CraneCuber. I also use a Brown Truss to hold the large motor used for the Elevator. This one is more difficult to see as it is in the rear of the robot.
While researching trusses and how to make LEGO builds stronger I read one very helpful quote, "Triangles are magic!". There are several places in the build where I used a beam to create a triangle to strengthen the robot. The robot is now very sturdy, you can pick it up with one hand from just about any point and it doesn't flex at all.
This is the first revision of CraneCuber in action. I'll discuss all of the software involved a little later in this document.
The first revision worked well for 2x2x2, 3x3x3 and 4x4x4 cubes. 5x5x5 and 6x6x6 cubes kept jamming up though which prevented CraneCuber from being able to solve them. The problem is really one of accuracy with the LEGO motors. You can tell the motor "turn 120 degrees" but it won't always turn exactly 120 degrees, sometimes it will go 118, the next time 123, the next time 121, etc.
The Elevator and the Flipper can be off by a few degrees and still do their job. If the Turntable under-rotates or over-rotates though the face of the cube becomes somewhat misaligned which can cause the cube to jam up when we attempt to rotate the next face of the cube.
I decided that after the Turntable finished rotating a cube face, I needed a way to "squish" the sides of the cube in order to make sure the cube was nice and flush. I added a fourth motor which I will refer to as "The Squisher" for the rest of this document. The Squisher mechanism consists of two walls, one is stationary while the other moves from outside towards the inside. Together the two walls squish the sides of the cube and correct any alignment errors that were caused by the Turntable under-rotating or over-rotating. You can see The Squisher in action here:
Note that the second revision is the design used in the Alexa enabled CraneCuber shown in the opening video at the top of this document.
The physical design and building of the robot is a very small part of the CraneCuber story. There are tens of thousands of lines of code and a few hundred hours of work behind the software. We can break the software down into three main sections:
- What are the RGB (Red, Green, Blue) values for each square?
- Translate each RGB value to one of six cube colors (white, yellow, red, orange, blue, green)
- What sequence of moves to solve the cube?
MindCub3r uses the LEGO color sensor to find the RGB (Red, Green, Blue) values for each square. This is not possible for CraneCuber though as initially it does not know what size cube it is solving so it wouldn't know where to position the color sensor or how many squares to scan.
CraneCuber instead uses a web camera to:
- photograph all six sides of the cube
- locate all squares in each image
- extract the RGB values for every cube square on every side
I will walk through the process for one of the cube faces photographed of the 5x5x5 in the opening video at the top of this document. The images below are the debugging images collected while I was filming the video.
The first step is very simple, we take a photograph of one side of the Rubik's Cube
The second step is to create a grayscale copy of the image and apply an anti-noise filter
The third step is to use Canny Edge Detection to find all of the edges in the image
The fourth step is to dilate the edges. We want to make them thicker as it makes the squares of the cube a little easier to find.
The fifth step is to find all of the contours of shapes in the dilated image. In the image below the blue lines are the various contours found in the image. The red lines are the approximate shape for each contour. We examine all of the shapes of the red lines to find the ones that look like squares (has four corners, each corner is roughly 90 degrees, etc). If we think the contour is of a square we display that contour in green.
The sixth step is to remove the non-square contours
The seventh step is to remove gigantic contours. There was only one gigantic contour in the image above, it was a contour that went around the outside edge and included almost the entire image.
The eighth step is to remove dwarf contours, these are the contours that are simply too small to be a Rubik's Cube square.
The ninth and final step is to determine the size of the cube, the boundary of the cube and remove any contours outside the cube boundary
We do the steps above for all six sides and extract the RGB values for all 150 squares of the 5x5x5 rubiks cube.
This software is open source and is available on github at https://github.com/dwalton76/rubiks-cube-tracker
This has become a popular repository, it has 73 stars on github. Here is a video of the rubiks-cube-tracker software being used to find a Rubik's Cube in a video stream.
We now need to take the RGB values for all 150 squares and reduce each square down to one of six colors (white, yellow, red, orange, green and blue). This will give us the state of the cube which is needed in order to calculate a solution to solve the cube.
This image displays the color of each square as extracted from the images in the previous step. Note that there is some variation in the colors, not all white squares are exactly the same white, orange and red sometimes look very similar, etc.
In order to reduce each RGB value down to one of six colors (white, yellow, etc) we are going to sort the colors. Once they are sorted we can easily divide them into six groups of equal size and assign a color name to each group.
For humans sorting colors is very easy, it turns out that for computers it is quite challenging. If we take the colors above and simply sort them by their RGB values we get the following which you can see is not at all in the order that you or I would sort these colors.
If we instead sort them by HSV (Hue, Saturation, Value) the sorting is better but still not correct:
After much trial and error I have found that what works best is to use a Travelling Salesman algorithm to sort the colors. You can see here that we could divide the colors into six clean groups.
The Travelling Salesman problem is a famous computer science problem. The problem it is solving is of a salesman that must visit multiple cities in the most efficient order possible (in terms of total distance traveled).
There are many libraries and algorithms out there for solving the travelling salesman problem, I used the tsp_solver python library. We plot the 150 RGB values in 3D and use the Travelling Salesman algorithm to find an ideal order to visit them in. The order found by Travelling Salesman provides the order in which to sort the colors. Visually it looks like this in action:
Here you can see all of the edge pieces (a 5x5x5 has two groups/orbits of edges) as sorted by Travelling Salesman. We can easily divide these into six groups and assign each group a color name.
We also sort the center pieces and corner pieces via Travelling Salesman and assign each square one of six colors. You'll notice in the image below there is no longer variation in the colors, all of the white squares are exactly the same, all of the blue squares are exactly the same, etc.
It took a lot of work to get here but at this point CraneCuber knows the exact state of the cube. This allows us to calculate a solution for how to solve the cube.
This software is open source and is available on github at https://github.com/dwalton76/rubiks-color-resolver
Software based rubiks cube solvers are a huge topic, students have done their PhD on algorithms to solve the 3x3x3 alone. I will describe how I ended up writing my solver and how it works at a high level but to go into great detail would be beyond the scope of this document (and this document is already pretty long).
When I started working on CraneCuber I did not intend to write my own rubiks cube solver. There are dozens of open source solvers out there for 2x2x2 and 3x3x3 cubes but not nearly as many people have tackled writing solvers for 4x4x4 and larger cubes. I was able to find exactly one open source solver for 4x4x4 but that is where the well ran dry. There were not ANY open source solvers for 5x5x5, 6x6x6, etc :( I decided I would write my own solver with a few goals in mind:
- it would be open source
- it would an NxNxN solver, meaning it could solve any size cube
- it would be able to run on minimal hardware, such as a Raspberry Pi
It took about 5 months of work to get it to solve a 4x4x4 and 5x5x5 and another 5 months to achieve NxNxN! I have continued to work on the solver over the past year, I have been able to reduce the amount of time it takes to calculate a solution as well as the length of the solution that it finds.
I feel confident in saying it is the only open source NxNxN solver in the world, I am pretty proud of it :) The solver is available on github at https://github.com/dwalton76/rubiks-cube-NxNxN-solver
The heart of software based Rubik's Cube solvers is an algorithm called Iterative Deepening A*. You will often see this abbreviated as IDA* (pronounced I-D-A-star).
The problem that a Rubik's Cube solver must solve is to find a sequence of moves that will take the cube from the scrambled state to the solved state. We could write a solver that would do a brute force breadth first search through increasingly longer sequences of moves until it found a solution but we would die of old age long before it finished. We need a smarter and faster way of finding a solution!
IDA* is an algorithm that allows the solver to eliminate huge sections of move sequences while searching for a solution. It does not work well enough to optimally solve a 5x5x5 cube but it does work well enough to solve some subset of the cube, such as solving the centers. Once the centers are solved we can use IDA* again to solve the edges. These are known as "phases". We can break the problem of solving a cube up into multiple phases and then use IDA* to solve each phase. The larger the cube the more phases are required to solve the cube. Most 3x3x3 solvers use two phases while my solver uses seven phases to solve a 5x5x5.
This was a very short introduction to how software based Rubik's Cube solvers work. I did a lengthy blog article on this subject that is available at http://programmablebrick.blogspot.com/2017/07/rubiks-cube-solver.html if you are interested in more details on how cube solvers work.
I hope that you enjoyed my project. I have really enjoyed working on it :) My apologies for such a long write-up on how it works. There is so much involved on the software side of the project I felt like I should give an in-depth explanation.