From: Alan L. Liu (aliu_at_cs.washington.edu)
Date: Wed Nov 19 2003 - 01:23:16 PST
Paper Reviewed: Symbolic Heuristic Search for Factored Markov Decision
Processes
Paper Authors: Zhengzhu Feng and Eric A. Hansen
Summary:
The paper discusses a way of using an admissible heuristic to create a
better MDP solving algorithm. By using dynamic programming that focuses
only on reachable state sets, the authors are able to show a significant
performance boost over SPUDD.
Important Ideas:
SPUDD does dynamic programming over all possible start states, but the
symbolic LAO* algorithm presented here restricts it to possible states.
This way avoids a lot of irrelevant computations.
The dynamic programming step can actually produce an admissible
heuristic to guide the algorithm in deciding how to expand from a
partial plan. This guarantees that the algorithm will find an optimal
policy.
Flaws:
I would have liked for them to explain further how an admissible
heuristic derives from DP.
Open questions:
Solutions for model checking can be used in the planning domain. It
seems that both SPUDD and this sym-LAO* algorithm ported techniques used
in VLSI design and verification. One might do a survey of solutions to
problems in other domains that are also relevant to problems in AI. It
might be the case that those solutions offer significantly better
performance than what's been explored in AI. More interestingly, they
might shed some insight on the nature of the problem that was never
noticed or exploited.
Is there an even better heuristic for planning? Better heuristics would
generate smaller search space, which in turn would improve search
performance. Until someone can prove that algorithm z is optimal, there
ought to be more refinements to be made.
This archive was generated by hypermail 2.1.6 : Wed Nov 19 2003 - 01:23:21 PST