Algorithms of distributed task allocation for cooperative agents

This paper considers the problem of distributed dynamic task allocation by a set of cooperative agents. The paper describes a rather specific situation. However, its methods have wide application and, thus, it can be useful to solve general problems of computer science. One of its main ideas is to combine optimization questions with the symmetries of initial objects. There are different types of tasks that are dynamically arriving to a system. Each of the agents can satisfy only a subset of the tasks. The main goal of the agents is to maximize the overall performance of the system and to fulfill the tasks as soon as possible. The agents are modeled using a stochastic closed queueing network. The problem is divided into two subproblems: to determine a distributed policy of optimal task distribution and to find the optimal effort levels of the agents subject to certain constraints. For the first subproblem, a distributed polynomial allocation algorithm for determining an instantaneous probabilistic optimal policy for task allocation is presented. The policy is independent of the state of the system and thus does not require information exchange among the agents during the performance of the tasks. For the second subproblem, an analytical solution to find the optimal effort levels for the agents is given. (C) 2000 Elsevier Science B.V. All rights reserved.