Abstract

We present a novel admissible pattern database heuristic (D) and tie-breaking rule (L) for Sokoban, allowing us to increase the number of optimally solved standard Sokoban instances from 20 to 28 and the number of proved optimal solutions from 25 to 32 compared to previous methods. The previously best heuristic for Sokoban (I) used the idea of an intermediate goal state to enable the effective use of pattern database heuristics in transportation domains, where the mapping of movable objects to goal locations is not fixed beforehand. We extend this idea to allow the use of multiple intermediate goal states and show that heuristic I is no longer effective. We solve this problem and show that our heuristic D is effective in this situation. Sokoban is a well-known single-agent search domain characterized by a large branching factor, long solution lengths, and the presence of unsolvable states. Given the exponential growth in the complexity of standard Sokoban instances, the increase in the number of optimally solved instances represents a major advance in our understanding of how to search in extremely large search spaces.