Semantic Web Service Automatic Composition Based on Discrete Event Calculus

Abstract

A semantic Web service automatic composition method based on discrete Event Calculus is proposed aiming at the issues of service AI planning composition such as large number of services and the confine of sequence composition process. Firstly, the extension of EC to DEC is present. Then the eight basic semantic Web service composition processes and their IOPE are modeled based on the actions, fluent and axioms of DEC. The service composition process is divided into two steps, abstract service planning and instance execution. And the service automatic composition framework is introduced. Also the abduction DEC planning method and semantic matching method of instance execution are given. The comparison indicate the superiority of this method: it solves the confine of sequence composition process of classic AI planning composition method with Event Calculus’ presentation of compound action, concurrent action, continuous action, knowledge of the agent and the predicate number of the DEC is much smaller than EC which speed the service discovering and composition.

49.1 Introduction

Emerging semantic Web services standards as OWL-S [1] enrich Web service standards like WSDL and BPEL4WS with rich semantic annotations to facilitate flexible dynamic web services discovery, invocation and and composition. The semantic description of function interface and behaviour of Web service can be provided by OWL-S, but it does not contain automated reasoning mechanism and does not support automatic service discovery and composition of semantic Web services. The key technology of automatic service composition is using semantic match and automated reasoning mechanism. The automatic semantic Web service composition methods contain method based on workflow, method based on intelligent planning, method based on formal description and so on [2]. The intelligent planning method shortening as AI is very popular and mature in Web service composition and can be implemented in some tools such as JSHOP and Prolog. The AI composition methods contains Hierarchy Task Network (HTN) [3], Situation Calculus [4], PDDL [5], dynamic, description logic [6], theorem prover [7] and so on. But they have two shortcomings: large number of services and the confine of sequence composition process.

Event Calculus is one of the convenient techniques for the automated composition of semantic web services. The Event Calculus (EC) is a temporal formalism designed to model and reason about scenarios described as a set of events whose occurrences have the effect of starting or terminating the validity of determined properties of the world. The one that will be used in this paper is the one defined by Shanahan [8]. The Event Calculus is based on first-order predicate calculus, and is capable of representing actions with indirect effects, actions with non-deterministic effects, compound actions, concurrent actions, and continuous change. Agarwal [9] presents a classification of existing solutions into four categories (approaches): interleaved, monolithic, staged and template-based composition and execution. Okutan [10] proposes the application of the abductive Event Calculus to the web service composition and execution problem about the interleaved and template-based type. Ozorhan [11] presents a monolithic approach to automated web service composition and execution problem based on Event Calculus. But they all have large numbers of predicates and the compose speed of them is slow. The discrete Event Calculus (DEC) has been proven to be logically equivalent with EC, when the domain of time points is limited to integers [12]. The DEC can eliminate the triply quantified axioms that lead to an explosion of the number of predicates.

In this paper, the Abductive Planning of the discrete Event Calculus is used to show that when atomic services are available. The service composition process is divided into two steps, abstract service planning and instance execution. And the service automatic composition framework is introduced and semantic matching method of instance execution is given.

49.2 Discrete Event Calculus

49.2.1 Event Calculus

The Event Calculus is based on first-order predicate calculus, and is capable of representing a variety of phenomena, including actions with indirect effects, actions with non-deterministic effects, compound actions, concurrent actions, and continuous change. The basic ontology of the Event Calculus comprises actions or events (or rather action or event types), fluents and time points. Table 49.1 introduces the language elements of the Event Calculus.

Table 49.1 Event calculus predicates in classical logic

The axioms of the Event Calculus relating the various predicates together are as follows:

$$ holdsAt\left( {F,T} \right) \leftarrow initially_{P} \left( F \right) \wedge \neg clipped\left( {F,0,T} \right) $$

(49.1)

$$ holdsAt\left( {F,T} \right) \leftarrow happens\left( {E,T_{0} } \right) \wedge initiates\left( {E,F,T_{0} } \right) \wedge T_{0} < T \wedge \neg clipped\left( {F,T_{0} ,T} \right) $$

(49.2)

$$ clipped\left( {F,T_{0} ,T_{1} } \right) \leftrightarrow \exists \begin{array}{*{20}c} {E,T\begin{array}{*{20}c} {happens\left( {E,T} \right)} \\ \end{array} } \\ \end{array} \wedge T_{0} \le T \wedge T \le T_{1} \wedge terminates(E,T,F) $$

