We describe a Multiagent Planning approach, named Social Continual Planning, that tackles open scenarios, where agents can join and leave the system dynamically. The planning task is not defined from a global point of view, setting a global objective, but we allow each agent to pursue its own subset of goals. We take a social perspective where, although each agent has its own planning task and planning algorithm, it needs to get engaged with others for accomplishing its own goals. Cooperation is not forced but, thanks to the abstraction of social commitment stems from the needs of the agents.
The ability to plan one’s own activities, even in dynamic and challenging scenarios such as Multiagent Systems (MAS), represents a key feature in many real-world applicative domains (see e.g., logistics, air traffic control, rescue missions, and so on). Not surprisingly, planning in MAS is drawing the attention of an ever growing number of researchers, as witnessed by the new series of Distributed and Multi-Agent Planning Workshops hosted by ICAPS.
The term Multiagent Planning (MAP) refers to a planning task in which a set of
planning agents, each equipped with its own tools and capabilities, has to synthesize a
joint solution (i.e., a joint multiagent plan). The planning task usually involves a number
of interdependent subgoals, so that some form of coordination among the agents is
necessary to solve the problem. Different methodologies have been proposed in the
literature. Besides centralized approaches (e.g., [
In all the above approaches, the planning task defines a global objective to be achieved by means of a “joint solution” involving the capabilities of the agents. Moreover, the set of agents to be involved is known in advance and cannot change during the planning process; the system is therefore closed. In this paper we deal with a different planning problem, and propose a methodology named Social Continual Planning (SCP), to tackle it. We consider the planning problem of an agent situated in an open multiagent system. The agent may resort on other agents for solving a task of its own interest. The agent plans both its own actions, and its interactions with others whenever it is not capable, or it deems as not convenient, to execute certain steps in autonomy. The focus is not on negotiation, but on the framework through which an agent seeks the help by the others, and on the engagements that bind agents to supporting each other. Interaction is not limited to communication but it is a process through which the involved agents progress each in the solution of its own task. Engagements are binary social relationships, that are established dynamically and that create expectations on the involved agents behavior. An agent autonomously decides (plans) when to bind to another one to do something.
More precisely, we take a social perspective in the sense that, even though each
agent has its own planning task and uses its own planning algorithm, the agent has
still to get engaged with others in order to accomplish its own goals. The interactions
that an agent has with others will, in general, allow both parties to get closer to their
own goals. Cooperation is not forced to the agents just because they are part of the
system, but rather cooperation stems from the needs of the agents within the system,
and endures as far as the parties take advantage of it. In other terms, we propose a form
of (agent) planning which is situated in a multiagent system, where an agent not only
has to plan its own actions, but has also to plan its social relationships with other agents.
Since the coordination has to be planned, it must be supported by a proper abstraction
that enables one agent to create expectations about the behaviors of others. To this end,
in this paper we adopt social commitments [
The paper is organized as follows. Section 2 overviews the most relevant literature. Section 3 introduces the necessary background. Section 4 explains our proposal. Section 5 describes the implementation, and exemplify the approach in the logistic scenario. Conclusions and a discussion end the paper. 2
To the best of our knowledge, the SCP problem has not been tackled in the literature,
so far. It is, however, worthwhile to report the main approaches that are currently
discussed in multiagent and distributed planning. Since the seminal work by Boutilier et
al. [
More recently, distributed approaches have emerged within the planning
community. However, even though the planning search can be distributed among the agents,
the definition of the planning task is still centralized in most of them. See for instance
the MA-STRIPS formalization [
Distributed approaches can be distinguished on how the planning and coordination
phases are actually carried on. First attempts to coordinating plan after the planning
phases [
This drawback is overcome by approaches (see e.g., [
For what concerns commitments, only recently there have been some attempts to
integrate them in planning problems, see [
The proposal presented in this paper strongly relies on social commitments (simply
commitments below), as first introduced in [
Commitments have a life cycle, and we adopt the one proposed in [
Commitments are manipulated by commitment operations such as: create (an agent creates a commitment toward someone), cancel (a debtor withdraws an own commitment), release (an agent withdraws a commitment of which it is the creditor), assign (a new creditor is specified by the previous one), delegate (a new debtor is specified by the previous one), discharge (the commitment is resolved). In particular, when the consequent condition u holds, the commitment is discharged. Notably, only an agent playing the role of debtor can create a commitment.
The reason for relying on commitments stems by the fact that commitments have
a normative power: Since debtors are expected to behave so as to satisfy their
engagements, commitments create social expectations on the agents’ behaviors [
There is a vast literature on social commitments. A comprehensive starting point for
the interested reader is [
The notion of goal plays an important role not only from the point of view of planning,
but also in general whenever one has to design and develop intelligent agents. In this
paper, we take advantage of the formalization initially proposed in [
As well as commitments, goals have a life cycle in which state transitions are
triggered by the execution of proper goal actions. Figure 2 shows the goal life cycle [
In [
The operational semantics of pragmatic rules is given via guarded rules in which Si are configurations:
guard
S1 −→ S2 Where guard is a condition over the current agent’s beliefs and commitments; whereas S1 −→ S2 is a state transition involving a change in the state of commitments or goals; usually it corresponds to an operation on goals or commitments. Pragmatic rules are distinguished into: (1) rules from goals to commitments, they involve commitments that are used as a means to achieve some goal; and (2) rules from commitments to goals, they involve goals that are used as a means to achieve either the antecedent (if the agent at issue is debtor) or the consequent (if creditor) condition of a commitment. Rules From Goals to Commitments. These rules address situations in which an agent manipulates (e.g., create, or cancel) a commitment to achieve a goal it cannot obtain alone, or to drop a goal is no longer required. Let G ∈ G be an agent goal G(x, p, r, q, s, f ), and C ∈ C be a commitment C(x, y, s, u) (note that the success condition s of G appears as antecedent in C): – ENTICE: (Only) by creating the commitment can the agent satisfy its goal. If G is active and C is null, x creates an offer to another agent – WITHDRAW OFFER: The commitment is of no utility once the end goal for which it is created no longer exists. If G fails or is terminated, then x cancels C. hGA, CN i create(C)
ENTICE hGT ∨F , CAi cancel(C)
WITHDRAW OFFER Rules from Commitments to Goals. The general idea of these rules is that an agent manipulates a goal to satisfy the antecedent or the consequence of a commitment in which the agent is involved. Let C be a commitment C(x, y, s, u); and let us consider two goals G1 = G(x, p, r, q, u, f ) and G2 = G(y, p′, r′, q′, s, f ′) – DELIVER: The agent activates a goal that would lead to discharging its commitment.
If C becomes detached (i.e., goal G2 has been satisfied), then debtor x activates a goal G1 to bring about the consequent:
hG1N , CDi consider(G1) ∧ activate(G1)
DELIVER – DETACH: The creditor brings about the antecedent hoping to influence the debtor to discharge the commitment. If G2 is null and C is conditional, agent y considers and activates G2:
hG2N , CC i consider(G2) ∧ activate(G2)
DETACH 4
A Social Continual Planning (SCP) system is an open environment inhabited by heterogeneous and independent agents. Each agent has its own planning task, and can perform a specific set of actions. A Social Continual Planning Problem is a planning problem of an agent, situated within an SCP system, which, for being solved, requires the agent to plan also a set of engagements, realized as social commitments, with other agents in the system. Agents can join and leave the system dynamically; however, we assume that no agent leaves the system as long as there are active commitments involving it either as debtor or as creditor.
More formally, an SCP system is a tuple hU , A, S) where: – U is a finite set of propositional atoms, whose truth value can be observed by all the agents in the SCP; U represents a sort of common language through which agents can interact. Atoms in this set are used to describe the state of the environment shared by the agents. In addition, these are the atoms that can appear as antecedents and consequents of the commitments. – A is a set of agents; each agent i ∈ A is associated with a configuration which extends the agent configuration we have already introduced. Specifically, the agent configuration for agent i is a tuple hBi, Gi, Ci, Actsi, Socsii: Bi, Gi, and Ci are as before; whereas: • Actsi is a set of actions agent i can perform; it is partitioned into: ∗ Φi is a set of “physical” actions; as usual, these actions are defined in terms of preconditions and effects, which can be both conditions on environment atoms (i.e., in U ) or on internal (agent-dependent) atoms that are not globally traced (i.e., the internal state of an agent is private). ∗ Σi is a set of social actions; preconditions and effects are defined in terms of goals in Gi and commitments in Ci. More precisely, each social action corresponds to a pragmatic rule from goals to commitments. Indeed, we consider these pragmatic rules as actions because, as we discuss below, they can be used by an automated planner to plan interactions with other agents. Note that while goals in Gi are private (only agent i can see and manipulate them), commitments in Ci have a social value: whenever i changes the state of a commitment in Ci, this change becomes visible to all the other agents in the system (see S ). • Socsi is a set of pragmatic rules from commitments to goals adopted by an agents; from our point of view these rules define the social strategy of agent i. Thus, these rules are not used during the planning search, but rather to decide which goals should be pursued. – S is the social state shared by all the agents in the SCP system at hand. The social state can be partitioned into two subsets: • S C is the set of all the active commitments defined between any two agents in A; in particular, for each agent i ∈ A, Ci ⊆ S , Ci is the projection of S over all the commitments in which i appears either as debtor or as creditor. • S E is the set of all the propositional atoms describing the environment that hold at a given time; in particular, S E ⊆ U .
Given an SCP system hU , A, S i, let i ∈ A be an agent, that is described by the tuple hBi, Gi, Ci, Actsi, Socsii. An SCP problem for i amounts to finding a plan, composed by Actsi and Socsi, to achieve Gi starting from Bi. In particular: – Bi is the initial state of the planning task i is responsible for; such a state is a set of atoms possibly occurring in U , but also occurring in a private set of atoms describing the internal state of i, and hence these atoms are not traced within the SCP system. We only assume that i joins the SCP system iff S ∪ Bi 6|= ⊥. – Gi is a list of goals the agent has to achieve; each goal can be an atom or a conjunction of atoms in U and possibly in the private set of agent’s atoms. Note that, differently from classical planning, it is not required that all the goals in Gi hold in a unique system state. – Ci is initially empty. – Φi is a set of domain-dependent actions agent i can directly perform whenever their preconditions hold. For instance, in a logistic domain, a truck-agent can perform action drive, whereas a plane-agent can fly. – Σi can be initialized in different ways; in fact, differently from Φi, this set needs not to be static; on the contrary, it could change over time according to contextual conditions. In our preliminary implementation, we have adopted a very simple solution. Let us consider the ENTICE rule above1. The objective of this rule is to create a commitment of the form C(i, j, s, u), in order to “entice” another agent j to bring about s, which is of interest for i. At this initial stage, however, i cannot know which condition u is of interest for j. Surely enough, i knows which atoms it can directly achieve by performing its physical actions. Thus, for each atom s ∈ U such that s never appears as an effect of any action in Φi, agent i creates a template entice-s whose effect is the creation of a commitment C(i, , s, u), where denotes any agent willing to satisfy s, and u is any atom in U that appears in 1 Other rules are treated consequently.
Algorithm 1 Social Continual Planning Strategy SCP-Strategy(Bi, Gi, Ci, Actsi, Socsi) 1. while Gi 6= ∅ ∨ Ci 6= ∅ do 2. on S change update Gi using Socsi 3. g ← pick up a goal from Gi 4. π ← plan to g 5. status ← execute π 6. if status equals success then 7. Gi ← Gi \ {g} 8. end if 9. end while the effects of at least one physical action in Φi. Of course, since the entice-s template can be instanced in different ways, depending on the actual u condition, agent i will offer first the conditions, that from its point of view, are the cheapest to achieve. – Socsi is a static set of rules, decided at design time, that defines the social behavior of i; namely, how an agent is reliable for bringing about the consequent and antecedent conditions of the commitments in Ci. 4.1
Basically, the SCP strategy we propose, sketched in Algorithm 1, is a form of continual
planning (see e.g., [
An agent i follows the SCP strategy as far as there are goals in Gi to be achieved or Ci is not empty. This second condition assures that an agent does not leave the system when it is still involved in some active commitments.2 At each iteration, the agent checks for updates in the social state S (line 2); any change occurring in S, in fact, can have an impact on the set Gi of goals. For instance, a new commitment C(j, , s, u) appearing in SC could draw the attention of agent i when u is a condition that i needs but it cannot achieve on its own, and at the same time i knows how to obtain s. In such a case, i could accept to be the creditor: s is added to Gi (i will eventually bring about s). On the other hand, the occurrence of a new atom in SE could make the achievement of a goal g in Gi no longer necessary, so g is dropped. Of course, these agent’s decisions are driven by the Socsi behavioral rules. 2 In principle, an agent may remaining situated within the system indefinitely, waiting for agents to cooperate with. For example, in a logistic domain, a shipper has the high-level objective of earn money by offering its transportation facilities. This objective does not immediately translate into an initial goal G, but rather it is better modeled in terms of pragmatic rules (i.e., both social actions in Σ, and behavioral rules in Socs), so as the shipper is willing to accept requests from other agents, but also offers itself shipment services to others.
Once Gi has been updated, agent i selects one goal g from Gi (line 3); and synthesizes a plan π reaching g (line 4). It is worth noting that any off-the-shelf planner can be used to synthesize π since from the point of view of the planner there is no distinction between social and physical actions (both kinds of actions are translated into PDDL, see below). We only assume that in case the used planner produces a partial-order plan (POP), π is one of the possible linearizations of such a POP.
After the planning step, the agent can start the execution of π (line 5), which contains both physical actions in Φi, and social actions in Σi. The execution of π proceeds one action a at a time and in the order. If a is a physical action, it is immediately executed, and its effects on atoms in U are made available to all the other agents via SE . If a is a social action, e.g., an entice-s action, the action execution affects SC with the addition of a new commitment C(i, , s, u), which has to be picked up by some other agent. The execution of π is therefore suspended; indeed, the entice-s action is part of π only in case the atom s is a precondition for some subsequent action, and hence the plan execution cannot proceeds without s. In case an agent j is interested in u, it accepts the offers by finalizing the commitment in C(i, j, s, u), and eventually it will bring about s. As soon as s is satisfied, i proceeds with the execution of its plan (u will be added to Gi the next time i checks for changes in S). When all the actions in π are performed, the execution phase terminates in success state (i.e., g has been achieved), and hence g is removed from Gi (line 7).
However, it is also possible that no agent is interested in the service u offered by i. To avoid an indefinite wait, i sets up a timer. As soon as the time runs out, the commitment is canceled from SC, and the plan execution terminates with a failure state. Since g has not been achieved, it is not removed from Gi. At the next iteration of the strategy, i first checks whether g is still required (line 2), and then tries to find an alternative plan reaching it (line 4) that may require a different instantiation for the entice-s action (i.e., with a different condition offered as consequent of the commitment).
Intuitively, the correctness of the approach relies on the coherence and convergence
properties discussed in [
To verify the feasibility of the SCP strategy, we implemented a proof-of-concept in C and SICStus Prolog 4.3.2. More precisely, an agent is implemented as an independent C program that embeds a simple Prolog planner. Each agent takes in input three files: 1. the description of the planning domain (in PDDL 2.2) from the point of view of a single agent, e.g., the templates of the physical actions the agent is capable to perform; 2. the definition of the planning problem (in PDDL 2.2) that this specific agent has to accomplish; 3. the list of environment objects, namely, those objects that constitute the ontological backbone shared by all the agents in the SCP system. All the possible atoms about these objects must be known by the all the agents.
Note that the parsing of the three files creates a number of initial structures within the Prolog planner, as for instance the list of action templates. This list is subsequently completed with a list of social actions (i.e., actions in Σ), following the procedure sketched above. This step consists in instantiating the predefined PDDL templates encoding the pragmatic rules from goals to commitments. For instance, a number of entice actions are created by instantiating the following template: (:action entice :parameters (?deb ?cre - agent
?ant ?cons - goal) :precondition (and (active-G ?deb ?ant) (not (achieved ?ant)) (cando ?deb ?cons) (null-C ?deb ?cre ?ant ?cons) ) :effect (and (not (null-C ?deb ?cre ?ant ?cons)) (active-C ?deb ?cre ?ant ?cons) (increase (plancost) 10) ))) where a dummy symbol is used to refer to the creditor agent ?cre, not known at this time. active-G and null-C are terms used to define goals and commitments, respectively, with their current state. ?ant and ?cons goals are unique identifiers associated to atoms such as at(pkg1, E). These identifiers are therefore shared by the agents. This workaround was necessary to overcome the current limits of the PDDL expressiveness for which nested terms are not admissible. This instantiation is realized as a C procedure. The generated instances are injected within the Prolog planner by using the C/SICStus bi-directional interface. Finally, note that the entice action is associated with a cost, this is used to avoid the planner resorts to them even when they are not strictly required (e.g., a “lazy” agent could ask others to obtain goals it can achieve by itself).
The social state is implemented by relying on the Inter-Process Communication
facilities offered by the Unix operating system. In particular, two segments of shared
memory are used, one for SC and one for SE . Initially both segments are empty, but
active processes take turns filling up the SE segment by publishing the public facts they
know about the environment objects (Unix semaphores are used to guarantee the
consistent access to the shared memory segments). If a contradiction arises at this step, the
agent terminates without joining the SCP system (i.e., without attempting to solve its
task). So far, behavioral rules that specify the social strategy Socs are implemented
directly in C. Indeed, only a subset of the rules discussed in [
After this preliminary steps, each agent can start solving its task by invoking the embedded planner. Note how the facts maintained by the planner correspond to the private belief state B, whereas facts that are maintained in the shared memories correspond to the social state. (For efficiency reasons, though, each planner replicates in its own working memory the facts in the social state.) 5.1
Let us exemplify the SCP strategy via a simple problem from the well-known logistic planning domain. Figure 3 shows the current state of the SCP system at hand: A through F are cities; C and D have airports, and plane pln1 can fly between them; trucks trk1 and trk2 can drive along the solid edges connecting the cities.
In such a scenario, the only shared object in the environment is represented by the package pkg1, currently located at B. Thus, U contains all the atoms about such an object, which in the logistic domain concern its position, specifically: U ={at(pkg1, A), at(pkg1, B), . . ., at(pkg1, E), at(pkg1, trk1), at(pkg1, trk2),at(pkg1, pln1)}.The set of agents is therefore A={trk1, trk2, pln1}; whereas, for the sake of simplicity, we suppose the social state S is currently empty.
Note that, since U refers only to the package position, the position of each agent is a private piece of information. Moreover, also the domain knowledge is partitioned: trk1 just needs to know how to move among A, B, and C, whereas it needs not to know how the other cities are connected.
Let us consider the problem from the point of view of truck trk1. Its local planning task consists in delivering package pkg1 to E. This is formalized as follows: – Btrk1={at(pkg1, B), at(trk1, A)}, – Gtrk1={at(pkg1, E)}, – Ctrk1=∅, – Φtrk1={drive(A, B), drive(A, C), . . ., load(pkg1, A), unload(pkg1, A), . . .} – Σtrk1={entice − at(trk1, , at(pkg1, E), $100), entice−at(trk1, , at(pkg1, D), $100), entice−at(trk1, , at(pkg1, F ), $100), entice− at(trk1, , at(pkg1, E), $1000), . . .} Note that Φtrk1 contains those actions that are typically defined in the logistic domain for a truck whereas Σtrk1 contains all the social actions agent trk1 is willing to use during its planning search. In particular, there are more entice actions sharing the same antecedent but differing in the consequent. This is the result of the instantiation procedure of the entice template. For instance, trk1 can either pay $100 or $1000 to have pkg1 at E. Of course, a proper usage of action costs would drive the planner in creating “cheaper” commitments first.
Agent trk1 starts the solution of its local planning task by finding a plan reaching the goal at(pkg1, E). The execution of such a plan starts a course of engagements that will involve all the agents. Table 3 summarizes the first four runs of the SCP strategy followed by the agents. Each row in the table shows which goal a specific agent is pursuing, the plan that has been synthesized by the agent, and how the execution of the plan (until the first social action) changes the social state.
The first row of the table shows the plan inferred by trk1: after having picked up package pkg1, the agent, that cannot physically deliver it to E, offers $ 100 to any agent willing to take pkg1 to E. Agent trk2 accepts the offer, see row 2, and plans how to achieve the goal. Also the trk2’s plan contains an offer towards any other agent which is willing to take pkg1 to D, which is accepted (see row 3) by agent pln1. To keep the discussion simple we assume that the agents are cooperative, and omit the fact that pln1 could ask trk2 to do something specific in exchange (e.g., pay for the shipment service). In row 4 we have that agent trk1 brings pkg1 to C where pln1 is waiting for loading and flying it to D, from which trk2 will take it to E. Note that the execution of the agents’ plans will progressively satisfy goals and commitments that will be removed from the social state. We have used the logistic domain as a test-bed for a preliminary experimental analysis. At this stage of development our main objective was to study the feasibility of the approach, and to highlight possible bottlenecks and shortcomings of the SCP strategy, in particular as concerns the instantiation of the entice action.
In a domain involving 2 trucks and 2 planes, we prepared 10 problems. In each problem, every agent was assigned with one package to be delivered. In all the cases, the agent could not deliver the package without the help of at least one other agent. Although the implementation is yet to be engineered, the first data we collected are very encouraging. On average, the instantiation of the entice action produces 68 instances for each agent. Such a large number of action could represent a burden for the planner, but in practice the planner we used (implementing a simple A* search) worked very efficiently; in fact, the planning times are on average 1500 ms, with a pick to 8000 ms only in one case. The length of the synthesized plans is 15 actions, on average, with a pick to 24.
These results show that, even though the instantiation of the entice action can produce a relatively large number of actions, the planner is not significantly burdened by them as in general only a few of them are applicable at the same time. In other words, the number of entice instances is not directly related to the search branching factor. 6
In this paper we addressed the SCP problem, and proposed the SCP strategy as a possible solution. Differently from MAP approaches, where a predefined team of agents has to find a joint plan solving a given planning task, here we deal with situations in which each agent is given a planning task which is independent of the others’ ones. The challenge, thus, is not to find a joint plan, but to find a plan for each agent that solves the agent’s planning task taking advantage of the cooperation with other agents. Moreover, agents are free to join and leave the system dynamically.
The novelties of our proposal are not limited to the openness of the agent team. While in approaches to MAP agents can be thought of as resources used for solving the given planning task, in SCP agents are seen as autonomous entities. This change implies that an agent cannot order another agent to do a job, but the agent can just make an offer, and as we have seen, social commitments come at handy to model this kind of relations. More importantly, however, we have to observe that an agent receiving an offer, being an autonomous entity, can accept or reject the offer depending on its contextual conditions and its local goals. A rational agent, in fact, should accept an offer only if the offer brings along some advantages, otherwise the offer should be put aside.
It is worth noting how the SCP strategy supports the decoupling of agents, that just
share environment objects, whereas they are independent for all the other respects. In
particular, each agent can implement its social strategy (i.e., pragmatic rules in Socs
and Σ) according to local criteria. Moreover, the planning algorithm each agent uses
can be tailored to meet optimization functions that are relevant for the agent itself. Note
also how the cooperation among the agents do not require that an agent knows the
action templates of others (as for instance happens in [
Many lines of research and improvement are possible. In the near future we aim
at engineering the implementation of the SCP strategy by exploiting one of the many
agents platforms available. In particular, the JaCaMo+ platform [
We would like to thank Lorenzo Pierini for his contribution to the implementation.