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
Structurally Restricted Fragments of Numeric Planning – a Complexity Analysis
Bar-Ilan University, Israel.
Linköping University, Department of Computer and Information Science, Artificial Intelligence and Integrated Computer Systems. Linköping University, Faculty of Science & Engineering.ORCID iD: 0000-0001-7434-2669
Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, Faculty of Science & Engineering.ORCID iD: 0000-0002-5288-3330
2023 (English)In: THIRTY-SEVENTH AAAI CONFERENCE ON ARTIFICIAL INTELLIGENCE, VOL 37 NO 10, ASSOC ADVANCEMENT ARTIFICIAL INTELLIGENCE , 2023, Vol. 37, p. 12112-12119Conference paper, Published paper (Refereed)
Abstract [en]

Numeric planning is known to be undecidable even under severe restrictions. Prior work has investigated the decidability boundaries by restricting the expressiveness of the planning formalism in terms of the numeric functions allowed in conditions and effects. We study a well-known restricted form of Hoffmann's simple numeric planning, which is undecidable. We analyze the complexity by imposing restrictions on the causal structure, exploiting a novel method for bounding variable domain sizes. First, we show that plan existence for tasks where all numeric variables are root nodes in the causal graph is in PSPACE. Second, we show that for tasks with only numeric leaf variables the problem is decidable, and that it is in PSPACE if the propositional state space has a fixed size. Our work lays a strong foundation for future investigations of structurally more complex tasks. From a practical perspective, our method allows to employ heuristics and methods that are geared towards finite variable domains (such as pattern database heuristics or decoupled search) to solve non-trivial families of numeric planning problems.

Place, publisher, year, edition, pages
ASSOC ADVANCEMENT ARTIFICIAL INTELLIGENCE , 2023. Vol. 37, p. 12112-12119
Series
AAAI Conference on Artificial Intelligence, ISSN 2159-5399
Keywords [en]
PRS: Mixed Discrete/Continuous Planning, PRS: Deterministic Planning
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:liu:diva-198694DOI: 10.1609/aaai.v37i10.26428ISI: 001243749200068OAI: oai:DiVA.org:liu-198694DiVA, id: diva2:1806608
Conference
37th AAAI Conference on Artificial Intelligence (AAAI) / 35th Conference on Innovative Applications of Artificial Intelligence / 13th Symposium on Educational Advances in Artificial Intelligence, Washington, DC, FEB 07-14, 2023.
Funder
Wallenberg AI, Autonomous Systems and Software Program (WASP)Swedish Research Council, 2021-04371Available from: 2023-10-23 Created: 2023-10-23 Last updated: 2024-09-06

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full text

Authority records

Gnad, DanielJonsson, Peter

Search in DiVA

By author/editor
Gnad, DanielJonsson, Peter
By organisation
Artificial Intelligence and Integrated Computer SystemsFaculty of Science & EngineeringSoftware and Systems
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 119 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