研究彩色滑块谜题的最优解复杂度与上下界，为多机器人系统提供理论支持。
Optimally Solving Colored Generalized Sliding-Tile Puzzles: Complexity and Bounds
- 将滑块谜题扩展至带颜色区分的多机器人场景，建模更贴近实际应用。
- 证明了问题在多种条件下的计算复杂性，并给出解长上下界仅差对数因子。
- 结果可推广到高维空间，适用于未来智能仓储与自动驾驶车库系统设计。
广义滑块谜题（GSTP）允许多个方块在棋盘上并行移动，同时遵循相邻方块间的自然几何碰撞约束，为移动机器人仓库或自动驾驶车库等多机器人应用提供了高保真数学模型。本文进一步研究了其推广形式——彩色广义滑块谜题（CGSP），其中方块具有不同程度的可区分性，这在前述应用场景中普遍存在。本研究揭示了CGSP及其关键子问题在广泛条件下的计算复杂性，并刻画了解决方案完成时间（makespan）的上下界，二者之差不超过对数因子。这些结论还被拓展至更高维度的谜题版本。
原文摘要 · Abstract (English)
The Generalized Sliding-Tile Puzzle (GSTP), allowing many square tiles on a board to move in parallel while enforcing natural geometric collision constraints on the movement of neighboring tiles, provide a high-fidelity mathematical model for many high-utility existing and future multi-robot applications, e.g., at mobile robot-based warehouses or autonomous garages. Motivated by practical relevance, this work examines a further generalization of GSTP called the Colored Generalized Sliding-Tile Puzzle (CGSP), where tiles can now assume varying degrees of distinguishability, a common occurrence in the aforementioned applications. Our study establishes the computational complexity of CGSP and its key sub-problems under a broad spectrum of possible conditions and characterizes solution makespan lower and upper bounds that differ by at most a logarithmic factor. These results are further extended to higher-dimensional versions of the puzzle game.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。