Re: OWL-S: Handling Failures, and automatic generation of composite process IOPRs [was: Re: A bunch of OWL-S difficulties]

See comments within the body of this message.

On Tue, 7 Sep 2004, Bijan Parsia wrote:

>
> On Sep 7, 2004, at 3:58 PM, Drew McDermott wrote:
> [snip]
> >>>> *composite*
> >>>>      processes can, in principle, be automatically generated by
> >>>> tools.
> >>>>      Since such tools don't yet exist, they have been manually
> >>>> generated
> >>>>      for this example.
> >>>>
> >>>> How would such automatic generation happen?
> >
> > It wouldn't.  That comment should be deleted.
>
> Many of us have been long skeptical about such claims.
>
> > As we discussed in today's telecon, it's probably not feasible to
> > infer the outputs or effects of a composite process.  A simple case is
> > where a step generates two outputs, only one of which is a useful
> > output of the process the step belongs to.  But the real problem is
> > that it's undecidable what effects or values a composite process is
> > going to have, unless some strong limits are put on recursion of
> > 'perform's of other processes.  I don't know if the topic of limiting
> > recursion in Owl-S has ever come up.
>
> Yes, in principle, at least. I think. I remember a Sheila slide, but I
> don't see any discussion of k-loops in "Simulation, Verification and
> Automated Composition of Web Services":
> 	http://citeseer.ist.psu.edu/narayanan02simulation.html


Ron Fadel and I actually addressed this issue in his master's work.
We built a compiler that compiled the IOPEs of each of the atomic
processes composing a composite process into IOPEs for the
composite process.  For cases that were not first-order definable,
i.e., anything that had iteration in it, we bounded the iteration
by a length k.  k-bounded iteration is first-order definable so
we got around the undecidability issue that way.  (This is defensible
because you can imagine writing software that "times-out" for large
k.)

The algorithm then works in a very intuitive way.

Formally,
The inputs and preconditions (IPs) are the IPs after regressing
the composite process to the initial state.
The ouputs and effects (OEs) are the OEs after progressing the
composite process to the final state.

More (or less) intuitively, the idea is that the IPs of the
composite process are the IPs of each individual atomic
process, conditioned on whether that part of the composition will be
executed.

Likewise the effects are the effects of each individual atomic
processes, modulo any effects that were "undone" by subsequent atomic
processes, all conditioned on whether that part of the composition
was executed.

So...the IOPEs become big conditional statements.

There is a paper addressing these issues in the context of planning
called:

McIlraith, S. and Fadel, R. ``Planning with Complex Actions''.
Proceedings of the Ninth International Workshop on Non-Monotonic
Reasoning (NMR2002),
pages 356-364, April, 2002.
http://www.ksl.stanford.edu/people/sam/mci-fad-nmr02f.pdf

Unfortunately, the paper was written for a theoretical audience.
The slides with running example may be helpful to follow in concert.
They are available at
http://www.ksl.stanford.edu/people/sam/NMR02-mci-fad.pdf


I can provide an example here, if people are interested and don't
want to wade throught the paper which is rife with notation.

- Sheila


>
> Hmm. I poked around (e.g., Rich Hull's stuff) but couldn't find the
> smoking slide or paper.
>
> [snip]
> > Adopting a "shorthand" convention in XML/RDF is like putting a smaller
> > hood ornament on your SUV to reduce gasoline consumption.
> [snip]
>
> I'm laughing.
>
> Cheers,
> Bijan Parsia.
>
>
>

Received on Tuesday, 7 September 2004 21:12:08 UTC