论文标题
魔术桌和物体重新安排
Rubik Tables and Object Rearrangement
论文作者
论文摘要
许多机器人应用需要重新安排许多移动物体，例如，在货架上组织产品，在运输端口上洗牌的容器，重新配置移动机器人的机队等。为了增加旨在解决这些重排问题的系统中的吞吐量，必须最大程度地减少原子操作的数量，例如单个对象的挑选n-播放。但是，由于对象之间的复杂相互依赖性，尤其是在高密度设置中，因此此优化任务构成了一个相当困难的挑战。 在应对上述挑战时，我们开发了一种新颖的算法工具Rubik Tables，它提供了对物体重新排列问题的简洁抽象，这是将存储在桌子或晶格中的商品的代理问题。在其基本形式中，rubik表是包含$ n^2 $项目的$ n \ times n $表。我们表明，在部分标记的设置中，可以使用最多$ 2N $列/行的重新配置，最多可以使用$ 2N $列/行，其中每个列（分别为，行）随机可以任意将存储在表的列中（resp。）中的项目定位。当物品完全可区分时，需要额外的$ N $ shuffles。魔术表允许许多概括，例如，到更高的维度。 使用Rubik表，我们为堆栈重排问题设计了第一个恒定因素最佳算法。 We show that, for $nd$ items stored in $n$ stacks of depth $d$ each, using one empty stack as the swap space, $O(nd)$ stack pop-push operations are sufficient for an arbitrary reconfiguration of the stacks where $d \le n^{\frac{m}{2}}$ for arbitrary fixed $m >0$. Rubik表的结果还允许开发恒定因素最佳解决方案，以解决极端机器人密度下的多机器人运动计划问题。这些基于Rubik表的算法在低多项式时间内运行。
A great number of robotics applications demand the rearrangement of many mobile objects, e.g., organizing products on shelves, shuffling containers at shipping ports, reconfiguring fleets of mobile robots, and so on. To boost the throughput in systems designed for solving these rearrangement problems, it is essential to minimize the number of atomic operations, e.g., the pick-n-places of individual objects. However, this optimization task poses a rather difficult challenge due to complex inter-dependency between objects, especially in high-density settings. In tackling the aforementioned challenges, we develop a novel algorithmic tool, Rubik Tables, that provides a clean abstraction of object rearrangement problems as the proxy problem of shuffling items stored in a table or lattice. In its basic form, a Rubik Table is an $n\times n$ table containing $n^2$ items. We show that the reconfiguration of items in such a Rubik Table can be achieved using at most $2n$ column/row shuffles in the partially labeled setting, where each column (resp., row) shuffle may arbitrarily permute the items stored in a column (resp., row) of the table. When items are fully distinguishable, additional $n$ shuffles are needed. Rubik Tables allow many generalizations, e.g., to higher dimensions. Using Rubik Table, we have designed a first constant-factor optimal algorithm for stack rearrangement problems. We show that, for $nd$ items stored in $n$ stacks of depth $d$ each, using one empty stack as the swap space, $O(nd)$ stack pop-push operations are sufficient for an arbitrary reconfiguration of the stacks where $d \le n^{\frac{m}{2}}$ for arbitrary fixed $m >0$. Rubik Table results also allow the development of constant-factor optimal solutions for solving multi-robot motion planning problems under extreme robot density. These algorithms based on Rubik Table results run in low-polynomial time.
