In this paper we develop a negotiation and contracting framework for inter-organisational workflows. The overall aim is to compute a group-plan from a given set of individual plans, where plans are formulated in the context of a given inter-organisational workflow between the agents. A general problem is that the individual plans are not consistent, i.e. the intersection of all individual plans does not contain a complete process, which leads from the initial state of the workflow to its final state. Therefore, negotiation is needed to obtain a compromise. In this paper we develop a generic negotiation protocol and use branching processes as the elementary data structure. The generic protocol is adapted within the specifics of our Sonar-framework. Sonar is a specification framework that defines the organisational structure of multi-agent systems. Sonar has a formal notion of teams and team-formation which is used here to instantiate the strategy parametres.
The paper studies the process of negotiation among self-interested agents in
the context of business-to-business scenarios. These negotiation processes play a
central role within distributed planning algorithms (cf. [
In our context, here especially our Sonar-framework (Self-Organising Net
Architecture) [
One central construct are inter-organisational workflow nets [
A first attempt to describe the partial plans that are the data during the negotiation is to encode them as sets of action sequences (or more precisely: as computational trees). Despite this is a very simple and lean approach it also has several drawbacks since the plans describe the interaction of two or more parties, so they are inherently concurrent. This has the consequence that there is no lean way to formalise the intersection of partial plans: The set theoretic intersection is not appropriate since due to concurrency different sequences may describe the same processes and a set theoretic intersection would remove too many elements. Analogously, also due to concurrency, there is no lean way of defining the distance of two plans.
We conclude that it is more natural to use partially ordered computations as
they allow to define intersections of plans. Petri net unfoldings [
Unfoldings have been used for planning before (e.g. [
The paper has the following structure: Section 2 recalls basic notions on Petri nets and branching processes. Section 3 defines a multi-party version of workflow nets. Section 4 defines partial plans as the intersection of branching processes and a negotiation protocol based on this formalisation. The work closes with a discussion of related work and an outlook. 2
In the following we give the basic definitions for branching processes. A branching process represents the causality as well as the conflicts between occurring events. The name unfolding is due to the fact that the process is unrolled by adding the transition pattern again and again at the end. An example of a branching process is given in Figure 1 ii), where the nodes are labelled with the original places and transitions from the Petri net given in Figure 1 i).
Petri Nets We recall basic definitions for Petri Nets [
A P/T net N = (P, T, F, M0) consists of a finite Petri net (P, T, F ) and the multiset M0 : P → N which is the initial marking.
A transition t ∈ T of a P/T net is enabled in the marking M iff enough
tokens are present: M (p) ≥ F (p, t) for all p ∈ P . The successor marking when
firing t is M ′(p) = (M (p) − F (p, t)) + F (t, p). We denote the enablement of t in
t t
marking M by M −→. Firing of t is denoted by M −→ M ′. The notation extends
to firing sequences w ∈ T ∗.
Occurrence Nets Petri net processes [
For a partial order ≤ on the set X we define the downward closure ↓ x := {y ∈ X | y ≤ x} and the upward closure ↑ x := {y ∈ X | y ≥ x}. The set of minimal elements of Y ⊆ X wrt. ≤ is denoted by ◦Y , the set of maximal elements by Y ◦.
Since occurrence nets N = (B, E, F ) allow for forward branching it is possible that two nodes x1 and x2 are in conflict which is the case whenever they are successors of two conflicting events e1, e2 ∈ b•. This is formalised by the conflict relation # which is a binary relation on B ∪ E:
x1 # x2 ⇐⇒ ∃b ∈ B : ∃e1, e2 ∈ b• : e1 6= e2 ∧ e1F ∗x1 ∧ e2F ∗x2 Definition 1. A finitely branching Petri net N = (B, E, F ) is an occurrence net iff (i) the < := F + is acyclic, (ii) each node has only finitely many predecessors (i.e. |↓ x| < ∞ for all x ∈ B ∪ E holds), (iii) # is irreflexive, and (iv) each place b ∈ B has at most one predecessor, i.e. |•b| ≤ 1 holds.
successor, |b•| ≤ 1 holds for all b ∈ B.
It follows from |b•| ≤ 1 that causal nets are conflict-free: # = ∅.
The relations li (line) and co (concurrent) are defined as li := ( < ∪ <−1 ∪ id A) and co := ((B ∪ E)2 \ li ∪ id A), where id A = {(a, a) | a ∈ A} is the identity relation. Note, that li and co are symmetric and reflexive relations. Since # is irreflexive and symmetric for occurrence nets, # is reflexive and symmetric. Let R ⊆ A × A be a symmetric and reflexive relation. A set K ⊆ A is a clique with respect to R iff all pairs of its elements are in the relation, i.e. for all x, y ∈ K we have x R y. A maximal clique is called a ken. For an occurrence net a ken C with respect to ( li ∩ #) is called a line, while a ken with respect to ( co ∩ #) is called a cut. For causal nets lines are li -kens and cuts are co -kens (since # = ∅). A cut C with C ⊆ B is called a place-cut, a cut C with C ⊆ E is called a transition-cut.
defined as an occurrence net R together with a pair of mappings φ = (φP , φT ), where φP : B → P and φT : E → T .
The mapping φ has to preserve the localities of transitions: Using the multiset extensions φP⊕ and φT⊕ this is expressed by the commutativity: φP⊕(•e) = •φT (e) and φP⊕(e•) = φT (e)•, which is equivalent to: φP is an isomorphism between •e and •φT (e) as well as between e• and φT (e)•.
Definition 2. Let N = (P, T, F, M0) be a P/T net, R = (B, E, ⋖) an occurrence net, and φ = (φP : B → P, φT : E → T ) a pair of mappings. Then (R, φ) is a branching process of N if the following conditions hold:
run R: φP⊕(◦R) = M0, which implies ◦R ⊆ B. 2. Compatibility of φ with the localities: φP⊕(•e) = •φT (e) and φP⊕(e•) = φT (e)•.
In the finite case, a process (R, φ) can be constructed from the possible firings, i.e. the enablement of transitions, of the net N . The construction is defined inductively for a process net, by adding transitions according to the enablement condition of the net N . The starting point is given by the initial marking, which defines a simple process without any transitions, but only a place for each token in the initial marking.
Full Branching Process/Unfolding There is one branching process, called the full branching process U (N ), that contains all alternative events.
To simplify the notion of a maximal unfolding we assume that the initial marking M0 is a set.
Definition 3. Let N = (P, T, F, M0) be a P/T net. The full branching process U (N ) = (R, φ) is defined as follows: – The occurrence net R = (B, E, ⋖) is given by the inductively defined sets ∞ ∞ B := Sk=0 Bk and E := Sk=0 Ek where
B0 := {(p, ∅) | M0(p) > 0} and E0 := ∅
n−1 n En+1 := {(t, U ) | Sk=0 Bk 6⊇ U ⊆ Sk=0 Bk ∧ U is conflict-free ∧ φ⊕(U ) = •t} Bn+1 := {(p, {e}) | e = (t, U ) ∈ En+1 ∧ p ∈ t•}
– The mappings φ = (φP , φT ) are defined as the first projection: φP (p, X) = p and φT (t, U ) = t.
Note, that the unfolding gives canonical names to places and transitions.
Note, that U (N ) is in general infinite even for net with finite state spaces since cycles in the reachability graph of N lead to infinite long unfolding paths. Let n Un(N ) denote the finite subnet of U (N ) that contains the nodes Sk=0 Bk ∪ Ek.
For finite branching processes it is well known that if the set C ⊆ B is maximal independent wrt. the relation ( co ∩ #) (i.e. C is a place-cut) then the multiset φP⊕(C) is a reachable marking. Analogously, if set C ⊆ E is maximal independent (i.e. a transition cut) then φT⊕(C) is a a maximal multiset of transitions that are concurrently enabled. 3
In this section we define the notions for workflow nets and branching processes to define partial plans and group-plans.
In the following we define an extension of workflow nets to model multi-party
interactions. Workflow Nets (WFN) [
A workflow net is sound [
Definition 4. A Dwfn is the tuple D = (P, T, F, r : T → Rol ), where (P, T, F ) is a WFN and for all p ∈ P we have |r(p•)| ≤ 1 and |r(•p)| ≤ 1.
Partial Plans as Branching Processes of Dwfn Essentially a partial plan of a Dwfn N is an occurrence net π such that all runs lead to the final marking of the Dwfn N .
Definition 5. The occurence net π = ((Bπ, Eπ, ⋖π), φπ) is a partial plan for the Dwfn N = (P, T, F, r) of depth n iff the following holds:
2. π is a sub-net of the unfolding Un(N ) = ((B, E, ⋖), φ), i.e. we have Bπ ⊆ B,
Eπ ⊆ E, ⋖π = ⋖ ∩ ((Bπ × Eπ) ∪ (Eπ × Bπ), and φπ = φ|(Bπ ∪ Eπ).
∀C : C• = ∅ =⇒ φP⊕(C) = {f }
We define PP(N ) := Sn∈N PPn(N ).
If N is a sound workflow then we know that the final marking is always reachable and therefore there is some n such that PPn(N ) is non-empty.
The formalisation of partial plans as a partially ordered structure is an essential issue. If one has used sequential computation trees instead, then one obtains the problem that if two events a and b are concurrently enabled then one would obtain the two branches ab and ba and it would be possible for one agent to e.g. accept ab and reject ba during the local planning – despite the fact that both describe the same interaction. This problem does not arise with branching processes.
Mutual Commitments in Partial Plans The multi-party structure of the workflow net and its branching processes carries over to partial plans. Assume agent a implements a certain role r in a Dwfn. Note, that a partial plan of a does not includ events assigned to its role r, but also events assigned to other roles. This describes the circumstance, that local planning is only practical whenever agent a can rely on some assumptions about the future behaviour of other agents involved in the interaction and makes some commitments to others as well. Therefore, a team negotiation process has the function to establish commitments, i.e. promises some agent makes to allow the planning of others.
Commitments have a natural expression in our formalism: Assume that an agent a implements the role ra in a Dwfn and the agent considers the partial plan πa as relevant during his reasoning process.
– If the event e belongs not to a itself (i.e. r(φ(e)) 6= ra) then a desires a commitment from this other role (desired commitment). – If the event e belongs to a itself (i.e. r(φ(e)) = ra) then a makes a commitment to the other roles (granted commitment).
We conclude, that branching processes of Dwfns, i.e. partial plans, are also useful to formalise the standard coordination concept: commitment. 4.1
Groups
In a multi-agent systems a task is implemented via teamwork, i.e. agents split the
task into smaller subtasks, assign them to other agents etc. The origin of such
approach lies in the contract net protocol [
Let A be the set of all agents and A ⊆ A the set of those agents that want to establish a common plan. We represents groups G as nested sets: A group has the form G = (a, {G1, . . . , Gn}), where a is the head of the group. Whenever n = 0 the group is an atomic group, i.e. a implemets a task and a is from the subset A; or n > 0 and the agent a delegates tasks to the groups {G1, . . . , Gn} and a is from the whole set of agents A. Note, that the head does not have to be in A, since it is not necessary that it participates in the team plan – whenever the agent delegates it has only administrative functions.
For a group G let G⋆ denote the set of immediate sub-groups {G1, . . . , Gn}. The set of all sub-groups of a group G is defined recursively:
Subgroups(G) := {G} ∪ [
G′∈G⋆
Subgroups(G′) (1) (2) We denote the set of sub-groups with depth j as:
Subgroupsj (G) := {G′ ∈ Subgroups(G) | depth(G′) = j} where depth(G) := 1 + max{depth(G′) | G′ ∈ G⋆}. 4.2
Common Partial Plans among a Group of Actors In the following, we define the distance of a branching process to a partial plan.
Assume we have a group G and the family (πg)g∈G⋆ of the group members’ plans that are all of the same depth n. We define the common view of the group as the intersection T πg := Tg∈G⋆ πg, where the intersection of the nets πg is defined component-wise. In this case we encounter the problem that the intersection is not a partial plan in general. Therefore, we calculate the distance between the intersection (πg)g∈G⋆ and a given partial plan π0. Without loss of generality we assume that nodes of π0 = (B0, E0, ⋖0) are given in canonical names of the unfolding Un(N ). In this case we calculate the distance as the number of nodes that are “missing” in the individual partial plans: x∈B0∪E0 d((πg)g∈G⋆ , π0) := X
|G⋆| − |{g ∈ G⋆ | x ∈ Bg ∪ Eg}| We define the set of all partial plans that are at most d steps away from (πg)g∈G⋆ : (3) (4) (5)
PPn N, (πg)g∈G⋆ , d := nπ ∈ PPn(N ) | d((πg)g∈G⋆ , π) ≤ do Obviously, these sets of partial plans are monotonous in d:
PPn(N, (πg)g∈G⋆ , d) ⊆
PPn(N, (πg)g∈G⋆ , d + 1) Usually, PPn(N, (πg)g∈G⋆ , d) = ∅ for small d. Especially, if the intersection Tg∈G⋆ πg is not a partial plan, then PPn(N, (πg)g∈G, d) = ∅ for d = 0. If the intersection T πg is already a partial plan, then it is in PPn(N, (πg)g∈G⋆ , d) for d = 0 and – together with monotonicity – we obtain the following proposition.
PPn(N, (πg)g∈G⋆ , d) 6= ∅ for all d ≥ 0.
A group-plan is a partial plan, that is very “close” to the intersection T πg.
from the set PPn(N, (πg)g∈G⋆ , d), where d = dG.
Note, that the definition of a group-plan πG from (πg)g∈G⋆ does not require that all the roles of the Dwfn N are represented by agents within G, i.e. we allow negotiation within a subset of all agents. For example assume that N describes the interaction of the roles r1, r2, and r3. Then we can formalise a negotiation between only two agents that implement r1 and r2. Their group-plan πG is a partial-plan that is agreed only among r1 and r2 by mutual commitments, but not by r3. Additionally, this group-plan formulates those commitments r1 and r2 desire from r3.
When N is a sound Dwfn, we can be sure that the final marking is reachable, i.e. there exists an n such that PPn(N ) 6= ∅. Since we always obtain a partial plan if we extend a sub-process till the final place f , we obtain the following existence property.
that PPn(N, (πg)g∈G⋆ , d) 6= ∅.
Example 1. The example in Figure 3 shows the group’s view on the group’s plans (πg)g∈G⋆ , where G = (H, {(R, ∅), (S, ∅)}) that are constructed for the Dwfn in Figure 2. We abbreviate the roles Requester and Supplier as R and
Fig. 3. The Group’s Partial Plans S, respectively. The set of agents executing tasks, i.e. implementing roles, is αA(G) = {R, S}. The agent H is an “inner” agent, that has delegated only.
To illustrate the family (πg)g∈G⋆ we label each node x in Fig. 3 with the set of agents/roles that have x in their partial plans (here: {}, {R}, {S}, or {R, S}). The inscriptions of the form #n describe the costs to add the node to the common plan.
Note, that if we restrict the plan to those nodes which are common for all agents, then we obtain the intersection Tg∈G⋆ πg. In this example the intersection is a branching process, but not a partial plan, since no final node f is labelled with A = {R, S}.
We oberserve that there is no partial plan within a distance less than 4. Within the distance d = 4 there is a partial plan which is obtained by adding the agent R = Requester to the nodes in the shaded area. (There is another partial plan for d = 4 that we obtain if we add the agent Supplier to the nodes right/below the shaded area.) 4.3
Negotiation of a Group-Plan The mathematical notion of the set of all partial plans within at most d steps, i.e. PPn(N, (πg)g∈G⋆ , d), is used in to define a distributed negotiation protocol. In the following we sketch our protocol underlying the negotiating process. The aim of negotiation is to construct a group-plan πG0 for the whole group G0.
Assume we have an initial value n for the the depth of the unfolding. The main idea is that we start with individual partial plans for each agent a, which is the smallest group of the form G = (a, ∅), i.e. a sub-group of depth = 1. We assume that each individual agent a has a plan πGn for each planning depth n.
In the protocol we go through several rounds: The negotiation protocol enumerates all tuples (n, d) by a certain strategy σ1, i.e. σ1 : N → N × N is a bijection. In each round (n, d) we increase the depth j of the sub-group G, until we generate a compromise for G0 or there is no compromise for the current round. If there is no compromise, we step to the next round (n′, d′).
Since the parameter d denotes the freedom of the negotiation process to deviate from the local plans, it is likely that negotiation must fail for the first rounds, i.e. negotiation fails and the next (n, d) is enumerated. After some rounds we extend either extend the depth n of the unfolding or the distance d . Therefore, it is more likely that negotiation succeeds in this round.
Due to Prop. 2, we have PPn(N, (πg)g∈G⋆ , d) 6= ∅ for some d and some n, which guarantees termination of the protocol. 5
In this paper we formalised a generic negotiation and contracting framework for inter-organisational workflows. The protocol is generic as it allows different strategies for generating sub-groups and generating compromises within a certain distance from the group’s plans. As a very useful property we obtain the result that the protocol terminates for all possible choices of those strategies.
We have shown that branching processes are a very useful data structure to
express the central concepts of negotiation, like partiality of plans, intersection
of partial plans, and distance of partial plans and compromises. The protocol is
used as a part of our Mulan4Sonar [
Our context of negotiation in business-to-business scenarios has several
aspects in common with standard algorithms in multi-agent systems, but is
different at the same. For a survey on distributed problem solving and
planning (cf. [
We give a short comparision of our approach and the PGP protocol [
On the contrary, the protocol we propose here is designed for agents that act within an organisational setting following the organisation centred design metaphor. Here, we have a predefined organisational structure, which manifests e.g. in distributed workflow nets. At least at the abstract level of interaction the workflow clearly defines the possible interactions.
Therefore we have choosen an a-piori approach, where the coordination primitives as defined in the workflow are considered first and later on the individual preferences are added and aligned via negotiation. To the best of our knowledge, our negotiation approach in combination with unfoldings is novel in the literature.
For future work it is planned to implement another variant of the negation process, where we consider refinement of workflows also. During the teamwork it is allowed to refine the subtaks, i.e. replace a role component by a refined one. The generation generates a hierarch of workflow refinements. The negotiation should then start a negotiation process for the most abstract workflow. When a compromise is reached, it starts a negotiation process for the next workflow refinement with the constraint that the group-plan for the refined workflow has to be a refinement of the abstract group-plan. This process is iterated until an agreement is achived for the finest workflow. In this scenario we rely on on Dwfn with an restricted set of refinement operations which carry over to the unfolding such that we can refine partial-plans during the negotiation.