Self organizing swarms are fascinating. If you have grown bored with watching ants or termites do their thing, you can now watch a swarm of 1000 tiny robots making shapes without anyone having overall control. 

We have covered Kilobot robots before, but this is the first time they have achieved the goal implied in their name - i.e. a 1000 robot swarm. Kilobots are small and very simple. They move using vibration channeled through three small wire legs. This is cheap, but it does means that the robots move comparatively slowly and this accounts for the long times it takes for the swarm to build the target shape. 

Kilobots can basically move in a given direction, communicate with neighbors and sense neighbors. It is the ability to sense neighbors that gives the Kilobot its ability to self organize. 

Take a look at the following video made by the Harvard Self-organizing Systems Research Group: 

What is more interesting than just seeing the robots form up is how they do it. 

The most important point is that all of the robots get the same program and yet the end up in different parts of the shape. At first this seems fairly magical, but when you start to think about it it is something that all cellular automata depend on. For example, each cell in the game of Life runs the same program, but some cells turn on and some turn off. If rules involve the state of a neighbour then the same program running on all of the Kilobots can produce different behavior in each Kilobot. 

The algorithm is quite clever. Four seed robots are placed next to an initial swarm. These serve to establish a co-ordinate system that each robot can use, i.e. the robots position themselves relative to the seed robots. The seed robots are the only robots that have a different program and they simply stay where they are put.  

One of the seed robots also sends out a message "a gradient" of zero that is used to give all of the robots a sense of where they are in the swarm.  All of the robots set their gradient to one more than the lowest value of the gradient that their neighbors are transmitting. For example, robots close to the seed have a gradient of 1, robots close to the gradient 1 robots assign themselves a gradient of 2 and so on. 

All of the other robots receive the same program which contains a picture of the shape the robots are trying to build as a bitmap. Only robots on the edge of the swarm start moving into a new position. The robots know that they are on the edge because they have a gradient value bigger then any of their neighbours. If the robot has neighbors that have the same gradient value then a locally unique ID number is used to break the tie and one of the maximally distant robots starts to move by following around the edge of the group in a clockwise direction.

Eventually it encounters three robots that know where they are in the co-ordinate system or the seed robots. Either way it can use this information to work out where it is in the co-ordinate system and hence if it is inside the desired shape or not. It then continues to follow the edge until either it is about to exit the shape or it encounters a robot that has already stopped and has a gradient value greater than its own - in either case it stops.  

How the entire process stops depends on how many robots there are and the size of the shape. If there aren't enough robots then they all stop but the shape is incomplete. If there are just the right number then they all stop and the shape is complete. Too many robots and the shape is complete but some robots continue to circle the edge trying to find a location and some never move from their original location.

There are lots of fine details omitted from this account of the algorithm, but this is the essential plan. As a result of the way the gradients are used as starting and stopping conditions the shape tends to be built up in layers of constant distance from the seed robots.

Now have another look at the video and see it all in action.  

I hope it makes a lot more sense now!

The algorithm is based on morphogenic gradients and is similar to the "grassfire" geometry invented by Harry Blum in 1967. In this cellular automata have rules that depend on a depth field, i.e. their shortest distance to the edge of the shape.  

Comments

Make a Comment or View Existing Comments Using Disqus

or email your comment to: comments@i-programmer.info