# On Computing Makespan-Optimal Solutions for Generalized Sliding-Tile Puzzles

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 36 references that are in the map.
- First posted on arXiv 18 Dec 2023.

## 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)
- [Priority Inheritance with Backtracking for Iterative Multi-agent Path Finding](https://mlsanity.com/paper/1901.11282/) (2019)
- [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)
- [A simple proof that the (n2-1)-puzzle is hard](https://mlsanity.com/paper/1707.03146/) (2017)
- [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)
- [A Linear Time Algorithm for the Feasibility of Pebble Motion on Graphs](https://mlsanity.com/paper/1301.2342/) (2013)

## Built on by (most cited first, 2 of 2)

- [Symbolic Planning and Multi-Agent Path Finding in Extremely Dense Environments with Unassigned Agents](https://mlsanity.com/paper/2509.01022/) (2025)
- [Optimally Solving Colored Generalized Sliding-Tile Puzzles: Complexity and Bounds](https://mlsanity.com/paper/2410.14947/) (2024)

## Abstract (arXiv)

In the 15-puzzle game, 15 labeled square tiles are reconfigured on a 4× 4 board through an escort, wherein each (time) step, a single tile neighboring it may slide into it, leaving the space previously occupied by the tile as the new escort. We study a generalized sliding-tile puzzle (GSTP) in which (1) there are 1+ escorts and (2) multiple tiles can move synchronously in a single time step. Compared with popular discrete multi-agent/robot motion models, GSTP provides a more accurate model for a broad array of high-utility applications, including warehouse automation and autonomous garage parking, but is less studied due to the more involved tile interactions. In this work, we analyze optimal GSTP solution structures, establishing that computing makespan-optimal solutions for GSTP is NP-complete and developing polynomial time algorithms yielding makespans approximating the minimum with expected/high probability constant factors, assuming randomized start and goal configurations.