We investigate 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  or partially labeled  ) 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 settingsthat are asymptotically optimal , in expectation, assuming that the initial configuration is randomly selected . Simulation studies confirm the effectiveness of our algorithms in comparison to natural greedy best-first algorithms.
We propose and study a class of rearrangement problems under a novel pick-n-swap prehensile manipulation model, in which a robotic manipulator, capable of carrying an item and making item swaps, is tasked to sort items stored in lattices of variable dimensions 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 low polynomial time cycle-following based algorithms that optimally perform rearrangements on 1D lattices under both fully- and partially-labeled settings. On the other hand, we show that rearrangement on 2D and higher dimensional lattices becomes computationally intractable to optimally solve. Despite their NP-hardness, we prove that efficient cycle-following based algorithms remain asymptotically optimal for 2D fully- and partially-labeled settings , in expectation, using the interesting fact that random permutations induce only a small number of cycles. We further improve these algorithms to provide 1.x-optimality when the number of items is small . Simulation studies corroborate the effectiveness of our algorithms.
R
investigate
propose and study
R
multi-object rearrangement problems
rearrangement problems under a novel pick-n-swap prehensile manipulation model,
A
of variable dimensions
A
, where each item has a unique label,
A
, where multiple items may be of the same type
D
efficient (
R
)
cycle-following based
R
fully and partially labeled
fully- and partially-labeled
R
prove
show
R
are able to again develop efficient algorithms
prove that efficient cycle-following based algorithms remain asymptotically optimal
R
fully and partially labeled settingsthat are asymptotically optimal
fully- and partially-labeled settings
R
assuming that the initial configuration is randomly selected
using the interesting fact that random permutations induce only a small number of cycles. We further improve these algorithms to provide 1.x-optimality when the number of items is small
R
confirm
corroborate
D
algorithms in comparison to natural greedy best-first