Agent motion planning with pull and push moves

Tadeu ZubaranMarcus Ritt

Agent motion planning is a common task in artificial intelligence. One of the simplest scenarios considers the delivery of boxes to storage loca- tions 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 sev- eral problem-specific improvements. We evaluate its efficiency on 100 instances from the literature. Our algorithm is able to solve 30 instances exactly.

Caso o link acima esteja inválido, faça uma busca pelo texto completo na Web: Buscar na Web

Biblioteca Digital Brasileira de Computação - Contato:
     Mantida por: