Object rearrangement is important for many applications but remains
challenging, especially in confined spaces, such as shelves, where objects
cannot be accessed from above and they block reachability to each other. Such
constraints require many motion planning and collision checking calls, which
are computationally expensive. In addition, the arrangement space grows
exponentially with the number of objects. To address these issues, this work
introduces a lazy evaluation framework with a local monotone solver and a
global planner. Monotone instances are those that can be solved by moving each
object at most once. A key insight is that reachability constraints at the
grasps for objects' starts and goals can quickly reveal dependencies between
objects without having to execute expensive motion planning queries. Given
that, the local solver builds lazily a search tree that respects these
reachability constraints without verifying that the arm paths are collision
free. It only collision checks when a promising solution is found. If a
monotone solution is not found, the non-monotone planner loads the lazy search
tree and explores ways to move objects to intermediate locations from where
monotone solutions to the goal can be found. Results show that the proposed
framework can solve difficult instances in confined spaces with up to 16
objects, which state-of-the-art methods fail to solve. It also solves problems
faster than alternatives, when the alternatives find a solution. It also
achieves high-quality solutions, i.e., only 1.8 additional actions on average
are needed for non-monotone instances.

该论文提出了一种懒惰计算法并结合局部单调求解器与全局规划器，以高效地解决在密闭空间中进行的物体重新排列问题。该算法可在考虑物体间可达性约束的情况下，快速发现物体间依赖关系，并在求解目标时拓展局部最优解来移动物体以完成整个任务，成功应用于高达 16 个物体的场景中，并且解决速度和解决质量都优于目前现有算法。