(49.3)

$$ declipped\left( {F,T_{0} ,T_{1} } \right) \leftrightarrow \exists \begin{array}{*{20}c} {E,T\begin{array}{*{20}c} {happens\left( {E,T} \right)} \\ \end{array} } \\ \end{array} \wedge T_{0} \le T \wedge T \le T_{1} \wedge initiates\left( {E,F,T} \right) $$

(49.4)

49.2.2 DEC

The axioms of DEC utilize a subset of the EC elements (Table 49.1), that is happens, holds At, initiates and terminates. The axioms that determine when a fluent holds, are defined as follows:

$$ holdsAt\left( {F,T + 1} \right) \leftarrow happens\left( {E,T} \right) \wedge initiates\left( {E,F,T} \right) $$

(49.5)

$$ holdsAt\left( {F,T + 1} \right) \leftarrow holdsAt\left( {F,T} \right) \wedge \neg \exists E\begin{array}{*{20}c} {} \\ \end{array} happens\left( {E,T} \right) \wedge terminates\left( {E,F,T} \right) $$

(49.6)

Compared to EC, DEC axioms are defined over successive timepoints. Additionally, the DEC axioms are quantified over a single time point variable. Therefore the number of predicates is substantially smaller than EC. Axioms (49.6), however, contain the existentially quantified variable E. Each of these axioms will be transformed into $2^{\left| \varepsilon \right|}$clauses. Moreover, each clause will contain a large number of disjunctions. To overcome the creation of $2^{\left| \varepsilon \right|}$clauses, we can employ the technique of subformula renaming, as it is used in [12]. According to this technique, the subformula $happens\left( {E,T} \right) \wedge initiates\left( {E,F,T} \right)$ in (49.5), is replaced by a utility predicate that applies over the same variables, e.g. $startAt\left( {E,F,T} \right)$. A corresponding utility formula, i.e. $startAt\left( {E,F,T} \right) \leftrightarrow happens\left( {E,T} \right) \wedge initiates\left( {E,F,T} \right)$, is then added to the knowledge base.

In order to eliminate the existential quantification and reduce further the number of variables, we adopt a similar representation as in [12], where the arguments of initiation and termination predicates are only defined in terms of fluent and time points—represented by the predicates initiated At and terminated At respectively. As a result, the domain-independent axioms of DEC presented above are universally quantified over fluents and time points. The axioms that determine when a fluent holds are thus defined as follows:

$$ holdsAt\left( {F,T + 1} \right) \leftarrow initiatedAt\left( {F,T} \right) $$

(49.7)

$$ holdsAt\left( {F,T + 1} \right) \leftarrow holdsAt\left( {F,T} \right) \wedge \neg terminatedAt\left( {F,T} \right) $$

(49.8)

49.3 Service Automatic Composition Method Based on DEC

49.3.1 The Basic Service Processes Translation to DEC

In OWL-S the composite processes are composed of sub-processes and specify constraints on the ordering and conditional execution of the sub-processes. The minimal set of control constructs according to includes Sequence, Split, Split +Join, Any-Order, Choice, If–Then-Else, Repeat-While and Repeat-Until. These constructs are translated automatically into compound events in our framework.

Translations of the sequence control construct:

$$ \begin{gathered} axiom\left( {happens\left( {pSequenceExample\left( {Inputs,Outputs} \right)} \right.,T_{0} ,T_{m} } \right.),\, \hfill \\ [happens\left( {pProcess_{1} \left( {Inputs_{1} ,Outputs_{1} } \right),T_{1} ,T_{2} } \right),happens\left( {pProcess_{2} \left( {Inputs_{2} ,Outputs_{2} } \right),T_{3} ,T_{4} } \right), \ldots ,\, \hfill \\ happens\left( {pProcess_{n} \left( {Inputs_{n} ,Outputs_{n} } \right),T_{x} ,T_{y} } \right),before\left( {T_{0} ,T_{1} } \right),before\left( {T_{1} ,T_{3} } \right), \ldots ,before\left( {T_{x} ,T_{m} } \right) \hfill \\ ]) \hfill \\ Input_{i} \subseteq Inputs \cup \bigcup\limits_{j = 1}^{i - 1} {Outputs_{j} } \quad for\,i = 1, \ldots ,n \quad Outputs \subseteq \bigcup\limits_{i = 1}^{n} {Outputs_{i} } \hfill \\ \end{gathered} $$

Translations of the Split control construct:

$$ \begin{gathered} axiom\left( {happens\left( {pSplitExample\left( {Inputs,Outputs} \right)} \right.,T_{0} ,T_{m} } \right.),\, \hfill \\ [happens\left( {pProcess_{1} \left( {Inputs_{1} ,Outputs_{1} } \right),T_{1} ,T_{2} } \right),happens\left( {pProcess_{2} \left( {Inputs_{2} ,Outputs_{2} } \right),T_{3} ,T_{4} } \right), \ldots ,\, \hfill \\ happens\left( {pProcess_{n} \left( {Inputs_{n} ,Outputs_{n} } \right),T_{x} ,T_{y} } \right),\left. {before\left( {T_{0} ,T_{1} } \right),before\left( {T_{0} ,T_{3} } \right), \ldots ,before\left( {T_{0} ,T_{x} } \right)} \right]) \hfill \\ \end{gathered} $$

$$ Inputs_{i} \subseteq Inputs \quad for\;i = 1,2, \ldots ,n \quad Outputs \subseteq \bigcup\limits_{j = 1}^{n} {Outputs_{j} } $$

Translations of the Split–Join control construct:

$$ \begin{gathered} axiom\left( {happens} \right.\left( {pSplitJoinExample\left( {Inputs,Outputs} \right),T_{0} ,T_{m} } \right), \hfill \\ \left[{happens\left( {pProcess_{1} \left( {Inputs_{1} ,Outputs_{1} } \right),T_{1} ,T_{2} } \right)} \right.,happens\left( {pProcess_{2} \left( {Inputs_{2} ,Outputs_{2} } \right),T_{3} ,T} \right),..., \hfill \\ happens\left( {pProcess_{n} \left( {Inputs_{n} ,Outputs_{n} } \right),T_{x} ,T_{y} } \right),before\left( {T_{0} ,T_{1} } \right),before\left( {T_{0} ,T_{3} } \right),...,before\left( {T_{0} ,T_{x} } \right), \hfill \\ \left. {\left. {before\left( {T_{2} ,T_{m} } \right),before\left( {T_{4} ,T_{m} } \right),...,before\left( {T_{y} ,T_{m} } \right)} \right]} \right) \hfill \\ \end{gathered} $$

Translations of the If–Then–Else control construct:

$$ \begin{gathered} axiom\left( {happens\left( {pIfThenElseExample\left( {Inputs,OutPuts} \right),T_{0} ,T_{m} } \right)} \right., \hfill \\ \left[ {happens\left( {jpl\_\,{pIfCondition}\left( {Inputs_{1} } \right),T_{1} ,T_{2} } \right)} \right.,happens\left( {pThenCase\left( {Inputs,Outputs} \right),T_{3} ,T_{4} } \right), \hfill \\ \left. {\left. {before\left( {T_{0} ,T_{1} } \right),before\left( {T_{2} ,T_{3} } \right),before\left( {T_{4} ,T_{m} } \right)} \right]} \right) \hfill \\ \end{gathered} $$

$$ \begin{gathered} axiom\left( {happens\left( {pIfThenElseExample\left( {Inputs,OutPuts} \right),T_{0} ,T_{m} } \right)} \right., \hfill \\ \left[ {happens\left( {jpl\_\,pElseCondition\left( {Inputs_{1} } \right),T_{1} ,T} \right)} \right.,happens\left( {pElseCase\left( {Inputs,Outputs} \right),T_{3} ,T_{4} } \right), \hfill \\ \left. {\left. {before\left( {T_{0} ,T} \right),before\left( {T_{2} ,T_{3} } \right),before\left( {T_{4} ,T_{m} } \right)} \right]} \right) \hfill \\ \end{gathered}$$

Translation of the Repeat-While control construct:

