Beyond Forks: Finding and Ranking Star Factorings for Decoupled Search

Beyond Forks: Finding and Ranking Star Factorings for Decoupled Search

Daniel Gnad, Valerie Poser, Jörg Hoffmann

Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence
Main track. Pages 4310-4316. https://doi.org/10.24963/ijcai.2017/602

Star-topology decoupling is a recent search reduction method for forward state space search. The idea basically is to automatically identify a star factoring, then search only over the center component in the star, avoiding interleavings across leaf components. The framework can handle complex star topologies, yet prior work on decoupled search considered only factoring strategies identifying fork and inverted-fork topologies. Here, we introduce factoring strategies able to detect general star topologies, thereby extending the reach of decoupled search to new factorings and to new domains, sometimes resulting in significant performance improvements. Furthermore, we introduce a predictive portfolio method that reliably selects the most suitable factoring for a given planning task, leading to superior overall performance.
Keywords:
Planning and Scheduling: Planning Algorithms
Combinatorial & Heuristic Search: Heuristic Search
Planning and Scheduling: Search in Planning and Scheduling
Planning and Scheduling: Planning and Scheduling