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

Direct link
Analysing Approximability and Heuristics in Planning Using the Exponential-Time Hypothesis
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.
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, 184-192 p.Conference paper (Refereed)
Abstract [en]

Cost-optimal planning has become a very well-studied topic within planning. Needless to say, cost-optimal planning has proven to be computationally hard both theoretically and in practice. Since cost-optimal planning is an optimisation problem, it is natural to analyse it from an approximation point of view. Even though such studies may be valuable in themselves, additional motivation is provided by the fact that there is a very close link between approximability and the performance of heuristics used in heuristic search. The aim of this paper is to analyse approximability (and indirectly the performance of heuristics) with respect to lower time bounds. That is, we are not content by merely classifying problems into complexity classes - we also study their time complexity. This is achieved by replacing standard complexity-theoretic assumptions (such as P not equal NP) with the exponential time hypothesis (ETH). This enables us to analyse, for instance, the performance of the h(+) heuristic and obtain general trade-off results that correlate approximability bounds with bounds on time complexity.

Place, publisher, year, edition, pages
IOS PRESS , 2016. Vol. 285, 184-192 p.
Series
, Frontiers in Artificial Intelligence and Applications, ISSN 0922-6389
National Category
Computer Science
Identifiers
URN: urn:nbn:se:liu:diva-132566DOI: 10.3233/978-1-61499-672-9-184ISI: 000385793700023ISBN: 978-1-61499-672-9; 978-1-61499-671-2OAI: oai:DiVA.org:liu-132566DiVA: diva2:1046664
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
Aghighi, MeysamBäckström, ChristerJonsson, PeterStåhlberg, Simon
By organisation
Software and SystemsFaculty of Science & Engineering
Computer Science

Search outside of DiVA

GoogleGoogle Scholar

Altmetric score

Total: 18 hits
ReferencesLink to record
Permanent link

Direct link