Planning algorithms for teams of robots fall into two categories: centralized algorithms, in which a single computer makes decisions for the whole team, and decentralized algorithms, in which each robot makes its own decisions based on local observations.
With centralized algorithms, if the central computer goes offline, the whole system falls apart. Decentralized algorithms handle erratic communication better, but they’re harder to design, because each robot is essentially guessing what the others will do. Most research on decentralized algorithms has focused on making collective decision-making more reliable and has deferred the problem of avoiding obstacles in the robots’ environment.
At the 2016 International Conference on Robotics and Automation in Stockholm, MIT researchers presented a new, decentralized planning algorithm for teams of robots that factors in not only stationary obstacles, but moving obstacles, as well. The algorithm also requires significantly less communications bandwidth than existing decentralized algorithms, but preserves strong mathematical guarantees that the robots will avoid collisions.
In simulations involving squadrons of mini-helicopters, the decentralized algorithm came up with the same flight plans that a centralized version did. The drones generally preserved an approximation of their preferred formation, a square at a fixed altitude, although to accommodate obstacles the square rotated and the distances between drones contracted. Occasionally, however, the drones would fly single file or assume a formation in which pairs flew at different altitudes.
Professor Daniela Rus, of MIT’s Department of Electrical Engineering and Computer Science and director of the Computer Science and Artificial Intelligence Laboratory, leads the group that developed the new algorithm. Rus is joined by Javier Alonso-Mora, a postdoc in Rus’ group; Mac Schwager, an assistant professor of aeronautics and astronautics at Stanford who worked with Rus as an MIT PhD student; and Professor Eduardo Montijano, of Centro Universitario de la Defensa in Zaragoza, Spain.
In a typical decentralized group planning algorithm, each robot might broadcast its observations of the environment to its teammates, and all the robots would then execute the same planning algorithm, presumably on the basis of the same information.
The MIT team found a way to reduce both the computational and communication burdens imposed by consensual planning. Essentially, each robot, on the basis of its own observations, maps out an obstacle-free region in its immediate environment and passes that map only to its nearest neighbors. When a robot receives a map from a neighbor, it calculates the intersection of that map with its own and passes that on. Each robot ends up with a map that reflects all of the obstacles detected by all the team members.
The maps have not three dimensions, but four, the fourth being time. This is how the algorithm accounts for moving obstacles. The four-dimensional map describes how a three-dimensional map would have to change to accommodate the obstacle’s change of location, over a span of a few seconds, in a mathematically compact manner.
The algorithm does assume that moving obstacles have constant velocity, which will not always be the case in the real world. But each robot updates its map several times a second, a short enough span of time that the velocity of an accelerating object is unlikely to change dramatically.
On the basis of its latest map, each robot calculates the trajectory that will maximize both its local goal, staying in formation, and its global goal.
The researchers are also testing a version of their algorithm on wheeled robots whose goal is to collectively carry an object across a room where human beings are also moving around, as a simulation of an environment in which humans and robots work together.