Distributed greedy algorithm for multi-agent task assignment problem with submodular utility functions

We consider a multi-agent task assignment problem where a group of agents need to select tasks from their admissible task sets. The utility of an assignment profile is measured by the sum of individual task utilities, which is a submodular function of the set of agents that are assigned to it. The objective is to find an assignment profile that maximizes the global utility. This problem is NP-hard in general. In this paper we propose an algorithm that provides an assignment profile with utility at least 1/(1 + kappa) of the optimal utility, where kappa is an element of [0, 1] is a parameter for the curvature of the submodular utility functions. In the worst case, when kappa = 1, our algorithm achieves utility at least 1/2 of the optimal. Moreover, when the communication links between agents are consistent with the admissible task sets, the algorithm can be implemented distributedly and asynchronously, which means that there is no centralized coordinator and each agent selects its task using only local information and local communication based on its own time-clock. (C) 2019 Elsevier Ltd. All rights reserved.