W3C home > Mailing lists > Public > public-sws-ig@w3.org > December 2004

Re: Planning under Description Logic ?--an obstacle towards WSAC

From: Evren Sirin <evren@cs.umd.edu>
Date: Mon, 06 Dec 2004 12:43:50 -0500
Message-ID: <41B49A56.3090000@cs.umd.edu>
To: Juergen Zimmer <jzimmer@inf.ed.ac.uk>
CC: bparsia@isr.umd.edu, Manshan Lin <lmshill@gmail.com>, public-sws-ig@w3.org

Juergen Zimmer wrote:

>
> Hi,
>
> I've read your paper as well and I've got a few questions and comments.
>
>> http://www.mindswap.org/papers/SWS-ISWC04.pdf
>>  
>>
> questions:
> 1) Is your modified Jshop planner available for research purposes?

We haven't made a public release of the system mainly because we want to 
do the integration with JSHOP2 which has the same features as SHOP2. 
This has been delayed for a long time due to the delays in the release 
of JSHOP2 and other constraints on my schedule. I've now started to work 
on implementing the system with JSHOP2 and generic Jena reasoner 
interface (so you can connect Pellet or DIG reasoners such as Racer).

> 2) Can it enumerate all possible plans (combinations of services)?

You can set the options to return frst plan or return all plans. Is this 
what you are asking?

> 3) How to you handle conditioned outputs and effects that are 
> introduced with Results in OWL-S 1.1?

SHOP2 can express conditional effects. Outputs are expressed as 
knowledge effects so conditional outputs would be represented as 
conditional effects but we haven't yet worked on this issue.

> 4) I'm not an expert in HTN planning but it seems to me that without 
> any methods (and only operators)
>   it wouldn't do anything, or am I wrong? 

Well, you are not completely wrong. But you can always write one generic 
HTN method that tries every operator in the domain. This would reduce 
the planning problem to simple forward search and theoretically you 
would find the plan if one exists. Practically, this approach would fail 
really bad and wouldn't scale to real world problems.

> I have the impression that the methods tell you the basic composition 
> steps that    can occur in your overall plan/composition.

> comments:
> 1) The problems you mention at the end of sec 3.3. reminded me of 
> truth-maintenance systems
>    that have been studied in AI for a while.

You are right that there is a resemblance. The problem is OWL DL, i.e. 
Description Logic SHION(D), is very expressive and DL reasoners can 
handle this expressivity with very optimized tableau algorithms. It is 
hard to figure out how truth maintenance data can be stored and updated 
without making the system impractical. One other (and even harder) 
problem to solve is the cases where deleting either assertion A or 
assertion B will be enough for the negative effect. How and why the 
reasoner should choose one assertion over the other? It is not clear if 
we would like to automate this process.

> 2) Analogously, the end of sec 4 reminded me of constraint solving 
> where people deal with networks of
>    constraint variables and restrictions. Maybe some of their methods 
> would be applicable to your problem.
>
> minor comments:
> Sorry, I don't want to be a nitpicker but I'd like to help improve 
> your publication (might be too late though).

It is late because the workshop proceedings have alreayd been published. 
The version available on our web site is not the camera-ready version 
and the typos you mentioned were already fixed. I'll update the online 
version with the latest camera-ready version.

Thanks,
Evren

