Rubik's Solver Software

Recently, Ben Katz and I collaborated on a Rubik's Cube solving robot to try to beat the world record time of 0.637 seconds, set by some engineers at Infineon.  We noticed that all of the fast Rubik's Cube solvers were using stepper motors, and thought that we could do better if we used better motors.  So we did:

Our solve time of 0.38 seconds includes acquiring the image from the webcam, detecting colors, finding a solution, and actually rotating the faces of the cube.  In the video, the machine is solving a "YJ Yulong Smooth Sitckerless Speed Cube Puzzle", available on Amazon for $4.55.  We used the cheapest cube we could find on Amazon Prime because we thought we'd end up destroying many of them, but somehow ended up only going through 4 cubes and 100's of solves.

Ben made a blog post that describes the hardware and build as well as the insane nonlinear minimum-time sliding mode controller which let us do 90 degree moves in around 10 ms.  We used Kollmorgen ServoDisc motors, which have a very high torque-to-inertia ratio.  The motor is coreless, so there are no heavy steel laminations on the rotor, and there's no steel to saturate, so it can accelerate insanely fast.  In a 10 ms quarter-turn move, the motor reaches over 1000 rpm. 

On the software side, I used OpenCV for the color detection and this fantastic implementation of Kociemba's Two-Phase algorithm called 'min2phase' .  We used Playstation 3 Eye webcams, which are only $7 on Amazon Prime, and work at 187 fps under Linux.  The software identifies all the colors, builds a description of the cube, and passes it to the min2phase solver. The resulting solve string is converted to a compact cube sequence message, and is sent to all motor controllers simultaneously using a USB to serial adapter connected to a differential serial IC.  This whole process takes around 45 ms.  Most of the time is spent waiting for the webcam driver and detecting colors.  All our software is on GitHub here: https://github.com/dicarlo236/cube-solver


The motor controllers step through the moves one by one and remain synchronized with the AND BOARD, which tells all the motor controllers when the current move is finished. 

Programming an ATMEGA328PB with avr-gcc

Atmel/Microchip have recently released the ATMEGA328PB, a microcontroller that's very similar to the ATMEGA328B commonly found in Arduinos.  The new features are:

• Slightly lower price
• Two more good timers
• Extra UART, SPI, and I2C
• 4 more PWMs

There are some major drawbacks though

• No more full-swing crystal oscillator
• Didn't work with the Arduino IDE when I tried
• Most toolchains don't support it yet out of the box

To program it with avr-gcc and avrdude requires a few extra steps.  These steps are written for a Linux development computer and a usbasp programmer.

The first step is to download and install the usual versions of avrdude, avr-gcc, avr-objcopy, avr-binutils, and avr-libc.  On Ubuntu, these are all packages that can be installed with apt.

The version of avrdude I have (6.2) didn't know about the 328pb, so I had to modify the avrdude.conf file.  On my install of Ubuntu 16.04, this was in /etc/avrdude.conf.  At the bottom, I added the lines:

part parent "m328" id = "m328pb"; desc = "ATmega328PB"; signature = 0x1e 0x95 0x16; ocdrev = 1; memory "efuse" size = 1; min_write_delay = 4500; max_write_delay = 4500; read = "0 1 0 1 0 0 0 0 0 0 0 0 1 0 0 0", "x x x x x x x x o o o o o o o o"; write = "1 0 1 0 1 1 0 0 1 0 1 0 0 1 0 0", "x x x x x x x x x x x x i i i i"; ; ;

which I got from here: https://lists.nongnu.org/archive/html/avrdude-dev/2016-06/msg00010.html

This is the same as the normal 328b, but has the correct device signature for the 328pb.  As far as I can tell, the device signature is the only difference between the two.

Next, we need to download a "pack" from Atmel's that tells gcc about the 328pb.  I downloaded the Atmel ATmega Series Device Support Pack from packs.download.atmel.com 

I had to copy all the *.h files from within the pack to /usr/lib/avr/include to get the avr io headers to work properly.  I also put all the other files from the pack into a folder called `packs` in my project folder.  Inside the packs folder should be folder like "gcc, include, templates..."

Now we can program the microcontroller:

First, compile the code with

avr-gcc test.c -DF_CPU=1000000 -mmcu=atmega328pb -c -B packs/gcc/dev/atmega328pb/

then, create an ELF then intel hex file with

avr-gcc -o test.elf test.o -DF_CPU=1000000 -mmcu=atmega328pb -c -B packs/gcc/dev/atmega328pb/

avr-objcopy -O ihex test.elf test.hex

finally, program the microcontroller.  This command attempts to set a very low programming clock speed to be safe.

avrdude -c usbasp -p atmega328pb -B 60 -U flash:w:test.hex

Debugging with GDB on an mbed STM32 Nucleo

Having a real debugger is incredibly useful, and it turns out it's not too hard to get GDB working on the STM32 Nucleo development boards with Linux. It's also a nice and very fast way to load code onto the Nucleo with no internet connection required.  Here's what I did to get debugging working on my Nucleo.

First, we need to install the compiler, debugger, openOCD, and make:

sudo apt install make gdb-arm-none-eabi gcc-arm-none-eabi openocd

To get the makefile and mbed libraries, I created a new project on the mbed compiler website, right clicked on the project in the tree on the left, and exported the project as "Make_gcc_arm", and unzipped the file.

Next, we need to retrieve the configuration files for the board and its interface.  On my computer, the openOCD script files were stored in /usr/share/openocd/scripts.  The file for the ST-Link is interface/stlink-v2-1.cfg, and the file for the micro itself is board/st_nucleo_f4.cfg.  I copied these two files to my project folder.


The default Makefile doesn't turn on debugging symbols, so it needs to be modified.  In the "Tools and Flags" section of the makefile, I added a '-g' flag after 'arm-none-eabi-gcc' for CC and CPP.  I ran make, which complained about clock-skew, but produced a BUILD folder with bin, elf, hex, and .o files. 

Next, we need to set up the connection between the ST-Link and the computer.  This is done with openOCD (on-chip-debugger).   OpenOCD must be started in the folder where you've copied the .cfg files for the ST-Link and the board.  To start the program, run


sudo openocd -f st_nucleo_f4.cfg -f stlink-v2-1.cfg -c init -c "reset init"

There may be an "already specified hl_layout stlink" error, but this shouldn't cause a problem.  You should see near the end of the output "target state: halted", the 3.3V supply voltage, and a few of the CPU registers.

Next, we need to run gdb with `arm-none-aebi-gdb`.  You should do this in the project folder - the one which has the BUILD folder in it.  To connect to OpenOCD, run `target remote localhost:3333`.  Next, we need to tell gdb which program we are trying to debug by running `file BUILD/project_name.elf`.  It may warn you that there is a program being debugged already, but you should press 'y' to force gdb to load the debugging symbols for the most recent build.  

The next step is to get the microcontroller ready to receive the program.  Sometimes you can get away with skipping these steps.  Run 'monitor reset' then 'monitor halt' to put the micro in a good state.  

Now we can load the firmware onto the microcontroller by running 'load'.  If at any point you change the source, all you need to do is run make, then run 'load' from gdb.  If the nucleo goes into a bad state, you can reset it with the 'monitor reset' command in gdb.

To start running the program, run 'continue'.  Surprisingly, almost every feature of GDB actually works in this setup.  I can view and modify local variables, arguments, and globals, can view registers, can use the hardware breakpoints and watchpoints of the microcontroller, and can pull up the source code for some of the mbed libraries as well.