Task Allocation via Coalition Formation Among Autonomous Agents

Abstract

Autonomous agents working in multi-agent environments may need to cooperate in order to fulfi ll tasks. Given a set of agents and a set of tasks which they have to satisfy, we consider situations where each task should be attached to a group of agents which will perform the task. The allocation of tasks to groups of agents is necessary when tasks cannot be performed by a single agent. It may also be useful to assign groups of agents to tasks when the group's performance is more effi cient than the performance of single agents. In this paper we give an effi cient solution to the problem of task allocation among autonomous agents, and suggest that the agents will form coalitions in order to perform tasks or improve the e ciency. We present a distributed algorithm with a low ratio bound and with a low computational complexity. Our algorithm is an any-time algorithm, it is simple, effi cient and easy to implement.