# New Algorithm Coordinates Complex Behaviors Between Hundreds of Robots in a Fraction of the Time

###### As a control algorithm moves robots through a space, each state the robots can be in is represented by a spot on the 3D graph. As the algorithm explores new options, it finds failures and potential next moves. This graph represents all of the wrong moves explored (blue) and the one route that is correct (red).

Credit: Michael Zavlanos, Duke

**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 one of the more memorable scenes from the 2002 blockbuster film Minority Report, Tom Cruise is forced to hide from a swarm of spider-like robots scouring a towering apartment complex. While most viewers are likely transfixed by the small, agile bloodhound replacements, a computer engineer might marvel instead at their elegant control system.

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

In a new paper published online on April 29 in The International Journal of Robotics Research, Zavlanos and his recent PhD graduate student, Yiannis Kantaros, who is now a postdoctoral researcher at the University of Pennsylvania, propose a new approach to this challenge called STyLuS*, for large-Scale optimal Temporal Logic Synthesis, that can solve problems massively larger than what current algorithms can handle, with hundreds of robots, tens of thousands of rooms and highly complex tasks, in a small fraction of the time.

To understand the basis of the new approach, one must first understand linear temporal logic, which is not nearly as scary as it sounds. Suppose you wanted to program a handful of robots to collect mail from a neighborhood and deliver it to the post office every day. Linear temporal logic is a way of writing down the commands needed to complete this task.

For example, these commands might include to visit each house in sequential order, return back to the post office and then wait for someone to retrieve the collected mail before setting out again. While this might be easy to say in English, it’s more difficult to express mathematically. Linear temporal logic can do so by using its own symbols which, although might look like Klingon to the common observer, they’re extremely useful for expressing complex control problems.

“The term linear is used because points in time have a unique successor based on discrete linear model of time, and temporal refers to the use of operators such as until, next, eventually and always,” said Kantaros. “Using this mathematical formalism, we can build complex commands such as ‘visit all the houses except house two,’ ‘visit houses three and four in sequential order,’ and ‘wait until you’ve been to house one before going to house five.’ ”

A traditional controller searches through each one of these nodes and the potential paths to take between them before figuring out the best way to navigate its way through. But as the number of robots and locations to visit increase, and as the logic rules to follow become more sophisticated, the solution space becomes incredibly large in a very short amount of time.

A simple problem with five robots living in a world with ten houses could contain millions of nodes, capturing all possible robot locations and behaviors towards achieving the task. This requires a lot of memory to store and processing power to search through.

To skirt around this issue, the researchers propose a new method that, rather than constructing these incredibly large graphs in their entirety, instead creates smaller approximations with a tree structure. At every step of the process, the algorithm randomly selects one node from the large graph, adds it to the tree, and rewires the existing paths between the nodes in the tree to find more direct paths from start to finish.

“This means that as the algorithm progresses, this tree that we incrementally grow gets closer and closer to the actual graph, which we never actually construct,” said Kantaros. “Since our incremental graph is much smaller, it is easy to store in memory. Moreover, since this graph is a tree, graph search, which otherwise has exponential complexity, becomes very easy because now we only need to trace the sequence of parent nodes back to the root to find the desired path.”

MORE of the story / click image TOP of PAGE