Unifying decision diagram theory for probabilistic planning

People

Supervisor

Research areas

Description

For decades decision diagrams have played an important role in many parts of Artificial Intelligence. Decision Diagrams are data structures used to represent functions and depending on the type of function one wishes to represent different forms of decision diagrams might be applicable. Affine Algebraic Decision Diagrams (AADDs) (Sanner and Allester 2005) are an extension of Algebraic Decision Diagrams to compactly represent functions with additive and multiplicative structure. One application of such decision diagrams is to symbolically solve stochastic planning tasks (Hoey et al. 1999, Sanner et al. 2010).
 
Edge-valued decision diagrams (Ciardo and Siminiceanu 2002) are another type of decision diagram which focus on exploiting additive, but not multiplicative structure. While originally designed for integer domains, these have been recently generalized to domains over arbitrary Monoids (Mattmüller et al. 2018). The question is now: are AADDs a specialized form of EVMDDs if we consider the right type of Monoid?
 
This project is about answering this question. On the theoretical side it requires to get familiar with the theory underlying both types of decision diagrams and to be able to draw connections and distinctions. On the practical side the usefulness of these type of decision diagrams may be evaluated on the latest benchmark set of the International Probabilistic Planning competition 2018.
 

 

Goals

The goal of this work is to find connections or distinction between the theory of AADDs and Monoid-based EVMDDs and (re-)evaluate their usefulness for the current benchmark set of probablistic planning domains.
 
 

Requirements

 Proficiency with C++, strong programming, data-structure and math skills, passion for artificial intelligence.
 
 

Background Literature

- Jesse Hoey and Robert St-Aubin and Alan Hu and Craig Boutilier. SPUDD: Stochastic Planning using Decision Diagrams. UAI, 1999.

 
- Scott Sanner and David Mc Allester. Affine Algebraic Decison Diagrams (AADDs) and their Application to Structured Probabilistic Inference. IJCAI, 2005.
 
- Scott Sanner and William Uther and Karina Valdivia Delgado. Approximate Dynamic Programming with Affine ADDs. AAMAS, 2010.
 
- Robert Mattmüller and Florian Geißer and Benedict Wright and Bernhard Nebel. On the Relationship between State-dependent Action Costs and Conditional Effects in Planning. AAAI, 2018.
 
 
 

Gain

 Research experience, and knowledge of advanced AI topics.
 
 

Keywords

 artificial intelligence, stochastic planning, decision diagrams

 

 

Updated:  1 June 2019/Responsible Officer:  Dean, CECS/Page Contact:  CECS Marketing