On Computing Makespan-Optimal Solutions for Generalized Sliding-Tile Puzzles
This addresses a foundational challenge in multi-agent motion planning for real-world applications like warehouse automation, though it is incremental in extending classic puzzles to more complex settings.
The paper tackles the problem of computing makespan-optimal solutions for generalized sliding-tile puzzles (GSTP), which model multi-agent motion in applications like warehouse automation, and shows that this is NP-complete while providing polynomial-time algorithms with constant-factor approximations under randomized configurations.
In the $15$-puzzle game, $15$ labeled square tiles are reconfigured on a $4\times 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.