From: Tal Shaked (tshaked_at_u.washington.edu)
Date: Fri May 09 2003 - 10:57:53 PDT
Incremental Pruning: A Simple, Fast, Exact Method for Partially Observable
Markov Decision Process – Cassandra, Littman, Zhang
This paper looks at some aspects and variations of incremental pruning for
solving POMDPs, compares them to other algorithms, and provides analysis and
empirical results arguing that it is currently the best method.
The most important ideas are contained somewhere between the second column
of page two and the end of page five, but I didn’t understand these parts or
know the background to make much sense out of it. It seems that at some
point they have an equation that is conceptually simpler and has better
performance than what is used in the witness algorithm. They then show that
although the worst-case complexities are the same for both algorithms in the
number of linear programs and constraints, the best case is asymptotically
better than the witness algorithm.
There did not seem to be much of a motivation section. The background
seemed insufficient for a reader who is not very familiar with the problems,
current algorithms, and the standard notation.
I’m not sure about current research directions since I don’t have much
intuition of the problem, current solutions, and which areas can be
improved.
This archive was generated by hypermail 2.1.6 : Fri May 09 2003 - 10:57:14 PDT