From: Tal Shaked (tshaked_at_cs.washington.edu)
Date: Tue May 06 2003 - 11:32:32 PDT
Incremental Contingency Planning - Dearden, Meuleau, Ramakrishnan, Smith,
Washington
This paper discusses techniques for figuring out the best places to insert
contingent branches given a seed plan, dealing with domains that have
various types of uncertainty including continuous quantities such as time
and resources.
The problem is that although it is possible to construct a main plan, it is
not possible to plan in advance for all potential contingencies. There would
basically be an infinite number of these. Instead it is important to add
branches at the best places that improve overall utility. It is costly to
compute the expected utility at all these points, so a heuristic is
necessary to estimate the utility, and then the same planner can be used to
create a plan at that branch point. It is pointed out that branching at
points most likely to fail is not necessarily good since it may be too late
(ie not enough resources to accomplish anything).
The utility is approximated by creating a planning graph and
back-propagating the utility through the proposition layers and actions
showing expected value given the amount of resources at a given point
through a piece-wise function. Dealing with conjunctive preconditions
involves creating tables with conditions, and then copying those tables into
the nodes that satisfy the conditions and repeatedly back-propagating.
Dealing with conjunctive effects involves considering the tables in all the
effects and taking the max. However, this does not consider joint value of
effects, which requires a few additions to computing the max.
These utility values can be used to find branching points by looking at when
their estimate value exceeds the utility of the main plan at some given
amount of resource. Without any contingency the main plan does best, but
with some contingency, branching at these points can result in doing better
than sticking to the main plan and failing to achieve the initially expected
utility.
Perhaps more could be said about using utility estimates, or maybe going
through a more concrete example of something happening to the main plan and
choosing a branch that was created from the described methods. The work is
in the early stages so there are no real experiments. Also many assumptions
are made, and depending on the domain, some may be more significant than
others, such as ignoring mutual exclusions.
As described, there are many future areas of work such as modeling the real
world more accurately (sensing actions having costs, noisy) and relaxing
some of the assumptions in calculating the heuristics. Perhaps there are
ways of guiding contingent planning so that the agent can deal more
effectively in real-time by borrowing some of these heuristic ideas and
computing advance not only branches, but information to guide online
replanning.
This archive was generated by hypermail 2.1.6 : Tue May 06 2003 - 11:32:37 PDT