Analysing Approximability and Heuristics in Planning Using the Exponential-Time Hypothesis
2016 (English)In: ECAI 2016: 22ND EUROPEAN CONFERENCE ON ARTIFICIAL INTELLIGENCE, IOS Press, 2016, Vol. 285, 184-192 p.Conference paper (Refereed)
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.
Frontiers in Artificial Intelligence and Applications, ISSN 0922-6389, E-ISSN 1879-8314 ; 285
IdentifiersURN: urn:nbn:se:liu:diva-132566DOI: 10.3233/978-1-61499-672-9-184ISI: 000385793700023ISBN: 978-1-61499-671-2 (print)ISBN: 978-1-61499-672-9 (electronic)OAI: oai:DiVA.org:liu-132566DiVA: diva2:1046664
22nd European Conference on Artificial Intelligence (ECAI)