Towards Automatic Non-Deterministic Web Service Composition.ppt
Download
Report
Transcript Towards Automatic Non-Deterministic Web Service Composition.ppt
Towards Automatic Non-Deterministic
Web Service Composition
Markou, G. & Refanidis, I.
Dept. of Applied Informatics, University of Macedonia, Greece
Tuesday, May 29, 2012
ICIW 2012 - Web Services-based Systems & Applications IV
In Summary
•
•
Introduction
Related Work
Method of Choice
o Use of Standards
o Online
o Evaluation
o
•
Proposed Approach
Translation between AI & Web Service languages
o Manual Web Service Composition module
o Automatic Web Service Composition module
Application
o Registry
o Web Service Editor
o
o
•
Evaluation
Quantitative criteria
o Use case scenarios
o
•
Conclusion
Tuesday, May 29, 2012
ICIW 2012 - Web Services-based Systems & Applications IV
2/31
•
Introduction
•
Related Work
Method of Choice
o Use of Standards
o Online
o Evaluation
o
•
Proposed Approach
o
o
o
o
o
o
•
Application
Registry
Web Service Editor
Translation between AI & Web Service languages
Manual Web Service Composition module
Automatic Web Service Composition module
Evaluation
Quantitative criteria
o Use case scenarios
o
•
Conclusion
Tuesday, May 29, 2012
ICIW 2012 - Web Services-based Systems & Applications IV
3/31
Motivation
• Difficult to expect from a human user /experts to manually
complete the goal of a Web Service Composition (WSC)
o Number of Web Services (WSs) is growing continuously
discovery phase more difficult
o Ever-changing environment: WSs can change interfaces or even part of
their usage multiple times throughout their lifespan
o Always possible that their execution is not successful
Tuesday, May 29, 2012
ICIW 2012 - Web Services-based Systems & Applications IV
4/31
System Goals - Functionalities:
•
•
•
•
•
•
•
Online
Registry / Advertisement / Semantic search of Web Services
Editing of Web Services
Translation/ mapping between AI & Web Service languages
Manual Web Service composition module
Automatic Web Service composition module
Evaluation based on
o Quantitative criteria
o Use case scenarios
Tuesday, May 29, 2012
ICIW 2012 - Web Services-based Systems & Applications IV
5/31
•
Introduction
•
Related Work
Method of Choice
o Use of Standards
o Online
o Evaluation
o
•
Proposed Approach
o
o
o
o
o
o
•
Application
Registry
Web Service Editor
Translation between AI & Web Service languages
Manual Web Service Composition module
Automatic Web Service Composition module
Evaluation
Quantitative criteria
o Use case scenarios
o
•
Conclusion
Tuesday, May 29, 2012
ICIW 2012 - Web Services-based Systems & Applications IV
6/31
Method of Choice (1/2)
• Most widespread: AI planning
• Diverse
• Method of choice?
• Use of standards?
o OWL-S / PDDL widely used
o Other standards (e.g., WSMO)
o Proprietary formats
Perhaps most notable is Sirin, et al. (2004)
o From WSC problem (described in OWL-S) to HTN
o Composite process that can be decomposed to simpler ones
Simple processes being atomic WSs
o Reduces complexity of the planning process
o Cannot cope with non-determinism
o Planner-dependent
Tuesday, May 29, 2012
ICIW 2012 - Web Services-based Systems & Applications IV
7/31
Method of Choice (2/2)
• AI planning also used in Hoffmann, et al. (2009)
o Treats the application of a WS as a belief update operation
o Identifies tractable special cases of WSC
Allow for a compilation
o
o
o
into planning under uncertainty
Subsequent use of existing conformant planner
PDDL-like problem descriptions
No standardized WS description
Tuesday, May 29, 2012
ICIW 2012 - Web Services-based Systems & Applications IV
8/31
Use of Standards
•
Klusch, Gerber & Schmidt (2005) and Hatzi, et al. (2011) rely
on translation of OWL-S descriptions to PDDL problems
o Klusch,
Gerber & Schmidt (2005):
files (in XML)
Does not have evaluation on WSC problems
Outputs modified PDDL
o Hatzi, et al. (2011) tackles uncertainty with re-planning module
o Both only address WSC problem, not other stages
Tuesday, May 29, 2012
ICIW 2012 - Web Services-based Systems & Applications IV
9/31
Online
•
YaWSA (Macdonald, 2007)
o Only web-based WSC system in literature with running demo
o Only implemented a WSC process (no registry, view WSs’, etc)
o No longer available for public use
•
Prototype web-based WSC system described in Du, Song,
and Munro (2006)
o
o
Supporting multiple phases of WSC
Public link to running demo of their implementation is not provided
Tuesday, May 29, 2012
ICIW 2012 - Web Services-based Systems & Applications IV
10/31
Evaluation
•
Literature suggests a gap in the evaluation process of the
current WSC systems
o Many simply evaluate their methodology on a single case study,
without referring to quantitative criteria, e.g., Chen, Xu, and ReiffMarganiec (2009), McDermott (2002), McIlraith and Son (2002)
•
Notable exceptions:
Hoffmann, et al. (2009) : Two artificial benchmarks with different encodings
and planners
o Hatzi, et al. (2011): Single use case, with different number of WSs
Test collection combination of hand-tailored atomic WSs and entire
domains of OWL-S Service Retrieval Test Collection (OWL-S TC)
o Kona, et al. (2008): Three versions of a single use case, each suited for a mode
of their WSC algorithm
Test collection: Modified version of the 2006 WS-Challenge
o
Tuesday, May 29, 2012
ICIW 2012 - Web Services-based Systems & Applications IV
11/31
•
•
Introduction
Related Work
Method of Choice
o Use of Standards
o Online
o Evaluation
o
•
Proposed Approach
o
o
o
o
o
o
•
Application
Registry
Web Service Editor
Translation between AI & Web Service languages
Manual Web Service Composition module
Automatic Web Service Composition module
Evaluation
Quantitative criteria
o Use case scenarios
o
•
Conclusion
Tuesday, May 29, 2012
ICIW 2012 - Web Services-based Systems & Applications IV
12/31
Proposed Approach - Application
User email
registration
Initial screen
Tuesday, May 29, 2012
Based on Google
Web Toolkit (GWT):
ICIW 2012 - Web Services-based Systems & Applications IV
13/31
Registry (1/2)
•
Core of the application is based on iServe
o Open platform for publishing and discovering services
o WSs are semantically
described in OWL-S, not Minimal Service Model
o Used its web-based application for
Browsing
Querying
Uploading services
o Populated the registry with version 4.0 of OWL-S TC
o Made several improvements to its interface and functionality
Tuesday, May 29, 2012
ICIW 2012 - Web Services-based Systems & Applications IV
14/31
Registry (2/2)
Inline
operations
Semantic
search
alternatives
Tuesday, May 29, 2012
ICIW 2012 - Web Services-based Systems & Applications IV
Web
Service
details
15/31
Proposed Approach – WS Editor
XML Editor
with syntax
highlighting
Pre-defined
OWL-S
templates
Tuesday, May 29, 2012
ICIW 2012 - Web Services-based Systems & Applications IV
16/31
Translation between AI & WS Languages
•
AI planning language: PDDL, the de facto planning language
o Specifically, NuPDDL
Compatible with PDDL2.1, retaining
most of it
Capable of modeling non-deterministic action effects (one of, unknown)
•
WS semantic description language: OWL-S, most widely used
o Heavily influenced from planning languages, such as PDDL
•
Partial mapping from OWL-S to PDDL exists
o Part of it straightforward:
input parameters identically named ones of PDDL action
hasPrecondition/ hasEffect parameters precondition/ effect of action
ServiceProfile
o Conversion of non-physical knowledge from OWL-S
to PDDL
problematic Introduction of new predicate in PDDL domain?
Tuesday, May 29, 2012
ICIW 2012 - Web Services-based Systems & Applications IV
17/31
Manual WSC Module
•
Under implementation
Based on PetalsBPM
Modification
from BPMN 2.0 editor to suit OWL-S WSC functionalities
To be compared with automatic WSC module (ease of use, speed, etc)
Tuesday, May 29, 2012
ICIW 2012 - Web Services-based Systems & Applications IV
18/31
Automatic WSC Module
•
Future work – Basic directions:
o WSs may fail to execute correctly, e.g.,
Unavailability of an atomic WS involved in the plan
Output of their successful execution
is not the expected one
o Generate plans tackling the most influential and likely contingencies
o Proposed solution based on contingent planning
Produce seed plan
Examine for significant/ likely points of failure
Add conditional
branches
Re-planning module will be integrated
Tuesday, May 29, 2012
ICIW 2012 - Web Services-based Systems & Applications IV
19/31
•
•
Introduction
Related Work
Method of Choice
o Use of Standards
o Online
o Evaluation
o
•
Proposed Approach
o
o
o
o
o
o
•
Application
Registry
Web Service Editor
Translation between AI & Web Service languages
Manual Web Service Composition module
Automatic Web Service Composition module
Evaluation
Quantitative criteria
o Use case scenarios
o
•
Conclusion
Tuesday, May 29, 2012
ICIW 2012 - Web Services-based Systems & Applications IV
20/31
Quantitative Criteria
•
Criteria to be considered:
o Number of Web Services considered for WSC
o Preprocessing time (parsing of ontologies’ concepts, etc)
o Transformation time (of WS domain to PDDL one)
o Planning time (to output a successful plan)
o Optimality of the outputted plans (least WSs used to achieve the
required goal)
Tuesday, May 29, 2012
ICIW 2012 - Web Services-based Systems & Applications IV
21/31
Use Case Scenarios
•
Based on OWL-S TC Semantic Web Services v. 4.0 (PDDL)
o Each scenario uses a subset of descriptions of an OWL-S TC domain
o A few semantic WS descriptions were added for testing purposes, and
some were modified
•
Each scenario with increasing non-determinism & complexity
Tuesday, May 29, 2012
ICIW 2012 - Web Services-based Systems & Applications IV
22/31
Movie Database Scenario (1/2)
1) Movie database search using a (partial) movie title
o Based on Communication domain: 58 semantic WSs in total
o Fully deterministic
- Serialized composite WS output
o Retrieve comedy films with titles similar to user input
o Output:
Movie titles
Pricing
Tuesday, May 29, 2012
information (tax-free price, recommended price, etc)
ICIW 2012 - Web Services-based Systems & Applications IV
23/31
Movie Database Scenario (2/2)
Composite Web Service (created through Manual WSC module)
Tuesday, May 29, 2012
ICIW 2012 - Web Services-based Systems & Applications IV
24/31
Online Bookstore Scenario (1/2)
2) Online bookstore product purchase
o User wants to purchase a book from an specific online bookstore with a
preferred method of payment
o Preferences regarding method of payment
o Based on Education domain: 285 semantic WSs in total
o Non-deterministic output
Different outcomes:
Output if book in stock:
Addition of book in shopping cart
Purchase with the specified method of payment
Output information regarding it, such as its author
Tuesday, May 29, 2012
No output if book not in stock
ICIW 2012 - Web Services-based Systems & Applications IV
25/31
Online Bookstore Scenario (2/2)
Composite Web Service (created through Manual WSC module)
Tuesday, May 29, 2012
ICIW 2012 - Web Services-based Systems & Applications IV
26/31
Camera Search Scenario (1/2)
3) Camera search and purchase
o User want to purchase an analog SLR model; willing to
settle for other ones if it is not in stock
User preference towards specific model
More than one sellers exist
o
o
Based on Economy domain: 359 semantic WSs in total
Possible iteration in output Web Service
Since more than one sellers exist, if product not available
at one, check another
If product not found in any of the sellers, try with other
versions (digital SLR, simple compact cameras)
Tuesday, May 29, 2012
ICIW 2012 - Web Services-based Systems & Applications IV
27/31
Camera Search Scenario (2/2)
Composite Web Service (created through Manual WSC module)
Tuesday, May 29, 2012
ICIW 2012 - Web Services-based Systems & Applications IV
28/31
•
•
Introduction
Related Work
Method of Choice
o Use of Standards
o Online
o Evaluation
o
•
Proposed Approach
o
o
o
o
o
o
•
Application
Registry
Web Service Editor
Translation between AI & Web Service languages
Manual Web Service Composition module
Automatic Web Service Composition module
Evaluation
Quantitative criteria
o Use case scenarios
o
•
Conclusion
Tuesday, May 29, 2012
ICIW 2012 - Web Services-based Systems & Applications IV
29/31
Conclusion
•
Current WSC approaches, in general:
o
o
o
Do not deal with inherent non-determinism in WSC domain
Are not online, despite WS’ use & nature being web-oriented
Do not evaluate their methodology using well defined
scenarios or test sets
Improvements have been made recently
•
•
Our final system is intended to be the first online and open
source system supporting multiple phases of WSC
Presented scenarios provide efficient way of evaluation
o
Can be used by other WSC works as a common test bed
Tuesday, May 29, 2012
ICIW 2012 - Web Services-based Systems & Applications IV
30/31
Thank you for your attention!
Questions?
Tuesday, May 29, 2012
ICIW 2012 - Web Services-based Systems & Applications IV
31/31
Tuesday, May 29, 2012
Extra Slides
ICIW 2012 - Web Services-based Systems & Applications IV
32/31
References:
Referenced papers:
•
•
•
•
•
•
•
•
•
•
E. Sirin, B. Parsia, D. Wu, J. Hendler, and D. Nau, “HTN planning for web service composition using SHOP2”, J. Web
Semant., vol. 1, no. 4, Oct. 2004, pp. 377-396.
J. Hoffmann, P. Bertoli, M. Helmert, and M. Pistore, “Message-based web service composition, integrity
constraints, and planning under uncertainty: a new connection”, J. Artif. Intell. Res, vol. 35, May 2009, pp.49-117.
M. Klusch, Α. Gerber, and M. Schmidt, “Semantic web service composition planning with OWLS-Xplan”, Proc. 1st
International AAAI Fall Symposium on Agents and the Semantic Web, Nov. 2005.
O. Hatzi, D. Vrakas, M. Nikolaidou, et al., “An integrated approach to automated semantic web service composition
through planning”, IEEE Trans. Service Computing, April 2011, pp. 301-308.
A. Macdonald, “Service composition with hyper-programming”. Technical Report, University of St Andrews, 2007.
X. Du, W. Song, and M. Munro, “Using common process patterns for semantic web services composition”, Proc.
15th International Conference on Information Systems Development (ISD’06), Sept. 2006.
K. Chen, J. Xu, and S. Reiff-Marganiec, “Markov-HTN planning approach to enhance flexibility of automatic web
service composition”, Proc. IEEE International Conference on Web Services (ICWS'09), July 2009, pp. 9-16.
D.V. McDermott, “Estimated-regression planning for interactions with web services”, Proc. Sixth International
Conference on Artificial Intelligence Planning Systems (AIPS ’02), April 2002, pp. 204-211.
S. McIlraith and T. Son, “Adapting Golog for composition of semantic web services”, Proc. 8th International
Conference on Principles of Knowledge Representation and Reasoning (KR2002), April 2002, pp. 482-496.
S. Kona, A. Bansal, M.B. Blake, and G. Gupta, “Generalized Semantics-Based Service Composition”, Proc. IEEE
International Conference on Web Services (ICWS’08), Sept. 2008.
Tuesday, May 29, 2012
ICIW 2012 - Web Services-based Systems & Applications IV