Domain-Dependent Single-Agent Search Enhancements

Abstract

AI research has developed an extensive collection of methods to solve state-space problems. Using the challenging domain of Sokoban, this paper studies the effect of search enhancements on program performance. We show that the current state of the art in AI generally requires a large programming and research effort into domain-dependent methods to solve even moderately complex problems in such difficult domains. The application of domain-specific knowledge to exploit properties of the search space can result in large reductions in the size of the search tree, often several orders of magnitude per search enhancement. Understanding the effect of these enhancements on the search leads to a new classification of search enhancements, and a new framework for developing single-agent search applications. This is used to illustrate the large gap between what is portrayed in the literature versus what is needed in practice.