Re: Composition as planning

I think people may be getting a somewhat misleading impression
of AI planning technology, its capabilities, and its limitations.

It's true that planners typically assume that they know
how the state of the world can change and that changes are
controlled by the actions in the plan.  That's how they
decide that a certain effect can be achieved by performing
operation B after operation A, or that A1 should be
combined with B1, not B2, while A2 needs B2 or B3.

Anything that wants to compose web services will have to
engage in some reasoning of that sort.  People do it
for example when they go to an on-line bookshop and decide
to buy something by putting it in their shopping basket
and then going to the checkout, etc.

However, plan construction is not the end of the story.  There's
also plan execution, execution monitoring, failure recovery, and plan
repair.  The example given earlier -- someone buys the book you were
going to buy and no more are in stock -- is one that can be handled in
that way.  The failure (you can't put the book into your basket, or
you can't buy it, or it can't be delivered soon enough) is detected,
and then the plan must then be repaired.

I am not saying all problems have been solved.  Far from it,
and it will take research to discover how well WS composition
can be handled by AI planning technology; nonetheless many
of the problems have been encountered in other contexts.

(An example of a difficult problem: if a plan needs repair,
what aspects of the existing plan should be preserved?)

Here's a quick list of some other elements of planning technology
that may be relevant.

(I mention some of the work I'm most familar with, and I know
I've left out many things, for which I apologize.  I hope others
will fill in some of the gaps.)

* Partial plans and combining planning with execution.  (For example,
  the I-X project in Edinburgh has developed "process panels" that
  can mix execution of steps in a plan with further planning.  We
  are currently strengthening the planning side and have to deal
  with the issues mentioned by Jim Hendler and others.  Earlier,
  we explored execution monitoring and plan repair with O-Plan.)
  (See also David Wilkins's SIPE and Cypress at SRI.)

* Mixed-initiative planning.  Here's some decisions are made by the
  planning software while others are made by the user or another
  agent.  (A hard problem here is a version of one Drew McDermott
  mentioned: how does the planner know when it should stop planning
  and ask another agent to do something?)

* Advice (as with the SIPE) to guide the planner.
  (It's natural to combine that with mixed-initiative planning.)

* Authority, telling the planner what it can do.  For example,
  with O-Plan we can tell the planner to plan only down to
  a certain level; a planner could also be restricted to
  certain "phases" of the plan: e.g. fully planning only
  the initial steps.  (This also fits naturally with mixed-initiative
  planning.)

* Obtaining information from external databases (perhaps ones
  not even known before plan execution began).

* Ability to handle many different constraint types (e.g. temporal,
  resource production and usage) and to have plug-in constraint-managers.

* A plan can include "goal-structure" (such as why an action
  was included or why action A must complete before B can begin);
  this can indicate what needs to me monitored during execution
  and also that certain partial failures have no significant
  impact and so may be ignored.

* Representation of events and even processes that are outside
  the control of the agent(s) executing the plan.  They come
  up during execution but some may also be described to the planner
  in advance.

I also can't help thinking again that some of the problems will
really be scheduling problems.  A good way to combine a planner
and scheduler could be very useful.

-- Jeff

Received on Friday, 6 February 2004 12:03:29 UTC