Researchers develop algorithm to divvy up tasks for human-robot teams

Researchers at Carnegie Mellon University's Robotics Institute (RI) have developed an algorithmic planner that helps delegate tasks to humans and robots. The planner, "Act, Delegate or Learn" (ADL), considers a list of tasks and decides how best to assign them. The researchers asked three questions: When should a robot act to complete a task? When should a task be delegated to a human? And when should a robot learn a new task?

"There are costs associated with the decisions made, such as the time it takes a human to complete a task or teach a robot to complete a task and the cost of a robot failing at a task," said Shivam Vats, the lead researcher and a Ph.D. student in the RI. "Given all those costs, our system will give you the optimal division of labor."

The team's work could be useful in manufacturing and assembly plants, for sorting packages, or in any environment where humans and robots collaborate to complete several tasks. The researchers tested the planner in scenarios where humans and robots had to insert blocks into a peg board and stack parts of different shapes and sizes made of Lego bricks.

Using algorithms and software to decide how to delegate and divide labor is not new, even when robots are part of the team. However, this work is among the first to include robot learning in its reasoning.

"Robots aren't static anymore," Vats said. "They can be improved and they can be taught."

Often in manufacturing, a person will manually manipulate a robotic arm to teach the robot how to complete a task. Teaching a robot takes time and, therefore, has a high upfront cost. But it can be beneficial in the long run if the robot can learn a new skill. Part of the complexity is deciding when it is best to teach a robot versus delegating the task to a human. This requires the robot to predict what other tasks it can complete after learning a new task.

Given this information, the planner converts the problem into a mixed integer program -- an optimization program commonly used in scheduling, production planning or designing communication networks -- that can be solved efficiently by off-the-shelf software. The planner performed better than traditional models in all instances and decreased the cost of completing the tasks by 10% to 15%.

Vats presented the work, "Synergistic Scheduling of Learning and Allocation of Tasks in Human-Robot Teams" at the International Conference on Robotics and Automation in Philadelphia, where it was nominated for the outstanding interaction paper award. The research team included Oliver Kroemer, an assistant professor in RI; and Maxim Likhachev, an associate professor in RI.

The research was funded by the Office of Naval Research and the Army Research Laboratory.