Optimally Solving Colored Generalized Sliding-Tile Puzzles: Complexity and Bounds
This work addresses complexity and bounds for a generalized puzzle model relevant to multi-robot systems like warehouses, but it is incremental as it builds on prior GSTP studies.
The paper tackles the computational complexity and solution bounds of the Colored Generalized Sliding-Tile Puzzle (CGSP), a model for multi-robot applications, establishing that lower and upper bounds differ by at most a logarithmic factor.
The Generalized Sliding-Tile Puzzle (GSTP), allowing many square tiles on a board to move in parallel while enforcing natural geometric collision constraints on the movement of neighboring tiles, provide a high-fidelity mathematical model for many high-utility existing and future multi-robot applications, e.g., at mobile robot-based warehouses or autonomous garages. Motivated by practical relevance, this work examines a further generalization of GSTP called the Colored Generalized Sliding-Tile Puzzle (CGSP), where tiles can now assume varying degrees of distinguishability, a common occurrence in the aforementioned applications. Our study establishes the computational complexity of CGSP and its key sub-problems under a broad spectrum of possible conditions and characterizes solution makespan lower and upper bounds that differ by at most a logarithmic factor. These results are further extended to higher-dimensional versions of the puzzle game.