# Wildfire Forecasting with Satellite Images and Deep Generative Model

Thai Nam Hoang1, 2, Sang T. Truong3, Chris Schmidt2

###### Abstract

Wildfire forecasting has been one of the most critical tasks that humanities
want to thrive. It plays a vital role in protecting human life. Wildfire
prediction, on the other hand, is difficult because of its stochastic and
chaotic properties. We tackled the problem by interpreting a series of
wildfire images as a video and used it to anticipate how the fire would behave
in the future. However, creating video prediction models that account for the
inherent uncertainty of the future is challenging. The bulk of published
attempts is based on stochastic image-autoregressive recurrent networks, which
raises various performance and application difficulties, such as computational
cost and limited efficiency on massive datasets. Another possibility is to use
entirely latent temporal models that combine frame synthesis and temporal
dynamics. However, due to design and training issues, no such model for
stochastic video prediction has yet been proposed in the literature. This
paper addresses these issues by introducing a novel stochastic temporal model
whose dynamics are driven in a latent space. It naturally predicts video
dynamics by allowing our lighter, more interpretable latent model to beat
previous state-of-the-art approaches on the GOES-16 dataset. Results will be
compared towards various benchmarking models.

## Introduction

Weather forecasting has been one of the essential tasks of humankind. Since
1975, the US Government has launched the Geostationary Operational
Environmental Satellite (GOES) to produce data that can enhance weather and
climate models, thus allowing for more precise and quick weather forecasting
and a better knowledge of long-term climate (NASA 2015; Dunbar and Garner
2021). Using informative GOES data can help with wildfire prediction and
detection, as lately, more and more wildfires are happening. The increase in
severity, frequency, and duration of wildfires brought on by anthropogenic
climate change and rising global temperatures has resulted in the emission of
significant amounts of greenhouse gases, the destruction of forests and their
related habitats, and damage to infrastructure and property (Marlon et al.
2012; Abatzoglou and Williams 2016; Vilà-Vilardell et al. 2020).

Previous projects on fire detection have been done. However, most of them
tried to tackle segmentation (Khyrashchev and Larionov 2020; Pereira et al.
2021; Zhang et al. 2021). However, these methods may not serve the whole idea
of wildfire prediction and prevention, as they tend to recognize the fire once
it happens already, and the larger it grows, the easier they can segment.
Additionally, they only tried to use traditional rasterized satellite images,
where images are patched into traditional RGB 3-channel. Therefore they could
not capture very early factors of small wildfire.

An advantage of GOES compared to other satellites is that GOES uses an
Advanced Baseline Imager (ABI), which takes the image of the Earth with 16
spectral bands (two visible channels, four near-infrared channels, and ten
infrared channels) with a fast scan time of 12 slices per hour and higher
resolution of 0.5-2km (Schmit et al. 2017; NOAA 2017b). We can utilize the
robustness of ABI images to create a temporal-like dataset that serves as
baseline data for prediction.

For the sake of synthesizing images, generating adversarial networks (GANs)
can be taken into account. The network introduces a generator and
discriminator for unsupervised adversarial training, which indirectly “learns”
the dataset through a minimax game (Goodfellow et al. 2014). The discriminator
distinguishes between genuine pictures from a training set and synthetic phony
ones created by the generator. Starting from this idea, we can evolve to
generate video frames instead of a single image. This idea can be classified
as stochastic video prediction. However, it is a daunting task as most
approaches are usually based on image-autoregressive models (Babaeizadeh et
al. 2017; Denton and Fergus 2018; Weissenborn, Täckström, and Uszkoreit 2019),
which was a pixel-wise tackle and built around Recurrent Neural Networks
(RNNs), where each generated frame is fed back to the model to produce the
next frame. However, the performance of this approach relies heavily on the
capability of its encoders and decoders, as each generated frame has to be re-
encoded in a latent space. Such techniques may have a negative impact on
performance and have limited application, especially when dealing with massive
amounts of data (Gregor et al. 2018; Rubanova, Chen, and Duvenaud 2019).

Another technique is to separate the dynamic of the state representations from
the produced frames, which are decoded separately from the latent space. This
is computationally interesting when combined with a low-dimensional latent
space and eliminates the relationship mentioned above between frame generation
and temporal dynamics. Furthermore, such models are more interpretable than
autoregressive models and may be used to create a complete representation of a
system’s state, for example, in reinforcement learning applications (Gregor et
al. 2018). However, these State-Space Models (SSMs) are more challenging to
train since they need non-trivial inference systems (Krishnan, Shalit, and
Sontag 2016) and careful dynamic model construction (Karl et al. 2016). As a
result, most effective SSMs are only assessed on minor or contrived toy tasks.

In this paper, we present a novel stochastic dynamic model for video
prediction that successfully harnesses the structural and computational
advantages of SSMs operating on low-dimensional latent spaces. Its dynamic
component governs the system’s temporal evolution through residual updates of
the latent state, which are conditioned on learned stochastic variables. This
approach enables us to execute an efficient training strategy and analyze
complex high-dimensional data such as movies in an interpretable way. This
residual principle is related to recent breakthroughs in the relationship
between residual networks and Ordinary Differential Equations (ODEs). As
illustrated in our research, this interpretation offers additional
possibilities, such as creating videos at varied frame rates. As evidenced by
comparisons with competing baselines on relevant benchmarks, the proposed
technique outperforms existing state-of-the-art models on the task of
stochastic video prediction.

## Related Works

Video synthesis encompasses a wide range of tasks, from super-resolution
(Caballero et al. 2016), interpolation between distant frames (Jiang et al.
2017), generation (Tulyakov et al. 2017), video-to-video translation (Wang et
al. 2018), and conditioning video prediction, which is the subject of this
study.

### Deterministic models

Beginning with RNN-based sequence generating models (Graves 2013), a variety
of video prediction algorithms based on LSTMs (Long Short-Term Memory networks
(Hochreiter and Schmidhuber 1997)) and its convoluted variation of ConvLSTMs
(Shi et al. 2015) were developed (Srivastava, Mansimov, and Salakhutdinov
2015; De Brabandere et al. 2016; Wichers et al. 2018; Jin et al. 2020).
Indeed, computer vision algorithms are frequently aimed at high-dimensional
video sequences and employ domain-specific approaches such as pixel-level
transformations, and optical flow (Walker, Gupta, and Hebert 2015; Walker et
al. 2016; Vondrick and Torralba 2017; Lu, Hirsch, and Scholkopf 2017; Fan,
Zhu, and Yang 2019) to help in the generation of high-quality predicting
outputs. However, such algorithms are deterministic, which limits their
efficacy by failing to produce high-quality long-term video frames
(Babaeizadeh et al. 2017; Denton and Fergus 2018). Another approach is to
apply adversarial losses (Goodfellow et al. 2014) to sharpen the resulting
frames (Vondrick and Torralba 2017; Lu, Hirsch, and Scholkopf 2017; Wu et al.
2020). Adversarial losses, on the other hand, are famously challenging to
train, and as a result, mode collapse develops, restricting generational
diversity.

### Stochastic and image-autoregressive models

Other methods manipulate pixel-level autoregressive generation and concentrate
on precise probability maximization (Oord et al. 2016; Kalchbrenner et al.
2016; Weissenborn, Täckström, and Uszkoreit 2020). Flow normalization has also
been studied using invertible transformations between the observation and
latent spaces (Kingma and Dhariwal 2018; Kumar et al. 2019). However, they
necessitate the careful construction of sophisticated temporal production
systems that manage high-dimensional data, resulting in exorbitant temporal
generation costs. For the inference of low-dimensional latent state variables,
Variational Auto-encoders are utilized in more efficient continuous models
(VAEs (Kingma and Welling 2013)).Stochastic variables were integrated into
ConvLSTM in (Babaeizadeh et al. 2017). In order to sample random variables
that are supplied to a predictor LSTM, both (He et al. 2018) and (Denton and
Fergus 2018) utilized a prior LSTM conditioned on previously produced frames.
Finally, (Lee et al. 2018) merged the ConvLSTM with learned prior, sharpening
the resulting videos with an adversarial loss. However, all of these
approaches are image-autoregressive in that they feed their predictions back
into the latent space, connecting the frame synthesis and temporal models
together and increasing their computing cost. (Minderer et al. 2019) offered
an autoregressive VRNN model based on learned image key points rather than raw
frames, which is similar to our work. It is unknown to what degree this
adjustment will alleviate the issues mentioned above. Instead, we address
these concerns by focusing on video dynamics and proposing a state-space model
that operates on a limited latent space.

### State-space model

Numerous latent state-space models, often trained using deep variational
inference, have been suggested for sequence modelization (Bayer and Osendorfer
2014; Fraccaro et al. 2016; Hafner et al. 2018). These initiatives, which
employ locally linear or RNN-based dynamics, are intended for low-dimensional
data since learning such models on complex data is difficult or concentrates
on control or planning tasks. On the other hand, the utterly latent technique
is the first to successfully apply to complex high-dimensional data such as
videos due to a temporal model based on residual updates of its latent state.
It is part of a recent development that connects differential equations with
neural networks (Lu et al. 2017; Long et al. 2017), leading to the integration
of ODEs, which are seen as continuous residual networks (He et al. 2016). On
the other hand, follow-ups and similar research are confined to low-
dimensional data, prone to overfitting, and unable to manage stochasticity
within a sequence. Another line of research examines stochastic differential
equations using neural networks (Ryder et al. 2018; De Brouwer et al. 2019),
but is confined to continuous Brownian noise, whereas video generation also
involves modeling of punctual stochastic events.

## Methods

We are concerned with the challenge of stochastic video prediction, attempting
to forecast future frames from a video given the initial conditioning frames.

### Latent Residual Dynamic Model

Let $x_{0:T}=\\{x_{0},x_{1},\ldots,x_{T-1}\\}$ be a sequence of $T$ video
frames, where each state $x_{t}\in{\mathbb{R}}^{b\times m\times n}$ is a
satellite image, where $b=10$ is the number of band (”channel”), and $m=1500$
and $n=2500$ is the maximum image size. We want generate $x_{T:T+h}$, where
$h$ is the forecasting horizon. One way to achieve this goal is to use an
parameterized autoregressive model $f_{\theta}$ that maps one state to
another: $x_{t+1}=f_{\theta}(x_{t})$. We introduce latent variables $y$ that a
dynamic temporal model drives to achieve this. Each frame $x_{t}$ is then
generated from the corresponding latent state $y_{t}$ only, making the
dynamics independent from the previously generated frames.

