- From: Drew McDermott <drew.mcdermott@yale.edu>
- Date: Sun, 1 Feb 2004 17:52:24 -0500 (EST)
- To: abcharl@keyworld.net
- Cc: nau@cs.umd.edu, a.tate@ed.ac.uk, public-sws-ig@w3.org
> [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