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

Marcus Gozon, Jingjin YuAAAI 2024 · DOI

TL;DR

This paper tackles the challenge of finding the fastest possible solutions (makespan-optimal) for a generalized sliding-tile puzzle (GSTP), which models complex multi-robot coordination tasks. The authors prove that finding these optimal solutions is computationally hard (NP-complete) and then develop algorithms that provide near-optimal solutions with provable bounds, effectively closing the gap between theoretical limits and practical performance.

What Problem Does This Paper Address?

The classic 15-puzzle, where tiles slide to achieve a goal configuration, is a familiar problem. However, real-world applications like warehouse automation and autonomous parking garages involve more complex scenarios. This paper introduces the Generalized Sliding-Tile Puzzle (GSTP) to model these scenarios. GSTP features:

  • Multiple escorts (empty spaces): Unlike the single empty space in the 15-puzzle, GSTP can have multiple.
  • Synchronous movement: Multiple tiles can move simultaneously in a single time step.
  • Corner Following Constraint (CFC): A crucial constraint where if tile A moves into a space occupied by tile B, tile B can only move in the same direction as A if it's moving towards A. This prevents collisions but adds significant complexity compared to standard multi-agent pathfinding (MAPF) problems.

The core challenge is to find solutions that minimize the total time (makespan) to reach the goal configuration, while respecting these complex constraints. Existing work often ignores CFC for tractability, or focuses on finding any feasible solution rather than the fastest one. This paper aims to understand the fundamental limits and develop efficient algorithms for makespan-optimal GSTP.

Methods

The paper makes two main contributions:

  1. NP-Completeness Proof: The authors prove that finding makespan-optimal solutions for GSTP is NP-complete. This is achieved by a reduction from a known NP-complete problem called 2/2/4-SAT. They construct a specialized GSTP instance using "gadgets" (specific arrangements of tiles and spaces) that mimic the logic of the SAT problem. The movement of "literal tiles" within these gadgets must precisely match a satisfying assignment of the SAT instance to achieve the target configuration within a specific makespan. This demonstrates that no polynomial-time algorithm can solve all GSTP instances optimally.
  2. Tight Makespan Bounds and Algorithms: The paper establishes tight theoretical bounds on the minimum makespan for GSTP, considering the number of escorts. They then develop polynomial-time algorithms that achieve makespans asymptotically matching these lower bounds.
  3. Leveraging Rubik Table Algorithm (RTA): They adapt the RTA, a technique for rearranging tiles using sequences of row and column shuffles, to the GSTP context. Since direct shuffles aren't possible with sliding tiles, they simulate these shuffles by grouping rows/columns and planning tile movements accordingly.
  4. Subroutines for Small Grids/Escorts: Crucial to their approach are efficient algorithms for solving GSTP on smaller grids (e.g., 2xM, 3xM) and with a limited number of escorts (1 or 2). These subroutines are then used as building blocks for solving larger, more general GSTP instances.
  5. Focus on Escort Movement: For deriving bounds, they abstract the problem by focusing on the movement of escorts, which implicitly encodes tile movements. This allows for more concise analysis and derivation of lower bounds based on the total Manhattan distance that needs to be covered.

Datasets

Not discussed in the paper. The problem is defined abstractly with grid configurations rather than specific datasets.

Key Insights and Ideas

  • CFC is the Bottleneck: The Corner Following Constraint (CFC) is identified as a key factor that makes GSTP significantly harder than standard MAPF problems, preventing simpler solutions and driving the NP-completeness.
  • Gadget Engineering for Reductions: The clever design of "variable gadgets" and "clause gadgets" is essential for the NP-completeness proof, demonstrating how complex logical constraints can be encoded into tile movements.
  • RTA as a Powerful Framework: Adapting the Rubik Table Algorithm, originally for permutation puzzles, proves effective for developing efficient algorithms for GSTP, even with the added complexity of CFC and multiple escorts.
  • Asymptotic Optimality Achieved: The paper successfully closes the "optimality gap" by providing algorithms whose performance (makespan) asymptotically matches the theoretical minimum possible makespan, regardless of the number of escorts.

Key Results

  • NP-Completeness: The problem of computing makespan-optimal solutions for GSTP is proven to be NP-complete, even with a limited number of escorts (e.g., $\epsilon |G|$ escorts).
  • Tight Makespan Bounds:
    • For $k < \min(m_1, m_2)$ escorts, the expected makespan lower bound is $\Omega(m_1 m_2 / k)$.
  • For $k \ge \min(m_1, m_2)$ escorts, the expected makespan lower bound is $\Omega(\max(m_1, m_2))$.
  • These lower bounds are matched asymptotically by the upper bounds derived from their algorithms.
  • Specific Upper Bounds: The paper provides concrete, albeit complex, upper bounds for various numbers of escorts, for example:
  • Single escort on $m_1 \times m_2$ grid: $81m_1m_2 + 6m_1 + 9m_2 - 3$ steps.
  • Two escorts on $m_1 \times m_2$ grid: $18m_1m_2 - 4m_1 - 5m_2 - 29$ steps.
  • For $2 \le k < \min(m_1, m_2)$ even escorts: $44m_1m_2 + m_1(5 - 2k/2) + 15m_2 - 29$ steps.

Limitations and Future Work

  • Constant Factors: While the algorithms achieve asymptotic optimality, the constant factors in the upper bounds are still quite large (e.g., 81, 18, 44). Reducing these constants is a practical challenge.
  • Practical Implementation: The paper focuses on theoretical hardness and bounds. Developing practical, efficient implementations of these algorithms for real-world applications remains an area for future work.
  • Other Objectives: The paper primarily addresses makespan optimality. Future work could explore other objectives, such as minimizing total distance traveled or energy consumption.
  • Variations of GSTP: Investigating variations of the GSTP formulation, such as those with obstacles or different movement rules, is also suggested.

Summary updated

BibTeX
@inproceedings{gozon2024computing,
  author = {Marcus Gozon and Jingjin Yu},
  title = {{On Computing Makespan-Optimal Solutions for Generalized Sliding-Tile Puzzles}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2024},
  doi = {10.1609/aaai.v38i9.28895},
}
Figure