$$ \begin{gathered} axiom\left( {happens\left( {pRepeatWhileExample\left( {Inputs,OutPuts} \right),T_{0} ,T_{m} } \right)} \right., \hfill \\ \left[ {happens\left( {jpl\_\,pLoopCondition\left( {Inputs_{1} } \right),T_{1} ,T_{2} } \right),} \right.happens\left( {pWhilecase\left( {Inputs,Outputs} \right),T_{1} ,T_{3} } \right), \hfill \\ \left. {\left. {before\left( {T_{0} ,T_{1} } \right),before\left( {T_{1} ,T_{2} } \right),before\left( {T_{1} ,T_{3} } \right),before\left( {T_{3} ,T_{m} } \right)} \right]} \right) \hfill \\ \end{gathered} $$

49.3.2 Web Service Automatic Composition Framework

The Web service automatic composition framework is in Fig. 49.1. The framework is divided into two steps: abstract service planning and instance execution. The steps of the workflow are: convert OWL-S descriptions and user inputs and outputs to the discrete Event Calculus axioms; execute the abductive theorem prover to generate plans; convert the generated plans to graphs; convert the selected graphs to OWL-S service files; execute the selected OWL-S service composition.

Fig. 49.1

The service automatic composition framework based on DEC

49.3.3 Abstract Service Planning

49.3.3.1 Translation of IOPE to DEC Axioms

The input and output of Web service translation to DEC are as follows:

$$\begin{gathered} axiom\left( {initiatedAt} \right)\pi \left( {web\_service\_event\left( {I_{1} ,I_{2} ,...,I_{k} ,O_{1} ,O_{2} ,...,O_{j} } \right),known\left( {out\_parameter\_name_{i} ,O_{i} } \right),T} \right), \hfill \\ \left[ {holdsAt} \right.\left( {known\left( {in\_parameter\_name_{1} ,I_{1} } \right),T} \right),...,holdsAt\left( {known\left( {in\_parameter\_name_{k} ,I_{k} } \right),T} \right), \hfill \\ \left. {\left. {holdsAt\left( {precondition_{1} ,T} \right),...,holdsAt\left( {precondition_{p} ,T} \right)} \right]} \right) \hfill \\ \end{gathered} $$

The precondition of Web service translation to DEC is as follows:

$$ \begin{gathered} axiom\left( {happens\left( {pPreconditionExample\left( {Input_{1} ,Input_{2} } \right),T_{1} ,T_{N} } \right)} \right., \hfill \\ \left[ {jpl} \right.\_pPrecondition\left( {Input_{1} ,Input_{2} } \right),atom\_number\left( {Input_{1} ,Arg_{1} } \right), \hfill \\ \left. {\left. {atom\_number\left( {Input_{2} ,Arg_{2} } \right),Arg_{1} < Arg_{2} ,\left[ {Other\;Events\;and\;Temporal\;Orderings} \right] \ldots } \right]} \right) \hfill \\ \end{gathered} $$

The effect of Web service translation to DEC is as follows:

$$ \begin{gathered} axiom\left( {initiatedAt\left( {web\_service\_event\left( {I_{1} ,I_{2} , \ldots ,I_{k} ,O_{1} ,O_{2} , \ldots ,O_{j} } \right)} \right.} \right.,effect\_e_{i} ,T), \hfill \\ \begin{array}{*{20}c} {} & {\left[ {holdsAt\left( {known\left( {in\_parameter\_name_{1} ,I_{1} } \right),T} \right), \ldots ,} \right.} \\ \end{array} holdsAt\left( {known\left( {in\_parameter\_name_{k} ,I_{k} } \right),T} \right), \hfill \\ \begin{array}{*{20}c} {} & {holdsAt\left( {precondition_{1} ,T} \right)} \\ \end{array} , \ldots ,\begin{array}{*{20}c} {}{holdsAt\left( {precondition_{p} ,T} \right)} \\ \end{array} \left. {\left. {} \right]} \right) \hfill \\ \end{gathered}$$

Here $effect\_e_{i}$ is the Prolog translation of the effect name taken from the has effect section of the service profile.

49.3.3.2 Abductive DEC Planning Algorithm

Abduction is used over the Event Calculus axioms to obtain partially ordered sets of events. Abduction is handled by a second order Abductive Theorem Prover (ATP) in [13]. The ATP tries to solve the goal list by proving the elements one by one. During the resolution, abducible predicates are stored in a residue to keep the record of the narrative. The narrative is a sequence of time-stamped events. In the definition of the predicate abduce, GL denotes the goal list, RL represents the residue list, NL represents the residue of negated literals, G is the axiom head and AL is the axiom body.

