RE: Composition as planning

Thanks for your replies.

HTN planners seem to fit nicely in the WS
composition scenario since decomposition of
complex services will be required to eventually
incorporate its primitive task into a new complex
service. Is it always the case that a complex
service be fully decomposed into its primitive
components? It could be the case that a complex
service be included into a yet more complex one
without there being the need for decomposition.
Right? How is this handled in HTN planning?

I found some papers that make use of the analogy
of Web services as STRIPS operators [1,2]. At
least as related to Web services with
preconditions and effects such analogy still seems
to hold. Also in the future work of [2] there is a
mention of a partial order planner, this seems
also to fit the requirements since a pop planner
has to plan with incomplete knowledge. Am I on the
right track or am I missing something?

I appreciate that there is work in progress over
such issues, but can someone shed some more light
on the issues relating the different planning
techniques:  HTN, partial order,
estimated-regression planning etc with Web
services composition?

Thanks again

Charlie

[1] Drew McDermott: Estimated regression planning
for interactions with Web services:
http://www.ime.usp.br/~kvd/Otros/plannerweb.pdf
[2] Mithun Sheshagiri + Finin + deJardins: A
Planner for composing Services Described in
DAML-S:
http://www.cs.umbc.edu/~finin//papers/icaps03.pdf


-----Original Message-----
From: public-sws-ig-request@w3.org
[mailto:public-sws-ig-request@w3.org]On Behalf Of
Dana Nau
Sent: Saturday, January 31, 2004 9:37 PM
To: Austin Tate
Cc: public-sws-ig@w3.org; Charlie Abela
Subject: 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
<?fontfamily><?param
Helvetica><?x-tad-smaller>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


<?/x-tad-smaller><?/fontfamily>