Abstract

Abstract: Heuristic search-based planners, such as HSP 2.0, solve STRIPS-style planning problems efficiently but spend about eighty percent of their planning time on calculating the heuristic values. In this paper, we systematically evaluate alternative methods for calculating the heuristic values for HSP 2.0 and demonstrate that the resulting planning times differ substantially. HSP 2.0 calculates each heuristic value by solving a relaxed planning problem with a dynamic programming method similar to value iteration. We identify two different approaches for speeding up the calculation of heuristic values, namely to order the value updates and to reuse information from the calculation of previous heuristic values. We then show how these two approaches can be combined, resulting in our PINCH method. PINCH outperforms both of the other approaches individually as well as the methods used by HSP 1.0 and HSP 2.0 for most of the large planning problems tested. In fact, it speeds up the planning time of HSP 2.0 by up to eighty percent in several domains and, in general, the amount of savings grows with the size of the domains, allowing HSP 2.0 to solve larger planning problems than was possible before in the same amount of time and without changing its overall operation.

Download the paper in pdf.

Download the paper in gzipped postscript (large download time).

Many publishers do not want authors to make their papers available electronically after the papers have been published. Please use the electronic versions provided here only if hardcopies are not yet available. If you have comments on any of these papers, please send me an email! Also, please send me your papers if we have common interests.

This page was automatically created by a bibliography maintenance system that was developed as part of an undergraduate research project, advised by Sven Koenig.