Abstract
With the growth of the Internet-of-Things and online Web services, more services with more capabilities are available to us. The ability to generate new, more useful services from existing ones has been the focus of much research for over a decade. The goal is, given a specification of the behavior of the target service, to build a controller, known as an orchestrator, that uses existing services to satisfy the requirements of the target service. The model of services and requirements used in most work is that of a finite state machine. This implies that the specification can either be satisfied or not, with no middle ground. This is a major drawback, since often an exact solution cannot be obtained. In this paper we study a simple stochastic model for service composition: we annotate the target service with probabilities describing the likelihood of requesting each action in a state, and rewards for being able to execute actions. We show how to solve the resulting problem by solving a certain Markov Decision Process (MDP) derived from the service and requirement specifications. The solution to this MDP induces an orchestrator that coincides with the exact solution if a composition exists. Otherwise it provides an approximate solution that maximizes the expected sum of values of user requests that can be serviced. The model studied although simple shades light on composition in stochastic settings and indeed we discuss several possible extensions.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
A preliminary version of this paper has been presented at the ICAPS 2017 Workshop on Generalized Planning. (The workshop does not have published proceedings.).
- 2.
- 3.
It can also be viewed as quantifying the probability (\(1-\lambda \)) that the process will terminate at some state.
- 4.
An alternative notion, for which similar results can be obtained is that of average reward, defined, e.g., as \(\liminf _{m\rightarrow \infty }\frac{1}{m} \sum _{i=0}^{m} R_t(\sigma _i,a_{i+1})\), which requires more mathematical sophistication to handle.
References
De Giacomo, G., Mecella, M., Patrizi, F.: Automated service composition based on behaviors: the Roman model. In: Bouguettaya, A., Sheng, Q., Daniel, F. (eds.) Web Services Foundations, pp. 189–214. Springer, New York (2014). https://doi.org/10.1007/978-1-4614-7518-7_8
Bronsted, J., Hansen, K.M., Ingstrup, M.: Service composition issues in pervasive computing. IEEE Pervasive Comput. 9(1), 62–70 (2010)
Medjahed, B., Bouguettaya, A., Elmagarmid, A.: Composing web services on the semantic web. Very Larg. Data Base J. 12(4), 333–351 (2003)
Yang, J., Papazoglou, M.: Service components for managing the life-cycle of service compositions. Inf. Syst. 29(2), 97–125 (2004)
Cardoso, J., Sheth, A.: Introduction to semantic web services and web process composition. In: Cardoso, J., Sheth, A. (eds.) SWSWPC 2004. LNCS, vol. 3387, pp. 1–13. Springer, Heidelberg (2005). https://doi.org/10.1007/978-3-540-30581-1_1
Wu, D., Parsia, B., Sirin, E., Hendler, J., Nau, D.: Automating DAML-S web services composition using SHOP2. In: Fensel, D., Sycara, K., Mylopoulos, J. (eds.) ISWC 2003. LNCS, vol. 2870, pp. 195–210. Springer, Heidelberg (2003). https://doi.org/10.1007/978-3-540-39718-2_13
Pistore, M., Marconi, A., Bertoli, P., Traverso, P.: Automated composition of web services by planning at the knowledge level. In: IJCAI (2005)
McIlraith, S., Son, T.: Adapting golog for composition of semantic web services. In: KR (2002)
Berardi, D., Calvanese, D., De Giacomo, G., Lenzerini, M., Mecella, M.: Automatic composition of E-services that export their behavior. In: Orlowska, M.E., Weerawarana, S., Papazoglou, M.P., Yang, J. (eds.) ICSOC 2003. LNCS, vol. 2910, pp. 43–58. Springer, Heidelberg (2003). https://doi.org/10.1007/978-3-540-24593-3_4
Hu, Y., De Giacomo, G.: A generic technique for synthesizing bounded finite-state controllers. In: ICAPS (2013)
De Giacomo, G., Patrizi, F., Sardiña, S.: Automatic behavior composition synthesis. Artif. Intell. 196, 106–142 (2013)
Hull, R.: Artifact-centric business process models: brief survey of research results and challenges. In: Meersman, R., Tari, Z. (eds.) OTM 2008. LNCS, vol. 5332, pp. 1152–1163. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-88873-4_17
Su, J.: Semantic web services: composition and analysis. IEEE Data Eng. Bull. 31(3) (2008)
Yadav, N., Sardiña, S.: Decision theoretic behavior composition. In: AAMAS (2011)
Menasce, D.: QoS issues in web services. IEEE Internet Comput. 6(6), 72–75 (2002)
Zeng, L., Benatallah, B., Ngu, A., Dumas, M., Kalagnanam, J., Chang, H.: QoS-aware middleware for web services composition. IEEE Trans. Softw. Eng. 30(5), 311–327 (2004)
De Giacomo, G., Vardi, M.Y.: Linear temporal logic and linear dynamic logic on finite traces. In: IJCAI (2013)
Nain, S., Lustig, Y., Vardi, M.Y.: Synthesis from probabilistic components. Log. Methods Comput. Sci. 10(2) (2014)
Muscholl, A., Walukiewicz, I.: A lower bound on web services composition. Log. Methods Comput. Sci. 4(2) (2008)
Yadav, N., Felli, P., De Giacomo, G., Sardiña, S.: Supremal realizability of behaviors with uncontrollable exogenous events. In: IJCAI, pp. 1176–1182 (2013)
Pistore, M., Barbon, F., Bertoli, P., Shaparau, D., Traverso, P.: Planning and monitoring web service composition. In: Bussler, C., Fensel, D. (eds.) AIMSA 2004. LNCS, vol. 3192, pp. 106–115. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-30106-6_11
Bacchus, F., Boutilier, C., Grove, A.J.: Rewarding behaviors. In: AAAI (1996)
Thiébaux, S., Gretton, C., Slaney, J.K., Price, D., Kabanza, F.: Decision-theoretic planning with non-Markovian rewards. J. Artif. Intell. Res. 25, 17–74 (2006)
Lacerda, B., Parker, D., Hawes, N.: Optimal policy generation for partially satisfiable co-safe LTL specifications. In: IJCAI (2015)
De Giacomo, G., Vardi, M.Y.: Synthesis for LTL and LDL on finite traces. In: IJCAI (2015)
De Giacomo, G., Vardi, M.Y.: LTL\({}_{\text{f}}\) and LDL\({}_{\text{ f }}\) synthesis under partial observability. In: IJCAI (2016)
Torres, J., Baier, J.A.: Polynomial-time reformulations of LTL temporally extended goals into final-state goals. In: IJCAI (2015)
Camacho, A., Triantafillou, E., Muise, C., Baier, J.A., McIlraith, S.: Non-deterministic planning with temporally extended goals: LTL over finite and infinite traces. In: AAAI (2017)
Fritz, C., McIlraith, S.A.: Monitoring plan optimality during execution. In: ICAPS (2007)
Baier, J.A., Fritz, C., Bienvenu, M., McIlraith, S.A.: Beyond classical planning: procedural control knowledge and preferences in state-of-the-art planners. In: AAAI (2008)
Levesque, H.J., Reiter, R., Lesperance, Y., Lin, F., Scherl, R.: GOLOG: a logic programming language for dynamic domains. J. Log. Program. 31, 59–83 (1997)
De Giacomo, G., Di Ciccio, C., Felli, P., Hu, Y., Mecella, M.: Goal-based composition of stateful services for smart homes. In: OTM (2012)
Fischer, M.J., Ladner, R.E.: Propositional dynamic logic of regular programs. J. Comput. Syst. Sci. 18, 194–211 (1979)
De Giacomo, G., Gerevini, A.E., Patrizi, F., Saetti, A., Sardiña, S.: Agent planning programs. Artif. Intell. 231, 64–106 (2016)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Brafman, R.I., De Giacomo, G., Mecella, M., Sardina, S. (2017). Service Composition in Stochastic Settings. In: Esposito, F., Basili, R., Ferilli, S., Lisi, F. (eds) AI*IA 2017 Advances in Artificial Intelligence. AI*IA 2017. Lecture Notes in Computer Science(), vol 10640. Springer, Cham. https://doi.org/10.1007/978-3-319-70169-1_12
Download citation
DOI: https://doi.org/10.1007/978-3-319-70169-1_12
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-70168-4
Online ISBN: 978-3-319-70169-1
eBook Packages: Computer ScienceComputer Science (R0)