Efficient, High-Quality Stack Rearrangement
Title | Efficient, High-Quality Stack Rearrangement |
Publication Type | Journal Article |
Year of Publication | 2018 |
Authors | Shuai, H, Stiffler, N, Bekris, KE, Yu, J |
Journal | IEEE Robotics and Automation Letters (RA-L) [Also accepted to appear at the 2018 IEEE International Conference on Robotics and Automation (ICRA)] |
Abstract | This work studies rearrangement problems involving the sorting of robots or objects in stack-like containers, which can be accessed only from one side. Two scenarios are considered: one where every robot or object needs to reach a particular stack, and a setting in which each robot has a distinct position within a stack. In both cases, the goal is to minimize the number of stack removals that need to be performed. Stack rearrangement is shown to be intimately connected to pebble motion problems, a useful abstraction in multi-robot path planning. Through this connection, feasibility of stack rearrangement can be readily addressed. The paper continues to establish lower and upper bounds on optimality, which differ only by a logarithmic factor, in terms of |
URL | https://www.cs.rutgers.edu/~kb572/pubs/stack_rearrangement.pdf |