From: Kevin Sikorski (kws_at_cs.washington.edu)
Date: Fri May 09 2003 - 10:27:20 PDT
Incremental Pruning: A Simple, Fast, Exact Method for Partially Observable
Markov Decision Processes
Anthony Cassandra, Michael L. Littman, Nevin L. Zhang
This paper describes an improvement on the Witness algorithm for exactly
solving POMDPs, provides time complexity bounds, and evaluates it on
several example domains.
The main contribution of this paper is identifying the identity equation:
purge (A crosssum B crossum C) = purge(purge(A crosssum B) crosssum C).
The authors were able to leverage this equation in their algorithm.
This paper offered at best a terse introduction to the background needed
to fully understand what was being presented. I am still trying to gain
an intuitive understanding of exactly what these vectors represent in the
POMDP, and exactly what filtering them in this manner provides.
Presumably, these are standard techniques that are well explained in other
papers on this topic.
The algorithm seems somewhat constrained by the fact that it can only
handle discrete probability distributions. Of course, we can always
discretize the POMDP, but then our answer is no longer exact.
I'm afraid I can't provide any meaningful future research directions for
this paper, as they didn't provide enough background for me to fully
understand their approach.
This archive was generated by hypermail 2.1.6 : Fri May 09 2003 - 10:27:21 PDT