Heuristic Search, Memory-Based Heuristics and Their Applications
Papers from the AAAI Workshop
Ariel Felner, Robert C. Holte, and Hector Geffner, Cochairs
Heuristic search is a well-established, fundamental field of research in artificial intelligence. Many hard problems in Artificial Intelligence can be modeled as pathfinding in a state-space graph. An intelligent search will be guided by heuristics so as to solve problems quickly.
In the past decade we have seen a large increase in the size of computer memories and disk storage. This has led to significant advances in heuristic search, with many new methods being introduced to better utilize the large memory and disk storage. Foremost among these are methods related to Pattern Databases, which are large lookup tables stored in memory that contain heuristic estimates based on exact solutions to subproblems of the original problem. Other methods were introduced to conduct search using disk space as a fast on-line working memory. This significantly increases the amount of available memory for the different tables and queues maintained by search algorithms and therefore larger problems can now be solved. All these new techniques greatly advance the strength of heuristic search and many problems can be solved orders of magnitude faster than before.
Traditionally, heuristic search and pattern databases have been used to solve combinatorial puzzles. Recently we have seen a large expansion of their use, with applications in other fields of artificial intelligence and computer science such as planning, model checking, dynamic programming and weighted logical inference.
The aim of this workshop is to discuss new achievements in heuristic search, their mutual influence, and their applicability to a large spectrum of problems and areas of artificial intelligence and computer science.