Generalized Decision Diagrams: The game is not over yet!

摘要

Decision diagrams have played an influential role in computer science and AI over the past few decades, with OBDDs (Ordered Binary Decision Diagrams) as perhaps the most practical and influential example. The practical influence of OBDDs is typically attributed to their canonicity, their efficient support of Boolean combination operations, and the availability of effective heuristics for finding good variable orders (which characterize OBDDs and their size). Over the past few decades, significant efforts have been exerted to generalize OBDDs, with the goal of defining more succinct representations while retaining the attractive properties of OBDDs. On the theoretical side, these efforts have yielded a rich set of decision diagram generalizations. Practially, however, OBDDs remain as the single most used decision diagram in applications. In this talk, I will discuss a recent line of research for generalizing OBDDs based on a new type of Boolean-function decompositions (which generalize the Shannon decomposition underlying OBDDs). I will discuss in particular the class of Sentential Decision Diagrams (SDDs), which branch on arbitrary sentences instead of variables, and which are characterized by trees instead of total variable orders. SDDs retain the main attractive properties of OBDDs and include OBDDs as a special case. I will discuss recent theoretical and empirical results, and a soon-to-be-released open source package for supporting SDDs, which suggest a potential breakthrough in the quest for producing more practical generalizations of OBDDs.