=Paper= {{Paper |id=Vol-275/paper-28 |storemode=property |title=Combining HTN-DL Planning and CBR to compound Semantic Web Services |pdfUrl=https://ceur-ws.org/Vol-275/paper28.pdf |volume=Vol-275 |dblpUrl=https://dblp.org/rec/conf/esws/Sanchez-Ruiz07 }} ==Combining HTN-DL Planning and CBR to compound Semantic Web Services== https://ceur-ws.org/Vol-275/paper28.pdf 
    Combining HTN-DL Planning and CBR to
       compound Semantic Web Services

    Antonio A. Sánchez-Ruiz, Pedro A. González-Calero, Belén Dı́az-Agudo

               Dep. Ingenierı́a del Software e Inteligencia Artificial
                    Universidad Complutense de Madrid, Spain
             email: {antsanch}@fdi.ucm.es {pedro,belend}@sip.ucm.es




1   Introduction

Semantic Web Services (SWS) are distributed and reusable software components
that are described using standard formal languages like SWDL or OWL-S. SWS
can be automatically discovered, invoked and combined. Complex applications
can be built combining different Web Services and therefore, it is important to
provide assisting tools to help in the composition process [6].
    Planning techniques can be used to find the flow of services that accom-
plish a specific task. Several approaches have been tried in software component
composition [4], but all of them have a common requirement: the domain must
be completely formalized, and this is very difficult in real domains. Case Based
Planning (CB Planning) [2] tries to solve this deficiency using cases that repre-
sent past experiences, i.e., plans that were used to solve previous problems. On
the other hand, HTN-DL planning [5] is a very new approach that combines
the power of hierarchical planning with the inference capabilities of Description
Logics.
    In my thesis I propose to combine CB Planning and HTN-DL to obtain a
hierarchical planner that utilizes the best of both worlds.


2   Related work

The problem of web service composition has been studied extensively in recent
years [6, 4]. Hierarchical planning (HTN Planning) [1] is a modern type of plan-
ning that tries to resolve problems by dividing them into simpler subproblems.
HTN planning has been used successfully in complex domains, like SWS com-
position [7, 3].
    HTN-DL [5] is a new HTN extension in which the domain, the problem and
the current state are described using an ontology in OWL. HTN-DL works with
the Open World Assumption and takes advantage of the inference capabilities
of Description Logics (DL) in the planning process. Furthermore, it can work
directly form a description in OWL-S of the available SWS.
3    My proposed approach: Case-Based HTN-DL Planning

The main drawbacks of HTN-DL are that it is much slower than classical plan-
ning and that needs an exhaustive domain description.
    Case-Based Planning [2] adapts cases or past experiences to solve new pro-
blems. They key idea is that similar problems usually have similar solutions.
The main features of CB Planners are: they can solve problems even without an
exhaustive description of the domain because the cases can store implicit know-
ledge about the domain (maybe the validity of plans can not be checked, but the
planner can guest its validity based on previous experiences); they can enhance
the performance and accuracy with use, by just learning new experiences (cases);
and they use the cases as heuristics in order to find solutions exploring a small
part of the search space (these heuristics can improve as more quality cases are
available).
    In my thesis I propose to combine Case Based Planning and HTN-DL in order
to obtain the best of both worlds (CB HTN-DL Planning) and apply these ideas
to compound SWS. The main features of this new approach are: it works with the
Open World Assumption using the DL inference capabilities; it works directly
with the OWL-S descriptions of the SWS; it will be able to work without a
complete description of the domain; it can use the cases as heuristic to guide the
search and enhance the performance; and the planner will presumably improve
the performance and accuracy with use because new cases will be learned.
    The thesis will have 3 different parts: the formalization of the planning the-
ory behind CB HTN-DL, the development of an example application in a real
environment, and the evaluation of the results.


References
1. K. Erol, J. A. Hendler, and D. S. Nau. UMCP: A sound and complete procedure
   for hierarchical task-network planning. In Artificial Intelligence Planning Systems,
   pages 249–254, 1994.
2. K. J. Hammond. Case-based planning: viewing planning as a memory task. Aca-
   demic Press Professional, Inc., San Diego, CA, USA, 1989.
3. U. Kuter, E. Sirin, B. Parsia, D. S. Nau, and J. A. Hendler. Information gathering
   during planning for web service composition. J. Web Sem., 3(2-3):183–205, 2005.
4. J. Peer. Web service composition as ai planning - a survey. Technical report,
   University of St. Gallen, March 2005.
5. E. Sirin. Combining description logic reasoning with ai planning for composition of
   web services. PhD thesis, University of Maryland, 2006.
6. B. Srivastava and J. Koehler. Web service composition — current solutions and
   open problems. In ICAPS 2003, 2003.
7. D. Wu, B. Parsia, E. Sirin, J. A. Hendler, and D. S. Nau. Automating daml-s web
   services composition using shop2. In International Semantic Web Conference, pages
   195–210, 2003.