Beyond Stars – Generalized Topologies for Decoupled Search
2022 (English)In: Proceedings of the Thirty-Second International Conference on Automated Planning and Scheduling, ICAPS 2022 / [ed] Akshat Kumar, Sylvie Thiébaux, Pradeep Varakantham, William Yeoh (eds), AAAI Press, 2022, Vol. 32, p. 110-118Conference paper, Published paper (Refereed)
Abstract [en]
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.
Place, publisher, year, edition, pages
AAAI Press, 2022. Vol. 32, p. 110-118
Series
Proceedings of the International Conference on Automated Planning and Scheduling, ISSN 2334-0835, E-ISSN 2334-0843
Keywords [en]
Artificial Intelligence, automated planning, classical planning, AI planning, state space search, decoupled search, problem decomposition
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:liu:diva-187931DOI: 10.1609/icaps.v32i1.19791Scopus ID: 2-s2.0-85142616963ISBN: 9781577358749 (electronic)OAI: oai:DiVA.org:liu-187931DiVA, id: diva2:1691712
Conference
International Conference on Automated Planning and Scheduling, ICAPS 2022, Singapore (virtual), June 13-24, 2022
Funder
German Research Foundation (DFG), HO 2169/6-22022-08-302022-08-302025-09-18Bibliographically approved