Semantic markup of Web services will enable the automation of various kinds of tasks, including discovery, composition, and execution of Web services. We describe how an AI planning system (SHOP2) can be used with DAML-S Web service descriptions to automatically compose Web services.
Semantic Web, DAML-S, Web Services, Web Service Composition, Automated Reasoning
As Web services -- that is, programs and devices accessible via standard Web protocols -- proliferate, it becomes more difficult to find the specific service that can perform the task at hand. It becomes even more difficult when there is no single service capable of performing that task, but there are combinations of existing services that could. Sufficiently rich, machine readable descriptions of Web services would allow the creation of novel, compound Web services with little or no direct human intervention. Semantic Web languages, such as the Web Ontology Language (OWL) or DAML+OIL, provide the foundations for such sufficiently rich descriptions.
In May 2001, the DARPA Agent Markup Language (DAML) Program released the first version of DAML-S[1], a set of ontologies for describing the properties and capabilities of Web services. The purpose of DAML-S markup of Web services is to support effective automation of various kinds of tasks including Web service discovery, composition, execution, and monitoring.
For our work, we are motivated by issues related to automated Web service composition. One part of DAML-S, namely its process ontology, provides a standard language for describing the composition of Web services. Below, we describe how SHOP2[2] --- an AI planning system --- can be used with DAML-S Web service descriptions to automatically compose Web services.
The example we describe here is a variation of the example described in Scientific American article[3]. Suppose Bill and Joan's mother goes to her physician complaining of pain and tingling in her legs and the physician proposes the following sequence of activities: 1) A prescription for Relafen ,an anti-inflammatory drug; 2) An MRI scan and an electromyography, both of these are diagnostic tests to try to determine possible causes for the symptoms; 3) A follow-up appointment with the physician to discuss the results of the diagnostic tests.
Bill and Joan need to do the following things for their mother:
For the three appointment times, there are the following preferences and constraints:
Consider a possible scenario in the near future, where Bill and Joan can use Web services to schedule their mother's appointments. It would be difficult for Bill and Joan to finish their task by consulting the Web services manually, because:
In the DAML-S process ontology, each Web service is modeled as a process. A process can be either atomic or composite. An atomic process represents a directly executable Web service. A composite process can be decomposed into other atomic or composite processes. How to decompose a composite processes is specified through its control constructs. A composite process represents a compound Web service. The goal of automatic service composition is as follows: for a composite process instance, find a collection of atomic process instances that forms a legal composition of this instance based on the composite process's DAML-S definition.
More specifically, we can build an agent that can plan a collection of Web service requests, whose execution will achieve the user's goal. HTN (Hierarchical Task Network) planning seems very promising for this, because the concept of task decomposition in HTN planning is very similar to the concept of composite process decomposition in DAML-S.
SHOP2 is a domain-independent HTN planning system. HTN planning is an AI planning methodology that creates plans by task decomposition. This is a process in which the planning system decomposes tasks into smaller and smaller subtasks, until primitive tasks are found that can be performed directly. SHOP2's knowledge base contains operators and methods. Each operator is a description of what needs to be done to accomplish some primitive task, and each method tells how to decompose some compound task into partially ordered subtasks.
A planning problem in SHOP2 is a triple (S, T, D), where S is initial state, T is a goal task list, and D is a domain description. SHOP2 will return a plan P = (p1 p2 ... pn), a sequence of instantiated operators that will achieve T from S in D.
To use SHOP2 for automatic DAML-S service composition, we encode a collection of DAML-S process definitions M for a group of Web services into a SHOP2 domain D as follows (In our translation, we assume that in DAML-S, an atomic process can either have effects or outputs. An atomic process with only output models an information collecting Web service. An atomic process with only effect models an world altering Web service):
The instance of a composite process T in M will become a task for SHOP2. SHOP2's recursive decomposition of this task into operator instances will correspond directly to the recursive decomposition of the composite process instance into atomic processes instances.
Our implementation includes:
To test the effectiveness of our approach, we have run SHOP2 on several instances of the problem described in Section 2. These problem instances varied from cases where it was easy to schedule satisfactory appointments to a case in which no nearby treatment centers had treatment times slot were close together, so that Bill and Joan would both have to drive Mom for treatments on separate days. In all of these cases, SHOP2 was easily able to find the best possible solution.
Our technology here is based on work with SHOP family of planning systems, with SHOP2 being the newest one in the family. One other technology that addresses aspect of automatic Web service composition and that deserves mention is the work of McIlraith[4] and others in Stanford University on adapting Golog for programming the semantic Web.
We have described a way to address the problem of automatic Web service composition by exploiting AI planning techniques, in particular, the SHOP2 planning system. Our approach involves translating DAML-S definitions of Web services into SHOP2 methods and operators, so that SHOP2 can be used with DAML-S Web service descriptions to automatically compose Web services.
This work was supported in part by Air Force Research Laboratory grant F30602-00-2-0505.