Automated Composition of Web Services by Planning at the Knowledge Level

1 Introduction

Research in planning is more and more focusing on the problem of the automated composition of web services: given a set of services that are published on the Web, and given a goal, generate a composition of the available services that satisfies the goal (see, e.g., [Narayanan and McIlraith, 2002]). In spite of the fact that several approaches have been proposed so far (see, e.g., [McIlraith and Son, 2002; Wu et al., 2003; Sheshagiri et al., 2003; Traverso and Pistore, 2004]), solving this problem in practice, by scaling up to realistic descriptions of web services, is far from trivial. Indeed it is widely recognized that web services must be modeled with nondeterministic and partially observable behaviors [Koehler and Srivastava, 2003; Hull et al., 2003; Berardi et al., 2003; McIlraith and Fadel, 2002; Traverso and Pistore, 2004; Martinez and Lesperance, 2004], and thus planning algorithms must work with incomplete information and with actions with uncertain effects. Moreover, in several application domains, web services cannot be simply modeled as atomic components, but as stateful processes whose interactions are intrinsically asynchronous [Fu et al., 2004; Foster et al., 2003; Pistore et al., 2005].

A. Marconi and P. Bertoli and P. Traverso

ITC-IRST

Via Sommarive 18 38050 Povo (TN), Italy [marconi, bertoli, traverso]@itc.it

Recent works address the problem of the practicality of the proposed solutions for web service composition. For instance, [Traverso and Pistore, 2004; Pistore et al., 2005] propose a framework where web services are modeled with stateful, nondeterministic, and partially observable behaviors, and planning techniques based on symbolic model checking are used to address the scalability problem. However, these techniques work under the rather unrealistic assumption that web services can exchange only a very small number of data values. For instance, as the experimental results reported in [Traverso and Pistore, 2004; Pistore et al., 2005] show, reasonable performances are obtained for web services whose variables can contain only two values. This amounts to say that amazon.com could sell just two books!

Luckily enough, as already stated in [Pistore et al., 2005], the composition solution should not depend on the actual data exchanged among web services, in the same way as the operations that one has to perform to buy a book do not depend on the precise book one wants to buy. The flow of operations and interactions depends instead on whether the desired book is available or not, on whether its cost is affordable, and so on. The relevant issues for interacting with amazon.com are whether one knows whether the book is available or not, whether one knows the value of its price, and so on. The hope here is to apply planning techniques at the knowledge level, in the style of those proposed in [Petrick and Bacchus, 2002], or used in [McIlraith and Son, 2002; Martinez and Lesperance, 2004]. This would make it possible to model only those features of the services which are relevant to compose them, and thus allow for an efficient automated composition.

Unfortunately, applying knowledge-level planning to solve the automated composition problem presents a major difficulty. While in [Petrick and Bacchus, 2002] the planning domain at the knowledge level is defined by hand, this is impractical for web service automated composition tasks. The knowledge level domain must be extracted automatically from the description of the services that are published, e.g., in standard languages, like BPEL4WS [Andrews et al., 2003]. The problem is therefore to devise a proper knowledge level model, which is suited for the automated composition task, and which can be obtained automatically from the published descriptions of the web services.

In this paper we propose a novel approach to the problem of automated composition that is based on planning at the knowledge level. We achieve this in the following steps:

• a0 We formally define a knowledge level model of web services that can be obtained automatically from specifications in standard languages for modeling and implementing services. We show indeed how BPEL4WS processes can be automatically translated into their knowledge level models.
• a0 We show how the automated composition problem can be described as a planning problem: from the knowledge level models of the available services and from the composition goal, we generate a planning problem such that a solution plan encodes the desired composition.
• a0 We apply the planning techniques described in [Pistore et al., 2005] to the knowledge level planning problem that we obtain from the previous steps. The key advantage w.r.t. [Pistore et al., 2005] is that we do not have to deal with all the possible values of variables that are exchanged among services.
• a0 We implement the proposed framework, and provide a preliminary experimental evaluation that clearly shows the benefits of our approach.

The paper is structured as follows. We first describe a simple example of composition of BPEL4WS processes, which we will use all along the paper (Section 2). We then briefly recall the framework for planning in asynchronous domains that has been first introduced in [Pistore et al., 2005] (Section 3). In Section 4, we describe the knowledge level representation of web services, and the resulting planning framework at the knowledge level. We finally describe the experimental evaluation (Section 5), some conclusions, and related work.

2 Composition of BPEL processes

Our reference example is the Purchase and Ship (P&S hereafter) example introduced in [Pistore et al., 2005; Traverso and Pistore, 2004].

Example 1 The P&S example consists in providing a furniture purchase & ship service by combining two independent existing services, a furniture producer Producer and a delivery service Shipper. This way, the User, also described as a service, may directly ask the composite service P&S to purchase a given item and deliver it at a given place (for simplicity, we assume that the shipment origin is fixed and leave it implicit).

The interactions with the existing services have to follow specific protocols. For instance, the interactions with the Shipper start with a request for transporting a product of a given size to a given location. This might not be possible, in which case the requester is notified, and the protocol terminates with failure. Otherwise, a cost and delivery time are computed and sent back to the requester. Then the Shipper waits for either an acceptance or a refusal of the offer from the invoker. In the former case, a delivery contract has been defined and the protocol terminates with success, while it terminates with failure in the latter case. Similar protocols are defined also for Producer and User. The messages exchanged among the involved services are described in Figure 1.