Based on (Franceschi et al. 2020), we suggest using a stochastic residual
network to describe the transition function of the latent dynamic of $y$.
State $y_{t+1}$ is selected to be deterministically dependent on the preceding
state $y_{t}$ and conditionally dependent on an auxiliary random variable
$z_{t+1}$. These auxiliary variables represent the video dynamics’
unpredictability. They have a learned factorized Gaussian prior that is solely
affected by the initial state. The model is depicted in Figure (1) and defined
as follows:

$\begin{cases}y_{1}\sim\mathcal{N}(0,I),\\\
z_{t+1}\sim\mathcal{N}(\mu_{\theta}(y_{t}),\sigma_{\theta}(y_{t})I),\\\
y_{t+1}=y_{t}+f_{\theta}(y_{t},z_{t+1}),\\\
x_{t}\sim\mathcal{G}(g_{\theta}(y_{t}))\end{cases}$ (1)

where $\mu_{\theta},\sigma_{\theta},f_{\theta},g_{\theta}$ are neural nets,
and $\mathcal{G}(g_{\theta}(y_{t}))$ is probability distribution parameterized
by $g_{\theta}(y_{t})$. Note that $y_{1}$ is assumed to have a standard
Gaussian prior and, in our VAE setting, will be inferred from conditioning
frames for the prediction.

$x_{0}$$x_{1}$$x_{2}$$x_{3}$$y_{0}$$z_{1}$$y_{1}$$z_{2}$$y_{2}$$z_{3}$$y_{3}$
Figure 1: Generative model $p$
$x_{0}$$x_{1}$$x_{2}$$x_{3}$$y_{0}$$z_{1}$$y_{1}$$z_{2}$$y_{2}$$z_{3}$$y_{3}$$x_{0}$$z_{1}$$y_{0}$$y_{1}$$y_{2}$$z_{2}$$y_{3}$$z_{3}$$x_{3}$$x_{1}$$x_{2}$
Figure 2: Inference model $q$

The residual update rule is based on the Euler differentiation technique for
differential equations. The state of the system $y_{t}$ is updated by its
first-order movement, i.e, the residual $f_{\theta}(y_{t},z_{t+1})$. +1). This
fundamental idea makes our temporal model lighter and more interpretable than
a normal RNN. Equation (1), on the other hand, differs from a discretized ODE
because of the introduction of the stochastic discrete-time variable $z$.
Nonetheless, we recommend that the Euler step size $\Delta t$ always be less
than $1$ to get the temporal model closer to continuous dynamics. With
$\frac{1}{\Delta t}\in{\mathbb{N}}$ to synchronize the step size with the
video frame rate, the updated dynamics are as follows:

$y_{t+\Delta t}=y_{t}+\Delta{t}\cdot f_{\theta}(y_{t},z_{\lfloor t\rfloor+1})$
(2)

The auxiliary variable $z_{t}$ is held constant between two integer time steps
in the formulation. It should be noted that during training or testing, a
different $\Delta t$ might be utilized. Because each intermediate latent state
may be decoded in the observation space, our model can generate videos at any
frame rate. This capacity allows us to assess the learned dynamic’s quality
while challenging its ODE inspiration by evaluating its generalization to the
continuous limit. For the rest of this section, we consider that $\Delta t=1$;
one can generalize to a smaller $\Delta t$ is straightforward as Figure (1)
remains unchanged.

### Content Variable

Some video sequence components, such as the terrain, can be static or vary
very slightly, such as the moving clouds. They may not affect the dynamics;
thus, we model them separately, as (Denton and Birodkar 2017; Yingzhen and
Mandt 2018) have done. We calculate a content variable $w$ that remains
constant throughout the generation process and is passed into the frame
generator along with $y_{t}$. It allows the dynamical element of the model to
concentrate just on movement, making it lighter and more stable. Furthermore,
it enables us to use architectural developments in neural networks, such as
skip connections (Ronneberger, Fischer, and Brox 2015), to generate more
realistic frames.

This content variable is a deterministic function $c_{\psi}$ of a fixed number
$k<T$ of frames $x_{c}^{(k)}=(x_{i_{0}},x_{i_{2}},\ldots,x_{i_{k}})$:

$\begin{cases}w=c_{\psi}(x_{c}^{(k)})=c_{\psi}(x_{i_{0}},x_{i_{2}},\ldots,x_{i_{k}})\\\
x_{t}\sim\mathcal{G}(g_{\theta}(y_{t}))\end{cases}$ (3)

During testing, $x_{c}^{(k)}$ are the last $k$ conditioning frames.

In contrast to the dynamic variables $y$ and $z$, this content variable has no
probabilistic prior. As a result, the information it carries is only
structurally confined rather than in the loss function. To avoid leaking
temporal information in $w$, we propose sampling these k frames evenly inside
$x_{0:T}$ during training. We also build $c_{\psi}$ as a permutation invariant
function (Zaheer et al. 2017) composed of an MLP fed with the sum of each
frame representation, as shown in (Santoro et al. 2017).

Because of the absence of prior and architectural limitations, $w$ can contain
as much non-temporal information as feasible while excluding dynamic
information. On the other hand, $y$ and $z$ should only include temporal
information that $w$ cannot capture owing to their high standard Gaussian
priors.

This content variable may be deleted from our model, resulting in a more
traditional deep state-space model.

### Variational Inference and Architecture

Following the generative model depicted in Figure (1), the conditional join
probability of the full model, given a content variable $w$, can be written
as:

$\begin{split}&p(x_{0:T},z_{1:T},y_{0:T}|w)\\\
=\;\;&p(y_{0})\prod_{t=1}^{T}p(z_{t},y_{t}|y_{t-1})\prod_{t=0}^{T}p(x_{t}|y_{t},w)\end{split}$
(4)

with

$p(z_{t},y_{t}|y_{t-1})=p(z_{t}|y_{t-1})p(y_{t}|y_{t-1},z_{t})$ (5)

According to Equation (1),
$p(y_{t}|y_{t-1},z_{t})=\delta(y_{t}-y_{t-1}-f_{\theta}(y_{t-1},z_{t}))$,
where $\delta$ is the Dirac delta function centered at $0$. Hence, in order to
optimize the likelihood of the observed videos $p(x_{0:T}|w)$, we need to
infer latent variables $y_{0}$ and $z_{1:T}$. This can be done by deep
variational inference using the inference model parameterized by $\phi$ and
shown in Figure (2), which comes down to considering a variational
distribution $q_{Z,Y}$ defined and factorized as follows:

$\begin{split}&q_{Z,Y}\triangleq q(z_{1:T},y_{0:T}|x_{0:T},w)\\\
=\;\;&q(y_{0}|x_{0:k})\prod_{t=1}^{T}q(z_{t}|x_{0:t})q(y_{t}|y_{t-1},z_{t})\\\
=\;\;&q(y_{0}|x_{0:k})\prod_{t=1}^{T}q(z_{t}|x_{0:t})p(y_{t}|y_{t-1},z_{t})\end{split}$
(6)

where $q(y_{t}|y_{t-1},z_{t})=p(y_{t}|y_{t-1},z_{t})$ begin the aforementioned
Dirac delta function. This yields the following evidence lower bound (ELBO):

