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
Planning over Integers: Compilations and Undecidability
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
University of Basel, Switzerland.ORCID iD: 0009-0008-8462-350X
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
Bar-Ilan University, Israel.
2023 (English)In: Proceedings of the Thirty-Third International Conference on Automated Planning and Scheduling / [ed] Sven Koenig; Roni Stern; Mauro Vallati, Cambridge, MA: AAAI Press, 2023, Vol. 33, p. 148-152Conference paper, Published paper (Refereed)
Abstract [en]

Restricted Tasks (RT) are a special case of numeric planning characterized by numeric conditions that involve one numeric variable per formula and numeric effects that allow only the addition of constants. Despite this, RTs form an expressive class whose planning problem is undecidable. The restricted nature of RTs often makes problem modeling awkward and unnecessarily complicated. We show that this can be alleviated by compiling mathematical operations that are not natively supported into RTs using macro-like action sequences. With that, we can encode many features found in general numeric planning such as constant multiplication, addition of linear formulas, and integer division and residue. We demonstrate how our compilations can be used to capture challenging mathematical problems such as the (in)famous Collatz conjecture. Our approach additionally gives a simple undecidability proof for RTs, and the proof shows that the number of variables needed to construct an undecidable class of RTs is surprisingly low: two numeric and one propositional variable.

Place, publisher, year, edition, pages
Cambridge, MA: AAAI Press, 2023. Vol. 33, p. 148-152
Series
Proceedings of the International Conference on Automated Planning and Scheduling, ISSN 2334-0835, E-ISSN 2334-0843
Keywords [en]
Theoretical foundations of planning and scheduling; Planning and scheduling with continuous state and action spaces
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:liu:diva-198698DOI: 10.1609/icaps.v33i1.27189ISBN: 1-57735-881-3 (print)ISBN: 978-1-57735-881-7 (print)OAI: oai:DiVA.org:liu-198698DiVA, id: diva2:1806680
Conference
Thirty-Third International Conference on Automated Planning and Scheduling (ICAPS 2023)
Projects
WASPAvailable from: 2023-10-23 Created: 2023-10-23 Last updated: 2025-11-13

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full texthttps://ojs.aaai.org/index.php/ICAPS/article/view/27189/26962

Authority records

Gnad, DanielJonsson, Peter

Search in DiVA

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

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

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