Jesse Hoey, Robert St. Aubin, Alan Hu and Craig Boutilier
Department of Computer Science
University of British Columbia
Vancouver, BC, CANADA, V6T 1Z4
email: {jhoey,staubin,ajh,cebly}@cs.ubc.ca
Abstract
Recently, structured methods for solving factored Markov decisions processes
(MDPs) with large state spaces have been proposed recently to allow
dynamic programming to be applied without the need for complete state
enumeration. We propose and examine a new value iteration algorithm
for MDPs that uses algebraic decision diagrams (ADDs) to represent
value functions and policies, assuming an ADD input representation of
the MDP. Dynamic programming is implemented via ADD manipulation. We
demonstrate our method on a class of large MDPs (up to 63 million
states) and show that significant gains can be had when compared to
tree-structured representations (with up to a thirty-fold reduction in
the number of nodes required to represent optimal value functions).
To appear, UAI-99
Return to List of Papers