Compact representations of complex knowledge form the core of solutions to many problems in Artificial Intelligence. Sequential decision making under uncertainty is one such important problem and Decision Theoretic Planning (DTP) has been one of the most successful frameworks for this task. Recent advances in DTP have focused on generating efficient solutions for Relational Markov Decision Processes (RMDP), a formulation that models problems that are naturally described using objects and relations among them. The core contribution of this thesis is the introduction of compact representation schemes for functions over relational structures, and associated algorithms that together lead to efficient solutions of RMDPs. Our First Order Decision Diagrams (FODD) representation captures an expressive class of functions generalizing existential quantification in logic to real valued functions, and the Generalized FODDs (GFODDs) capture both existential and universal quantification. The thesis develops several algorithms for composition and logical simplification of functions represented by FODDs and GFODDs using theorem proving and model-checking methods. We prove various theoretical properties on their correctness and their applicability in the context of solutions for RMDPs. Through implementation, experimentation and empirical evidence we demonstrate the success of FODD-based algorithms to solve RMDPs, by applying them to solve stochastic planning problems that have been used as challenge benchmarks in planning research.
|Commitee:||BLUMER, ANSELM, BRODLEY, CARLA, MILLER, ERIC, TADEPALLI, PRASAD|
|School Location:||United States -- Massachusetts|
|Source:||DAI-B 71/12, Dissertation Abstracts International|
|Subjects:||Artificial intelligence, Computer science|
|Keywords:||Artificial intelligence, Automated planning, Decision theoretic planning, Knowledge representation, Markov decision process, Relational markov decision process|
Copyright in each Dissertation and Thesis is retained by the author. All Rights Reserved
The supplemental file or files you are about to download were provided to ProQuest by the author as part of a
dissertation or thesis. The supplemental files are provided "AS IS" without warranty. ProQuest is not responsible for the
content, format or impact on the supplemental file(s) on our system. in some cases, the file type may be unknown or
may be a .exe file. We recommend caution as you open such files.
Copyright of the original materials contained in the supplemental file is retained by the author and your access to the
supplemental files is subject to the ProQuest Terms and Conditions of use.
Depending on the size of the file(s) you are downloading, the system may take some time to download them. Please be