ARM Community: Oh No, Not Another ARM Powered LEGO Rubik's Cube Solver! - ARM Community

It's been a while since the video of my Android MultiCuber 777 cube solving robot was uploaded to ARM’s YouTube channel - ARMflix. Since then, I’ve also demonstrated the Android Speedcuber at a number of events including ARM TechCon 2010. However, I've finally found enough spare time to create a new robot. For those of you who've been following my blogs and have read this far hoping to hear about another LEGO Rubik's Cube puzzle solving robot, I'm sorry to disappoint you... my latest creation does not solve a Rubik's Cube puzzle. In fact, it doesn't even solve a cube-shaped puzzle at all! Take a look at the video below, which has already been featured by Engadget, to see the ARM Powered Android Megaminxer solve the Megaminx dodecahedron-shaped puzzle using an HTC Desire smartphone with Qualcomm Snapdragon processor and be entertained by some unusual disco antics. Then read on to find out about some of the challenges I overcame in developing this robot.



The Challenge – Non-Cubic
If you've read my other blogs, you'll know that I can't resist a challenge. A number of comments on the videos of my previous creations asked about solving non-cubic puzzles. At first I responded, perhaps cheekily, asking “does the V-CUBE 7 7x7x7 puzzle solved by Android MultiCuber 777 count as “non-cubic” because of its curved faces?”

But in my heart, I couldn’t even convince myself that this puzzle was really not a cube, so I continued to think about an alternative. I’ve had a Megaminx puzzle in my collection for a while and it occurred to me that this might be an appropriate challenge, so I started to think of a way to create a robot to solve it.

The Mechanism – LEGO Is Not Just For Squares! :)
The Megaminx puzzle is a dodecahedron consisting of 12 pentagonal faces each with 5 edges. The faces can be turned in a similar way to the regular Rubik’s Cube puzzle to change the relative positions of pieces on each edge and corner of the puzzle. I realised that the principles of the mechanism used in MultiCuber 777 could be adapted to manipulate the Megaminx. I described in a previous blog how MultiCuber uses two square rings, one fixed and one rotating, to turn two adjacent layers of the cube shape puzzle so I reasoned that two pentagonal rings could be used to turn the faces of the Megaminx.

I started playing with LEGO when I was about 5 years old and have spent many fun hours trying different ways of building interesting shapes and mechanisms. When LEGO introduced Mindstorms NXT centered around an ARM7 microprocessor, I was in heaven as it enabled me to create a wide variety of robot designs.

Most LEGO bricks are just that – bricks. Essentially blocks with right-angles between the faces. However, because they are connected by round studs, they can be joined at arbitrary angles. This method allowed me to create the required 5-sided rings with careful use of sloping LEGO bricks to fit snugly round a face of the Megaminx.

The tilting mechanism for MultiCuber supports rotations by 90 degrees about a horizontal axis through the centre of two opposite faces of the cube to allow different faces of the cube to be directed towards the turning mechanism. Applying a similar technique to the Megaminxer resulted in a tilting mechanism consisting of an angled bracket which rotates about an axis through the centre of two opposite faces of the dodecahedron. However, in order to orientate the puzzle to keep the top and bottom faces horizontal and always pointing in the same direction to match the fixed pentagonal ring in the turning mechanism, the axis of rotation is at an angle to the horizontal.

MultiCuber’s rotating cage serves two purposes. It is used to turn faces and inner layers of the cube and also to rotate the entire cube. Since the Megaminx has sloping rather than vertical sides, it could not be raised into a cage so I had to devise an alternative mechanism to rotate the entire puzzle. I engineered a gearing mechanism connected via universal joints and a pivoting mechanism to allow the motor driving the turning rings to rotate a wheel at the top of the piston which lifts the Megaminx. When this piston is about half way between the tilting bracket and the turning rings, the gears are engaged so that the same motor which turns the faces via the rings can also turn the wheel on the piston to rotate the entire dodecahedron.

