Single-Agent Search in the Presence of Deadlocks

Andreas Junghanns, Jonathan Schaeffer

Single-agent search is a powerful tool for solving a variety of applications. Most of the application domains used to explore single-agent search techniques have the property that if you start with a solvable state, at no time in the search can you reach a state that is unsolvable. In this paper we address the implications that arise when state transitions can lead to unsolvable (deadlock) states. Deadlock states are partially responsible for the failure of our attempts to solve positions in the game of Sokoban. In this paper, we introduce pattern search, a real-time learning algorithm that identifies the minimal conditions (pattern) necessary for a deadlock, and applies that knowledge to eliminate provably irrelevant parts of the search tree. Identification of deadlock patterns is equivalent to correcting the heuristic lower bound of a position to infinity. Generalizing pattern searches to find arbitrary lower bound increases yields a powerful new search enhancement. In the game of Sokoban, pattern searches result in a 15-fold reduction of the cost of each additional IDA* iteration.

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.