Distributed Algorithm Design for Multi-robot Generalized Task Assignment Problem

Lingzhi Luo, Nilanjan Chakraborty and Katia Sycara
Conference Paper, Proceedings of International Conference on Intelligent Robots and Systems (IROS), Tokyo, Japan, November, 2013

View Publication

Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.


We present a provably-good distributed algorithm for generalized task assignment problem in the context of multi- robot systems, where robots cooperate to complete a set of given tasks. In multi-robot generalized assignment problem (MR- GAP), each robot has its own resource constraint (e.g., energy constraint), and needs to consume a certain amount of resource to obtain a payoff for each task. The objective is to find a maxi- mum payoff assignment of tasks to robots such that each task is assigned to at most one robot while respecting robots’ resource constraints. MR-GAP is a NP-hard problem. It is an extension of multi-robot linear assignment problem since different robots can use different amount of resource for doing a task (due to the heterogeneity of robots and tasks). We first present an auction- based iterative algorithm for MR-GAP assuming the presence of a shared memory (or centralized auctioneer), where each robot uses a knapsack algorithm as a subroutine to iteratively maximize its own objective (using a modified payoff function based on an auxiliary variable, called price of a task). Our iterative algorithm can be viewed as (an approximation of) best response assignment update rule of each robot to the assignment of other robots at that iteration. We prove that our algorithm converges to an assignment (approximately) at equilibrium under the assignment update rule, with an approximation ratio of 1 + α (where α is the approximation ratio for the Knapsack problem). We also combine our algorithm with a message passing mechanism to remove the requirement of a shared memory and make our algorithm totally distributed assuming the robots’ communication network is connected. Finally, we present simulation results to depict our algorithm’s performance.

author = {Lingzhi Luo and Nilanjan Chakraborty and Katia Sycara},
title = {Distributed Algorithm Design for Multi-robot Generalized Task Assignment Problem},
booktitle = {Proceedings of International Conference on Intelligent Robots and Systems (IROS), Tokyo, Japan},
year = {2013},
month = {November},
} 2017-09-13T10:39:13-04:00