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

Direct link
Upper and Lower 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.
2016 (English)In: ECAI 2016: 22ND EUROPEAN CONFERENCE ON ARTIFICIAL INTELLIGENCE, IOS PRESS , 2016, Vol. 285, 716-724 p.Conference paper (Refereed)
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 have been thoroughly analysed in this respect. We provide a number of upper and lower bound results for both plan satisfiability (PSAT) and length-optimal planning (LOP), with an emphasis on monotone planning (where actions have only positive effects) which is used in, for instance, h(+) and similar heuristics. Let v and a be the number of variables and actions, respectively. We consider both restrictions on the number and polarity of preconditions and effects of actions and the PUBS restrictions in SAS(+). For all such classes, we show that PSAT and LOP is either tractable or cannot be solved in subexponential time 2(o(v)) or time 2(o(a)), unless the so-called Exponential Time Hypothesis (ETH) is false. There is also a sharp transition: monotone LOP can be solved in time 2(o(v)) if a is an element of o(v/log v) but not if a is an element of Omega(v). We also study upper bounds and discuss the trade-off between time and space, providing a polynomial-space algorithm for monotone LOP that beats depth-first search in most cases. This raises the important question how lower bounds are affected by polynomial space restrictions.

Place, publisher, year, edition, pages
IOS PRESS , 2016. Vol. 285, 716-724 p.
Series
, Frontiers in Artificial Intelligence and Applications, ISSN 0922-6389
National Category
Computer Science
Identifiers
URN: urn:nbn:se:liu:diva-132567DOI: 10.3233/978-1-61499-672-9-716ISI: 000385793700084ISBN: 978-1-61499-672-9; 978-1-61499-671-2OAI: oai:DiVA.org:liu-132567DiVA: diva2:1046662
Conference
22nd European Conference on Artificial Intelligence (ECAI)
Available from: 2016-11-14 Created: 2016-11-14 Last updated: 2016-11-14

Open Access in DiVA

No full text

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
Computer Science

Search outside of DiVA

GoogleGoogle Scholar

Altmetric score

Total: 9 hits
ReferencesLink to record
Permanent link

Direct link