Towards Automatic Composition of Web Services : SAT-Based Concretisation of Abstract Scenarios

• Autorzy: Niewiadomski A. , Penczek W. , Półrola A. , Szreter M. , Zbrzezny A.
• Języki publikacji: EN

Abstrakty

EN

Automating the composition of web services is an object of a growing interest. In our paper [13] we proposed a method for converting the problem of the composition to the problem of building a graph of worlds consisting of formally defined objects, and presented the first phase of this composition aimed at building a graph of types of services (an abstract graph). In this work we propose a method of replacing abstract flows of this graph by sequences of concrete services able to satisfy the user’s request. The method is based on SAT-based reachability checking for (timed) automata with discrete data and parametric assignments.

Słowa kluczowe

EN

worlds and services; abstract planning; timed automata with discrete data

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2012
• Tom: Vol. 120, nr 2
• Strony: 181--203
• Opis fizyczny: Bibliogr. 31 poz., tab., wykr.

Twórcy

autor

Niewiadomski A.

autor

Penczek W.

autor

Półrola A.

autor

Szreter M.

autor

Zbrzezny A.

• Institute of Computer Science, PAS, Jana Kazimierza 5, 01-248 Warsaw, Poland,

Bibliografia

• [1] S. Ambroszkiewicz. EnTish: An Approach to service Description and Composition. ICS PAS, Ordona 21, 01-237 Warsaw, 2003.
• [2] S. Bahadori, S. Kafi, K. Zamani far, and M. R. Khayyambashi. Optimal web service composition using hybrid ga-tabu search. Journal of Theoretical and Applied Information Technology, pages 10-15, 2005.
• [3] A. Biere, A. Cimatti, E. Clarke, M.Fujita, and Y. Zhu. Symbolic model checking using SAT procedures instead of BDDs. In Proc. of the ACM=IEEE Design Automation Conference (DAC'99), pages 317-320, 1999.
• [4] A. Blum and M. L. Furst. Fast planning through planning graph analysis. In In Journal of Artificial Intelligence, pages 281-300, 1997.
• [5] A. Blum and J. Langford. Probabilistic planning in the Graphplan framework. In Proc. of the 5th European Conference on Planning, pages 319-332, 1999.
• [6] R. Bryant. Graph-based algorithms for boolean function manipulation. IEEE Transaction on Computers, 35(8):677-691, 1986.
• [7] D. Doliwa, W. Horzelski, M. Jarocki, A. Niewiadomski,W. Penczek, A. P´ołrola, and J. Skaruz. HarmonICS - a tool for composing medical services. In Proc. of the 4th Central-European Workshop on Services and Their Composition (ZEUS 2012), volume 847 of CEUR Workshop Proceedings, pages 25-33. CEUR-WS.org, 2012.
• [8] D. Doliwa,W. Horzelski, M. Jarocki, A. Niewiadomski,W. Penczek, A. P´ołrola, M. Szreter, and A. Zbrzezny. PlanICS - a web service composition toolset. Fundamenta Informaticae, 112(1):47-71, 2011.
• [9] S. Edelkamp and M. Helmert. On the implementation of MIPS. In Proc. of AIPS-00 Workshop on Model Theoretic Approaches to Planning, pages 18-25, 2000.
• [10] A. Gerevini and I. Serina. LPG: A planner based on local search for planning graphs with action costs. In Proc. of the 6th Int. Conf. on Artificial Intelligence Planning Systems (AIPS'02), pages 13-22, 2002.
• [11] S. Hoelldobler and H. P. Stoerr. Solving the entailment problem in the fluent calculus using binary decision diagrams. In Proc. of AIPS-00 Workshop on Model Theoretic Approaches to Planning, pages 18-25, 2000.
• [12] J. Hoffmann, I.Weber, J. Scicluna, T. Kaczmarek, and A. Ankolekar. Combining scalability and expressivity in the automatic composition of semantic web services. In Proc. of the 8th Int. Conf. on Web Engineering (ICWE'08), pages 98-107. IEEE Computer Society, 2008.
• [13] M. Jarocki, A. Niewiadomski, W. Penczek, A. P´ołrola, and M. Szreter. Towards automatic composition of web services: Abstract planning phase. In S. Ambroszkiewicz, J. Brzeziński, W. Celary, A. Grzech, and A. Zieliński, editors, SOA Infrastructure Tools: Concepts and Methods, pages 181-210. Poznan University of Economics Press, 2010.
• [14] R. Jensen and M. M. Veloso. OBDD-based universal planning for synchronized agents in non-deterministic domains. Journal of Artificial Intelligence Research, pages 189-226, 2000.
• [15] H. Kautz and B. Selman. Planning as satisfiability. In Proc. of the 10th European Conf. on Artificial Intelligence (ECAI'92), pages 359-363, 1992.
• [16] H. Kautz and B. Selman. Blackbox: A new approach to the application of theorem proving to problem solving. In Working notes of the Workshop on Planning as Combinatorial Search at AIPS-98, 1998.
• [17] M. Klusch, A. Geber, and M. Schmidt. Semantic web service composition planning with OWLS-XPlan. In Proc. of the 1st Int. AAAI Fall Symposium on Agents and the Semantic Web. AAAI Press, 2005.
• [18] D. McDermott, M. Ghallab, A. Howe, C. Knoblock, A. Ram, M. Veloso, D. Weld, and D. Wilkins. PDDL - the Planning Domain Definition Language - version 1.2. Technical Report TR-98-003, Yale Center for Computational Vision and Control, 1998.
• [19] W. Penczek, A. Półrola, and A. Zbrzezny. Towards automatic composition of web services: A SAT-based phase. In Proc. of the 2nd Int. Workshop on Abstractions for Petri Nets and Other Models of Concurrency and of the Int. Workshop on Scalable and Usable Model Checking (APNOC'10 + SUMO'10), pages 76-96, 2010.
• [20] S. R. Ponnekanti and A. Fox. SWORD: A developer toolkit for web service composition. In Proc. of the 11st Int. World Wide Web Conference (WWW'02), 2002.
• [21] J. Rao. Semantic Web Service Composition via Logic-Based Program Synthesis. PhD thesis, Dept. of Comp. and Inf. Sci., Norwegian University of Science and Technology, 2004.
• [22] J. Rao, P. Küngas, and M. Matskin. Logic-based web services composition: From service description to process model. In Proc. of the IEEE Int. Conf. on Web Services (ICWS'04). IEEE Computer Society, 2004.
• [23] J. Rao and X. Su. A survey of automated web service composition methods. In Proc. of the 1st Int. Workshop on Semantic Web Services and Web Process Composition (SWSWPC 2004), pages 43-54, 2004.
• [24] D. Redavid, L. Iannone, and T. Payne. OWL-S atomic services composition with SWRL rules. In Proc. Of the 4th Italian Semantic Web Workshop: Semantic Web Applications and Perspectives (SWAP 2007), 2007.
• [25] D. Roman, J. de Bruijn, A. Mocan, H. Lausen, J. Domingue, C. Bussler, and D. Fensel. WWW: WSMO, WSML, and WSMX in a nutshell. In Proc. of the 1st Asian Semantic Web Conference (ASWC'06), volume 4185 of LNCS, pages 516-522. Springer-Verlag, 2006.
• [26] M. Sheshagiri, M. desJardins, and T. A. Finin. A planner for composing service described in DAML-S. In In Workshop on Planning for Web Services, International Conference on Automated Planning and Scheduling, pages 28-35, 2003.
• [27] E. Sirin, J. Hendler, and B. Parsia. Semi-automatic compositions of web services using semantic description. In Proc. of the Int. Workshop 'Web Services: Modeling, Architecture and Infrastructure' (at ICEIS 2003), 2003.
• [28] B. Srivastava and J. Koehler. Web service composition - current solutions and open problems. In Proc. Of Int. Workshop on Planning for Web Services (at ICAPS 2003), 2003.
• [29] T. Vitvar, A. Mocan, M. Kerrigan, M. Zaremba, M. Zaremba, M. Moran, E. Cimpian, T. Haselwanter, and D. Fensel. Semantically-enabled service oriented architecture : concepts, technology and application. Service Oriented Computing and Applications, 1:129-154, 2007.
• [30] A. Zbrzezny. A boolean encoding of arithmetic operations. Technical Report 999, ICS PAS, 2007.
• [31] A. Zbrzezny and A. Półrola. SAT-based reachability checking for timed automata with discrete data. Fundamenta Informaticae, 70(1-2):579-593, 2007.