The P&S has the goal to sell home-delivered furniture (i.e., to reach the situation where the user has confirmed an order and the service has confirmed the corresponding suborders to producer and shipper), interacting with Shipper, Producer, and User according to their protocols. A typical interaction could be as follows:

1. the User asks P&S for an article ✁ , that he wants to be transported at location ✂ ;
2. P&S asks the Producer for the size, the cost, and how much time does it take to produce the article ✁ ;
3. P&S asks the Shipper for the price and time needed to transport an object of such a size to ✂ ;
4. P&S sends the User an offer which takes into account the overall cost (plus an added cost for P&S) and time to achieve its goal;
5. the User sends a confirmation of the order, which is dispatched by P&S to Shipper and Producer.

This is however only the normal case, and other interactions should be considered, e.g., for the cases the producer and/or delivery services are not able to satisfy the request, or the user refuses the final offer.

With automated composition of web services we mean the generation of a new composite service (the P&S in our case) that interacts with a set of existing component services (Shipper, Producer, and User in our case) in order to satisfy a given composition goal (sell home-delivered furniture).

We assume that the interaction protocols of the component services, as well as the composite service, are described as BPEL4WS processes (see Figure 2 for a graphical representation of the Shipper BPEL4WS process). Notice that while existing services are described as abstract BPEL4WS processes (providing essentially the communication protocol), the synthesized service is an executable BPEL4WS process exporting all the details to be directly deployed and run. A BPEL4WS description specifies the types and internal variables of a service, and its input and output capabilities. The behavior of the process is described using input (receive) and output (invoke, reply) activities combined by standard constructs, such as sequences, loops, parallel executions, conditional choices, and nondeterministic choices.

From a BPEL4WS process, we can automatically extract a formal model of the interactions with the service, covering both the static aspects (e.g., its communication channels) and the behavioral aspects (defined in term of transition steps). For the moment, the translation is restricted to a subset of BPEL4WS processes: we support all BPEL4WS basic and structured activities, like invoke, reply, receive, sequence, switch, while, flow (without links) and pick; moreover we support assignments and a limited form of correlation. Our next steps will be dealing with scopes and with fault, event and compensation handlers.

