Abstract
Automatically composing Web services to form processes in the context of service-oriented architectures has attracted significant research. Prevalent approaches for automatically composing Web services predominantly utilize planning techniques to achieve the composition. However, classical planning based approaches face the following challenges: (i) difficulty in modeling the uncertainty of Web service invocations, (ii) inability to optimize the composition using non-functional parameters, and (iii) difficulty in scaling efficiently to large compositions. In order to address these issues, we present a hierarchical framework for logically composing Web services, which we call Haley. In comparison to classical planners, Haley utilizes decision-theoretic planning that is able to model and reason with the uncertainty inherent in Web service invocations and provides an expected cost-based optimization. Haley uses symbolic planning techniques that operate directly on first-order logic based representations of the state space to obtain the compositions. Consequently, it supports automated elicitation of the corresponding planning problem from Web service descriptions and produces a domain representation that is more compact than that of classical planners. Furthermore, it promotes scalability by exploiting the natural hierarchy found in real-world processes. Due to the limitations of the existing approaches and the complexity of the Web service composition problem, few implemented tools exist, although many approaches have been proposed in the literature. We have implemented Haley and provided a comprehensive tool suite for composing Web services. The suite operates on Web services described using well-known languages such as SAWSDL. It provides process designers with an intuitive interface to specify composition requirements, goals and a hierarchical decomposition if available, and automatically generates BPEL compositions while hiding the complexity of the planning and of BPEL from users.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Singh M, Huynhs M (2005) Service-oriented computing: semantics, processes and agents. Wiley, New York
Gudgin M, Hadley M, Mendelsohn N, Moreau JJ, Nielsen HF, Karmarkar A, Lafon Y (2007) Simple object access protocol (soap), version 1.2. http://www.w3.org/tr/soap12-part1
Chinnici R, Moreau JJ, Ryman A, Weerawarana S (2007) Web services description language (wsdl), version 2.0. http://www.w3.org/tr/2007/rec-wsdl20-20070626
Wu D, Parsia B, Sirin E, Hendler JA, Nau DS (2003) Automating DAML-S web services composition using SHOP2. In: International aemantic web conference (ISWC), pp 195–210
Kuter U, Sirin E, Nau D, Parsia B, Hendler J (2005) Information gathering during planning for web serivce composition. J Web Semant 3: 183–205
Rao J, Su X (2004) A survey of automated web service composition methods. In: Workshop on semantic web services and web process composition (SWSWPS), pp 43–54
McIlraith S, Son TC (2002) Adapting Golog for composition of semantic web services. In: International conference on principles and knowledge representation and reasoning (KR-02), Toulouse, France, pp 482–496
Medjahed B, Bouguettaya A, Elmagarmid AK (2003) Composing web services on the semantic web. VLDB J 12(4): 333–351
Traverso P, Pistore M (2004) Automated composition of semantic web services into executable processes. In: International semantic web conference (ISWC), pp 380–394
Pistore M, Marconi A, Bertoli P, Traverso P (2005) Automated composition of web services by planning at the knowledge level. In: International joint conferences on artificial intelligence (IJCAI), pp 1252–1259
Oh SC, Lee D, Kumara SRT (2007) Web service planner (wspr): an effective and scalable web service composition algorithm. Int J Web Serv Res (JWSR) 4: 1–22
Qiu L, Chang L, Lin F, Shi Z (2007) Context optimization of ai planning for semantic web services composition. J Serv Oriented Comput Appl 1(2): 117–128
Bylander T (1991) Complexity results for planning. In: International joint conference of artificial intelligence (IJCAI), pp 274–279
Blythe J (1999) Decision-theoretic planning. AI Mag 20(2): 37–54
Bellman RE (1957) Dynamic programming. Dover, New York
Doshi P, Goodwin R, Akkiraju R, Verma K (2005) Dynamic workflow composition: using markov decision processes. J Web Serv Res (JWSR) 2(1): 1–17
Zhao H, Doshi P (2006) A hierarchical framework for composing nested web processes. In: International conference on service oriented computing (ICSOC), pp 116–128
Martin DL, Burstein MH, McDermott DV, McIlraith SA, Paolucci M, Sycara KP, McGuinness DL, Sirin E, Srinivasan N (2007) Bringing semantics to web services with OWL-S. In: International world wide web conference (WWW), pp 243–277
Farrell J, Lausen H (2006) SAWSDL: semantic annotations for wsdl. http://www.w3.org/tr/sawsdl/
der Aalst WV, Hee KV (2004) Workflow management: models, methods and systems. MIT Press, Cambridge
Puterman M (1994) Markov decision processes: discrete stochastic dynamic programming. Wiley-Interscience, London
Boutilier C, Reiter R, Price B (2001) Symbolic dynamic programming for first-order MDPs. In: International joint conferences on artificial intelligence (IJCAI), pp 690–700
Holldobler S, Skvortsova O (2004) A logic-based approach to dynamic programming. In: Learning and planning in Markov processes-advances and challenges-AAAI 04 workshop, pp 31–36
Kersting K, Otterlo MV, Raedt LD (2004) Bellman goes relational. In: Twenty-first international conference on machine learning (ICML), pp 465–472
Hirtle D, Boley H, Grosof B, Kifer M, Sintek M, Tabet S, Wagner G (2006) Schema specification of RuleML. http://www.ruleml.org/0.91/
McCarthy J (1963) Situations, actions and causal laws. Technical report, AI Laboratory, Stanford University
Reiter R (2001) Knowledge in action: logical foundations for specifying and implementing dynamic systems. MIT Press, Cambridge
Sanner S, Boutilier C (2005) Approximate linear programming for first-order MDPs. In: Twenty-first conference in uncertainty in artificial intelligence, pp 509–517
Ludwig H, Keller A, Dan A, King R, Franck R (2003) Web service level agreement (wsla) language specification. http://www.research.ibm.com/wsla
Martin D, Burstein M, Hobbs J, Lassila O, McDermott D, McIlraith S, Narayanan S, Paolucci M, Parsia B, Payne T, Sirin E, Srinivasan N, Sycara K (2006) OWL-S: semantic markup for web services. http://www.daml.org/services/owl-s/1.1
Andrieux A, Czajkowski K, Dan A, Keahey K, Ludwig H, Nakata T, Pruyne J, Rofrano J, Tuecke S, Xu M (2007) Web services agreement specification (ws-agreement). http://forge.gridforum.org/sf/projects/graap-wg
Horrocks I, Patel-Schneider PF, Boley H, Tabet S, Grosof B, Dean M (2004) Swrl: a semantic web rule language combining owl and ruleml. http://www.w3.org/submission/swrl
Boutilier C, Reiter R, Soutchanski M, Thrun S (2000) Decision-theoretic, high-level agent programming in the situation calculus. In: Seventeenth conference on artificial intelligence, pp 355–362
Cimatti A, Pistore M, Roveri M, Traverso P (2003) Weak, strong, and strong cyclic planning via symbolic model checking. Artif Intell 147(1–2): 35–84
Morell J, Swiecki B (2001) E-readiness of the automotive supply chain: just how wired is the supplier sector. Technical report, Center for Automotive Research, Center for Electronic Commerce, ERIM
Turing A (1936) On computable numbers, with an application to the entscheidungs problem. Proc Lond Math Soc 42: 230–265
Nau DS, Au TC, Ilghami O, Kuter U, Murdock JW, Wu D, Yaman F (2003) SHOP2: an HTN planning system. J Artif Intell Res (JAIR) 20: 379–404
Sirin E, Parsia B, Wu D, Hendler JA, Nau DS (2004) HTN planning for web service composition using SHOP2. J Web Semant 1(4): 377–396
McIlraith SA, Son TC, Zeng H (2001) Semantic web services. IEEE Intell Syst 16: 45–53
Benatallah B, Sheng QZ, Dumas M (2003) The Self-Serv environment for web services composition. IEEE Internet Comput 7(1): 40–48
Aggarwal R, Verma K, Miller JA, Milnor W (2004) Constraint driven web service composition in METEOR-S. In: IEEE international conference on services computing (SCC), pp 23–30
Cardoso J, Miller J, Sheth A, Arnold J (2004) Quality of service for workflows and web service processes. J Web Semant 1: 281–308
Zeng L, Benatallah B, Dumas M, Kalagnanam J, Sheng QZ (2003) Quality driven web services composition. In: International world wide web conference (WWW), pp 411–421
Canfora G, Esposito R (2004) A lightweight approach for QoS-aware service composition. In: Second international conference on service oriented computing (ICSOC), pp 36–47
Wiesemann W, Hochreiter R, Kuhn D (2008) A stochastic programming approach for QoS-aware service composition. In: IEEE international symposium on cluster computing and the grid (CCGrid), pp 226–233
Agarwal V, Chafle G, Dasgupta K, Karnik NM, Kumar A, Mittal S, Srivastava B (2005) Synthy: a system for end to end composition of web services. J Web Semant 3(4): 311–339
Chafle G, Das G, Dasgupta K, Kumar A, Mittal S, Mukherjea S, Srivastava B (2007) An integrated development environment for web service composition. In: IEEE international conference on web services (ICWS), pp 839–847
Nagarajan M, Verma K, Sheth AP, Miller JA (2007) Ontology driven data mediation in web services. Int J Web Serv Res (JWSR) 4(4): 104–126
Rohanimanesh K, Mahadevan S (2001) Decision-theoretic planning with concurrent temporally extended actions. In: Uncertainty in artificial intelligence (UAI), pp 472–479
Kiepuszewski B, ter Hofstede AHM, Bussler C (2000) On structured workflow modelling. In: Conference on advanced information systems engineering (CAiSE), pp 431–445
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Zhao, H., Doshi, P. A hierarchical framework for logical composition of web services. SOCA 3, 285–306 (2009). https://doi.org/10.1007/s11761-009-0052-9
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11761-009-0052-9