TU 3: Decision Diagrams in Automated Planning and Scheduling
Sunday June 22nd, 2014. (PM - quarter day)
Decision diagrams have proved to be a useful data structure for model checking, temporal verification, graphical model inference, and factored planning (factored MDPs and POMDPs among may applications). This tutorial will cover the foundations of binary and algebraic decision diagrams (BDDs & ADDs) -- their properties, their algorithms, their use in various automated planning settings (including a discussion of when other techniques are preferable to decision diagrams), and tricks of the trade (variable orderings, approximation, and application-specific operations) that help one achieve maximal efficiency in practice. Beyond BDDs and ADDs, the tutorial will also cover a variety of less well-known but important decision diagrams and their applications: Zero-suppressed DDs (ZDDs) for set representation, Affine ADDs (AADDs) for arithmetic function representation, and recent extensions of decision diagrams to continuous variables (XADDs) enabling novel exact solutions to a variety of continuous planning problems. While focusing on the theory of decision diagrams, the tutorial will constantly relate the theory to practical applications in automated planning and scheduling.