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

http://ir.library.oregonstate.edu/concern/defaults/bn999795c

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/.

Descriptions

Attribute NameValues
Creator
Abstract or Summary
  • 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.
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
Series
Keyword
Rights Statement
Funding Statement (additional comments about funding)
Publisher
Peer Reviewed
Language
Replaces
Additional Information
  • description.provenance : Made available in DSpace on 2012-10-16T22:09:25Z (GMT). No. of bitstreams: 1 JoshiSaketElectricalEngineeringComputerScienceDecisionTheoreticPlanning.pdf: 477824 bytes, checksum: 100ce1ede8c0300d07522f1457573b68 (MD5) Previous issue date: 2011-12
  • description.provenance : Approved for entry into archive by Deanne Bruner(deanne.bruner@oregonstate.edu) on 2012-10-16T22:09:25Z (GMT) No. of bitstreams: 1 JoshiSaketElectricalEngineeringComputerScienceDecisionTheoreticPlanning.pdf: 477824 bytes, checksum: 100ce1ede8c0300d07522f1457573b68 (MD5)
  • description.provenance : Submitted by Deanne Bruner (deanne.bruner@oregonstate.edu) on 2012-10-16T18:51:44Z No. of bitstreams: 1 JoshiSaketElectricalEngineeringComputerScienceDecisionTheoreticPlanning.pdf: 477824 bytes, checksum: 100ce1ede8c0300d07522f1457573b68 (MD5)

Relationships

In Administrative Set:
Last modified: 07/18/2017

Downloadable Content

Download PDF
Citations:

EndNote | Zotero | Mendeley

Items