You can see these three mechanisms, the turning rings, the tilting bracket and rotation wheel if you watch the video closely during the solve.



The Software – Just Minor Changes?
Over the years I have developed quite a bit of code and one of the lessons I’ve learned is to consider writing generic algorithms and data structures, even when the initial requirements may be for a specific case. You never know when you may want to re-use the code on a different project with slightly different requirements. Fortunately, even when I’m just coding for fun, I tend to do this even when it may seem like a little more effort.

The table-driven methods that I developed for my range of solvers were relatively easy to adapt, even though I had assumed that they would only ever be required to solve cubic puzzles. For example, the data structures I used in my first Nokia N95 based Rubik’s Cube solver, represent the pieces as a sequence of edges around each face. Although I had used the hard-coded constant 4 for the number of edges, it was straightforward to change this to a symbolic constant that I could then modify to 5 in just one place for the pentagonal faces of the Megaminx (of course I ought to have used a symbolic constant in the first place but nobody’s perfect! :)

Instead of using a 3-dimensional array or similar to relate the faces of the cube, which could have been a natural choice for a cube solver, I originally chose a more general data structure to describe the relationship between faces which was relatively easy to adapt to the dodecahedron.

All of my table driven algorithms are fairly generic. Even the high performance algorithm used in the latest Android Speedcuber could be applied to puzzles other than the regular 3x3x3 cube. However the memory requirements for puzzles with more pieces would be prohibitive. So I simply adapted the algorithm I developed for the first Nokia-based robot. In the same way that the data structures for the puzzle itself were configurable, the representation of move sequences, table indexing and even the table generation required only relatively straightforward changes.

I also had to modify the image capture and colour sampling code to consider the different number, shape and position of each piece. The colour discrimination was probably one of the hardest parts of the project because the Megaminx has 12 colors rather than 6 on the cubic puzzles. The larger number of colors and specific colors used on the Megaminx meant that they are closer together in the colour spectrum and harder to distinguish (in particular the light, mid and dark greens caused me rather a headache!). But I managed to refine the method I described in my in a previous blog.

Choice of Android App Development Environment
The core solving algorithm for the latest Android Speedcuber used the Android NDK to compile C++ into code to execute natively using the ARMv7 instruction set architecture to achieve the maximum performance from the 1GHz Qualcomm Snapdragon platform in the HTC Desire smartphone.

However, the code base that I used for this project was written in Java, and I decided to focus on just making the robot work rather than aiming straight for the fastest possible speed, I used the Android SDK for the entire app for Megaminxer for convenience. The ARM Solution Center for Android (SCA) is a good place to start if you’re considering developing your own Android app.

The Robot Is Only The Beginning
Developing the robot is only part of what goes into the videos on ARMflix. Several of my colleagues have worked extremely hard on the video production side. I think Scott Sartain was inspired when said that the multi-faceted Megaminx reminded him of a mirrored disco ball :) Thanks guys! I must say an extra thank you to Tanya Zielke for creating some of the wonderfully fun graphics for the Android Megaminxer video. Some of the early comments left by viewers indicate that you’ll either love them or hate them… You should judge for yourself, but I hope most of you, as I do, will absolutely love them! :)



***Remember to check out the feature on Engadget!

Update - Wow!
I'm flattered. The video has been viewed on YouTube over 10,000 times in just the last few hours :)

Shortlink to this post: http://bit.ly/hjgQ6F


David Gilday, Principal Engineer, ARM, It all started with LEGOs. When asked what I was going to do when I grew up, I gave the answers that everyone expected of me…"train driver" or "fireman". But secretly I dreamed of a job where I could spend all my time building things with my favorite toy... Well thanks to ARM's cool technology it has come true (well in-between my regular day job anyway)! As I got older, I became interested in puzzle solving, electronics and programming and my "expectations" gradually changed from train driver to chip designer. However, my hobby and dream have remained essentially the same and I continue to enjoy dabbling in construction, electronics, mathematics and software programming in my spare time.