mirage   mirage   mirage

Decision-Theoretic Planning with Generalized First Order Decision Diagrams

DSpace/Manakin Repository

Show simple item record

dc.creator Joshi, Saket
dc.creator Kersting, Kristian
dc.creator Khardon, Roni
dc.date.accessioned 2012-10-16T22:09:25Z
dc.date.available 2012-10-16T22:09:25Z
dc.date.issued 2011-12
dc.identifier.citation Joshi, S., Kersting, K., & Khardon, R. (2011). Decision-theoretic planning with generalized first-order decision diagrams. ARTIFICIAL INTELLIGENCE, 175(18), 2198-2222. doi: 10.1016/j.artint.2011.09.001 en_US
dc.identifier.uri http://hdl.handle.net/1957/34481
dc.description This is the author's peer-reviewed final manuscript, as accepted by the publisher. The published article is copyrighted by Elsevier and can be found at: http://www.journals.elsevier.com/artificial-intelligence/. en_US
dc.description.abstract Many tasks in AI require representation and manipulation of complex functions. First-Order Decision Diagrams (FODD) are a compact knowledge representation expressing functions over relational structures. They represent numerical functions that, when constrained to the Boolean range, use only existential quantification. Previous work has developed a set of operations for composition and for removing redundancies in FODDs, thus keeping them compact, and showed how to successfully employ FODDs for solving large-scale stochastic planning problems through the formalism of relational Markov decision processes (RMDP). In this paper, we introduce several new ideas enhancing the applicability of FODDs. More specifically, we first introduce Generalized FODDs (GFODD) and composition operations for them, generalizing FODDs to arbitrary quantification. Second, we develop a novel approach for reducing (G)FODDs using model checking. This yields – for the first time – a reduction that maximally reduces the diagram for the FODD case and provides a sound reduction procedure for GFODDs. Finally we show how GFODDs can be used in principle to solve RMDPs with arbitrary quantification, and develop a complete solution for the case where the reward function is specified using an arbitrary number of existential quantifiers followed by an arbitrary number of universal quantifiers. en_US
dc.description.sponsorship Kristian Kersting was supported by the Fraunhofer ATTRACT fellowship STREAM. Saket Joshi and Roni Khardon were partly supported by the NSF grants IIS 0936687 and IIS 0964457, and Saket Joshi was additionally supported by a Computing Innovation Postdoctoral Fellowship. en_US
dc.language.iso en_US en_US
dc.publisher Elsevier en_US
dc.relation.ispartofseries Artificial Intelligence en_US
dc.relation.ispartofseries Vol. 175 no. 18 en_US
dc.subject Knowledge representation en_US
dc.subject Automated reasoning en_US
dc.subject First order logic en_US
dc.subject Model checking en_US
dc.subject Markov decision process en_US
dc.subject Dynamic programming en_US
dc.subject Decision theoretic planning en_US
dc.title Decision-Theoretic Planning with Generalized First Order Decision Diagrams en_US
dc.type Article en_US
dc.description.peerreview yes en_US
dc.identifier.doi 10.1016/j.artint.2011.09.001

This item appears in the following Collection(s)

Show simple item record

Search ScholarsArchive@OSU

Advanced Search


My Account