The Need for Different Domain-Independent Heuristics

June 1994

The Need for Different Domain-Independent Heuristics

Authors:

Peter Stone, Manuela Veloso, and Jim Blythe

Abstract:

PRODIGY's planning algorithm uses domain-independent search heuristics. In this paper, we support our belief that there is no single search heuristic that performs more efficiently than others for all problems or in all domains. The paper presents three different domain-independent search heuristics of increasing complexity. We run PRODIGY with these heuristics in a series of artificial domains (introduced in (Barrett & Weld 1994)) where in fact one of the heuristics performs more efficiently than the others. However, we introduce an additional simple domain where the apparently worst heuristic outperforms the other two. The results we obtained in our empirical experiments lead to the main conclusion of this paper: planning algorithms need to use different search heuristics in different domains. We conclude the paper by advocating the need to learn the correspondence between particular domain characteristics and specific search heuristics for planning efficiently in complex domains.
@conference{Stone-1994-16076,
author = {Peter Stone And Manuela Veloso And Jim Blythe},
title = {The Need for Different Domain-Independent Heuristics},
booktitle = {Proceedings of 2nd International Conference on Artificial Intelligence Planning Systems (AIPS '94)},
year = {1994},
month = {June},
pages = {164 - 169},
}
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.