Beyond Stars - Generalized Topologies for Decoupled Search

Decoupled search decomposes a classical planning task bypartitioning its variables such that the dependencies betweenthe resulting factors form a star topology. In this topology,a single center factor can interact arbitrarily with a set ofleaf factors. The leaves, however, can interact with each otheronly indirectly via the center. In this work, we generalize thisstructural requirement and allow arbitrary topologies. Thecomponents must not overlap, i. e., each state variable is as-signed to exactly one factor, but the interaction between fac-tors is not restricted. We show how this generalization is con-nected to star topologies, which implies the correctness ofdecoupled search with this novel type of decomposition. Weintroduce factoring methods that automatically identify thesetopologies on a given planning task. Empirically, the gener-alized factorings lead to increased applicability of decoupledsearch on standard IPC benchmarks, as well as to superiorperformance compared to known factoring methods.