$\begin{split}&\log p(x_{0:T}|w)\geq\mathcal{L}(x_{0:T};w,\theta,\phi)\\\
\triangleq\;\;&-D_{\text{KL}}[q(y_{0}|x_{0:k})\parallel p(y_{0})]\\\
&+{\mathbb{E}}_{(\tilde{z}_{1:T},\tilde{y}_{0:T})\sim
q_{Z,Y}}\bigg{[}\sum_{t=0}^{T}\log p(x_{t}|\tilde{y}_{t},w)\\\
&-\sum_{t=1}^{T}D_{\text{KL}}[q(z_{t}|x_{0:t})\parallel
p(z_{t}|\tilde{y}_{t-1}]\bigg{]}\end{split}$ (7)

where $D_{\text{KL}}$ denotes the Kullback-Leibler (KL) divergence.

The sum of KL divergence expectations implies considering the full past
sequence of inferred states for each time step due to the dependence on
conditionally deterministic variable $y_{1:T}$. However, optimizing
$\mathcal{L}(x_{0:T};w,\theta,\psi)$ with respect to model parameter $\theta$
and variational parameters $\phi$ can be done efficiently by sampling a single
full sequence of states from $q_{Z,Y}$ per example, and computing gradients by
backpropagation (Rumelhart, Hinton, and Williams 1986), trough all inferred
variables, using reparameterization trick (Kingma and Welling 2013). We
classically choose $q(y_{0}|x_{0:k})$ and $q(z_{t}|x_{0:t})$ to be factorized
Gaussian so that all KL divergences can be computed analytically.

We include an $L_{2}$ regularization term on residual $f_{\theta}$ applied to
$y$, which stabilizes the temporal dynamics of the residual network, as noted
by (Behrmann et al. 2019; de Bézenac, Ayed, and Gallinari 2019; Rousseau,
Drumetz, and Fablet 2019). Given a set of videos $\mathcal{X}$, the complete
optimization problem, where $\mathcal{L}$ is defined as in Equation (7), is
then given as:

$\begin{split}\arg\max_{\theta,\phi,\psi}&\sum_{x\in\mathcal{X}}\bigg{[}{\mathbb{E}}_{x_{c}^{(k)}}\mathcal{L}(x_{0:T};c_{\psi}(x_{c}^{(k)}),\theta,\phi)\\\
&-\lambda{\mathbb{E}}_{(\tilde{z}_{1:T},\tilde{y}_{0:T})\sim
q_{Z,Y}}\sum_{t=1}^{T}\parallel
f_{\theta}(y_{t-1,z_{t}})\parallel_{2}\bigg{]}\end{split}$ (8)

The first latent variables are inferred with the conditioning framed and are
then predicted with the dynamic model. In contrast, each frame of the input
sequence is considered for inference during training, which is done as
follows. Firstly, each frame $x_{t}$ is independently encoded into a vector-
valued representation $\tilde{x}_{t}$, with $\tilde{x}_{t}=h_{\psi}(x_{t})$.
$y_{0}$ is then inferred using an MLP on the first $k$ encoded frames
$\tilde{x}_{0:k}$. Each $z_{t}$ is inferred in a feed-forward fashion with an
LSTM on the encoded frames. Inferring $z$ this way experimentally performs
better than, e.g., inferring them from the whole sequence $x_{0:T}$; we
hypothesize that this follows from the fact that this filtering scheme is
closer to the prediction setting, where the future is not available.

## Experiments

### Training

In this part, we qualitatively investigate the dynamics and latent space
learned by our model.

The stochastic nature and originality of the video prediction task make it
challenging to evaluate ordinarily (Lee et al. 2018): because the task is
stochastic, comparing the ground truth and a predicted video is insufficient.
We, therefore, follow the standard strategy (Denton and Fergus 2018; Lee et
al. 2018), which consists of sampling a specific number (here, 100 samples) of
probable futures from the tested model and reporting the highest performing
sample against the genuine video for each test sequence. We show this
disparity for two generally used metrics that are computed frame-by-frame and
averaged over time: Peak Signal-to-Noise Ratio (PSNR, _higher is better_) and
Structured Similarity (SSIM, _higher is better_) (Horé and Ziou 2010). PSNR
penalizes inaccuracies in projected dynamics since it is a pixel-wise
measurement derived from $L2$ distance, but it may also favor fuzzy
predictions. To avoid this problem, SSIM compares local frame patches,
although this results in some dynamics information being lost. We consider
these two measures complementary since they capture distinct sizes and
modalities.

We present experimental results on the GOES data that we briefly present in
the following section. We also compare our model against SVG (Denton and
Fergus 2018) and StructVRNN (Minderer et al. 2019). SVG has the most similar
training and architecture among the models. To do fair comparisons using this
technique, we employ the same neural architecture as SVG for our encoders and
decoders. Unless otherwise indicated, our model is evaluated with the same
$\Delta t$ as in training, as shown in Equation (2).

### Dataset

We used GOES-16 CONUS (ABI-L1b-RadC) infrared ABI spectral bands (band 7 - 16)
(NASA 2017), specifically at night from 22:00:00 to 5:00:00 CST (UTC-5) or
5:00:00 to 12:00:00 UTC. The dataset can be pulled directly from AWS s3 (AWS
2022). We set the data from day 80 to day 135 of the year 2022, which is 56
days or eight weeks. For each band, there will be a total of 4704 slices.

### Preprocessing

Initially, each slice will be $1500\times 2500$. Since a single slice sizes
about 3-4Mb, we decided to crop to $256\times 256$ to, first of all, cut down
the size and, therefore, speed up the calculation. Moreover, doing so will
center our focus on the Mid and South regions of the US, where wildfires
usually happen during spring and summer. Each pixel represents the value of
radiance of brightness in each band. We first have to convert the other band’s
radiance temperature into band 7’s radiance temperature. We first calculate
its brightness temperature by applying the Planck function, and the spectral
bandpass correction into radiance temperature (NOAA 2017a):

$BT=\bigg{[}\frac{fk_{2}}{\log(\frac{fk_{1}}{L_{v}}+1)}-bc_{1}\bigg{]}\times\frac{1}{bc_{2}}$
(9)

where $L_{v}$ is the radiance, $fk_{1}$ and $fk_{2}$ are coefficients of the
Planck function derived from physical constants (i.e., the speed of light, the
Boltzmann constant, and the Planck constant) and the bandpass central
wavenumber, and $bc_{1}$ and $bc_{2}$ are the spectral response function
offset and scale correction terms. These four coefficients are included in the
product metadata as variables: planck_fk1, planck_fk2, planck_bc1, and
planck_bc2 (NOAA 2019).

Next, we will calculate the radiance of band $b$ in band 7 (NOAA 2017a):

$Rad_{b\\_in\\_b7}=\frac{fk_{1}}{\exp(\frac{fk_{2}}{BT\times
bc_{2}+bc_{1}})-1}$ (10)

After that, we normalized every band into the domain of $[0,1]$ to even cut
down the size. Notice here we used dask.array to store chunks instead of
numpy, which can cause bottleneck while calculating the data (1):

Listing 1 Normalization

⬇

1def normalization(crop: da.Array) -> da.Array:

2 stack_len, _, _ = crop.shape

3

4 dif_max = da.nanmax(crop, axis=(1, 2))

5 dif_min = da.nanmin(crop, axis=(1, 2))

6

7 new_crop_stack = []

8 for i in range(stack_len):

9 curr = crop[i]

10 new_crop_stack.append((curr - dif_min[i]) / (dif_max[i] - dif_min[i]))

11

12 new_crop_stack = da.stack(new_crop_stack, axis=0)

13 return new_crop_stack

Figure 3: Ground truth (conditioning frames) and generated frames from our
model.

We treated each band slice as a single channel for our image. Therefore a
single ”image” can have 10 ”channels.” To explore the data’s stochastic
characteristics, we can stack them to create a ”video” with 12 frames in total
video.shape = (12, 10, 256, 256). Finally, videos are compressed as .npz files
to reduce the size and increase the flexibility in storing.

Figure 4: Band 7 and crop region Figure 5: PSNR and SSIM scores with respect
to $t$ the dataset. Figure 6: Loss vs. epochs over time Figure 7: Average
negative PSNR vs. epochs over time

## Results and Discussion

We trained the model on our GOES-16 dataset. The dataset is highly stochastic
as the cloud can change its direction anytime. We set the size of the state-
space variable $y$ and auxiliary variable $z$, both to $20$. For Euler step
that shown in Equation (2), we set it to $2$. We used $2$ conditioning frames
to generate the next $h$ frames, as shown in Figure (5). Our method averages
$40.43$ on PSNR and $0.934$ on SSIM. As discussed by (Villegas et al. 2017),
expanding network capacity can enhance the performance of such variational
models. However, this is outside the scope of our work.

We challenge here the ODE inspiration of our model. Equation (2) amounts to
learning a residual function $f_{z_{\lfloor t\rfloor+1}}$ over $t\in[\lfloor
t\rfloor,\lfloor t\rfloor+1]$. We aim to test whether this dynamic is close to
its continuous generalization:

$\frac{dy}{dx}=f_{z_{\lfloor t\rfloor+1}}(y)$ (11)

which is a piecewise ODE. To this end, we refine this Euler approximation
during testing by using $\frac{\Delta t}{2}$; if this maintains the
performance of our model, then the dynamic rule of the latter is close to the
piecewise ODE, as shown in Figure (5).

## Conclusion and Future Works

We provide a unique dynamic latent model for stochastic video prediction that
decouples frame synthesis and dynamics, unlike previous image-autoregressive
models. This temporal model is based on residual updates of a tiny latent
state and has outperformed RNN-based models. This confers numerous desired
qualities on our strategy, including temporal economy and latent space
interpretability. We empirically illustrate the proposed model’s performance
and benefits, which beats previous state-of-the-art approaches for stochastic
video prediction. To the best of our knowledge, this is the first paper to
offer a latent dynamic model that scales for video prediction. The suggested
model is particularly innovative compared to current work on neural networks
and ODEs for temporal modeling; it is the first residual model to scale to
complex stochastic data such as videos.

We believe that the major principles of our method (state-space, residual
dynamic, static content variable) may be applied to different models. We will
supply a large amount of data for future studies, from GOES-16 (East) and
GOES-17 (West), to provide the variety in wildfire circumstances. Furthermore,
instead of employing ten bands, we may enhance our general characteristic of
picture slices by mixing all visible and near-infrared bands with infrared to
produce a full 16-band image. This gives the output a more distinct and
realistic appearance, so the produced frames have more informative values.

## Acknowledgements

We would like to thank all members, including students and staffs of 2022
Undergraduate Student Programmer at SSEC for helful discussions and comments,
as well as William Roberts for his help to process the GOES-16 dataset.

## References

  * Abatzoglou and Williams (2016) Abatzoglou, J. T.; and Williams, A. P. 2016.  Impact of anthropogenic climate change on wildfire across western US forests.  _Proceedings of the National Academy of Sciences_.
  * AWS (2022) AWS. 2022.  AWS S3 Explorer NOAA GOES-16.  ”Accessed: 2022-18-07”.
  * Babaeizadeh et al. (2017) Babaeizadeh, M.; Finn, C.; Erhan, D.; Campbell, R. H.; and Levine, S. 2017.  Stochastic Variational Video Prediction.
  * Bayer and Osendorfer (2014) Bayer, J.; and Osendorfer, C. 2014.  Learning Stochastic Recurrent Networks.
  * Behrmann et al. (2019) Behrmann, J.; Grathwohl, W.; Chen, R. T. Q.; Duvenaud, D.; and Jacobsen, J.-H. 2019\.  Invertible Residual Networks.  In Chaudhuri, K.; and Salakhutdinov, R., eds., _Proceedings of the 36th International Conference on Machine Learning_ , volume 97 of _Proceedings of Machine Learning Research_ , 573–582. PMLR.
  * Caballero et al. (2016) Caballero, J.; Ledig, C.; Aitken, A.; Acosta, A.; Totz, J.; Wang, Z.; and Shi, W. 2016.  Real-Time Video Super-Resolution with Spatio-Temporal Networks and Motion Compensation.
  * De Brabandere et al. (2016) De Brabandere, B.; Jia, X.; Tuytelaars, T.; and Van Gool, L. 2016.  Dynamic Filter Networks.
  * De Brouwer et al. (2019) De Brouwer, E.; Simm, J.; Arany, A.; and Moreau, Y. 2019.  GRU-ODE-Bayes: Continuous modeling of sporadically-observed time series.
  * de Bézenac, Ayed, and Gallinari (2019) de Bézenac, E.; Ayed, I.; and Gallinari, P. 2019.  Optimal Unsupervised Domain Translation.
  * Denton and Fergus (2018) Denton, E.; and Fergus, R. 2018.  Stochastic Video Generation with a Learned Prior.
  * Denton and Birodkar (2017) Denton, E. L.; and Birodkar, v. 2017.  Unsupervised Learning of Disentangled Representations from Video.  In Guyon, I.; Luxburg, U. V.; Bengio, S.; Wallach, H.; Fergus, R.; Vishwanathan, S.; and Garnett, R., eds., _Advances in Neural Information Processing Systems_ , volume 30. Curran Associates, Inc.
  * Dunbar and Garner (2021) Dunbar, B.; and Garner, R. 2021.  GOES Overview and History.
  * Fan, Zhu, and Yang (2019) Fan, H.; Zhu, L.; and Yang, Y. 2019.  Cubic LSTMs for Video Prediction.
  * Fraccaro et al. (2016) Fraccaro, M.; Sønderby, S. K.; Paquet, U.; and Winther, O. 2016.  Sequential Neural Models with Stochastic Layers.
  * Franceschi et al. (2020) Franceschi, J.-Y.; Delasalles, E.; Chen, M.; Lamprier, S.; and Gallinari, P. 2020\.  Stochastic Latent Residual Video Prediction.  In _Proceedings of the 37th International Conference on Machine Learning_. arXiv.
  * Goodfellow et al. (2014) Goodfellow, I. J.; Pouget-Abadie, J.; Mirza, M.; Xu, B.; Warde-Farley, D.; Ozair, S.; Courville, A.; and Bengio, Y. 2014.  Generative Adversarial Networks.
  * Graves (2013) Graves, A. 2013.  Generating Sequences With Recurrent Neural Networks.
  * Gregor et al. (2018) Gregor, K.; Papamakarios, G.; Besse, F.; Buesing, L.; and Weber, T. 2018.  Temporal Difference Variational Auto-Encoder.
  * Hafner et al. (2018) Hafner, D.; Lillicrap, T.; Fischer, I.; Villegas, R.; Ha, D.; Lee, H.; and Davidson, J. 2018.  Learning Latent Dynamics for Planning from Pixels.
  * He et al. (2018) He, J.; Lehrmann, A.; Marino, J.; Mori, G.; and Sigal, L. 2018.  Probabilistic Video Generation using Holistic Attribute Control.
  * He et al. (2016) He, K.; Zhang, X.; Ren, S.; and Sun, J. 2016.  Deep Residual Learning for Image Recognition.  In _2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 770–778.
  * Hochreiter and Schmidhuber (1997) Hochreiter, S.; and Schmidhuber, J. 1997.  Long Short-Term Memory.  _Neural Computation_ , 9.
  * Horé and Ziou (2010) Horé, A.; and Ziou, D. 2010.  Image Quality Metrics: PSNR vs. SSIM.  In _2010 20th International Conference on Pattern Recognition_ , 2366–2369.
  * Jiang et al. (2017) Jiang, H.; Sun, D.; Jampani, V.; Yang, M.-H.; Learned-Miller, E.; and Kautz, J. 2017\.  Super SloMo: High Quality Estimation of Multiple Intermediate Frames for Video Interpolation.  _2018 IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_.
  * Jin et al. (2020) Jin, B.; Hu, Y.; Tang, Q.; Niu, J.; Shi, Z.; Han, Y.; and Li, X. 2020.  Exploring Spatial-Temporal Multi-Frequency Analysis for High-Fidelity and Temporal-Consistency Video Prediction.
  * Kalchbrenner et al. (2016) Kalchbrenner, N.; Oord, A. v. d.; Simonyan, K.; Danihelka, I.; Vinyals, O.; Graves, A.; and Kavukcuoglu, K. 2016.  Video Pixel Networks.
  * Karl et al. (2016) Karl, M.; Soelch, M.; Bayer, J.; and van der Smagt, P. 2016.  Deep Variational Bayes Filters: Unsupervised Learning of State Space Models from Raw Data.
  * Khyrashchev and Larionov (2020) Khyrashchev, V.; and Larionov, R. 2020.  Wildfire segmentation on satellite images using Deep Learning.  _2020 Moscow Workshop on Electronic and Networking Technologies (MWENT)_.
  * Kingma and Dhariwal (2018) Kingma, D. P.; and Dhariwal, P. 2018.  Glow: Generative Flow with Invertible 1x1 Convolutions.  In Bengio, S.; Wallach, H.; Larochelle, H.; Grauman, K.; Cesa-Bianchi, N.; and Garnett, R., eds., _Advances in Neural Information Processing Systems_ , volume 31. Curran Associates, Inc.
  * Kingma and Welling (2013) Kingma, D. P.; and Welling, M. 2013.  Auto-Encoding Variational Bayes.
  * Krishnan, Shalit, and Sontag (2016) Krishnan, R. G.; Shalit, U.; and Sontag, D. 2016.  Structured Inference Networks for Nonlinear State Space Models.
  * Kumar et al. (2019) Kumar, M.; Babaeizadeh, M.; Erhan, D.; Finn, C.; Levine, S.; Dinh, L.; and Kingma, D. 2019.  VideoFlow: A Conditional Flow-Based Model for Stochastic Video Generation.
  * Lee et al. (2018) Lee, A. X.; Zhang, R.; Ebert, F.; Abbeel, P.; Finn, C.; and Levine, S. 2018.  Stochastic Adversarial Video Prediction.
  * Long et al. (2017) Long, Z.; Lu, Y.; Ma, X.; and Dong, B. 2017.  PDE-Net: Learning PDEs from Data.
  * Lu, Hirsch, and Scholkopf (2017) Lu, C.; Hirsch, M.; and Scholkopf, B. 2017.  Flexible spatio-temporal networks for video prediction.  _2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_.
  * Lu et al. (2017) Lu, Y.; Zhong, A.; Li, Q.; and Dong, B. 2017.  Beyond Finite Layer Neural Networks: Bridging Deep Architectures and Numerical Differential Equations.
  * Marlon et al. (2012) Marlon, J. R.; Bartlein, P. J.; Gavin, D. G.; Long, C. J.; Anderson, R. S.; Briles, C. E.; Brown, K. J.; Colombaroli, D.; Hallett, D. J.; Power, M. J.; Scharf, E. A.; and Walsh, M. K. 2012.  Long-term perspective on wildfires in the Western USA.  _Proceedings of the National Academy of Sciences_.
  * Minderer et al. (2019) Minderer, M.; Sun, C.; Villegas, R.; Cole, F.; Murphy, K.; and Lee, H. 2019.  Unsupervised Learning of Object Structure and Dynamics from Videos.
  * NASA (2015) NASA. 2015.  GOES Environmental Satellites.
  * NASA (2017) NASA. 2017.  ABI Bands Quick Information Guides.  ”Accessed: 2022-18-07”.
  * NOAA (2017a) NOAA. 2017a.  GOES-R Calibration Working Group and GOES-R Series Program, (2017): NOAA GOES-R Series Advanced Baseline Imager (ABI) Level 1b Radiances.
  * NOAA (2017b) NOAA. 2017b.  Instruments: Advanced Baseline Imager (ABI).
  * NOAA (2019) NOAA. 2019.  GOES R Series Product Definition and Users’ Guide.
  * Oord et al. (2016) Oord, A. v. d.; Kalchbrenner, N.; Vinyals, O.; Espeholt, L.; Graves, A.; and Kavukcuoglu, K. 2016.  Conditional Image Generation with PixelCNN Decoders.
  * Pereira et al. (2021) Pereira, G. H. d. A.; Fusioka, A. M.; Nassu, B. T.; and Minetto, R. 2021.  Active fire detection in Landsat-8 imagery: A large-scale dataset and a deep-learning study.  _ISPRS Journal of Photogrammetry and Remote Sensing_ , 178: 171–186.
  * Ronneberger, Fischer, and Brox (2015) Ronneberger, O.; Fischer, P.; and Brox, T. 2015.  U-Net: Convolutional Networks for Biomedical Image Segmentation.
  * Rousseau, Drumetz, and Fablet (2019) Rousseau, F.; Drumetz, L.; and Fablet, R. 2019.  Residual Networks as Flows of Diffeomorphisms.
  * Rubanova, Chen, and Duvenaud (2019) Rubanova, Y.; Chen, R. T. Q.; and Duvenaud, D. 2019.  Latent ODEs for Irregularly-Sampled Time Series.
  * Rumelhart, Hinton, and Williams (1986) Rumelhart, D. E.; Hinton, G. E.; and Williams, R. J. 1986.  Learning representations by back-propagating errors.
  * Ryder et al. (2018) Ryder, T.; Golightly, A.; McGough, A. S.; and Prangle, D. 2018.  Black-box Variational Inference for Stochastic Differential Equations.
  * Santoro et al. (2017) Santoro, A.; Raposo, D.; Barrett, D. G. T.; Malinowski, M.; Pascanu, R.; Battaglia, P.; and Lillicrap, T. 2017.  A simple neural network module for relational reasoning.
  * Schmit et al. (2017) Schmit, T. J.; Griffith, P.; Gunshor, M. M.; Daniels, J. M.; Goodman, S. J.; and Leblair, W. J. 2017.  A Closer Look at the ABI on the GOES-R Series.  _Bulletin of the American Meteorological Society_ , 98.
  * Shi et al. (2015) Shi, X.; Chen, Z.; Wang, H.; Yeung, D.-Y.; Wong, W.-k.; and Woo, W.-c. 2015.  Convolutional LSTM Network: A Machine Learning Approach for Precipitation Nowcasting.
  * Srivastava, Mansimov, and Salakhutdinov (2015) Srivastava, N.; Mansimov, E.; and Salakhutdinov, R. 2015.  Unsupervised Learning of Video Representations using LSTMs.
  * Tulyakov et al. (2017) Tulyakov, S.; Liu, M.-Y.; Yang, X.; and Kautz, J. 2017.  MoCoGAN: Decomposing Motion and Content for Video Generation.
  * Villegas et al. (2017) Villegas, R.; Yang, J.; Hong, S.; Lin, X.; and Lee, H. 2017.  Decomposing Motion and Content for Natural Video Sequence Prediction.
  * Vilà-Vilardell et al. (2020) Vilà-Vilardell, L.; Keeton, W. S.; Thom, D.; Gyeltshen, C.; Tshering, K.; and Gratzer, G. 2020.  Climate change effects on wildfire hazards in the wildland-urban-interface – blue pine forests of Bhutan.  _Forest Ecology and Management_ , 461.
  * Vondrick and Torralba (2017) Vondrick, C.; and Torralba, A. 2017.  Generating the future with Adversarial Transformers.  _2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_.
  * Walker et al. (2016) Walker, J.; Doersch, C.; Gupta, A.; and Hebert, M. 2016.  An Uncertain Future: Forecasting from Static Images using Variational Autoencoders.
  * Walker, Gupta, and Hebert (2015) Walker, J.; Gupta, A.; and Hebert, M. 2015.  Dense Optical Flow Prediction from a Static Image.
  * Wang et al. (2018) Wang, T.-C.; Liu, M.-Y.; Zhu, J.-Y.; Liu, G.; Tao, A.; Kautz, J.; and Catanzaro, B. 2018.  Video-to-Video Synthesis.  In Bengio, S.; Wallach, H.; Larochelle, H.; Grauman, K.; Cesa-Bianchi, N.; and Garnett, R., eds., _Advances in Neural Information Processing Systems_ , volume 31. Curran Associates, Inc.
  * Weissenborn, Täckström, and Uszkoreit (2019) Weissenborn, D.; Täckström, O.; and Uszkoreit, J. 2019.  Scaling Autoregressive Video Models.
  * Weissenborn, Täckström, and Uszkoreit (2020) Weissenborn, D.; Täckström, O.; and Uszkoreit, J. 2020.  Scaling Autoregressive Video Models.  In _International Conference on Learning Representations_.
  * Wichers et al. (2018) Wichers, N.; Villegas, R.; Erhan, D.; and Lee, H. 2018.  Hierarchical Long-term Video Prediction without Supervision.
  * Wu et al. (2020) Wu, Y.; Gao, R.; Park, J.; and Chen, Q. 2020.  Future Video Synthesis with Object Motion Prediction.
  * Yingzhen and Mandt (2018) Yingzhen, L.; and Mandt, S. 2018.  Disentangled Sequential Autoencoder.  In _Proceedings of the 35th International Conference on Machine Learning_ , volume 80 of _Proceedings of Machine Learning Research_ , 5670–5679. PMLR.
  * Zaheer et al. (2017) Zaheer, M.; Kottur, S.; Ravanbakhsh, S.; Poczos, B.; Salakhutdinov, R.; and Smola, A. 2017.  Deep Sets.
  * Zhang et al. (2021) Zhang, J.; Zhu, H.; Wang, P.; and Ling, X. 2021.  Att Squeeze U-Net: A lightweight network for forest fire detection and recognition.  _IEEE Access_ , 9.


# The Grasp Loop Signature: A Topological Representation for Manipulation
Planning with Ropes and Cables

Peter Mitrano1 and Dmitry Berenson1 This work was supported in part by Toyota
Research Institute, the Office of Naval Research Grant N00014-21-1-2118, and
NSF grants IIS-1750489, IIS-2113401, and IIS-2220876.1Department of Robotics,
University of Michigan

###### Abstract

This paper studies robotic manipulation of deformable, one-dimensional objects
(DOOs) like ropes or cables, which has important potential applications in
manufacturing, agriculture, and surgery. In such environments, the task may
involve threading through or avoiding becoming tangled with other objects.
Grasping with multiple grippers can create closed loops between the robot and
DOO, and if an obstacle lies within this loop, it may be impossible to reach
the goal. However, prior work has only considered the topology of the DOO in
isolation, ignoring the arms that are manipulating it. Searching over possible
grasps to accomplish the task without considering such topological information
is very inefficient, as many grasps will not lead to progress on the task due
to topological constraints. Therefore, we propose the
${\mathcal{G}_{L}}$-signature which categorizes the topology of these grasp
loops and show how it can be used to guide planning. We perform experiments in
simulation on two DOO manipulation tasks to show that using the
${\mathcal{G}_{L}}$-signature is faster and more successful than methods that
rely on local geometry or additional finite-horizon planning. Finally, we
demonstrate using the ${\mathcal{G}_{L}}$-signature in a real-world dual-arm
cable manipulation task.

##  I Introduction

Manipulation planning for deformable one-dimensional objects (DOOs) like ropes
and cables is challenging due to the high-dimensional state representation of
these objects and the cost of simulating their motion. Furthermore, most tasks
benefit from multiple arms to control DOO shape and avoid becoming tangled
with the environment. Therefore, the planner needs to consider the DOO, the
arms manipulating it, and the environment. A task and motion planning (TAMP)
approach to this problem would decompose planning into a grasp selection
problem and a motion planning problem for the DOO given a specific grasp, as
in [1, 2, 3]. However, the DOO planning problems are often expensive to solve.
To reduce the space of grasps we need to search, we borrow the idea of a
signature from the field of topology.

Figure 1: Annotated image of our real world cable threading setup. The red
dashed line shows a grasp loop $\tau_{1}$ that is linked with the skeleton
$\mathit{S}_{1}$. The blue grasp loop is not linked with $\mathit{S}_{1}$.
This distinction is captured by the proposed ${\mathcal{G}_{L}}$-signature and
is used in planning.

To explain what this signature represents, consider how the robot should grasp
the tip of the cable in Figure 1. By grasping we form a loop, which we call a
grasp loop and show as blue and red dashed lines in Figure 1. It is possible
to grasp either around the left side or the right side of the frame, but these
two grasps are categorically different in that we cannot smoothly deform from
one to the other without breaking the grasp or the frame. The frame also forms
a loop, called an obstacle loop ($\mathit{S}_{1}$). When grasping from the
left (red), these two loops are linked, but when grasping from the right
(blue) they are not. Our key insight is that the robot, DOO, and environment
form a graph of grasp loops and we can use this graph to construct a
signature, ${\mathcal{G}_{L}}$-signature, which captures topological
information relevant for planning. To be clear, we do not address knots in the
DOO. Our work is complimentary to work on tying or untying knots [4, 5, 6, 7].

The main contribution of this paper is the ${\mathcal{G}_{L}}$-signature which
compactly represents the topological relationship between the object, the arms
manipulating it, and the environment. We demonstrate that this signature is
useful for manipulation planning with DOOs. In simulation, we show that
methods using the ${\mathcal{G}_{L}}$-signature outperform baselines and
ablations which search for grasps without using topological information.
Finally, we demonstrate a threading and point reaching task on a physical
robot. Videos and animations can be found on our Project
Website111https://sites.google.com/view/doo-manipulation-signature/home.

##  II Related Work

Topology in Motion Planning: Topology and homotopy have been used in path
planning for flying and driving robots [8, 9], as well as tethered robots
[10]. [10] operates only in 2D and [11] considers an approximation of homotopy
for 3D path planning. [8] introduces a simple-to-compute and exact signature
for characterizing the homotopy of 3D paths with respect to 3D obstacles with
holes in them, called the h-signature. We build on [8] to define our
${\mathcal{G}_{L}}$-signature.

Manipulation Planning for Deformable Objects: Prior work on knot tying and
untying has also applied knot theory to DOO manipulation [4, 12, 5, 7, 13, 14,
6]. These methods use planar crossing representations, which project a curve
into a specified plane and count the sequence and type of crossings. [5] used
this method for robotic knot tying, and extended this to tying around
obstacles by specifying connections between obstacles and the DOO. However,
these methods do not consider how the manipulator effects the topology, and
fail in some cases with non-planar obstacles. A method for threading surgical
needles was proposed in [15], but uses floating grippers and does not address
planning for the robots’ arms or obstacles, and is limited to tight-tolerance
insertion tasks. [16, 17, 18, 19, 20] all address manipulation planning for
DOOs assuming the grasp is fixed, which is complementary to this work.

Grasping and Regrasping: With rigid grasping, the challenge is primarily in
achieving a stable grasp [21, 22]. With deformables, the challenge is where to
grasp, as studied in cloth smoothing or folding [23, 24, 25]. These works use
pick-and-place primitives with a single manipulator, which is too restrictive
for many tasks. In contrast, we use a dual-arm manipulator and use joint
velocities as our action space. In [26], a dual arm manipulator autonomously
dresses a mannequin. Their method for grasp planning is based on learned
visual models of the garment, and only considers grasps near keypoints such as
the elbow or shoulder. The methods in [1, 2, 3] plan grasps on the DOO, but
they assume the rope is planar (flat on a table), use one manipulator, and do
not consider obstacles for the manipulator. [27] describes a method that
produces pick, place, and sliding paths in the configuration space without
explicit task planning. However, this method does not address underactuated
kinodynamic systems such as DOOs.

##  III Defining the ${\mathcal{G}_{L}}$-signature

Figure 2: (A) Illustration of the h-signature for a loop representing the
robot and DOO (red/blue) and a loop representing an obstacle (black). (B) Two
examples of the h-signature for a skeleton with two obstacle loops $S_{1}$ and
$S_{2}$.

###  III-A Preliminaries

We primarily use notation that is consistent with [8]. We call a closed one-
dimensional curve in 3D a loop. The environment is assumed to be decomposed
into a skeleton made up of multiple obstacle loops
$\textbf{S}=\\{\mathit{S}_{1},\dots,\mathit{S}_{n}\\}$. Each obstacle loop is
made up of line segments
$\mathit{S}_{i}=\\{\textbf{s}_{i}^{1},\dots,\textbf{s}_{i}^{n_{i}}\\}$. In
practice, the skeleton can either be specified manually or computed
automatically from a medial axis transform of a mesh or pointcloud of the
environment. The state $s=(q,o)$ contains the robot state $q$ (joint angles)
and the DOO state $o$ (ordered list of points in $\mathbb{R}^{3}$).

[8] plans paths that are in a given homotopy class or avoid a certain homotopy
class. They compare two paths by considering the homotopy class of the closed
loop $\tau$ formed by joining the two paths at their shared start and end
points. For a path loop $\tau$ and an obstacle loop $\mathit{S}$, they define
the h-signature $h(\tau,\mathit{S})\in\mathbb{Z}$, which counts the number of
times $\tau$ passes through $\mathit{S}$. The sign of $h$ in this case is
determined by the direction of $\tau$. The h-signature can be extended to a
list of the h-signatures with respect to each obstacle loop in the skeleton
$h(\tau,\textbf{S}))=[h(\tau,\mathit{S}_{1}),\dots,h(\tau,\mathit{S}_{n})]$.
These cases are illustrated in Figure 2. The equation for computing
$h(\tau,\mathit{S})$ is reproduced from [8]. The point
$\textbf{s}_{i}^{j^{\prime}}$ is the point that follows $\textbf{s}_{i}^{j}$,
and $r$ is a point on the loop $\tau$. The integration over $\tau$ is done
numerically.

