How Harvard’s 1,024 robot swarm does what it does

Researchers at Harvard University’s school of engineering have been puzzling over autonomous robot collaboration – in particular, how do you get robots that can only sense a short distance to make something big without an all-seeing eye or central control to direct them.

And recently they have had some success – getting 1,024 ‘Kilobots’ to huddle into pre-defined patterns, and three construction robots to make simple buildings.

Kilobots are extraordinarily simple, designed at Harvard to be ant-like and mass-produced cheaply – they are now available from a Swiss company called K-Team.

Each Kilobot is essentially a 33mm diameter PCB standing on three 20mm long rigid wire legs.

Intended for use on a smooth surface – Harvard has a 2.4×2.4m table – Kilobots are shaken forward by vibration from two phone-style vibrator motors on the PCB.

By spinning the motors at different speeds, Kilobots can creep forward, turn left, or turn right.

Power for three hours of travel comes from a Li-ion battery carried on top. Charge control is included on the PCB, with charge power coming from voltage applied between any leg and a spring on top of the battery.

On-board, an 8bit Atmel microcontroller (2kbyte RAM, 32kbyte ROM) does the thinking, and a top-mounted tri-colour LED displays status to human observers.

Perhaps the most crucial piece of equipment is a wide-angle infra-red transceiver mounted underneath in the centre of each Kilobot. Infra-red from this bounces off the white table top to be picked up by other nearby Kilobots.

Kilobots swarm following the map on the left.


Communication range is up to 10cm, and the intensity of received IR gives the robot some idea of the distance between it and its neighbours. Distance estimation varies somewhat from robot to robot, and is not identical in all directions, so control algorithms have to be tolerant of these vagaries.

This limited communication range gives swarm members their short-sightedness. If a neighbour is more than 10cm away, a robot cannot have any direct knowledge of it, only knowledge that has been passed via others.

For convenience, all members of the swarm can be programmed simultaneously by an over-head optical transmitter. All members of the swarm, except four in the pattern-forming experiment, get the same programme.

The universal programme includes a map of the required pattern in the form of a coarsely-pixelated grid (see photo), with pixels set to 0 (leave empty) or 1 (fill with robots). Pixels only indicate the pattern to be filled, not exact final robot positions – there is no intention to achieve one-robot-per-pixel in a square grid. Robots fill the required shape in a largely random arrangement with average inter-robot spacing determined by a pre-programmed value – more of this later.

Starting position

All the Kilobots are closely packed into one arbitrarily-shaped swarm, adjacent to where the final pattern is required (see photo).

The four unique robots are seeds, placed within range of each other on the edge of the starting swarm.

The seeds will not be moving, and will eventually be just inside the edge of the finished pattern. One of them is programmed to be the origin of the finished pattern: x=0, y=0.

How big is the swarm?

All robots transmit and receive frequently. When a message is received, as well as decoding it, the recipient estimates how far away the transmitting robot was.

One number passed between robots is ‘gradient’. All robots listen for gradient values coming from neighbours. They assume a gradient value one more then the lowest value they hear, and transmit this new value.

At the start, only the origin robot knows its gradient value, which is set to ’0′. This it transmits, and a neighbour receiving this 0 gradient value assumes its own gradient value ’1′, and transmits this. Depending on how they are positioned, neighbours of these two hear 0 or 1 as the lowest value in earshot, and assume 1 or 2 respectively.

The overall effect is that gradient numbers, on average, increment along straight lines away from the origin robot like spokes in a cartwheel. Lines drawn between robots with equal gradient values will form loops around the origin.

These loops are actually near to circular as there is a further restriction in gradient dissemination: robots have to ignore values sent from greater than a pre-programmed range. When this is set closer to 33mm, gradient value contour loops are closer to circular.

Any robot that can only hear robots of lower or equal gradient value, know they are on the edge of the swarm, and know roughly the size of the swarm, even though the centre is way beyond their 10cm communication range.

Off I go

Until now, all robots have also been transmitting an ‘I am stationary’ message.

Robots that know they are on the edge of the swarm start to move forwards and right, while staying a pre-programmed fixed distance from any neighbour they approach – it is this distance which will eventually govern final image inter-robot spacing.

This simple rule causes edge robots to orbit the coastline of the swarm, each performing a part-circle around every individual on the coast before passes on to its neighbour.

Where am I?

The four seeds have the beginnings of an x-y grid programmed into them and, by each measuring their distance to the other three (many times to reduce noise), they can calculate an estimate of their x-y coordinates on the required image pixel grid. Once they have estimated their position, they are ‘localised’ and transmit their x-y positions.

