Friday, August 15, 2014

Robot swarm shuffles into formation

Engineers in the US have built a swarm of 1,000 little robots that can shuffle into specific formations on command.


Each of the identical robots is given a picture of the required shape, and then they work together to make it happen.


It takes up to 12 hours, but then this is the biggest throng of robots ever built and studied in this way.


Inspired by biological examples, like cells forming organs or ants building bridges, the work could help develop self-assembling tools and structures.


'Each robot is identical and we give them all the exact same program,' explained Dr Michael Rubenstein, the first author of the study, which is published in Science.


'The only thing they have to go on, to make decisions, is what their neighbours are doing.'



The robots are 3cm across and cylindrical - about the size of a sushi roll. Dr Rubenstein and his colleagues at Harvard University dubbed them 'Kilobots' and built 1,024 of them altogether: the same as the number of bytes in a kilobyte.


'Start Quote



Actually watching the experiment run is like watching paint dry'



End Quote Dr Michael Rubenstein Harvard University


Each Kilobot shuffles on three straight, spindly legs, chosen because they are cheaper than wheels. The robots' arena is a large wooden square, about the size of a tournament snooker table, complete with edges to stop them waddling off the edge.


Blinking lights


At the start of an experiment, the whole bristling crowd is bunched up together on one side.


Overhead hangs an infra-red light, which can communicate with the swarm thanks to an infra-red sensor nestled on each robot's underside. That light only sends one command, however: 'go'.


When that happens, all the robots start their program. The same program.


A random selection will start first, if they are in a position to move: inching slowly around the table and flashing their own infra-red lights to broadcast information to the other Kilobots nearby.


'Start Quote



Increasingly, we're going to see large numbers of robots working together'



End Quote Prof Radhika Nagpal Harvard University


So that they know where to start the shape they've been programmed to make, four 'seed' robots have already been placed in a suitable position by one of the scientists. The seed robots kick off a coordinate system, which spreads through the swarm via those infrared lights, bouncing off the table from any transmitting robot to anyone 'listening' within 10cm.


'Each robot looks at its current state - so, what have I done in the past - and also looks at what its neighbours are doing, based on communication. And it makes its own decisions,' Dr Rubenstein told the BBC.


'Running this identical program, all the robots are capable of taking turns to join the shape.'


Individually, the Kilobots have very limited capabilities and they also make mistakes. But the algorithm made specially to govern their behaviour is able to overcome these limitations.


In designing their robotic swarm, the researchers drew inspiration particularly from ants. Masses of army ants, Dr Rubenstein explained, also produce structures that defy the limitations of an individual six-legged specimen.


'The structures that ants form are relatively different from the structure that we were able to form, but it's the same type of principle,' he said.


The whole process is also incredibly time consuming.


Dr Rubenstein said he hasn't taken his Kilobot show on the road anywhere, and doesn't even tidy the robots away when they're finished: 'We just leave them sitting on the table. It would take a couple of hours to pack them into a box.'


Even watching the programmed images take shape, over six to 12 hours, is far from a spectator sport.


'It wasn't very exciting,' said Dr Rubenstein, who 'usually stuck around' to take notes, in case of a mishap. 'Actually watching the experiment run is like watching paint dry.'


Nonetheless, the Kilobots have attracted considerable interest since the team first unveiled them at a conference in 2012. All the code involved is open-source, and a company is selling the robots for around $100 each.


'Start Quote



This goes well beyond the state of the art in robotics, as the algorithm copes with huge numbers of robots even in the presence of failure'



End Quote Dr Roderich Gross University of Sheffield


Tipping point


The potential applications go much further than throwing very slow shapes on a very big table.


Prof Radhika Nagpal runs the lab where the experiments were done. 'Increasingly, we're going to see large numbers of robots working together,' she said, 'whether its hundreds of robots cooperating to achieve environmental cleanup or a quick disaster response, or millions of self-driving cars on our highways.'


'Understanding how to design 'good' systems at that scale will be critical.'


Researchers in the UK are also impressed.


'Performing self-assembly with a thousand-robot swarm is a remarkable feat,' said Dr Sabine Hauert, a robotics lecturer at the University of Bristol, '[especially] given the advances needed to build hardware that is affordable and easy-to-use, and design algorithms that scale to large numbers of unreliable robots.'


She told BBC News the study shows we are reaching a 'tipping point' in swarm engineering, where computing and hardware can both be scaled up to big experiments like these.


Dr Roderich Gross, a robotics engineer at the University of Sheffield, is a paid-up fan: his laboratory has acquired 900 of the robots, to run their own tests.


'The Harvard Kilobot system is not only the largest swarm of robots in the world, but also an excellent test bed allowing us to validate distributed algorithms in practice,' he said.


'The Kilobot swarms are able to attain an arbitrary shape. This goes well beyond the state of the art in robotics, as the algorithm copes with huge numbers of robots even in the presence of failure.'


Meanwhile Prof William Harwin, who studies cybernetics at the University of Reading, was most taken by the scale of the project and the manual labour involved. 'The most impressive thing is that they built 1,000 robots,' he said.


Figuring out how to transfer this sort of new technology rapidly to the production line, Prof Hardwin noted, would be 'the game-changer'.


Follow Jonathan on Twitter