Publication
Generalized First Order Decision Diagrams for First Order Markov Decision Processes
Saket Joshi; Kristian Kersting; Roni Khardon
In: Craig Boutilier (Hrsg.). IJCAI 2009, Proceedings of the 21st International Joint Conference on Artificial Intelligence. International Joint Conference on Artificial Intelligence (IJCAI-2009), July 11-17, Pasadena, California, USA, Pages 1916-1921, Morgan Kaufmann Publishers Inc. 2009.
Abstract
First order decision diagrams (FODD) were recently introduced as a compact knowledge representation expressing functions over relational structures. FODDs represent numerical functions that, when constrained to the Boolean range, use only existential quantification. Previous work developed a set of operations over FODDs, showed how they can be used to solve relational Markov decision processes (RMDP) using dynamic programming algorithms, and demonstrated their success in solving stochastic planning problems from the International Planning Competition in the system FODD-Planner. A crucial ingredient of this scheme is a set of operations to remove redundancy in decision diagrams, thus keeping them compact. This paper makes three contributions. First, we introduce Generalized FODDs (GFODD) and combination algorithms for them, generalizing FODDs to arbitrary quantification. Second, we show how GFODDs can be used in principle to solve RMDPs with arbitrary quantification, and develop a particularly promising case where an arbitrary number of existential quantifiers is followed by an arbitrary number of universal quantifiers. Third, we develop a new approach to reduce FODDs and GFODDs using model checking. This yields a reduction that is complete for FODDs and provides a sound reduction procedure for GFODDs.