From: Andrei Alexandrescu (andrei_at_metalanguage.com)
Date: Mon Nov 24 2003 - 13:28:31 PST
Acting Optimally in Partially Observable Stochastic Domains Authors:
by R.Cassandra, Leslie Pack Kaebling, and Michael L. Littman
* Summary
The paper is an introduction to an improved Witness algorithm for
finding near-optimal solutions for POMDPs.
* Ideas
The computational efficiency of the tweaked algorithm is much better
than that of existing algorithms imported from the operations research
community, at the cost of some precision - tradeoff that the authors
deem as acceptable in concrete cases.
The Witness algorithm is the most stable and guaranteed to have
nonexponential behavior in the worst case. In practice, the authors
have reportedly obtained excellent running times and problem sizes.
* Flaws
This is just a preliminary paper to get a foot in the door, which is
entirely understandable. Its briefness relies on hefty prerequisistes
and glossing over important details of the proposed algorithm. There
are no clear tests and performance measures.
* Future work
Policy iteration is just around the corner, and it promises better
performance. Also dynamic programming methods could be applied.
Cheers,
Andrei
This archive was generated by hypermail 2.1.6 : Mon Nov 24 2003 - 13:28:32 PST