Dissertation/Thesis Abstract

First order decision diagrams for decision theoretic planning
by Joshi, Saket, Ph.D., Tufts University, 2010, 190; 3427479
Abstract (Summary)

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.

Indexing (document details)
Advisor: Khardon, Roni
Commitee: BLUMER, ANSELM, BRODLEY, CARLA, MILLER, ERIC, TADEPALLI, PRASAD
School: Tufts University
Department: Computer Science
School Location: United States -- Massachusetts
Source: DAI-B 71/12, Dissertation Abstracts International
Source Type: DISSERTATION
Subjects: Artificial intelligence, Computer science
Keywords: Artificial intelligence, Automated planning, Decision theoretic planning, Knowledge representation, Markov decision process, Relational markov decision process
Publication Number: 3427479
ISBN: 9781124319353
Copyright © 2019 ProQuest LLC. All rights reserved. Terms and Conditions Privacy Policy Cookie Policy
ProQuest