A new approach to designing motion plans for multiple robots grows “trees” in the search space to solve complex problems in a fraction of the time

In a building several stories tall with numerous rooms, hundreds of obstacles and thousands of places to inspect, the several dozen robots move as one cohesive unit. They spread out in a search pattern to thoroughly check the entire building while simultaneously splitting tasks so as to not waste time doubling back on their own paths or re-checking places other robots have already visited.

Such cohesion would be difficult for human controllers to achieve, let alone for an artificial controller to compute in real-time.

“If a control problem has three or four robots that live in a world with only a handful of rooms, and if the collaborative task is specified by simple logic rules, there are state-of-the-art tools that can compute an optimal solution that satisfies the task in a reasonable amount of time,” said Michael M. Zavlanos, the Mary Milus Yoh and Harold L. Yoh, Jr. Associate Professor of Mechanical Engineering and Materials Science at Duke University.

“And if you don’t care about the best solution possible, you can solve for a few more rooms and more complex tasks in a matter of minutes, but still only a dozen robots tops,” Zavlanos said. “Any more than that, and current algorithms are unable to overcome the sheer volume of possibilities in finding a solution.”

The researchers show that this method will always find an answer if there is one, and it will always eventually find the best one possible. They also show that this method can arrive at that answer exponentially fast. Working with a problem of 10 robots searching through a 50-by-50 grid space— 250 houses to pick up mail — current state-of-the-art algorithms take 30 minutes to find an optimal solution.

STyLuS* does it in about 20 seconds.

via Duke University