From: Lillie Kittredge (kittredl_at_u.washington.edu)
Date: Wed Nov 19 2003 - 01:33:47 PST
Feng and Hansen modify the SPUDD framework by including reachability analysis of the states -
in combination with dynamic programming, they focus the algorithm's attention on the relevant
parts of the state space, improving performance.
The authors seem to feel that Hoey et al. were on the right track with SPUDD; specifically that
the symbolic use of ADDs to manipulate sets of states instead of single states is a good tactic
for dealing with enormous state spaces. Feng and Hansen's insight was that the algorithm
could be improved by only considering states reachable from the start state. They combine this
with a LAO* search through MDP policies, using a well-designed heuristic to guide them.
It was such a relief to read something so well-written and free of grammatical errors that it's
hard to find fault. Furthermore, they designed their experiments well and conscientiously; I
particularly appreciated their acknowledgment that their algorithm's performance depended on
the starting state, and so they reported for each problem the averages of 50 runs with random
start states. As with the previous paper, though, I do wonder how applicable the test cases are
to real planning problems. As such I'd like to see more examples tested, and be more
convinced of their relevance.
As in the previous paper, an open question is, how does this perform, really, on realistic
problems, and real-world problems? Are better heuristics possible?
This archive was generated by hypermail 2.1.6 : Wed Nov 19 2003 - 01:33:48 PST