Pull and PushPull are PSPACE-complete. (English) Zbl 1338.68088
Summary: We prove PSPACE-completeness of a broad class of moving-blocks problems similar to the well-known puzzle Sokoban. Several computational complexity results are known for moving-blocks problems. However, most of the literature is focused on problems with push moves and the complexity of many of them are still open. In this article, we study the computational complexity of moving-blocks problems with pull moves and problems with push and pull moves. Our reductions are from Nondeterministic Constraint Logic. We improve the known NP-hardness results of Pull problems to PSPACE-completeness results. We also were able to show that the whole class of PushPull problems is PSPACE-complete.
MSC:
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
| 68T40 | Artificial intelligence for robotics |
Keywords:
moving-blocks problems; PSPACE-completeness; Sokoban; nondeterministic constraint logic; motion planningReferences:
| [1] | Sharir, M., Algorithmic motion planning, (Goodman, J. E.; O’Rourke, J., Handbook of Discrete and Computational Geometry (1997), CRC Press, Inc.), 733-754 · Zbl 0925.93625 |
| [2] | Dor, D.; Zwick, U., SOKOBAN and other motion planning problems, Comput. Geom., 13, 4, 215-228 (1999) · Zbl 0948.68205 |
| [3] | Everett, H. R.; Gage, D. W., From laboratory to warehouse: security robots meet the real world, Int. J. Robot. Res., 18, 7, 760-768 (1999) |
| [4] | Junghanns, A.; Schaeffer, J., Sokoban: enhancing general single-agent search methods using domain knowledge, Artificial Intelligence, 129, 1-2, 219-251 (2001) · Zbl 0971.68151 |
| [5] | Pereira, A. G.; Ritt, M.; Buriol, L. S., Optimal Sokoban solving using pattern databases with specific domain knowledge, Artificial Intelligence, 227, 52-70 (2015) · Zbl 1346.68180 |
| [6] | Demaine, E.; Demaine, M.; O’Rourke, J., PushPush and Push-1 are NP-hard in 2D, (Canadian Conference on Computational Geometry (2000)), 211-219 |
| [7] | Holzer, M.; Schwoon, S., Assembling molecules in ATOMIX is hard, Theoret. Comput. Sci., 313, 3, 447-462 (2004), special issue on Algorithmic Combinatorial Game Theory · Zbl 1070.68069 |
| [8] | Hearn, R.; Demaine, E. D., PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation, Theoret. Comput. Sci., 343, 1-2, 72-96 (2005) · Zbl 1079.68040 |
| [9] | Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), Freeman · Zbl 0411.68039 |
| [10] | Culberson, J., Sokoban is PSPACE-complete, (International Conference on Fun with Algorithms (1999)), 65-76 |
| [11] | Demaine, E. D.; Hearn, R. A.; Hoffmann, M., Push-2-F is PSPACE-complete, (Canadian Conference on Computational Geometry (2002)), 31-35 |
| [12] | Demaine, E. D.; Demaine, M. L.; Hoffmann, M.; O’Rourke, J., Pushing blocks is hard, Comput. Geom., 26, 21-36 (2003) · Zbl 1041.65021 |
| [13] | Demaine, E. D.; Hoffmann, M.; Holzer, M., PushPush-k is PSPACE-complete, (International Conference on FUN with Algorithms (2004)), 159-170 |
| [14] | Ritt, M., Motion planning with pull moves (2010), pp. 1-9 |
| [15] | Demaine, E. D.; Hoffmann, M., Pushing blocks is NP-complete for noncrossing solution paths, (Canadian Conference on Computational Geometry (2001)), 65-68 |
| [16] | O’Rourke, J.; the Smith Problem Solving Group, PushPush is NP-hard in 3D (1999), Smith College, Tech. rep. |
| [17] | Savitch, J. W., Relationships between nondeterministic and deterministic tape complexities, J. Comput. System Sci., 4, 2, 177-192 (1970) · Zbl 0188.33502 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
