Solving Moving-Blocks Problems

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

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.