On Computing Makespan-Optimal Solutions for Generalized Sliding-Tile Puzzles
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Optimally Solving Colored Generalized Sliding-Tile Puzzles: Complexity and Bounds
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 …
Makespan Optimal Solving of Cooperative Path-Finding via Reductions to Propositional Satisfiability
The problem of makespan optimal solving of cooperative path finding (CPF) is addressed in this paper. The task in CPF is to relocate a group of agents in a non-colliding way so that each agent eventually reaches its goal…
Optimal Sequential Task Assignment and Path Finding for Multi-Agent Robotic Assembly Planning
We study the problem of sequential task assignment and collision-free routing for large teams of robots in applications with inter-task precedence constraints (e.g., task $A$ and task $B$ must both be completed before ta…
SparsePipe: Parallel Deep Learning for 3D Point Clouds
We propose SparsePipe, an efficient and asynchronous parallelism approach for handling 3D point clouds with multi-GPU training. SparsePipe is built to support 3D sparse data such as point clouds. It achieves this by adop…
Deep LearningGPUOffloading Algorithms for Maximizing Inference Accuracy on Edge Device Under a Time Constraint
With the emergence of edge computing, the problem of offloading jobs between an Edge Device (ED) and an Edge Server (ES) received significant attention in the past. Motivated by the fact that an increasing number of appl…
Edge-computingimage-classificationImage Classification