For lack of space we omit the formal definition of this translation (details can be found at http://astroproject.org/) but we illustrate it in the case of the Shipper process.

Example 2 Figure 3 shows a formal model of the Shipper, automatically extracted from the BPEL4WS process of Figure 2. The Shipper process is characterized by a set of abstract types used in the interactions (e.g., Size, Cost), by a set of inputs and outputs (e.g., request and offer, respectively), and by a set of typed functions used to manipulate internal variables (e.g., function costOf, which is used to obtain the cost of a particular shipping request). Variables are used to store information on the state of the process. In Figure 3, variables of abstract types (e.g., customer size) store values used in the communications, while an additional variable pc implements a "program counter" that holds the current execution step of the service. The model describes the evolution of the process through a set of possible transitions, each corresponding to a "step" in the BPEL4WS process; each transition defines an applicability condition, a firing action, and an effect (defined as a list of assignment to variables). Possible actions are inputs, outputs, and a special action TAU which is used to model internal evolutions of the process, such as assignments and decision making (e.g., the transition from state prepareOffer, where the internal functions costOf and delayOf are used to compute the shipping price and delivery time).

PROCESS Shipper; TYPE Size; Location; Cost; Delay; INPUT request(Size, Location); ack(); nack(); OUTPUT offer(Delay, Cost); not avail(); FUNC costOf(Size, Location) : Cost; delayOf(Size, Location) : Delay; VARIABLE pc: a0 START, getRequest, checkAvailable, end checkAvailable, sequence1, sequence2, prepareOffer, sendOffer, waitAnswer, endWaitAnswer, empty1, prepareNotAvail, sendNotAvail, SUCC, FAIL ✁ ; customer size: Size; customer loc: Location; offer delay: Delay; offer cost: Cost; INIT pc := START; TRANS pc = START -[TAU]- ✂ pc := getRequest; pc = getRequest -[INPUT request(customer size, customer loc)]- ✂ pc := checkAvailable, pc = checkAvailable -[TAU]- ✂ pc := sequence1; pc = checkAvailable -[TAU]- ✂ pc := sequence2; pc = sequence1 -[TAU]- ✂ pc := prepareOffer; pc = prepareOffer -[TAU]- ✂ pc := sendOffer, offer cost:=costOf(customer size,customer loc), offer delay:=delayOf(customer size,customer loc); pc = sendOffer -[OUTPUT offer(offer cost, offer delay)]- ✂ pc := waitAnswer; pc = waitAnswer -[INPUT nack]- ✂ pc := FAIL; pc = waitAnswer -[INPUT ack]- ✂ pc := empty1; pc = empty1 -[TAU]- ✂ pc := endWaitAnswer; pc = endWaitAnswer -[TAU]- ✂ pc := endCheckAvailable; pc = endCheckAvailable -[TAU]- ✂ pc := SUCC; pc = sequence2 -[TAU]- ✂ pc := prepareNotAvail; pc = prepareNotAvail -[TAU]- ✂ pc := sendNotAvail; pc = sendNotAvail -[OUTPUT not avail]- ✂ pc :=FAIL;

3 A Planning Framework for Service Composition

The work in [Pistore et al., 2005] presents a formal framework for the automated composition of web services which is based on planning techniques: component services define the planning domain, composition requirements are formalized as a planning goal, and planning algorithms are used to generate the composite service. Due to the nature of web services, the resulting planning domain is nondeterministic and partially observable. The framework of [Pistore et al., 2005] differs from other planning frameworks since it assumes an asynchronous, message-based interaction between the domain (encoding the component services) and the plan (encoding the composite service). More precisely, the planning domain is modeled as a state transition system (STS from now on) that can be in one of its possible states (a subset of which are initial) and can evolve to new states as a result of performing some actions. In particular, input actions represent messages sent to the component services, while output actions are messages received from the component services. Private actions are actions that the composite service can perform internally, without interacting with the component services 1 , while the special action ✄ is used to model internal evolutions of the component services which are not visible to the service user. Finally, a labeling function associates to each state the set of properties ☎ ✆ ✞ ✠ holding in that state.

1 As we will see, private actions are used to model operations such as computing the total cost for the user from the costs received from the producer and from the shipper. Private actions are specific of the knowledge-level approach presented here and for this reason they do not appear in [Pistore et al., 2005]. The extension of the theory of [Pistore et al., 2005] to private actions is straightforward.

Definition 1 (state transition system (STS))

A state transition system a0 is a tuple ✁ ✂ ☎ ✂ ✞ ☎ ✡ ☎ ✌ ☎ ✏ ☎ ✓ ☎ ✕ ✖ where:

• a0 ✂ is the finite set of states;
• a0 ✂ ✞ ✙ ✂ is the set of initial states;
• a0 ✡ is the finite set of input actions;
• a0 ✌ is the finite set of output actions;
• a0 ✏ is the finite set of private actions;
• a0 ✓ ✙ ✂ ✣ ✥ ✡ ✧ ✌ ✧ ✏ ✧ ✫ ✄ ✭ ✯ ✣ ✂ is the transition relation;
• a0 ✕ ✲ ✂ ✵ ✷ ✹ ✺ ✼ ✽ is the labeling function.

In a composition problem, the composite service is defined as a "controller" a0 ✿ (also described as a STS), which interacts with the domain a0 , orchestrating the component services by invoking their operations and handling results. We now recall the formal definition of the behavior of a STS a0 when controlled by a0 ✿ .

Definition 2 (controlled system)

Let a0 ❀ ✁ ✂ ☎ ✂ ✞ ☎ ✡ ☎ ✌ ☎ ✏ ☎ ✓ ☎ ✕ ✖ and a0 ✿ ❀ ✁ ✂ ✿ ☎ ✂ ✞ ✿ ☎ ✌ ☎ ✡ ☎ ✏ ☎ ✓ ✿ ☎ ✕ ❉ ✖ be two state transition systems, where ✕ ❉ ✥ ❊ ✿ ✯ ❀ ● for all ❊ ✿ ❍ ✂ ✿ . The STS a0 ✿ ■ a0 , describing the behaviors of system a0 when controlled by a0 ✿ , is defined as:

a0 ✿ ■ a0 ❀ ✁ ✂ ✿ ✣ ✂ ☎ ✂ ✞ ✿ ✣ ✂ ✞ ☎ ✡ ☎ ✌ ☎ ✏ ☎ ✓ ✿ ■ ✓ ☎ ✕ ✖ where:

• a0 ✁ ✥ ❊ ✿ ☎ ❊ ✯ ☎ ✄ ☎ ✥ ❊ ◆ ✿ ☎ ❊ ✯ ✖ ❍ ✥ ✓ ✿ ■ ✓ ✯ if ✁ ❊ ✿ ☎ ✄ ☎ ❊ ◆ ✿ ✖ ❍ ✓ ✿ ;
• a0 ✁ ✥ ❊ ✿ ☎ ❊ ✯ ☎ ✄ ☎ ✥ ❊ ✿ ☎ ❊ ◆ ✯ ✖ ❍ ✥ ✓ ✿ ■ ✓ ✯ if ✁ ❊ ☎ ✄ ☎ ❊ ◆ ✖ ❍ ✓ ;
• a0 ✁ ✥ ❊ ✿ ☎ ❊ ✯ ☎ ✁ ☎ ✥ ❊ ◆ ✿ ☎ ❊ ◆ ✯ ✖ ❍ ✥ ✓ ✿ ■ ✓ ✯ , with ✁ ◗ ❀ ✄ , if ✁ ❊ ✿ ☎ ✁ ☎ ❊ ◆ ✿ ✖ ❍ ✓ ✿ and ✁ ❊ ☎ ✁ ☎ ❊ ◆ ✖ ❍ ✓ .

Due to the asynchronous nature of web service interactions, and in order to guarantee a correct execution of the composite service, we need to rule out explicitly the cases where the sender is ready to send a message that the receiver is not able to accept. According to [Pistore et al., 2005], a state ❊ is able to accept a message ✁ if there exists some successor ❊ ◆ of ❊ , reachable from ❊ through a (possibly empty) sequence of ✄ transitions, such that an input transition labeled with ✁ can be performed in ❊ ◆ . This intuition is captured in the following definition, wherewe denote by ✄ -closure ✥ ❊ ✯ the set of states reachable from ❊ through a chain of ✄ transitions. For what concerns private actions, since they correspond to internal operations of the composite service, we simply assume that they are executable in the current state of a0 .

Definition 3 (deadlock-free controller)

Let a0 ❀ ✁ ✂ ☎ ✂ ✞ ☎ ✡ ☎ ✌ ☎ ✏ ☎ ✓ ☎ ✕ ✖ be a STS and a0 ✿ ❀ ✁ ✂ ✿ ☎ ✂ ✞ ✿ ☎ ✌ ☎ ✡ ☎ ✏ ☎ ✓ ✿ ☎ ✕ ❉ ✖ be a controller for a0 . a0 ✿ is said to be deadlock free for a0 if all states ✥ ❊ ✿ ☎ ❊ ✯ ❍ ✂ ✿ ✣ ✂ that are reachable from the initial states of a0 ✿ ■ a0 satisfy the following conditions:

• a0 if ✁ ❊ ☎ ✁ ☎ ❊ ◆ ✖ ❍ ✓ with ✁ ❍ ✌ then there is some ❊ ◆ ✿ ❍ ✄ -closure ✥ ❊ ✿ ✯ such that ✁ ❊ ◆ ✿ ☎ ✁ ☎ ❊ ◆ ◆ ✿ ✖ ❍ ✓ ✿ for some ❊ ◆ ◆ ✿ ❍ ✂ ✿ ;
• a0 if ✁ ❊ ✿ ☎ ✁ ☎ ❊ ◆ ✿ ✖ ❍ ✓ ✿ with ✁ ❍ ✡ then there is some ❊ ◆ ❍ ✄ -closure ✥ ❊ ✯ such that ✁ ❊ ◆ ☎ ✁ ☎ ❊ ◆ ◆ ✖ ❍ ✓ for some ❊ ◆ ◆ ❍ ✂ .
• a0 if ✁ ❊ ✿ ☎ ✁ ☎ ❊ ◆ ✿ ✖ ❍ ✓ ✿ with ✁ ❍ ✏ then ✁ ❊ ☎ ✁ ☎ ❊ ◆ ✖ ❍ ✓ for some ❊ ◆ ❍ ✂ .

In [Pistore et al., 2005], the composition problem for domain a0 and composition goal ❳ is defined as the problem of finding a deadlock-free STS a0 ✿ such that a0 ✿ ■ a0 satisfies ❳ . Planning techniques, based on the planning as model checking framework, are used to solve this problem, and the experimental results show the effectiveness of this approach.

However, the approach of [Pistore et al., 2005] requires a finite set of data values for all data types (e.g., only a finite number of articles, locations, costs. . . can be defined in the P&S domain). This assumption guarantees that the formal model of a BPEL4WS process such as the one in Figure 3 can be mapped into a finite-state STS. Moreover, the number of data values impact dramatically on the size of the generated STS, and very small sets of values need to be used to allow for an effective plan generation: for instance, all experiments in [Pistore et al., 2005] assume only two values for each data type. In the following we show how to adapt the framework of [Pistore et al., 2005] to a knowledge-level planning approach in order to remove this restriction and allow for automated composition with a realistic (or even infinite) number of data values.

4 Service Composition via Knowledge-Level Planning

The key aspect for extending the approach of [Pistore et al., 2005] to the knowledge level is the definition of an appropriate model for providing a knowledge level description of the component services. In this section we formally define such a model in terms of a suitable knowledge base (from now on ❩ ❬ ). Thenwe showhow to construct the STS corresponding to the planning domain by composing the knowledge bases of the component services.

Definition 4 (Knowledge Base)

A knowledge base ❩ ❬ is a set of propositions of the following form:

• a0 ❩ ❪ ✥ ❫ ✯ where ❫ is a variable with an abstract type;
• a0 ❩ ✥ ❫ ❀ ❴ ✯ where x is an enumerative variable and v is one of its possible values;
• a0 ❩ ✥ ❫ ❀ ❛ ✯ where x and y are two variables with the same type;
• a0 ❩ ✥ ❫ ❀ ❞ ✥ ❛ ❢ ☎ ❣ ❣ ❣ ☎ ❛ ✐ ✯ ✯ where ❫ ☎ ❛ ❢ ☎ ❣ ❣ ❣ ☎ ❛ ✐ are variables with an abstract type and ❞ is a function compatible with the types of ❫ ☎ ❛ ❢ ☎ ❣ ❣ ❣ ☎ ❛ ✐ .

With ❩ ✥ ✠ ✯ we mean that we know that proposition ✠ is true and with ❩ ❪ ✥ ❫ ✯ that we know the value of the variable ❫ . This definition of knowledge base is very simple; still, our experiments show that it is powerful enough to model web service composition problems.

We say that a knowledge base ❩ ❬ is consistent if it does not contain contradictory knowledge propositions such as ❩ ✥ ❫ ❀ ❴ ✯ and ❩ ✥ ❫ ❀ ❴ ◆ ✯ , with ❴ ◗ ❀ ❴ ◆ . We say that ❩ ❬ is closed under deduction if it contains all the propositions that can be deduced from the propositions in ❩ ❬ ; for instance a

❩ ❬ containing both ❩ ❪ ✥ ❫ ✯ and ❩ ✥ ❫ ❀ ❛ ✯ should contain also ❩ ❪ ✥ ❛ ✯ .

The knowledge base ❩ ❬ of a component service is obtained from the variables, functions and types of the service.

Example 3 An example of knowledge base for the Shipper process in Figure 3 is:

KB= ✁ K(pc = waitAnswer) ✂ K ✄ (customer size) ✂ K ✄ (customer loc) ✂ K(offer cost = costOf(customer size, customer loc))✂ K(offer delay = delayOf(customer size, customer loc))✂ K✄ (offer cost), K✄ (offer delay)☎ ✆

In the following we describe when a transition can be executed in a knowledge base ❩ ❬ and how its execution affects ❩ ❬ .

We model a transition ✞ , such as those presented in Figure 3, as a triple ✥ ✟ ☎ ✁ ☎ ✡ ✯ where ✟ ❀ ✥ ☞ ❢ ✍ ❣ ❣ ❣ ✍ ☞ ✐ ✯ are its conditions, ✁ is its firing action and ✡ ❀ ✥ ✒ ❢ ✔ ❣ ❣ ❣ ✔ ✒ ✐ ✯ are its effects. We start by defining the auxiliary restriction and update operations.

The restriction of a knowledge base ❩ ❬ with a condition ✟ , denoted with ✆ ✒ ❊ ✞ ✆ ✘ ☞ ✞ ✥ ❩ ❬ ☎ ✟ ✯ , is performed adding to ❩ ❬ the knowledge obtained from ✟ and closing under deduction; for instance:

restrict( ✁ K(x = y)☎ , y = z) = ✁ K(x = y), K(y = z), K(x = z)☎ ✆

The update of a knowledge base ❩ ❬ with an effect ✡ , denoted with ✜ ✠ ✢ ✁ ✞ ✒ ✥ ❩ ❬ ☎ ✡ ✯ , consists in performing the following steps: for each assignment in ✡ , remove from ❩ ❬ the knowledge we had on the modified variable, add the knowledge derived from the assignment and close the ❩ ❬ under deduction. For instance:

update( ✁ K(x = y)☎ , z := x; x := w) = update( ✁ K(x = y), K(z = x), K(z = y)☎ , x := w) = ✁ K(z = y), K(x = w) ☎ ✆

We now give the definitions of applicability and execution which depend on a service transition ✞ and on an action ✁ ✿ performed by a peer interacting with the service; the firing action ✁ in ✞ and the peer action ✁ ✿ correspond to the same action except that the former is instantiated on service variables, while the latter on variables of the peer. Consider for instance the following example where action request(s, l) performed by the peer corresponds to the Shipper request(customer size, customer loc).

Example 4 Let's consider the input transition t of the Shipper

pc = getRequest -[INPUT request(customer size, customer loc)]-> pc := checkAvailable

and suppose that our current knowledge base is:

KB = ✁ K(pc = getRequest), K ✄ (s) ✂ K ✄ (l) ☎ .

where s:Size and l:Location are additional variables. Action request(s, l), corresponding to invoking the Shipper action using s and l as parameters, is applicable in KB since we know the values of s and l and the condition of transition t is obviously consistent with KB.

The knowledge base obtained by executing on KB transition t and action request(s, l), is defined as follows:

• a0 we restrict KB with the knowledge K(pc = getRequest) associated to the transition condition; in this specific case KB remains unchanged;
• a0 then we update KB with the knowledge carried by the input action on the variables used as action parameters; this consists in removing from KB all the knowledge we had on customer size and customer loc, adding the new knowledge K(customer size = s), K(customer loc = l) and closing under deduction; we obtain:
• a0 finally we update the knowledge base with the effects, removing from KB' all the knowledge we had on the variables modified by the assignments, adding the new knowledge (in this case K(pc := checkAvailable)) and closing under deduction; we obtain:

KB' = ✁ K(pc = getRequest), K ✄ (s)✂ K✄ (l)✂ K✄ (customer size)✂ K✄ (customer loc)✂ K(customer size = s) ✂ K(customer loc = l) ☎ ;

KB'' = ✁ K(pc = checkAvailable), K✄ (s)✂ K ✄ (l) ✂ K ✄ (customer size) ✂ K ✄ (customer loc) ✂ K(customer size = s) ✂ K(customer loc = l) ☎ .

Definition 5 (KL Applicability and Execution)

A transition ✞ ❀ ✥ ✟ ☎ ✁ ☎ ✡ ✯ and a corresponding action ✁ ✿ are applicable in ❩ ❬ , written ✧ ★ ★ ✪ ✬ ✮ ✧ ✯ ✪ ✱ ✳ ✞ ✵ ✥ ❩ ❬ ☎ ✁ ✿ ✯ if:

• a0 ✁ ✿ ❀ ✘ ✥ ❫ ❢ ☎ ❣ ❣ ❣ ☎ ❫ ✐ ✯ and ✁ ❀ ✘ ✥ ❛ ❢ ☎ ❣ ❣ ❣ ☎ ❛ ✐ ✯ , where ✘ is an input, ❩ ❪ ✥ ❫ ❢ ✯ ☎ ❣ ❣ ❣ ☎ ❩ ❪ ✥ ❫ ✐ ✯ ❍ ❩ ❬ and ✆ ✒ ❊ ✞ ✆ ✘ ☞ ✞ ✥ ❩ ❬ ☎ ✟ ✯ is consistent; or
• a0 ✁ ✿ ❀ ✞ ✥ ❫ ❢ ☎ ❣ ❣ ❣ ☎ ❫ ✐ ✯ and ✁ ❀ ✞ ✥ ❛ ❢ ☎ ❣ ❣ ❣ ☎ ❛ ✐ ✯ , where ✞ is an output, and ✆ ✒ ❊ ✞ ✆ ✘ ☞ ✞ ✥ ❩ ❬ ☎ ✟ ✯ is consistent; or
• a0 ✁ ✿ ❀ ✁ ❀ ✄ and ✆ ✒ ❊ ✞ ✆ ✘ ☞ ✞ ✥ ❩ ❬ ☎ ✟ ✯ is consistent.

If ✧ ★ ★ ✪ ✬ ✮ ✧ ✯ ✪ ✱ ✳ ✞ ✵ ✥ ❩ ❬ ☎ ✁ ✿ ✯ , then we denote with ❩ ❬ ◆ ❀ ✱ ✿ ✱ ✮ ✳ ✞ ✵ ✥ ❩ ❬ ☎ ✁ ✿ ✯ the execution on ❩ ❬ of ✞ and ✁ ✿ , defined as follows:

• a0 if ✁ ✿ ❀ ✄ and ✞ ❀ ✥ ✟ ☎ ✄ ☎ ✡ ✯ then ❩ ❬ ◆ ❀ ✜ ✠ ✢ ✁ ✞ ✒ ✥ ❩ ❬ ◆ ◆ ☎ ✡ ✯ , where ❩ ❬ ◆ ◆ ❀ ✆ ✒ ❊ ✞ ✆ ✘ ☞ ✞ ✥ ❩ ❬ ☎ ✟ ✯ ;
• a0 if ✁ ✿ ❀ ✘ ✥ ❫ ❢ ☎ ❣ ❣ ❣ ☎ ❫ ✐ ✯ , where ✘ is an input, and ✞ ❀ ✥ ✟ ☎ ✘ ✥ ❛ ❢ ☎ ❣ ❣ ❣ ☎ ❛ ✐ ✯ ☎ ✡ ✯ then ❩ ❬ ◆ ❀ ✜ ✠ ✢ ✁ ✞ ✒ ✥ ❩ ❬ ◆ ◆ ☎ ❛ ❢ ✲ ❀ ❫ ❢ ✔ ❣ ❣ ❣ ✔ ❛ ✐ ✲ ❀ ❫ ✐ ✔ ✡ ✯ , where ❩ ❬ ◆ ◆ ❀ ✆ ✒ ❊ ✞ ✆ ✘ ☞ ✞ ✥ ❩ ❬ ☎ ✟ ✯ ;
• a0 if ✁ ✿ ❀ ✞ ✥ ❫ ❢ ☎ ❣ ❣ ❣ ☎ ❫ ✐ ✯ , where ✞ is an output, and ✞ ❀ ✥ ✟ ☎ ✞ ✥ ❛ ❢ ☎ ❣ ❣ ❣ ☎ ❛ ✐ ✯ ☎ ✡ ✯ then ❩ ❬ ◆ ❀ ✜ ✠ ✢ ✁ ✞ ✒ ✥ ❩ ❬ ◆ ◆ ☎ ❫ ❢ ✲ ❀ ❛ ❢ ✔ ❣ ❣ ❣ ✔ ❫ ✐ ✲ ❀ ❛ ✐ ✔ ✡ ✯ , where ❩ ❬ ◆ ◆ ❀ ✆ ✒ ❊ ✞ ✆ ✘ ☞ ✞ ✥ ❩ ❬ ☎ ✟ ✯ ✧ ✫ ❩ ❪ ✥ ❛ ❢ ✯ ☎ ❣ ❣ ❣ ☎ ❩ ❪ ✥ ❛ ✐ ✯ ✭ .

Notice that the execution of a transition increases the knowledge in ❩ ❬ , not only with the information in the effects, but also with those in the condition. Indeed, if the transition is executed, this means that the condition is known to hold.

The planning domain at the knowledge level is constructed from the knowledge-level models of each component service and from a knowledge-level representation of the composition goal. The latter defines which are the variables and the functions of the composite service, like, for instance, the cost of the offer to the user, or a special function that adds a mark up to the sum of the costs of the shipper and producer. We call these variables and functions, goal variables and goal functions.

Given a composition goal, we automatically generate its knowledge level representation that declares what the composite service must know and how goal variables and functions must be related with the variables and functions of the component services.

Example 5 A possible (very simple) composition goal for our reference example is:

TryReach

user.pc = SUCC a0 producer.pc = SUCC a0 shipper.pc = SUCC a0 user.offer cost ✁ addCost(producer.costOf(user.article), shipper.costOf(producer.sizeOf(user.article), user.location))

The goal declares that we want all the services to reach the situation where the order has been confirmed. Moreover it states that the offered cost must be obtained by applying the function addCost to the costs offered by the producer and the shipper. The operator TryReach is one of the modal operators provided by the EAGLE goal specification language. It requires that the plan reaches the goal condition whenever possible in the domain. For further details, see [Pistore et al., 2005]

To obtain the knowledge level goal, we flatten the functions introducing auxiliary variables until only basic propositions are left:

TryReach

user.pc = SUCC a0 producer.pc = SUCC a0 shipper.pc = SUCC a0 user.offer cost = goal.added cost a0 goal.added cost = addCost(goal.prod cost, goal.ship cost) a0 goal.prod cost = producer.costOf(goal.user art) a0 goal.ship cost = shipper.costOf(goal.prod size, goal.user art) a0 goal.user art = user.article a0 goal.prod size = producer.sizeOf(goal.user art) a0 goal.user loc = user.location

From this flattened goal we can extract the goal variables: goal.added cost, goal.prod cost, goal.ship cost, goal.prod size, goal.user art, and goal.user loc; and the goal function goal.addCost(Cost, Cost)✂ Cost.

The goal can then be automatically translated into its corresponding knowledge level goal:

TryReach

K(user.pc = SUCC) a0 K(producer.pc = SUCC) a0 K(shipper.pc = SUCC) a0 K(user.offer cost = goal.added cost) a0 K(goal.added cost = goal.addCost(goal.prod cost, goal.ship cost))a0 K(goal.prod cost = producer.costOf(goal.user art))a0 K(goal.ship cost = shipper.costOf(goal.prod size, goal.user art)) a0 K(goal.user art = user.article)a0 K(goal.prod size = producer.sizeOf(goal.user art))a0 K(goal.user loc = user.location)

The knowledge-level representation of the composition goal defines therefore a further knowledge base, that we call the knowledge base of the goal.

The knowledge-level planning domain a0 is obtained by combining the knowledge bases of the component services and the knowledge base of the goal, by instantiating the input and output actions of the component services on goal variables, and by adding the private actions obtained by applying goal functions to goal variables.

Definition 6 (Knowledge-level Planning Domain)

The planning domain a0 for a composition problem is an STS ✁ ✂ ☎ ✂ ✞ ☎ ✡ ☎ ✌ ☎ ✏ ☎ ✓ ☎ ✕ ✖ defined as follows:

• a0 the set of states ✂ are all the possible ❩ ❬ defined on the set of typed variables ✄ ❀ ☎ ✝ ✟ ✞ ✆ ✆ ✆ ✐ ✄ ✝ and on the set of typed functions ✡ ❀ ☎ ✝ ✟ ✞ ✆ ✆ ✆ ✐ ✡ ✝ , where ✄ ❢ ☎ ❣ ❣ ❣ ☎ ✄ ✐ and ✡ ❢ ☎ ❣ ❣ ❣ ☎ ✡ ✐ are the variables and functions of the component services, while ✄ ✞ and ✡ ✞ are those of the composition goal;
• a0 ✂ ✞ ✙ ✂ is the set of initial states corresponding to the initial knowledge bases ❩ ❬ ❢ ✞ ☎ ❣ ❣ ❣ ☎ ❩ ❬ ✐ ✞ , obtained from the initial assignments of the component services;
• a0 ✡ is the set of input actions ✘ ✥ ❫ ❢ ☎ ❣ ❣ ❣ ☎ ❫ ✐ ✯ such that ✘ ✥ ❛ ❢ ☎ ❣ ❣ ❣ ☎ ❛ ✐ ✯ is an input action in a transition of a component service and ❫ ❢ ☎ ❣ ❣ ❣ ☎ ❫ ✐ are goal variables with the same type of service variables ❛ ❢ ☎ ❣ ❣ ❣ ☎ ❛ ✐ ;
• a0 ✌ is the set of output actions ✞ ✥ ❫ ❢ ☎ ❣ ❣ ❣ ☎ ❫ ✐ ✯ such that ✞ ✥ ❛ ❢ ☎ ❣ ❣ ❣ ☎ ❛ ✐ ✯ is an output action in a transition of a component service and ❫ ❢ ☎ ❣ ❣ ❣ ☎ ❫ ✐ are goal variables with the same type of service variables ❛ ❢ ☎ ❣ ❣ ❣ ☎ ❛ ✐ ;
• a0 ✏ is the set of private actions ❫ ✞ ✲ ❀ ❞ ✥ ❫ ❢ ☎ ❣ ❣ ❣ ☎ ❫ ✐ ✯ where ❞ is a goal function and ❫ ✞ ☎ ❫ ❢ ☎ ❣ ❣ ❣ ☎ ❫ ✐ are goal variables compatible with the type of ❞ ;
• a0 ✓ is the set of transitions ✆ ❀ ✁ ❊ ☎ ✁ ✿ ☎ ❊ ◆ ✖ , with ❊ ☎ ❊ ◆ ❍ ✂ , such that:
• if ✁ ✿ is an input, output or ✄ action, then there exists a ✞ ❀ ✥ ✟ ☎ ✁ ☎ ✡ ✯ in the sets of transitions of the component services such that ✧ ★ ★ ✪ ✬ ✮ ✧ ✯ ✪ ✱ ✳ ✞ ✵ ✥ ❊ ☎ ✁ ✿ ✯ and ❊ ◆ ❀ ✱ ✿ ✱ ✮ ✳ ✞ ✵ ✥ ❊ ☎ ✁ ✿ ✯ ;
• if ✁ ✿ is a private action of the form ❫ ✞ ✲ ❀ ❞ ✥ ❫ ❢ ☎ ❣ ❣ ❣ ☎ ❫ ✐ ✯ , then ❩ ❪ ✥ ❫ ❢ ✯ ☎ ❣ ❣ ❣ ☎ ❩ ❪ ✥ ❫ ✐ ✯ ❍ ❊ and ❊ ◆ ❀ ✜ ✠ ✢ ✁ ✞ ✒ ✥ ❊ ☎ ❫ ✞ ✲ ❀ ❞ ✥ ❫ ❢ ☎ ❣ ❣ ❣ ☎ ❫ ✐ ✯ ✯ ;
• a0 ✕ is the trivial function associating to each state the set of propositions that hold in that state.

Given the domain a0 described above, we can apply the approach presented in [Pistore et al., 2005] and obtain a deadlock free a0 ✿ that controls a0 by satisfying the composition requirements ❳ . Despite of the fact that the synthesized controller a0 ✿ is modelled at the knowledge level, its elementary actions model communication with the component services (sending and receiving of messages) and manipulation of goal variables; given this, it is straightforward to obtain the executable BPEL4WS composite service from a0 ✿ .

5 Experimental Evaluation

We have implemented the proposed approach, and used the planning as symbolic model checking techniques presented in [Pistore et al., 2005] to perform an experimental evaluation. All the tests have run on a 3 GHz Xeon PC, limiting memory usage to 512MBytes, and with a CPU timeout of 1000 seconds.

We first considered the P&S example explained in the previous sections, which, in spite of the reduced number of components, requires a rather intricated protocol to be established for achieving the goal. Figure 4 shows the results of our experiments. The same planning engine is run to perform knowledge-level composition and ground level compositions, where different ranges of values can be produced and exchanged by the Shipper, Producer and User. The horizontal axis reports the cardinality a0 of the data types (i.e. Size, Location, Cost, Delay) handled by the services. We also consider intermediate cases where we have, for instance, two possible values for the Cost and only one value for the Size), reporting the average cardinality in the figure. On the vertical axis, we report the composition time. As expected, ground level composition is only feasible for the unrealistic cases where processes may exchange only data with 2 or at most 3 values. Indeed, the time for ground composition grows exponentially with the cardinality of the data types, and even the simple case where types have cardinality 4 is unmanageable. On the contrary, knowledge-level composition takes about 10 seconds to complete, with a performance similar to that of the ground level for a0 ❀ ✷ . This is a reasonable result, since, basically, binary variables at the ground level correspond to (binary) knowledge atoms at the knowledge-level.

