Re: Doubt about expressing partial order plan in OWL-S 1.1

On Thu, 30 Dec 2004 19:36:39 -0500, Drew McDermott
<drew.mcdermott@yale.edu> wrote:
> 
> 
> > [Manshan Lin]
> > If the resulting plan is in partial order manner, I'm wondering
> > whether we can directly use the constructs (such as Sequence,
> > Unordered,Split-join) in OWL-S process model to express the plan.
> >
> > For example:
> > OperationB<OperationEnd,
> > OperationC<OperationEnd,
> > OperationD<OperationB,
> > OperationD<OperationC,
> > OperationE<OperationC
> > OperationBegin<OperationD
> > OperationBegin<OperationE
> > (Note: OperationBegin, OperationB, ... mean performs of
> > the processes)
> >
> > If "Unordered" construct allows interleaving,
> > can we express the above plan as following ?
> 
> Actually, it doesn't.  It's been replaced by "Any-order," which
> requires its steps to be executed in sequence, without saying _which_
> sequence.

Since there are "Any-order" in OWL-S 1.1, it means that some processes 
without ordering constraints cannot be executed in parallel. But how can
we know an process can not be executed in parallel with another process?
Is there any markup in OWL-S 1.1 indicating this? Or the choice between
"Any-order" and "Split-join" is up to the user, who models the process?
If the user, who is constructing the new composite process, is not familiar
with the component processes' implementation, what's the criteria for the
choice?

> 
> But let's say you used Split-Join instead.
> 
> > -------------------------------------------------
> > X1=(Sequence OperationB OperationEnd)
> > X2=(Sequence OperationC OperationEnd)
> > ...
> > X7=(Sequence OperationBegin OperationE)
> > Y=(Unorder X1 X2 X3 X4 X5 X6 X7)
> > -------------------------------------------------
> 
> So Y would = (Split-Join X1 ... X7)
> 
> > ***I don't know whether the same perform instance can appear
> > in two or more constructs.***

If the same perform instance can appear in two or more constructs,
the Sequence construct may be used to specify the partial order
constraints

> 
> Syntactically it certainly can, because we routinely use rdf:ID's to
> refer to occurrences of performs.  You can toss that ID in instead of
> the entire description.  (In the surface syntax, you would use a tag
> as a step; the current grammar might not allow that.)
> 
> The question is what the semantics would be.  There really isn't any
> official semantics.  In a denotational framework, the denotation of a
> process expression would be the set of all its execution traces.  The
> control constructs that compose processes would be defined analogous
> to this definition for Sequence:
> 
>     E is an execution of a;b;...;c
> 
> if and only if E is a time interval I such that instances of a, b, ...,
> c occur in that order in the interval, not overlapping, in the right
> order, such that begin(a) coincides with begin(I), etc. etc.
> 
> In other words, an occurrence of _a_ in _a;b;...;c_ is interpreted as
> a process type.  If we give an ID to the defining RDF for _a_, that
> makes the ID a synonym for that process type.  Hence, there should be
> no obstacle to including it in multiple places.  Unfortunately, the
> meaning comes out wrong.  Nothing says that in a particular execution
> trace the subtrace corresponding to the occurrence of #a in this
> context (say):
> 
>    <objList:first rdf:resource="#a"/>
> 
> (in a Sequence, say) is the same as the subtrace corresponding to 'a'
> in this context:
> 
>    <objList:first>
>       <perform rdf:ID="a"> ...
>          <owls:process rdf:resource="examp:a"/>
>       </perform>
>    </objList:first>
> 
> (in another Sequence, or a Split-Join).  The class Perform has
> processes as elements, not execution traces.  So reusing an ID saves a
> bit of typing, but means exactly the same as what you'd get by
> retyping the entire Perform description.  (Plus, it would mislead the
> innocent.)

If it requires that the same Perform instance can occur in only one Construct
instance, there are two ways to express the partial order plan P below:
 OperationB<OperationEnd,
 OperationC<OperationEnd,
 OperationD<OperationB,
 OperationD<OperationC,
 OperationE<OperationC
 OperationBegin<OperationD
 OperationBegin<OperationE

(1) we can transfer the partial order plan P to P', which P' indicates P
(the converser does not hold).

Partial order plan P':
  OperationB<OperationEnd,
  OperationC<OperationEnd,
  OperationD<OperationB,
  OperationD<OperationC,
  OperationE<OperationC
* OperationBegin<OperationE
* OperationE<OperationD

The plan P' can then be expressed with the constructs in OWL-S:
Sequence(
  Sequence(OperationBegin OperationE OperationD)
  Split-join(OperationB OperationC)
  OperationEnd
)

However, tranfering P to P' may increase the excution duration.
And I don't see any algorithm transferring a partial order plan to
a plan expressed by using only Sequence and Split-join constucts, 
till now. 

(2) we can add some properties to split-join construct to indicate
the partial order constrains between its component processes. How
to schedule the parallel execution is up to the agent who executes
it.

I think method (2) is simpler than method (1).

---
Happy new year!  :-)

Best regards! 

Manshan Lin (林满山)
Email: lmshill@hotmail.com;lmshill@gmail.com;lms-hill@21cn.com
Affiliation: School of Computer Science and Engineering, the South
China University of Technology
Phone: (+86)13711287277
2004-12-31

----------------------
            \ " 
  ___0__/   |
       /_       |
 .__/   \_.    |

Received on Friday, 31 December 2004 08:21:19 UTC