From: Danny Wyatt (danny_at_cs.washington.edu)
Date: Wed Nov 19 2003 - 09:54:30 PST
Symbolic Heuristic Search for Factored Markov Decision Processes
Zhengzhu Feng, Eric A. Hansen
Summary
The authors describe a modification of the LAO* algorithm that searches
through sets of states in an MDP instead of single states. The sets of
states---as well as every other part of the MDP---are represented with
ADD's.
Important Ideas
Representing a set of states with a boolean function over the state
variables allows a set of states to in turn be represented with an ADD
(or BDD). If the value function over states is also represented as an
ADD, then irrelevant states can be "masked" out of the value function
using existing ADD operations between the value ADD and the ADD for a
set of states.
Flaws
The authors say that the search space is so large that they had to use
their ADD representations for non-symbolic LAO* and SPUDD for some
tests, but they never specify which. I'd like to see a more
fine-grained decomposition of the comparisons to better show any
separate effects of their ADD representations and their symbolic LAO*
algorithm.
Open Questions
Just what is a realistic MDP problem? The authors are unsatisfied with
how much better their representations performed than SPUDD on the
factory problems, so they devise new ones to tax their representations
and algorithm more. But which of these (if either) is more likely in
applied situations? Or are there several classes of problems each
admitting their own best algorithm?
This archive was generated by hypermail 2.1.6 : Wed Nov 19 2003 - 09:53:53 PST