Adversarial Object Rearrangement in Constrained Environments with
  Heterogeneous Graph Neural Networks
Adversarial object rearrangement in the real world (e.g., previously unseen
or oversized items in kitchens and stores) could benefit from understanding
task scenes, which inherently entail heterogeneous components such as current
objects, goal objects, and environmental constraints. The semantic
relationships among these components are distinct from each other and crucial
for multi-skilled robots to perform efficiently in everyday scenarios. We
propose a hierarchical robotic manipulation system that learns the underlying
relationships and maximizes the collaborative power of its diverse skills
(e.g., pick-place, push) for rearranging adversarial objects in constrained
environments. The high-level coordinator employs a heterogeneous graph neural
network (HetGNN), which reasons about the current objects, goal objects, and
environmental constraints; the low-level 3D Convolutional Neural Network-based
actors execute the action primitives. Our approach is trained entirely in
simulation, and achieved an average success rate of 87.88% and a planning cost
of 12.82 in real-world experiments, surpassing all baseline methods.
Supplementary material is available at
https://sites.google.com/umn.edu/versatile-rearrangement.
Xibai Lou, Houjian Yu, Ross Worobel, Yang Yang, Changhyun Choi
Adversarial Object Rearrangement in Constrained Environments with Heterogeneous Graph Neural Networks

###### Abstract

