=Paper= {{Paper |id=None |storemode=property |title=Autonomous Agents Coordination: Action Description Languages Meet CLP(FD) and Linda |pdfUrl=https://ceur-ws.org/Vol-598/paper03.pdf |volume=Vol-598 |dblpUrl=https://dblp.org/rec/conf/cilc/DovierFP10 }} ==Autonomous Agents Coordination: Action Description Languages Meet CLP(FD) and Linda== https://ceur-ws.org/Vol-598/paper03.pdf

Autonomous Agents Coordination:
Action Description Languages
meet CLP(F D) and Linda ⋆

Agostino Dovier1 , Andrea Formisano2 , and Enrico Pontelli3
1
Univ. di Udine, Dip. di Matematica e Informatica. agostino.dovier@uniud.it
2
Univ. di Perugia, Dip. di Matematica e Informatica. formis@dmi.unipg.it
3
New Mexico State University, Dept. Computer Science. epontell@cs.nmsu.edu

Abstract. The paper presents a knowledge representation formalism
for multi-agent systems, where diﬀerent autonomous agents reason and
act in a shared environment. Agents are autonomously pursuing indi-
vidual goals, but are capable of interacting through a shared knowl-
edge repository and collaborative actions. In their interaction through
shared portions of the world, agents deal with problems of synchroniza-
tion and concurrency, and have to realize coordination by developing
proper strategies and policies in order to ensure a consistent global exe-
cution of their autonomously derived plans.
To model this kind of knowledge, the paper proposes an high-level Action
Description Language (ADL). A distributed planning problem is formal-
ized by providing a number of declarative speciﬁcations of the portion of
the problem pertaining a single agent. Each of these speciﬁcations is ex-
ecutable by a stand-alone CLP-based planner. The coordination among
agents exploits a Linda-like infrastructure.
This is a working project and a concrete implementation of the system
is being developed in SICStus Prolog.

1 Introduction
Representing and reasoning in multi-agent domains are two of the most active
research areas in multi-agent system (MAS) research. The literature in this area
is extensive, and it provides a plethora of logics for representing and reasoning
about various aspects of MAS domains, e.g., [12, 8, 15, 13, 6].
A large number of the logics proposed in the literature have been designed
to speciﬁcally focus on particular aspects of the problem of modeling MAS,
often justiﬁed by a speciﬁc application scenario. This makes them suitable to
address speciﬁc subsets of the general features required to model real-world MAS
domains. The task of generalizing some of these existing proposals to create a
uniform and comprehensive framework for modeling several diﬀerent aspects of
MAS domains is an open problem. Although we do not dispute the possibility of
⋆
Research partially funded by projects GNCS-INdAM:Tecniche innovative per la programma-
zione con vincoli in applicazioni strategiche; MUR-PRIN:Innovative and multidisciplinary ap-
proaches for constraint and preference reasoning; Ricerca di base 2009–cod.2009.010.0336.
extending several of these existing proposals in various directions, the task does
not seem easy. Similarly, a variety of multi-agent programming platforms have
been proposed, mostly in the style of multi-agent programming languages, like
Jason [2], ConGolog [9], IMPACT [14], 3APL [11], GOAL [10], but with limited
planning capabilities.
Our eﬀort is on developing a knowledge representation formalism for multi-
agent systems, in the form of a high-level action language. The foundations
of this eﬀort can be found in the action language B M V [5]; this is a ﬂexi-
ble single-agent action language, generalizing the action language B [7], with
support for multi-valued ﬂuents, non-Markovian domains, and constraint-based
formulations—which enable, for example, the formulation of costs and prefer-
ences. B M V was implemented in CLP(FD). In this work, we propose to extend
B M V to support MAS scenarios. The perspective is that of a distributed environ-
ment, with agents pursuing individual goals but capable of interacting through
shared knowledge and through collaborative actions.
A ﬁrst step in this direction has been described in the B MAP language [4];
MAP
B provides a multi-agent action language with capabilities for centralized
planning. In this paper, we expand on this by moving B MAP towards a truly dis-
tributed multi-agent platform. The language is extended with C ommunication
primitives for modeling interactions among Autonomous Agents. We refer to
this language simply as B AAC . Diﬀerently from what described in [4], agents in
the framework proposed in this paper can have private goals and are capable of
developing independent plans. Agents’ plans are composed in a distributed fash-
ion, leading to replanning and/or introduction of coordination actions to enable
a consistent global execution.
A ﬁrst prototype of the resulting framework is being implemented, using
CLP(FD) for the development of the individual plans of each agent, and Linda
for the coordination and interaction among them.

2 Syntax of the Multiagent Language BAAC

The signature of B AAC consists of a set G of agent names, used to identify the
agents of the system, a set F of ﬂuent names,1 a set A of action names, and a set
V of values for the ﬂuents in F. We assume V = Z. The behavior of each agent a
is speciﬁed by means of an action description theory Da , namely a collection of
axioms of the forms described in what follows.
Considering the action theory Da of an agent a, name and priority of the
agent are speciﬁed by agent declarations:

agent a [ priority n ]. (1)

where n ∈ N. We adopt the convention that 0 denotes the highest priority, which
is also the default value, in absence of the priority declaration. As we will see,
1
Intuitively, a ﬂuent expresses a property of an object in a world, and forms part of
the description of states of the world. Such properties might be aﬀected by actions.

2
priorities might be used to resolve possible conﬂicts among actions of diﬀerent
agents.
It is possible to specify which agents are known to agent a, as follows:

known agents a1 , a2 , . . . , ak . (2)

Consequently, agent a is able to explicitly query one of the ai s to start a com-
munication phase (see below).
We assume the existence of a unique “global” set F of ﬂuents, and any given
agent a knows and can access only those ﬂuents that are declared in Da by
axioms of the form (we refer to these ﬂuents as the “local state” of the agent):

fluent f1 , . . . , fh valued dom i . (3)

with fi ∈ F, h ≥ 1, and domi ⊂ V is a set of values representing the admissible
values for each fi (possibly represented as an interval [v1 , v2 ] if this is the case).
Fluents are used in Fluent Expressions (FE), which are deﬁned as follows:

FE ::= n | f t | f @r | FE1 ⊕ FE2 | − (FE) | abs(FE) | rei(C) (4)

where n ∈ V, f ∈ F, t ∈ {0, −1, −2, −3, . . . }, ⊕ ∈ {+, −, ∗, /, mod}, and r ∈ N.
FE is said a timeless expression if it contains no occurrences of f t with t ̸= 0 and
no occurrences of f @r. f can be used as a shorthand of f 0 .
The notation f t is an annotated ﬂuent expression. The expression refers
to a relative time reference, indicating the value f had −t steps in the past.
An expression of the form f @r denotes the value f has at the rth step in the
evolution of the world (i.e., it refers to an absolutely speciﬁed point in time). The
last alternative in (4), a reiﬁed expression, requires the notion of constraint C.
The semantics of rei(C) is a Boolean value depending on the truth of C.
A Primitive Constraint (PC) is formula FE1 op FE2 , where FE1 and FE2 are
ﬂuent expressions, and op ∈ {=, ̸=, ≥, ≤, >, <}. A constraint C is a propositional
combination of PCs. As a syntactic sugar, with f ++ we denote the primitive
constraint f = f −1 + 1 and with f -- the primitive constraint f = f −1 − 1.
An axiom of the form action x in Da , declares that the action x ∈ A
is executable by the agent a.2 A special action, nop (no operation) is always
executable by every agent. It has no eﬀect on ﬂuents’ values. Executability of
actions is ruled by axioms of the form

executable x if C. (5)

where x ∈ A and C is a constraint, stating that C has to be entailed by the current
state for x to be executable. We assume that at least one executability axiom
is present for each action x. If there are multiple executability axioms, then the
2
Observe that the same action name x can be used for diﬀerent actions executable
by diﬀerent agents. This does not cause ambiguity, because each agent knowledge is
described by its own action theory.

3
conditions are considered in disjunction. The eﬀects of an action execution are
modeled through axioms (dynamic causal laws) of the form

x causes Eﬀ if Prec. (6)

where x ∈ A, Prec is a constraint, and Eﬀ is a conjunction of primitive con-
straints of the form f = FE, for f ∈ F, and FE is a ﬂuent expression. The axiom
asserts that if Prec is true with respect to the current state, then Eﬀ must hold
after the execution of x.
Since agents share ﬂuents, their actions may interfere and cause inconsis-
tencies. A conﬂict happens when the eﬀects of diﬀerent concurrent actions are
incompatible and would lead to an inconsistent state. A suitable procedure has
to be applied to resolve a conﬂict and determine a consistent subset of the con-
ﬂicting actions (see also Sect. 3.3). At least two perspectives can be followed, by
assigning either a passive or an active role to the conﬂicting agents, during the
conﬂict resolution phase. In the ﬁrst case, a further actor is in charge of resolv-
ing the conﬂict, and all agents will adhere to its decision. Alternatively, agents
themselves are in charge of reaching an agreement, possibly through negotiation.
In case such last possibility is adopted, the following options allow one to specify
in the action theories some basic reaction policies the agents might apply.

action x OP T. (7)

where
OP T ::= on conflict OC OP T
| on failure OF OP T
OC ::= retry after T [provided C]
| forego [provided C]
| arbitration
OF ::= retry after T [if C]
| replan [if C] [add goal C]
| fail [if C]
Notice that in the same axiom one can specify policies to be adopted whenever
a failure occurs in executing an action.
We remark here the diﬀerence between conﬂict and failure. The former, as
mentioned above, occurs during the transition from a state to another, because of
incoherent eﬀects of concomitant actions. A failure occurs whenever an action x
cannot be executed as planned by an agent a. (This might happen, for instance,
because after the detection of a conﬂict involving x, the outcome of the conﬂict
resolution phase requires x to be inhibited.) In this case the agent a might have
to reconsider its plan. Hence reacting to a failure is a “local” activity the agent
might perform after the state transition has been completed. In axioms of the
form (7), one can specify diﬀerent reactions to a conﬂict (resp. a failure) of the
same action. Alternatives will be considered in their order of appearance.
The following example illustrates some speciﬁc cases of (7).
Example 1. Let us assume that the agents a and b have priority 0, while agent
c has priority 2. Let us assume, moreover, that the current state is such that

4
actions act a, act b, and act c are all executable (respectively, by agents a, b,
and c), where their eﬀects on ﬂuent f are of setting it to 1, 2, and 3, respectively.
Assume that the following options have been deﬁned:
action act a on conflict retry after 2
action act b on conflict forego
action act c on failure retry after 3
and that the plan of agent a (resp., b, c) requires the execution of action act a
(resp., act b, act c) in the current state. Of course there is a conﬂict: the eﬀects
of concomitant execution of the three actions are incostintent. One possible
conﬂict resolution procedure is that of focusing on higher priority agents. In the
example at hand, this causes action act c to be removed from execution list.
Therefore agent c fails in executing its action and will react retrying to execute
the same action after 3 steps.
Some policy must be now chosen to resolve the conﬂict between a and b. The ﬁrst
possibility is that agents have passive roles in conﬂict resolution, and a referee
selects, according to some criteria, a (possibly maximal) consistent subset of the
actions/agents. Assume a is selected (by simple lexicographical criteria)—then,
it can set f = 1 and succeed, while b will get a failure message.
An alternative policy consists in not involving any referee and in making a
and b in charge for resolving the conﬂict. In such a case, they will apply their
on conflict options. This causes a to retry the execution after 2 steps and b to
forego. Both of them will get a failure message, because neither act a nor act b
are executed.
Apart from possible communication occurring among agents during the con-
ﬂict resolution phase, other forms of “planned” communication can be modeled
in an action theory. An axiom of this form
request C1 if C2 .
implicitly describes an action that allows an agent to broadcast a request to other
agents. The action is executable if the precondition C2 holds. By executing this
action, an agents asks if there is another agent that can make the constraint C1
true. Only an agent knowing all the ﬂuents occurring in C1 is allowed to answer
to the request.
Instead of broadcasting an help request, an agent a can send such a message
directly to another agent by providing its name:3
request C1 to agent a′ if C2 .
The following construct speciﬁes a form of communication primitive that
subsumes the previous ones:
request C1 [ to agent a′ ] if C2 [ offering C3 ]. (8)
If the last option is used, the requesting agent also provides a “reward” by
promising to ensure C3 in case of acceptance of the proposal. Axioms of these
types allow one to model bargains and transactions. Here is an example.
3
Any request sent to a nonexistent agent will never receive an answer.

5
agent guitar maker. action make guitar.
executable make guitar if neck > 0 and strings >= 6 and
body > 0 and pickup > 0.
% actions for making two different kinds of guitars:
make guitar causes guitars++ and neck-- and body-- and
strings = strings−1 − 6 and pickup = pickup−1 − 2
if pickup >= 2.
make guitar causes guitars++ and neck-- and strings = strings−1 − 6 and
body-- and pickup-- if pickup < 2.
% interaction with joiner:
request neck > 0 to agent joiner if neck = 0.
request body > 0 to agent joiner if body = 0.
% interaction with seller:
request strings > 5 to agent seller if strings < 6
offering seller account = seller account−1 + 8.
request pickup > 0 to agent seller if pickup = 0
offering seller account = seller account−1 + 60.
% the goal is to make 10 guitars:
goal guitars = 10.
% initially the maker owns some material:
initially guitars = 2 and body = 3 and
neck = 5 and pickup = 6 and strings = 24.

Fig. 1. An action description in BAAC for a guitar maker agent

Example 2. Consider a situation where three agents exist: a guitar maker, a
joiner that provides wooden parts of guitars (bodies and necks), and a seller
that sells strings and pickups. For simplicity, we assume that the maker has
plenty of money (so we do not take into account what he spends), that the
seller wants to be paid for his materials, and that necks and bodies can be
obtained for free (e.g., the joiner has a ﬁxed salary paid by the maker). The
money income of the seller is modeled by changes in the value of the ﬂuent
seller account. In Fig. 1 we report an action description theory that models
the agent guitar maker (analogous theories can be formulated for the other two
agents). Observe that two point-to-point interactions are modeled—namely, the
one between the guitar maker and the joiner, to obtain necks and bodies, and
the one between the guitar maker and the seller, to buy strings and pickups.
Two kind of guitars can be made, diﬀering in the number of pickups.

We can inherit from [5] the capability of dealing with static causal laws and
with cost constraints for actions and plans. Moreover, it is possible to allow
ﬂuent references of the form f t = FE, with t > 0 (a future value for the ﬂuent f
is “booked”). For simplicity, we do not consider these features in this paper.
An action domain description consists of a collection Da of axioms of the
forms described so far, for each agent a ∈ G. Moreover it includes, for each agent

6
a, a collection Oa of goal axioms (objectives), of the form
goal C.
where C is a constraint; and a collection Ia of initial state axioms of the form:
initially C.
where C is a constraint involving only timeless expressions. For simplicity, we
assume all the collections Ia as drawn from a consistent global initial state
description I, i.e., Ia ⊆ I. A
⟨ speciﬁc instance of a ⟩ planning problem is a triple
∧ ∧ ∧
Da , Ia , Oa
a∈G ∧ a∈G a∈G
The problem has a solution only if a∈G Oa characterizes a consistent state.

3 Semantics

The semantics of B AAC can be split into two parts: the semantics of the action
description languages used locally by each agent, that do not consider the axioms
(7) and (8), and the semantics of the overall system that deals with agents’
interactions. Let us assume that there is an overall time limit N, within which
the planning activities of all agents have to be completed.

3.1 Local semantics

As far as the local view is concerned, following [7], the semantics is given in
terms of transition systems. Nodes (states) of the transition systems are uniquely
characterized by assigning a value to each ﬂuent. Two states u, v are linked if and
only if there is an action applicable to u and leading to v. The formal semantics
of the language B M V , upon which BAAC is deﬁned, is given in detail in [5].
A plan of an agent is a sequence of states s0 , . . . , sN such that si , si+1 are
linked in the transition system. Evaluation of a ﬂuent expression f t in a state
is the value of the ﬂuent in state si+t . Evaluation of a ﬂuent expression f @i is
the value of the ﬂuent in state si . Evaluation of a constraint in a state si can be
inductively deﬁned in the natural way.
Each agent a looks for a sequence of states s0 , . . . , sk , with s0 determined by
Ia and k ≤ N such that Oa are all satisﬁed in state k. As soon as the goal for
agent a is satisﬁed, the agent succeeds and “exits” the system. In practice, we
might assume that it always executes nop from time k + 1 to time N. Observe,
that the length of each agent’s local-plan might change as steps are executed,
because of the replanning phases the agent may perform, as a consequence of
failures. Observe, moreover, that it suﬃces for the agent to reach the goal within
N steps, i.e., its goal should hold at a time k ≤ N, but it does not need to hold
at time k + 1.
A remark here is needed on actions of the form request C1 if C2 in Da .
The constraint C2 is evaluated by the agent a in the state si . If C2 holds then
a is allowed to send a request for help in achieving C1 (see details in Sect. 3.3).
Let us focus here on the evaluation of the constraint C1 . If in a future instant,

7
say j > i, some other agent b accepts to fulﬁll the required condition, then b
guarantees the satisﬁability of C1 , as evaluated with respect to the j-th state
sj . Thus, ﬂuents of the form f t with t < 0, that are allowed in C1 , have to be
considered by agent b w.r.t. the j-th state.

3.2 Concurrent plan execution
Agents are autonomous and develop their activities independently, except for the
execution of the actions/plans. In executing their plans, the agents must take
into account the eﬀects of concurrent actions. A basic communication mechanism
among agents is realized by exploiting a tuple space, and the accesses to the tuple
space occur through Linda-like primitives [3]. Moreover, most of the interactions
among concurrent agents (especially those aimed at resolving conﬂicts) are ruled
by a speciﬁc process, a supervisor, that also provides a global timing for all agents
enabling them to execute their actions synchronously.
More in general, the supervisor process stores the initial state and the changes
caused by the successful executions of actions. It synchronizes the action exe-
cutions and controls the coordination and the arbitration in case of conﬂicts. It
also sends a success or a failure signal to each agent at each action execution
attempt, together with the list of changes to its local state.
Let us describe how the execution of concurrent plans proceeds. As men-
tioned, each action description includes a collection of constraints describing a
portion of the initial state.

Supervisor process
∪
• At the very beginning the supervisor acquires the speciﬁcation I = a∈G Ia
of the initial state.
• At each time step the supervisor starts a new state transition:
– Each active agent sends to the supervisor a request to perform an action
(typically, next action of its locally computed plan), by specifying its
eﬀects on the (local) state.
– The supervisor collects all these requests and starts an analysis, aimed at
determining those subsets of actions/agents that conﬂicts (if any). There
is a conﬂict whenever agents require incompatible assignments of values
to ﬂuents. The transition takes place once all conﬂicts have been resolved
and a sub-collection of compatible actions has been identiﬁed by means
of some ﬁxed policy (see below). These actions are enabled while the
remaining ones are inhibited.
– Enabled actions are executed. This changes the current (global) state.
– These changes are then sent back to all agents to make them update
their local states. All agents are also notiﬁed about the outcome of the
procedure. In particular, those agents requiring an inhibited action receive
a failure message.
• The computation stops when time N is reached.
Notice that after each step of the local plan execution, each agent needs to check
if the reached state still supports its subsequent planned actions. If not, the

8
agent has to reason locally and revise its plan (replan phase). The replanning is
due to the fact that the reached state might be diﬀerent from the expected one.
This may occur in two cases:
1. The proposed action was inhibited, so the agent actually executed a nop (in
this case it has received a failure notice from the supervisor).
2. Its interaction was successful, i.e., the planned action was executed, but the
eﬀects of actions of other agents aﬀected ﬂuents in its local state—for instance,
an agent a assumed that ﬂuent g held its value by inertia, but another agent
b changed such value. There is no direct conﬂict between the actions of a and
b, but agent a has to verify that the rest of its plan is still applicable (e.g.,
the next action in a’s plan may have lost its executability condition).

3.3 Conflicts resolution
A conﬂict resolution procedure is invoked by the supervisor whenever it deter-
mines a subset of incompatible actions.
Diﬀerent policies can be adopted in this phase and diﬀerent roles can be
played by the supervisor. First of all, the supervisor exploits priorities of agents
to attempt a solution of the conﬂict, by inhibiting actions of lower priority agents.
If this does not suﬃce, further options are applied. We describe here some of the
easiest viable possibilities, that we have already implemented in our prototype.
The architecture of the system is highly modular (cf. Sect. 3.6), and it can be
easily extended by adding more complex policies and protocols.
The two approaches we implemented so far, diﬀer by assigning the active role
either to the supervisor or to the conﬂicting agents, in resolving the conﬂict.
1. The supervisor has the active role—it acts as a referee and decides, without
any further interaction with the agents, which actions have to be inhibited.
In the current prototype, the arbitration strategy is limited to
– a random selection of a single action to be executed; or
– the computation of a maximal set of compatible actions to be executed.
This computation is done by solving a CSP (by generating at run-time a
suitable CLP(FD) encoding).
Note that, in this strategy, on conflict policies assigned to actions by ax-
ioms (7) are ignored.
Such a centralized way of resolving the conﬂicts might represent a critical
point of the system, since all conﬂicting agents must wait for supervisor’s
decision. We describe, in what follows, a second approach that reduces such
a dependence between agents and supervisor.
2. The supervisor just notiﬁes the set of conﬂicting agents about the joint incon-
sistency of their actions. The set of agents involved in the conﬂict is completely
in charge for resolving it by means of a negotiation phase. The supervisor waits
for a solution from the agents.
In solving the conﬂict each agent a makes use of one of the on conflict
directives (7) speciﬁed for its conﬂicting action x. The semantics of these
directives are as follows (in all the cases [provided C] is an optional qualiﬁer;
if it is omitted it is interpreted as provided true):

9
• The option on conflict arbitration causes the explicit invocation of the
supervisor which performs an arbitration phase (involving all the conﬂicting
agents) to resolve the conﬂict, as previously described.
• The option on conflict forego provided C causes the agent a to “search”
among the other conﬂicting agent for someone, say b, that can guarantee
the condition C. In this case, b performs its action while the execution of a’s
action fails (in other words we could say that a executes a nop in place of its
action). Diﬀerent strategies can be implemented in order to perform such a
“search for help”. A simple one is the round-robin policy described below,
but, clearly, many other alternatives are possible and should be considered
in completing the prototype.
• Similarly, the option on conflict retry after T provided C, diﬀers
from the preceding one because a will execute nop during the following
T time steps and then will try again to execute its action (provided that
the preconditions of the action still hold).
• If there is no applicable option (e.g., no option is deﬁned or none of the
agents accept to, or is able to, guarantee C), the action is inhibited and its
execution fails.
Also the manner in which agents negotiate and exploit the on conflict op-
tions can rely on several policies an protocols, of diﬀerent complexity. For
instance, one possibility moght be the election of a “leader” within each of
the conﬂicting set S of agents. This agent is then in charge for coordinating
the agents in S so to resolve the conﬂict without interacting with the supervi-
sor; another possibility would consist in not identifying a privileged agent and
in leaving each agent of S free to proceed and to ﬁnd an agreement by sending
proposals to other agents (possibly by adopting some order of execution, some
priorities, etc.) and receiving theis proposals/answers. In the current proto-
type we implemented a round-robin policy. Such a rather rigid policy is just
a simple example of how to realize an alwais terminating protocol for conﬂict
resolution. Diﬀerent solutions can be easily added to the prototype thanks
to its modularity. The round-robin policy proceeds as follows. Let us assume
that the agents a1 , . . . , am aim at executing actions z1 , . . . , zm , respectively,
and these actions are conﬂicting. The agents are sorted by the supervisor, and
they take turn in resolving the conﬂict. Suppose that at a certain round j of
the procedure the agent ai is selected. It determines the j-th option for its
action and tries to apply it. If the option is directly applicable or an agree-
ment is reached with another agent on a condition C, then the two agents exit
the procedure. If no arbitration is invoked the remaining agents complete the
procedure. If the option does not yield success (e.g., the agents do not agree),
then the next agent in the sequence will start its active role in the round,
while ai waits its next turn in round j + 1.
Notice that this procedure always ends with a solution to the conﬂict, since
a ﬁnite number of on conflict options are deﬁned for each action.

Once all conﬂicts have been addressed, the supervisor applies the enabled ac-
tions, and obtains the new global state. Each agent receives a communication

10
containing the outcome of its action execution and the changes to its local state.4
Moreover, further information might be sent to participating agents, depending
on the outcome of the coordination procedure. For instance, when two agents
agree on an on conflict option, they “promise” to execute speciﬁc actions (e.g.,
the fact that one agent has to execute T consequent nop, etc.). This information
has to be sent back to the interested agents to guide their replanning phases.

3.4 Failure policies

Agents receive a failure message from the supervisor whenever their requested
actions have been inhibited. In such case, the original plan of the agent has to
be revised to detect if the local goal can still be reached, possibly by replanning.
Also in this case diﬀerent approaches can be applied. For instance, one agent
could avoid developing an entire plan at each step, but limit itself to produce
a partial plan for the very next step. Alternatively, an agent could attempt to
determine the “minimal” modiﬁcations to the existing plan in order to make it
valid with respect to the new encountered state.5
In this replanning phase, the agent might exploit the on failure options
corresponding to the inhibited action. The intuitive semantics of these options
can be described as follows.
• retry after T [if C]: the agent ﬁrst evaluates the constraint C; if C holds,
then it executes T times the action nop and then tries again the failed action
(provided that its executability and its preconditions still hold).
• replan [if C1 ] [add goal C2 ]: the agent ﬁrst evaluates C1 ; if it holds,
then in the following replanning phase the goal C2 is added to the current
local goal. The option add goal C2 is optional; if it is not present then nothing
is added to the goal, i.e., it is the same as add goal true.
• fail [if C1 ]: this is analogous to replan [if C1 ] add goal false. In this
case the agent declares that it is impossible to reach its goal. It quits and does
not participate to the subsequent steps of the concurrent plan execution.
• If none of the above options is applicable, then the agent will proceed as if
the option replan if true is present.
All the options declared for the inhibited action are considered in the given order,
executing the ﬁrst applicable one.

3.5 Broadcasting and direct requests

Let us describe a simple protocol for implementing point-to-point and broadcast
communication between agents following an explicit request of the form (8).
In particular, let us assume that the current state is the i-th one of the plan
execution—hence, the supervisor is coordinating the transition to the i + 1-th
4
Actually, the supervisor might provide some other information that might be useful
for the agent. For instance, it detects if the eﬀects of an action has been subsumed
by other executed actions.
5
At this time, the prototype includes only replanning from scratch at each step.

11
state by executing the i+1-th action of each local plan. The handling of requests
is interleaved with the agent-supervisor interactions that realize plan execution—
though, the supervisor does not intervene on it and the requests and oﬀers are
directly exchanged among agents. We can sketch the main steps involved in a
state transition, from the point of view of an agent a, as follows:

(1) The agent a tries to execute its action and sends this information to the
supervisor (as explained in Sect. 3.2).
(2) Possibly after a coordination phase, a receives from the supervisor the out-
come of its attempt to execute the action (namely, failure or success, the
changes in the state, etc.)
(3) If the action execution succeeded, before declaring accomplished the cur-
rent transition, a starts an interaction with other agents to handle pending
requests. During such interaction, the communication among agents relies
on the Linda tuple-space (requests and oﬀers are posted and retrieved by
agents).
(3.a) Agent a fetches the collection H of all the requests still pending and
emitted until step i. For each request h ∈ H, a decides whether to accept
the request for help from the agent b that sent the request h. Such a decision
might involve exploitation of the planning facilities, in order to determine
if the requested condition can be achieved by a, possibly by modifying its
original plan. In the positive case, a posts its oﬀer into the tuple-space and
waits for a rendezvous with b.
(3.b) Agent a checks whether there are answers to the requests it previously
posted. For each request for which there are answers, a collects the set
of oﬀers/agents that expressed their willingness to help a. By using some
strategy, a selects one of the responding agents, say b. The policy for choos-
ing the responding agent can be programmed (e.g., by exploiting priorities,
agent’s knowledge on other agents, random selection, trust criteria, utility
and optimality considerations, etc.). Once the choice has been made, a
establishes a rendezvous with each responding agent and (a) declares its
availability to b, (b) communicates the fulﬁllment of the request to the
other agents. The request is also removed from the tuple space, along with
all the obsolete oﬀers.
(4) The transition can then be considered completed for the agent a. By taking
into account the information about the outcome of the coordination phase
in solving conﬂicts (point (2)), the agreement reached in handling requests
(point (3)), a might need to modify its plan. If the replanning phase succeeds,
then a will proceed with the execution of the next action in its local plan.

Note that we provided separated descriptions for steps (3.a) and (3.b). In a
concrete implementation, these two steps have to be executed in an interleaved
manner, to avoid that a ﬁxed order in sending requests and oﬀers causes dead-
locks or starvation.

12
3.6 Implementation issues

A ﬁrst prototype of the system has been implemented in SICStus Prolog, us-
ing the libraries clpfd for agents reasoning (by exploiting the interpreter for
Action Description Languages described in [5]), system, linda/server, and
linda/client for handling process communication. A server process is launched,
generating the connection address that must be used by the client processes. This
piece of information is stored in a text ﬁle, where a launching script (runner,
available for both Linux and Windows) can also ﬁnd the number of agents and
the bound N on the maximum number of steps.
The system is structured in modules. Fig. 2 displays the modules composing
the Prolog prototype and their dependencies. As far as the reasoning/planning
module is concerned, we slightly modiﬁed the interpreter of [5] to accept the new
syntax presented here (module sicsplan in Fig. 2). The modules spaceServer
(through lindaServer) and lindaClient implement the interfaces with the
Linda tuple-space. These modules support all the communications among agents.
Each autonomous agent corresponds to an instance of the module plan executor,
which in turn relies on sicsplan for planning/replanning activities, and on
client for interacting with other actors in the system. As previously explained,
a large part of the coordination is guided by the module supervisor. Notice that
both the supervisor and clients act as linda-clients. Conﬂict resolution func-
tionalities are provided to the modules clients and supervisor by the modules
ConflictSolver client and ConflictSolver super, respectively. Finally, the
arbitration opt module implements the arbitration protocol(s).
Let us remark that all the policies exploited in coordination, arbitration,
and conﬂict handling can be customized by simply providing a diﬀerent imple-
mentation of individual predicates exported by the corresponding modules. For
instance, to implement a conﬂict resolution strategy diﬀerent from the round-
robin described earlier, it suﬃces to add to the system a new implementation
of the module ConflictSolver super (and for ConflictSolver client, if the
speciﬁc strategy requires an active role of the conﬂicting agents). Similar exten-
sions can be done for arbitration opt.

4 Conclusions and future work

In this paper, we illustrate a preliminary design of an high-level action descrip-
tion language for the description of multi-agent domains. The language enables
the description of agents with individual goals operating in a shared environ-
ments. The agents can explicitly interact (by requesting help from other agents
in achieving their own goals) and implicitly cooperate in resolving conﬂicts that
may arise during execution of their individual plans. The main features of the
framework we described in this paper have been realized into an implementa-
tion, based on SICStus Prolog. The implementation is fully distributed, and uses
Linda to enable communication among agents. Such a prototype is currenlty be-
ing reﬁned and extended with further features.

13
settings runner plan executor

client supervisor

ConflictSolver client ConflictSolver super

spaceServer sicsplan arbitration opt

linda/server linda/client clpfd

Fig. 2. The dependencies between modules in the system. The modules’ names recall
the corresponding Prolog-ﬁles names. The module runner is the starter of the appli-
cation. The module settings speciﬁes user options (policies, strategies, etc.) and the
sources ﬁles containing the action descriptions, it is imported by all the others (we
omitted drawing the corresponding arcs, as well as the nodes relative to less relevant
SICStus libraries).

The work is preliminary but already shows strong potential and several av-
enues of research. The immediate goal in the improvement of the system consists
in adding reﬁned strategies and coordination mechanisms, involving for instance,
payoﬀ, trust, etc. Then, we intend to evaluate the performance and quality of
the system in several multi-agent domains (e.g., game playing scenarios, mod-
eling of auctions, and other domains requiring distributed planning). We also
plan to investigate strategies to enhance performance by exploiting features pro-
vided by the constraint solving libraries of SICStus (e.g., the use of the table
constraint [1]).
We will investigate the use of future references in the ﬂuent constraints (as
supported in B M V )—we believe this feature may provide a more elegant ap-
proach to handle the requests among agents, and it is necessary to enable the
expression of complex interactions among agents (e.g., to model forms of nego-
tiation with temporal references).
We will also explore the implementation of diﬀerent strategies associated
to conﬂict resolution; in particular, we are interested in investigating how to
capture the notion of “trust” among agents, as a dynamic property that changes
depending on how reliable agents have been in providing services to other agents
(e.g., accepting to provide a property but failing to make it happen).
Also concerning trust evaluation, diﬀerent approaches can be integrated in
the system. For instance, a “controlling entity” (e.g., either the supervisor or a
privileged/elected agent) could be in charge for assigning the “degree of trust”
of each agents. Alternatively, each single agent could develop its own opinion
on other agents’ reliability, depending on the behaviour they manifested in past

14
interactions. Finally, work is needed to expand the framework to enable greater
ﬂexibility in several aspects, such as:
• in handling deadlines for requests—e.g., by allowing axioms of the form
request C1 if C2 until T
indicating that the request is valid only if accomplished within T time steps.
• in admitting dynamic changes in the knowledge the agents have on other
agents (e.g., an action might make an agent aware of the existance of other
agents; so, modifying the knowledge speciﬁed by axioms (2)), or on the world
(e.g., an action might change the rights another agent has to access/modify
some ﬂuents; so, modifying the knowledge speciﬁed by axioms (3)).

References
[1] R. Barták and D. Toropila. Reformulating constraint models for classical planning.
In D. Wilson and H. C. Lane, editors, FLAIRS’08: Twenty-First International
Florida Artificial Intelligence Research Society Conference, pages 525–530. AAAI
Press, 2008.
[2] R. Bordini, J. Hübner, and M. Wooldridge. Programming Multi-agent Systems in
AgentSpeak using Jason. J. Wiley and Sons, 2007.
[3] N. Carriero and D. Gelernter. Linda in context. Communications of the ACM,
32(4):444–458, 1989.
[4] A. Dovier, A. Formisano, and E. Pontelli. Representing Multi-Agent Planning in
CLP. In E. Erdem, F. Lin, and T. Schaub, editors, LPNMR 2009, volume 5753
of LNCS, pages 423–429. Springer, 2009.
[5] A. Dovier, A. Formisano, and E. Pontelli. Multivalued action languages with
constraints in CLP(FD). Theory and Practice of Logic Programming, 10(2):167–
235, 2010.
[6] R. Fagin, J. Halpern, Y. Moses, and M. Vardi. Reasoning about knowledge. The
MIT Press, 1995.
[7] M. Gelfond and V. Lifschitz. Action languages. Electronic Transactions on Arti-
ficial Intelligence, 2:193–210, 1998.
[8] J. Gerbrandy. Logics of propositional control. In AAMAS, pages 193–200, 2006.
[9] G. D. Giacomo, Y. Lespèrance, and H. Levesque. ConGolog, a concurrent pro-
gramming language based on the situation calculus. Artificial Intelligence, 121(1–
2), 2000.
[10] K. Hindriks and T. Roberti. GOAL as a Planning Formalism. In MATES, 2009.
[11] J. M. M. Dastani, F. Dignum. 3APL: A Programming Language for Cognitive
Agents. ERCIM News, European Research Consortium for Informatics and Math-
ematics, 53, 2003.
[12] L. Sauro, J. Gerbrandy, W. van der Hoek, and M. Wooldridge. Reasoning about
Action and Cooperation. In H. Nakashima, M. P. Wellman, G. Weiss, and P. Stone,
editors, AAMAS’06: Proceedings of the 5th International Joint Conference on Au-
tonomous Agents and Multiagent Systems, pages 185–192. ACM, 2006.
[13] M. Spaan, G. Gordon, and N. Vlassis. Decentralized planning under uncertainty
for teams of communicating agents. In AAMAS, pages 249–256, 2006.
[14] V. Subrahmanian, P. Bonatti, J. Dix, T. Eiter, S. Kraus, F. Ozcan, and R. Ross.
Heterogeneous Agent Systems: Theory and Implementation. The MIT Press, 2000.
[15] W. van der Hoek, W. Jamroga, and M. Wooldridge. A logic for strategic reasoning.
In AAMAS, pages 157–164, 2005.