Re: Composition as planning

Thanks for cc'ing me, Austin!

To Charlie: when you refer to "the classical planning problem", do you  
mean planning with STRIPS-style operators?  If so, then it's badly  
suited for web-service work because two of its key assumptions aren't  
satisfied: (1) it assumes that the world is completely static except  
for the planner's actions, and (2) it assumes that the planner is  
omniscient.

On the other hand, there are several non-classical planning systems  
(e.g., Austin's and mine) that are better suited for composition of web  
services.  Jim Hendler and I and several of our students had a paper in  
ISWC 2003 about that; you can download a copy at  
<http://www.mindswap.org/papers/ISWC03-SHOP2.pdf>.  Here's the abstract  
of the paper:

The DAML-S Process Model is designed to support the application of AI  
planning techniques to the automated composition of Web services. SHOP2  
is an Hierarchical Task Network (HTN) planner well-suited for working  
with the Process Model. We have proven the correspondence between the  
semantics of SHOP2 and the situation calculus semantics of the Process  
Model. We have also implemented a system which soundly and completely  
plans over sets of DAML-S descriptions using a SHOP2 planner, and then  
executes the resulting plans over the Web. We discuss the challenges  
and difficulties of using SHOP2 in the information-rich and  
human-oriented context of Web services.

I hope this helps.

On Jan 31, 2004, at 9:06 AM, Austin Tate wrote:

> At 09:08 PM 31/01/2004 +0800, you wrote:
>> Does anyone know of work that compares the composition of web  
>> services with the
>> classical planning problem and which describes which concepts in  
>> planning are
>> valid and which others need to be modified or added (if any)?
>
> We are working on that area Charlie. See also work on SHOP2 at  
> Maryland, and the work of Blythe/Gil and others at USC/ISI.
>
> If you take recent practical planners as a basis, they already allow  
> for:
>
> a) specification of an outline process or requirements in the form of  
> an initial plan including some aspects of state requirements and some  
> aspects of activity performance in any combination desired.
>
> b) they can take a library of process descriptions in the form of  
> other partial plans, standard operating procedures, or descriptions of  
> activities that are considered executable (no further refinement is  
> known from the library anyway).
>
> c) they can then automatically, or with user guidance or control  
> refine the initial outline plan using the library of components to get  
> a more detailed plan... going as far as you wish at plan time.
>
> d) they can then support execution and execution monitoring of the  
> partial plans, making selections of undecided parts at run time.
>
> e) they can spot variance to the expected and required outcomes of  
> activities and start plan repair processes to recover dynamically.
>
> O-Plan is an instance of such a planner...   
> http://www.aiai.ed.ac.uk/project/oplan/
> Its actually been running over the web in demo mode since 1995 using  
> an HTTP style service interface from other applications and a web  
> style user interface using CGI scripts (it predates work on more  
> recent standards for such things).
>    * Tate, A. and Dalton, J. (2003) O-Plan: a Common Lisp Planning Web  
> Service, invited paper, in Proceedings of the International Lisp  
> Conference 2003, October 12-25, 2003, New York, NY, USA, October  
> 12-15, 2003.
> http://www.aiai.ed.ac.uk/project/ix/documents/2003/2003-luc-tate- 
> oplan-web.pdf
>
>
> We are now, within the DAML program, working on its successor I-Plan  
> that sits within the I-X Process Panel framework and will assist with  
> the general support to multi-agent planning and replanning.  But its  
> also being created to act as a web services composition tool.   
> http://www.aiai.ed.ac.uk/project/ix/
>
> The principal differences that I see in what we need to do to make  
> this kind of AI planning useful in a web services context is to have  
> some idea of how to decide what service descriptions to use at plan  
> time and which to use (or discover) at execute time.  There is little  
> point planning in fine detail a long time before you understand  
> something of the execution context.  This is not a simple problem!   
> You need to have some model of the likely execution context at plan  
> time.  This could be quite different if the composition is done ahead  
> of time for verification and checking... to the case where its  
> composed dynamically immediately ahead of execution and you can assume  
> pretty much the same environment for both planning and execution  
> (except for recover issues if the situation changes).
>
> Our target for the I-Plan work in the DAML program is described in a  
> AAAI Spring 2004 Symposium Web Services workshop paper. That's our  
> only paper referring to this current research at the moment.  This  
> describes how we will use I-Plan to compose semantic and grid services  
> workflows that can be checked by IHMC's KAoS system for likely run  
> time policy violations (and other analyses) ahead of actual execution  
> in which these policies will be enforced by policy management  
> services.
>    * Uszok, A., Bradshaw, J.M., Jeffers, R., Johnson, M., Tate, A.,  
> Dalton, J. and Aitken, S. (2004) Policy and Contract Management for  
> Semantic Web Services, AAAI Spring Symposium, Stanford University,  
> California, USA, March 2004
> http://www.aiai.ed.ac.uk/project/ix/documents/2004/2004-aaai-spring- 
> uszok-sws.pdf
>
> The richness of process/services description that can be used by such  
> AI planners will only come into their own if the OWL-S/SWSL/SWS  
> languages of the future support a moderately rich process model. NIST  
> PSL is a possible base for this process model in SWSL and would give  
> an extendible framework that would fit very well with the approach of  
> using AI planning and execution recovery methods in web services  
> composition and enactment. We are inputting to that effort by  
> promoting our simple abstract and very extensible framework for  
> process models called <I-N-C-A> (Issues, Nodes, Constraints and  
> Annotations).
>
> Best wishes, Austin
>
>
>
>
>
>
>
>
>
>
> --
> Prof. Austin Tate, Artificial Intelligence Applications Institute,  
> Informatics,
> University of Edinburgh, Appleton Tower, Crichton Street, Edinburgh  
> EH8 9LE, UK
> Tel: +44 131 650 2732 Fax: +44 131 650 6513 E-mail: a.tate@ed.ac.uk
>
Professor Dana S. Nau
Department of Computer Science, and Institute for Systems Research
University of Maryland, College Park, MD 20742
phone 301-405-2684    fax 301-405-6707    http://www.cs.umd.edu/~nau