From: Bhushan Mandhani (bhushan_at_cs.washington.edu)
Date: Wed Nov 19 2003 - 10:06:27 PST
Summary:
The paper combines heuristic search with symbolic model checking
(specifically the Spudd planner) for solving MDP's.
Main Ideas:
1. Symbolic model checking algorithms use dynamic programming to solve
MDP's. They cover the entire state space, which can be large. Adding
heuristic search, so that dynamic programming is done over a subset of
states i.e, the states reachable from the start state, improves
efficiency.
2. In the LAO* search done here, everything is stored as an ADD. Further,
the ADD's are made even more compact by "masking", and this further prunes
the set of states considered.
3. In the results in this paper, symbolic LAO* was seen to outperform
Spudd.
Flaw:
1. The problems a1-a4 used in experimental evaluation are all artificial.
The use of real-world MDP's to determine the gain in efficiency obtained
using the proposed method would have been better.
Future Work:
Further exploration of general methods to prune the state space. The idea
of combining heuristic search with dynamic programming seems powerful and
should be explored further.
This archive was generated by hypermail 2.1.6 : Wed Nov 19 2003 - 10:06:28 PST