=Paper=
{{Paper
|id=None
|storemode=property
|title=Multi Agent Resource Allocation: a Comparison of Five Negotiation Protocols
|pdfUrl=https://ceur-ws.org/Vol-741/ID9_Briola_Mascardi.pdf
|volume=Vol-741
|dblpUrl=https://dblp.org/rec/conf/woa/BriolaM11a
}}
==Multi Agent Resource Allocation: a Comparison of Five Negotiation Protocols==
https://ceur-ws.org/Vol-741/ID9_Briola_Mascardi.pdf
Multi Agent Resource Allocation:
a Comparison of Five Negotiation Protocols
Daniela Briola and Viviana Mascardi
Dipartimento di Informatica e Scienze dell’Informazione (DISI)
Università degli Studi di Genova
Email: {briola, mascardi}@disi.unige.it
Abstract—This paper describes five systems that exploit negoti- Due to this large amount of MARA problems and related
ation strategies to solve multiagent resource allocation problems. solutions described in literature, we limit ourselves to analyze
A deep comparison is drawn among them according to different those works that are closer to the FYPA one we modeled and
criteria that involve general features of the systems; adherence
to widely accepted agent definitions; domain, purpose, and implemented in our recent research activities [7], [12].
approach; analysis, design and implementation of the negotiation In particular, we focus on works where agents interact to
protocol. Considerations on how extending one of the analyzed coordinate themselves for moving in a well defined physical
systems in order to move a concrete step towards the realization area or for accessing shared resources during time. For each
of an integrated platform for developing negotiation protocols are system we discuss, we motivate why we did not select it to
also provided in the conclusions.
solve our specific FYPA MARA problem.
I. I NTRODUCTION The paper is structured in the following way. After dis-
cussing the state of the art in agent-based negotiation (Section
Allocating resources amongst multiple entities is a central
II), in sections III-VII we introduce the five systems and the
matter of concern in both Computer Science and Economics.
MARA problems they solve:
It has inter-disciplinary characteristics which make it rel-
evant to disparate application domains including industrial • FYPA (Find Your Path, Agent!) [7], [11], [12], developed
procurement, manufacturing and scheduling, network routing, by ourselves for solving a real industrial problem of
airport traffic management, crisis management, logistics, pub- dynamic (re-)allocation of tracks to trains inside a station
lic transport, and the timely allocation of resources in grid (Section III);
architectures [14]. • MPCA (Multi-Party Collision Avoidance) [40] for air-
The abstractions of agents and multiagent systems are very plane collision avoidance (Section IV);
• APR (Airplane rerouting) [3] for airplane collision avoid-
suitable to model and implement distributed problems of
this kind, and the Multiagent Resource Allocation (MARA) ance (Section V);
• Waypoints [34] for autonomous robots collision avoid-
research sub-field is recently gaining more and more attention.
A tentative definition of MARA can be found in [14]: ance (Section VI); and
• SPAM (Scalable Protocol for Anytime Multi-level) [27]
“Multiagent Resource Allocation is the process of
for target tracking with sensors (Section VII).
distributing a number of items amongst a number of
agents.” In Section VIII we provide a systematic comparison among
these systems, carried out taking different criteria into account
However, as the authors of [14] observe, this definition
ranging from how much do they stick to the agent definition
needs to be further qualified: What kind of items (resources)
given in [24], to their industrial exploitation, to the language
are being distributed? How are they being distributed (in other
and platforms used for their implementation. Section IX
words, what kind of allocation procedure or mechanism do
concludes the paper and outlines the future directions of our
they employ)? And finally, why are they being distributed (that
research.
is, what are the objectives of searching for an allocation and
how are these objectives determined)? II. AGENT- BASED NEGOTIATION : THE STATE - OF - THE - ART
In this paper, we analyze five existing systems that solve
different MARA problems, and whose allocation procedure A. Trends and research areas
mechanism is based on negotiation. Multiagent research has long been divided into two fields,
For each of them we answer the questions of what kind one concerned with cooperative (benevolent) agents and the
of items (resources) are being distributed and why are they other concerned with self-interested agents [18]. There has
being distributed, we provide some details on the negotiation been very little cross-fertilization of ideas between these fields.
protocol they adopt, and we answer many other questions Research on self-interested agents is often based on classical
that, in our opinion, are relevant to gain a deeper insight of game theory with its assumptions of common knowledge
the system and to understand whether and how it might be among agents and complete rationality of agent reasoning.
exploited to solve the specific user’s MARA problem. This is in contrast with the research on cooperative agents
which makes no such assumptions; rather, it has generally been In general, multiagent systems provide a framework where
based on heuristic approaches having their roots in knowledge- both the inherent distribution of processing and information in
based AI search, planning and scheduling mechanisms. an application and the complexities that come from issues of
However, perhaps the most fundamental and powerful scale can be handled in a natural way.
mechanism for managing inter-agent dependencies at run-time In these areas the word “Negotiation” is rarely expressly and
is negotiation, that is the process by which a group of agents explicitly used, but nevertheless in these fields agents usually
come to a mutually acceptable agreement on some matter. need to cooperate to achieve a goal, and cooperation is a type
Negotiation underpins attempts to cooperate and coordinate of negotiation.
(both between artificial and human agents) and is required There has also been a long tradition of work dating back to
both when the agents are self interested and when they are the inception of the field on coordination based on logical
cooperative. reasoning about the beliefs, desires, intentions (BDI) and
In the remainder of this section we will concentrate on commitments of agents [16], [20], [35], [36], and more recent
cooperative agents and on the main areas where they are work on the use of market mechanisms for solving multiagent
used. Most of our knowledge on this subject comes from the resource allocation problems [42].
overview on negotiation in MASs made by Lesser [26], whose The synthesis of ideas from each of these different ap-
research activity, carried out in collaboration with many other proaches to coordination holds great potential for future de-
scientists, covers a large variety of case studies, domains and velopments in the field.
applicative projects.
Examples of application domains that have used a multia- III. FYPA
gent approach for allowing the involved entities to negotiate The FYPA problem was proposed to us by Ansaldo STS,
in a cooperative way are: the Italian leader in design and construction of signaling and
• Distributed situation assessment, which emphasizes how automation systems for conventional and high speed railway
(diagnostic) agents with different spheres of awareness lines.
and control (network segments) should share their local Ansaldo STS uses a system that computes, few times a
interpretations to arrive at consistent and comprehensive year, the global distribution of trains over the Italian railway
explanations and responses. Examples of applications network. That system does not compute safe paths of trains
belonging to this category are: inside stations: the system is only able to generate paths for
– network diagnosis [37]; crossing the station that are consistent with the station physical
– information gathering on the Internet [17], [32]; configuration, but cannot check that each path does not raise
– distributed sensor networks [13], [29]). conflicts with paths of all the other trains crossing the station in
the same time period. This check and the final identification of
• Distributed resource scheduling and planning, which em-
safe paths inside the station were indeed performed by human
phasizes how (scheduling) agents (associated with each
operators by hand.
work cell) should coordinate their schedules to avoid and
In order to automatize the train schedule definition process
resolve conflicts over resources, and to maximize system
as much as possible, Ansaldo needed another system that could
output. Under this category we can find for example:
be used off-line to identify a safe and (sub)optimal allocation
– factory scheduling [31], [33], [38];
of tracks inside a station to trains, given the time trains enter
– network management [1];
and exit the stations (times that are decided by the pre-existing
– intelligent environments [6], [22].
system).
• Distributed expert systems, which emphasize how agents One of Ansaldo’s requirements was to have a system de-
share information and negotiate over collective solutions signed and implemented is such a way that, if its performances
(designs) given their different expertise and solution cri- demonstrated to suit the real time constraints, it could be used
teria. The following applications fall under this category: on-line as well, in order to face re-allocation problems due
– concurrent engineering [25]; to unavailability of the pre-computed path because of tracks
– network service restoration [15], [23]. being out of order or already occupied by other trains.
The need for a multiagent approach can also come from The FYPA system that we developed is suitable both for
applications where agents represent the interests of different on-line and off-line usage. It is already used for off-line
organizational entities (e.g., electronic commerce [39] and computation of paths inside stations, and its on-line application
enterprise integration [4]). Other emerging uses of multiagent is under way: FYPA is able to compute a complete re-
systems are in layered systems architectures where agents at allocation of trains in huge stations (tests made by Ansaldo
different layers need to coordinate their decisions (e.g., to STS engineers with data from Mestre and Pisa) in less than 2
achieve appropriate configurations of resources and computa- seconds, hence quasi real-time [10].
tional processing [41]), and in the design of survivable systems In order to solve Ansaldo STS’ problems and implement
where agents dynamically reorganize to respond to changes the FYPA system, we designed a multiagent system able to
in resources availability, software and hardware malfunctions, manage the real-time allocation (and re-allocation) of a set of
and intrusions. limited resources. The resources are railway tracks (or only
“railway” further on) inside a station plus a set of segments multiagent system must suggest the user possible alternative
of railway where trains are allowed to stop (for example to reorganizations of the route of many planes.
let the passengers in and out) that we call “stop nodes”: these Regarding the airspace management, an accurate re-
nodes are connected by one, or usually more, railways. A “stop search has been made by the “Agent technology center”
node” can be occupied by only one train at a time. Due to the (http://agents.felk.cvut.cz/) that developed AGENTFLY, “a
physical distribution in the space of “stop nodes”, some of multi-agent system enabling large-scale simulation of civilian
the railways intersect with each other so it is not possible for and unmanned air traffic. The system integrates advanced
different trains to use them at the same time, because they flight path planning, decentralized collision avoidance with
may crash. highly detailed models of the airplanes and the environ-
A train can enter or leave the station using only a set of ment” [2]. The AGENTFLY project is still maintained and
“stop nodes”, that we call “entering” and “exiting nodes” its authors are continuously improving it in many ways. Its
respectively. Once inside the station, the train can move license was sold to BAE Systems as a testbed simulation
following the railways to reach some “stop nodes”, can wait platform. It is used by US Air Force, IHMS at Florida and
there for a period it autonomously determines and then can several universities. Its authors are working with the Federal
reach an “exiting nodes” and leave the station. FYPA only Aviation Authority (FAA) using AGENTFLY as a tool on their
manages trains inside the station or entering it. When they computation grids.
reach an “exiting nodes”, they leave the station and are no Besides this system, the authors presented many studies on
longer managed by FYPA. protocols to avoid collisions in airspace.
Every train has a predefined path in the station that it should In [40] two algorithms to avoid collisions among aerial
follow, that is generated by the pre-existing Ansaldo system vehicles are presented. The authors kindly accepted to review
but that does not meet the requirements of being conflict-free our analysis (in this section and in section VIII) of their work,
with respect to the other paths. Each train can hence change so we are able to provide some details also on the AGENTFLY
some “stop nodes” if needed to reach the conflict-freeness project in Section VIII, where we add some footnotes to Tables
requirement, but it usually has to deviate as little as possible to report additional information submitted by the authors.
from its original plan. In a three dimensions space a group of autonomous air-
The main aim of our protocol is to dynamically find a planes with a mission need to coordinate themselves to avoid
solution to conflicts and unavailabilities (that may be dealt collisions: a mission is made of several points that must be
with in an homogeneous way, since both amount to a resource reached in a specified time interval. To fulfill the mission, the
needed by a train not being available), or in other words to airplane will follow a list of steps, each characterized by a
find a new path in the station for every train, respecting all maneuver, a direction, a velocity, starting from the previous
the safety, minimum-delay and minimal-changes constrains. step. More, every plane must maintain a minimum distance
When an allocation problem arises, the system has to change from all the others, and there are no-flight zones in the
the “station crossing plan” of one, or more, trains: every train airspace. When two, or more, airplanes have a part of the
has a specific typology (may be a slow passenger train, a fast plan in common, they need to change it to avoid crashing.
one, a goods carrier and so on) and every typology has a Every agent can only interact with the ones within a range R
priority. So if the system has to make a train stop for more defined at the start of the simulation: these are the other planes
time on a “stop node”, waiting for the next node to become that it can “see” (on a virtual radar) from its position in the
free (forcing in this way the train to wait), usually it prefers to space. Every agent sends to the others it sees an update on its
stop the train with lower priority. The aim of the algorithm is future mission steps so they can check if there are conflicts.
also to find a solution where the delay of the involved trains is The authors propose two solutions to the above problem: a
as limited as possible, and where the higher priority of a train local one and a global one.
implies a minor delay. Moreover the protocol has to keep the In the local one, the two agents involved in a conflict
changes made to the original “station crossing plan” as limited propose, at first, a list of possible changes to their path and
as possible. look if they can adopt one of these change to avoid the
conflict. If they are not able to find a solution based on the
IV. MPCA list of generated maneuvers, they generate more maneuvers
(accepting higher values for the parameters, for examples
An area where multiagent systems are very often used is the trying to move more to left, speeding up/slowing down more,
one of “collision avoidance”: in this domain the system reflects making the altitude higher and so on) and add them to the
a situation where unmanned entities (autonomous airplanes) list: then they try again to solve the conflict. They repeat this
need to move avoiding crashing, respecting constraints on the procedure until they find a solution. In this way the list can
path they can use, time to make a decision, distance they need be filled with tens or hundreds maneuvers and the solution is
to maintain between them and so on. always found. A random choice is used when there are several
Usually, this type of problem is faced in the airspace solutions with the same utility value (using an utility function
management, where unmanned little planes need a protocol not described here).
to negotiate the route, or in software applications where the When the agents have solved their conflict, they will check
if other collisions exist and will start the protocol again to The MPCA algorithm in particular is very similar to the
solve the first one that arises. FYPA one because it is based on the same idea of “moving
If an agent is involved in more than one collision, it will others to get space for you”: for this reason it has been selected
solve the one that is expected to occur first in time. for our analysis and comparison. The MPCA domain, instead,
This algorithm is called “Iterative peer-to-peer collision is quite different from ours because airplanes have much more
avoidance (IPPCA)”. flexibility in their movements than trains (they must avoid
In the second algorithm (the one proposing a global solu- certain zones and avoid other agents, but must neither follow
tion) called Multi-Party Collision Avoidance (MPCA), authors rigid and limited paths, nor have to reach a fixed point but
enlarge the set of agents involved in the collision to find a and area) and, above all, they move in a 3D space. For these
better solution: in this case the idea is to give the colliding reasons MPCA could not be selected for solving our FYPA
agents enough space to make their evasion maneuvers (to avoid problem.
all the agents around) without changing their plans too much.
The agents that have a colliding path create a group: then V. A IRPLANE REROUTING (APR)
they try to change their paths (they create a list with all the
Another attempt to apply multiagent system negotiation to
possible modifications to their paths) and add to the group
the airplane collision avoidance problem comes from Agogino
those agents that could be interested by these path changes.
and Tumer [3]. In their work the authors present a multiagent
So the group is enlarged to involve all the agents that are near
structure to control air traffic flow using tree kinds of “change
to the ones that have a conflict. Then, the possible alternative
mechanisms”, explained later, and then analyze a learning
plans are analyzed by the group till a solution is found, and
algorithm to improve the system efficiency (that we do not
all the agents will modify their path as decided.
report here because it is out of our scope). The domain is the
The group searches the states space of possible plan changes
one of US airspace, where the space is divided into regional
(due to all the possible applications of evasion maneuvers
centers and again into sectors. The algorithm uses a global
sequences, velocity change and so on) using an A* algorithm
evaluation function that considers the congestion in a particular
modified for the situation.
set of sectors and the global air traffic delay. Using this
To simplify the communication and synchronization issues
common function agents independently take decisions about
the authors have implemented this protocol creating, for each
how changing their plans. In this system agents are ground
group, a coordinator agent that collects all the information it
location throughout the airspace and are called “fixes”. Each
needs to solve the problem and than to find a solution. In this
agent is responsible for the aircrafts going through its fix.
way the organization of the algorithm is partially centralized.
Every airplane has a “flight plan” consisting of a sequence
If an agent is involved in more multi-party groups, it will
of fixes. In this organization agents can change the plan of the
only join the one with the earliest expected collision in the
interested airplanes in three ways:
time line.
As the authors explained to us, MPCA could be used as a • Miles in trail (MIT): agents control the distance that the
global protocol, but it is not intended to be so. The idea is to airplane must keep from each other while approaching a
used it as a “local/global” protocol. This means to compute fix. If the MIT values is high, fewer planes will be able
“globally” a solution for a small group of airplanes, that are to cross this area because they need to slow down their
involved in a single collision situation, but in the meanwhile velocity to maintain the distance
another group of agents can solve different collision in their • Ground delays: an agent can control how long aircrafts
corner of the world. So MPCA was designed to be something that will eventually go through a fix should wait on the
between local and global: it is used to solve “globally” ad hoc ground, that is, the airplanes will arrive later at the fix
local problems. • Rerouting: an agent can divert the foreseen planes of its
The MPCA has been tested using AGENTFLY and the fix making them choosing another path.
comparison has been made using the IPPCA algorithm, im- The algorithm identifies sets of agents that can influence
plemented as plug-ins in AGENTFLY. themselves rerouting airplanes in their fixes: each agent lists
The observed differences between IPPCA and MPCA are: the possible solutions to the congestion problem and then
• message flow characteristics: IPPCA has quite steady chooses the best solution using different learning algorithms
bandwidth of communication flow. MPCA has high peaks (the authors study some types of learning strategies and
and then very low communication (as the data are com- compare them).
puted by the coordinator); This agent’s organization is quite similar to the one we
• quality of solution: MPCA provides better solutions be- adopted, so we included this algorithm in our comparison.
cause the A* is able to find solutions that are not checked From the available documentation, it is not clear whether the
with IPPCA; agents can use in the same simulation all the three techniques
• computation demands: as the MPCA goes through much seen above to change the plan (or if they must use only one
bigger space, the computation is much longer. This one type in a run) and furthermore we did not find the strategy
of the reasons to keep MPCA local by restricted size of used to choose among these strategies (if they are foreseen
the group. simultaneously).
The algorithm has been developed using FACET (Future of that research). Upon specification of a desired destination D
ATM Concepts Evaluation Tool) [5], that receives scripts from the motion primitive will compute a path that takes the agent
the agents, simulates the execution of the algorithm, and to D with zero final velocity.
returns the overall impact of their changes to the airplane’s Every agent stores information about itself and the other
plans. agents and is able to communicate using a wireless network.
This algorithm is interesting but seems to work only if The algorithm grants that every agent will always, and only,
the groups are limited to few agents, because it is based on move inside its reserved area, A. Instead of choosing the
the list of possible choices, that becomes too long if there reserved area (A) directly, agents are indicating their intentions
are large sets of agents, or too many possibilities of plan by requesting an area (called B area) first, and exchanging it
changes. More, the agents seem not to negotiate, but only to with the others. Agents can change B arbitrarily. However,
work independently using the same evaluation strategy and significant changes to B can cause the negotiation cycle to
only one possible change to the airplane route. All these start over. The requested area B has to contain the reserved
constraints seem prevent the system from being applicable to area A at all times, hence, an agent cannot move to a location
very complex scenarios or short term simulations, as FYPA that is not inside the requested area.
instead does. Two intersecting B areas indicate a possible conflict. In
this case the agents will negotiate to find out which one gets
VI. WAYPOINTS
priority and how the A areas are being selected. The base for
Similar problems and solutions as those discussed above can this negotiation is a scalar cost function: the agents with a
be found in the field of autonomous robots which are able to conflict exchange their respective costs and choose who has
independently move and need to avoid collisions while trying the higher priority using this, choosing also who will change
to reach a desired destination. This is a common situation for its A area. The agent with the lower priority will reduce its A
example in the military area, where robots are entities that area (stopping and waiting for the other agent to pass over).
must explore territories, or in industrial applications where With this solution an agent should stop and wait several
little robots could be used in places that are not suitable for times, getting a huge delay: the algorithm proposes also a
humans (under-water, in mines, and so on). second way of acting. Instead of stopping, an agent can decide
In the area of autonomous robots it is worth mentioning the to change its path to avoid an obstacle (or simply a point
proposal made by Purwin, D’Andrea and Lee [34]: the authors of its paths that intersects with many other agents) and to
present a cooperative decentralized path-planning algorithm move around that. It will choose a “way-point”, that is a new
for a group of autonomous agents that provides guaranteed intermediate destination, and will try to reach it using the same
collision free trajectories in real-time. The algorithm is based algorithm shown above. Then it will start again to reach the
on the idea that every agent reserves an exclusive area (called initial destination.
A area) for itself and always remains inside that area, and no In the basic algorithm all agents can communicate with all
two reserved areas are allowed to intersect at any time. the others: this implementation is foreseen for autonomous
The core of the algorithm is based on pair-wise conflict robots, with limited battery autonomy and wireless communi-
resolution among two agents. Both agents operate according cation limitation, so if the total number of agents is huge then
to exactly the same rules, with the only exception being the robots can limit their communication range to reach only
how priority is assigned. For the algorithm the following the nearest agents, saving energy. This algorithm’s limitation
assumptions are made: is realistic because probably only the agents that are close to
• decentralized agents: all computation/control is done on each other can have intersecting paths, consequently an agent
board; must inform only its neighbors of the changes to A and B
• the total number of agents is known; areas.
• motion primitives are available to move the agents in a We do not describe the algorithm with more details because
deterministic fashion; it presents a complex and out-of-our-scope description of the
• point-to-point communication between agents is sup- primitives chosen for changing the reserved and requested
ported; area, that are managed by a geometrical function and not by
• agents can localize themselves, but not others. the negotiation protocol: the A and B areas will be always
The algorithm is executed considering discrete time (agents rectangles, chosen to approximate the new path. Moreover, the
work with “frames”, that is, they assume a discrete divisions paper presents the pseudo-code of the protocol, so reporting it
of time). here is not interesting, and the code in C++ is also available
Every agent is trying to reach its task location, which has on the author’s web site.
been selected by some higher level entity that is not in the This algorithm is similar to FYPA in the idea of how the
scope of that work. Position and velocity of the agent are agents collaborate to solve the conflicts and how they can
expressed in a global Cartesian coordinate system. The agent’s change their strategy: in both protocols agents can stop and
motion is controlled by a deterministic motion primitive MP(), wait for the other to move, or can change their path. The
which contains trajectory generation and low-level control of difference is that in our domain the paths are limited to a
the mechanical actuators (also this aspect is out of the scope predefined set and are divided into fixed parts. Every subpart
is managed by a Resource agent, whereas in that article agents and specifies how much the agent will concede before skipping
are able to move without limitations and without intermediate to the second phase.
agents. More, those agents operate in a wireless environment, The second function of stage 1 is to ensure that some utility
so the number of exchanged messages and the real distance is obtained while waiting for stage 2 to complete. If the reason
of the agents can make the difference on the behavior of the the protocol was started was a resource requirement change,
entities: in this case some limitations and heuristics must be a temporary solution is applied to the problem: this solution,
adopted (not described here), while in our algorithm the only although not conflicts free, has the ability to obtain at least
limitation is due to the computational time of managing all the some utility while the mediator tries to get a better solution.
messages. Anyway we tested our system also with complex Conflicts that are unresolved are actually left to the individual
configurations and the number of messages does not make the sensor agents to handle.
performances degrade. If stage 1 was activated because of a newly discovered
conflict, and a conflict-free solution cannot be found, then the
VII. SPAM manager just enters stage 2: in this case it does not concede,
In [27] a “cooperative negotiation protocol that solves a dis- does not bind a temporary solution, and it does not reset its
tributed resource allocation problem while conforming to soft objective level, but it only enters stage 2 to find a solution.
real-time constraints in a dynamic environment” called SPAM Stage 2 attempts to solve all local conflicts that a track
(Scalable Protocol for Anytime Multi-level) is presented by manager has by elevating the negotiation to the track managers
Mailler, Lesser and Horling. In particular that proposal models that are in direct conflict over the desired resources. The
the resource allocation problem as a constraint satisfaction originating track manager takes the role of the negotiation
problem. mediator and starts collecting all the information it needs to
As in the other domains described above, in that work we generate alternative solutions. These solutions are generated
can find a set of limited resources and some agents interested without a global vision, so they are conflict free only from the
in using them in different moments for different periods: the point of view of the mediator. What this means is that the view
resources are three sensors platforms, and agents need at least of the mediating manager is limited to only the constraints that
three sensors to track an entity moving in the environment. arise from the sharing of a resource with it. If the solution that
More sensors give a more accurate target’s location. will be imposed by the mediator will cause other conflicts then
In the proposed solution each platform is managed by an other agents will try to solve them, even starting again all the
agent, which is also in charge of localizing and following a algorithm.
target (this task allocation is made out of the system), deciding When an agent is the mediator of a conflict, it starts
which sensors (of which platform) it needs to do this and asking the other agents for meta level information, than it
when. So if two, or more, agents (called also track managers) elaborates them and generates all the possible alternative
need the same sensor for different tasks then a conflict arises solutions, including those where one, or more agents, must
and it must be solved. The solution is centralized because the lower its utility function. Then it will send the list with the
agent that first creates the conflict becomes the “mediator” of it alternative solutions to the agents involved and will wait for
and must solve it, asking the other involved agents information their responses: the other agents will reorder the list using their
and then propagating its decision. Every agent has an utility local information and utility function and will send back this
function U that uses to evaluate the proposed solution (the set reordered list to the mediator. Last, the mediator chooses a
of sensors and the period of usage), and can change U to solve solution, possibly a good one for all the agents involved, and
quickly a conflict. sends it to the agents that must apply it.
SPAM protocol works in two main phases, trying at first to At this point, each of the track managers is free to propagate
find a solution which avoids the negotiation. At the end of the and mediate a new negotiation if it chooses to enter the
first stage there is always a solution, even if it is not the optimal second stage. At the time when this article was written, SPAM
one or if it generates conflicts. The algorithm foresees also to allows the agents to enter potential oscillations, maintaining
lose a target, solution that anyway causes a huge penalization no prior state other than objective levels, from negotiation to
of the social utility. negotiation and rely on the environment to break oscillations.
Stage 1 of SPAM serves two primary functions. The first To test the SPAM protocol the authors implemented a model
one is to try to find a solution within the context of the of the domain in a simulation environment called Farm [21],
information that the protocol has when it starts up. However, a component-based distributed simulation environment written
since the protocol attempts to maximize the social utility, each in Java. They performed tests to evaluate the performance of
of the agents tries to maximize its local utility without causing SPAM compared with those of a Greedy Tracking Agent and
new constraint violations. If this can be done, then no further an Optimal Tracking Agent. To do this, the simulation used
negotiation is necessary, and the protocol terminates at the end not moving targets.
of stage 1. In the simulation with moving targets (a not comparing test,
Moreover, in this stage the agents use a “concession rate” only a performance test), SPAM gives good results, near to
to decide if they have to activate the second phase, more the optimal, and shows a linear increase in the time needed to
expensive, or not: this rate is a percentage of the agent’s utility converge when the problem gets harder, but they do not have
implemented other solutions to compare with. In particular, “Limited” referred to sociality underlies a
Comparing this protocol to FYPA, the main difference that solution where the agents communicate among each others
emerges seems to be in the possibility for a track manager but use very simple data structures and, above all, sociality
agent to “loose a track”, namely give up tracking an object, if amounts to simple exchange of information: the solution to
it becomes too hard to do that: in SPAM this event is allowed, the problem is partially centralized, so the agents are more
even if it is the last option, whereas in our protocol it is not “communicative” than “social”. The same value for the “Pro-
possible for a user agent - a train - to give up obtaining activity”1 parameter underlines that the main behavior of
resources - railway tracks and nodes: the train has to stay agents is passive, that is, they wait for some changes in the
somewhere in the station!. Furthermore, the representation environment happen before acting. So these agents are more
of the domain as a constraint problem should be almost reactive than proactive.
difficult for the FYPA domain, and finally we preferred a real
distributed negotiation, while the solution proposed in [27] B. Domain, Purpose, Approach of the MAS
is partially centralized. In a way similar to the Contract Net Table III provides a comparison with respect to the general
protocol, agents do not negotiate, they choose one of them features of the protocols.
to solve the constraint problem and then apply the solution it
• Which is the domain where the protocol is applied?
proposes.
The described protocols refer to different applicative do-
VIII. C OMPARISON mains, that are summarized in this way: Railway manage-
ment (“RAIL”), Air traffic management (“AIR”), Sensors
A brief comparison among FYPA and these algorithms has
management (“SENSOR”) and Autonomous robots’s path
been already presented in the previous sections, with the aim
management (“ROBOT”).
of clarifying why they have been chosen for the comparison
• Is the protocol used for simulation purposes (for
and why they have been not adopted to solve our resource
example, for performing a what-if analysis or for
allocation problem.
implementing a decision support system)? For this
Now, in order to draw a systematic comparison between the parameter the value will be “YES” if the system/protocol
five systems introduced in the previous sections, we identify a has been implemented/used in simulations too
set of features relevant for characterizing a negotiation proto- • Is the protocol used for controlling agents (hence, not
col, besides the general ones proposed in [14] and summarized for simulation purposes, but for allowing real agents
in Table I. to negotiate)? In this case, the value will be “YES” if,
A. Accepted agent definition and only if, the system has the real control over physical
entities, that is, its decisions are not checked by an human
We adhere to the definition given by Jennings, Sycara and
operator. The value will be “Limited” if a human user will
Wooldridge [24]:
accept the proposed solutions before applying them.
“An agent is a computer system, situated in some • Which is the approach underlying the protocol? For
environment, that is capable of flexible autonomous this parameter we list the main standard techniques used
action in order to meet its design objectives. There in the protocol, for example Game theory, Auctions and
are thus three key concepts in our definition: situat- so on.
edness, autonomy, and flexibility.” • Is the system used for a real industrial application?
Hence, the first characterizing feature we consider in our Which one?
comparison is what definition of agent is accepted by the
authors, specifying which standard features can be found in C. Analysis and design of the MAS negotiation protocol
the MAS discussed above. Table IV shows the values for the parameters that we
• Are agents autonomous? considered for the design features of the protocols.
• Are agents situated?
• Which is the detail level of the MAS design? The
• Are agents responsive?
possible values are: High (Verbal description of the
• Are agents pro-active?
system), Low (Detailed description with use cases or
• Are agents social?
Class Diagram or other languages)
Table II provides a comparison among the protocols we • Is the pseudo-code, or a simplified version of the code,
described in this paper, with respect to the accepted definition of the negotiation protocol available?
of agenthood. For every parameter the possible values are:
1 Concerning the MPCA protocol, the value NO for the filed “Pro-activity”
• YES: the agents show all the typical features associated
is correct if we limit our evaluation only to the MPCA protocol, but if we
with the parameter; consider agents in the whole AGENTFLY project (those called “pilot agent”),
• NO: the agents show none, or very few, of the typical they are pro-active as well. At the beginning, every pilot agent receives its
features associated with the parameter; mission (which can be changed by human operator during the simulation)
and the agent plans its trajectory to fulfill its mission or to communicate
• LIMITED: the agents show some of the typical main with other agents if it is in a group mission (see “tactical-agentfly” at
features associated with the parameter. http://agents.felk.cvut.cz/)
What kind of resources are being distributed? How are they being distributed? Why are they being distributed?
MPCA volumes of air space see details in Section IV to avoid collisions among airplanes
APR volumes of air space see details in Section V to avoid collisions among airplanes
Waypoint rectangular areas see details in Section VI to avoid collisions among robots
SPAM sensors see details in Section VII to track targets
FYPA railway tracks and nodes inside a station see details in Section III to avoid collisions among trains
Table I
C OMPARISON : GENERAL FEATURES
Autonomy Situatedness Reactivity Pro-activity Sociality
MPCA YES YES YES NO YES
APR YES YES YES LIMITED LIMITED
Waypoint YES YES YES NO LIMITED
SPAM YES YES YES NO LIMITED
FYPA LIMITED YES YES YES YES
Table II
C OMPARISON : ACCEPTED AGENT DEFINITION
Domain Simulation Real control Approach Industrial
MPCA AIR YES YES A* state search YES (BAE Systems and others)
LIMITED (foreseen for the Fed-
APR AIR YES LIMITED Learning algorithm
eral Flight Administration)
Scalar cost function,
Waypoint ROBOT NO YES NO
Computational Geometry
Distributed Constraints
SPAM SENSOR YES NO NO
Satisfaction Problem
Distributed resources
FYPA RAIL YES LIMITED YES (Ansaldo STS)
allocation
Table III
C OMPARISON : D OMAIN AND SIMULATION
• How many different agent roles does the MAS in- This applies to Table V too.
clude?
• How many different kinds of messages do the agents D. Implementation of the MAS negotiation protocol
exchange? The number indicates the type of different
In Table V we summarize the values for the parameters
ACL messages (if known) or different semantics (request,
regarding the implementation features of the protocols.
answer, update...)
• Is the solution computed in a partially centralized way
• Is the MAS implemented?
(at least, in any iteration step of the negotiation)? The • In which programming language?
• Is the MAS based upon an existing agent platform?
value will be YES if the final solution in calculated by
• Can the strategy of the agent vary during the same
only one agent2 , NO if the solution emerges from a real
negotiation among agents. execution run? With “varying strategy agent”3 we intend
• Is the algorithm guaranteed to terminate? Under
an agent that is able to act in different ways using
which conditions? The value will be NO if the algorithm different rules. That is, it is able to find many ways to
is allowed to enter a loop or a situation where it does not solve a problem during the execution/simulation
• Is the code implementing the protocol available?
assure to find a solution within a specified time, while
the value will be YES if the algorithm will always find a Under which license? The possible values are: “FREE”
solution. In this case, if the solution is partial or it accepts if the code is available under an open license, “NO” if
some constraints violation, this will be specified between the code is protected by a Non disclosure agreement or
round brackets. it has been registered for a third private entity or “UNK”
if we do not know how/it the code is available.
If, from the available documentation, we were not able to
clearly understand the correct value to be assigned to some 3 Concerning the MPCA protocol, once the MPCA or IPPCA is used for
parameter, we use the value UNK, that stands for “unknown”. solving particular problem, the agent will use it until a solution is find
or timeout will pass. Considering the global “AGENTFLY” project, pilots
agent have several different methods to solve collision avoidance (MPCA and
2 Concerning the MPCA protocol, a decentralized implementation exists but IPPCA are just some of them) and they select the best method based on
it is not published, so we do not consider it in this paper. current situation (time to solution, mission goals, environment and so on).
Design Pseudo-Code Roles Messages Centralized Termination
MPCA HIGH YES 2 2 YES YES
APR UNK NO 1 2 NO YES
Waypoint UNK YES 1 3 NO YES
YES (but with no assurance that
SPAM UNK NO 2 4 YES
all tracks have been managed)
YES (a no-way-out situation is
FYPA Low YES 3 7 NO
reported to the user)
Table IV
C OMPARISON OVER THE DESIGN FEATURES
Var.
Impl. Lang. Platforms Code available User GUI
Strategy
YES (for aca- ON
MPCA YES Java AGENTFLY/ AGLOBE NO YES
demic purposes) LINE
APR YES UNK FACET NO UNK NO NO
Waypoint YES C++ 2005 Cornell RoboCup YES FREE NO PH
SPAM YES Java FARM YES UNK NO NO
OFF
YES (JADE in-
FYPA YES Java JADE YES NO LINE,
terface)
[10]
Table V
C OMPARISON OVER THE IMPLEMENTATION FEATURES
• Can the user interact with the MAS on-line during to users, instead of many different and not integrated MARA
the MAS execution? If the value is “YES” it means that solutions.
the user can change the execution of the system while it As far as FYPA is concerned, we already made the success-
is running, using a GUI or other techniques. ful effort to generalize the problem that Ansaldo STS posed
• Which GUI is available? The value can be “ON LINE” to our attention, in order to exploit the solution we developed
if a GUI exists and the user is allowed to modifies the in situations other than the specific Ansaldo STS one [7]. If
execution of the system, “OFF LINE” if something exists we will be able to prove that the FYPA protocol is suited to
that shows the user the execution of the protocol (during manage even more MARA problems, we could move another
the execution or later), “NO” if the system only gives step further and design a platform for developing negotiation
the result but is not able to let the user understand the protocols, starting from the FYPA one. This platform could
intermediate steps of the protocol. The value will be “PH” help users to develop new negotiation protocols step by step,
if the system is physically implemented so its execution is starting from the definition of the model (entities, resources
visible for the user (you can see for example the physical and their dependencies) and moving on with the definition of
entities moving) but it can not be considered a GUI. the rules regulating the interaction (specifying the time-outs,
the priorities of entities...) and, for example, those to calculate
IX. C ONCLUSIONS AND FUTURE WORK the alternative allocations.
This paper complements the one presented at WOA 2009 The next extension would be to integrate this platform
[12] and further refined in [11], where we discussed the for developing negotiation protocols into the DCaseLP rapid
preliminary design and implementation of the FYPA system. prototyping framework [28], thus resulting into an “Enhanced
In this paper we propose a systematic comparison among DCaseLP”, in order to allow developers to specify rules
five MARA systems, including FYPA. The comparison is regulating the agents behavior using a logical language such
detailed enough to help a developer/scientist looking for as tuProlog.
implemented MARA solutions, in choosing among them. Finally, as proposed in [9], a further extension to our
From the comparison, a fact emerges: all the analyzed work could be to integrate the verification capabilities offered
systems (and many others that we took under consideration by Concurrent MetateM [19] into the “Enhanced DCaseLP”
during our research activity but that we did not report here) are framework.
designed to solve very specific problems, although in principle Regarding the proposal to integrate ontologies in MASs
they might be easily generalized (with little or much effort that we presented at WOA 2008 [8], our research group has
depending on the system) to face similar problems in domains already extended the Ontology Agent, as described in [30].
other than those they were designed for. The “Enhanced DCaseLP” will take advantage of these results
If this generalization process took place, an integrated plat- without any further effort since the extended Ontology Agent,
form for developing negotiation protocols could be provided being developed in JADE, will be able to be integrated into it
for free. [21] B. Horling, R. Mailler, and V. Lesser. Farm: A scalable environment
for multi-agent development and evaluation. In A. G. C. Lucena,
ACKNOWLEDGEMENTS J. C. A. Romanovsky, and P. Alencar, editors, Advances in Software
Engineering for Multi-Agent Systems, pages 220–237. Springer-Verlag,
This paper is based on Chapter 7 of Daniela Briola’s Ph.D. Berlin, February 2004.
Thesis, [7]. [22] B. Hubermanand and S. Clearwater. A multi-agent system for controlling
We thank Riccardo Caccia from Ansaldo STS for his help building environments. In V. Lesser, editor, Proceedings of the 1st
International Conference on Multiagent Systems, 1995 June 12-14; San
and support during all the stages of FYPA development. Francisco, CA, volume 1, pages 171–176, 1995.
[23] N. R. Jennings. Cooperation in industrial multi-agent systems. World
R EFERENCES Scientific Publishing Co., Inc., River Edge, NJ, USA, 1994.
[1] M. R. Adler, A. B. Davis, R. Weihmayer, and R. W. Worrest. Conflict [24] N. R. Jennings, K. Sycara, and M. Wooldridge. A roadmap of
resolution strategies for nonhierarchical distributed agents. In L. Gasser agent research and development. Autonomous Agents and Multi-Agent
and M. N. Huhns, editors, Distributed artificial intelligence: vol. 2, pages Systems, 1(1):7–38, 1998.
139–161, San Francisco, CA, USA, 1990. Morgan Kaufmann Publishers [25] S. Lander and V. Lesser. Sharing Meta-Information to Guide Cooperative
Inc. Search Among Heterogeneous Reusable Agents. IEEE Transactions on
[2] AgentFly: reference homepage. http://agents.felk.cvut.cz/projects/ Knowledge and Data Engineering, 9(2):193–208, January 1997.
agentfly/. [26] V. R. Lesser. Cooperative multiagent systems: A personal view of the
[3] A. Agogino and K. Tumer. Regulating air traffic flow with coupled state of the art. IEEE Transactions on Knowledge and Data Engineering,
agents. In AAMAS ’08: Proceedings of the 7th international joint 11:133–142, 1999.
conference on Autonomous agents and multiagent systems, pages 535– [27] R. Mailler, V. Lesser, and B. Horling. Cooperative negotiation for soft
542, Richland, SC, 2008. International Foundation for Autonomous real-time distributed resource allocation. In AAMAS ’03: Proceedings
Agents and Multiagent Systems. of the second international joint conference on Autonomous agents and
[4] M. Barbuceanu and M. S. Fox. Cool: A language for describing multiagent systems, pages 576–583, New York, NY, USA, 2003. ACM.
coordination in multi agent systems, 1995. [28] V. Mascardi, M. Martelli, and I. Gungui. DCaseLP: a prototyping
[5] K. D. Bilimoria, B. Sridhar, G. B. Chatterji, K. S. Shethand, and S. R. environment for multi-language agent systems. In M. Dastani, A. E.-
Grabbe. Future atm concepts evaluation tool. In Air Traffic Control F. Seghrouchni, J. Leite, and P. Torroni, editors, In Proceedings of the
Quarterly , 9(1), 2001. First Workshop on LAnguages, methodologies and Development tools
[6] M. Boman, P. Davidsson, N. Skarmeas, K. Clark, and R. Gustavsson. for multi-agent systemS, LADS’007 Post-proceedings, volume 5118 of
Energy saving and added customer value in intelligent buildings. Build- LNCS, pages 139–155. Springer-Verlag, 2008.
ing, 1:505–516, 1998. [29] C. L. Mason and R. R. Johnson. Datms: a framework for distributed
[7] D. Briola. Negotiation in Multiagent Systems: Protocols, Ontologies and assumption based reasoning. In L. Gasser and M. N. Huhns, editors,
Applications. PhD thesis, DISI, University of Genova, Italy, 2011. Distributed artificial intelligence: vol. 2, pages 293–317, San Francisco,
[8] D. Briola, A. Locoro, and V. Mascardi. Ontology agents in fipa- CA, USA, 1990. Morgan Kaufmann Publishers Inc.
compliant platforms: a survey and a new proposal. In From Objects [30] F. Mulattieri. Progettazione ed implementazione di un ontology agent.
to Agents Workshop, WOA 2008, Proceedings, 2008. Master’s thesis, DISI, University of Genova, Italy, 2010.
[9] D. Briola, M. Martelli, and V. Mascardi. Specification, simulation and [31] D. E. Neiman, D. W. Hildum, V. R. Lesser, and T. W. Sandholm.
verification of negotiation protocols in a unified agent-based framework Exploiting meta-level information in a distributed scheduling system. In
(extended abstract). In ICTCS 2010: 12th Italian Conference on Proceedings of the twelfth national conference on Artificial intelligence
Theoretical Computer Science, 2010. (vol. 1), AAAI ’94, pages 394–400, Menlo Park, CA, USA, 1994.
[10] D. Briola and V. Mascardi. Design and implementation of a NetLogo American Association for Artificial Intelligence.
interface for the stand-alone FYPA system. In this volume. [32] T. Oates, M. V. N. Prasad, and V. R. Lesser. Cooperative information-
[11] D. Briola, V. Mascardi, and M. Martelli. Intelligent agents that monitor, gathering: a distributed problem-solving approach. IEE Proceedings -
diagnose and solve problems: Two success stories of industry-university Software, pages 72–88, 1997.
collaboration. In Journal of Information Assurance and Security, [33] H. Parunak. Manufacturing experience with the contract net. Distributed
volume 4, pages 106–117, 2009. Artificial Intelligence, pages 285–310, 1987.
[12] D. Briola, V. Mascardi, M. Martelli, R. Caccia, and C. Milani. Dynamic [34] O. Purwin, R. D’Andrea, and J.-W. Lee. Theory and implementation
resource allocation in a MAS: A case study from the industry. In From of path planning by negotiation for decentralized agents. Robot. Auton.
Objects to Agents Workshop, WOA 2009, Proceedings, 2009. Syst., 56(5):422–436, 2008.
[13] N. Carver and V. Lesser. A new framework for sensor interpretation: [35] A. S. Rao and M. P. Georgeff. Modeling rational agents within a bdi-
Planning to resolve sources of uncertainty. In In Proceedings of the architecture. In KR’91, pages 473–484, 1991.
Ninth National Conference on Artificial Intelligence, pages 724–731, [36] M. P. Singh. Towards a formal theory of communication for multi-agent
1991. systems. In In Proceedings of the Twelfth International Joint Conference
[14] Y. Chevaleyre, P. E. Dunne, U. Endriss, J. Lang, M. Lemaı̂tre, on Artificial Intelligence (IJCAI-91, pages 69–74. Morgan Kaufmann,
N. Maudet, J. A. Padget, S. Phelps, J. A. Rodrı́guez-Aguilar, and 1991.
P. Sousa. Issues in multiagent resource allocation. Informatica (Slove- [37] T. Sugawara and K. Murakami. A Multiagent Diagnostic System for
nia), 30(1):3–31, 2006. Internetwork Problems. Proceedings of INET’92, January 1992.
[15] D. Cockburn and N. R. Jennings. Archon: A distributed artificial [38] K. Sycara, S. Roth, N. Sadeh, and M. Fox. Distributed constrained
intelligence system for industrial applications, 1995. heuristic search. IEEE Transactions on Systems, Man, and Cybernetics,
[16] P. R. Cohen and H. J. Levesque. Intention is choice with commitment. 21:1446–1461, 1991.
Artif. Intell., 42:213–261, March 1990. [39] U.S. Congress, Office of Technology Assessment. Electronic Enter-
[17] K. Decker. Designing behaviors for information agents. In In Proceed- prises: Looking to the Future. U.S. Government Printing Office, 1994.
ings of the 1st Intl. Conf. on Autonomous Agents, pages 404–412. ACM [40] D. Šišlák, J. Samek, and M. Pěchouček. Decentralized algorithms for
Press, 1997. collision avoidance in airspace. In AAMAS ’08: Proceedings of the 7th
[18] E. H. Durfee and J. S. Rosenschein. Distributed problem solving and international joint conference on Autonomous agents and multiagent
multi-agent systems: Comparisons and examples. In Proc. 13th Intl systems, pages 543–550, Richland, SC, 2008. International Foundation
Distributed Artificial Intelligence Workshop, pages 94–104, 1994. for Autonomous Agents and Multiagent Systems.
[19] M. Fisher. A survey of concurrent metatem - the language and its [41] R. Weihmayer and R. Brandau. A distributed ai architecture for customer
applications. In Proceedings of the First International Conference network control. In IEEE Global Telecommunications Conference,
on Temporal Logic, ICTL ’94, pages 480–505, London, UK, 1994. Globecom’90, Proceedings, pages 656–662. IEEE, 1990.
Springer-Verlag. [42] M. P. Wellman. A market-oriented programming environment and its
[20] B. Grosz and C. Sidner. Plans for discourse. In P. Cohen, J.Morgan, and application to distributed multicommodity flow problems. Journal of
M. Pollack, editors, Intentions in Comm., pages 417–444. MIT Press, Artificial Intelligence Research, 1:1–23, 1993.
Cambridge, Mass., 1990.