Agent motion planning with pull and push moves

• Tadeu Zubaran UFRGS
• Marcus Ritt UFRGS

Resumo

Agent motion planning is a common task in artificial intelligence. One of the simplest scenarios considers the delivery of boxes to storage locations on a regular grid with obstacles. When the agent can only push boxes, we obtain the well-known, PSPACE-hard Sokoban puzzle [Culberson 1997]. In this paper we propose an exact solver for the scenario called Pukoban where the agent can push and pull boxes. The solver is, to the best of our knowledge, the first one proposed for Pukoban. It is based on the A* search algorithm with several problem-specific improvements. We evaluate its efficiency on 100 instances from the literature. Our algorithm is able to solve 30 instances exactly.

Referências

Clercq, D. D. Pukoban. [link].

Culberson, J. C. (1997). Sokoban is PSPACE-complete. Technical report, University of Alberta, 97-02.

Demaine, E. D., Demaine, M. L., Hoffmann, M., and O’Rourke, J. (2003). Pushing blocks is hard. Computational Geometry, 26:21–36.

Dor, D. and Zwick, U. (1999). Sokoban and other motion planning problems. Computational Geometry, 13:215–228.

Hart, P. E., Nilsson, N. J., and Raphael, B. (1968). A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, 4(2):100–107.

Hüffner, F., Edelkamp, S., Fernau, H., and Niedermeier, R. (2001). Finding optimal solutions to Atomix. In Advances in artifical intelligence, volume LNCS 2174, pages 229–243.

Jurkovski, B. (2010). Pukoban solver. Available: [link].

Korf, R. E. (1985). Depth-first iterative-deepening: An optimal admissible tree search. Artificial Intelligence, 27:97–109.

Kuhn, H. W. (1955). The hungarian method for the assignment problem. Naval Research Logistic Quarterly, 2:83–97.

Schaeffer, J. and Junghanns, A. (2000). Sokoban: Enhanceing general single-agent search methods using domain knowledge. Artificial Intelligence, 129(1–2):219–251.