Solving Moving-Blocks Problems

• André G. Pereira UFRGS
• Luciana S. Buriol UFRGS
• Marcus Ritt UFRGS

DOI: https://doi.org/10.5753/ctd.2017.3464

Resumo

Moving-blocks problems are extremely hard to solve and a representative abstraction of many applications. Despite their importance, the known computational complexity results are limited to few versions of these problems. In addition, there are no effective methods to optimally solve them. We address both of these issues. This thesis proves the PSPACE-completeness of many versions of moving-blocks problems. Moreover, we propose new methods to optimally solve these problems based on heuristic search with admissible heuristic functions and tie-breaking strategies. Our methods advance the state of the art, create new lines of research and improve the results of applications.

Referências

Asai, M. and Fukunaga, A. (2017). Tie-Breaking Strategies for Cost-Optimal Best First Search. Journal of Artificial Intelligence Research, 58:67–121.

Corrêa, A. B., Pereira, A. G., and Ritt, M. (2016). Improved airport ground traffic control with domain-dependent heuristics. In Brazilian Conference on Intelligent Systems, pages 73–78.

Culberson, J. (1999). Sokoban is PSPACE-complete. In International Conference on Fun with Algorithms, pages 65–76.

Demaine, E. D., Hearn, R. A., and Hoffmann, M. (2002). Push-2-F is PSPACE-Complete. In Canadian Conference on Computational Geometry, pages 31–35.

Demaine, E. D. and Hoffmann, M. (2001). Pushing blocks is NP-complete for noncrossing solution paths. In Canadian Conference on Computational Geometry.

Demaine, E. D., Hoffmann, M., and Holzer, M. (2004). PushPush-k is PSPACE-Complete. In International Conference on FUN with Algorithms, pages 159–170.

Hearn, R. and Demaine, E. D. (2005). PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation. Theoretical Computer Science, 343(1-2):72–96.

Hoffmann, J., Edelkamp, S., Thiébaux, S., Englert, R., dos Santos Liporace, F., and Trug, S. (2006). Engineering Benchmarks for Planning: The Domains Used in the Deterministic Part of IPC-4. Journal of Artificial Intelligence Research, 26(1):453–541.

Long, D. and Fox, M. (2003). The 3rd International Planning Competition: Results and Analysis. Journal of Artificial Intelligence Research, 20:1–59.

McDermott, D. M. (2000). The 1998 AI planning systems competition. AI Magazine, 21(2).

O’Rourke, J. (1999). PushPush is NP-hard in 3D. Technical report, Smith College.

Pereira, A. G., Holte, R., Schaeffer, J., Buriol, L. S., and Ritt, M. (2016a). Improved Heuristic and Tie-Breaking for Optimally Solving Sokoban. In International Joint Conference on Artificial Intelligence.

Pereira, A. G., Ritt, M., and Buriol, L. S. (2013). Finding Optimal Solutions to Sokoban Using Instance Dependent Pattern Databases. In Symposium on Combinatorial Search.

Pereira, A. G., Ritt, M., and Buriol, L. S. (2014a). Solving motion planning problems. In International Joint Conference on Artificial Intelligence School - DC.

Pereira, A. G., Ritt, M., and Buriol, L. S. (2014b). Solving Sokoban Optimally using Pattern Databases for Deadlock Detection. In Encontro Nacional de Inteligência Artificial.

Pereira, A. G., Ritt, M., and Buriol, L. S. (2015). Optimal Sokoban Solving using Pattern Databases with Specific Domain Knowledge. Artificial Intelligence, 227:52 – 70.

Pereira, A. G., Ritt, M., and Buriol, L. S. (2016b). Pull and PushPull are PSPACE-complete. Theoretical Computer Science, 628:50 – 61.

Ritt, M. (2010). Motion planning with pull moves. CoRR, abs/1008.2952:1–9.