Agent motion planning with pull and push moves - Zubaran, Tadeu; Ritt, Marcus (Anais do Encontro Nacional de Inteligência Artificial e Computacional (ENIAC), 2011)
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.