From: Sumit Sanghai (sanghai_at_cs.washington.edu)
Date: Tue Apr 29 2003 - 10:53:58 PDT
Probabilistic Planning in the GraphPlan Framework
-- Avrim Blum and John Langford
Summary : The paper extends the GraphPlan algorithm to a finite time horizon probabilistic domain
Ideas : The 2 most important ideas presented in the paper are the PGraphPlan and TGraphPlan. PGraphPlan solves the problem of finding the policy which maximizes the expectation of reaching the goal state. PGraphPlan uses forward chaining as opposed to backward chaining. The reason being that backward chaining can be quite costly because of uncertainty in the action model. To reduce the time taken for forward chaining the paper presents heuristics which can detect if a proposition at time t is "useful" in reaching the goal state. These heuristics do not use any probabilistic information and can be applied to GraphPlan as well.
TGraphPlan on the other hand finds a policy which gives the highest probability of reaching the goal state. One can immediately see that the backward chaining used by GraphPlan can be reused here.
Flaws : Some of the flaws in the paper are that it does not have any substantial new information to give. TGraphPlan is a direct extension of GraphPlan and seems quite obvious. PGraphPlan uses forward chaining because backward chaining can be quite costly (which the authors are not convincingly able to put forward). And also, the heuristics used for forward chaining remove the "useless" propositions and apart from that the algorithm uses standard dynamic programming. The experiments themselves do not explain how the heuristics were useful and how PGraphPlan compares in time with GraphPlan (on deterministic problems).
Future Work : There is some scope for future work especially in finding heuristics which use the probabilistic information and how these heuristics may help in backward and forward search. Apart from that, it might be useful to look at how GraphPlan can be used in the discounted reward model (both for finite and infinite domains).
This archive was generated by hypermail 2.1.6 : Tue Apr 29 2003 - 10:54:00 PDT