Hex Bug Swarm

About a year ago I participated in an art project for a hackathon where we wanted to have a swarm of "creatures" under computer control. The concept called for these creatures to participate in a simulated society, which would be guided by a crowd of humans online. They had to look like real animals, at least when viewed via a cheap webcam. We had a budget for materials, but it was fairly small and had to include many things other than robots.

For me it was an exciting challenge: hack together a capable robot swarm on a shoestring budget and on a hackathon's timeframe. I wanted to answer the question: What does it take to get a bunch of robots moving around on a surface under the control of a computer? To get started I went looking for prior art, and found the following representative projects:

  • Kilobots (story) - Move on little stilt legs by vibration. Communicate with each other using reflected light. Various sources claim $14 per robot but commercially it costs $1127.28 for a pack of 10 robots ($112.73 per robot).
  • AERobot - Can be purchased from Seeed Studio for $20 per robot. Uses vibration for motion, plugs directly into USB port.
  • Jasmine - ~$120 per robot.
  • mROBerTO - From University of Toronto.
  • Droplet - From University of Colorado Boulder. Nice open design.
  • R-One - From Rice University.
  • Zooids - From Stanford University - design is open source.
  • Actuated Workbench - Uses magnets in a surface to actuate a swarm of magnetic objects (nice quote: "...the actuated workbench works even when set on fire").
  • Madgets - Also uses magnets under a surface to actuate objects above.
  • Tangible Bots - Robots used as interface elements on tabletop display (paper).
  • Thumbles - Swarm of robots with omni-wheels used for tabletop display interfaces.
  • BitDrones - Drone cubes for 3D user interfaces. 3 types: 1) Pixel Drones (w/ OLED display) 2) Shape Drones (cube) 3) Display Drones (big display).
  • "Image and Animation Display with Multiple Mobile Robots".

All of these projects are fascinating and accomplish different goals using a swarm of robots. However they are all similar in that they all take advantage of expensive custom hardware to achieve their research goals. In one case, the Kilobots project, a claimed goal is affordable hardware ($14/robot claimed in this Fast Company article), but the real cost is much higher ($112.73/robot).

I wanted to make a truly cheap swarm. So I looked to consumer electronics and searched for devices that had the basic capabilities I needed to serve as a starting point. That led me to the Hexbug Fire Ant toy.

Each one of these toys has tank-style driving remote-controlled by an infrared controller. They can move forward and backward and turn in either direction. Unfortunately the communications are not separated into channels, so any robot will react to the signals sent by any controller. All I wanted for my base was wireless control and the ability to move anywhere on a 2D surface, so the Hexbugs were enough to go on. I got 28 to serve as raw material for my swarm. Each cost <$20 at the time, though at the time of writing the price has risen to twice that.

Reverse Engineering the Communication Protocol

The first thing I did when I got the toys (after driving them all over my floor) was try to figure out how the infrared remote control works so I could control a robot from my computer. I broke open a controller and connected a probe to its IR LED. I also broke open a robot and soldered a wire to the output of its IR sensor. Then I drove the robot around with the controller while capturing with my logic analyzer and saw traces like the following:

Pushing the back button on the left side

There's a 38 KHz carrier and a simple short/long bit encoding scheme. Every message starts with an extra long pulse. And then one can choose to interpret short pulses as zeroes and the longer pulses as ones. The last 6 bits of the message vary between commands.

I pushed all the buttons, recorded the messages sent, and manually decoded them into this list of available commands:

  • STOP = 0b000001
  • FORWARD = 0b000111
  • BACKWARD = 0b011001
  • LEFT FORWARD = 0b000011
  • LEFT BACKWARD = 0b010001
  • RIGHT FORWARD = 0b000101
  • RIGHT BACKWARD = 0b001001

Then I slapped together my own controller using a Raspberry Pi, an AVR microcontroller, and a large IR emitter. I called it the Horus Eye after the Egyptian god of the sky (among other things).

The huge capacitor is to filter noise on the 5V rail from rapidly flashing the LEDs

I included a camera because I wanted to eventually use it to track the robots for closed loop control. But to get started I wrote a Python program to control a single robot using a PS3 controller:

Hacking the Hardware

All of this initial work gave me a basis for experimentation, but it did not get me a swarm. If every robot responds to every command then there is no way to individually control them. To achieve that I would need to modify the toys. And to be able to modify them I needed to understand how they work. So I set about dissecting one.

When reverse engineering hardware my first step is often to take it apart and take the best pictures I can of the top and bottom of the PCB. I bring the photos into Photoshop and use the Warp Perspective tool to precisely line up the two sides of the PCB. Then I carefully trace the copper on each side to produce a map of the circuit that I can refer back to while I work out exactly what everything does.

There are very few parts in the control circuit for the toy. The main parts are the visible-light LED, two motor driver ICs, a glob top IC, a button pad, and an IR sensor. Everything is powered by a stack of coin cell batteries. Two DC motors drive the wheels of the robot via a gear train.

