High-Quality Tabletop Rearrangement with Overhand Grasps: Hardness Results and Fast Methods
High-Quality Tabletop Rearrangement with Overhand Grasps: Hardness Results and Fast Methods
复制标题
DOI：
10.15607/rss.2017.xiii.051
复制
发表时间：
2017-05
期刊：
影响因子：
--
通讯作者：
Shuai D. Han;Nicholas M. Stiffler;A. Krontiris;Kostas E. Bekris;Jingjin Yu
中科院分区：
文献类型：
--
作者：
Shuai D. Han;Nicholas M. Stiffler;A. Krontiris;Kostas E. Bekris;Jingjin Yu
研究了一类在实际应用中经常出现的对象重排问题的组合结构。这些问题涉及放置在平坦的水平表面上的多个相似几何形状的物体，机器人可以从上面接近它们并执行拾取和放置操作来重新排列它们。本文考虑了开始和目标对象姿势重叠的情况，以及它们不重叠的情况。对于重叠姿态，主要目标是最小化拾取和放置动作的数量，然后最小化末端执行器行进的距离。对于非重叠的情况，目标只是最小化末端效应器距离。虽然这些问题不涉及一般重排的所有复杂性，但在这两种情况下，它们仍然是计算上的困难挑战。这是通过良好理解，硬组合的挑战和这些重排问题之间的双向减少。减少的好处是，有很好的研究算法来解决这些完善的组合挑战。这些算法在实践中可以是非常有效的，尽管硬度的结果。本文建立在这些减少的结果，提出了一个算法流水线处理的重排问题。实验评估表明，该管道实现了高质量的路径方面的优化目标。此外，它表现出非常理想的可扩展性的对象的数量增加，在重叠和非重叠的设置。
This paper studies the underlying combinatorial structure of a class of object rearrangement problems, which appear frequently in applications. The problems involve multiple, similar-geometry objects placed on a flat, horizontal surface, where a robot can approach them from above and perform pick-and-place operations to rearrange them. The paper considers both the case where the start and goal object poses overlap, and where they do not. For overlapping poses, the primary objective is to minimize the number of pick-and-place actions and then to minimize the distance traveled by the end-effector. For the non-overlapping case, the objective is solely to minimize the end-effector distance. While such problems do not involve all the complexities of general rearrangement, they remain computationally hard challenges in both cases. This is shown through two-way reductions between well-understood, hard combinatorial challenges and these rearrangement problems. The benefit of the reduction is that there are well studied algorithms for solving these well-established combinatorial challenges. These algorithms can be very efficient in practice despite the hardness results. The paper builds on these reduction results to propose an algorithmic pipeline for dealing with the rearrangement problems. Experimental evaluation shows that the proposed pipeline achieves high-quality paths with regards to the optimization objectives. Furthermore, it exhibits highly desirable scalability as the number of objects increases in both the overlapping and non-overlapping setups.