Helping Robots Collaborate

Sometimes, one robot isn’t enough. Consider a search-and-rescue mission to find a hiker lost in the woods. Rescuers might want to deploy a squad of wheeled robots to roam the forest, perhaps with the aid of drones scouring the scene from above. The benefits of a robot team are clear. But orchestrating that team is no simple matter. How to ensure the robots aren’t duplicating each other’s efforts or wasting energy on a convoluted search trajectory?

MIT researchers have designed an algorithm to ensure the fruitful cooperation of information-gathering robot teams. Their approach relies on balancing a tradeoff between data collected and energy expended — which eliminates the chance that a robot might execute a wasteful maneuver to gain just a smidgeon of information. The researchers say this assurance is vital for robot teams’ success in complex, unpredictable environments. “Our method provides comfort, because we know it will not fail, thanks to the algorithm’s worst-case performance,” says Xiaoyi Cai, a PhD student in MIT’s Department of Aeronautics and Astronautics (AeroAstro).

Cai’s method, called Distributed Local Search, is an iterative approach that improves the team’s performance by adding or removing individual robot’s trajectories from the group’s overall plan. First, each robot independently generates a set of potential trajectories it might pursue. Next, each robot proposes its trajectories to the rest of the team. Then the algorithm accepts or rejects each individual’s proposal, depending on whether it increases or decreases the team’s objective function. “We allow the robots to plan their trajectories on their own,” says Cai. “Only when they need to come up with the team plan, we let them negotiate. So, it’s a rather distributed computation.”

Distributed Local Search proved its mettle in computer simulations. The researchers ran their algorithm against competing ones in coordinating a simulated team of 10 robots. While Distributed Local Search took slightly more computation time, it guaranteed successful completion of the robots’ mission, in part by ensuring that no team member got mired in a wasteful expedition for minimal information. “It’s a more expensive method,” says Cai. “But we gain performance.”

Cai also points to potential applications in mapping and search-and-rescue — activities that rely on efficient data collection. “Improving this underlying capability of information gathering will be quite impactful,” he says. The researchers next plan to test their algorithm on robot teams in the lab, including a mix of drones and wheeled robots. This research was funded in part by Boeing and the Army Research Laboratory’s Distributed and Collaborative Intelligent Systems and Technology Collaborative Research Alliance (DCIST CRA).

For more, please click here.