  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.
