3. Methods
3.6 SWRL-based Semantic Web Service Composition
Section 3.5 proposed an approach to converting SAWSDL files referring to SWRL rules into OWL-S Processes. This section describes how the generated OWL-S de-scriptions can be used in semantic web service composition. The main difference to Section 3.3 is that now the condition and effect expressions may be formulated in SWRL instead of SPARQL, and therefore the planning solution presented in Sec-tion 3.3 is inapplicable. Furthermore, this secSec-tion presents an enhanced planner
3. Methods 60 component attached to Service Monitor. The planner can solve even relatively com-plex problems without a separate restriction expression, which the planner presented in Section 3.3 typically requires for other than the most trivial planning problems.
While the proposed composition approach is primarily based on the assumption that the service pre- and postconditions are expressed using SWRL, it can sup-port service descriptions using SPARQL as the expression language. However, the SPARQL expressions must be restricted to a relatively simple syntax that can be automatically translated to SWRL.
3.6.1 Composition Pattern Overview
The current version of Service Monitor supports the parallel achievement of several production goals. A new goal can be registered by invoking theStartGoal operation, which assigns the goal a unique identifier and initiates a process that first attempts to compose a solution plan for achieving the goal and then executes the plan. The process is automatically repeated until either the goal is achieved or the goal is terminated by invoking the StopGoal operation. The repeating of the process is required when either the AI planning algorithm fails to compose a solution plan for achieving the goal or the execution of the obtained plan fails.
Figure 3.11 illustrates the registration of a new goal and the subsequent goal achievement process through a sequence diagram. The main difference to the se-quence diagram of Figure 3.3 is that now the registering of new goals and their achievement is asynchronous. Furthermore, Service Monitor sendsGoalStatusChanged event notifications to registered subscribers as the status of a goal process changes.
Table 3.7 summarizes the new operations in the Service Monitor interface.
3.6.2 Requirements
The requirements for using the enhanced planner are as follows:
• The semantic web service descriptions use SWRL or SPARQL (with some syntax restrictions) in expressing conditions and effects.
• The number of objects in the domain model is constant.
SWRL has a somewhat simple syntax. Hence, when OWL-S Process conditions and effects are expressed in SWRL, it is relatively effortless to convert the Processes into planning operators that include both negative and positive conditions, as well as negative and positive effects. Nonetheless, the requirement of using SWRL is not absolute, since it is possible to automatically translate other languages, such as SPARQL, into SWRL. On the other hand, some SPARQL constructs are somewhat
3. Methods 61
Figure 3.11: TheStartGoal operation is invoked to initiate a new goal process.
Table 3.7: The Service Monitor interface provides operations for starting and terminating goal processes as well as for monitoring their progress.
Operation
challenging to translate into SWRL, and Service Monitor currently requires that such constructs are avoided if the SWRL-based planning approach is used.
3. Methods 62 The most critical requirement is that none of the OWL-S Processes creates new OWL instances in the domain model. In other words, the set of objects in the domain model must be numerable. The requirement allows the planning component to assign a unique ID number to each object. Thus, the planner can enumerate each statement built using the objects and predicates, as well.
3.6.3 Obtaining an AI Planning Problem
While the enhanced planner is conceptually based on PDDL, it internally uses a numeric representation of the domain and the planning operators. Nonetheless, the numeric model is used only in computations and can be rapidly converted into the human-readable PDDL syntax.
Before attempting to solve a planning problem, the planner instantiates all actions in the planning problem. The action instantiation includes first determining all of the applicable variable value combinations for each SWRL rule and then using each combination to create a new planning operator, whose conditions and effects refer only to ground instances. Thus, the number of the resulting planning operators is typically considerably larger than the original number of SWRL rules extracted from the OWL-Sprocesses. After the instantiation, the effects and conditions of each operator are sets of statements, which are internally represented as numbers. The planning goals are instantiated similarly, and therefore a goal can be instantiated to a set of alternative goals, each based on a different variable value combination.
After the aforementioned instantiation procedure, the input data used by the planning algorithm includes the following:
• the set of all possible statementsS ⊂Z
• the initial state I ⊂S
• the set of goal state alternatives G, where each g ∈ G is a tuple hg+, g−i, so that
– g+ ⊂S is the set of positive goals – g− ⊂S is the set of negative goals
• the instantiated actionsA, where eacha ∈Ais a tuplehpre+, pre−, post+, post−i, so that
– pre+⊂S is the set of positive preconditions – pre−⊂S is the set of negative preconditions – post+ ⊂S is the set of positive postconditions
3. Methods 63
– post− ⊂S is the set of negative postconditions
While different versions of the planner component can be developed, the forward search and backward search solutions appear the most viable. The backward search planner preprocesses the domain description by eliminating all negative precondi-tions from acprecondi-tions. The algorithm for eliminating negative precondiprecondi-tions is described in [24]. After the preprocessing step, the instantiated actions can be expressed as triples hpre, post+, post−i, where pre ⊂ S denotes the set of statements that must hold for the action to be applicable. However, the forward search algorithm de-scribed in the sequel includes no preprocessing phase.
3.6.4 The Domain-independent Planning Algorithm
Thus far, the forward search algorithm appears the most efficient solution, since it performs simple pruning of the state space by only considering those actions that can be relevant for the desired production goal. The state space pruning technique is essentially based on the concept of helpful actions described by Hoffmann and Nebel [29]. An actiona ∈Ais potentially relevant if it satisfies one of two conditions:
• The action directly achieves a proposition that is included in one of the alter-native production goals: ∃g ∈G:post+(a)∩g+ 6=∅ ∨post−(a)∩g−6=∅.
• The action directly achieves a proposition that is included in the conditions of another action: ∃a2 ∈A:post+(a)∩pre+(a2)6=∅ ∨post−(a)∩pre−(a2)6=∅.
The set of potentially relevant actions remains constant for each goal, and hence it is sufficient to compute it only once after instantiating the actions.
The planning algorithm is based on state space search. Each state is identified by the set of statements that hold in that state. As each statement is enumerated, the states are essentially sets of integers. However, the representation can be compacted by only representing a state as a set of integers indicating the differences to the initial state.
While forward search can be conducted in both Bread-First Search (BFS) and Depth-First Search (DFS) manner, BFS is more applicable to the planning algo-rithm, as it guarantees that only minimal solutions are discovered.
Algorithm 2 contains the pseudo-code for the planning algorithm. The forward search planning algorithm starts from the initial state and considers all potentially relevant actions to compute the successor states. As all successor states are added to a First-In, First-Out (FIFO) stack of unprocessed states, the search space nodes are processed in BFS-manner. Once the successor states have all been computed, the algorithm retrieves the first state in the stack and continues search. The algorithm
3. Methods 64 Algorithm 2 The forward search algorithm prunes the state-space by only consid-ering potentially relevant actions.
while U nprocessed 6=∅ do
choose the first nodeCurrent∈U nprocessed U nprocessed⇐U nprocessed\ {Current}
for all a∈Relevant do
if pre+(a)⊆Current∧pre−(a)∩Current=∅ then N ewState⇐Current∪post+(a)\post−(a)
Graph.nodes⇐Graph.nodes∪ {N ewState}
U nprocessed⇐U nprocessed∪ {N ewState}
Create a link between Currentand N ewState
if ∃g ∈G|g+ ⊆N ewState∧g−∩N ewState=∅ then return N ewState
else if |Graph.nodes|> maxN odeCount then return failure
end if end if end for end while
terminates if the state satisfies the goal or if there are no more unprocessed states in the stack. The latter case indicates that there is no solution for the planning problem. However, typically the amount of computing resources available is limited.
To avoid excessive use of resources, the search algorithm terminates after analyzing the number of nodes indicated by themaxNodeCount parameter, which may be set to, for example, 500000.
The output of Algorithm 2 is a state-space node that fulfills one of the alternative goals. The links in the search graph correspond to instantiated planning operators, each of which can be mapped to a source OWL-S Process and the appropriate se-lection of input parameter values. Hence, the planner can extract a sequence of semantic web service invocations that leads to a domain state fulfilling the goal ex-pression. However, executing such sequential solution plans may be unnecessarily slow, since only one operation is executed at a time. Therefore, the planner com-ponent incorporates an additional solution plan refinement phase transforming the sequence into a tree structure. The tree has a single root node, which corresponds to the initial state and a single leaf node, which corresponds to the terminal node of a plan execution. The links between the nodes correspond to OWL-S processes
3. Methods 65 and the associated input variable bindings. Each non-root and non-leaf node must have one or more of input links and output links.
The plan execution begins from the root node of the plan tree. When all input actions of a node have been executed, the output actions are executed in parallel.
The plan execution is completed when all input actions of the terminal node have been executed.