I did not see a way to convince the controller under the glob top to control the toy any differently, so I decided to start my modifications by removing it. If you are lucky these epoxy blobs can be cleanly removed with careful application of some flush cutters.

With the original controller gone I needed to add my own to get the toy to do anything again. When I was tracing the PCB I noted that the pinout of the motor drivers conveniently placed VCC and ground on the same pins as an ATtiny10 in its small outline transistor (SOT) package. The ATtiny10 in the SOT package has only 4 I/O pins, and one of those is the RESET line by default.

ATtiny10 SOT pinout
Motor drivers- one removed to reveal the pinout

If I just wanted to drive the robot around then 4 pins is plenty because each motor driver uses 2. But I also want to receive communications from the outside world, so I probably need at least one I/O pin for that. To overcome this I decided to sacrifice some mobility. If I lost the ability to reverse on the right side then I could free up a pin for communications but still drive anywhere if given some extra time to spin all the way around. Because of the pin mapping the modification turned out to be fairly clean, requiring the microcontroller and just two wires.

It's a little hard to see but there is an ATtiny10 riding the the motor driver on one side. A short wire jumps over to the motor driver on the opposite side. And a longer wire jumps to the demodulated output of the IR sensor.

The parasite successfully infected the host. The toy is a zombie under its control.

I wrote some initial basic firmware that just turned the motor control pins on and off over and over to see that the microcontroller was working as expected. Then the real work began: I needed to implement a new communication protocol that would allow every robot in a swarm to be individually controlled.

The Zombie Language

All that was needed was a way for a given robot to receive the same control commands as the original toy, but know whether or not it should follow them based on its unique ID. Then the remote control system can individually control every robot in the swarm by giving them commands one by one.

One of the first questions is: how much data should be sent for each command? We need to address the robot we want to command and tell it what we want it to do, so there will be an address and command portion in every message. There are 4 commands (2 bits) but maybe I will want to add a few later, so I need at least 3 bits for them. I wanted to support a reasonable swarm. I had 28 robots to control. So I chose 5 bits for the address, to let me support swarms up to 32 robots in size. 3 bits + 5 bits = 1 byte, which is nice. That's the size of the registers on the AVR CPU in the ATtiny10, so that size will make it easier to write the code for handling communications.

I ended up writing the firmware in assembly. You can find it on GitHub here. But I'll go over the most significant parts of the code here. Let's look at initialization and the main loop first:

; Execution starts here
reset:
  ; Set outputs for controlling motors
  sbi   DDR_MOTOR, PIN_REV_L
  sbi   DDR_MOTOR, PIN_FWD_L
  sbi   DDR_MOTOR, PIN_FWD_R

  ; Enable TIMER0 with 64 divider (15625/s at 1MHz)
  ldi   r16, 0x3
  out   TCCR0B, r16

  ; Enable PCINT0 (on PB0)
  ldi   r16, 1 << PCINT0
  out   PCMSK, r16

  ; Enable pin change interrupts
  ldi   r16, 1 << PCIE0
  out   PCICR, r16

  ; Enable interrupts
  sei

loop:
  rjmp	loop

During initialization the code configures the I/O pins we need for output, starts a hardware timer to use as our sensor-sampling clock, and enables the pin change interrupt for the sensor I/O pin. Then the main loop just does nothing forever. Everything the robot will do will happen when requested by a command that is received, so the real action will happen in the IR sensor interrupt handler.

.macro measure_pulse
  in    r16, TCNT0L
  in    r17, TCNT0H
time_pulse_start_wait_%:
  sbis  PINPORT_RX, PIN_RX
  rjmp time_pulse_start_wait_%

  ; Calculate pulse length

  in    r18, TCNT0L
  in    r19, TCNT0H

  ; r18:r19 is pulse length in clock1 ticks
  sub   r18, r16
  sbc   r19, r17
.endm

; Receive IR packet
ir_interrupt:
  ; Exit interrupt if we are not here because of a falling edge
  sbic  PINB, PIN_RX
  reti

  ; Prevent further interrupts while we are handling this one
  cli

time_pulse:
  ; Measures length of first pulse
  ; and skip if it is not a (long) start pulse
  ; 1.193ms (0x1F timer diff) is a long pulse

  measure_pulse

  ; Exit interrupt if this is not a long pulse

  ldi   r16, low(PULSE_LONG)
  ldi   r17, high(PULSE_LONG)

  cp r18, r16
  cpc r19, r17
  brlt ir_interrupt_done

  ; It's a start pulse!
ir_interrupt_start:
  ; Sample the rest of the bits in the incoming message
  clr   r20 ; For the received bits
  ldi   r21, PACKET_BIT_COUNT
ir_interrupt_read_bit:
  sbic  PINPORT_RX, PIN_RX
  rjmp  ir_interrupt_read_bit

  measure_pulse

  ldi   r16, low(PULSE_MED)
  ldi   r17, high(PULSE_MED)

  cp r18, r16
  cpc r19, r17
  brlt ir_interrupt_read_bit_0

