Article

 

Decision-Theoretic Planning with Generalized First Order Decision Diagrams Public Deposited

Contenu téléchargeable

Télécharger le fichier PDF
https://ir.library.oregonstate.edu/concern/articles/bn999795c

Descriptions

Attribute NameValues
Creator
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.
  • Keywords: Markov decision process, Model checking, Automated reasoning, Decision theoretic planning, Knowledge representation, Dynamic programming, First order logic
Resource Type
DOI
Date Available
Date Issued
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
Journal Title
Journal Volume
  • 175
Journal Issue/Number
  • 18
Déclaration de droits
Funding Statement (additional comments about funding)
  • 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.
Publisher
Peer Reviewed
Language
Replaces

Des relations

Parents:

This work has no parents.

Articles