Research map / Learning theory and algorithms / Combinatorial and search optimization
On Computing Makespan-Optimal Solutions for Generalized Sliding-Tile Puzzles
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that makespan-optimal generalized sliding-tile puzzle (GSTP) is NP-complete and gives matching asymptotic makespan lower and upper bounds for all escort counts using Rubik table algorithm and escort-jump analysis.
Problem
Computing makespan-optimal solutions for generalized sliding-tile puzzles with multiple escorts and synchronous multi-tile moves under the corner-following constraint, which arise in warehouse automation and parking garages.
Approach
Models tile motion via escort jumps, derives a Manhattan-distance-based lower bound on makespan showing dependence on escort count, and matches it with upper bounds built by applying Rubik table row/column shuffles realized by careful sliding-tile sub-routines on 2- and 3-row grids under the corner-following constraint.
Key results
- Computing makespan-optimal GSTP solutions is NP-complete, with or without an enclosing grid, and remains NP-complete with floor(|G|^epsilon) escorts.
- Expected makespan lower bound Omega(m1 m2 / k) for k < min(m1,m2) escorts, and Omega(max(m1,m2)) for k >= min(m1,m2), matched by upper bounds such as (81+o(1)) m1 m2 for one escort and (22+o(1)) m1 m2/floor(k/2) for 2<k<min(m1,m2).
- Single-escort feasible GSTP instances on 3 x m grids are solvable in 120m steps; two-escort instances on 2 x m grids in 10m-13 steps.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the proposed algorithm for single-escort instances | GSTP · GSTP, single escort | makespan upper bound: 81m_1 m_2 + 6m_1 + 9m_2 - 3 | Helped |
| Use the proposed algorithm for two-escort instances | GSTP · GSTP, two escorts | makespan upper bound: 18m_1 m_2 - 4m_1 - 5m_2 - 29 | Helped |
| Use the proposed algorithm with an even number of escorts and parallel row/column shuffles | GSTP · GSTP, 2 ≤ k < min(m_1, m_2), k even | makespan upper bound: \frac{44m_1 m_2}{k} + m_1(5 - \frac{24}{k}) + 15m_2 - 29 | Helped |
| Increase the number of escorts across regimes | GSTP · Random start and goal configurations across escort counts | makespan lower bound: exp. $\Omega(\dfrac{m_1 m_2}{k})$; h.p. $\Omega(\max(m_1, m_2))$ | Mixed |
| Apply the proposed construction and algorithmic bounds | GSTP · GSTP across escort counts | asymptotic makespan bound | Helped |
Limitations
- Some proofs are sketched or omitted, and several constants are only sketched in the main text.
- Upper bounds are asymptotic/constant-factor and no empirical evaluation or practical algorithm is presented.
- Lower bound is in expectation over random configurations, and the high-probability bound applies only for k >= min(m1,m2).
Experimental setup
Metrics: makespan asymptotic bounds NP-completeness
Baselines: Prior GSTP upper bounds (single escort O(m1 m2 max(m1,m2)), 2m1+2m2-4 escorts O(
Builds on: Rubik table algorithm 15-puzzle TTFSAT (SAT variant)
Closest papers by meaning
- Symbolic Planning and Multi-Agent Path Finding in Extremely Dense Environments with Unassigned Agents (AAAI 2026 · similarity 0.82)
- Best-First Width Search: Exploration and Exploitation in Classical Planning (AAAI 2017 · similarity 0.81)
- PUZZLES: A Benchmark for Neural Algorithmic Reasoning (NeurIPS 2024 · similarity 0.80)
- Multi-Robot Task Allocation Using Global Games with Negative Feedback: The Colony Maintenance Problem (AAAI 2025 · similarity 0.80)
- Facility Location Games with Optional Preferences: A Revisit (AAAI 2025 · similarity 0.79)
- Convex Markov Games: A New Frontier for Multi-Agent Reinforcement Learning (ICML 2025 · similarity 0.79)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.