Uncertainty in Artificial Intelligence
First Name   Last Name   Password   Forgot Password   Log in!
    Proceedings   Proceeding details   Article details         Authors         Search    
Solving POMDPs by Searching the Space of Finite Policies
Nicolas Meuleau, Kee-Eung Kim, Leslie Kaelbling, Anthony Cassandra
Abstract:
Solving partially observable Markov decision processes (POMDPs) is highly intractable in general, at least in part because the optimal policy may be infinitely large. In this paper, we explore the problem of finding the optimal policy from a restricted set of policies, represented as finite state automata of a given size. This problem is also intractable, but we show that the complexity can be greatly reduced when the POMDP and/or policy are further constrained. We demonstrate good empirical results with a branch-and-bound method for finding globally optimal deterministic policies, and a gradient-ascent method for finding locally optimal stochastic policies.
Keywords: POMDPs, Finite State Controllers
Pages: 417-426
PS Link: http://www.cs.brown.edu/people/nm/PS_files/uai99_1.ps
PDF Link: /papers/99/p417-meuleau.pdf
BibTex:
@INPROCEEDINGS{Meuleau99,
AUTHOR = "Nicolas Meuleau and Kee-Eung Kim and Leslie Kaelbling and Anthony Cassandra",
TITLE = "Solving POMDPs by Searching the Space of Finite Policies",
BOOKTITLE = "Proceedings of the Fifteenth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-99)",
PUBLISHER = "Morgan Kaufmann",
ADDRESS = "San Francisco, CA",
YEAR = "1999",
PAGES = "417--426"
}


hosted by DSL   •   site info   •   help