- From: Jan Ortmann <j.ort@web.de>
- Date: Tue, 5 Sep 2006 11:21:30 +0200
- To: <drew.mcdermott@yale.edu>, <public-sws-ig@w3.org>
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