Algorithms of distributed task allocation for cooperative agents

✍ Scribed by Sarit Kraus; Tatjana Plotkin

• Publisher: Elsevier Science
• Year: 2000
• Tongue: English
• Weight: 173 KB
• Volume: 242
• Category: Article
• ISSN: 0304-3975
• DOI: 10.1016/s0304-3975(98)00175-3

✦ Synopsis

This paper considers the problem of distributed dynamic task allocation by a set of cooperative agents. The paper describes a rather speciÿc 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 di erent 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 fulÿll 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 ÿnd the optimal e ort levels of the agents subject to certain constraints. For the ÿrst 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 ÿnd the optimal e ort levels for the agents is given.