Swarms of UAVs flying in perfect formation could be one step closer thanks to a control algorithm being created at MIT (Massachusetts Institute of Technology). The complexities involved in controlling teams of moving robots so they do not crash into each other, or indeed into other objects/entities that cross their path, is a challenging 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 decentralised planning algorithm can handle both stationary and moving obstacles, and do so with reduced computational overheads.
Why are decentralised control algorithms better than centralised control algorithms? The basic answer is they are more resilient, given a centralised algorithm has a single point of failure if its central controller goes offline.
The researchers also assert that decentralised algorithms have the advantage of handling erratic communication better than centralised 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 centralised algorithm a single entity has all the information and finds a solution. In a decentralised algorithm each entity (robot) has only partial information of the environment and the other robots (for example, it can only see a few neighbours). The robots need to communicate to pass information and coordinate, explained Javier Alonso-Mora, one of the researchers involved in developing the algorithm.
Up till now, most research on decentralised 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 UAV swarms navigating in formation, for example for surveillance of an area, mapping of an environment, added 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 centralised 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 decentralised algorithm requires what they say is significantly lower communications bandwidth, as well as lower computation costs, 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 decentralised algorithm has robots only share maps with their immediate neighbours and also has each calculate where neighbours’ maps intersect with their own – sharing only relevant intersected data on to the next neighbour. 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, added 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 would expect a centralised 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 UAVs contracting. Occasionally the UAVs would also fly single file or assume a formation in which pairs flew at different altitudes.
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.
The team is working on a demonstrator with real vehicles as well as similar applications, said Alonso-Mora. He added that they may also experiment with actual UAVs 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 in 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 UAVs buzzing over your city.
At this stage it is research, stressed 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.
Make your inbox more interesting.Add some geo.
Keep abreast of news, developments and technological advancement in the geomatics industry.Sign up for free