一般化スライディングタイルパズルのメイクスパン最適解計算
On Computing Makespan-Optimal Solutions for Generalized Sliding-Tile Puzzles
複数のタイルが同期移動する一般化スライディングタイルパズルにおいて、最適解の構造を解析し、メイクスパン最適解の計算がNP完全であることを示すとともに、ランダムな初期・目標配置に対して定数近似比を高確率で達成する多項式時間アルゴリズムを開発した。
著者: Marcus Gozon, Jingjin Yu
分類: cs.RO, cs.AI, cs.MA
原文アブストラクト
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.
