AW: Discussion on Modelling Effects

Thank you for your reply,

There is another question this raises to me. If we have complex
processes with concurrency, conditionals and loops, how can we get a
description that PDDL can work with? Wouldn't it be more useful to
consider planning as Model Checking as some approaches suggest (e.g.
[1])? My research background is in the field of abstract state machines
and high-level Petri nets, so this seems rather natural to me. For
complex processes, we would definitely need some search heuristics,
however, because the search space might get huge. For processes without
loops I would think that a symbolic analysis would help us in getting
the pre- and postconditions for a complex process which again might be
used in planning languages such as PDDL. 

[1]
http://www.informatik.uni-trier.de/~ley/db/indices/a-tree/t/Traverso:Pao
lo.html

Regards, 

Jan Ortmann

> [Jan Ortmann]
> 
> I would like to start a discussion about what kind of information pre-
> and postconditions need to provide. 
>

I know you wanted to start it back in June, but I was busy....

> Since the approach followed by OWL-S and WSMO is to use an axiomatic
> semantics we should provide a set of Hoare-triples {P}p{Q} for each
> process. Preconditions "declare" the variables and provide conditions
to
> call the process. But what are the effects? Here, I suppose, we should
> model all things that a process changes. For a process, where I buy
> something, this usually includes the balance of my account as well as
> the fact, that something will be delivered. Thus we need be able to
> express, that things change, although we did not pass them in as a
> parameter (my account), and we need a concept of time (since things
will
> be delivered in the future). 
> 
> I would think that we might have a precondition 
> 
> {Creditcard(X) /\ X.account.balance>200 /\ Book(Y) /\ Buyer(Z)}
> 
> where the value of functional roles (attributes) was written as in OO
> languages by a dot. An effect might look like
> 
> {[X.account.balance]after = [X.account.balance]before - 200 /\
> [Y.owner]after=Z}
> 
> Here I indicated the states by "[*]after" and "[*]before". 
> 
> Are there any publications on these issues or any further suggestions?


[Drew McDermott]

Yes, there is a large literature on effective representations of
preconditions and effects in the AI planning literature.  There is a
standard language, PDDL, that captures the consensus. [1]  A lot of
the conventions of PDDL have been incorporated into OWL-S, but I will
just sketch the PDDL notation here.

PDDL divides effects into the numerical and the nonnumerical.  The
latter are handled using the sort of atomic-formula manipulation you
proposed, although in a Lispish syntax.  Instead of the before/after
notation, there is a connective 'when': (when p q) means that if p is
true before the action, then q becomes true after.  But your example
didn't require this, because you don't mention the owner before.
All we need to write is the effect

   (owns ?x ?y)

where ?x is the agent of the action (buy ?x ?y).

Numerical conditions depend upon the notion of _fluent_, a
numerical term whose value varies from situation to situation.  (In my
opinion, the term "fluent" should be used for _any_ term, numerical or
not, that is situation-dependent, but I believe the current usage is
as described.)  We write 

    (assign f e)

to mean that fluent f gets as value in the after situation the value
of e in the before situation.  The very common case (i.e., the ones
current algorithms can handle!) (assign f (+ f x)) can be written
(increase f x).  (assign f (- f x)) can be written (decrease f x).

So your effect would probably be written 

      (decrease (account-balance ?x) 200)

I don't think the formalism above is the correct way to model buying,
although it's what people usually write.  The problem is that when one
buys a book, it is quite unusual to be after a particular physical
book.  (Unless, say, it is autographed by Archduke Franz Ferdinand
with an inscription written the day before he was assassinated.)  Nor
is it correct to say that one wants to own an arbitrary copy of the
book.  One may already own two copies, but want to buy a third to give
to one's favorite intern.  I suggest that what we want is a fluent

  (num-transferred d a1 a2 t)

= the number of objects matching description d transferred from agent
a1 to agent a2 since time t.  Then our goal is 

     (increase (num-transferred book amazin.com me now)
               1)

This requires a slight enhancement to existing formalisms to allow
goals of the form (increase f c), but I doubt it will require an
increase in planning firepower to handle them.  On the other hand,
there is an issue about what form the d (description) argument can
take.  It would be nice to have arbitrary lambda expressions, but
that _would_ require an increase in planning firepower.

                                             -- Drew McDermott
                                                Yale University 
                                                CS Department


[1] http://cs-www.cs.yale.edu/homes/dvm/#PDDL

Received on Tuesday, 5 September 2006 09:23:12 UTC