Triangulating on three neighbours gives three different positions on the plane. A simple mathematical algorithm gets best positional accuracy by ‘minimising the spread’ of the three positions, said Harvard.

Kilobots swarm following a different map.

Once the seeds have localised, their neighbours can also localise and the x-y grid spreads through the swarm as soon as any non-localised robot can triangulate on three localised neighbours.

Moving edge robots continually recalculate their position (and gradient value) to remain localised, and continue to transmit their position for the use of others.

Are we nearly there yet?

Eventually, an edge-following robot, comparing its estimated position to its internal pixel map, will know it has entered the required pattern. It will continue to edge-follow inside the image.

It will stop when it: is about to leave the required image, or it bumps into a robot of equal gradient value that has already stopped – which the moving robot knows because the stationary one will be sending out an ‘I have arrived’ message.

These two simple stopping rules cause the image to fill-out with approximately concentric arcs of stationary robots centred on the origin robot.

What could possibly go wrong

All sorts of mix-ups are possible – for example: too many robots moving off the starting coastline at the same time, sticking vibration motors, faster robots catching up with slower ones, or clumsy robots knocking others from their final resting place.

A few simple rules have been developed to sort these situations.

Where rules cause stalemate between two robots, the robot with the highest ID number wins.

These ID numbers are randomly self-allocated. If two robots with the same ID come into range, they both randomly recalculate – which can result in a ripple of re-calculation should a new number match another local. ID numbers are locally unique, but may not be globally unique.

Algorithms cause and cope with odd situations

In experiments, 1,000 Kilobot images (see K photo) have taken up to 11 hours to form.

Multiple attempts at forming identical shape and size rectangles with a smaller number of Kilobots have shown the algorithms are robust – the rectangle is always formed, even though the pattern of robots within each rectangle is different in each case.

Why not just simulate the whole thing?

“We can simulate the behaviour of large swarms of robots, but a simulation can only go so far,” says Professor Radhika Nagpal. “The real-world dynamics, the physical interactions and variability, make a difference, and having the Kilobots to test artificial intelligence algorithms on real robots has helped us better understand how to recognise and prevent the failures that occur at these large scales.”

3-D construction robots

In a separate project, called Termes, Harvard has taken inspiration from termites.

This involves 3-d rather than 2-d construction, and robots carrying and placing square tiles to make a structure rather than making a pattern out of their own bodies.

The tiles have the proportions of Scrabble tiles, although they are considerably larger.

Termes robots have four types of sensor and three actuators. They can travel horizontally, climb one tile, or descend one tile, while carrying another tile, which they can deposit in front of themselves – so they can make their own staircase of tiles.

Also, as they can turn around on the spot, they can also construct a staircase with right-angled bends.

The desired structure is described as an x-y-z grid of whole tiles.

Rather than provide each robot with a 3-d map of the finished structure and have it decide its own method of construction – with the inherent risk of one robot stranding another – an off-line compiler turns the structure definition into a construction plan, for any number of robots, which is a series of paths, consisting of flat sections and staircases. All directions are left, right or straight. There are no diagonal paths.

To avoid congestion, this plan has one or more routes up and one or more paths down.

Where ever a robot is, which it knows by always starting at tile 0,0,0 and counting whole tiles in x, y and z, its stored path information tells it which direction, or directions, it can move away from its current position.

When it come across a place where a tile should be, it deposits its load and moves down for another tile.

The exact set of rules followed by Termes robots are created by the compiler for the particular job. The compiler also rejects structures that are impossible to build.

Like Kilobots, once Termes robots leave the construction site they edge-follow the incomplete structure to the point that come across spare tiles, then edge follpw around to tile 0,0,0 whee the construction path always begins.

Harvard has proved that locally-collaborating robots can construct large pre-defined structures, rather than needing central control and long-distance communication.

And while centralised systems can have good group efficiency and fast recovery from problems, Harvard points out that central control fails when the central controller breaks, and it also proposes that central control might not be the best solution with large numbers of robots, over wide areas, or in remote locations.

“We’ve proven the extreme end of the scale: that it could be just like the termites. And from the termites’ point of view, it’s working out great,” says Nagpal. “It may be that, in the end, you want something in between the centralised and the decentralised system.”

The Kilobot experiment is described in the 15th August issue of Science, and Termes in the 14th February issue and at the AAAS 2014 Annual Meeting. Research was supported by the Wyss Institute for Biologically Inspired Engineering at Harvard University.

There is a Harvard Kilobot swarm video. Scroll down.

steve bush

from News http://ift.tt/1phn1gH

via Yuichun