From: MAUSAM (mausam_at_cs.washington.edu)
Date: Tue Apr 29 2003 - 11:20:33 PDT
Probabilistic Planning in Graphplan Framework
A. Blum and J. Langford
The authors extend the Graphplan framework to solve problems in
probabilistic domains.
The authors build a planning graph from the initial states by representing
uncertain outcomes as part of the planning graph itself. They compute some
speed-up information like neededness and a form of value propagation which
prune some impossible states. After building such a graph they do a
forward state space search to find the optimal value function by doing
dynamic programming. This is called PGRAPHPLAN.
The authors also develop a non-optimal but fast strategy (TGRAPHPLAN) in
which they find the most probable path to the goal and then create
branches on such a path.
All methods based on planning graph have an explicit time horizon
requirements, which essentially means that one has to increase the
horizon gradually which takes up a lot of time. In deterministic setting
life is easier, since if a goal can be achieved in time t then it can also
be achieved in time t+1 with no additional benefits. However, in
probabilistic setting the probability of achieving the goal could increase
as time passes by and we might want to optimise a more general objective
function over time and probability of success. Such a paradigm would be
very hard to represent in such a framework.
Similarly, if we are talking about infinite horizon reward model, then it
is totally unclear if it is even possible to be done using such
techniques.
Moreover, a lot of speed up heuristics were suggested, however it was not
mentioned how much each of these heuristics actually improved the various
solutions. In fact, some discussion of where each heuristics comes handy
would have been very appropriate.
I think there is a possible study comparing various backward information
that could be propagated. The authors suggest neededness. Khambampati &
Parker study redundancy. These could be compared to see which are useful
in what scenarios.
In this solution, the state space is explicitly enumerated. I wonder if we
can do better.
This archive was generated by hypermail 2.1.6 : Tue Apr 29 2003 - 11:20:34 PDT