A Tabled Prolog Program for Solving Sokoban

• Autorzy: Zhou N.-F. , Dovier A.
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

computer program language; Prolog; problem solving; mathematical optimization; generalization; dynamic programming

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2013
• Tom: Vol. 124, nr 4
• Strony: 561--575
• Opis fizyczny: Bibliogr. 23 poz., wykr.

Twórcy

autor

Zhou N.-F.

• Department of Computer and Information Science, CUNY Brooklyn College & Graduate Center, USA

autor

Dovier A.

• Dipartimento di Matematica e Informatica, Università di Udine, Udine, Italy

Bibliografia

• [1] Marcello Balduccini. Splitting a CR-prolog program. In LPNMR 2009, LNCS 5753, pages 17-29, 2009.
• [2] R. Bartak and D. Toropila. Reformulating constraint models for classical planning. In David Wilson and H. Chad Lane, editors, FLAIRS’08: Twenty-First International Florida Artificial Intelligence Research Society Conference, pages 525-530. AAAI Press, 2008.
• [3] Adi Botea, Martin Muller, and Jonathan Schaeffer. Using abstraction for planning in sokoban. In Computers and Games, pages 360-375, 2002.
• [4] Francesco Calimeri, Giovambattista Ianni, Francesco Ricca, Mario Alviano, Annamaria Bria, Gelsomina Catalano, Susanna Cozza, Wolfgang Faber, Onofrio Febbraro, Nicola Leone, Marco Manna, Alessandra Martello, Claudio Panetta, Simona Perri, Kristian Reale, Maria Carmela Santoro, Marco Sirianni, Giorgio Terracina, and Pierfrancesco Veltri. The third answer set programming competition. In LPNMR 2011, LNCS 6645, pages 388-403, 2011. See also: https://www.mat.unical.it/aspcomp2011.
• [5] Marc Denecker, Joost Vennekens, Stephen Bond, Martin Gebser, and Miroslaw Truszczynski. The second answer set programming competition. In LPNMR 2009, LNCS 5753, pages 637-654, 2009.
• [6] Dorit Dor and Uri Zwick. Sokoban and other motion planning problems. Computational Geometry: Theory and Applications, 13:215-228, 1995.
• [7] Agostino Dovier, Andrea Formisano, and Enrico Pontelli. An empirical study of constraint logic programming and answer set programming solutions of combinatorial problems. J. Exp. Theor. Artif. Intell. 21(2):79- 121, 2009.
• [8] Agostino Dovier, Andrea Formisano, and Enrico Pontelli. Multivalued action languages with constraints in CLP(FD). Theory and Practice of Logic Programming, 10(2):167-235, 2010.
• [9] Agostino Dovier, Andrea Formisano, and Enrico Pontelli. An investigation of Multi-Agent Planning in CLP. Fundamenta Informaticae, 105(1-2):79-103, 2010.
• [10] Agostino Dovier, Andrea Formisano, and Enrico Pontelli. Perspectives on Logic-based Approaches for Reasoning About Actions and Change. In Logic Programming, Knowledge Representation, and Nonmonotonic Reasoning, Essays Dedicated to Michael Gelfond on the Occasion of His 65th Birthday, LNCS 6565, pages 259-279. Springer, 2011.
• [11] Juliana Freire, Terrance Swift, and David Scott Warren. Beyond depth-first: Improving tabled logic programs through alternative scheduling strategies. Journal of Functional and Logic Programming, (3), 1998.
• [12] Martin Gebser, Roland Kaminski, Benjamin Kaufmann, Max Ostrowski, Torsten Schaub, and Sven Thiele. Engineering an incremental asp solver. In ICLP, pages 190-205, 2008.
• [13] Michael Gelfond and Vladimir Lifschitz. The stable model semantics for logic programming. In Proceedings of the Joint International Conference and Symposium on Logic Programming (JICSLP), pages 1070-1080, 1988.
• [14] Michael Gelfond and Vladimir Lifschitz. Action languages. Electron. Trans. Artif. Intell., 2:193-210, 1998.
• [15] Hai-Feng Guo and Gopal Gupta. Simplifying dynamic programming via mode-directed tabling. Softw., Pract. Exper., 38(1):75-94, 2008.
• [16] Patrik Haslum, Adi Botea, Malte Helmert, Blai Bonet, and Sven Koenig. Domain-independent construction of pattern database heuristics for cost-optimal planning. In AAAI, pages 1007-1012, 2007.
• [17] International Planning Competition http://ipc.informatik.uni-freiburg.de/. The Sokoban domain can be found in http://ipc.informatik.uni-freiburg.de/Domains.
• [18] Andreas Junghanns and Jonathan Schaeffer. Sokoban: Enhancing general single-agent search methods using domain knowledge. Artif. Intell., 129(1-2):219-251, 2001.
• [19] Fangzhen Lin and Yuting Zhao. ASSAT: Computing answer sets of a logic program by SAT solvers. Artificial Intelligence, 157(1-2):115-137, 2004.
• [20] David Scott Warren. Memoing for logic programs. Comm. of the ACM, Special Section on Logic Programming, 35:93-111, 1992.
• [21] Neng-Fa Zhou. The language features and architecture of B-Prolog. Theory and Practice of Logic Programming 12(1-2):189-218, 2012.
• [22] Neng-Fa Zhou, Yoshitaka Kameya, and Taisuke Sato. Mode-directed tabling for dynamic programming, machine learning, and constraint solving. In ICTAI, pages 213-218, 2010.
• [23] Neng-Fa Zhou, Taisuke Sato, and Yi-Dong Shen. Linear tabling strategies and optimizations. Theory and Practice of Logic Programming, 8(1):81-109, 2008.