>
> It seems that you managed to mess up you LaTeX and the referees of 
> your paper didn't see it:
> 1) sec 2.4: "(see Figure 2.4)" should be "(see Fig. 1)"|
> 2) sec 3.1: "in figure 2.1" --> "in Fig. 2"
> 3) sec 3.2: "in figure 3.2" --> "in Fig. 3"
> I'm not a native speaker but I think the following should be:
> 1) sec 5:  "Actually, Lisp version" --> "Actually, the Lisp version"
>                "contained significantly more number of individuals" 
> --> "contained significantly more individuals"
>                "We first implemented... and run..." --> "We first 
> implemented... and ran..."
>                                                                         
>                                         ===
>                "However, only way..." --> "However, the only way..."
>
> Manshan Lin wrote:
>
>>>> hi all,
>>>> I've just read all the discussion about applying AI planning technique
>>>> to SWS.
>>>> I notice that most traditional planning algorithm are based on first
>>>> order logic, which is based on close-world assumption.
>>>>     
>>>
>>> Er...really? First order....closed-world....BOOM! ;)
>>>   
>>
>>
>> Sorry for my expression, what I actually refer to is the traditional
>> planning algorithm. :)
>>
>>  
>>
>>>> The question is :
>>>> When using DL to describe world state, what adaptions should
>>>> traditional AI planning techniques make?
>>>>     
>>>
>>> Let me point you our paper on Planning for Web Services:
>>>       http://www.mindswap.org/papers/SWS-ISWC04.pdf
>>>   
>>
>>
>> Yes, I've read your paper. It is trying integrate OWL-DL 
>> reasoner(Pellet) with an AI
>> planner(SHOP2) to solvethe evaluation
>> of preconditions and applying effects. There are some questions:
>> (1) In section 2.2, it seems that HTN planner starts its planning from
>> initial state to the goal
>> state. Do you assume that the user provides all needed information at
>> the very beginning? What's
>> more, it seems that the plan generated by the HTN planner does not
>> support pallel execution, since
>> it only generates a sequence of actions. (Since I'm not familiar
>> withHTN planning, point it out
>> if I'm wrong. :) ).
>> (2) In section 3.1 the fouth paragraph, it mentions due to open-world
>> assumption, "as SWRL does
>> not allow negated atoms appear in rule bodies, we also restrict the
>> preconditions to contain only
>> non-negated SWRL atoms". In my opinion, negation is relative. Don't
>> you think that "not(?person
>> rdf:type Registered)" can be easily converted to "(?person rdf:type
>> complementOf(Registered))"?
>> (3) In section 3.2, it mentions how to evaluate universally quantified
>> expressions. The evaluation
>> however returns to the closed world assumption. To avoid ambiguity,
>> should it uses another symbol
>> to express "as far as I know, all ...". (4) In section 3.3 fouth 
>> paragraph, it mentions "we have the problem
>> of OK deriving the same assertion
>> from other facts even after we remove that assertion from the KB
>> ...... This is exactly why planning
>> systems make the distinctions between primitive and derived predicates
>> and do not allow derived predicates
>> in effect". How can we make sure that the effects of an operation must
>> be primitive? Just like we
>> can't require others not to inherit a concept. In some KBs, they are
>> primitive, while in some KBs,
>> they also can be derived predicates.
>>
>>  
>>
>>> It describes our attempt to use OWL as the world state represenation
>>> language of the SHOP planner.
>>>
>>>   
>>>
>>>> For example,
>>>> TBOX: EffectA = intersectionOf(EffectB,EffectC)
>>>> ABOX: a individual EffectA
>>>>     
>>>
>>> Er...So you're talking owl full here? With the same thing both a class
>>> and a individual?
>>>   
>>
>>
>> Sorry for my expression again, :(. What I mean is that 'a' is an
>> individual of 'EffectA'.
>>
>>  
>>
>>>> Then we can choose an operation that achieves EffectA or we can choose
>>>> two operations (one achieves EffectB and the other achieves EffectC).
>>>>     
>>>
>>> I don't udnerstand.
>>>
>>>   
>>>
>>>> It's a little like adding some common rules
>>>> (in this case EffectB(x) and EffectC(x)->EffectA(x))
>>>> to traditional planning domain.
>>>>     
>>>
>>> I presume you're talking about secondary effects? yeah, they're a
>>> problem :)
>>>   
>>
>>
>> No, I mean EffectA(x) equals to the conjunction of EffectB(x) and 
>> EffectC(x).
>> Just like we can see the glass as half empty or as half full. The 
>> expression are different but they have the same meaning.
>> That is,
>> TheGlassHalfEmptyEffect(x) -> TheGlassHalfFullEffect(x)
>> Another example,
>> GetMyCarRepairedEffect(x) and GetMyCarCleanEffect(x) ->
>> GetMyCarRepairedAndCleanEffect(x)
>>
>> The concept "GetMyCarRepairedAndCleanEffect" is the intersection of 
>> the concept
>> "GetMyCarRepairedEffect" and "GetMyCarCleanEffect".
>>
>>  
>>
>>>> When EffectB and EffectC are not
>>>> atomic concepts, the situation becomes more complex. How to handle
>>>> this kind of things in planning algorithms?
>>>>     
>>>
>>> Well, I won't repeat our paper, but I will add that the problem is
>>> *much* trickier when your *domain* may have been gathered from
>>> disparate sources. It's hard to forbid use of derived literals in that
>>> case (IMHO).
>>>   
>>
>>
>> Best regards!
>>
>> Manshan Lin
>> Email: lmshill@hotmail.com;lmshill@gmail.com
>> Affiliation: School of Computer Science and Engineering, the South
>> China University of Technology
>> Phone: (+86)13711287277
>> 2004-12-03
>>
>>  
>>
>
>
>
Received on Monday, 6 December 2004 17:44:38 GMT

This archive was generated by hypermail 2.2.0+W3C-0.50 : Sunday, 16 March 2008 00:10:59 GMT