From: Stanley Kok (koks_at_cs.washington.edu)
Date: Mon Apr 28 2003 - 17:57:30 PDT
Paper Title: Probabilistic Planning in the Graphplan Framework
Authors: Avrim L. Blum and John C. Langford
One-line summary:
This paper presents probabilistic extensions of Graphplan viz.
PGraphplan and TGraphplan.
Most Important Ideas in the Paper:
1. The heuristic of value propagation. It seems that this
heuristic can be extended to any graph representation of a planning
problem with a payoff at the goal.
2. The heuristic of "neededness". This heuristic for forward search
mirrors the mutex heuristic of regression search.
Flaw in the Paper:
1. The paper does not conclusively show how much each heuristic
(value propagation and neededness) contribute to the performance
of PGraphplan. It merely claims in the Discussion section, that
value propagation has a more pronounced contribution.
2. The paper states that PGraphplan is _generally_ slower than
Graphplan (presumably on deterministic problems). However, it
does not provide any emprical results nor state when PGraphplan
is faster.
Important, open research questions:
1. Could value propagation be used as a heuristic for vanilla
Graphplan? If so, Would the cost of computing the heuristic be offset
by the reduction in solution times?
2. Why does the computationally less intensive TGraphplan perform
worse than PGraphplan on the Moat and Castle and 8-puzzle problems?
This archive was generated by hypermail 2.1.6 : Mon Apr 28 2003 - 17:57:31 PDT