Information Technology Reference
In-Depth Information
Self-organization of Roles Based on Multilateral
Negotiation for Task Allocation
Florin Leon
Technical University “Gheorghe Asachi” of Iasi
Bd. Mangeron 27, 700050 Iasi, Romania
fleon@cs.tuiasi.ro
Abstract.
An important issue in many multiagent systems is the way in
which agents can be coordinated in order to perform different roles. This
paper proposes a method by which the agents can self-organize based
on the changes of their individual utilities. We assume that the tasks
given to the agents have a number of attributes and complexity levels,
and that the agents have different preferences regarding these features.
The adaptive behaviour of the agents is based on the psychological the-
ory of cognitive dissonance, where an agent working on a low-preference
task gradually improves its attitude towards it. The agents go through
personal learning curves and improve their performance by learning or
decrease it by forgetting. A (near-)optimal assignment of tasks between
agents is achieved by an evolutionary multilateral negotiation, as agents
value the attributes of the tasks differently. Over repeated trials, the sys-
tem is shown to stabilize, and the agents converge to specific roles, i.e.
handling tasks mainly defined by particular attributes. The total pro-
ductivity of the system increases as an emergent property of the system.
Keywords:
multiagent system, self-organization, organizational roles,
multilateral negotiation solutions, task allocation, evolutionary algorithm.
1
Introduction
The ability of a multiagent system to dynamically reorganize its structure and
operation at run-time is highly valuable for many applications. Therefore, allo-
cating tasks to agents in multiagent systems is a significant research issue.
A popular approach to task allocation is by using auction based mechanisms.
Each agent computes a cost for completing a task and broadcasts the bid for
it. The auctioneer agent decides the best available bid and the winning bid-
der attempts to perform the task. Following the classic contract-net protocol
[3], several variations of this method have been more recently proposed for the
control of unmanned space or aerial vehicles [11,9]. Also, an emergent alloca-
tion method for mobile robots was proposed, where each robot uses only the
information obtained from its immediate neighbours [1].
The
Extended Generalized Assignment Problem
(E-GAP) [10] studies the as-
signment of tasks to agents, taking into account the agents' capacities in order
