Using Markov Decision Process Model with Logic Scoring of Preference Model to Optimize HTN Web Services Composition

Introduction

Web services are software “components” at an abstraction level suitable for business level reuse which are combined into larger systems, often dynamically and only when need arises. This is possible as their functionality is described in a way that can be machine interpreted (e.g., through a WSDL file or a Semantic Web description). These combinations, which are usually referred to as compositions, allow for services that are part of different applications, reside on different platforms, are developed using diverse programming languages and are possibly owned by different business partners to cooperate smoothly. The need for composition arises as usually a single service cannot fulfill the requirements of a user. Web service composition provides a mechanism to combine different services to handle a complex business process. Automated Web service composition allows to combine services without human involvement in the planning and is valuable in many domains, e-commerce is a typical example. However, with the rapid increase of Web services, increasingly complex requirement of business process in the real world automatic service composition requires a flexible mechanism to deal with changing service availability. AI planning has often been adopted for automated Web services composition, as exemplified by the methods presented in for example Sirin, Wu, Hendler, and Nau (2004), Schuschel and Weske (2004), Paik, Maruyama, and Huhns (2006), and Akkiraju, Srivastava, Ivan, Goodwin, and Syeda-Mahmood (2006) to handle this issue.

In Sirin et al. (2004), an HTN planning method has been suggested to handle automatic Web services composition. This method translates OWL-S Web service descriptions to a SHOP2 domain and then a given business plan is achieved by decomposing complex tasks using operators from the SHOP2 domain. Considering the procedure of task decomposition, this method mainly is concerned with the feasibility of task decomposition; that is can one plan be found? However, a plan may fail for various reasons, service instances may no longer exists when they are about to be invoked, feature interaction in Web services (Weiss, Esfandiari, & Luo, 2007) may lead to undesired behavior or the specific plan might simply not be the best available for a user. There usually are several possible plans which can solve one specific high-level business process, so there is a natural redundancy to avoid these problems, one only needs to go a step further than just finding one plan. For example, if a user wants to attend an exhibition in another city in a few days. On the condition of satisfying user’s requirements, he can make a choice of taking a flight or a train to the city and then attend the exhibition. In this situation, the user always wants to know what options he has and which is of the best quality (that is satisfying his non-functional criteria such as cost considerations or time saving).

This paper addresses the aspect of finding multiple composition plans and then selecting the most appropriate for a user. We propose an enhanced approach for Web services composition based on the combination of HTN planning and a Markov decision process model. With this approach, several highly suitable Web service plans will be obtained providing different solutions to a business process using Web services composition and hence offering much more flexible solution to the customer. To make sure these plans are indeed some of the best solutions available we use an evaluation mechanism to illustrate the optimal solution amongst those multiple solutions using a Markovian decision process. In this way, the optimal solution not only meets the requirements of the business process in its functional aspects, but also satisfied the expectations that the solution is of the best quality based on requirements considering the non-functional aspects.

This paper is an extension of our work presented at ICWS 2009 (Chen, Xu, & Reiff-Marganiec, 2009). The paper extends the previous work by addressing a number of issues queried at the conference as well as on some aspects which were planned as future work. Specifically we present a more (1) realistic case study with a more complete (2) analysis of the approach in terms of its complexity. We have also enhanced the (3) method to evaluate the non-functional (or QoS) properties and addressed the issue of choosing appropriate (4) values for the threshold used in the control strategy.