From: Lucas Kreger-Stickles (lucasks_at_cs.washington.edu)
Date: Wed Nov 19 2003 - 11:00:14 PST
* Paper title/Author
Symbolic Heuristic Search for Factored Markov Decision Processes
Feng and Hansen
* One-line summary
The authors present an algorithm (symbolic-LAO*) that combines the use
of state abstraction with the use of admissible hueristics to improve
the performance when solving MDPs.
* The (two) most important ideas in the paper, and why
I think that one of the major ideas of the paper is that heuristics and
dynamic programming can be combined to create algorithms that draw on
the strengths of both.
The other major idea I find throughout the paper is that ideas from
model checking (such as ADDs) can be efficitvly used to reduce both the
memory requirements and the size of the search space when solving
decision theotretic planning problems. While they concede that the use
of ADDs was not an origional idea, this paper does contribute further
empirical evidence for their use.
* The one or two largest flaws in the paper
If find the use of artificial examples to be esspecially troubling.
When they first introduce the idea they present it as OK since the
problems they construct are supposed to be harder for huerisitic search
to solve. However, when they then go on to compare the results of
symbolic-LAO* against LAO* (which also uses hueristics) and conclude
that symbolic-LAO* is better by way of the artificial examples I get
suspicous.
* Identify two important, open research questions on the topic, and why
they matter
I would like to see some data where symbolic-LAO* outperforms other
algorithms on 'real' (ie not artificial') planning problems.
Also, this paper briefly mentions techniques that they used to
automatically generate admissible heurisitcs. While not the focus of
this paper, I think more work in this area would be of great benifit to
the AI community.
This archive was generated by hypermail 2.1.6 : Wed Nov 19 2003 - 11:00:14 PST