Re: Composition as planning

Charlie,

At the risk of promoting my own paper, here is an excerpt from the
following paper that helps address this questions.  (Apologies it's
a little long).

  McIlraith, S. and Son, T. ``Adapting Golog for Composition of Semantic
  Web Services''. Proceedings of the Eighth International Conference on
  Knowledge Representation and Reasoning (KR2002), pages 482-493, April,
  2002.
   http://www.ksl.stanford.edu/people/sam/mci-son-kr02.ps

The paper describes the work we did with Golog on Web Service Composition
in 2001/2002.  The excerpt below addresses your specific question, in
part.

Regards,
Sheila McIlraith
University of Toronto

------------------------

The provision of, effectively, a knowledge representation of the
properties and capabilities of Web services enables the automation of
many tasks, as outlined in \cite{mcisonzen01}.
In this paper we focus on the task of automated Web service
composition (WSC): Given a set of Web services and a description of
some task or goal to be achieved (e.g., ``Make the travel arrangements
for my KR2002 conference trip.''), find a composition of services that
achieves the task.  Disregarding network issues, WSC can be conceived
as either a software synthesis problem, or as a planning and plan
execution problem, depending upon how we represent our services.
In either case, this application domain has many distinctive features
that require and support tailoring.  We identify and address many of
these features in this paper.


In this paper we conceive WSC as a planning and execution task, where
the actions (services) may be complex actions.  In related work, we
show how to compile service representations into operators that embody
all the possible evolutions of a complex action, in order to treat
complex actions as primitive action plan operators \cite{mcifad02}.
As a planning task, WSC is distinguished in that it is planning with
very incomplete information.  Several sequenced information-gathering
services may be required, that culminate in the execution of only a
few world-altering services.  (Imagine making your travel plans on the
Web.)  Since our actions (services) are software programs, the input
and output parameters of the program act as knowledge preconditions
and knowledge effects in a planning context.  Software programs can
also have side-effects in the world (such as the purchase of a
commodity), that are modeled as non-knowledge effects.  Service
preconditions are regularly limited to knowledge preconditions.
Information-gathering services (aka sensors) don't fail, network
issues aside.  Exogenous events affect the things being sensed.
Persistence of knowledge has a temporal extent associated with it
(contrast stock prices to the price of a shirt at the Gap), which
affects the sequencing of services.  Services often provide multiple
outputs, a subset of which must be selected to act as input for a
subsequent service (consider picking flights).

Many services perform similar functions, so WSC must choose between
several services, each sharing some of the same effects.  Also, plans
(compositions of services) are often short, so the plan search space is
short and broad.  WSC tasks may or may not be described in terms of a goal
state.  In some instances they are described as a set of loosely
coupled goals, or constraints.  Many plans may satisfy the WSC task.
User input and user constraints are key in pruning the space of plans
(e.g., choosing from the multitude of available flights)
and in distinguishing desirable plans.

<and it goes on>

On Sat, 31 Jan 2004, Charlie Abela 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)?
>
> Regards
>
> Charlie
>
> --
> Charlie Abela
> Research Student,
> CSAI, Department,
> University of Malta
>
> -------------------------------------------------
> This mail sent through IMP: http://horde.org/imp/
>
>

Received on Saturday, 31 January 2004 14:05:18 UTC