Uncertainty in Artificial Intelligence
First Name   Last Name   Password   Forgot Password   Log in!
    Proceedings   Proceeding details   Article details         Authors         Search    
Incremental Pruning: A Simple, Fast, Exact Method for Partially Observable Markov Decision Processes
Anthony Cassandra, Michael Littman, Nevin Zhang
Abstract:
Most exact algorithms for general partially observable Markov decision processes (POMDPs) use a form of dynamic programming in which a piecewise-linear and convex representation of one value function is transformed into another. We examine variations of the "incremental pruning'' method for solving this problem and compare them to earlier algorithms from theoretical and empirical perspectives. We find that incremental pruning is presently the most efficient exact method for solving POMDPs.
Keywords: POMDPs, witness algorithm.
Pages: 54-61
PS Link: http://www.cs.duke.edu/~mlittman/papers/uai97-pomdp.ps
PDF Link: /papers/97/p54-cassandra.pdf
BibTex:
@INPROCEEDINGS{Cassandra97,
AUTHOR = "Anthony Cassandra and Michael Littman and Nevin Zhang",
TITLE = "Incremental Pruning: A Simple, Fast, Exact Method for Partially Observable Markov Decision Processes",
BOOKTITLE = "Proceedings of the Thirteenth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-97)",
PUBLISHER = "Morgan Kaufmann",
ADDRESS = "San Francisco, CA",
YEAR = "1997",
PAGES = "54--61"
}


hosted by DSL   •   site info   •   help