$\begin{split}h(\tau,\mathit{S})=\frac{1}{4\pi}\int_{\tau}\sum_{j=1}^{n_{i}}\Phi(\textbf{s}_{i}^{j},\textbf{s}_{i}^{j^{\prime}},r)\Delta
r\\\
\Phi(\textbf{s}_{i}^{j},\textbf{s}_{i}^{j^{\prime}},r)=\frac{1}{||d||^{2}}\Big{(}\frac{d\times
p^{\prime}}{||p^{\prime}||}-\frac{d\times p}{||p||}\Big{)}\\\
p=\textbf{s}_{i}^{j}-r,\quad p^{\prime}=\textbf{s}_{i}^{j^{\prime}},\quad
d=\frac{(\textbf{s}_{i}^{j^{\prime}}-\textbf{s}_{i}^{j})\times(p\times
p^{\prime})}{||\textbf{s}_{i}^{j^{\prime}}-\textbf{s}_{i}^{j}||^{2}}\end{split}$
(1)

We take this idea but apply it to grasp loops, instead of paths. Unlike in
path planning, where the direction of $\tau$ matters, we only care how or
whether loops are linked. Accordingly, we assert that $h$ is always non-
negative.

###  III-B Computing the ${\mathcal{G}_{L}}$-signature

Figure 3: The process of constructing the ${\mathcal{G}_{L}}$-signature. (C)
There are 2 grasp loops and 3 object loops, so the
${\mathcal{G}_{L}}$-signature is a set with two elements, and each element is
a vector of 3 non-negative integers. Figure 4: Example scenes and their
${\mathcal{G}_{L}}$ values. The dashed blue and red lines are grasp loops, and
the solid black lines are obstacle loops. (B.3) The blue grasp loop is omitted
from the signature, as described in Section III-B. The purple sphere shows the
goal region.

The ${\mathcal{G}_{L}}$-signature is composed of the h-signatures
$h(\tau,\textbf{S})$ of grasp loops $\tau$ formed by the robot and DOO. The
grasp loops are constructed based on a graphical model of the state where
vertices are the robot base, its grippers, and attach points, and edges are
paths between them. Attach points are used to represent locations on the DOO
which are fixed relative to the robot (e.g. plugged into the wall or tethered
to the robot itself). Figure 3 illustrates how the graph construction step
works. The robot base vertex is connected to all gripper and attach vertices
because it connects to the grippers directly (via the robot geometry) and the
attach points indirectly (via the environment). Edges connect grippers/attach
points to one another if they are adjacent on the DOO. In Figure 3, the
vertices $(g_{1},g_{2})$ are adjacent, as are $(g_{2},a_{1})$, but
$(g_{1},a_{1})$ are not.

From this graph, we extract all cycles of 3 vertices which contain a gripper,
and convert each cycle to a grasp loop $\tau$. We consider only length-3
cycles containing a gripper in our signature because these contain the
relevant information for planning how to manipulate the DOO. Including longer
cycles would add redundant information. Likewise, cycles not containing a
gripper are omitted for compactness, since we assume that attach points cannot
be changed by the planner. To make a grasp loop from a cycle, we concatenate
the 3D paths represented by the cycles’ edges. This requires a skeletonized
representation of the robot geometry, which can be constructed from the
kinematic tree and the origins of the links, as well as the points
representing the DOO. A path between the robot base and an attach point
($(b,a_{1})$ in Figure 3) can be chosen arbitrarily, as long as it is the same
for all states.

