The paper deals with the abstract planning problem { a stage of the Web Service Composition in the Planics framework. The planning task is viewed from the graph perspective, searching a graph built of vertices representing service and object types, and edges connecting service types to object types processed by each corresponding service. The preprocessing search identi es all the service and object types, which can potentially participate in a plan bounded by the given length. Then, the planning problem is split into subproblems, at the basis of the relation of independence between the sets of object types listed in user query as the desired result of the composition. The ontology is divided into disjoint sub-ontologies, each of which contains only the types relevant for the respective set. If there is a sub-plan for every sub-ontology, the resulting plan is composed out of these sub-plans. The presented approach uses similarily de ned graphs, and makes use of planners as external tools, as in [Szr15] describing graph-based pruning of ontologies, however the aim is di erent. In [Szr15], there are removed all the service and object types which, for the given user query, cannot occur in any plan bound by a xed length. The current work optimizes planning in what is left by this reduction.
The key concept of Service-Oriented Architecture (SOA) [Erl05] consists in using independent (software) components available via well-de ned interfaces. Frequently, there is no web service directly satisfying the user objective, but a composition of services can deliver the requested result. An automatic composition of Web services should relieve the user of a manual preparation of detailed execution plans, matching services to each other, and of choosing optimal providers for all the components. The problem of nding such a composition is hard and well known as the Web Service Composition Problem (WSCP) [Erl05]. There is a number of various approaches to solve WSCP [LOKX10].
Automated composition of web services Web services are widely used to implement SOA paradigm, but much of their bene ts is revealed when they can be composed automatically. The existing solutions to WSCP are divided into several groups. Following [LOKX10] our approach belongs to AI planning methods, including also approaches based on: automata theory, situation calculus, Petri nets, automated theorem proving, and model checking.
In the paper [SPAS03] Sycara et.al. present DAML-S, the predecessor of OWL-S, which is one of the standards to describe Semantic Web services. The authors show how to compose services using the DAML-S virtual machine and matchmaking mechanism with a support of a planning-capable agent. Another approach to WSC using OWL-S is described in [KG05] where Klusch et.al. introduce the OWLS-Xplan framework.
Graph-based approaches to planning and web services composition Several papers use graph-based approach to the WSCP. An example is [HM06], where information about inputs and outputs of services is represented by interface automata. The key di erence between these papers and our approach is that we model matching of the service input and output at the graph level, by reducing it to the problem of testing reachability in graphs. Graph vertices model not only services, but also objects read and produced by services. Due to introducing the abstract planning we can reduce matching of service and object types to the problem of existing paths between selected graph vertices. The other approaches use graphs as a model for representing the state space, but test matching objects to services by calling specialized algorithms. This can hamper the performance. Another original feature is using graph databases for representing graphs and doing operations on them. To the best of our knowledge, we could also nd no experimental analysis showing that graph-based approaches can e ectively deal with ontologies with signi cant numbers of service and object types.
Graph databases [RWE13] are a relatively recent addition in the domain of the NoSQL databases, de ned by rejecting the traditional database model of relational tables, and using alternative solutions, in this case graphs. Neo4j [Lal15] is one of the most popular implementations. 2
For the e ciency reason, the planning process in Planicsis divided into two phases: abstract and concrete planning. The former deals with matching types, and the latter with matching the exact values of attributes. The current paper deals only with the former one. Here, we brie y recall the formulation of the abstract planning problem (APP) in Planics. We present only the intuitions, but all the formal de nitions can be found in [D+11].
Planics has much in common with well known approaches to composition of web services in the Semantic Web environment. One of similarities between Planics and DAML-S/OWL-S is the description of service capabilities. That is, both the approaches use the implicit capability representation, i.e., a service is described by the state transformation, its input, and output. This paradigm is often called IOPE - Input, Output, Precondition, E ect. Services process objects: read those placed in their input list, and write or produce those in output lists. In addition, objects from inout lists can be both read and written. We refer to all these lists as input and output lists. Objects have as attributes either primitive types such as integers, booleans, and strings, or other objects. Pre- and postconditions formulae, assigned to service types, determine the state of (some of) these attributes before and after executing the service. All the service and object types are organized in an inheritance hierarchy and represented in an ontology. A user query represents the aim of the composition, with similar input and output lists, and pre-/postcondition formulae as for services, determining the initial and the expected state of the composition process. The precisely de ned semantics de nes which sequences of services are the solution of the user query.
Semantics of abstract planning In abstract planning, the aim is to nd the abstract plan(s). A world is a set of objects with valuations assigned to their attributes. An transformation is an application of a service to an input world, producing an output world such that the valuations of objects from both worlds occuring in the lists for the service are consistent with the pre- and postcondition formulae. A solution is a sequence of service types, with a context function assigning instances of objects to the input and output list of every service. A solution explains which transformations are needed in order to deliver all the object types requested in the user query, with the appropriate attributes set or not. Note that the objects needed by services can be provided in the input lists of the user query, or by services producing objects while taking no input. Two solutions are equivalent if they contain the same number of occurences for every service type. An abstract plan is an equivalence class with respect to this relation, so that the irrelevant orderings of services are abstracted away.
Currently there are three Planics solvers, based on SMT [NP13], Genetic Algorithms (GA) [SNP13] and the hybrid (H) [NPS15] being the combination of SMT and GA. For testing the performance, an ontology generator has been implemented, with several parameters characterizing the randomly generated ontologies. These parameters include the minimal and maximal numbers of services, objects, object attributes, objects in service lists, and objects in the user query. The structure of the plans is determined by the number of partial orders out of which which every object from the nal world can be constructed.
The performance of the planners exhibits some general characteristics. SMT planner can handle smaller ontologies than GA, but nds all the plans and can determine that no plan exists at all. The hybrid planner combines the features of both SMT and GA planner. A common feature of all the planners is that their performance degrades when the length of the solutions increases. Also, all the plans found for the given depth need to be of the equal length.
Graph-based reduction of ontology In [Szr15] we have shown a graph-based pruning approach removing from an ontology all the service and object types which are not relevant for any plan of the given length, as determined by the user query. The search is implemented using a graph database. This improved signi cantly the performance of all the tested planners, and it corresponds to a typical scenario where only a small part of the ontology is relevant for the user query. Now we brie y describe this reduction.
First, the ontology graph is constructed for the given ontology, so that every service type and every object type are uniquely represented by a graph vertex. For every vertex representing a service type, there are incoming edges from vertices for the object types present in the input lists of the service, and there are outgoing edges to vertices for the object types in the output lists.
For the given user query, the additional two vertices are added to the ontology graph: the start and nal vertex. The start vertex has outgoing edges to every object type from the input lists of the user query. The nal vertex has incoming edges from every object type from the output lists of the user query. Then, we search for all the paths leading from start to nal vertex, yielding query k-subgraph Gqs. We proved that only the service and object types present in Gqs, with their supertypes and the subtypes of the object types from the query, can occur in any plan of the length bound by k, and all the other types can be pruned.
Some pruned ontologies are still hard for the planners. We diagnosed that the problem is caused by the length of the plans rather than by their number. Usually, even restricting the ontology with more plans only to the types occuring in a single plan does not improve the situation.
Paper contribution: nding sub-ontologies in the reduced ontology Now we will focus on more e cient planning for the ontologies pruned by the graph reduction. In particular, we identify the disjoint sub-ontologies which can be checked independently, so that the resulting plans can be composed by taking a sub-plan found for every sub-ontology. The sub-ontologies are identi ed by using the graph approach based on analysis of Gqs. In particular, for every object type occurring in the output lists of the user query, we de ne a Object Type Derivation Graph (OTDG) which is Gqs restricted to the paths going via the vertex representing this type.
Then, we introduce the independence relation between the subsets of object types occurring in the output lists of the user query. Two such subsets are independent i for every pair of object types from both these sets, their OTDGs are disjoint (have no common vertices). For every subset, the sub-ontology contains all the service and object types present in the OTDGs for the object types from the set, and the predecessors of these types. The user query is restricted to sub-queries accordingly.
The correctness of the reduction is shown in the following way. We claim that the set of plans generated by our construction at the basis of sub-plans found for every sub-ontology is equal to the set of plans for the k-reduced ontology. To show this, rst we prove that every plan composed of sub-plans for sub-ontologies is a plan in the k-reduced ontology. Then, we show that for every plan from the k-reduced ontology, there exists a plan composed from the elements of union of a sub-plan for every sub-ontology such that these two plans are equivalent.
Note that if there is no sub-plan for a sub-ontology, then no plan exists for the complete ontology.
Experiments We brie y describe experiments in which we compared the performance of two planners (SMT and GA) for three approaches: the full ontology (FO), the k-reduced ontology (RO) and the sub-ontologies (SO). The examine two groups of benchmarks produced by a scalable generator accepting several parameters. There are ve objects of distinct object types to be produced (njEW j = 5). 102 object types and 64 service types are present in every ontology. In the group A the length for every subplan is len = k=njEW j, compared to k being the length of every plan for FO and RO. There are 4 plans, because two object types can be produced in two ways, and other object types in a single way. In the group B, we scale the number of ways in which some two object types can be produced. The length of every plan is thus constant but the number of plans changes.
We implemented the described algorithm generating the k-query subgraphs for every query, and determining the sub-ontologies corresponding to the subgraphs determined by our independence relation. Its running time is very short (well below 1 second) for all the benchmarks presented in the paper.
A len = 2 + id1; njEWj = 5; k = 5 len, jpj = 4 B len = 2; k = 1S0M;nTjSEOWj = 5; jpj = 2id2 id13214567 jSp4444430Mj1T80TTTT87F2..OOOOO557t jSpM4444431jT35TTTT43R6..OOOOO820t jSpM4444444jTS0012233O.......4713929t jpG4420000jA12357F2020363.......O1677949t jGp3341000jA1134R1909642O.......9923947t j4444444GpAjS1111112O.......4335681t id223145 j13pS62482jM11637T128FTT065O...OO858t jS13p62482Mj385T864RTT419...OOO059t j13p62842j 11122t.....87701 jpG45266jA1F07676.....O41607t jGp64276AjR54475.....O27853t jG13p62482AjS11122O.....89613t
The conclusion is that the sub-plans are found very quickly, because they are much shorter than the complete plan. 3
As the experiments testify, the presented algorithm can shorten the planning times by several orders of magnitude, when it is applicable. Conceptually, it is di erent from the well-known partial-order reductions used in formal veri cation. The key di erence is that the latter approaches deal with global states, possibly pruning some executions not relevant for preserving the requested properties. Here we identify independent sub-systems at the basis of their local behavior.
The future research will consist in proposing weaker independence conditions, relaxing the requirement for disjoint OTDGs. Another research direction is to encode OTDGs directly into a planner. This would enable nding plans of di erent lengths for a xed depth bound. An ultimate aim is a fully graph-based planner directly exploating the structure of the problem.