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, rigorously proven, 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.
翻译:我们调查了使用多个缓冲器解决使用轻便移动操纵原始件的一类重新排列问题的实用性。 在此问题上, 随机储存在薄饼中的物体将使用带有 k ⁇ 1 交换空格或缓冲器的机器人臂进行分类, 能够同时在终端效果器上维持 k 对象。 在结构方面, 我们显示, 添加每个新的缓冲器会减少回报率, 以保存终端效应或旅行距离, 并保持最小的回收操作总数 。 这是由于随机移动中一个有趣的循环循环结构, 且经过严格验证, 最大循环覆盖超过60%的物体。 在算法方面, 我们建议对 1D 和 2D 顶端重新排列问题采用快速算法, 能够有效地使用多个缓冲来提升解决方案的最佳性。 数字实验显示了我们方法的效率和可缩放性, 并且随着使用更多的缓冲器来确认正在不断缩小的返回结构 。