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

Direct link
Cite
Citation style
  • apa
  • harvard1
  • 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
Time and Space Bounds for Planning
Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, Faculty of Science & Engineering.
Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, Faculty of Science & Engineering.
2017 (English)In: The journal of artificial intelligence research, ISSN 1076-9757, E-ISSN 1943-5037, Vol. 60, p. 595-638Article in journal (Refereed) Published
Abstract [en]

There is an extensive literature on the complexity of planning, but explicit bounds on time and space complexity are very rare. On the other hand, problems like the constraint satisfaction problem (CSP) have been thoroughly analysed in this respect. We provide a number of upper- and lower-bound results (the latter based on various complexity-theoretic assumptions such as the Exponential Time Hypothesis) for both satisficing and optimal planning. We show that many classes of planning instances exhibit a dichotomy: either they can be solved in polynomial time or they cannot be solved in subexponential time and thus require O (2(cn)) time for some c amp;gt; 0. In many cases, we can even prove closely matching upper and lower bounds; for every epsilon amp;gt; 0, the problem can be solved in time O (2((1+epsilon)n)) but not in time O (2((1-epsilon)n)). Our results also indicate, analogously to CSPs, the existence of sharp phase transitions. We finally study and discuss the trade-off between time and space. In particular, we show that depth-first search may sometimes be a viable option for planning under severe space constraints.

Place, publisher, year, edition, pages
AI ACCESS FOUNDATION , 2017. Vol. 60, p. 595-638
National Category
Discrete Mathematics
Identifiers
URN: urn:nbn:se:liu:diva-145837DOI: 10.1613/jair.5535ISI: 000425309600002OAI: oai:DiVA.org:liu-145837DiVA, id: diva2:1192151
Note

Funding Agencies|Swedish Research Council (VR) [621-2014-4086]

Available from: 2018-03-21 Created: 2018-03-21 Last updated: 2018-03-21

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full text

Search in DiVA

By author/editor
Bäckström, ChristerJonsson, Peter
By organisation
Software and SystemsFaculty of Science & Engineering
In the same journal
The journal of artificial intelligence research
Discrete Mathematics

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

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

Direct link
Cite
Citation style
  • apa
  • harvard1
  • 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