Re: Composition as planning

> [Charlie Abela]

> HTN planners seem to fit nicely in the WS
> composition scenario since decomposition of
> complex services will be required to eventually
> incorporate its primitive task into a new complex
> service. Is it always the case that a complex
> service be fully decomposed into its primitive
> components? It could be the case that a complex
> service be included into a yet more complex one
> without there being the need for decomposition.
> Right? How is this handled in HTN planning?
> 
 ...
> I appreciate that there is work in progress over
> such issues, but can someone shed some more light
> on the issues relating the different planning
> techniques:  HTN, partial order,
> estimated-regression planning etc with Web
> services composition?

The biggest gap in current planning research is that it doesn't have a
good theory of when to stop planning.  You raised one important case,
when a hierarchical plan should remain "undecomposed" for now,
possibly until execution time.  Another is when the choice of action
at a future time depends on the messages received in the course of (or
other outcomes of) prior actions.  This is called _contingent_
planning, and classically it's been treated as requring an exhaustive
decision tree instead of a linear sequence of actions.  But in the
case of loops, or long-range plans, it would seem that there are times
when the planner should stop planning after it has convinced itself
that it has found a course of action that stands a good chance of
being completable in a hopefully-not-too-sub-optimal way.  For the
last few decades, this _partial-planning_ problem has been mentioned
many times, but I don't know of any solution to it.

I'm hopeful that my current Optop planner (your reference [1]) might
be a good framework for exploring this issue, but so far it's just a
hope.  I am currently debugging an extension to Optop so it can mix
hierarchical and action-based planning.  I don't know whether it will
be successful until I get it debugged and tested.  This mixture is
important because, as you implied, web-service planning requires
canned hierarchical plans, but the ability to come up with new
compositions requires understanding what each individual action can
achieve on its own.

The reason I think that Optop might be good at partial planning (not
to be confused with partial-order planning) is that its search states
are of the form

         plan prefix
         + plausible completion

The _plan prefix_ is the sequence of actions the plan will start with
if this search state can be extended to a complete plan.  It's
guaranteed to be executable.  In the initial state, the plan prefix is
empty.  The _plausible completion_ is a combination of a tree of
actions extracted from the regression-match graph and the execution
state of hierarchical plans the planner is commmitted to in this
search state.  The plan is complete when the plausible completion is
empty, in which case the sequence of actions achieves the goal.
What's nice about the plausible completion is that it comes with an
execution scenario that ignores destructive interactions among future
actions and arrives at an estimate of the objective function in the
final state.  What's nice about the plan prefix is that you can start
executing it now.  

So theoretically you can compare different partial plans, and you can
stop planning and execute some of the actions whenever further
planning seems counterproductive.  It's not clear when that is, of
course.

I wish I had a paper describing this, but I don't yet.  Note that I
left contingent planning out of this account.  I view it as
orthogonal. 

-- 
                                   -- Drew McDermott
                                      Yale Computer Science Department

Received on Sunday, 1 February 2004 17:52:51 UTC