=Paper=
{{Paper
|id=Vol-1664/w5
|storemode=property
|title=Applying Social Norms to Implicit Negotiation among Non-Player Characters in Serious Games
|pdfUrl=https://ceur-ws.org/Vol-1664/w5.pdf
|volume=Vol-1664
|authors=Marco Robol,Paolo Giorgini,Paolo Busetta
|dblpUrl=https://dblp.org/rec/conf/woa/RobolGB16
}}
==Applying Social Norms to Implicit Negotiation among Non-Player Characters in Serious Games==
https://ceur-ws.org/Vol-1664/w5.pdf
Applying social norms to implicit negotiation
among Non-Player Characters in serious games
Marco Robol Paolo Giorgini Paolo Busetta
Department of Information Engineering Department of Information Engineering Delta Informatica SpA
and Computer Science and Computer Science Trento, Italy
University of Trento University of Trento Email: paolo.busetta@deltainformatica.eu
Trento, Italy Trento, Italy
Email: marco.robol@studenti.unitn.it Email: paolo.giorgini@unitn.it
Abstract—Believable Non Player Characters (NPCs), i.e. arti- able to interpret and follow them. Specifically, INCA adopts
ficial characters simulating rational entities, are a great addition social norms to rule the order of engagement of resources,
to videogames, no matter if used for entertainment or serious so that each agent can autonomously reason and implicitly
reasons. Especially NPCs that represent people in realistic set-
tings need to show plausible behaviors; to this end, one of main coordinate with others without the need of negotiations. Com-
issues to be tackled is coordination with other participants, either mon examples of situations where INCA is suitable include
other NPCs or human players, when performing everyday tasks pedestrians crossing doors or gates, people queuing in front
such as crossing doors, queuing at an office, picking the first of automatic vending machines, drivers selecting a tollbooth
free object up from a set, and so on. Much of this coordination among those at the entrance of a highway, and so on. The
happens silently and is driven by social norms that may vary
according to culture and context. In this paper, we propose an ability of silently using social norms is especially important
approach to represent social norms in autonomous agents and when one of the characters involved is not an NPC but the
enable implicit coordination driven by observations of others’ avatar of a human player.
behavior. Our approach does not use central coordinators or a After a short introduction to PRESTO (Sec. II), we outline
coordination protocol, but rather let each agent take its own
our approach (Sec. III), then present some of our current
decision so to support more realistic interactions with human
players. A software architecture and initial experimental results technical choices (Sec. IV) and a few examples (Sec. V). We
are presented and discussed. exploit disjunctive logic to rapidly investigate the representa-
tion of social norms in different scenarios; we discuss how this
I. I NTRODUCTION logic-based approach will become the base for implementation
In current videogames, with highly realistic graphics pro- in an imperative language, required for practical deployment
viding an immersive experience, believable NPCs representing on commercial systems (Sec. VII). Theoretical underpinning
humans or other rational entities are an important and largely in multi-agent research is discussed in Sec. VIII.
expected feature. Immersive videogames are increasingly ex-
ploited for serious purposes, such as training, where the issue II. BASELINE - PRESTO
of believability and plausibility of behaviours becomes more 1
PRESTO is a suite of development tools and run-time facil-
relevant than when the objective is pure entertainment.
ities for artificial intelligence in games, focusing in particular
Smart NPCs represent the evolution of their pre-
on cognitive simulation [1]. PRESTO interfaces a number of
programmed, context-insensitive older versions. Smart NPCs
game engines, including Unity2 , to compute the perceptions
require sophisticated behavioral models with many facets,
of NPCs and control their behavior by means of autonomous
including perception elaboration, a decision system, emotions
agents developed with PRESTO’s own DICE framework.
representation, and other aspects driven by cognitive models.
Figure 1 shows a simplified anatomy of PRESTO. Its core
Their implementation can be very complex, particularly when
provides services such as perception elaboration (Situation
they need to interact with other NPCs and, even worse,
Awareness (SA)) and low-level control of the entities in the
with human players. Among other abilities, NPCs must use
Virtual Reality (VR). An ontology provides the conceptual-
basic coordination mechanisms that are commonly adopted
ization required to make behavioral models and scripts inde-
by humans and that could be the result of the application of
pendent of the specificities of a simulation, game or rendering
cultural- and context-sensitive social norms.
engine [2], [3]. A script engine controls the overall evolution of
This paper reports on the work done within the PRESTO [1]
a simulation, while the DICE multi-agent framework is used
project for NPCs coordination. PRESTO’s main objective
for building complex NPC models as an assembly of roles,
is the creation of middleware for the support of rational
behaviour in videogames. We apply a distributed approach to 1 Plausible Representation of Emergency Scenarios for Training Operations
coordination, called Implicit Negotiation Coordinating Agents (PRESTO), a R&D project by Delta Informatica Spa.
(INCA); the idea is to make NPCs aware of social norms and 2 unity3d.com, (2016). Unity Technologies [Accessed 26 Feb. 2016].
23
goals that have to be satisfied by a role and behavioral models resources and minimize eventual conflicts?”. INCA tackles this
implementing the tactics required to achieve goals [1]. coordination problem by reasoning on these concepts: (i) the
actors, who are the performers of some coordinated actions
Fig. 1. PRESTO toward some resources; (ii) the resources, as the representa-
tions of something that only a limited number of actors at a
time can/have to engage; (iii) the order of engagement on the
various resources that actors have to follow; (iv) the actions to
be performed by the actors to carry on with the coordination
process and finally engage the resources.
INCA focuses on coordination by implicit negotiation,
which is very common in people’s everyday activities. Each
actor computes an order of engagement of resources by itself,
without communicating with any of the participants or a
central coordinator. This is possible thanks to social norms pre-
Work is in progress within PRESTO to allow a human shared between all the participants, allowing them to generate
player to become the strategic controller of an agent, del- coherent queues.
egating low level procedures to the latter. This offers the Note that agents are autonomous and can therefore decide
advantages of enabling the construction of cognitive-level to break rules; for example, if an agent realizes to be late it
GUIs and, internally, of uniformly represent and perceive could decide to not respect its turn and overcome others actors
humans and NPCs. in the same queue, resulting in a non coordinated behavior.
To apply INCA, we need to identify and give semantics
A. DICE
to the actions performed by the actors related to a coordi-
Delta Infrastructure for Cognition and Emotion (DICE) is nation process. We have identified four actions that actors
a framework to implement autonomous agents capable of necessitate and are required to perform in order to coordinate
controlling NPCs of a VR in real time. It integrates the fa- and access resources. Adopting a BDI-inspired terminology,
cilities of PRESTO with AOS’ JACK R [4], an agent-oriented they are called approaching, waiting, engaging and engaged.
development environment built on top of, and integrated with, For example, an actor that wants to enter a room and needs
the Java programming language. to pass through a narrow door, first gets close to that door
DICE adds a number of facilities to JACK, including a high- (approaching), then, if there are others attempting to pass,
level interpreted language and mechanisms to push goals to an waits until those who arrived earlier are gone (waiting),
agent from the outside, e.g. scripts and GUIs. then walks toward the door (engaging) and finally crosses it
DICE takes control of a JACK agent with a scheduler (engaged).
implementing a cyclic process, inspired by the classic OODA The agent in control of an NPC reasons on the information
loop [5]. Such approach guarantees synchronization with the it has about the current coordination context, which includes
simulation cycle typical of Computer Graphic (CG) engines. other NPCs involved in the coordination and their current
In its first step, called SA Drilling Down, the scheduler actions, and tries to compute a solution that represents an order
cycle processes the perceptions coming from the VR; then, it of engagement by applying context-specific social norms.
generates intentions in reaction to perceptions; finally, it gives It is worth to stress that information is constrained to what
control to the current main intention (plan) that runs until it the agent has perceived, and so could be incomplete. Also,
decides to yield. During the period in which the plan runs the assumption that others are following the same norms is
(called “cognitive step”) incoming perceptions are queued but not always valid, thus it is necessary to handle unexpected
not processed by DICE. behaviors (e.g. somebody applying different social norms or
Introspection is a general term covering the ability of an even ignoring them because of a strong emotion, such as,
agent to reflect upon his own cognitive functions [6]; DICE panic).
supports introspection over both goals and intentions. While
meta-level reasoning in JACK is limited to choosing, from a A. Architecture
pool of applicable plans (intentions), the one to be executed Figure 2 illustrates the integration of INCA within a single
to achieve a goal, DICE supports richer meta-level reasoning agent controlling a NPC in a VR, thus the represented archi-
thanks to its introspection and attitude manipulation facilities. tecture is repeated for each NPC in a game. In short, social
norms for coordination are integrated into each autonomous
III. M ETHODOLOGICAL APPROACH agent thanks to a meta-level where they are evaluated by an
INCA is the distributed approach that we propose here to intention deliberation process.
improve the interaction and coordination abilities of NPCs 1) Agent domain-level: The domain level is concerned with
with each other (and potentially with human players). Specifi- engaging some specific resources in coordination with others.
cally, INCA handles the question: “what actions, and in which A coordination desire is achieved by executing intentions
order, should each actor performs to tidily engage shared performing coordination actions appropriate for the specific
24
Fig. 2. INCA anatomy The meta-language is based on DLV 3 , a disjunctive logic
language that allows Knowledge Representation and Reason-
ing (KR&R), being one of the best implementation of a
Disjunctive Logic Programming (DLP) language [7].In DLP
languages, facts describe an initial situations on which the
application of disjunctive rules generates different models.
The coordination reasoner takes in input a Knowledge
Base (KB) containing all the information about the context
of coordination, the actors and the resources, which could
be partial because of the limited information available to the
agent. A queue engine computes all possible combinations
of actors in the queues and generates a model for each
configuration. Then a set of social norms is applied to filters
the solutions, at best, up to one. Finally, an instructions
engine computes the instructions that each actor should follow.
1) Social norms in DLV: With social norm we intend a
filtering criteria of the configurations of actors in the queues, as
computed by the queue engine. They are represented, in DLV,
as weak constraint rules that rate each configuration giving a
weighted penalty to the ones that does not respect them. DLV
returns the solution that minimize the number of weighted
penalties.
In the example of individuals that want to pass through a
door, social norms describe commonly adopted rules to define
the order of access; for instance, in normal conditions in a
Western country, well-behaving adults respect their order of
arrival. In DLV this can be obtained with a weak constraint
rule that gives a penalty to each configuration where a person
X, who has arrived after Y, is in the queue before the latter:
domain of application. Which action, and so which intention,
:∼ next(X,Y), queue(X,C), queue(Y,C), waiting-before-than-
to execute and in which order are decisions taken by the meta-
for-queue(Y,X,C). The “next(X,Y)” fact encodes that “Y” will
level, which reasons about the coordination independently of
access the resource after “X”; “next” facts are generated for
the domain.
each person to define his queuing order relation with respect to
2) Agent meta-level: Coordination reasoning is performed all other people in his own queue. As another example consider
at meta-level, to keep it separated from the specific domain of the case of multiple queues, where people tend to spread so to
application. The meta-level does not make the agent execute minimize the time of access. Such a norm can be expressed by
any action but operates only on the agent’s internal state, a weak constraint that gives higher penalties to configurations
controlling intention deliberation thanks to introspection. with more people in the same queue: :∼ next(X, Y). A long
To this end, the meta-level evaluates social norms with queue is a valid candidate that generates a penalty. Assume
respect to the current context. These social norms are not that there are two persons and two queues: a configuration
built into INCA but provided by the agent when formulating in which people are distributed between the queues does not
its domain-level coordination desire. Norms may have been receive any penalty, while a configuration where they are in a
selected by a process influenced by different factors, such as single queue gets one penalty.
a cognitive model that can affect coordination by replacing
commonly applied social norms with others that reflect the IV. T OOLSET SUPPORT FOR INCA
current emotional state of the agent. For example, if a person INCA has been implemented within the DICE framework
is panicking and thus acting irrationally, she does not care described in Sec. II. Its API is currently used by the behav-
to adopt or follow a socially accepted behavior and simply ioral models controlling navigation to coordinate the passage
decides to overcame all the other participants and puts herself through doors, gates and other restrictions along a path. In the
at the top of the queue. following we briefly illustrate the interplay between INCA and
BDI domain-specific models.
B. Social norms development and test with DLV To allow the automatic recognition of actions performed by
other NPCs, INCA exploits the ability offered by PRESTO of
To provide a fast and effective development environment, dynamically tagging entities in the VR with labels taken from
we opted for a meta-language to represent and reason on social
norms. 3 Dlvsystem.com, (2016). DLVSYSTEM S.r.l. [Accessed 25 Feb. 2016]
25
its ontology. INCA uses tagging to publish the fact that an V. E XAMPLES
NPC is interested in accessing a certain resource and which
This section illustrates a few examples of application of
action it is currently performing. This is required because
INCA. The first ones extend what has been presented in
intention recognition, an innate capability in humans and many
Sec. IV, concerning the crossing of doors during navigation.
animals, is computationally hard if not impossible in a VR
They show how agents adopt INCA to coordinate access to
given the insufficient level of details corresponding to the clues
a single resource, with typical cultural variants captured by
used by real people.4
social norms. In the last example, concerning a situation of
Initiating coordination on a set of resources (e.g. one or
simultaneous emergencies to be tackled with urgency, agents
more doors to go from a room to another) can be decided
adopt INCA to silently distribute their workload as it would
by any behavioral model of the agent. For instance, a plan of
be expected e.g. by a well trained team; this is obtained by
the navigation model will start coordination when a door is
modeling the phenomena as multiple resources to be engaged.
perceived along the current path. Worth noticing is that the
navigation model also exploits PRESTO’s dynamic tagging
A. Crossing doors
to reduce dependencies from a specific classification of the
entities in the VR; a “has crossability” relation can be attached PRESTO’s navigation subsystem is designed so that agents
as a so-called PRESTO quality on anything that restricts a path handle any crossable entity on their path by coordinating
and requires coordination with NPCs arriving from the same access with others and engaging the entity with an appropriate
or from the opposite direction. plan (e.g. opening a door, move across it, closing).
The model invokes INCA to get access to an internal object To illustrate how this works, consider an NPC “A” that
which contains: (i) a state of the coordination representing arrives in front of a door. It realizes that the door needs to
the action to perform plus additional parameters, set by INCA be crossed and that nobody else is in front, so it approaches
itself to drive the domain-level; (ii) the resources to coordinate the door and engages it. An NPC “B” arrives just after “A”
on and the policy to adopt, which is a set of the social norms and realizes that “A” was first, so it waits before engaging the
valid for the specific domain selected by the model itself at door.
the beginning. This object is passed to a coordination goal In PRESTO, as mentioned above, doors, gates and so on
that is started by the model itself. A coordination goal is a are ontologically tagged as open or closed with the quality
domain-specific goal (e.g., “door passed”) tagged so that the “has crossability”. Given this, the navigation model in DICE
introspection facilities can identify it as controlled by INCA; is able to identify a door on the NPC’s current path from
the goal is achieved when the coordination is concluded (in the stream of perceptions generated by the PRESTO situation
our example, when the NPC crossed one of the doors). awareness module. As a consequence, the model invokes
The BDI plans that are invoked to satisfy the coordination INCA and gives itself a goal for crossing the door. This goal
goal are the domain-specific implementations of the generic is tagged as a coordination goal, so that the meta-level is able
coordination actions (Sec. III), i.e. approaching, waiting, en- to recognize it and take its control as discussed in the previous
gaging and engaged. In our navigation example, “approaching” section. Its applicable plans deal with the specific sequences
moves the NPC from wherever it is to a certain distance from of actions required to implement the current coordination
the door, “waiting” is the (model-chosen) orderly queuing action determined by INCA (initially approaching the door
behind the door or crowding in front of it, “engaging” the until it is necessary to wait for those in front to cross it, then
final move from wherever the NPC is to a distance where moving to the distance required to finally open and cross the
it can finally open the door and cross it (“engaged”). INCA door). INCA continuously collects and processes data from
first chooses what is the right action to perform then, if a the agent’s memory and incoming perceptions. In the case
new action is required, uses DICE’s introspection API to force of the agent B above, at some point INCA decides that it is
the termination of the current action plan and let the normal necessary to wait for A, so, by introspection, the approaching
BDI retry logic to select the appropriate plan given the chosen plan is terminated and the state of coordination updated to
action (specified in the INCA internal object described above). “waiting”, causing the BDI logic to select the related plan to
INCA exploits the SA step of the DICE scheduler to keep attempt to achieve the coordination goal. Observe that waiting
track of what all other NPCs are doing from perception can be implemented in various ways, according to cultural
updates; the KB for a coordination goal is built from this or emotional factors; the simplest option is just stopping the
data. The SA step is used also to start and monitor an external NPC at its current location, without attempting e.g. to queue
process executing DLV to compute the resource-access queues it behind those in front or getting as close as possible along
and decide which action to take next. the shortest path, as required by more realistic modeling. It
Management of surprises and stalemates arising from con- is left to the agent programmer when developing, selecting or
flicting norms is left to future work. configuring the navigation model for a specific NPC to set it
up according to the desired behaviour. Worth noticing is that,
4 This implies that, in order to achieve NPC / human coordination, players
as part of its introspection facilities, DICE allows to read the
should control avatars at a cognitive level and let their underlying DICE mod-
els perform low-level actions requiring coordination, rather than controlling current emotions and to dynamically change the behavioural
their avatars as puppets as commonly done in videogames. model concerning a specific capability (“role” in DICE terms),
26
such as navigation, to select one appropriate for the current 2) Results interpretation and conclusion: Figure 3 shows
state of the character in the simulation. the execution time as a function of the number of resources.
Let us revisit the case of passage through doors by applying Figure 4 shows the execution time as a function of the number
a more sophisticated social norm, based not simply on the of actors.
arrival order alone but on the socially expected behavior of
letting an elderly person pass first (and maybe providing help). Fig. 3. Execution time with respect to the number of resources
To obtain this, the same policy adopted by INCA in the case
above is modified to consider these exceptions. Assuming that
“B” arrives later as above but represents an elder character,
“A” will let it pass first because it determines that this is the
correct behavior while “B” passes through the door without
waiting because it is also aware of the same rule.
Let us consider a third case of passage through a door, an
emergency situation in which the agent-controlled NPCs are
in panic. Agents could decide to ignore any social norm by
not even invoking INCA and thus attempting to go through the
same door. In this case the NPCs move relying only on the
physic to handle movement and path conflicts. This recreates a
typical situation of panic. Note that this is the same behaviour
that is obtained when no coordination mechanisms is applied
(even in calm situations), which is one of the reasons for Fig. 4. Execution time with respect to the number of actors
simple simulations to appear not realistic to the observer.
B. Extinguishing fires
PRESTO is being used for emergency training and simula-
tion; a typical problem in this domain is fire management. Let
us consider the case of two agent-controlled NPCs, “A” and
“B”, which could be e.g. firefighters, that need to extinguish a
number of fires in a building and need to coordinate in order
to decide who tackles which fire.
INCA can be used as in the case of the door above. Each
character declares on which resources it wants to coordinate
(in this case, a set of fires). INCA automatically manages the
allocation of a specific resource among those available when
there are many resources and many users applying any desired The execution time of a single run of the reasoner increases
policy (e.g., the arrival order discussed above), no matter what with the increment of both the number of resources or the
a “resource” is engaged for. number of actors; in the first case the increment is linear, while
In our example, if “A” arrives first in the building, its in the second is exponential. This is due to the increasing num-
INCA will choose the first perceived fire. When “B” arrives, ber of possible combinations of the actors in the coordination
it perceives “A” engaged with one of the fires and thus, queue.
automatically, chooses the first non-engaged one. Once A is VII. F ROM DISJUNCTIVE LOGIC TO PROCEDURAL CODE
done with its chosen fire, it will restart coordination on the set
The implementation discussed in the previous sections has
of remaining fires, and so on until all fires are extinguished.
the great merit of enabling easy experimentation with different
VI. E VALUATION - SCALABILITY TEST policies. DLV is excellent at expressing constraints in a con-
We evaluate the scalability of the DLV coordination rea- densed way, easy to understand and to modify. Further, the data
soner, which is the active component of INCA, with respect to shown in the previous section demonstrate that, for practical
the execution time over two factors of complexity: the number purposes, the performance of the current implementation is
of actors and the number of resources. A fixed and simple acceptable at least with up to a few tens of characters. Still, it
policy has been adopted for all the tests. is not realistic to deploy such an architecture on state-of-the-art
1) Method of execution: The tests have been ran on a personal computers for use by a casual gamer.
machine equipped with an Intel(R) Core(TM) i7-5500U @ We are currently exploring techniques for (automatically or
2.4Ghz and 8GB of RAM. A KB is sistematically generated, semi-automatically) converting the queue engine and social
then the DLV process is ran 5 times, for each combination of norms implemented in DLV to a procedural form, suitable
the factors of complexity, and the execution times is measured. for implementation in Java or other common imperative
From the 5 measures, of the same combination, the higher and languages. Mimicking the current implementation, a non-
the lower are removed, then the remaining 3 are averaged. optimized procedure would consist of two major steps: com-
27
puting possible queue configurations and applying weights to without any need for either a central arbiter (to be avoided in
order them. MAS) or negotiation (also complex in MAS).
The queue engine, explained in Section III, computes all 4) Semantic negotiation: Garruzzo et al. in [14] propose a
possible combinations of actors in the queues, which represent method to form clusters of agents with similar characteristics,
alternative configurations to handle the coordination. Proce- or semantically homogeneous, based on semantic negotiation.
durally, the same can easily be obtained with nested loops or In comparison to our work it is worth noticing that we do not
recursion over the list of actors producing lists representing apply any explicit protocol; rather, an implicit group formation
queue configurations. happens by stating interest on a resource and performing
At this point INCA needs to apply a policy, a set of actions coherent with what is supposed to be a shared norm.
social norms, to select one among all the available con- IX. C ONCLUSION
figurations. Social norms are represented in INCA as DLV
weak constraints, which are weighted penalties assigned to In this paper, we proposed INCA, a distributed approach to
configurations given a matching criteria on the characteristics improve the coordination abilities of agent controlled NPCs.
of actors and their order in the configuration. The more INCA integrates social norms into autonomous agents with
a configuration is penalized, the more it is less likely to a meta-level architecture. This allows agents to implicitly
be the one to be chosen to handle the coordination. An coordinate by reasoning and following these social norms.
implementation in an imperative language should go through INCA also provides an environment of development and test
all the queue configurations computed in the previous step of these norms based on the DLV language. INCA can be
and apply all possible matching criteria, incrementing the therefore exploited to simulate people implicit coordination
configuration penalty score every time a match occurs. The mechanisms. An INCA supporting tool-set has been imple-
winning configuration is the one with the lowest penalty score. mented in PRESTO where, in order to evaluate its performance
in complex scenarios, we performed scalability tests. As future
The obvious but important fact to be stressed is that, while
work, we will work on the implementation of a version of
in DLV policies are easily represented as weak constraints and
INCA not dependent on DLV.
new policies can be added at any time, even dynamically (thus
supporting learning, for instance), ad-hoc code must be written R EFERENCES
for each new type of policy to be procedurally supported. [1] P. Busetta and M. Dragoni, “Composing Cognitive Agents from Be-
havioural Models in PRESTO,” in Proceedings of the 16th Workshop
VIII. R ELATED WORK ”From Objects to Agents” (WOA-2015), 2015.
[2] M. Dragoni, C. Ghidini, P. Busetta, M. Fruet, and M. Pedrotti, “Using
This section presents some research works about social Ontologies For Modeling Virtual Reality Scenarios,” in Proceedings of
ESWC 2015, 2015.
norms and the problem of coordination in Multi-Agent Sys- [3] P. Busetta, M. Fruet, P. Consolati, M. Dragoni, and C. Ghidini, “De-
tems (MASs). veloping an ontology for autonomous entities in a virtual reality: the
PRESTO experience,” in Proceedings of MESAS 2015 workshop, 2015.
1) Social norms and autonomous agents: Wooldridge in [4] P. Busetta, R. Rönnquist, A. Hodgson, and A. Lucas, “Jack intelligent
[8] defines social norms as an established expected pattern agents-components for intelligent agents in java,” AgentLink News
of behaviors, which can be exploited to define coordination Letter, vol. 2, no. 1, pp. 2–5, 1999.
[5] J. Tweedale, N. Ichalkaranje, C. Sioutis, B. Jarvis, A. Consoli, and
mechanisms between agents. Deliberative normative agents G. Phillips-Wren, “Innovations in multi-agent systems,” Journal of
are agents that have an explicit knowledge about the enacted Network and Computer Applications, vol. 30, no. 3, pp. 1089–1115,
norms in a multi-agent environment and can make a choice 2007.
[6] K. Konolige, “A Computational Theory of Belief Introspection,” in
whether to obey the norms or not[9]. Dignum et al. in [10] IJCAI, vol. 85, 1985, pp. 503–508.
propose enhancement of BDI architectures by incorporating [7] N. Leone, G. Pfeifer, W. Faber, T. Eiter, G. Gottlob, S. Perri, and F. Scar-
social norms, allowing a rich spectrum of social behaviors to cello, “The DLV system for knowledge representation and reasoning,”
ACM Trans. Comput. Logic, vol. 7, no. 3, pp. 499–562, 2006.
be described in a single framework. [8] M. Wooldridge, Introduction to MultiAgent Systems. Hoboken, NJ,
2) Coordination approaches in MAS: For Wooldridge in USA: Wiley, 2002.
[8] the coordination problem is that of managing inter- [9] C. Castelfranchi, F. Dignum, C. M. Jonker, and J. Treur, “Deliberate
Normative Agents: Principles and Architecture,” Intelligent Agents VI,
dependencies between the activities of agents.A basic ap- vol. LNAI 1757, pp. 364–378, 2000.
proach to coordinate multiple agents is to restrict their ac- [10] F. Dignum, D. Morley, E. Sonenberg, and L. Cavedon, “Towards so-
tivities in a way which enables them to achieve their goals cially sophisticated BDI agents,” in Proceedings of Fourth International
Conference on MultiAgent Systems, 2000, pp. 111–118.
while not interfering with other agents [11]. Coordination [11] Y. Shoham and M. Tennenholtz, “On social laws for artificial agent
can adopt implicit negotiation, where agents do not explicitly societies: off-line design,” Artificial Intelligence, vol. 73, pp. 231–252,
communicate, but negotiation is embedded in a pre-existing 1995.
[12] F. Scharpf, “Games Real Actors Could Play: Positive and Negative Co-
context [12]. ordination in Embedded Negotiations,” Journal of Theoretical Politics,
3) Coordination by social norms: Shoham et al. in [13] vol. 6, no. 1, pp. 27–53, 1994.
ask themselves why not adopt a convention, or, as we would [13] Y. Shoham and M. Tennenholtz, “On the synthesis of useful social laws
for artificial agent societies,” in AAAI-92 Proceedings, 1992.
like to think of it, a social law, according to which if each [14] S. Garruzzo and D. Rosaci, “Agent clustering based on semantic
agent obeys the convention, there will be avoided a lot of negotiation,” ACM Transactions on Autonomous and Adaptive Systems
interactions, creating an implicitly coordinated social behavior (TAAS), vol. 3, no. 2, p. 7, 2008.
28