A Tabled Prolog Program for Solving Sokoban

Issue title: Special Issue on the Italian Conference on Computational Logic: CILC 2011

Article type: Research Article

Authors: Zhou, Neng-Fa | Dovier, Agostino

Affiliations: Department of Computer and Information Science, CUNY Brooklyn College & Graduate Center, USA. [email protected] | Dipartimento di Matematica e Informatica, Università di Udine, Udine, Italy. [email protected]

Note: [] Address for correspondence: Univ. of Udine, DIMI, Via delle Scienze 206, 33100 Udine, Italy

Abstract: This paper presents our program in B-Prolog submitted to the third ASP solver competition for the Sokoban problem. This program, based on dynamic programming, treats Sokoban as a generalized shortest path problem. It divides a problem into independent subproblems and uses mode-directed tabling to store subproblems and their answers. This program is very simple but quite efficient. Without use of any sophisticated domain knowledge, it easily solves 14 of the 15 instances used in the competition. We show that the approach can be easily applied to other optimization planning problems.

DOI: 10.3233/FI-2013-849

Journal: Fundamenta Informaticae, vol. 124, no. 4, pp. 561-575, 2013