A quantized consensus algorithm for distributed task assignment

Abstract

This paper proposes a novel distributed algorithm for a multi-agent assignment problem, in which a group of agents has to reach a consensus on an optimal distribution of tasks among themselves. Distributing a number of tasks to a number of agents is one of the most fundamental resource allocation problems that appear in numerous control and decision systems, ranging from multi-agent robotics to processor allocation in computing systems. The problem is formalized as a distributed consensus algorithm, i.e., as a procedure using which the agents can exchange messages and update autonomously and iteratively their assigned tasks. The proposed distributed algorithm aims to minimize the task costs assuming that each agent can perform a subset of the available tasks and can communicate with a subset of agents. Some results prove that the convergence to a task assignment consensus is reached and a suitable stopping criterion is given.