Sokoban: Enhancing general single-agent search methods using domain knowledge

Artificial intelligence (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 general search enhancements on pr ogram performance. We show that the current state of the art in Al generall y requires a large research and programming effort to use domain-dependent knowledge to solve even moderately complex problems in such difficult domai ns. The application of domain-specific knowledge to exploit properties of t he search space can result in large reductions in the size of the search tr ee, often several orders of magnitude per search enhancement, This applicat ion-specific knowledge is discovered and applied using application-independ ent search enhancements. Understanding the effect of these enhancements on the search leads to a new taxonomy of search enhancements, and a new framew ork for developing single-agent search applications. This is used to illust rate the large gap between what is portrayed in the literature versus what is needed in practice. (C) 2001 Elsevier Science B.V. All rights reserved.