ir_interrupt_read_bit_1:
  sec
  rjmp  ir_interrupt_read_finish
ir_interrupt_read_bit_0:
  clc
ir_interrupt_read_finish:
  ror   r20 ; Shift received bit in

  dec   r21
  brne  ir_interrupt_read_bit

  ; We are done reading the packet! Received value in r21
  mov   r21, r20

  ; Does the ID match ours?
  andi  r20, 0x1F ; Mask the ID (lower 5 bits)
  cpi   r20, MY_ID
  brne  ir_interrupt_not_me ; (Nope)

  ; The command is addressed to us!
  ; Let's decode and execute it
  mov   r20, r21
  andi  r20, 0xE0 ; Mask the command (upper 3 bits)
  cpi   r20, CMD_STOP << 5
  brne  ir_interrupt_check_fwd_l

  rjmp ir_interrupt_done
ir_interrupt_check_fwd_l:
  cpi   r20, CMD_FORWARD_LEFT << 5
  brne ir_interrupt_check_fwd_r
  rjmp ir_interrupt_done
ir_interrupt_check_fwd_r:
  cpi   r20, CMD_FORWARD_RIGHT << 5
  brne ir_interrupt_check_rev_l
  rjmp ir_interrupt_done
ir_interrupt_check_rev_l:
  cpi   r20, CMD_REVERSE_LEFT << 5
  brne ir_interrupt_done
  rjmp  ir_interrupt_done

ir_interrupt_not_me:
ir_interrupt_done:
  ; Re-enable interrupts and resume doing nothing
  sei
  reti

Short and sweet, only a couple dozen instructions. When a message starts there is a long start bit which triggers the IR interrupt. The handler then starts measuring the lengths of the incoming pulses (using the measure_pulse macro). Short pulses are interpreted as zeroes and long pulses are interpreted as ones. Once all 8 bits have been received the address is checked against that of the robot. If it matches then the command is decoded and executed, changing the states of the I/O pins to drive or stop the motor on each side of the robot.

Raising a Zombie Swarm

So now there is a way to tell individual robots what to do. The rest is easy, right? All we have to do is modify the rest of the toys and we have our robot swarm. Easy.

Not so.

If you have ever done short-run electronics manufacturing you know how this goes. You pour effort into a beautiful design, make a working prototype, sit back and look at it running on your desk, and bask for a fleeting moment in the thought, "ah, my work is finally done." Then you blink, and free fall down out of the bright sunny space above the clouds into the cold black abyss of reality. You don't just need one, you need 10 or 100 or 1000. Your work has just begun.

So it was for me building my robot swarm. For each of the 28 robots I carefully flashed the microcontroller with the firmware containing the robot's unique ID, chopped off the top of the toy, popped the glob top off with clippers, applied the modification under a microscope with tweezers and soldering iron, tested it, and fixed any issues if necessary. It probably took a solid 8 hours to finish, but in the end I had the bodies for my swarm:

I removed their wheels so they could not rise up against me

With the hardware ready I set about the next phase of the project, coordinating the swarm and putting them under precise control.

Controlling the Swarm

As a simple test I extended my PS3 controller code to let me select individual robots to control.

It was fun to drive them around this way, and for a moment I considered adding support for multiple controllers and racing robots with my friends. But time for the project was running out. A human controlling a single robot would not do. I needed a crowd of humans to control a swarm of robots.

Controlling this swarm is challenging because of a couple of factors. Communication is in one direction, from the control system to the robots, so it's not possible to ask the robots about their states. The robots don't have sensors besides the IR receiver so they do not have anything interesting to say anyway. So although the robot with a given ID can be told to move in any direction, without information about where it is and what direction it is facing it's not really possible to get it to a specific location. That's where the camera on the Eye of Horus comes in.

With a camera mounted above the space the swarm occupies it's possible to figure out where robots are and where they are facing by telling random robots to move and watching what parts of the image change. I used a technique called optical flow analysis implemented in Python using the computer vision library OpenCV to find regions of the video with movement and identify what direction the movement happened in. Once I had that information I was able to label robots and track their positions and orientations over time.

The next step would have been to write a motion planner to make it possible to specify a path for each individual robot to follow. But the project deadline loomed large and we had to cut things short to complete the art installation. I used what I had to link activity in the artificial society simulation (code here) to the activity of random robots. It turned out to be enough to produce relatively lifelike movement.

The Art Installation

To complete the illusion we were aiming for, of a group of animals controlled by the aggregate activity of humans, we covered each of the robots in hair:

Viewed from above via webcam they actually looked fairly convincing. The movements were a little more like those of insects than furry mammals, but it was close enough for us.

For the final setup we put the robots in an aquarium with plants and rocks to mimic a natural environment.

So ends the saga of the swarm. But you can read about the overall art project that this was a part of in this article on the MIT CAST website.