Steps Towards The Automatic Creation of Search Heuristics

• Author(s) / Creator(s)

  • Hernadvolgyi, Istvan
  • Holte, Robert

• Technical report TR04-02. The long-term goal of our research is to develop robust methods that use abstraction to create heuristics automatically from a description of a search space. Our research has progressed significantly towards this goal. This paper reviews the current state of the art, and the major open problems remaining to be solved. Pattern databases are the foundation of the approach. The paper describes domain abstraction, which extends the notion of \"pattern\" in a way that permits available memory to be more fully exploited to reduce search time. The paper demonstrates that a certain easily computed approximation to a formula developed by Korf and Reid \cite{korf98} is monotonically related to the actual number of nodes expanded using the pattern database. This involves a large-scale experiment involving all possible domain abstractions for the 8-Puzzle in which the blank tile remains unique. The principal remaining obstacle to automatic heuristic creation is shown to be the difficulty of predicting or controlling the size of a pattern database. This difficulty arises for two reasons, the main one being \"non-surjectivity\": domain abstractions can create abstract spaces in which some states do not have a pre-image. The paper identifies two specific causes of non-surjectivity, related to the space's orbits and blocks, and illustrates others. | TRID-ID TR04-02

• Date created

  2004

• Subjects / Keywords

  • Search heuristics creation

• Type of Item

  Report

• DOI

  https://doi.org/10.7939/R3FJ29G5K

• License

  Attribution 3.0 International