# Optimally Solving Colored Generalized Sliding-Tile Puzzles: Complexity and Bounds

arXiv: https://arxiv.org/abs/2410.14947 · HTML: https://mlsanity.com/paper/2410.14947/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 31 references that are in the map.
- First posted on arXiv 19 Oct 2024.

## Builds on (most cited first, 11 of 11)

- [Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks](https://mlsanity.com/paper/1906.08291/) (2019)
- [EECBS: A Bounded-Suboptimal Search for Multi-Agent Path Finding](https://mlsanity.com/paper/2010.01367/) (2020)
- [LaCAM: Search-Based Algorithm for Quick Multi-Agent Pathfinding](https://mlsanity.com/paper/2211.13432/) (2022)
- [Optimal Multi-Robot Path Planning on Graphs: Complete Algorithms and Effective Heuristics](https://mlsanity.com/paper/1507.03290/) (2015)
- [Coordinated Motion Planning: Reconfiguring a Swarm of Labeled Robots with Bounded Stretch](https://mlsanity.com/paper/1801.01689/) (2018)
- [Toward Efficient Physical and Algorithmic Design of Automated Garages](https://mlsanity.com/paper/2302.01305/) (2023)
- [Computing Coordinated Motion Plans for Robot Swarms: The CG:SHOP Challenge 2021](https://mlsanity.com/paper/2103.15381/) (2021)
- [Sub-1.5 Time-Optimal Multi-Robot Path Planning on Grids in Polynomial Time](https://mlsanity.com/paper/2201.08976/) (2022)
- [Constant Factor Time Optimal Multi-Robot Routing on High-Dimensional Grids in Mostly Sub-Quadratic Time](https://mlsanity.com/paper/1801.10465/) (2018)
- [On Computing Makespan-Optimal Solutions for Generalized Sliding-Tile Puzzles](https://mlsanity.com/paper/2312.10887/) (2023)
- [Rubik Tables and Object Rearrangement](https://mlsanity.com/paper/2002.04979/) (2020)

## Abstract (arXiv)

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.