MIT Researchers Launch a New Decentralized Planning Algorithm for Groups of Robots

There are two categories for planning algorithms for teams of robots: decentralized and centralized algorithms. In decentralized algorithms, each robot makes individual decisions based on local observations. In centralized algorithms, a single computer is capable of making decisions for the entire team.

However, the entire system falls apart with centralized algorithms when the central computer goes offline. Inconsistent communication is handled better by the decentralized algorithms, but they are difficult to design because each robot is essentially guessing what the other robots will do. Most research on decentralized algorithms focuses on enabling collective decision-making to be more reliable, and has failed to address the issue of avoiding hurdles in the robots’ environment.

MIT researchers will be launching a new, decentralized planning algorithm for groups of robots at the International Conference on Robotics and Automation in May. This new algorithm factors in both the moving and stationary obstacles. Compared to the existing decentralized algorithms, these new algorithms need significantly less communications bandwidth, and have the potential to preserve powerful mathematical guarantees that the robots will prevent collisions.

In simulations that deal with squadrons of mini helicopters, the decentralized algorithm developed flight plans similar to that obtained by the centralized algorithm. Generally, the drones preserved an estimation of their preferred formation, which is a square at a fixed altitude. Rotation of the square and contraction of the distances between drones to make room for obstacles. However, there are times when the drones fly single file or take up a formation where pairs of drones flew at varied heights.

It’s a really exciting result because it combines so many challenging goals. 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.

Daniela Rus, the Andrew and Erna Viterbi Professor, Department of Electrical Engineering and Computer Science, MIT

Rus is joined on the paper by first author Javier Alonso-Mora, a postdoc in Rus’ group; Mac Schwager, an assistant professor of aeronautics and astronautics at Stanford University who worked with Rus as an MIT PhD student in mechanical engineering; and Eduardo Montijano, a professor at Centro Universitario de la Defensa in Zaragoza, Spain.

Trading regions

In a standard decentralized group planning algorithm, all of the robots individually broadcast their environment-based observations to their teammates. The robots then perform the same planning algorithm, often depending on the same information.

Rus, Alonso-Mora, and their team discovered a method to decrease both the communication and computational burdens forced by consensual planning. They mainly focus on establishing the fact that each robot, based on its own observations, plans an obstacle-free region in its environment and sends this map only to its very close neighbors. After receiving a map from a neighbor, the robot determines the intersection of that map based on its own and then passed that on.

This maintains the size of the robots’ communications and their number, because every single robot communicates with only its neighbors. The intersection of 100 maps is described through an explanation of the intersection of two. Each robot finally has a map reflecting all the obstacles identified by the team members.

Four dimensions

The maps have four dimensions instead of three, the fourth one being time. It is through these dimensions that the algorithm accounts for all moving obstacles. The four-dimensional map explains how a three-dimensional map will have to change in order to accommodate the change of location of an obstacle within a few seconds. This is accomplished in a mathematically compact manner.

The algorithm assumes that the moving obstacles have constant velocity, which is not always achieved in the real-world. It only takes a second for each robot to update its map an increasing number of times. This time period is short enough that an accelerating object’s velocity is unlikely to go through a dramatic change.

Based on the latest map, each robot determines the trajectory that will help maximize both its global goal and local goal.

Currently, the researchers are examining a version of their algorithm on wheeled robots that focus on collectively carrying an object through a room where human beings are also moving, as a simulation of an environment in which both robots and humans operate together.