Robotic systems, often working collaboratively as a team of multiple autonomous agents, are becoming valuable players in different real-world applications; these include search and rescue, disaster response, goods delivery, and inventory management services. Coordinating a large team of robots using a centralized algorithm is often computationally intractable, demonstrates poor scalability, and is vulnerable to communication disruptions. Our research focuses on developing scalable decentralized task planning frameworks for multi-robot applications.

In our current implementation, called decentralized multi-agent task-allocation or Dec-MATA, the decentralized task planning problem is posed as a maximum-weighted matching of a bipartite graph (see Figure below), the solution of which allows each robot to autonomously identify the optimal sequence of tasks it should undertake. The well-known blossom algorithm is used for solving the weighted maximum graph matching problem. The graph weights are determined based on a soft clustering approach and the actual value of each task. The clustering process also facilitates reduction of the task allocation problem by eliminating unlikely robot-task pair candidates. In preliminary numerical experiments, Dec-MATA exhibited significantly (orders of magnitude) superior computational efficiency compared to state-of-the-art multi-traveling salesman solutions to multi-robot problems.