Complexity Results and Fast Methods for Optimal Tabletop Rearrangement with Overhand Grasps
Complexity Results and Fast Methods for Optimal Tabletop Rearrangement with Overhand Grasps
复制标题
DOI：
10.1177/0278364918780999
复制
发表时间：
2017-11
期刊：
影响因子：
--
通讯作者：
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 travel distance of the end-effector. Although such problems do not involve all the complexities of general rearrangement, they remain computationally hard in both cases. This is shown through reductions from well-understood, hard combinatorial challenges to these rearrangement problems. The reductions are also shown to hold in the reverse direction, which enables the convenient application on rearrangement of well-studied algorithms. 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, including hardware-based trials, shows that the proposed pipeline computes 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 setup.