Swarms of drones flying in terrifyingly perfect formation could be one step closer, thanks to a control algorithm being developed at MIT.
The complexities involved in controlling teams of moving robots so they don’t crash into each other, or indeed wipe out other objects/entities that cross their path, is a hard problem that continues to keep roboticists busy.
But the team of researchers at MIT reckon they have made a breakthrough that could make perfect complex drone formations easier to pull off. They say their decentralized planning algorithm can handle both stationary and moving obstacles, and do so with reduced computational overheads.
Why are decentralized control algorithms better than centralized control algorithms? The basic answer is they are more resilient, given a centralized algorithm has a single point of failure if its central controller goes offline.
The researchers also assert that decentralized algorithms have the advantage of handling erratic communication better than centralized algorithms. And what’s more potentially erratic than a swarm of flying robots? But, on the flip side, they are also harder to design, given that all the moving pieces have to be involved in doing a bit of the thinking.
“In a centralized algorithm a single entity has all the information and finds a solution. In a decentralized algorithm each entity (robot) has only partial information of the environment and the other robots (for example, it can only see a few neighbors). The robots need to communicate to pass information and coordinate,” explains, Javier Alonso-Mora, one of the researchers involved in developing the algorithm.
Up til now, most research on decentralized control algorithms has focused on making collective decision-making more reliable, according to the group — deferring the (hard) problem of avoiding obstacles which they have rather chosen to drive straight at.
“The closest applications [for the algorithm] would be drone swarms navigating in formation, for example for surveillance of an area, mapping of an environment,” adds Alonso-Mora, discussing potential future applications for robot teams. “And mobile manipulators collaboratively carrying objects on the factory floor.”
Last year the team demoed a centralized version of the algorithm using a pair of wheeled robots tasked with carrying an object together. You can see a video of that project on YouTube here.
Their decentralized algorithm requires what they say is significantly lower communications bandwidth, as well as lower computation cost, thanks to the distributed way it makes robots share intel on obstacle-free regions in their immediate vicinity.
How does this work? Instead of each robot broadcasting to every other robot a complete map of safe space around it, the decentralized algorithm has robots only share maps with their immediate neighbors and also has each calculate where neighbors’ maps intersect with their own — sharing only relevant intersected data on to the next neighbor. So the idea is that, collectively, the team of robots maintains a comprehensive map of safe terrain while reducing the comms data needed to keep the swarm moving.
“The robots do not communicate the position of all the obstacles they see. Instead, they communicate the region (set of linear constraints/convex region). So, they all get an overview of the ‘free space’ without a need to know where all the obstacles are.”
“This scales well in scenarios with many obstacles,” adds Alonso-Mora.
As well as mapping 3D space, the algorithm also includes a fourth dimension — time — to allow swarming bots to predict the trajectory of moving obstacles and re-route their own formation accordingly.
This process does involve some guestimation, with the researchers noting that it works in a “mathematically compact manner” by assuming that moving obstacles have a constant velocity. Obviously that assumption is not always true, but given that each robot updates its map several times per second they reckon it’s a short enough time span/margin of error to handle most accelerating objects, given that most moving obstacles will not dramatically change velocity at very high speeds.
So far the researchers have tested their algorithm with simulated drones and say it came up with the same flight plans they’d expect a centralized control algorithm to.
This resulted in squadrons of virtual mini helicopters “generally” maintaining an approximation of their preferred formation (a square at a fixed altitude), but with the square sometimes rotating to accommodate obstacles and/or the distances between drones contracting. “Occasionally” the drones would also fly single file or assume a formation in which pairs flew at different altitudes, they add.
They have also tested the decentralized algorithm on physical (wheeled) robots, and suggest such a scenario could be useful to further use-cases where teams of robots are expected to work in environments also containing humans.
“We are working on a demonstrator with real vehicles as well as similar applications,” says Alonso-Mora.
He adds that they “may” also experiment with actual drones at a later stage, too. (Presumably there’s rather higher costs involved with testing the robustness of control algorithms if your control robots are flying around mid-air… )
The researchers will be presenting their paper at the International Conference on Robotics and Automation next month. Expect to wait rather longer to see a perfect formation of drones buzzing over your city.
“At this stage it is research,” stresses Alonso-Mora, going on to note that many big challenges remain when it comes to creating robust algorithms for controlling robot teams.
“Accounting for the robot dynamics. Long term guarantees in dynamic environments with many moving obstacles. Communication/networking issues in real systems. Perception of the environment. Just to name a few.”