From: Kevin Sikorski (kws_at_cs.washington.edu)
Date: Tue May 06 2003 - 00:01:09 PDT
Incremental Contingency Planning
Richard Dearden, Nicolas Meuleau, Sailesh Ramakrishnan, David E. Smith,
Rich Washington
This paper provides a method for identifying the places in a plan where
providing contingency plans provides the most expected utility.
The authors used the example of a Mars rover to show that no matter how
good your planner is, there is always the possibility that your initial
plan fails, either due to impassible terrain, or damage to the rover, or
some other condition. In this case, it is much more efficient to have
contingency plans on the rover itself, than to wait for the next
communication window for mission control to provide them directly. This
paper provides a method to "efficiently" decide where such contingency
plans should be placed to maximize the expected utility in the event of
such a failure. Where in the plan these contingency branches should be
located is identified by backpropgating tables of expected rewards and
preconditions through the plan graph.
The authors did a good job of identifying future research directions and
listing the assumptions that the algorithm relies on. Future research
extensions included handling noise in sensor information, propagating full
distributions through the plan graph rather than just scalars, and
allowing mutex relations in the plan graph.
What is the worst-case for this algorithm? Because we have to copy tables
in cases where an action has multiple pre-conditions, I can see us having
many table entries (about O(|states|*|properties|)) in a sufficiently
convoluted problem. Then again, since we are regressing, we aren't likely
to visit all states. A related question is how often do these worst-case
problems appear in real-life rover planning problems? I would expect them
to be pretty rare. And seeing some graphs of how this performs in even a
toy domain would be nice - there were absolutely no performance numbers at
all here.
This archive was generated by hypermail 2.1.6 : Tue May 06 2003 - 00:01:10 PDT