  Object rearrangement is a fundamental sub-task in accomplishing a great many
physical tasks. As such, effectively executing rearrangement is an important
skill for intelligent robots to master. In this study, we conduct the first
algorithmic study on optimally solving the problem of Multi-layer Object
Rearrangement on a Tabletop (MORT), in which one object may be relocated at a
time, and an object can only be moved if other objects do not block its top
surface. In addition, any intermediate structure during the reconfiguration
process must be physically stable, i.e., it should stand without external
support. To tackle the dual challenges of untangling the dependencies between
objects and ensuring structural stability, we develop an algorithm that
interleaves the computation of the optimal rearrangement plan and structural
stability checking. Using a carefully constructed integer linear programming
(ILP) model, our algorithm, Stability-aware Integer Programming-based Planner
(SIPP), readily scales to optimally solve complex rearrangement problems of 3D
structures with over 60 building blocks, with solution quality significantly
outperforming natural greedy best-first approaches.
  Upon the publication of the manuscript, source code and data will be
available at https://github.com/arc-l/mort/
