Not Logged In

Using Abstraction for Planning in Sokoban

Full Text: planning.pdf PDF

Heuristic search has been successful for games like Chess and Checkers, but seems to be of limited value in games such as Go and Shogi, and puzzles such as Sokoban. Other techniques are necessary to approach the performance that humans achieve in these hard domains. This papers explores using planning as alternative problem-solving framework for Sokoban. Previous attempts to express Sokoban as a planning application led to poor performance results. Abstract Sokoban is introduced as a new planning formulation of the domain. The approach abstracts a Sokoban problem into rooms and tunnels. This allows for the decomposition of the hard intitial problem into several simpler sub-problems, each of which can be solved effciently. The experimental results show that the abstraction has the potential for an exponential reduction in the size of the search space explored.

Citation

A. Botea, M. Mueller, J. Schaeffer. "Using Abstraction for Planning in Sokoban". Computers and Games, pp 360-375, January 2002.

Keywords: machine learning
Category: In Conference

BibTeX

@incollection{Botea+al:02,
  author = {Adi Botea and Martin Mueller and Jonathan Schaeffer},
  title = {Using Abstraction for Planning in Sokoban},
  Pages = {360-375},
  booktitle = {Computers and Games},
  year = 2002,
}

Last Updated: June 05, 2007
Submitted by Staurt H. Johnson

University of Alberta Logo AICML Logo