liu.seSearch for publications in DiVA
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Beyond Stars – Generalized Topologies for Decoupled Search
Linköping University, Department of Computer and Information Science, Artificial Intelligence and Integrated Computer Systems. Linköping University, Faculty of Science & Engineering. Saarland University, Saarland Informatics Campus, Saarbrücken, Germany . (RLPLab)ORCID iD: 0000-0001-7434-2669
Aalborg University, Aalborg Øst, Denmark.
Saarland University, Saarland Informatics Campus, Saarbrücken, Germany; Czech Technical University in Prague, Faculty of Electrical Engineering, Czech Republic.
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-2Available from: 2022-08-30 Created: 2022-08-30 Last updated: 2025-09-18Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Authority records

Gnad, Daniel

Search in DiVA

By author/editor
Gnad, Daniel
By organisation
Artificial Intelligence and Integrated Computer SystemsFaculty of Science & Engineering
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 362 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf