# Adversarial Object Rearrangement in Constrained Environments with
Heterogeneous Graph Neural Networks

Xibai Lou1, Houjian Yu1, Ross Worobel2, Yang Yang2 and Changhyun Choi1
*This work was in part supported by UMII MnDRIVE Ph.D. Graduate Assistantship and MnDRIVE Initiative on Robotics, Sensors, and Advanced Manufacturing.1 The authors are with the Department of Electrical and Computer Engineering, Univ. of Minnesota, Minneapolis, USA {lou00015, yu000487<EMAIL_ADDRESS>The authors are with the Department of Computer Science and Engineering, Univ. of Minnesota, Minneapolis, USA {worob006<EMAIL_ADDRESS>
###### 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.

###### Index Terms:

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.

Figure 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”.

To address this challenge, we propose to learn from the heterogeneous task
components and exploit the distinct 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.

Figure 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.

##  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\\{\textsc{pick-place},\textsc{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$ {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,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(V,E)})$;
hence the pick-place probability
$p_{pick}(\mathcal{C},\mathcal{O}^{t},\mathcal{O}^{T})=Pr(\mathcal{S}_{a}=0|\mathcal{G(V,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.

Algorithm 1 Rearrangement in Constrained Environments

Input:  Goal Image $I_{T}$, encoder $E_{\phi}$, Coordinator $\mathcal{N}_{c}$
Output:  $o^{t}\in\mathcal{O}^{t},a\in\mathcal{A}$

1:$\mathcal{M}_{T},\mathcal{M}_{C}\leftarrow\texttt{Segmentation($I_{T}$)}$

2:$N\leftarrow\texttt{length($\mathcal{M}_{T}$)}$

3:$\mathcal{H}_{T}\leftarrow\texttt{ExtractFeature($\mathcal{M}_{T},I_{T}$)}$

4:$\mathcal{P}_{T},\mathcal{P}_{c},\mathbf{z}_{T},\mathbf{z}_{c}\leftarrow\texttt{BackProjection($\mathcal{M}_{T},\mathcal{M}_{c},I_{T}$)}$

5:$V_{T},V_{c}\leftarrow\texttt{VoxelTransformation}(\mathcal{P}_{T},\mathcal{P}_{c})$

6:$\mathbf{x}_{T},\mathbf{x}_{c}\leftarrow
E_{\phi}(V_{T},V_{c})\cup(\mathbf{z}_{T},\mathbf{z}_{c})$

7:for ${t}\in\ {0,...,T-1}$ do

8: $I_{t}\leftarrow\texttt{Observation($\mathcal{W}$)}$

9: $\mathcal{M}\leftarrow\texttt{Segmentation($I_{t}$)}$

10: $\mathcal{H}_{t}\leftarrow\texttt{ExtractFeature($\mathcal{M},I_{t}$)}$

11: $\mathbf{c}\leftarrow\texttt{Match($\mathcal{H}_{t},\mathcal{H}_{T},N$)}$

12:
$\mathcal{P}_{t},\mathbf{z}_{t}\leftarrow\texttt{BackProjection($\mathcal{M},I_{t}$)}$

13: $V_{t}\leftarrow\texttt{VoxelTransformation}(\mathcal{P}_{t})$

14: $\mathbf{x}_{t}\leftarrow E_{\phi}(V_{t})\cup\mathbf{z}_{t}$

15:
$\mathcal{G(V,E)}\leftarrow\texttt{BuildGraph($\mathbf{x}_{t},\mathbf{x}_{T},\mathbf{x}_{c},\mathbf{c}$)}$

16: $p_{a},p_{o}\leftarrow\texttt{$\mathcal{N}_{c}$.Feedforward}(\mathcal{G})$

17:
$o^{t}\leftarrow\operatorname*{argmax}_{o^{t}\in\mathcal{O}^{t}}p_{o}(\mathcal{C},\mathcal{O}^{t},\mathcal{O}^{T})$

18: if $p_{a}>0.5$ then

19: $a\leftarrow\texttt{Push}(o^{t})$

20: else

21: $a\leftarrow\texttt{Pick-place}(o^{t})$

22: $\texttt{Actors}(a)$

###  IV-A 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, 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$.

###  IV-B 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}$.

###  IV-C HetGNN-based Coordinator

Figure 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}^{\prime}_{T},\mathbf{x}^{\prime}_{t},\mathbf{x}^{\prime}_{c}$.

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

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

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

$\displaystyle\alpha_{i,j}=\frac{\exp\left(\mathrm{\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(\mathrm{\sigma}\left(\mathbf{a}^{\top}[\mathbf{\Theta}\mathbf{x}_{i}\,\|\,\mathbf{\Theta}\mathbf{x}_{k}]\right)\right)}$
(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(V,E)}$, the network aggregates node embeddings by using the
message passing functions corresponding to 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.

###  IV-D 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)111Note that the acronym
GSP refers to the 3D CNN grasping module in [14], defined here for a concise
reference., 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.

###  IV-E Expert Planner and Training

Figure 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.

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^{\ast}$
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^{\ast}$ 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:

$\displaystyle\mathcal{L}_{action}=-{(y\log(p)+(1-y)\log(1-p))}.$ (3)

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

$\displaystyle\mathcal{L}_{object}=\left\\{\begin{matrix}\frac{1}{2}(y-\hat{y})^{2}&\text{if}\leavevmode\nobreak\
\left|(y-\hat{y})\right|<\delta\\\
\delta((y-\hat{y})-\frac{1}{2}\delta)&\text{otherwise}\end{matrix}\right.$ (4)

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

$\displaystyle\mathcal{L}=\mathcal{L}_{object}+\lambda\mathcal{L}_{action}.$
(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 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^{\ast}$ 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.

Figure 5: The simulated experiments include various constraints that increase
clutteredness and planning difficulty. Our approach achieves comparable
results to the expert planner and outperforms all the baseline methods. Table
I: Success Rate (%) on Tabletop

| Model | Plan | GNN | NeRP+Push | Ours | Expert
---|---|---|---|---|---|---
5-object | 94.12 | 98.04 | 88.24 | 94.12 | 98.04 | 100.00
6-object | 90.02 | 92.16 | 90.20 | 98.04 | 98.04 | 100.00
7-object | 84.27 | 88.24 | 82.35 | 90.20 | 94.12 | 100.00

Table II: Planning Cost (# actions) on Tabletop

| Model | Plan | GNN | NeRP+Push | Ours | Expert
---|---|---|---|---|---|---
5-object | 12.33 | 10.12 | 13.49 | 19.41 | 9.67 | 8.42
6-object | 15.42 | 15.47 | 16.69 | 22.13 | 11.91 | 10.12
7-object | 18.96 | 18.41 | 26.58 | 24.27 | 15.60 | 13.54

Table III: Success Rate (%) in Constraints

| Model | Plan | GNN | NeRP+Push | Ours | Expert
---|---|---|---|---|---|---
Shelf | 88.24 | 96.08 | 82.36 | 98.04 | 98.04 | 100.00
Bins | 82.35 | 78.43 | 72.55 | 84.31 | 98.04 | 100.00
Pantry | 84.31 | 82.35 | 72.55 | 88.24 | 94.12 | 100.00

Table IV: Planning Cost (# actions) in Constraints

| Model | Plan | GNN | NeRP+Push | Ours | Expert
---|---|---|---|---|---|---
Shelf | 16.64 | 16.12 | 17.58 | 21.56 | 14.19 | 13.82
Bins | 20.56 | 18.08 | 18.91 | 24.83 | 15.64 | 14.21
Pantry | 18.16 | 17.45 | 19.83 | 22.21 | 14.68 | 13.65

Figure 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.

###  V-A 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 II 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 IV
and IV.

Result Analysis: In the Tabletop experiments, our approach achieved a 94.12%
success rate with a 15.60 planning cost in the most cluttered 7-object
scenario, surpassing all baseline methods. The major challenge is to
understand the relations between current and goal objects. Although Model has
access to all the mesh models and the expert action selection module, it
performs poorly owing to the uninformed planner, which frequently proposes
targets whose 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.

###  V-B 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 VI 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.

Table V: Success Rate (%) in Real World

| Plan | GNN | NeRP+Push | Ours
---|---|---|---|---
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

Table VI: Planning Cost (# actions) in Real World

| Plan | GNN | NeRP+Push | Ours
---|---|---|---|---
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

##  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
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.

## References

  * [1] C. Garrett, R. Chitnis, R. Holladay, B. Kim, T. Silver, L. Kaelbling, and T. Lozano-Pérez, “Integrated task and motion planning,” _Annual Review of Control, Robotics, and Autonomous Systems_ , vol. 4, 05 2021.
  * [2] L. P. Kaelbling and T. Lozano-Pérez, “Hierarchical task and motion planning in the now,” in _2011 IEEE International Conference on Robotics and Automation_ , 2011, pp. 1470–1477.
  * [3] R. Wang, K. Gao, D. Nakhimovich, J. Yu, and K. E. Bekris, “Uniform object rearrangement: From complete monotone primitives to efficient non-monotone informed search,” in _2021 IEEE International Conference on Robotics and Automation (ICRA)_ , 2021, pp. 6621–6627.
  * [4] K. Gao, D. Lau, B. Huang, K. E. Bekris, and J. Yu, “Fast high-quality tabletop rearrangement in bounded workspace,” in _2022 International Conference on Robotics and Automation (ICRA)_. IEEE Press, 2022, p. 1961–1967.
  * [5] A. Qureshi, A. Mousavian, C. Paxton, M. Yip, and D. Fox, “Nerp: Neural rearrangement planning for unknown objects,” in _Proceedings of Robotics: Science and Systems_ , 2021.
  * [6] A. Curtis, X. Fang, L. P. Kaelbling, T. Lozano-Pérez, and C. R. Garrett, “Long-horizon manipulation of unknown objects via task and motion planning with estimated affordances,” in _2022 International Conference on Robotics and Automation (ICRA)_ , 2022, pp. 1940–1946.
  * [7] Z. Pan and K. Hauser, “Decision making in joint push-grasp action space for large-scale object sorting,” in _2021 IEEE International Conference on Robotics and Automation (ICRA)_. IEEE, 2021, pp. 6199–6205.
  * [8] B. Tang and G. S. Sukhatme, “Selective object rearrangement in clutter,” in _6th Annual Conference on Robot Learning_ , 2022.
  * [9] R. Wang, Y. Miao, and K. E. Bekris, “Efficient and high-quality prehensile rearrangement in cluttered and confined spaces,” in _IEEE International Conference on Robotics and Automation (ICRA)_ , 2022.
  * [10] C. Zhang, D. Song, C. Huang, A. Swami, and N. V. Chawla, “Heterogeneous graph neural network,” ser. KDD ’19. New York, NY, USA: Association for Computing Machinery, 2019, p. 793–803.
  * [11] D. Batra, A. X. Chang, S. Chernova, A. J. Davison, J. Deng, V. Koltun, S. Levine, J. Malik, I. Mordatch, R. Mottaghi, _et al._ , “Rearrangement: A challenge for embodied ai,” _arXiv preprint arXiv:2011.01975_ , 2020.
  * [12] C. Xie, Y. Xiang, A. Mousavian, and D. Fox, “The best of both modes: Separately leveraging rgb and depth for unseen object instance segmentation,” in _Conference on Robot Learning (CoRL)_ , 2019.
  * [13] H. Yu and C. Choi, “Self-supervised interactive object segmentation through a singulation-and-grasping approach,” in _Computer Vision–ECCV 2022: 17th European Conference, Tel Aviv, Israel, October 23–27, 2022, Proceedings, Part XXXIX_ , ser. Lecture Notes in Computer Science, vol. 13699\. Springer, 2022, pp. 621–637.
  * [14] X. Lou, Y. Yang, and C. Choi, “Learning to generate 6-dof grasp poses with reachability awareness,” in _2020 IEEE International Conference on Robotics and Automation (ICRA)_. IEEE, 2020, pp. 1532–1538.
  * [15] A. Murali, W. Liu, K. Marino, S. Chernova, and A. Gupta, “Same object, different grasps: Data and semantic knowledge for task-oriented grasping,” in _Conference on Robot Learning_ , 2020.
  * [16] M. Sundermeyer, A. Mousavian, R. Triebel, and D. Fox, “Contact-graspnet: Efficient 6-dof grasp generation in cluttered scenes,” in _2021 IEEE International Conference on Robotics and Automation (ICRA)_ , 2021, pp. 13 438–13 444.
  * [17] A. Goyal, A. Mousavian, C. Paxton, Y.-W. Chao, B. Okorn, J. Deng, and D. Fox, “Ifor: Iterative flow minimization for robotic object rearrangement,” in _Proceedings of the Conference on Computer Vision and Pattern Recognition (CVPR)_ , June 2022.
  * [18] C. Paxton, C. Xie, T. Hermans, and D. Fox, “Predicting stable configurations for semantic placement of novel objects,” in _Proceedings of the 5th Conference on Robot Learning_ , ser. Proceedings of Machine Learning Research, A. Faust, D. Hsu, and G. Neumann, Eds., vol. 164. PMLR, 08–11 Nov 2022, pp. 806–815.
  * [19] W. Liu, C. Paxton, T. Hermans, and D. Fox, “Structformer: Learning spatial structure for language-guided semantic rearrangement of novel objects,” in _2022 International Conference on Robotics and Automation (ICRA)_ , 2022, pp. 6322–6329.
  * [20] A. Zeng, S. Song, S. Welker, J. Lee, A. Rodriguez, and T. Funkhouser, “Learning synergies between pushing and grasping with self-supervised deep reinforcement learning,” in _IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_ , 2018.
  * [21] A. Zeng, P. Florence, J. Tompson, S. Welker, J. Chien, M. Attarian, T. Armstrong, I. Krasin, D. Duong, V. Sindhwani, and J. Lee, “Transporter networks: Rearranging the visual world for robotic manipulation,” _Conference on Robot Learning (CoRL)_ , 2020.
  * [22] J. E. King, M. Cognetti, and S. S. Srinivasa, “Rearrangement planning using object-centric and robot-centric action spaces,” in _2016 IEEE International Conference on Robotics and Automation (ICRA)_ , 2016, pp. 3940–3947.
  * [23] Y. Labbe, S. Zagoruyko, I. Kalevatykh, I. Laptev, J. Carpentier, M. Aubry, and J. Sivic, “Monte-carlo tree search for efficient visually guided rearrangement planning,” _IEEE Robotics and Automation Letters_ , 2020\.
  * [24] D. Hafner, T. Lillicrap, I. Fischer, R. Villegas, D. Ha, H. Lee, and J. Davidson, “Learning latent dynamics for planning from pixels,” in _Proceedings of the 36th International Conference on Machine Learning_ , ser. Proceedings of Machine Learning Research, K. Chaudhuri and R. Salakhutdinov, Eds., vol. 97. PMLR, 09–15 Jun 2019, pp. 2555–2565.
  * [25] C. Paxton, Y. Barnoy, K. Katyal, R. Arora, and G. D. Hager, “Visual robot task planning,” in _2019 International Conference on Robotics and Automation (ICRA)_ , 2019, pp. 8832–8838.
  * [26] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, L. u. Kaiser, and I. Polosukhin, “Attention is all you need,” in _Advances in Neural Information Processing Systems_ , I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, Eds., vol. 30. Curran Associates, Inc., 2017\.
  * [27] T. N. Kipf and M. Welling, “Semi-Supervised Classification with Graph Convolutional Networks,” in _Proceedings of the 5th International Conference on Learning Representations_ , ser. ICLR ’17, 2017.
  * [28] A. Sanchez-Gonzalez, J. Godwin, T. Pfaff, R. Ying, J. Leskovec, and P. Battaglia, “Learning to simulate complex physics with graph networks,” in _International Conference on Machine Learning_. PMLR, 2020, pp. 8459–8468.
  * [29] M. Wilson and T. Hermans, “Learning to manipulate object collections using grounded state representations,” in _Proceedings of the Conference on Robot Learning_ , ser. Proceedings of Machine Learning Research, L. P. Kaelbling, D. Kragic, and K. Sugiura, Eds., vol. 100. PMLR, 30 Oct–01 Nov 2020, pp. 490–502.
  * [30] S. Hun Cheong, B. Y. Cho, J. Lee, C. Kim, and C. Nam, “Where to relocate?: Object rearrangement inside cluttered and confined environments for robotic manipulation,” in _2020 IEEE International Conference on Robotics and Automation (ICRA)_ , 2020, pp. 7791–7797.
  * [31] G. Koch, R. Zemel, and R. Salakhutdinov, “Siamese neural networks for one-shot image recognition,” in _ICML deep learning workshop_ , vol. 2. Lille, 2015.
  * [32] M. Danielczuk, A. Kurenkov, A. Balakrishna, M. Matl, D. Wang, R. Martín-Martín, A. Garg, S. Savarese, and K. Goldberg, “Mechanical search: Multi-step retrieval of a target object occluded by clutter,” in _Proc. IEEE Int. Conf. Robotics and Automation (ICRA)_ , 2019.
  * [33] X. Lou, Y. Yang, and C. Choi, “Collision-aware target-driven object grasping in constrained environments,” in _2021 IEEE International Conference on Robotics and Automation (ICRA)_. IEEE, 2021\.
  * [34] J. Zhou, G. Cui, S. Hu, Z. Zhang, C. Yang, Z. Liu, L. Wang, C. Li, and M. Sun, “Graph neural networks: A review of methods and applications,” _AI Open_ , vol. 1, pp. 57–81, 2020.
  * [35] P. Veličković, G. Cucurull, A. Casanova, A. Romero, P. Liò, and Y. Bengio, “Graph Attention Networks,” _International Conference on Learning Representations_ , 2018.
  * [36] X. Lou, Y. Yang, and C. Choi, “Learning object relations with graph neural networks for target-driven grasping in dense clutter,” in _2022 International Conference on Robotics and Automation (ICRA)_ , 2022, pp. 742–748.
  * [37] J. Pan, S. Chitta, and D. Manocha, “Fcl: A general purpose library for collision and proximity queries,” in _2012 IEEE International Conference on Robotics and Automation_ , 2012, pp. 3859–3866.
  * [38] E. Rohmer, S. P. Singh, and M. Freese, “V-rep: A versatile and scalable robot simulation framework,” in _2013 IEEE/RSJ International Conference on Intelligent Robots and Systems_. IEEE, 2013, pp. 1321–1326.