The was much media consternation when aviation police recently announced that a British Airways plane had been struck by a drone while approaching Heathrow Airport.
Since then, it transpires that the "drone" may well have actually been a plastic bag, but if it was a UAV then perhaps a new algorithm developed by roboticists from MIT might have helped. It allows swarms of robots to avoid moving obstacles while staying in formation.
Centralised vs Decentralised
Normally, planning algorithms for teams of robots come in two flavours - centralised and decentralised. Centralised algorithms let a single computer make decisions for the whole team, while decentralised algorithms let each bot make their own decisions based on local observations. As you might expect, the latter are harder to design but more resilient if something goes wrong.
The algorithm developed by the MIT researchers is decentralised, uses significantly less communication bandwidth than existing algorithms, and - most impressively of all - can cope with both static and moving objects while preserving strong guarantees that robots will avoid collisions.
In simulations using squadrons of miniature helicopters, the swarm was able to preserve an approximation of its preferred formation (a square) while still dodging around moving obstacles throughout their flight path. Occasionally they would fly single-file or assume a more vertical formation when the situation was particularly tricky.
Exciting Result
"It's a really exciting result because it combines so many challenging goals," said Daniela Rus from MIT's Department of Electrical Engineering and Computer Science, whose group developed the new algorithm.
"Your group of robots has a local goal, which is to stay in formation, and a global goal, which is where they want to go or the trajectory along which you want them to move. And you allow them to operate in a world with static obstacles but also unexpected dynamic obstacles, and you have a guarantee that they are going to retain their local and global objectives. They will have to make some deviations, but those deviations are minimal."
The next step for the team is to test a new version of the algorithm on wheeled robots, whose goal will be to collectively carry objects across a room where human beings are also moving around - simulating an environment where humans and robots are working together.
