Beyond Stars – Generalized Topologies for Decoupled Search

Authors

  • Daniel Gnad Saarland University, Saarland Informatics Campus, Saarbrücken, Germany Linköping University, Sweden
  • Álvaro Torralba Aalborg University, Denmark
  • Daniel Fišer Saarland University, Saarland Informatics Campus, Saarbrücken, Germany Czech Technical University in Prague, Faculty of Electrical Engineering, Czech Republic

Keywords:

Classical Planning, Problem Decomposition, Decoupled Search, Heuristic Search

Abstract

Decoupled search decomposes a classical planning task by partitioning its variables such that the dependencies between the resulting factors form a star topology. In this topology, a single center factor can interact arbitrarily with a set of leaf factors. The leaves, however, can interact with each other only indirectly via the center. In this work, we generalize this structural requirement and allow arbitrary topologies. The components must not overlap, i.e., each state variable is assigned to exactly one factor, but the interaction between factors is not restricted. We show how this generalization is connected to star topologies, which implies the correctness of decoupled search with this novel type of decomposition. We introduce factoring methods that automatically identify these topologies on a given planning task. Empirically, the generalized factorings lead to increased applicability of decoupled search on standard IPC benchmarks, as well as to superior performance compared to known factoring methods.

Downloads

Published

2022-06-13

How to Cite

Gnad, D., Torralba, Álvaro, & Fišer, D. (2022). Beyond Stars – Generalized Topologies for Decoupled Search. Proceedings of the International Conference on Automated Planning and Scheduling, 32(1), 110-118. Retrieved from https://ojs.aaai.org/index.php/ICAPS/article/view/19791