To evaluate the scalability of the knowledge-level approach when the number of component services grows, we perform two sets of experiments, considering a generalization of the example domain that involves a set of component services. In our first set of experiments, each component is represented by a very simple abstract BPEL4WS process that is requested to provide a service and can respond either by performing the service, or by refusing. The composition requirement is that either all services end successfully, or a failure is reported to the invoker of the composed service. Figure 5 reports the knowledge-level composition times, for increasing number of services to be composed (indicated on the horizontal axis). The composition achieves results comparable to those reported in [Pistore et al., 2005], where ground composition is performed only considering the case of types with range of cardinality 2. We manage to compose 14 services in 20 minutes.

In the second set of experiments, also reported in Figure 5, we make the protocol more complex, by requiring a higher degree of interleaving between components. Here, the interactions with each component are more complex than a single invoke-response step, and, to achieve the goal, it is necessary to carry out interactions with all components in an interleaved way. Such interleaving is common in the P&S example where, e.g., the P&S cannot confirm the order to the producer if shipping is not available or if the user does not accept the offer. The increased complexity reflects on the complexity of the composition; however, compositions of reasonable complexity (up to 8 services) can be achieved within 20 minutes. Even in this case, automated composition takes a rather low amount of time, surely faster than manual development of BPEL4WS code.

