From: Christophe Bisciglia (chrisrb_at_cs.washington.edu)
Date: Tue Apr 29 2003 - 11:15:19 PDT
Avrim L. Blum and John C. Langford Probabilistic Planning in the Graphplan
Framework
This paper presents a way to modify the structure of a planning graph to
apply ideas from Graphplan to contingent probabilistic models. PGraphplan
produces an optimal policy (in terms of its probability for success),
while TGraphplan is faster (greedy), but sub-optimal.
One interesting idea presented by the paper was a means to compute a
node.s .neededness.. Essentially, if all paths from P to the goal use Q,
any state containing P but not Q can be pruned.
Another idea presented is that of value propagation. This propagates the
heuristic value throughout the graph. This is useful because the heuristic
is computed in such a way that the hvalue of any node is greater than or
equal to its true value, so if the hvalue of some node at time t is less
than t, it can safely be pruned as there would be no way to reach the goal
in the time remaining.
As far as flaws in the paper go, there were two things that came to mind.
First, with all this talk of Graphplan, it would have been nice to see the
planners specifically compared to Graphplan, rather than just presenting
speculation. The other flaw I noticed was a lack of concrete discussion of
how much pairwise .needed. nodes contributed in comparison to value
propagation.
This paper presented several ideas that might be helpful, yet they didn.t
attempt. First, with respect to pairwise .needed. nodes, it would be
interesting to see if identifying nodes as redundant would be worth the
difficulty of propagation. Another thing that struck me, sort of as a
flaw, and sort of as an open question had to do with value propagation.
Since this is a probabilistic domain, and some actions are more likely to
occur than others, why propagate hvalues evenly over edges? Wouldn.t it
make sense to use some notion of likelihood while propagating the
heuristic?
This archive was generated by hypermail 2.1.6 : Tue Apr 29 2003 - 11:15:20 PDT