论文标题
关于基于Pick-N-S-Swap的晶格重排中缓冲区的效用
On the Utility of Buffers in Pick-n-Swap Based Lattice Rearrangement
论文作者
论文摘要
我们研究了使用多个缓冲区在解决一类Pick-N-S-Swap操作原始原始原始原始词的重新排列问题方面的实用性。在此问题中，将随机存储在晶格中的对象应使用具有k> = 1个交换空间或缓冲区的机器人臂对其进行排序，该机器人能够同时在其末端效果上固定k对象。在结构方面，我们表明，每种新缓冲区的添加在节省最终效果距离距离的距离时会带来减少的回报，同时保持了最小的Pick-N-S-Swap操作总数。这是由于随机M permuntry中有趣的递归周期结构，其中最大的循环覆盖了60％以上的物体。在算法方面，我们提出了1D和2D晶格重排问题的快速算法，这些算法可以有效地使用多个缓冲区来提高解决方案最佳性。数值实验证明了我们方法的效率和可扩展性，并确认了随着更多的缓冲区的使用而减少的返回结构。
We investigate the utility of employing multiple buffers in solving a class of rearrangement problems with pick-n-swap manipulation primitives. In this problem, objects stored randomly in a lattice are to be sorted using a robot arm with k>=1 swap spaces or buffers, capable of holding up to k objects on its end-effector simultaneously. On the structural side, we show that the addition of each new buffer brings diminishing returns in saving the end-effector travel distance while holding the total number of pick-n-swap operations at the minimum. This is due to an interesting recursive cycle structure in random m-permutation, where the largest cycle covers over 60% of objects. On the algorithmic side, we propose fast algorithms for 1D and 2D lattice rearrangement problems that can effectively use multiple buffers to boost solution optimality. Numerical experiments demonstrate the efficiency and scalability of our methods, as well as confirm the diminishing return structure as more buffers are employed.