6 Conclusions and RelatedWork

In this paper, we have shown how automated composition can be obtained by translating automatically process-level descriptions of web services, e.g., BPEL4WS processes, to a planning problem that describes the interactions among services at the knowledge level. Our solution exploits the framework for planning in asynchronous domains presented in [Pistore et al., 2005]. We show experimentally how the knowledge level approach increases significantly the practical applicability of this framework.

The idea of planning at the knowledge level is not new, and the solution that we propose is based on the idea presented in [Petrick and Bacchus, 2002]. Notice however that our work addresses an orthogonal problem, i.e., the problem of how a knowledge-level planning domain can be automatically generated from a set of BPEL4WS processes that describe web services. Moreover, at the technical level, our works differs from those proposed in [Petrick and Bacchus, 2002] in the kind of information that we represent and store in the knowledge bases, as well as in the knowledge-level planning domain that we automatically generate, and in the planning algorithm we exploit.

The work in [Martinez and Lesperance, 2004] shows how to use the knowledge level planner presented in [Petrick and Bacchus, 2002] to solve service composition problems. However they deal only with atomic services (services exporting a single operation instead of a protocol) and the knowledge level domain (e.g. domain action specification, update rules) is written by hand.

Different automated planning techniques have been proposed to tackle the problem of service composition, see, e.g., [Wu et al., 2003; Sheshagiri et al., 2003]. However, most of them cannot deal with the problem that we address in this paper, since they cannot deal with conditional outputs, uncertain action effects, and partial observability. A remarkable exception is the work described in [Narayanan and McIlraith, 2002; McIlraith and Son, 2002; McIlraith and Fadel, 2002], which instead deals with sensing actions and knowledge level predicates. However, even in this work, the knowledge level domain is given by hand, and the problem of devising a knowledge base that can be generated automatically from BPEL4WS web services descriptions is not addressed. Moreover, the composition problem is limited to sequential compositions of services.

The work in [Hull et al., 2003] presents a formal framework for composing e-services from behavioral descriptions given in terms of automata; they focus on the theoretical foundations, without providing practical implementations. Moreover, the considered e-composition problem is fundamentally different from our process-level composition, since it is seen as the problem of generating a set of rules coordinating the execution of the available services. No concrete and executable process is generated with that approach. This is the main difference also with the work described in [Berardi et al., 2003].

In the future, we plan to extend the work to the automated composition of semantic web services, e.g., described in OWL-S [OWL-S, 2003], along the lines of the work in [Traverso and Pistore, 2004], which at the moment is not based on knowledge-level planning. We will also explore variants of our knowledge base, so to allow flexible ways to model different features of ground level domains.

Acknowledgements This work is partially funded by the MIUR-FIRB project RBNE0195K5, "Knowledge Level Automated Software Engineering", and by the MIUR-PRIN 2004 project "Advanced Artificial Intelligence Systems for Web Services". The authors want to thank all members of the Astro project (http://astroproject.org/) for their collaboration and their feedback.