USING PROBLEM REDUCTION AND INTROSPECTIVE-BASED SEARCH FOR SOKOBAN

摘要

The Sokoban game is one of the hardest reference problems in planning. In this paper, we present the application of a general framework to this problem, which constitutes a novel approach to the domain. The main principles are to use a decomposition of the problem and to control the hierarchical search by using introspective reasoning. With this approach, we have been able to reach the efficiency of the best solvers with an inferior development effort, which demonstrates the generality of our framework and the interest of the approach. The types of solved problems also seem to be quite different from the other solvers, which indicates an original approach and the possibility of promising combinations.