  The Sentential Decision Diagram (SDD) is a tractable representation of
Boolean functions that subsumes the famous Ordered Binary Decision Diagram
(OBDD) as a strict subset. SDDs are attracting much attention because they are
more succinct than OBDDs, as well as having canonical forms and supporting many
useful queries and transformations such as model counting and Apply operation.
In this paper, we propose a more succinct variant of SDD named Variable Shift
SDD (VS-SDD). The key idea is to create a unique representation for Boolean
functions that are equivalent under a specific variable substitution. We show
that VS-SDDs are never larger than SDDs and there are cases in which the size
of a VS-SDD is exponentially smaller than that of an SDD. Moreover, despite
such succinctness, we show that numerous basic operations that are supported in
polytime with SDD are also supported in polytime with VS-SDD. Experiments
confirm that VS-SDDs are significantly more succinct than SDDs when applied to
classical planning instances, where inherent symmetry exists.