Adversarial object rearrangement in the real world (e.g., previously unseen or oversized items in kitchens and stores) could benefit from understanding task scenes, which inherently entail heterogeneous components such as current objects, goal objects, and environmental constraints. The semantic relationships among these components are distinct from each other and crucial for multi-skilled robots to perform efficiently in everyday scenarios. We propose a hierarchical robotic manipulation system that learns the underlying relationships and maximizes the collaborative power of its diverse skills (e.g., pick-place, push) for rearranging adversarial objects in constrained environments. The high-level coordinator employs a heterogeneous graph neural network (HetGNN), which reasons about the current objects, goal objects, and environmental constraints; the low-level 3D Convolutional Neural Network-based actors execute the action primitives. Our approach is trained entirely in simulation, and achieved an average success rate of 87.88% and a planning cost of 12.82 in real-world experiments, surpassing all baseline methods. Supplementary material is available at [https://sites.google.com/umn.edu/versatile-rearrangement](https://sites.google.com/umn.edu/versatile-rearrangement).

 Deep Learning in Grasping and Manipulation, Perception for Grasping and Manipulation

## I Introduction

Real-world robots typically operate in highly structured environments rather than everyday scenarios that contain adversarial objects (e.g., previously unseen or oversized items) and complex constraints (e.g., boxes, shelves, etc.). While a factory robot simply transfers identical items on a belt drive, a domestic robot tasked with rearranging a pantry may frequently encounter oversized containers on shelves. As illustrated in Fig. 1, real-world object rearrangement tasks are inherently heterogeneous, consisting of current objects, goal objects, and environmental constraints. The semantic relationships among these components (e.g., the "meat can" on the "ground" has a goal location on the "shelf") contain essential information for efficiently completing the task. Robots that understand and utilize such knowledge are more likely to succeed in the real world, where adversarial objects and various environmental constraints are ubiquitous.

The object rearrangement problem has traditionally been addressed with model-based task and motion planning (TAMP) [1], which often assumes a fully observable environment and is thus difficult to scale to previously unseen scenarios [2, 3, 4]. Recent deep learning-based approaches can generalize to novel objects, owing to the advances in perception and grasping models [5, 6]. However, they typically assume no environmental constraints (e.g., an open tabletop) [7, 8, 4] or rely on iterative collision checking [9], which limits their generalizability in the real world. Additionally, most existing works focus on graspable objects and separately study pick-place or pushing. Although some have investigated both [7, 8], they only push to facilitate grasping [8] or employ specialized tools [7]. Relatively few have explored coordinating low-cost pushing, which may be limited by the environment, with pick-place to improve the robot's capability and efficiency. Therefore, the problem of rearranging adversarial objects with multiple skills in constrained environments remains unsolved.

To address this challenge, we propose to learn from the heterogeneous task components and exploit the distinct

Fig. 1: In this adversarial object rearrangement task, the color-coded heterogeneous task components (e.g., current objects, goal objects, and environmental constraints) are linked by different semantic relationships that are crucial to efficiently guiding a multi-skilled robot. By understanding that the “bowl” and the “shelf” are related by “on”, a robot will swiftly push it to the nearby goal and clear space for the “meat can”, which requires pick-place to move from “ground” to “shelf”.
semantic relationships among them. We devise an adversarial object rearrangement system that utilizes both pushing and grasping, to maximize the robot's efficiency and generalize to novel constrained environments. Our hierarchical approach represents a task as a heterogeneous graph over a pair of current and goal RGB-D images, which are segmented into objects and environmental constraints. At the high-level, a heterogeneous graph neural network [10] (HetGNN)-based coordinator reasons about the graph and its underlying semantic information and predicts the optimal action primitive and next target, such that the goal configuration can be successfully achieved by the low-level actors with minimal planning costs. The system operates in a closed-loop fashion, continually re-observing the scene at each time step to predict more accurate rearrangement plans.

We experiment in both simulated and real-world environments. Our approach achieves, on average, an 88.78% success rate with 12.82 actions in real-world tests, outperforming several baselines by large margins. To the best of our knowledge, this is the first approach that utilizes HetGNN to coordinate robot skills for rearranging adversarial objects in constrained environments. The main contributions of this paper are as follows:

* We propose a hierarchical pushing and grasping robotic system that addresses adversarial object rearrangement problems in constrained environments. By leveraging the semantic relationships in the task, the high-level coordinator guides the 3D CNN-based low-level actors to perform more efficiently.
* Our approach represents the rearrangement task as a heterogeneous graph and exploits the power of a HetGNN to reason about the underlying relationships among the task components. It learns from an expert planner in simulation and predicts the next target and action end-to-end.
* While previous approaches often assume an open workspace or use hard-coded solutions, our method learns to adapt to complex environments, where previously unseen constraints could significantly limit existing works.

## II Related Work

Object rearrangement is an essential challenge in robotics and embodied AI [11]. The problem is commonly studied under the broad subject of task and motion planning (TAMP) [1], which is often formulated hierarchically with a high-level task planner (i.e., which action to perform on which item) and a low-level motion planner (i.e., how to move the end-effector) such that the goals can be achieved [2, 11]. Typical TAMP approaches are model-based and often rely on task-specific knowledge and accurate 3D models of the environment [2, 3, 4]. Hence, they often do not generalize well to the real world, where the required information may not be accessible.

Recent works have equipped classical TAMP with deep learning-based perception [12, 13] and grasping models [14, 15, 16] to generalize to novel objects [6, 5, 17, 8]. However, many researchers focus exclusively on pick-place [5, 18, 19, 17], largely limiting the robot's capability in the real world where objects are frequently not graspable (e.g., large items with a parallel-jaw gripper or cloths with a suction gripper). To rearrange more adversarial objects, non-prehensile action primitives such as pushing are needed. Inspired by [20], Tang et al. [8] use pushing to facilitate grasping by breaking the clutter, but not to rearrange adversarial objects. While [7] sorts large-scale basic cuboids with both pushing and grasping, they build a specialized end of arm tooling (EOAT) for pushing. Transporter [21] and TRLB [4] bypass the challenge with suction mechanisms.

Long-horizon planning for object rearrangement has been studied analytically with Rapidly Exploring Random Tree (RRT) [22] or Monte Carlo Tree Search (MCTS) [23], which explores multiple future possibilities but is less robust to noise and occlusions. PlaNet [24] addresses the partial observability issue with a learned forward dynamics model and plans actions in latent space. Similarly, Visual Robot Task Planning [25] learns to encode the scene into a latent representation and then uses tree search for planning in this latent space. Both works are task-specific in simulation and highly likely require large demonstration data to generalize to a real robot. Other researchers have leveraged spatial relations for planning [18, 19]. Liu et al. [19] take language as an input that specifies the goal configuration and then employ Transformers [26] to translate the spatial relations into a sequence of pick-place instructions. Our approach conveniently uses a single imperfect RGB-D image to specify the goal and directly transfer to the real world.

Prior robotics research has investigated Graph Neural Networks [27, 28] in object rearrangement problems [29, 5, 8]. Closely related to our work, NeRP [5] employs a high-level object selection module with k-GNNs that plan for rearranging novel objects with pick-place. However, they are limited to graspable objects on an open tabletop, not considering any environmental constraints. Tang et al. [8] compare the Graph Edit Distance (GED) between the start and goal scene graphs and plan for selective object rearrangement of multiple objects, but also assume a simplified environment. In constrained environments, existing works typically assume a constant structure [30] and rely on iterative collision checking [9], which is computationally expensive and often suffers from noise and occlusion in the real world. These methods are not as generalizable as ours, as we employ a novel HetGNN-based [10] coordinator that exploits the semantic relationships among heterogeneous components in the task and significantly improves the robot's efficiency.

## III Problem Formulation

We aim to design an efficient robotic manipulation system that addresses adversarial object rearrangement problems in unstructured real-world environments, where environmental constraints could heavily influence the robot's behavior. We formulate the problem as follows:

**Definition 1**.: _Given a goal image \(I_{T}\) describing a desired object configuration in a constrained environment, the goal of the rearrangement task is to apply a sequence of manipulation actions on the current objects to achieve the
goal configuration where every object is within \(\tau\) of its corresponding goal location in 3D space._

In our experiments, we use \(\tau=3\)\(cm\). The constrained environments considered in this work are defined as

**Definition 2**.: _Constrained environments include geometric constraints such that certain manipulation actions are not always feasible (e.g., pushing an object across height discontinuities)._

We assume about robot skills and objects as follows:

**Assumption 1**.: _The robot is capable of pick, place, move, and push. pick-place is a sequence of pick, move, and place, while push requires a single move._

**Assumption 2**.: _The adversarial objects are possibly unknown (i.e., novel objects) to the robot and may not be graspable (e.g., object dimension is larger than the maximum opening of the robot's end effector) for which only push is applicable._

Let \(\mathcal{O}^{t}=\{o_{1}^{t},o_{2}^{t},\cdots,o_{N}^{t}\}\) and \(\mathcal{O}^{T}=\{o_{1}^{T},o_{2}^{T},\cdots,o_{N}^{T}\}\) denote the set of objects in the current scene and the goal scene, respectively. The robot action \(a\in\{\text{pick-place},\text{push}\}\) for a selected object \(o_{i}^{t}\in\mathcal{O}^{t}\) is subject to a binary-valued metric \(\mathcal{S}_{a}(o_{i}^{t},o_{i}^{T},\mathcal{C})\in\{\text{0,1}\}\) where \(\mathcal{C}=\{c_{1},c_{2},\cdots,c_{N}\}\) denotes the set of environmental constraints in the scene. \(\mathcal{S}_{a}=1\) indicates that push is more effective for the selected object at time \(t\), whereas \(\mathcal{S}_{a}=0\) represents that pick-place is more effective. When both actions are applicable, the robot performs push (i.e., \(\mathcal{S}_{a}=1\)) since it costs fewer actions.

To reason about the relationships between the objects \(\mathcal{O}^{t},\mathcal{O}^{T}\), and the constrained environment \(\mathcal{C}\), we employ a heterogeneous graph representation \(\mathcal{G}\). A heterogeneous graph \(\mathcal{G}(\mathcal{V},\mathcal{E})\), where \(\mathcal{V}\) and \(\mathcal{E}\) represent the set of nodes and edges, respectively, is associated with node and edge type mapping functions \(\phi\colon\mathcal{V}\rightarrow\mathcal{F}\) and \(\psi\colon\mathcal{E}\rightarrow\mathcal{R}\), where \(\mathcal{F}\) is the set of node types (e.g., "current", "goal", and "environment") and \(\mathcal{R}\) is the set of edge types describing spatial relations (e.g., a "goal" node is "in" a "box"). The heterogeneous graph \(\mathcal{G}\) is constructed from a pair of RGB-D observations of current and goal configurations \((I_{t},I_{T})\). We would like to learn a high-level coordinator that predicts a selection probability \(p_{o}(\mathcal{C},\mathcal{O}^{t},\mathcal{O}^{T})\) for each object such that the goal configuration can be achieved with the least number of actions by rearranging the most feasible object. The coordinator should simultaneously learn to select the appropriate action for such targets. Specifically, the action probability \(p_{a}(\mathcal{C},\mathcal{O}^{t},\mathcal{O}^{T})=p_{push}(\mathcal{C}, \mathcal{O}^{t},\mathcal{O}^{T})=Pr(\mathcal{S}_{a}=1|\mathcal{G}(\mathcal{V},\mathcal{E}))\); hence the pick-place probability \(p_{pick}(\mathcal{C},\mathcal{O}^{t},\mathcal{O}^{T})=Pr(\mathcal{S}_{a}=0| \mathcal{G}(\mathcal{V},\mathcal{E}))=1-p_{push}\).

## IV Proposed Approach

This section describes the proposed adversarial object rearrangement system that coordinates pick-place and push in constrained environments. To address the exploration challenge in long-horizon problems, our approach takes advantage of the hierarchical structure and uses a high-level coordinator in conjunction with low-level actors to guide the robot at each time step \(t\). The goal configuration at time \(T\) is given as a reference RGB-D image \(I_{T}\). Given the current observation of the scene \(I_{t}\), the HetGNN-based coordinator reasons about the underlying relationships in the heterogeneous graph and simultaneously predicts which object should be prioritized and how to move it, such that the goal can be achieved efficiently. The overview of the approach is described in Fig. 2, and the algorithm is delineated in Algorithm 1.

### _Object Matching_

Given the goal configuration specified by an RGB-D image \(I_{T}\), the object matching module finds each object's correspondence in the current observation \(I_{t}\). We first obtain the instance masks \(\mathcal{M}_{T}\) of \(N\) objects in \(I_{T}\) using the SAG [13], an object instance segmentation method with active robotic manipulation. Next, we encode each object's RGB-D cropping from \(\mathcal{M}_{T}\) into a feature vector \(\mathbf{h}_{i}\in\mathbb{R}^{10}\) using a Siamese network [31]. The network is trained with contrastive loss such that the L2 distance in the latent space is close for the same objects and far for different ones [32],

Fig. 2: The current RGB-D image \(I_{t}\) and goal \(I_{T}\) are fed into the graph constructor, which encodes the heterogeneous task components (color-coded) into node embeddings with pre-trained 3D encoders. Then the HetGNN updates the embeddings based on its learned parameters, and the high-level coordinator predicts the object selection score \(p_{o}\) and the action selection score \(p_{a}\) for each object. We select the object with the highest \(p_{o}\) as the target and decide which action to execute based on \(p_{a}\). Finally, we feed the decision to the low-level actors, which are responsible for performing the robot’s actions. The closed-loop system will run until the goal configuration is achieved or the maximum number of steps is reached.
[33]. The set \(\mathcal{H}_{T}=\{\mathbf{h}_{1}^{T},\mathbf{h}_{2}^{T},\cdots,\mathbf{h}_{N}^{T}\}\) represents the features of objects in the goal configuration. At the current time step \(t\), we follow the same procedure to extract the feature set \(\mathcal{H}_{t}\) of current objects. The L2 distance between each element in \(\mathcal{H}_{t}\) and each element in \(\mathcal{H}_{T}\) is calculated, and the current-goal correspondence \(\mathbf{c}\in\mathbb{R}^{N\times 2}\) is established by associating each goal object to the one with the smallest L2 distance in the current time \(t\).

### _Constructing Heterogeneous Graph_

The high-level coordinator is based on a HetGNN, which exploits the heterogeneity and the underlying semantic information in the input heterogeneous graph. To construct a graph that can efficiently capture the information, we consider three different node types: current objects \(\mathcal{O}^{t}\), goal objects \(\mathcal{O}^{T}\), and the environmental constraints \(\mathcal{C}\). Unlike the traditional homogeneous graphs, the relationships between these nodes are represented by a set of heterogeneous edge types, which could be semantically interpreted (e.g., the edge between "current objects" nodes and "constraints" nodes representing the "in" relationship, the edge between "current objects" nodes and "goal object" nodes representing the "to" relationship).

The heterogeneous graph is illustrated in Fig. 2. The nodes \(\mathcal{V}\) include current nodes \(\mathbf{v}^{t}\), goal nodes \(\mathbf{v}^{T}\), and the constraints nodes \(\mathbf{v}^{c}\), representing different types of the heterogeneous task components. The graph connectivity contains two fully-connected sub-graphs, one for current nodes and one for goals nodes. Each current node is also connected to its corresponding goal node, specified by the current-goal correspondence \(\mathbf{c}\). The constraint node(s) is/are individually connected to each object node to propagate the influence of the environmental constraints. Each node embedding is extracted from the geometric shape of the object or environment. Specifically, the point clouds of the current objects \(\mathcal{P}_{t}\), goal objects \(\mathcal{P}_{T}\), and constraints \(\mathcal{P}_{c}\) are obtained through back-projection, and transformed into voxel grids \(V_{t}\), \(V_{T}\), and \(V_{c}\), respectively. We then encode the voxel grids into geometric features \(\mathbf{x}_{t}\), \(\mathbf{x}_{T}\), and \(\mathbf{x}_{c}\) using a 3D encoder \(E_{\phi}\): Conv3D(1, 32, 5) \(\rightarrow\) ELU \(\rightarrow\) Maxpool(2) \(\rightarrow\) Conv3D(32, 32, 3) \(\rightarrow\) ELU \(\rightarrow\) Maxpool(2) \(\rightarrow\) FC(\(32\times 6\times 6\times 6\), 12). The encoder is taken from a pretrained 3D Convolutional Autoencoder, whose latent features could effectively represent the shape of the input object. Finally, each node embedding is concatenated with the object's location \(\mathbf{z}\in\mathbb{R}^{3}\).

### _HetGNN-based Coordinator_

GNNs are effective in discovering underlying relationships among nodes by learning a non-linear function \(\mathcal{F}\), which encodes a graph \(\mathcal{G}\) to \(\mathcal{G}^{\prime}\) with updated node and edge features [34]. We start with the base homogeneous Graph Attention Networks (GAT) [35]. The message-passing function, parameterized by a weight matrix \(\mathbf{\Theta}\) and attention coefficients \(\alpha_{i,j}\), for updating latent features \(\mathbf{x}_{i}\) of node \(\mathbf{v}_{i}\) is defined as

\[\mathbf{x}_{i}^{\prime}=\alpha_{i,i}\mathbf{\Theta}\mathbf{x}_{i}+\sum_{j\in \mathcal{N}(i)}\alpha_{i,j}\mathbf{\Theta}\mathbf{x}_{j} \tag{1}\]

where the attention coefficients \(\alpha_{i,j}\) are computed by

\[\alpha_{i,j}=\frac{\exp\left(\sigma\left(\mathbf{a}^{\top}[\mathbf{\Theta} \mathbf{x}_{i}\,\|\,\mathbf{\Theta}\mathbf{x}_{j}]\right)\right)}{\sum_{k\in \mathcal{N}(i)\cup\{i\}}\exp\left(\sigma\left(\mathbf{a}^{\top}[\mathbf{\Theta }\mathbf{x}_{i}\,\|\,\mathbf{\Theta}\mathbf{x}_{k}]\right)\right)} \tag{2}\]

The \(\mathbf{a}\) is the learned weight matrix of the attention mechanism, \(\mathcal{N}(i)\) is the neighbors of \(\mathbf{v}_{i}\), and \(\sigma=LeakyReLU(\cdot)\).

Note that homogeneous graph neural networks could not differentiate different types of nodes and edges. They lack the mechanism to effectively harness the heterogeneous information. To exploit the semantic relationships among the heterogeneous task components, we adopt the approach in [10] that introduces heterogeneity to the homogeneous GNN by dedicating an individual message passing function to each edge type, as shown in Fig. 3. Given a heterogeneous graph \(\mathcal{G}(\mathcal{V},\mathcal{E})\), the network aggregates node embeddings by using the message passing functions corresponding to

Fig. 3: The HetGNN network takes as input graphs of heterogeneous node types (e.g., \(\mathbf{x}_{T},\mathbf{x}_{t},\mathbf{x}_{c}\)). The message passing functions are duplicated for each edge type to update the weights for different relationships. Finally, the scores \(p_{a}\) and \(p_{o}\) are derived from updated current node features \(\mathbf{x}_{T}^{\prime},\mathbf{x}_{t}^{\prime},\mathbf{x}_{c}\).
the active edge types, which are determined by the types of the connected nodes. For instance, the edge between current nodes \(\mathbf{v}_{t}\) and goal nodes \(\mathbf{v}_{T}\) belongs to a "current-to-goal" edge type. The HetGNN includes three graph attention convolutional layers to ensure effective learning of the underlying relational information. After the node embeddings are updated by the HetGNN, two Multi-Layer-Perceptron (MLP)-based prediction heads, object selector \(\psi_{o}:\mathcal{V}\rightarrow\mathcal{O}\) and action selector \(\psi_{a}:\mathcal{V}\rightarrow\mathcal{A}\), are connected to \(\mathbf{x}_{t}\) to estimate which action should be performed on which object.

### _Low-level Actors_

The low-level actors are responsible for executing the actions decided by the high-level coordinator. If pick-place is selected, we first generate a batch of grasp candidates following the shape completion-based sampling algorithm in [36]. Next, we use the Grasp Stability Predictor (GSP)1, a 3D CNN-based 6-DoF grasp detection algorithm, to select a feasible pose for grasping. After the target object has been successfully grasped, we place the object to its corresponding goal location by checking the current-goal correspondence \(\mathbf{c}\) calculated in IV-A. If push is the more effective action for the target, we plan for a direct pushing path while checking collisions using the flexible collision library (FCL) [37]. The robot closes its fingers and follows a straight path, which is divided into multiple short segments of fixed length by the intermediate waypoints. Then we use the mean square error (MSE) between the object's voxel grids and goal location to supervise a simplified model predictive control loop.

Footnote 1: Note that the acronym GSP refers to the 3D CNN grasping module in [14], defined here for a concise reference.

### _Expert Planner and Training_

To obtain training data, we generated 3,000 RGB-D images of the randomly positioned training objects (e.g., toy blocks and cylinders of different size) in environments with arbitrary constraints (e.g., bins, shelves). Then, two RGB-D images are randomly sampled as start and goal configurations for a rearrangement task. For all the rearrangement tasks, we define a pick-place cost of **3** and a push cost of **1** following Assumption 1.

The training labels, action selection labels, and object selection labels are automatically annotated by an expert planner built in a fully observable simulator. First, the expert planner examines each object's mesh model and reasons about which action primitive to use. It relies on two criteria: 1) if the object is graspable and 2) if a direct pushing path exists between the current and goal location. The binary action selection label will be 1 for push if the object is not graspable or a direct pushing path exists, and 0 for pick-place if the object is graspable and no direct pushing path exists. We assume there are no invalid tasks such as moving an ungraspable object across a discontinuous path (e.g., moving a large plate from the table onto the shelf). Then, based on the action assigned to the objects, the expert planner computes the optimal planning solution analytically using the \(A^{*}\) algorithm, which globally minimizes the predefined operating cost function by computing all possible planning sequences. For an ungraspable object without a direct pushing path, we assign an action cost of 3 because it requires multiple pushing actions. An infinite heuristic cost is associated with a planning sequence if the goal location is blocked by other objects, determined by FCL. The binary object selection label is 1 if it is the first in a sequence planned by \(A^{*}\) and 0 otherwise. The dataset contains 30,000 pairs of current and goal RGB-D images and labels, which are transformed into heterogeneous graphs using methods described in Sec. IV-B.

During training, we use a binary cross-entropy loss \(\mathcal{L}_{action}\) to supervise the action predictions:

\[\mathcal{L}_{action}=-(y\log(p)+(1-y)\log(1-p)). \tag{3}\]

The Huber loss \(\mathcal{L}_{object}\) for the object prediction head output \(\hat{y}\) is defined as

\[\mathcal{L}_{object}=\begin{cases}\frac{1}{2}(y-\hat{y})^{2}&\text{if}\ \ |(y-\hat{y})|<\delta\\ \delta((y-\hat{y})-\frac{1}{2}\delta)&\text{otherwise}\end{cases} \tag{4}\]

where \(\delta=1.15\). The combined loss \(\mathcal{L}\) is defined as

\[\mathcal{L}=\mathcal{L}_{object}+\lambda\mathcal{L}_{action}. \tag{5}\]

We empirically found that \(\lambda=0.65\) yields the best performance for our problem.

## V Experiments

We experiment in both simulated and real-world settings. These experiments are designed to: 1) demonstrate the effectiveness of our hierarchical system for the adversarial object rearrangement problem; 2) evaluate our HetGNN-based coordinator in various constrained environments and compare it to other baselines; and 3) show the generalizability of our approach to unstructured everyday scenarios.