$$ AH \leftarrow AB_{1} \wedge AB_{2} \wedge \ldots \wedge AB_{N} \quad axiom\left( {AH,\left[ {AB_{1} ,AB_{2} , \ldots ,AB_{N} } \right]} \right) $$

$$ abduct\left( {GL,RL} \right) \leftarrow abduct\left( {GL,\square{},RL,\square{}} \right)\;\;abduct\left( {\square{},RL,RL,NL} \right) $$

$$ \begin{gathered} abduct\left( {\left[ {holdsAt\left. {\left( {F,T} \right)} \right|GL} \right],CurrRL,RL,NL} \right) \leftarrow axiom\left( {initially\left( F \right),AL} \right), \hfill \\ \begin{array}{*{20}c} {} & {irresolvable\left( {clipped\left( {0,F,T} \right),CurrRL,NL} \right)} \\ \end{array} ,append\left( {AL,GL,NewGL} \right), \hfill \\ \begin{array}{*{20}c} {} & {abduct\left( {NewGL,CurrRL,RL,\left[ {\left. {clipped\left( {0,F,T} \right)} \right|NL} \right]} \right)} \\ \end{array} \hfill \\ \end{gathered} $$

$$ \begin{gathered} abduct\left( {\left[ {\left. {holdsAt\left( {neg\left( F \right),T} \right)} \right|GL} \right],R1,R3,N1,N4} \right) \leftarrow axiom\left( {initially\left( {neg\left( F \right)} \right),AL} \right), \hfill \\ \begin{array}{*{20}c} {} & \begin{gathered} irresolvable\left( {declipped\left( {0,F,T} \right),CurrRL,NL} \right),append\left( {AL,GL,NewGL} \right), \hfill \\ abduct\left( {NewGL,CurrRL,RL,\left[ {de\left. {clipped\left( {0,F,T} \right)} \right|NL} \right]} \right) \hfill \\ \end{gathered} \\ \end{array} \hfill \\ \end{gathered} $$

49.3.4 Generating Output Graphs from the Results of the Planner

The Service-Oriented C⁴ISR system on the naval fields is taken as an example for generating output graphs from the results of the planner. Fig. 49.2 is the generating graph. There eight services are as follows: the surface target detection service $W_{1}$, the underwater target detection service $W_{2}$, the information process service $W_{3}$, the fire control compute service $W_{4}$, the missile launch service $W_{5}$, the torpedo launch service $W_{6}$, the efficiency evaluate service $W_{7}$, the repeat attack service $W_{8}$, St and En are the start and end services. The $W_{1}$ and $W_{2}$ are concurrent, then the $W_{3}$ is in sequence. The $W_{5}$ and $W_{6}$ are choice relation. The $W_{8}$ is loop with $W_{4}$, $W_{5}$, $W_{6}$ and $W_{7}$, and k is a small integer. The abstract service of the process is corresponding to an instance service set, and the QoS of the instance services are different according their equipments such as execute time, cost, and accuracy.

Fig. 49.2

Graph model of service-oriented C⁴ISR system on the naval fields

49.3.5 The Instance Service Matching Method

The instance service matching process is divided into two steps: the local semantic matching and the global QoS-ware matching. The local semantic matching is not only considering the input and output matching, but also the local semantic matching. The global QoS-ware matching is translated into a multi-objective services composition optimization with QoS constraints. The multi-objective estimation of distribution algorithm based on Independent Component Analysis is utilized to produce a set of optimal Pareto services composition with constraint principle by means of optimizing various objective functions simultaneously.

49.4 Conclusion

A semantic Web service automatic composition method based on discrete Event Calculus is proposed aiming at the issues of service AI planning composition method such as large number of services, the confine of sequence composition process. The eight basic semantic Web service composition processes and their IOPE are modeled based on the actions, fluent and axioms of DEC. The service composition process is divided into two steps, abstract service planning and instance execution. And the service automatic composition framework is introduced. Also the abduction DEC planning algorithm and semantic matching method of instance execution are given. The comparison indicate the superiority of this method: it solves the confine of sequence composition process of classic AI planning composition method with DEC’ presentation of compound action, concurrent action, continuous action, knowledge of the agent, the predicate number of the DEC is much smaller than EC which speed the service discovering and composition.