=Paper=
{{Paper
|id=None
|storemode=property
|title=A Survey of Multi-Agent Systems for Optimization Problems
|pdfUrl=https://ceur-ws.org/Vol-741/INV01_Schaerf.pdf
|volume=Vol-741
|dblpUrl=https://dblp.org/rec/conf/woa/Schaerf11
}}
==A Survey of Multi-Agent Systems for Optimization Problems==
https://ceur-ws.org/Vol-741/INV01_Schaerf.pdf
A Survey of Multi-Agent Systems for Optimization
Problems
Andrea Schaerf
DIEGM, University of Udine
Via delle Scienze 206
33100 Udine, Italy
Email: schaerf@uniud.it
Web: http://www.diegm.uniud.it/schaerf
Abstract—Optimization problems, such as resource alloca- problem. The university course timetabling (CTT) problem
tion or scheduling, often involves different entities, such as is one of the most studied educational timetabling problems
departments or production units, which might have different and consists in scheduling a sequence of events or lectures
constraints and objectives, but are interested in cooperating. In
this presentation, we survey various scenarios and the solutions of university courses in a prefixed period of time (typically
proposed in the literature for this kind of situations. We start a week), satisfying a set of various constraints on rooms and
from simple distributed constraint satisfaction problems, to move students.
to more complex situations involving contract nets and Markov We consider the timetabling problem for a set of university
Decision Problems. Finally, we discuss various kinds of auctions departments (or schools, or faculties) that have to schedule the
and market mechanisms to solve this kind of problems using a
timetabling problem as running example. courses of their curricula in a given term. Each department pre-
pares its weekly schedule based on its endowment of rooms,
I. O UTLINE OF THE P RESENTATION and according to its own constraints, rules, and objectives. In
Complex optimization problems are ubiquitous in the indus- general, a department is not willing to share its information
trial context. They range from resource allocation, to machine with the other departments; therefore we assume that all input
scheduling, to logistics just to name some. In many cases, the data are private for each department and thus inaccessible to
overall problem involves different entities, such as departments the others.
or production units. The various entities, which have their On the other hand, whenever resources are usable for
crucial decisions to make in terms of assignments, might have more departments, e.g., they are located in the same site,
different constraints and objectives. Nevertheless, they are departments could benefit from sharing and/or exchanging
normally interested in cooperating in order to obtain a global their resources. Indeed, the resource endowment for each term
solution acceptable for all the entities involved. In addition, it is not always optimally suited to the needs of the departments,
is often the case that there are privacy issues involved among but rather based on political and historical matters. Moreover,
the entities, so that the possibility to share all the information normally there are no global objectives to be satisfied; there-
is not a viable option. fore all departments exchange resources for their own selfish
In all these cases, it might be useful to resort to an interest, although they have a moral impulse to be helpful with
architecture in which each decision maker is equipped with the other departments, whenever possible without loss.
an agent-based software system. Each system should be able We this specific timetabling setting, we discuss the possible
to solve complex optimization tasks, but also to interact general architectures for the system and we describe the tasks
and negotiate with the other systems for the achievement of and the functionalities of each of the agents. Finally, we will
common objectives or for the identification of actions that lead discuss the trade-off between privacy and independence in the
to mutual advantages. one side and effectiveness and efficiency on the other, for this
In this presentation, we survey various scenarios and the so- type of distributed problems.
lutions proposed in the literature for this kind of situations. We
start from simple distributed constraint satisfaction problems,
to move to more complex situations involving Contract Nets
or Markov Decision Problems. Finally, we discuss various
kinds of auctions and market mechanisms to solve this kind
of problems.
We also discuss how optimization packages have to be
modified in order to take care of the presence of uncertain
resources that might be obtained from the other entities.
Special attention will be devoted to a running case, arising
from a real-world problem, namely an educational timetabling