PhD Defense: First Order Decision Diagrams for Decision Theoretic Planning

July 22, 2010
3:00 pm - 5:00 pm
Halligan 127
Speaker: Saket Joshi, Tufts University


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. We recently introduced First Order Decision Diagrams (FODD) and Generalized FODDs (GFODD), which are compact representation schemes for complex functions over relational structures, and associated algorithms that together lead to efficient solutions of RMDPs. FODDs capture an expressive class of functions generalizing existential quantification in logic to real valued functions, and GFODDs capture both existential and universal quantification. In this talk I will walk through our work on FODDs and GFODDs, their applications to solving RMDPs, and experimental results on FODD- Planner, a RMDP solver based on FODDs showing competitive performance with top ranking stochastic planning systems from the International Planning Competition.