Nav: Home

Algorithm for robot teams handles moving obstacles

April 21, 2016

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 International Conference on Robotics and Automation in May, MIT researchers will present a new, decentralized planning algorithm for teams of robots that factors in not only stationary obstacles, but also moving obstacles. 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 minihelicopters, 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 of them flew at different altitudes.

"It's a really exciting result because it combines so many challenging goals," says Daniela Rus, the Andrew and Erna Viterbi Professor in MIT's Department of Electrical Engineering and Computer Science and director of the Computer Science and Artificial Intelligence Laboratory, 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."

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 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.

But Rus, Alonso-Mora, and their colleagues found a way to reduce both the computational and communication burdens imposed by consensual planning. The essential idea is that 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.

This keeps down both the size of the robots' communications -- describing the intersection of 100 maps requires no more data than describing the intersection of two -- and their number, because each robot communicates only with its neighbors. Nonetheless, each robot ends up with a map that reflects all of the obstacles detected by all the team members.

Four dimensions

The maps have not three dimensions, however, 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. But it does so 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.
-end-
Additional background

ARCHIVE: Enabling human-robot rescue teams

ARCHIVE: Robotics competition generated groundbreaking research

ARCHIVE: Helping robots handle uncertainty

ARCHIVE: Helping robots put it all together

Massachusetts Institute of Technology

Related Robots Articles:

Tactile sensor gives robots new capabilities
Eight years ago, Ted Adelson's research group at MIT's Computer Science and Artificial Intelligence Laboratory (CSAIL) unveiled a new sensor technology, called GelSight, that uses physical contact with an object to provide a remarkably detailed 3-D map of its surface.
Researchers question if banning of 'killer robots' actually will stop robots from killing
A University at Buffalo research team has published a paper that implies that the rush to ban and demonize autonomous weapons or 'killer robots' may be a temporary solution, but the actual problem is that society is entering into a situation where systems like these have and will become possible.
Soft robots that mimic human muscles
An EPFL team is developing soft, flexible and reconfigurable robots.
Team of robots learns to work together, without colliding
When you have too many robots together, they get so focused on not colliding with each other that they eventually just stop moving.
Social robots -- programmable by everyone
The startup LuxAI was created following a research project at the Interdisciplinary Centre for Security, Reliability and Trust (SnT) of the University of Luxembourg.
On the path toward molecular robots
Scientists at Hokkaido University have developed light-powered molecular motors that repetitively bend and unbend, bringing us closer to molecular robots.
Gentle strength for robots
A soft actuator using electrically controllable membranes could pave the way for machines that are no danger to humans.
Robots get creative to cut through clutter
Clutter is a special challenge for robots, but new Carnegie Mellon University software is helping robots cope, whether they're beating a path across the moon or grabbing a milk jug from the back of the refrigerator.
Humans can empathize with robots
Toyohashi Tech researchers in cooperation with researchers at Kyoto University have presented the first neurophysiological evidence of humans' ability to empathize with a robot in perceived pain.
Giving robots a more nimble grasp
Engineers at MIT have now hit upon a way to impart more dexterity to simple robotic grippers: using the environment as a helping hand.

Related Robots Reading:

Best Science Podcasts 2019

We have hand picked the best science podcasts for 2019. Sit back and enjoy new science podcasts updated daily from your favorite science news services and scientists.
Now Playing: TED Radio Hour

Climate Crisis
There's no greater threat to humanity than climate change. What can we do to stop the worst consequences? This hour, TED speakers explore how we can save our planet and whether we can do it in time. Guests include climate activist Greta Thunberg, chemical engineer Jennifer Wilcox, research scientist Sean Davis, food innovator Bruce Friedrich, and psychologist Per Espen Stoknes.
Now Playing: Science for the People

#527 Honey I CRISPR'd the Kids
This week we're coming to you from Awesome Con in Washington, D.C. There, host Bethany Brookshire led a panel of three amazing guests to talk about the promise and perils of CRISPR, and what happens now that CRISPR babies have (maybe?) been born. Featuring science writer Tina Saey, molecular biologist Anne Simon, and bioethicist Alan Regenberg. A Nobel Prize winner argues banning CRISPR babies won’t work Geneticists push for a 5-year global ban on gene-edited babies A CRISPR spin-off causes unintended typos in DNA News of the first gene-edited babies ignited a firestorm The researcher who created CRISPR twins defends...