From: Xu Miao (xm_at_u.washington.edu)
Date: Wed Nov 19 2003 - 11:18:19 PST
Title: Symbolic Heuristic Search for Factored Markov Decision Processes
Authors: Zhengzhu Feng Eric A. Hansen
Summary:
Based on ADD and SPUDD, the authors introduced State Abstraction and
Reachability Analysis so that a much improved algorithm Symbolic LAO*
algorithm is developed with experiments showing an impressive improvement of
the performance.
Important ideas:
1. Characteristic function is used to state abstraction, which
reduced the computational complexity further than ADD. But ADD is still used
to represents the functions (value, reward, policy and heuristic functions)
2. LAO* is introduced to replace the DP in SPUDD. A masking is used
to do a reachablility analysis so that every time DP will only expend
reachable states and update those states' value. A heuristic function is
used to guid the search.
Flaws:
1. Experiments demonstrate high performance of Symb-LAO*. For some
small G, it is better than SPUDD, close to LAO*;for some big G, it is better
than both of them. But these experiments maybe not enough, especially the
big G examples are artificial ones.
Open questions:
1. Design a good heuristic function will be benefit.
2. Integrating additional strategies into a decision-theoretic
planner, as the autors claimed, but I am not very clear about it.
This archive was generated by hypermail 2.1.6 : Wed Nov 19 2003 - 11:17:39 PST