For each grasp loop $\tau_{i}$, we compute the associated h-signature
$h(\tau_{i},\textbf{S})$. The ${\mathcal{G}_{L}}$-signature of the state,
denoted ${\mathcal{G}_{L}}(s)$, is the multiset of the h-signatures of each
grasp loop. In a multiset the order does not matter, but elements may repeat.
The number of repetitions of an element is called its multiplicity. Two
multisets are equivalent if their elements and multiplicities are equal.
Preserving repetitions in the ${\mathcal{G}_{L}}$-signature allows us to
represent multiple grasp loops that go through the same obstacle loop.

This may result in a grasp loop $\tau$ containing two grippers for which
$h(\tau,\textbf{S})=\bm{0}$ (i.e. not linked S). The blue dashed grasp loop
shown in Figure 4 B.3 shows this. Releasing one of the grippers does not
categorically change what we can do with the object, and neither would
grasping with an additional gripper right next to two already grasping.
Therefore, if there is a cycle with $h(\tau,\textbf{S})=\bm{0}$ containing two
grippers, one of the grippers is removed from the graph and the process
restarts from the cycle extraction step.

###  III-C Computational Complexity

The complexity of computing the ${\mathcal{G}_{L}}$-signature can be written
in Big-O notation based on the number of skeletons $n_{s}$, line segments in
the skeleton $l_{s}$, arms and/or attach points $n_{a}$, and the length of the
arms and/or DOO $l_{a}$. Due to the rules of construction defined above, in
the worst case where all arms are grasping, the graph of grasps loops is a fan
graph ($F_{1,n_{a}}$) [28]. In the base case of $n_{a}=2$, the graph has 3
vertices and one cycle of length 3. Adding another vertex adds one cycle, so
in the worst case $n_{a}$ arms/attach points create $n_{a}-1$ loops. Each
cycle (loop) is compared with each skeleton, and the number of comparisons
scales linearly with both the number of line segments and the length of the
loop, giving a total complexity of $O\big{(}(n_{a}-1)n_{s}l_{s}l_{a}\big{)}$.
Our Python implementation, using the NetworkX library [29] for computing the
${\mathcal{G}_{L}}$-signature for a state, takes $\leq$10ms in the Untangling
and Threading environments.

##  IV DOO Manipulation with ${\mathcal{G}_{L}}$-signature

###  IV-A Problem Statement

In this section, we define the DOO manipulation problem which our proposed
planning method addresses. In our experiments, the robot has two 7-dof arms
attached to a 2-dof torso with parallel-jaw grippers, but the
${\mathcal{G}_{L}}$-signature can be applied to other robot morphologies. We
assume we have a complete geometric model and skeleton of the environment.
When manipulating with the current grasp, the action space is joint velocities
$\dot{q}$. We describe points on the DOO primarily by their location
$l\in[0,1]$, where $l=0$ is one end of the DOO and $l=1$ is the other. Each
location also corresponds to a point $p(l)\in\mathbb{R}^{3}$. Grasps are
represented by a vector of locations $\bm{l}=[l_{1},l_{2}]$, one for each
gripper. A set of grasp locations $\bm{l}$ must also be paired with a
collision-free motion of the robot to the new grasp locations, which may be
reachable by many distinct joint configurations.

The goal of the manipulation is to bring a keypoint $l_{k}$ on the DOO to a
goal region with position $p_{\text{goal}}$ and radius $d_{\text{goal}}$. This
is a useful skill for plugging in cables, or for using tools with an attached
cable or hose, and more complex tasks like cable harnessing can be described
as a sequence of these point reaching goals. Additionally, one can specify a
desired ${\mathcal{G}_{L}}$-signature for the goal
${\mathcal{G}_{L}}{}_{\text{goal}}$. This type of DOO manipulation is
complementary to tying or untying knots, which has been addressed in prior
work [5, 6, 7].

###  IV-B DOO Point Reaching Method

Algorithm 1 describes our method for point reaching tasks. This algorithm
serves to demonstrate the utility of the ${\mathcal{G}_{L}}$-signature in
planning. It uses cost functions that are designed for our robot and our
scenarios, and these functions may need to be modified for other applications.
Given the current grasp, we use MPPI [30] to find an action $\dot{q}$ that
minimizes the goal cost $C_{\text{goal}}$, shown in Eq. (2). MPPI runs until
the goal is reached or progress stops. If progress stops, we plan and execute
a grasp change, and resume running MPPI. This process is repeated until the
goal is reached (trial success) or for $i^{\text{max}}$ iterations (trial
failure). For both MPPI and grasp planning, we model the dynamics of the
robot, rope, and obstacles in MuJoCo [31].

Algorithm 1 DOO Point Reaching with the ${\mathcal{G}_{L}}$-signature

1:procedure pointReaching($s,n_{x},l_{k},p_{\text{goal}},d_{\text{goal}}$)

2: for $i<i^{\text{max}}$ do

3: $\dot{q}=$MPPI$(s,p_{\text{goal}},C_{\text{goal}})$

4: $s=f(\dot{q})$ $\triangleright$ Execute and get state

5: if $||p_{\text{goal}}-p(l_{k})||<d_{\text{goal}}$ then

6: break

7: if trapped then

8: $d_{0}=\min(|\bm{l}_{0}-l_{k}|)$ $\triangleright$ Initial geodesic

9: $\bm{l}^{*}=\textit{PlanGrasp}(s,n_{x},C_{\text{grasp}},l_{k},\mathcal{B})$

10: $d^{*}=\min(|\bm{l}^{*}-l_{k}|)$

11: if $d^{*}\geq d_{0}$ then $\triangleright$ Unable to grasp closer

12: Add ${\mathcal{G}_{L}}(s)$ to $\mathcal{B}$

13:
$\bm{l}^{*}=\textit{PlanGrasp}(s,n_{x},C_{\text{grasp}},l_{k},\mathcal{B})$

14: ExecuteGraspChange$(\bm{l}^{*})$

The method for determining if MPPI is trapped, called trap detection, is
adapted from [32]. Trap detection operates on a window of recent joint
configurations $q_{1},\dots,q_{T}$, and computes the average one-step state
difference $\bar{q}=\frac{q_{T}-q_{1}}{T}$ and keeps a running maximum of this
value $\bar{q}^{+}$ over the trial. MPPI is considered trapped when the ratio
$\frac{\bar{q}}{\bar{q}^{+}}$ is below a threshold (0.2-0.3 in our
experiments).

The goal cost used for MPPI is shown in Equation (2), where the state $s$ is
used to compute the grasp locations $\bm{l}$, grasping state
$\bm{\mathbb{1}_{g}}$, keypoint position $p(l_{k})$, grasp positions
$p(\bm{l})$, and number of contacts $n_{\text{con}}$.

$\begin{split}C_{\text{goal}}(s,\dot{q})=||p(l_{k})-p_{\text{goal}}||+\alpha_{1}\sum_{i=1}^{n_{a}}\mathbb{1}_{\bm{g},i}||p(l_{i})-p_{\text{goal}}||+\\\
\alpha_{2}\sqrt{n_{\text{con}}}+\alpha_{3}||\dot{q}||\end{split}$ (2)

The first term in Eq. 2 brings the keypoint $p(l_{k})$ towards the goal
$p_{\text{goal}}$. The second term provides a reward for moving any grippers
which are grasping towards the goal. $n_{a}$ is the number of arms,
$\bm{\mathbb{1}_{g}}$ is a binary vector
($\mathbb{1}_{\bm{g},i}\in\bm{\mathbb{1}_{g}}$) indicating which grippers are
grasping, and $l_{i}\in\bm{l}$ are the current grasp locations. This term is
useful when the DOO is slack and the keypoint cannot be pulled directly (See
Figure 4 C). The third term penalizes collision between the robot and
environment, based on the number of contacts $n_{\text{con}}$ reported by the
dynamics. Finally, the fourth term penalizes high joint velocities to
encourage smooth motion. The hyperparameters $\alpha_{1,2,3}$ were selected to
prioritize collision avoidance first, then bringing the keypoint to the goal.

In PlanGrasp we sample $n_{x}$ grasps ($\approx$50) and choose the best one.
Grasps are sampled by first choosing a strategy for each gripper. The possible
strategies are STAY, GRASP, MOVE, or RELEASE. STAY means the gripper does not
change its grasp, or remains not grasping. GRASP means the gripper is not
grasping and should create a new grasp. MOVE means the gripper is currently
grasping, but should move to a new grasp location. RELEASE means the gripper
is currently grasping and should release. For the GRASP or MOVE strategies, we
sample a location $l\in[0,1]$. At least one gripper must be grasping. For each
candidate grasp, we simulate release and grasp dynamics using MuJoCo. Modeling
grasping using friction and caging is challenging, so we instead use equality
constraints between the rope and the grippers that are grasping. MoveIt [33]
is used to find collision-free paths to move the grippers to desired grasp
locations. The result is a candidate state $s$ and collision free trajectory
for each candidate grasp. We choose the grasp with the lowest cost according
to Eq. 3. With abuse of notation, we say the candidate state $s$, change in
state $\Delta s$, and grasp state $\bm{\mathbb{1}_{g}}$ are derived from the
candidate grasp locations $\bm{l}$.

$\begin{split}C_{\text{grasp}}(\bm{l})=\mathbb{1}{}_{\text{feasible}}+\mathbb{1}_{\mathcal{B}}(s)+\mathbb{1}_{{\mathcal{G}_{L}}}(s,{\mathcal{G}_{L}}{}_{\text{goal}})+\\\
\bm{\mathbb{1}_{g}}\cdot|\bm{l}-l_{k}|+\beta_{1}\Delta s\end{split}$ (3)

The first term in Eq 3 assigns a large penalty (e.g. 100) if no collision-free
path to the grasp was found. The next two terms assign a large penalty based
on the ${\mathcal{G}_{L}}$-signature of candidate state, either for matching a
blocklisted signature (second term) or for not matching the goal signature
(third term). The fourth term encourages grasping near the keypoint, based on
the geodesic distance for any grasping grippers. The final term penalizes the
change in robot and DOO state. This results in shorter and faster grasps and
is weighted by $\beta_{1}$ to be the least important term. The large penalties
dominate the keypoint and state-change terms.

We use a blocklist of ${\mathcal{G}_{L}}$-signature’s to avoid retrying
topological configurations in which we have failed to reach the goal.
Specifically, we blocklist the current ${\mathcal{G}_{L}}$-signature if the
planner cannot find a grasp with lower geodesic cost (4th term in Eq (3)) than
the current grasp (Alg 1 lines 8-12). In other words, we do not blocklist if
it is possible to grasp closer to the keypoint. This avoids blocklisting the
current ${\mathcal{G}_{L}}$-signature in the case that progress halts, not
because of topological constraints, but because the grasp is too far away from
the keypoint to control it. This is inspired by the idea of diminishing
rigidity [34], which says that the control over a point on a deformable object
decreases as the geodesic distance to the gripper increases. In the case of
multiple grippers, the initial grasp locations $\bm{l}_{0}$ or new grasp
locations $\bm{l}^{*}$ may be a list of locations, in which case we use the
$\min$ when computing the geodesic distance.

##  V Applications

We now describe how the above framework can be applied or adapted to DOO
manipulation in three different environments, Pulling, Untangling, and
Threading. We use a horizon of $H=15$ in MPPI.

###  V-A Pulling Environment

The Pulling environment contains a large hose attached to a wall. The scene is
depicted in Figure 4 C. The robot is initially not grasping the hose, and the
head of the hose is out of the robot’s reach. The goal region, shown as a
purple sphere, is near the base of the robot on the floor. This environment
requires regrasping to bring the head of the hose to the goal, and
demonstrates the behavior of the general method in the case where there are no
skeletons, and no changes in the ${\mathcal{G}_{L}}$-signature.

When applying Alg 1 in this environment, the robot initially chooses a grasp
as far down the DOO as it can reach, due to the geodesic cost term in Equation
3. Then, the gripper pulls towards the goal due to the second term in the MPPI
cost (2). This brings more of the DOO within reach. When the gripper reaches
the goal, the cost cannot be decreased and the controller slows to a stop. At
this point, trap detection triggers regrasp planning. Since the DOO is now
closer, a plan is found that reaches closer to the tip ($l_{k}=1$) than
before. Because the grasp is closer to the tip, the current
${\mathcal{G}_{L}}$-signature is not blocklisted. This repeats until the grasp
is close enough to the tip that it can be brought to the goal region. In the
Pulling environment, our method succeeded in 25/25 trials, where each trial
differs in the initial DOO configuration and the random seed used for sampling
in planning.

###  V-B Untangling Environment

Method | Success | Wall Time (m) | Sim Time (m)
---|---|---|---
${\mathcal{G}_{L}}$-signature (ours) | 22/25 | 12 (5) | 1.4 (1.1)
Always Blocklist | 22/25 | 14 (7) | 1.3 (1.0)
No ${\mathcal{G}_{L}}$-signature | 10/25 | 20 (10) | 2.0 (1.3)
TAMP50 | 15/25 | 142 (116) | 2.4 (1.7)
TAMP5 | 9/25 | 34 (22) | 1.8 (1.2)
TABLE I: Results in the Untangle environment. Times in minutes are for the
completion of the task, where Sim Time does not include planning time.
Standard deviations are given in parentheses.

The Untangle environment resembles a computer rack with a cable that needs to
be plugged in. The scene is depicted in Figure 4 A. One end of the DOO is
fixed to the environment (e.g. plugged in elsewhere), and the robot is
initially grasping some other location on the DOO. The robot often needs to
regrasp several times in order to reach the goal. Unlike in the Pulling
environment, the ${\mathcal{G}_{L}}$-signature can take on many different
values depending on the configuration of the DOO and the grasp configuration.
This demonstrates the utility of the ${\mathcal{G}_{L}}$-signature in planning
when there is no goal ${\mathcal{G}_{L}}$-signature.

We evaluate Alg 1 on this task, and compare to an ablation that omits the two
terms using the ${\mathcal{G}_{L}}$-signature from Eq 3. We call this method
No ${\mathcal{G}_{L}}$-signature. This often results in greedy re-grasping of
the keypoint. We also evaluate a version called Always Blocklist, where we
blocklist the current ${\mathcal{G}_{L}}$-signature every time a trap is
detected. Finally, we compare our proposed method to a method inspired by task
and motion planning (TAMP), where $H$ additional steps of MPPI are simulated
for each candidate grasp during planning and the final goal cost is used in
place of cost terms relying on the ${\mathcal{G}_{L}}$-signature. We test two
versions of this method with $H=5$ and $H=50$. Success rates and trial times
are shown in Table I. Trials vary in the initial configuration of the robot,
grasp location, DOO configuration, in the size of the computer rack, and in
the location of the goal.

Methods using the ${\mathcal{G}_{L}}$-signature have the highest success rates
and are faster than alternatives. Always Blocklist has an equivalent success
rate as the full proposed method, but prematurely abandons grasps that would
lead to reaching the goal. Our method and the Always Blocklist method each
failed in 3 trials by trying too many unsuccessful grasps before
$i^{\text{max}}$ was reached. The No ${\mathcal{G}_{L}}$-signature ablation
and both TAMP methods usually fail by greedily trying to grasp the keypoint.
Without a very long horizon or the ${\mathcal{G}_{L}}$-signature, the planner
often grasps with configurations that make reaching the goal impossible. The
longer horizon used in $H=50$ helps alleviate this issue but is insufficient
in many cases while also causing a 10x increase in planning time.

###  V-C Threading Environment

In the Threading environment, the objective is for the robot to thread the DOO
through a series of fixtures in a specified order (e.g. “fixture 1, then
fixture 2, then fixture 3”), after which it should bring the keypoint to a
goal region. The threading is described by a series of goal signatures
${\mathcal{G}_{L}}_{1},\dots,{\mathcal{G}_{L}}_{N}$. This skill could be
applied to installing cable harnesses in a car or electrical wiring in a
building. One end of the DOO is fixed to the environment, and the robot is
initially grasping some other location on the DOO. This environment is
depicted in Figure 4 B.

Algorithm 2 DOO Threading with the ${\mathcal{G}_{L}}$-signature

1:procedure
Threading($s,p_{\text{goal}},n_{x},{\mathcal{G}_{L}}_{1},\dots,{\mathcal{G}_{L}}_{N}$)

2: $j=1$ $\triangleright$ Threading subgoal index

3: for $i<i^{\text{max}}$ do

4: if $j<N$ then $\triangleright$ threading subgoals

5: $\dot{q}=$MPPI$(s,{\mathcal{G}_{L}}_{j},C_{\text{goal}})$

6: $s=f(\dot{q})$ $\triangleright$ Execute and get state

7: if disc penetrated then

8:
$\bm{l}^{*}=\textit{PlanGrasp}(s,n_{x},C_{\text{grasp}},{\color[rgb]{0.3125,0.74609375,0.4296875}1},\mathcal{B})$

9: if ${\mathcal{G}_{L}}(\bm{l}^{*})=={\mathcal{G}_{L}}_{j}$ then

10: ExecuteGraspChange$(\bm{l}^{*})$

11: if trapped then

12:
$\bm{l}^{*}=\textit{PlanGrasp}(s,n_{x},C_{\text{grasp}},{\color[rgb]{0.3125,0.74609375,0.4296875}l-0.05},\mathcal{B})$

13: ExecuteGraspChange$(\bm{l}^{*})$

14: if ${\mathcal{G}_{L}}(s)=={\mathcal{G}_{L}}_{j}$ then

15: $j=j+1$ $\triangleright$ next subgoal

16: else $\triangleright$ final point reaching

17: $\dot{q}=$MPPI$(s,p_{\text{goal}},C_{\text{goal}})$

18: $s=f(\dot{q})$ $\triangleright$ Execute and get state

19: if $p_{\text{goal}}-p(l_{k})<d_{\text{goal}}$ then

20: break

The method is detailed in Alg 2, and key differences to Alg 1 are highlighted
in green. In MPC, the ${\mathcal{G}_{L}}$-signature is used in the same way as
in Alg 1, but the goal cost has been changed to match the new task.
Additionally, we use the ${\mathcal{G}_{L}}$-signature to ensure certain goal
signatures at each stage of threading. To reach a threading subgoal, we
augment the goal cost (Eq (2)) with the magnetic-field cost proposed in [15].
This uses the formula
$\sum_{j=1}^{n_{i}}\Phi(\textbf{s}_{i}^{j},\textbf{s}_{i}^{j^{\prime}},r)$
from Equation (1) for the direction of the magnetic field, but where $r$ is
the keypoint of the DOO. This causes the keypoint to follow virtual magnetic
field lines through the fixture in the specified direction.

When a threading subgoal is reached, and the planner returns a grasp which
does not match ${\mathcal{G}_{L}}{}_{\text{goal}}$, we reject it and continue
running MPPI to push the cable further through the fixture. This happens when
there is no feasible grasp matching ${\mathcal{G}_{L}}{}_{\text{goal}}$ due to
obstacles or reachability issues. Furthermore, we also check
${\mathcal{G}_{L}}{}_{\text{goal}}$ after executing the grasp to ensure that
any deviations that occurred when executing the grasp plan do not change the
${\mathcal{G}_{L}}$-signature. To check when a threading subgoal is reached,
we use the disc penetration check from [15]. The goal signatures
${\mathcal{G}_{L}}_{1},\dots,{\mathcal{G}_{L}}_{N}$ are used in the grasp
planning (3rd term in Eq (3)), but the blocklist is not (2nd term). Grasp
sampling is restricted to alternating single-gripper grasps, which speeds up
grasp planning. The keypoint location for grasp planning is also restricted to
speed up planning. It is chosen to be the tip ($l_{k}=1$) when a threading
subgoal is reached, and further down the DOO than the current grasp when stuck
($l_{k}=l-0.05$).

We compare our proposed method to the TAMP5 method described previously. In
this environment, the TAMP method often chooses grasps that correctly thread
through fixtures 1 and 2, because those grasps allow immediate progress
towards the next subgoal. However, it often grasps incorrectly on fixture 3,
which requires the robot to first reach further around and results in less
immediate progress towards the next subgoal. We also adapted the method in
[15] from a single floating gripper to our dual arm robot. As in our method,
we use alternating single-gripper grasps. Instead of the more general trap
detection method we use, this baseline checks the distance between the gripper
and the fixture being threaded. This baseline fails similarly to the TAMP5
method, but additionally fails when MPPI is trapped but is outside the
distance-to-fixture threshold. Success rates and trial times are shown in
Table II. Trials vary in the initial configuration of the robot, grasp
location, DOO configuration, and in the positions of the fixtures. In the
trials in which our method failed to complete the task, MPPI reached a joint
configuration with one arm that prevented the other arm from grasping the DOO
at or near the tip, as required by our method. This means the robot remained
stuck until $i^{\text{max}}$ was reached.

Method | Success | Wall Time (m) | Sim Time (m)
---|---|---|---
${\mathcal{G}_{L}}$-signature | 42/50 | 8 (2) | 1.3 (0.4)
TAMP5 | 21/50 | 17 (3) | 1.3 (0.6)
Wang et al. [15] | 12/50 | 8 (3) | 1.0 (0.8)
TABLE II: Results on the Threading task.

###  V-D Real World Threading

We demonstrate a simplified version of the Threading task in the real world,
as depicted in Figure 1. This shows the applicability of the proposed methods
in the presence of significant calibration, perception, and dynamics modeling
errors. We use CDCPD2 [35] to track the DOO and visual servoing from in-hand
cameras to guide grasping. The environment geometry is specified manually, and
the simulation dynamics were tuned to match the real world setup as closely as
possible for the particular setup.

##  VI DISCUSSION

Figure 5: Additional examples where the ${\mathcal{G}_{L}}$-signature may be
useful. (A) Drones lifting a large object can be treated similarly to a multi-
armed robot. (B) Dual-arm grasping of large rigid objects can result in
distinct signatures.

The planning methods described above are somewhat specific to their respective
tasks, and the tasks represent a small subset of the domain of rope and cable
manipulation. However, the ${\mathcal{G}_{L}}$-signature may be useful for
other planning methods and other tasks, as shown in Figure 5. In both of these
examples, we can compute the ${\mathcal{G}_{L}}$-signature and see that it
categorizes different states in ways that may be useful for planning.

We use the ${\mathcal{G}_{L}}$-signature as part of the cost function in
sampling-based MPC, but it could also be used as a constraint in RRT or A*
planners (similar to [8]). Additionally, while the signature is composed of
integers when all grasp and obstacle loops are closed, for incomplete loops
they take on real values and have gradients which may be used in gradient-
based planning methods. The ${\mathcal{G}_{L}}$-signature could also be used
to constrain the topology of shape completion or scene reconstruction. For
example, to ensure that when reconstructing the shape of a hook, it does not
form a closed loop that would trap the robot arm or DOO.

##  VII CONCLUSION

In this paper, we proposed the ${\mathcal{G}_{L}}$-signature which describes
the topology of closed loops formed by grasping the DOO with respect to closed
loops formed by stationary objects in the environment. Our
${\mathcal{G}_{L}}$-signature builds on the h-signature proposed in prior work
on topological path planning. Furthermore, we describe an algorithm for
manipulating DOOs that plans grasps based on the proposed
${\mathcal{G}_{L}}$-signature. In our experiments, we find that using the
${\mathcal{G}_{L}}$-signature improves task success and reduces planning times
compared to a task and motion-planning method. Finally, we use the method to
thread a cable and bring it to a goal region on a real robot.

## References

  * [1] Gabriel Arslan Waltersson, Rita Laezza, and Yiannis Karayiannidis.  Planning and control for cable-routing with dual-arm robot.  ICRA, 2022.
  * [2] Ashvin Nair, Dian Chen, Pulkit Agrawal, Phillip Isola, P. Abbeel, Jitendra Malik, and Sergey Levine.  Combining self-supervised learning and imitation for vision-based rope manipulation.  ICRA, 2017.
  * [3] Wilson Yan, Ashwin Vangipuram, P. Abbeel, and Lerrel Pinto.  Learning predictive representations for deformable objects using contrastive estimation.  In Conference on Robot Learning, 2020.
  * [4] Hidefumi Wakamatsu, Akira Tsumaya, Eiji Arai, and Shinichi Hirai.  Manipulation planning for knotting/unknotting and tightly tying of deformable linear objects.  ICRA, 2005.
  * [5] Mitul Saha and Pekka Isto.  Manipulation planning for deformable linear objects.  IEEE Trans. Robotics, 2007.
  * [6] Priya Sundaresan, Jennifer Grannen, Brijen Thananjeyan, Ashwin Balakrishna, Jeffrey Ichnowski, Ellen R. Novoseller, Minho Hwang, Michael Laskey, Joseph Gonzalez, and Ken Goldberg.  Untangling dense non-planar knots by learning manipulation features and recovery policies.  In RSS, 2021.
  * [7] Weifu Wang and Devin Balkcom.  Knot grasping, folding, and re-grasping.  IJRR, 2018.
  * [8] Subhrajit Bhattacharya, Maxim Likhachev, and Vijay Kumar.  Identification and representation of homotopy classes of trajectories for search-based path planning in 3d.  In RSS, 2011.
  * [9] Subhrajit Bhattacharya, Maxim Likhachev, and Vijay R. Kumar.  Topological constraints in search-based robot path planning.  Autonomous Robots, 2012.
  * [10] Takeo Igarashi and Mike Stilman.  Homotopic path planning on manifolds for cabled mobile robots.  WAFR, 2010.
  * [11] Path Deformation Roadmaps: Compact Graphs with Useful Cycles for Motion Planning, 2008.
  * [12] Hidefumi Wakamatsu, Akira Tsumaya, Eiji Arai, and Shinichi Hirai.  Manipulation planning for unraveling linear objects.  ICRA, 2006.
  * [13] Jennifer Grannen, Priya Sundaresan, Brijen Thananjeyan, Jeffrey Ichnowski, Ashwin Balakrishna, Minho Hwang, Vainavi Viswanath, Michael Laskey, Joseph Gonzalez, and Ken Goldberg.  Untangling dense knots by learning task-relevant keypoints.  In Conference on Robot Learning, 2020.
  * [14] Priya Sundaresan, Jennifer Grannen, Brijen Thananjeyan, Ashwin Balakrishna, Michael Laskey, Kevin Stone, Joseph Gonzalez, and Ken Goldberg.  Learning rope manipulation policies using dense object descriptors trained on synthetic depth data.  ICRA, 2020.
  * [15] Weifu Wang, Dmitry Berenson, and Devin Balkcom.  An online method for tight-tolerance insertion tasks for string and rope.  ICRA, 2015.
  * [16] Daniel Sánchez, Weiwei Wan, and Kensuke Harada.  Tethered tool manipulation planning with cable maneuvering.  IEEE Robotics and Automation Letters, 2019.
  * [17] Peter Mitrano, Dale McConachie, and Dmitry Berenson.  Learning Where to Trust Unreliable Models in an Unstructured World for Deformable Object Manipulation.  Science Robotics, 2021.
  * [18] Dale McConachie, Thomas Power, Peter Mitrano, and Dmitry Berenson.  Learning When to Trust a Dynamics Model for Planning in Reduced State Spaces.  IEEE Robotics and Automation Letters, 2020.
  * [19] Peter Mitrano and Dmitry Berenson.  Data augmentation for manipulation.  RSS, 2022.
  * [20] Peter Mitrano, Alex LaGrassa, Oliver Kroemer, and Dmitry Berenson.  Focused adaptation of dynamics models for deformable object manipulation.  ICRA, 2023.
  * [21] Jeffrey Mahler, Florian T. Pokorny, Brian Hou, Melrose Roderick, Michael Laskey, Mathieu Aubry, Kai Kohlhoff, Torsten Kröger, James J. Kuffner, and Ken Goldberg.  Dex-net 1.0: A cloud-based network of 3d objects for robust grasp planning using a multi-armed bandit model with correlated rewards.  In ICRA, 2016.
  * [22] Jeffrey Mahler, Jacky Liang, Sherdil Niyaz, Michael Laskey, Richard Doan, Xinyu Liu, Juan Aparicio Ojea, and Ken Goldberg.  Dex-net 2.0: Deep learning to plan robust grasps with synthetic point clouds and analytic grasp metrics.  In Robotics: Science and Systems, 2017.
  * [23] Ryan Hoque, Daniel Seita, Ashwin Balakrishna, Aditya Ganapathi, Ajay Kumar Tanwani, Nawid Jamali, Katsu Yamane, Soshi Iba, and Ken Goldberg.  Visuospatial foresight for multi-step, multi-task fabric manipulation.  RSS, 2020.
  * [24] Xingyu Lin, Yufei Wang, Zixuan Huang, and David Held.  Learning visible connectivity dynamics for cloth smoothing.  Conference on Robot Learning, 2021.
  * [25] Yilin Wu, Wilson Yan, Thanard Kurutach, Lerrel Pinto, and P. Abbeel.  Learning to manipulate deformable objects without demonstrations.  ArXiv, abs/1910.13439, 2019.
  * [26] Fan Zhang and Y. Demiris.  Learning garment manipulation policies toward robot-assisted dressing.  Science Robotics, 2022.
  * [27] Thierry Siméon, Jean-Paul Laumond, Juan Cortés, and Anis Sahbani.  Manipulation planning with probabilistic roadmaps.  IJRR, 2004.
  * [28] Eric W Weisstein.  Fan graph.  MathWorld – Wofram Web Resource.
  * [29] Aric A. Hagberg, Daniel A. Schult, and Pieter J. Swart.  Exploring network structure, dynamics, and function using networkx.  Python in Science Conference, 2008.
  * [30] Grady Williams, Paul Drews, Brian Goldfain, James M. Rehg, and Evangelos A. Theodorou.  Aggressive driving with model predictive path integral control.  ICRA, 2016.
  * [31] Emanuel Todorov, Tom Erez, and Yuval Tassa.  Mujoco: A physics engine for model-based control.  In IROS, 2012.
  * [32] Sheng Zhong, Zhenyuan Zhang, Nima Fazeli, and Dmitry Berenson.  TAMPC: A controller for escaping traps in novel environments.  RA-L, 2021.
  * [33] David Coleman, Ioan A. Șucan, Sachin Chitta, and Nikolaus Correll.  Reducing the barrier to entry of complex robotic software: a moveit! case study.  Journal of Software Engineering for Robotics, 2014.
  * [34] Dmitry Berenson.  Manipulation of deformable objects without modeling and simulating deformation.  In IROS, 2013.
  * [35] Yixuan Wang, Dale McConachie, and Dmitry Berenson.  Tracking Partially-Occluded Deformable Objects while Enforcing Geometric Constraints.  ICRA, 2021.