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

On Wed, 8 Dec 2004 15:19:26 +0000 (GMT), Drew McDermott
<> wrote:
> > [Manshan Lin]
> > I'm wondering these days about two questions:
> > 1. In planning for WSAC, we have two choices: a) planning from
> > the initial state to the goal; b) planning from the goal to the initial
> > state. Because it is hard for us to establish a complete initial state
> > before planning (the user doesn't know what information he should
> > privide in advance. For example, some plans generated to buy a
> > book may require the user to provide his address, while some may
> > require the user to provide both his address and phone number),
> > b) seems to be a good choice.
> The way this distinction is drawn in AI textbooks must not be taken
> too seriously.  Almost all planners search a space of _partial plans_.
> A partial plan is a set of design choices tentatively made.  The hope
> is that that set can be extended to a complete and workable plan.  If
> not, then the planner must undo some of the design choices ---
> backtrack --- and try something else.
> Against that backdrop we usually see reasoning patterns that could be
> characterized as "forward" and "backward," often both types in the
> same planner.  For example, in a classic partial-order planner a
> partial plan is a set of commitments to actions to achieve some of the
> subgoals discovered so far, plus a set of ordering constraints adopted
> to avoid deleting a subgoal too early, plus a set of open subgoals
> that still need to be achieved.  A typical operation on such a plan is
> to pick an open subgoal and choose a way of achieving it.  That's
> "backward" reasoning, I suppose.  Another operation is to use a goal
> achieved by an existing step to achieve an open subgoal.  "Forward"
> reasoning?  Another is to postpone an action that threatens to delete
> an achieved action.  Is that "forward" or "backward"?  At this point
> this question starts to seem a bit irrelevant.

As mention in quite a few papers, in practice, the resulting plan of WSC is 
relative short, but the choices are vast since many concrete WSes share 
similar functionality. This fact shows that we are trying to find a simple
plan in a large and unbounded planning domain.

If we launch our planning from the initial state, we have to face a large
number of irrelevant WSes. Of cource, we can use some heuristics to compute
the contribution of each operation, but there is too much cost in computing 
the irrelevant ones' heuristic. Launching from "initial state" and launching
from "goal" are not symmetric. What's more, most of the heuristics for planning
(such as RePop, HSPR)aims at finding the shortest plan, not the best plan. I
think the heuristics should be enhanced. The planning for WSC becomes more
complicated when we take non-functional factors into consideration. 

On Wed, 22 Dec 2004 22:35:10 +0800, Manshan Lin <> wrote:
> If the resulting plan is in partial ordering manner,

I don't think total order planning is feasible to solve WSC. 
Considering long duration ws, partial ordering planning seems more

> it seems that sometimes we can directly use the constructs in OWL-S

sorry, it should be "we cannot directly use the constructs in OWL-S"

> process model to express the plan. For example:
> OperationB<OperationA,
> OperationC<OperationA,
> OperationD<OperationB,
> OperationD<OperationC,
> OperationE<OperationC
> Is there a need to make OWL-S support this feature?
> If so, the current Qos reduction algorithm for composite web service[1]
> seems infeasible to this situation and needs to be extended.
> [1] Cardoso J., Miller J., Sheth A. and Arnold J., "Modeling Quality
> of Service for Workflows and Web Service Processes", the International
> Journal on Very Large Data Bases ( VLDBJ), May 2002.

Best regards!
Manshan Lin (林满山)
Affiliation: School of Computer Science and Engineering, the South
China University of Technology
Phone: (+86)13711287277

Received on Friday, 24 December 2004 04:04:52 UTC