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

Direct link
Improving heuristics through relaxed search - An analysis of TP4 and HSP*a in the 2004 planning competition
Linköping University, The Institute of Technology. Linköping University, Department of Computer and Information Science, KPLAB - Knowledge Processing Lab.
2006 (English)In: The journal of artificial intelligence research, ISSN 1076-9757, Vol. 25, 233-267 p.Article in journal (Refereed) Published
Abstract [en]

The h(m) admissible heuristics for (sequential and temporal) regression planning are defined by a parameterized relaxation of the optimal cost function in the regression search space, where the parameter m offers a trade-off between the accuracy and computational cost of the heuristic. Existing methods for computing the h(m) heuristic require time exponential in m, limiting them to small values (m <= 2). The h(m) heuristic can also be viewed as the optimal cost function in a relaxation of the search space: this paper presents relaxed search, a method for computing this function partially by searching in the relaxed space. The relaxed search method, because it compute h(m) only partially, is computationally cheaper and therefore usable for higher values of m. The (complete) h(2) heuristic is combined with partial hm heuristics , for m = 3, ... computed by relaxed search, resulting in a more accurate heuristic. This use of the relaxed search method to improve on the h(2) heuristic is evaluated by comparing two optimal temporal planners: TP4, which does not use it, and HSP*(a), which uses it but is otherwise identical to TP4. The comparison is made on the domains used in the 2004 International Planning Competition, in which both planners participated. Relaxed search is found to be cost effective in some of these domains, but not all. Analysis reveals a characterization of the domains in which relaxed search can be expected to be cost effective, in terms of two measures on the original and relaxed search spaces. In the domains where relaxed search is cost effective, expanding small states is computationally cheaper than expanding large states and small states tend to have small successor states.

Place, publisher, year, edition, pages
AAAI Press , 2006. Vol. 25, 233-267 p.
National Category
Engineering and Technology
URN: urn:nbn:se:liu:diva-48102DOI: 10.1613/jair.1885OAI: diva2:268998
Available from: 2009-10-11 Created: 2009-10-11 Last updated: 2011-02-23

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Haslum, Patrik
By organisation
The Institute of TechnologyKPLAB - Knowledge Processing Lab
In the same journal
The journal of artificial intelligence research
Engineering and Technology

Search outside of DiVA

GoogleGoogle Scholar

Altmetric score

Total: 104 hits
ReferencesLink to record
Permanent link

Direct link