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.