**Evaluation metrics**: Following Definition 1, we define the _success rate_ as \(\frac{\#\text{ of successful rearrangement}}{\#\text{ of total rearrangement problems}}\). If a given rearrangement is not achievable (e.g., lifting a non-graspable object from the ground to the upper shelf), the experiment will be re-initialized. Each test is limited to \(2\times N\) planning steps, where \(N\) is the number of objects. A timeout is also considered a failure. We also consider the _planning cost_, which measures the number of actions taken to rearrange the objects from the start to the goal configuration. Each push costs **1** action and each pick-place costs **3** actions by Definition 2. Because pick-place only approaches could

Fig. 4: The testing objects are drawn from the YCB dataset and differ in size, color, and shape from our basic training objects (e.g., blocks, cylinders). Some objects such as bowls and cracker boxes, may not be graspable due to their orientation.
not work in our settings due to the non-graspable objects, we instead compare our method with the following four baselines:

* **Model** is a model-based approach that assumes access to ground truth IDs and mesh models. It randomly selects a target and checks if its corresponding goal location is available. If that location is occupied, it will push the occupying object to an arbitrary free space. Otherwise, it moves the object using the expert action selection algorithm described in Sec. IV-E.
* **Plan** is a variant of the expert planner in Sec. IV-E. It combines an optimal planner with a deep learning-based perception module [13]. Instead of using 3D models, this classical approach is based-on segmentation masks and plans for the entire action sequence with \(A^{*}\) algorithm that globally minimizes the cost function.
* **GNN** employs a Homogeneous Graph Neural Network instead of HetGNN for the coordinator. The network is trained with the same dataset as ours, except that the heterogeneous structure is not used. All other components are kept the same as in our approach.
* **NeRP+Push** builds upon a recent state-of-the-art object rearrangement approach [5]. It learns a k-GNN-based planner that selects a near-optimal policy and uses pick-place for unknown object rearrangement. To adapt to our test environments, we allow NeRP to heuristically push ungraspable objects when the object mask is larger than a threshold.
* **Expert** is our expert planner in Sec. IV-E whose performance is regarded as the upper bound of each scenario. It computes the optimal solution but may fail due to unexpected object dynamics and imperfect low-level actors.

### _Simulation Experiments_

The simulated test environment is in CoppeliaSim 4.0 [38] with Bullet physics engine v2.83. The scene includes a Franka Emika Panda robot arm with the original gripper, different numbers of testing objects, and various environmental constraints. A single-view RGB-D observation is taken with a simulated Kinect camera.

**Experiment scenes:** The experiments are depicted in Fig. 5. We first test in the open _Tabletop_ scenario for which the baseline methods were designed to verify if our approach is efficient in the simple environment. Each scene contains five to seven objects from Fig. 4 to demonstrate that our approach is generalizable to different numbers of objects (i.e., clutteredness). Each method is tested 51 times, and the success rate and planning cost are compiled in Table I and II respectively. Then we experiment with increasing the complexity of the environmental constraints: _Shelf_ demonstrates that our approach is able to efficiently solve multi-planar scenarios; _Bins_ is commonly seen in warehouses and introduces more partial occlusions; the additional shelves in _Pantry_ mimic a more realistic scene and show the generalizability to novel constraints, where analytical approaches often face difficulties. The experiments contain six YCB objects, and the results are compiled in Table III and IV.
goal locations are occupied. _Plan_'s open-loop planner could not resolve a collision immediately, potentially causing more failures and requiring more actions to complete the task afterward. _GNN_ learns less effectively and makes predictions that are not as accurate as ours (e.g., selecting pick-place while push is feasible). _NeRP+Push_ only pushes when the item is not graspable, since it could not efficiently coordinate different skills. The results suggest that our approach is able to generalize to different numbers of adversarial objects and is the most efficient in cluttered scenes, thanks to the HetGNN coordinator and the closed-loop design.

Constrained experiments increase environmental discontinuities and clutteredness, necessitating more accurate reasoning about the relationships among task components. The privileged information available to _Model_ helps maintain its performance, while _GNN_ becomes worse since it has no knowledge of the relations between each component. This indicates that the information learned by HetGNN is crucial to efficient planning. _Plan_ depends on accurate object masks to calculate the true trajectory cost, and _NeRP+Push_ only considers objects' center locations. Consequently, their performance suffers from the additional challenge of constrained experiments. In contrast, our HetGNN-based coordinator that employs 3D shape features generalizes better with partial observations. Overall, we achieved an average success rate of 96.73%, surpassing the best-performing baseline by 7.2%, with a planning cost of only 14.50, which is the closest to _Expert_'s result.

### _Real-robot Experiments_

Our real-world experiment consists of a Franka Emika Panda robot arm with FESTO DHAS soft fingers and an Intel RealSense D415 camera that overlooks the workspace. We test each method 11 times in three real-world scenarios: _Bins_, _Shelf_, and _Novel_. _Model_ is excluded from the baseline methods because ground truth mesh models are not available in the real world. Five adversarial objects are first randomly placed in the scene as the goal configuration and then re-initialized to the start configuration. To address the sim-to-real gap of the RGB-D sensor, we fine-tuned the object-matching module with a dataset consisting of 500 real-world images.

Fig. 6 depicts a successful rearrangement task in novel scenarios. Due to the perception challenge and more complex object dynamics in the real world, the performance of all the methods declines compared to the simulated results. However, ours drops much less thanks to the learned model that is robust to noise and occlusion. _Plan_ and _NeRP+Push_ sometimes select the wrong action and falsely store objects when the goal locations are available because of inaccurate masks and noise. Collisions with the occluded geometry also become more frequent in the real world, highlighting the importance of our closed-loop system. We summarized the experimental results in Table V and VI. Our approach achieves an average success rate of 87.88% and completes the task with 12.82 actions, indicating that it is the most efficient and generalizable to novel office objects and constraints. Our method is limited by the analytical pushing algorithm, which may rotate large objects unexpectedly and incur additional costs if they collide with other objects.

## VI Conclusion

We presented an object rearrangement system that coordinates pick-place and push in challenging scenarios with adversarial objects and environmental constraints. Our approach hierarchically employs a HetGNN coordinator and low-level 3D CNN-based actors to achieve the goal arrangement in an efficient manner. The proposed simulation-trained rearrangement system achieved an average success rate of 87.88% and a planning cost of 12.82 in real-world

\begin{table}
\begin{tabular}{c c c c c} \hline \hline  & Plan & GNN & NeRP+Push & Ours \\ \hline Shelf & 81.82 & 72.73 & **90.91** & **90.91** \\ Bins & 72.73 & 63.64 & 72.73 & **81.82** \\ Novel & 63.64 & 72.73 & 81.82 & **90.91** \\ \hline \hline \end{tabular}
\end{table} TABLE V: Success Rate (%) in Real World

\begin{table}
\begin{tabular}{c c c c c} \hline \hline  & Plan & GNN & NeRP+Push & Ours \\ \hline Shelf & 14.62 & 16.67 & 19.56 & **11.81** \\ Bins & 19.13 & 17.88 & 23.83 & **14.34** \\ Novel & 20.20 & 17.37 & 21.21 & **12.31** \\ \hline \hline \end{tabular}
\end{table} TABLE VI: Planning Cost (# actions) in Real World

Fig. 6: An example of real-world experiments in the _Novel_ scenario (11 actions). The HetGNN-based coordinator predicts the most feasible target and utilizes pick-place and push accordingly while the low-level actors execute the plan in closed-loop.
experiments with adversarial objects and environmental constraints. One avenue for future extension is to simultaneously learn the orientations of objects during placement, as we are currently focusing on arranging objects in terms of positions.
