Algebraic sentential decision diagrams in symbolic probabilistic planning

Abstract

The Sentential Decision Diagram (SDD) is a novel data structure that compactly represents Boolean functions, like Binary Decision Diagrams (BDDs), but with a theoretical advantage in some classes of functions, when SDDs may be exponentially smaller than BDDs. Algebraic Decision Diagrams (ADDs) are an extension of BDDs which allows numeric values in terminal nodes, for representing factored case functions onto real numbers. In this paper, we propose an algebraic extension of SDDs, the Algebraic SDD (ASDD), and examine its suitability in probabilistic planning using a symbolic value iteration algorithm that employs ASDDs to maintain and manipulate its functions when solving Markov Decision Problems (MDPs). © 2013 IEEE.