Rearrangement on Lattices with Swaps: Optimality Structures and Efficient Algorithms

We propose and study a class of multi-object rearrangement problems in which a robotic manipulator; capable of carrying an item and making item swaps; is tasked to sort items stored in lattices in a time-optimal manner. We systematically analyze the intrinsic optimality structure; which is fairly rich and intriguing; under different levels of item distinguishability (fully labeled; where each item has a unique label; or partially labeled; where multiple items may be of the same type) and different lattice dimensions. Focusing on the most practical setting of one and two dimensions; we develop efficient (low polynomial time) algorithms that optimally perform rearrangements on 1D lattices under both fully- and partially-labeled settings. On the other hand; we prove that rearrangement on 2D and higher dimensional lattices becomes computationally intractable to optimally solve. Despite their NP-hardness; we are able to again develop efficient algorithms for 2D fully- and partially-labeled settings that are asymptotically optimal; in expectation; assuming that the initial configuration is randomly selected. Simulation studies confirm the effectiveness of our algorithms in comparison to greedy best-first approaches. Source code of Python implementation: https://github.com/rutgers-arc-lab/lattice-rearrangement/