Robotics: Science and Systems XVII

Rearrangement on Lattices with Swaps: Optimality Structures and Efficient Algorithms

Jingjin Yu


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:



    AUTHOR    = {Jingjin Yu}, 
    TITLE     = {{Rearrangement on Lattices with Swaps: Optimality Structures and Efficient Algorithms}}, 
    BOOKTITLE = {Proceedings of Robotics: Science and Systems}, 
    YEAR      = {2021}, 
    ADDRESS   = {Virtual}, 
    MONTH     = {July}, 
    DOI       = {10.15607/RSS.2021.XVII.014}