# NeW CRFs: Neural Window Fully-connected CRFs for Monocular Depth Estimation

Weihao Yuan Xiaodong Gu Zuozhuo Dai Siyu Zhu Ping Tan
Alibaba Group

###### Abstract

Estimating the accurate depth from a single image is challenging since it is
inherently ambiguous and ill-posed. While recent works design increasingly
complicated and powerful networks to directly regress the depth map, we take
the path of CRFs optimization. Due to the expensive computation, CRFs are
usually performed between neighborhoods rather than the whole graph. To
leverage the potential of fully-connected CRFs, we split the input into
windows and perform the FC-CRFs optimization within each window, which reduces
the computation complexity and makes FC-CRFs feasible. To better capture the
relationships between nodes in the graph, we exploit the multi-head attention
mechanism to compute a multi-head potential function, which is fed to the
networks to output an optimized depth map. Then we build a bottom-up-top-down
structure, where this neural window FC-CRFs module serves as the decoder, and
a vision transformer serves as the encoder. The experiments demonstrate that
our method significantly improves the performance across all metrics on both
the KITTI and NYUv2 datasets, compared to previous methods. Furthermore, the
proposed method can be directly applied to panorama images and outperforms all
previous panorama methods on the MatterPort3D dataset. 111Project page:
https://weihaosky.github.io/newcrfs

##  1 Introduction

Depth prediction is a classical task in computer vision and is essential for
numerous applications such as 3D reconstruction, autonomous driving, and
robotics [13, 8, 42, 41]. Such a vision task aims to estimate the depth map
from a single color image, which is an ill-posed and inherently ambiguous
problem since infinitely many 3D scenes can be projected to the same 2D scene.
Therefore, this task is challenging for traditional methods [22, 23, 30],
which are usually limited to low-dimension and sparse distances [22], or known
and fixed objects [23].

Recently, many works have employed the deep networks to directly regress the
depth maps and achieved good performances [6, 17, 1, 18, 7, 2]. Nevertheless,
since there are no geometric constraints of multi-view [9, 40, 43] to exploit,
the focus of most works is designing more powerful and more complicated
networks. This renders this task a difficult fitting problem without the help
of other guidance.

In traditional monocular depth estimation, some methods build the energy
function from Markov Random Fields (MRFs) or Conditional Random Fields (CRFs)
[30, 31, 37]. They exploit the observation cues, such as the texture and
position information, along with the last prediction to build the energy
function, and then optimize this energy to obtain a depth prediction. This
approach is demonstrated to be effective in guiding the estimation of the
depth, and is also introduced in some deep methods [20, 11, 29, 38]. However,
they are all limited in neighbor CRFs rather than fully-connected CRFs (FC-
CRFs) due to the expensive computation, while the fully-connected CRFs capture
the relationship between any node in a graph and are much stronger.

Figure 1: The neural window fully-connected CRFs take image feature
$\mathcal{F}$ and upper-level prediction $X$ as input, and compute the fully-
connected energy $E$ in each window, which is then fed to the networks to
output an optimized depth map.

To address the above challenge, in this work we segment the input to multiple
windows, and build the fully-connected CRFs energy within each window, in
which way the computation complexity is reduced considerably and the fully-
connected CRFs becomes feasible. To capture more relationships between the
nodes in the graph, we exploit the multi-head attention mechanism [35] to
compute the pairwise potential of the CRFs, and build a new neural CRFs
module, as is shown in Figure 1. By employing this neural window FC-CRFs
module as decoder, and a vision transformer as encoder, we build a
straightforward bottom-up-top-down network to estimate the depth. To make up
for the isolation of each window, a window shift action [21] is performed, and
the lack of global information in these window FC-CRFs is addressed by
aggregating the global features from global average pooling layers [45].

In the experiments, our method is demonstrated to outperform previous methods
by a significant margin on both the outdoor dataset, KITTI [8], and the indoor
dataset, NYUv2 [32]. Although the state-of-the-art performance on KITTI and
NYUv2 has been saturated for a while, our method further reduces the errors
considerably on both datasets. Specifically, the Abs-Rel error and the RMS
error of KITTI are decreased by $10.3\%$ and $9.8\%$, and that of NYUv2 are
decreased by $7.8\%$ and $8.2\%$. Our method now ranks first among all
submissions on the KITTI online benchmark. In addition, we evaluate our method
on the panorama images. As is well-known, the networks designed for
perspective images usually perform poorly on the panorama dataset [34, 36, 14,
33]. Remarkably, our method also sets a new state-of-the-art performance on
the panorama dataset, MatterPort3D [3]. This demonstrates that our method can
handle the common scenarios in the monocular depth prediction task.

The main contributions of this work are then summarized as follows:

$\bullet$ We split the input image into sub-windows and perform fully-
connected CRFs optimization within each window, which reduces the high
computation complexity and makes the FC-CRFs feasible.

$\bullet$ We employ the multi-head attention to capture the pairwise
relationships in the window FC-CRFs, and embed this neural CRFs module in a
network to serve as the decoder.

$\bullet$ We build a new bottom-up-top-down network for monocular depth
estimation and show a significant improvement of the monocular depth across
all metrics on KITTI, NYUv2, and MatterPort3D datasets.

##  2 Related Work

###  2.1 Traditional Monocular Depth Estimation

Prior to the emergence of deep learning, monocular depth estimation is a
challenging task. Many published works limit themselves in either estimating
1-D distances of obstacles [22] or limited in several known and fixed objects
[23]. Then Saxena et al. [30] claim that local features alone are insufficient
to predict the depth of a pixel, and the global context of the whole image
needs to be considered to infer the depth. Therefore, they use a
discriminatively-trained Markov Random Field (MRF) to incorporate multiscale
local and global image features, and model both depths at individual pixels as
well as the relation between depths at different pixels. In this way, they
infer good depth maps from the monocular cues like colors, pixel positions,
occlusion, known object sizes, haze, defocus, etc. Since then, MRFs [31] and
CRFs [37] have been well used in monocular depth estimation in traditional
methods. However, the traditional approaches still suffer from estimating
accurate high-resolution dense depth maps.

###  2.2 Neural Networks Based Monocular Depth

In monocular depth estimation, neural network based methods have dominated
most benchmarks. There are mainly two kinds of approaches for learning the
mapping from images to depth maps. The first approach directly regresses the
continuous depth map from the aggregation of the information in an image [6,
26, 17, 39, 1, 12, 18, 28]. In this approach, coarse and fine networks are
first introduced in [6] and then improved by multi-stage local planar guidance
layers in [17]. A bidirectional attention module is proposed in [1] to utilize
the feed-forward feature maps and incorporate the global context to filter out
ambiguity. Recently, more methods have begun to employ vision transformers to
aggregate the information of images [28]. The second approach tries to
discretize the depth space and convert the depth prediction to a
classification or ordinal regression problem [7, 2]. A spacing-increasing
quantization strategy is used in [7] to discretize the depth space more
reasonably. Then, an adaptive bins division is computed by the neural networks
for better depth quantization. Also, other approaches bring in auxiliary
information to help the training of the depth network, such as sparse depth
[10] or segmentation information [44, 24, 15, 27]. All these approaches try to
directly regress the depth map from the image feature, which falls into a
difficult fitting problem. The structures of their networks become
increasingly complex. In contrast to these works, we build an energy with the
fully-connected CRFs, and then optimize this energy to obtain a high-quality
depth map.

###  2.3 Neural CRFs for Monocular Depth

Since the graph models, like MRFs and CRFs, are effective in traditional depth
estimation, some methods try to embed them into neural networks [19, 20, 11,
29, 38]. These methods regard the patches of pixels as nodes and perform the
graph optimization. One such approach first uses networks to regress a coarse
depth map and then utilizes CRFs to refine it [19], where the post-processing
function of CRFs is proven to be effective. However, the CRFs are separated
from neural networks. To better combine CRFs and networks, other methods
integrate CRFs into the layers of the neural networks and train the whole
framework end-to-end [20, 11, 29, 38]. But they are all limited to CRFs rather
than fully-connected CRFs due to the high computation complexity.

In this work, different from previous methods, we split the whole graph into
multiple sub-windows, such that the fully-connected CRFs become feasible.
Also, inspired by recent works in vision transformer[35, 5, 21], we use the
multi-head attention mechanism to capture the pairwise relationship in FC-CRFs
and propose a neural window fully-connected CRFs module. This module is
embedded into the network to play the role of the decoder, such that the whole
framework can be trained end-to-end.

##  3 Neural Window Fully-connected CRFs

Figure 2: Graph model of fully-connected CRFs and window fully-connected CRFs.
In a fully-connected CRFs graph (a), taking the orange node as an example, it
is connected to all other nodes in the graph. In a window fully-connected
CRFs, however, the orange node is only connected to all other nodes within one
window. Figure 3: Network structure of the proposed framework. The encoder
first extracts the features in four levels. A PPM head aggregates the global
and local information and makes the initial prediction $X$ from the top image
feature $\mathcal{F}$. Then in each level, the neural window fully-connected
CRFs module builds multi-head energy from $X$ and $\mathcal{F}$, and optimizes
it to a better prediction $X^{\prime}$. Between each level a rearrange upscale
is performed considering the sharpness and network weight.

This section first introduces the window fully-connected CRFs, followed by its
integration with neural networks. Afterward, the network structure is
displayed, where the neural window FC-CRFs module is embedded into a top-down-
bottom-up network to serve as the decoder.

###  3.1 Fully-connected Conditional Random Fields

In traditional methods, Markov random fields (MRFs) or conditional random
fields (CRFs) are leveraged to handle dense prediction tasks such as monocular
depth estimation [30] and semantic segmentation [4]. They are shown to be
effective in correcting the erroneous predictions based on the information of
the current and adjacent nodes. Specifically, in a graph model, these methods
favor similar label assignments to nodes that are proximal in space and color.

Thus, in this work we employ CRFs to help the depth prediction. Since the
depth prediction of the current pixel is determined by long-range pixels in
one image, to increase the receptive field, we use fully-connected CRFs [16]
to build the energy. In a graph model, the energy function of the fully-
connected CRFs is usually defined as

$E(\mathbf{x})=\sum_{i}\psi_{u}(x_{i})+\sum_{ij}\psi_{p}(x_{i},x_{j}),$ (1)

where $x_{i}$ is the predicted value of node $i$, and $j$ denotes all other
nodes in the graph. The unary potential function $\psi_{u}$ is computed for
each node by the predictor according to the image features.

The pairwise potential function $\psi_{p}$ connects pairs of nodes as

$\psi_{p}=\mu(x_{i},x_{j})f(x_{i},x_{j})g(I_{i},I_{j})h(p_{i},p_{j}),$ (2)

where $\mu(x_{i},x_{j})=1$ if $i\neq j$ and $\mu(x_{i},x_{j})=0$ otherwise,
$I_{i}$ is the color of node $i$, $p_{i}$ is the position of node $i$. The
pairwise potential usually considers the color and position information to
enforce some heuristic punishments, which make the predicted values
$x_{i},x_{j}$ more reasonable and logical.

In regular CRFs, the pairwise potential only computes the edge connection
between the current node and neighboring nodes. In fully-connected CRFs,
however, the connections between the current node and any other nodes in a
graph need to be computed, as shown in Figure 2 (a).

###  3.2 Window Fully-connected CRFs

Although the fully-connected CRFs can bring global-range connections, its
disadvantage is also obvious. On the one hand, the number of edges connecting
all pixels in an image is large, which makes the computation of this kind of
pairwise potential quite resource-consuming. On the other hand, the depth of a
pixel is usually not determined by distant pixels. Only pixels within some
distance need to be considered.

Therefore, in this work we propose the window-based fully-connected CRFs. We
segment an image into multiple patch-based windows. Each window includes
$N\times N$ image patches, of which each patch is composed of $n\times n$
pixels. In our graph model, each patch rather than each pixel is regarded as
one node. All patches within one window are fully-connected with edges, while
the patches of different windows are not connected, as displayed in Figure 2
(b). In this case, the computation of pairwise potential only considers the
patches within one window, so that the computation complexity is reduced
significantly.

Taking an image with $h\times w$ patches as an example, the computation
complexity of FC-CRFs and window FC-CRFs for one iteration are

$\displaystyle\Omega(\text{FC-CRFs})=$ $\displaystyle\
hw\times\Omega(\psi_{u})+hw(hw-1)\times\Omega(\psi_{p})$ (3)
$\displaystyle\Omega(\text{Window FC})=$ $\displaystyle\
hw\times\Omega(\psi_{u})+hw(N^{2}-1)\times\Omega(\psi_{p}),$

where $N$ is the window size, $\Omega(\mu_{u})$ and $\Omega(\mu_{p})$ are the
computation complexity of one unary potential and one pairwise potential,
respectively.

In the window fully-connected CRFs, all windows are non-overlapped, which
means there is no information connection between any windows. The adjacent
windows, however, are physically connected. To resolve the isolation of
windows, we shift the windows by $(\frac{N}{2},\frac{N}{2})$ patches in the
image and calculate the energy function of shifted windows after computing
that of the original windows, similar to swin-transformer [21]. In this way,
the isolated neighboring pixels are connected in the shifted windows. Hence,
each time we calculate the energy function, we calculate two energy functions
successively, one for the original windows and the other one for the shifted
windows.

Input image

DORN

Ours

Error map

Figure 4: Qualitative results on the KITTI online benchmark, which are
generated by the online server.

###  3.3 Neural Window FC-CRFs

In traditional CRFs, the unary potential is usually acted by a distribution
over the predicted values, e.g.,

$\psi_{u}(x_{i})=-\log P(x_{i}|I),$ (4)

where $I$ is the input color image and $P$ is the probability distribution of
the value prediction. The pairwise potential is usually computed according to
the colors and positions of pixel pairs, e.g.,

$\psi_{p}(x_{i},x_{j})=\mu(x_{i},x_{j})||x_{i}-x_{j}||e^{-\frac{||I_{i}-I_{j}||}{2\sigma^{2}}}e^{-\frac{||p_{i}-p_{j}||}{2\sigma^{2}}}.$
(5)

This potential encourages distinct-color and distant pixels to have various
value predictions while punishing the value discrepancies in similar-color and
adjacent pixels.

These potential functions are designed by hands and cannot be too complicated.
Thus they are hard to represent high-dimensional information and describe
complex connections. So in this work, we propose to use neural networks to
perform the potential functions.

For the unary potential, it is computed from the image features such that it
can be directly obtained by the network as

$\psi_{u}(x_{i})=\theta_{u}(I,x_{i}),$ (6)

where $\theta$ is the parameters of a unary network.

For the pairwise potential, we realize that it is composed of values of the
current node and other nodes, and a weight computed based on the color and
position information of the node pairs. So we reformulate it as

$\psi_{p}(x_{i},x_{j})=w(\mathcal{F}_{i},\mathcal{F}_{j},p_{i},p_{j})||x_{i}-x_{j}||,$
(7)

where $\mathcal{F}$ is the feature map and $w$ is the weighting function. We
calculate the pairwise potential node by node. For each node $i$, we sum all
its pairwise potentials and obtain

$\psi_{p_{i}}=\alpha(\mathcal{F}_{i},\mathcal{F}_{j},p_{i},p_{j})x_{i}+\sum_{j\neq
i}\beta(\mathcal{F}_{i},\mathcal{F}_{j},p_{i},p_{j})x_{j},$ (8)

where $\alpha,\beta$ are the weighting functions and will be computed by the
networks.

Inspired by recent works in transformer [35, 5], we calculate a query vector
$\mathbf{q}$ and a key vector $\mathbf{k}$ from the feature map of each patch
in a window and combine vectors of all patches to matrices $Q$ and $K$. Then
we calculate the dot product of matrices $Q$ and $K$ to get the potential
weight between any pair, after which the predicted values $X$ are multiplied
by the weights to get the final pairwise potential. To introduce the position
information, we also add a relative position embedding $P$. Therefore, the
equation 8 can be calculated as

$\displaystyle\psi_{p_{i}}=$ $\displaystyle\ \text{SoftMax}(q\cdot
K^{T}+P)\cdot X$ (9) $\displaystyle\sum_{i}\psi_{p_{i}}=$ $\displaystyle\
\text{SoftMax}(Q\cdot K^{T}+P)\cdot X,$

where $\cdot$ denotes dot production. Thus, the output of the SoftMax gets the
weights $\alpha$ and $\beta$ of Equation 8. Therefore, the dot product between
$Q$ and $K$ calculates the scores between each node with any other node, which
determines the message passing weights with $P$, while the dot product between
previous prediction $X$ and the output of the SoftMax performs the message
passing.

###  3.4 Network Structure

#### Overview.

To embed the neural window fully-connected CRFs into a depth prediction
network, we build a bottom-up-top-down structure, where four levels of CRFs
optimizations are performed, as is shown in Figure 3. We embed this neural
window FC-CRFs module into the network to act as a decoder, which predicts the
next-level depth according to the coarse depth and image features. For the
encoder, we employ the swin-transformer[21] to extract the features.

For an image with the size of $H\times W$, there are four levels of image
patches for the feature extraction encoder and the CRFs optimization decoder,
from $4\times 4$ pixels to $32\times 32$ pixels. At each level, $N\times N$
patches make up a window. The window size $N$ is fixed at all levels, so there
will be $\frac{H}{4N}\times\frac{W}{4N}$ windows at the bottom level and
$\frac{H}{32N}\times\frac{W}{32N}$ windows at the top level.

#### Global Information Aggregation.

At the top level, to make up for the lack of global information of the window
FC-CRFs, we use the pyramid pooling module (PPM) [45] to aggregate the
information of the whole image. Similar to [45], we use global averaging
pooling of scales $1,2,3,6$ to extract the global information, which is then
concatenated with the input feature to map to the top-level prediction $X$ by
a convolutional layer.

#### Neural Window FC-CRFs Module.

In each neural window FC-CRFs block, there are two successive CRFs
optimizations, one for regular windows and the other one for shifted windows.
To cooperate with the transformer encoder, the window size $N$ is set to $7$,
which means each window contains $7\times 7$ patches. The unary potential is
computed by a convolutional network and the pairwise potential is computed
according to equation 9. In each CRFs optimization, multiple-head $Q$ and $K$
are calculated to obtain multi-head potentials, which can enhance the
relationship capturing ability of the energy function. From the top level to
the bottom level, a structure of $32,16,8,4$ heads is adopted. Then the energy
function is fed into an optimization network composed of two fully-connected
layers to output the optimized depth map $X^{\prime}$.

#### Upscale Module.

After the neural window FC-CRFs decoders at the top three levels, a shuffle
operation is performed to rearrange the pixels, by which the image is upscaled
from $\frac{h}{2}\times\frac{w}{2}\times d$ to $h\times w\times\frac{d}{4}$.
On the one hand, this operation increases the flow to the next level with a
larger scale without losing the sharpness like upsampling. On the other hand,
this reduces the feature dimension to lighten the subsequent networks.

#### Training Loss.

Following previous works [17, 2, 18], we use a Scale-Invariant Logarithmic
(SILog) loss proposed by [6] to supervise the training. Given the ground-truth
depth map, we first calculate the logarithm difference between the predicted
depth map and the real depth:

$\Delta d_{i}=\log\hat{d_{i}}-\log d^{*}_{i},$ (10)

where $d^{*}_{i}$ is the ground-truth depth value and $\hat{d_{i}}$ is the
predicted depth at pixel $i$.

Then for $K$ pixels with valid depth values in an image, the scale-invariant
loss is computed as

$\mathcal{L}=\alpha\sqrt{\frac{1}{K}\sum_{i}\Delta
d_{i}^{2}-\frac{\lambda}{K^{2}}(\sum_{i}\Delta d_{i})^{2}},$ (11)

where $\lambda$ is a variance minimizing factor, and $\alpha$ is a scale
constant. In our experiments, $\lambda$ is set to $0.85$ and $\alpha$ is set
to $10$ following previous works [17].

Method | cap |  Abs Rel $\downarrow$ |  Sq Rel $\downarrow$ |  RMSE $\downarrow$ |  RMSElog $\downarrow$ |  $\delta<1.25$ $\uparrow$ |  $\delta<1.25^{2}$ $\uparrow$ |  $\delta<1.25^{3}$ $\uparrow$
---|---|---|---|---|---|---|---|---
Eigen et al. [6] |  0-80m | $0.190$ | $1.515$ | $7.156$ | $0.270$ | $0.692$ | $0.899$ | $0.967$
Liu et al. [20] | 0-80m | $0.217$ | $-$ | $7.046$ | $-$ | $0.656$ | $0.881$ | $0.958$
Xu et al. [38] | 0-80m | $0.122$ | $0.897$ | $4.677$ | $-$ | $0.818$ | $0.954$ | $0.985$
DORN [7] | 0-80m | $0.072$ | $0.307$ | $2.727$ | $0.120$ | $0.932$ | $0.984$ | $0.995$
Yin et al. [39] | 0-80m | $0.072$ | $-$ | $3.258$ | $0.117$ | $0.938$ | $0.990$ | $0.998$
BTS [17] | 0-80m | $0.059$ | $0.241$ | $2.756$ | $0.096$ | $0.956$ | $0.993$ | $0.998$
PackNet-SAN [10] | 0-80m | $0.062$ | $-$ | $2.888$ | $-$ | $0.955$ | $-$ | $-$
Adabin [2] | 0-80m | $0.058$ | $0.190$ | $2.360$ | $0.088$ | $0.964$ | $0.995$ | $\mathbf{0.999}$
DPT* [28] | 0-80m | $0.062$ | $-$ | $2.573$ | $0.092$ | $0.959$ | $0.995$ | $\mathbf{0.999}$
PWA [18] | 0-80m | $0.060$ | $0.221$ | $2.604$ | $0.093$ | $0.958$ | $0.994$ | $\mathbf{0.999}$
Ours | 0-80m | $\mathbf{0.052}$ | $\mathbf{0.155}$ | $\mathbf{2.129}$ | $\mathbf{0.079}$ | $\mathbf{0.974}$ | $\mathbf{0.997}$ | $\mathbf{0.999}$
Table 1: Quantitative results on the Eigen split of KITTI dataset. Seven widely used metrics are reported. “Abs Rel” error is the main ranking metric. Note that the “Sq Rel” error is calculated in a different way here. “*” means using additional data for training. Method | dataset |  SILog $\downarrow$ |  Abs Rel $\downarrow$ |  Sq Rel $\downarrow$ |  iRMSE $\downarrow$ |  RMSE $\downarrow$ |  $\delta<1.25$ $\uparrow$ |  $\delta<1.25^{2}$ $\uparrow$ |  $\delta<1.25^{3}$ $\uparrow$
---|---|---|---|---|---|---|---|---|---
DORN [7] | val | $12.22$ | $11.78$ | $3.03$ | $11.68$ | $3.80$ | $0.913$ | $0.985$ | $0.995$
BTS [17] | val | $10.67$ | $7.51$ | $1.59$ | $8.10$ | $3.37$ | $0.938$ | $0.987$ | $0.996$
BA-Full [1] | val | $10.64$ | $8.25$ | $1.81$ | $8.47$ | $3.30$ | $0.938$ | $0.988$ | $0.997$
Ours | val | $\mathbf{8.31}$ | $\mathbf{5.54}$ | $\mathbf{0.89}$ | $\mathbf{6.34}$ | $\mathbf{2.55}$ | $\mathbf{0.968}$ | $\mathbf{0.995}$ | $\mathbf{0.998}$
DORN [7] | online test | $11.77$ | $8.78$ | $2.23$ | $12.98$ | $-$ | $-$ | $-$ | $-$
BTS [17] | online test | $11.67$ | $9.04$ | $2.21$ | $12.23$ | $-$ | $-$ | $-$ | $-$
BA-Full [1] | online test | $11.61$ | $9.38$ | $2.29$ | $12.23$ | $-$ | $-$ | $-$ | $-$
PackNet-SAN [10] | online test | $11.54$ | $9.12$ | $2.35$ | $12.38$ | $-$ | $-$ | $-$ | $-$
PWA [18] | online test | $11.45$ | $9.05$ | $2.30$ | $12.32$ | $-$ | $-$ | $-$ | $-$
Ours |  online test | $\mathbf{10.39}$ | $\mathbf{8.37}$ | $\mathbf{1.83}$ | $\mathbf{11.03}$ | $-$ | $-$ | $-$ | $-$
Table 2: Quantitative results on the official split of KITTI dataset. Eight
widely used metrics are reported for the validation set while only four
metrics are available from the online evaluation server for the test set.
“SILog” error is the main ranking metric. Our method ranks 1st among all
submissions on the KITTI depth prediction online benchmark at the submission
time of this paper.

Input image

BTS

Adabins

Ours

Ground truth

Figure 5: Qualitative results on the NYUv2 dataset. Method |  Abs Rel $\downarrow$ |  Sq Rel $\downarrow$ |  RMSE $\downarrow$ |  RMSElog $\downarrow$ |  log10 $\downarrow$ |  $\delta<1.25$ $\uparrow$ |  $\delta<1.25^{2}$ $\uparrow$ |  $\delta<1.25^{3}$ $\uparrow$
---|---|---|---|---|---|---|---|---
Liu et al. [20] | $0.230$ | $-$ | $0.824$ | $-$ | $0.095$ | $0.614$ | $0.883$ | $0.971$
Xu et al. [38] | $0.125$ | $-$ | $0.593$ | $-$ | $0.057$ | $0.806$ | $0.952$ | $0.986$
DORN [7] | $0.115$ | $-$ | $0.509$ | $-$ | $0.051$ | $0.828$ | $0.965$ | $0.992$
Yin et al. [39] | $0.108$ | $-$ | $0.416$ | $-$ | $0.048$ | $0.875$ | $0.976$ | $0.994$
BTS [17] | $0.110$ | $0.066$ | $0.392$ | $0.142$ | $0.047$ | $0.885$ | $0.978$ | $0.994$
DAV [12] | $0.108$ | $-$ | $0.412$ | $-$ | $-$ | $0.882$ | $0.980$ | $0.996$
PackNet-SAN* [10] | $0.106$ | $-$ | $0.393$ | $-$ | $-$ | $0.892$ | $0.979$ | $0.995$
Adabin [2] | $0.103$ | $-$ | $0.364$ | $-$ | $0.044$ | $0.903$ | $0.984$ | $0.997$
DPT* [28] | $0.110$ | $-$ | $0.357$ | $-$ | $0.045$ | $0.904$ | $0.988$ | $\mathbf{0.998}$
PWA [18] | $0.105$ | $-$ | $0.374$ | $-$ | $0.045$ | $0.892$ | $0.985$ | $0.997$
Ours | $\mathbf{0.095}$ | $\mathbf{0.045}$ | $\mathbf{0.334}$ | $\mathbf{0.119}$ | $\mathbf{0.041}$ | $\mathbf{0.922}$ | $\mathbf{0.992}$ | $\mathbf{0.998}$
Table 3: Quantitative results on NYUv2. “Abs Rel” and “RMSE” are the main
ranking metrics. “*” means using additional data.

##  4 Experiments

###  4.1 Implementation Details

Our work is implemented in Pytorch and experimented on Nvidia GTX 2080 Ti
GPUs. The network is optimized end-to-end with the Adam optimizer
($\beta_{1}=0.9$, $\beta_{1}=0.999$). The training runs for $20$ epochs with
the batch size of $8$ and the learning rate decreasing from $1\times 10^{-4}$
to $1\times 10^{-5}$. The output depth map of our network is of
$\frac{1}{4}\times\frac{1}{4}$ size of the original image, which is then
resized to the full resolution.

###  4.2 Datasets

KITTI dataset. KITTI dataset [8] is the most used benchmark with outdoor
scenes captured from a moving vehicle. There are two mainly used splits for
monocular depth estimation. One is the training/testing split proposed by
Eigen et al. [6] with $23488$ training image pairs and $697$ testing images.
The other one is the official split proposed by Geiger et al. [8] with $42949$
training image pairs, $1000$ validation images, and $500$ testing images. For
the official split, the ground-truth depth maps for the testing images are
withheld by the online evaluation benchmark.

NYUv2 dataset. NYUv2 [32] is an indoor datasets with $120K$ RGB-D videos
captured from $464$ indoor scenes. We follow the official training/testing
split to evaluate our method, where $249$ scenes are used for training and
$654$ images from $215$ scenes are used for testing.

MatterPort3D dataset. To verify the effectiveness of our method on more
domains, we also evaluate our method on the panorama images. MatterPort3D [3]
is the biggest real-world dataset among all widely used datasets in panorama
depth estimation. Following the official split, we use $7829$ images from $61$
houses to train our network and then evaluate the model on the merged set of
$957$ validation images and $2014$ testing images. All images are resized to
$1024\times 512$ in both training and evaluation.

Method |  Abs Rel $\downarrow$ |  Abs $\downarrow$ |  RMSE $\downarrow$ |  RMSElog $\downarrow$ |  $\delta<1.25$ $\uparrow$ |  $\delta<1.25^{2}$ $\uparrow$ |  $\delta<1.25^{3}$ $\uparrow$
---|---|---|---|---|---|---|---
OmniDepth [46] | $0.2901$ | $0.4838$ | $0.7643$ | $0.1450$ | $0.6830$ | $0.8794$ | $0.9429$
BiFuse [36] | $0.2048$ | $0.3470$ | $0.6259$ | $0.1134$ | $0.8452$ | $0.9319$ | $0.9632$
SliceNet [25] | $0.1764$ | $0.3296$ | $0.6133$ | $0.1045$ | $0.8716$ | $0.9483$ | $0.9716$
HoHoNet [33] | $0.1488$ | $0.2862$ | $0.5138$ | $0.0871$ | $0.8786$ | $0.9519$ | $0.9771$
UniFuse [14] | $0.1063$ | $0.2814$ | $0.4941$ | $0.0701$ | $0.8897$ | $0.9623$ | $0.9831$
Ours | $\mathbf{0.0906}$ | $\mathbf{0.2252}$ | $\mathbf{0.4778}$ | $\mathbf{0.0638}$ | $\mathbf{0.9197}$ | $\mathbf{0.9761}$ | $\mathbf{0.9909}$
Ours* | $\mathbf{0.0793}$ | $\mathbf{0.1970}$ | $\mathbf{0.4279}$ | $\mathbf{0.0575}$ | $\mathbf{0.9376}$ | $\mathbf{0.9812}$ | $\mathbf{0.9933}$
Table 4: Quantitative results on the Matterport3D dataset. “*” means using
additional data for training.

###  4.3 Evaluations

Evaluation on KITTI.  For outdoor scenes, we evaluate our method on the KITTI
dataset. We first perform the training and testing on the Eigen split, of
which the testing images are available so that the network can be better
tuned. The results are reported in Table 1, where we can see that our method
outperforms previous methods by a significant margin. Almost all errors are
reduced by about $10\%$. Specifically, the “Abs-Rel”, “Sq Rel”, “RMSE” and
“RMSElog” errors are decreased by $10.3\%$, $18.4\%$, $9.8\%$, and $10.2\%$,
respectively. Although our method is trained without additional data, it can
outperform previous methods trained with additional training data.

We then evaluate our method on the KITTI official split, where the testing
images are hidden. The results on the validation set and the testing set are
all presented in Table 2. The results of the testing set are cited from the
online benchmark and the results of the validation set are cited from BANet
[1]. Here we can see that our method reduces the main ranking metric, the
SILog error, markedly. Our method now ranks 1st among all submissions on the
KITTI depth prediction online server. The colorful visualizations of the
predicted depth maps and the error maps generated by the online server are
shown in Figure 4. Our method predicts cleaner and smoother depth while
maintaining sharper edges of objects, e.g., the edges of the humans.

Evaluation on NYUv2.  For indoor scenes, we evaluate our method on the NYUv2
dataset. Since the state-of-the-art performance on NYUv2 dataset has been
saturated for a while, some methods have begun to use additional data to
pretrain the model and then finetune it on NYUv2 training set [10, 28].
Differently, without any additional data, our method can significantly improve
the performance in all metrics, as is shown in Table 3. Specifically, the “Abs
Rel” error is reduced to within $0.1$ and the “$\delta<1.25^{2}$” accuracy
reaches $99\%$. This emphasizes the contribution of our method in improving
the results. The qualitative results in Figure 5 illustrate that our method
estimates better depth especially in difficult regions, such as repeated
texture, messy environment, and bad light.

Evaluation on MatterPort3D.  As is studied in previous works, directly
applying a deep network for perspective images to the standard representation
of spherical panoramas, i.e., the equirectangular projection, is suboptimal,
as it becomes distorted towards the poles [36, 14, 33, 34]. As such, methods
in this task try all kinds of ways to convert the panorama images to
distortion-free shape, e.g., the cubemap projection [36, 14], the horizontal
feature representation [33], and spherical convolutional filters [34]. In
comparison to the above-mentioned methods, we directly apply our network
designed for perspective images to the panorama images, and outperforms all
previous methods, as is presented in Table 4. Specifically, the “Abs Rel” and
“Abs” errors are decreased by $14.8\%$ and $20.0\%$.

In addition, we realize that the number of the training set of MatterPort3D is
small, so we collect more data in the real world. We use $50K$ images to
pretrain the network and then finetune it on the MatterPort3D training set,
which results in a better performance, as shown in Table 4. The model
pretrained with more data is denoted by “Ours*”. This demonstrates the
pretraining with more images can clearly boost the performance in panorama
depth estimation.

Setting | Abs Rel | Sq Rel | RMSE |  Rlog | $1.25$ | $1.25^{2}$
---|---|---|---|---|---|---
Baseline | $0.069$ | $0.256$ | $2.610$ | $0.103$ | $0.947$ | $0.993$
Neural CRFs | $0.055$ | $0.185$ | $2.322$ | $0.086$ | $0.965$ | $0.995$
\+ S | $0.054$ | $0.174$ | $2.297$ | $0.084$ | $0.968$ | $0.996$
\+ S + R | $0.054$ | $0.168$ | $2.271$ | $0.083$ | $0.970$ | $0.996$
\+ S + R + P | $0.052$ | $0.155$ | $2.129$ | $0.079$ | $0.974$ | $0.997$
8, 4, 2, 1 | $0.055$ | $0.165$ | $2.203$ | $0.083$ | $0.970$ | $0.996$
16, 8, 4, 2 | $0.054$ | $0.162$ | $2.172$ | $0.081$ | $0.972$ | $0.997$
32, 16, 8, 4 | $0.052$ | $0.155$ | $2.129$ | $0.079$ | $0.974$ | $0.997$
Table 5: Ablation study on the Eigen split of KITTI dataset. The first six
metrics of those used in Table 1 are reported here. “S” refers to window
shift, “R” refers to rearrange upscale, and “P” refers to PPM head. The last
three rows display the results of using different numbers of heads.

###  4.4 Abalation Study

To better inspect the effect of each module in our method, we evaluate each
component by an ablation study and present the results in Table 5.

Baseline vs. Neural CRFs.  To verify the effectiveness of the proposed neural
window fully-connected FC-CRFs, we build a baseline model. This model is a
well-used UNet structure with the same encoder as ours. In other words,
compared to our full method, the PPM head and the rearrange upscale are
removed, and the decoder is replaced by the well-used convolutional decoder.
Then based on this baseline, we only replace the decoder with our neural
window FC-CRFs module, and obtain a noticeable performance improvement as
shown in Table 5. The “Abs Rel” error is reduced from $0.069$ to $0.055$, and
then to $0.054$ by adding the shift action. This demonstrates the
effectiveness of the neural window FC-CRFs in estimating accurate depths.

Rearrange upscale.  On top of the basic neural FC-CRFs structure, we add the
rearrange upscale module. The performance increment gained from this module is
not large, but visually the output depth maps have sharper edges, and the
parameters of the network are reduced.

PPM head.  The PPM head aggregates the global information, which is lacking in
window FC-CRFs. This module can help in some regions that are difficult for
estimating with only local information, e.g., the complex texture and the
white walls. From the results in Table 5, we see this module contributes to
the performance of our framework.

Multi-head energy.  The CRFs energy is calculated in a multi-head manner. With
more heads, the ability of capturing the pairwise relationship would be
stronger but the weight of the network would be heavier. In previous
experiments, the numbers of the heads in four levels are set to 32, 16, 8, 4.
Here we use fewer heads to see how a lightweight structure performs. From the
results in Table 5, fewer heads lead to a small performance decrease.

##  5 Conclusion

We propose a neural window fully-connected CRFs module to address the
monocular depth estimation problem. To solve the expensive computation of FC-
CRFs, we split the input into sub-windows and calculate the pairwise potential
within each window. To capture the relationships between nodes of the graph,
we exploit the multi-head attention to compute a neural potential function.
This neural window FC-CRFs module can be directly embedded into a bottom-up-
top-down structure and serves as a decoder, which cooperates with a
transformer encoder and predicts accurate depth maps. The experiments show
that our method significantly outperforms previous methods and sets a new
state-of-the-art performance on KITTI, NYUv2, and MatterPort3D datasets.

## References

  * [1] Shubhra Aich, Jean Marie Uwabeza Vianney, Md Amirul Islam, Mannat Kaur, and Bingbing Liu.  Bidirectional attention network for monocular depth estimation.  In Proceedings of the IEEE International Conference on Robotics and Automation, pages 11746–11752, 2021.
  * [2] Shariq Farooq Bhat, Ibraheem Alhashim, and Peter Wonka.  Adabins: Depth estimation using adaptive bins.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 4009–4018, 2021.
  * [3] Angel Chang, Angela Dai, Thomas Funkhouser, Maciej Halber, Matthias Niessner, Manolis Savva, Shuran Song, Andy Zeng, and Yinda Zhang.  Matterport3d: Learning from rgb-d data in indoor environments.  arXiv preprint arXiv:1709.06158, 2017.
  * [4] Liang-Chieh Chen, George Papandreou, Iasonas Kokkinos, Kevin Murphy, and Alan L Yuille.  Deeplab: Semantic image segmentation with deep convolutional nets, atrous convolution, and fully connected crfs.  IEEE Transactions on Pattern Analysis and Machine Intelligence, 40(4):834–848, 2017.
  * [5] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al.  An image is worth 16x16 words: Transformers for image recognition at scale.  In Proceedings of the International Conference on Learning Representations, 2020.
  * [6] David Eigen, Christian Puhrsch, and Rob Fergus.  Depth map prediction from a single image using a multi-scale deep network.  In Advances in Neural Information Processing Systems, pages 2366–2374, 2014.
  * [7] Huan Fu, Mingming Gong, Chaohui Wang, Kayhan Batmanghelich, and Dacheng Tao.  Deep ordinal regression network for monocular depth estimation.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 2002–2011, 2018.
  * [8] Andreas Geiger, Philip Lenz, and Raquel Urtasun.  Are we ready for autonomous driving? the kitti vision benchmark suite.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 3354–3361. IEEE, 2012.
  * [9] Xiaodong Gu, Weihao Yuan, Zuozhuo Dai, Chengzhou Tang, Siyu Zhu, and Ping Tan.  Dro: Deep recurrent optimizer for structure-from-motion.  arXiv preprint arXiv:2103.13201, 2021.
  * [10] Vitor Guizilini, Rares Ambrus, Wolfram Burgard, and Adrien Gaidon.  Sparse auxiliary networks for unified monocular depth prediction and completion.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 11078–11088, 2021.
  * [11] Yan Hua and Hu Tian.  Depth estimation with convolutional conditional random field network.  Neurocomputing, 214:546–554, 2016.
  * [12] Lam Huynh, Phong Nguyen-Ha, Jiri Matas, Esa Rahtu, and Janne Heikkilä.  Guiding monocular depth estimation using depth-attention volume.  In Proceedings of the European Conference on Computer Vision, pages 581–597. Springer, 2020.
  * [13] Shahram Izadi, David Kim, Otmar Hilliges, David Molyneaux, Richard Newcombe, Pushmeet Kohli, Jamie Shotton, Steve Hodges, Dustin Freeman, Andrew Davison, et al.  Kinectfusion: real-time 3d reconstruction and interaction using a moving depth camera.  In Proceedings of the 24th annual ACM symposium on User interface software and technology, pages 559–568, 2011.
  * [14] Hualie Jiang, Zhe Sheng, Siyu Zhu, Zilong Dong, and Rui Huang.  Unifuse: Unidirectional fusion for 360 panorama depth estimation.  IEEE Robotics and Automation Letters, 6(2):1519–1526, 2021.
  * [15] Marvin Klingner, Jan-Aike Termöhlen, Jonas Mikolajczyk, and Tim Fingscheidt.  Self-supervised monocular depth estimation: Solving the dynamic object problem by semantic guidance.  In Proceedings of the European Conference on Computer Vision, pages 582–600. Springer, 2020.
  * [16] Philipp Krähenbühl and Vladlen Koltun.  Efficient inference in fully connected crfs with gaussian edge potentials.  Advances in Neural Information Processing Systems, 24:109–117, 2011\.
  * [17] Jin Han Lee, Myung-Kyu Han, Dong Wook Ko, and Il Hong Suh.  From big to small: Multi-scale local planar guidance for monocular depth estimation.  arXiv preprint arXiv:1907.10326, 2019.
  * [18] Sihaeng Lee, Janghyeon Lee, Byungju Kim, Eojindl Yi, and Junmo Kim.  Patch-wise attention network for monocular depth estimation.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 1873–1881, 2021.
  * [19] Bo Li, Chunhua Shen, Yuchao Dai, Anton Van Den Hengel, and Mingyi He.  Depth and surface normal estimation from monocular images using regression on deep features and hierarchical crfs.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 1119–1127, 2015.
  * [20] Fayao Liu, Chunhua Shen, and Guosheng Lin.  Deep convolutional neural fields for depth estimation from a single image.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 5162–5170, 2015.
  * [21] Ze Liu, Yutong Lin, Yue Cao, Han Hu, Yixuan Wei, Zheng Zhang, Stephen Lin, and Baining Guo.  Swin transformer: Hierarchical vision transformer using shifted windows.  arXiv preprint arXiv:2103.14030, 2021.
  * [22] Jeff Michels, Ashutosh Saxena, and Andrew Y Ng.  High speed obstacle avoidance using monocular vision and reinforcement learning.  In Proceedings of the International Conference on Machine Learning, pages 593–600, 2005.
  * [23] Takaaki Nagai, Takumi Naruse, Masaaki Ikehara, and Akira Kurematsu.  Hmm-based surface reconstruction from single images.  In Proceedings of the International Conference on Image Processing, volume 2, pages II–II. IEEE, 2002.
  * [24] Matthias Ochs, Adrian Kretz, and Rudolf Mester.  Sdnet: Semantically guided depth estimation network.  In German Conference on Pattern Recognition, pages 288–302. Springer, 2019.
  * [25] Giovanni Pintore, Marco Agus, Eva Almansa, Jens Schneider, and Enrico Gobbetti.  Slicenet: deep dense depth estimation from a single indoor panorama using a slice-based representation.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 11536–11545, 2021.
  * [26] Xiaojuan Qi, Renjie Liao, Zhengzhe Liu, Raquel Urtasun, and Jiaya Jia.  Geonet: Geometric neural network for joint depth and surface normal estimation.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 283–291, 2018.
  * [27] Siyuan Qiao, Yukun Zhu, Hartwig Adam, Alan Yuille, and Liang-Chieh Chen.  Vip-deeplab: Learning visual perception with depth-aware video panoptic segmentation.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 3997–4008, 2021.
  * [28] René Ranftl, Alexey Bochkovskiy, and Vladlen Koltun.  Vision transformers for dense prediction.  In Proceedings of the International Conference on Computer Vision, pages 12179–12188, 2021.
  * [29] Elisa Ricci, Wanli Ouyang, Xiaogang Wang, Nicu Sebe, et al.  Monocular depth estimation using multi-scale continuous crfs as sequential deep networks.  IEEE Transactions on Pattern Analysis and Machine Intelligence, 41(6):1426–1440, 2018.
  * [30] Ashutosh Saxena, Sung H Chung, Andrew Y Ng, et al.  Learning depth from single monocular images.  In Advances in Neural Information Processing Systems, volume 18, pages 1–8, 2005.
  * [31] Ashutosh Saxena, Min Sun, and Andrew Y Ng.  Make3d: Learning 3d scene structure from a single still image.  IEEE Transactions on Pattern Analysis and Machine Intelligence, 31(5):824–840, 2008.
  * [32] Nathan Silberman, Derek Hoiem, Pushmeet Kohli, and Rob Fergus.  Indoor segmentation and support inference from rgbd images.  In Proceedings of the European Conference on Computer Vision, pages 746–760. Springer, 2012.
  * [33] Cheng Sun, Min Sun, and Hwann-Tzong Chen.  Hohonet: 360 indoor holistic understanding with latent horizontal features.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 2573–2582, 2021.
  * [34] Keisuke Tateno, Nassir Navab, and Federico Tombari.  Distortion-aware convolutional filters for dense prediction in panoramic images.  In Proceedings of the European Conference on Computer Vision, pages 707–722, 2018.
  * [35] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  In Advances in Neural Information Processing Systems, pages 5998–6008, 2017.
  * [36] Fu-En Wang, Yu-Hsuan Yeh, Min Sun, Wei-Chen Chiu, and Yi-Hsuan Tsai.  Bifuse: Monocular 360 depth estimation via bi-projection fusion.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 462–471, 2020.
  * [37] Xiaoyan Wang, Chunping Hou, Liangzhou Pu, and Yonghong Hou.  A depth estimating method from a single image using foe crf.  Multimedia Tools and Applications, 74(21):9491–9506, 2015.
  * [38] Dan Xu, Wei Wang, Hao Tang, Hong Liu, Nicu Sebe, and Elisa Ricci.  Structured attention guided convolutional neural fields for monocular depth estimation.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 3917–3925, 2018.
  * [39] Wei Yin, Yifan Liu, Chunhua Shen, and Youliang Yan.  Enforcing geometric constraints of virtual normal for depth prediction.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 5684–5693, 2019.
  * [40] Weihao Yuan, Rui Fan, Michael Yu Wang, and Qifeng Chen.  Mfusenet: Robust depth estimation with learned multiscopic fusion.  IEEE Robotics and Automation Letters, 5(2):3113–3120, 2020.
  * [41] Weihao Yuan, Kaiyu Hang, Danica Kragic, Michael Y Wang, and Johannes A Stork.  End-to-end nonprehensile rearrangement with deep reinforcement learning and simulation-to-reality transfer.  Robotics and Autonomous Systems, 119:119–134, 2019.
  * [42] Weihao Yuan, Kaiyu Hang, Haoran Song, Danica Kragic, Michael Y Wang, and Johannes A Stork.  Reinforcement learning in topology-based representation for human body movement with whole arm manipulation.  In Proceedings of the IEEE International Conference on Robotics and Automation, 2019.
  * [43] Weihao Yuan, Yazhan Zhang, Bingkun Wu, Siyu Zhu, Ping Tan, Michael Yu Wang, and Qifeng Chen.  Stereo matching by self-supervision of multiscopic vision.  In Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems, pages 5702–5709. IEEE, 2021.
  * [44] Zhenyu Zhang, Zhen Cui, Chunyan Xu, Yan Yan, Nicu Sebe, and Jian Yang.  Pattern-affinitive propagation across depth, surface normal and semantic segmentation.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 4106–4115, 2019.
  * [45] Hengshuang Zhao, Jianping Shi, Xiaojuan Qi, Xiaogang Wang, and Jiaya Jia.  Pyramid scene parsing network.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 2881–2890, 2017.
  * [46] Nikolaos Zioulis, Antonis Karakottas, Dimitrios Zarpalas, and Petros Daras.  Omnidepth: Dense depth estimation for indoors spherical panoramas.  In Proceedings of the European Conference on Computer Vision, pages 448–465, 2018.


# Fast Footstep Planning on Uneven Terrain Using Deep Sequential Models

Hersh Sanghvi This work was supported by NSF grant CCF-2112665 (TILOS). School
of Engineering and Applied Science
University of Pennsylvania
Email<EMAIL_ADDRESS>Camillo Jose Taylor  School of Engineering and
Applied Science
University of Pennsylvania
Email<EMAIL_ADDRESS>
###### Abstract

One of the fundamental challenges in realizing the potential of legged robots
is generating plans to traverse challenging terrains. Control actions must be
carefully selected so the robot will not crash or slip. The high
dimensionality of the joint space makes directly planning low-level actions
from onboard perception difficult, and control stacks that do not consider the
low-level mechanisms of the robot in planning are ill-suited to handle fine-
grained obstacles. One method for dealing with this is selecting footstep
locations based on terrain characteristics. However, incorporating robot
dynamics into footstep planning requires significant computation, much more
than in the quasi-static case. In this work, we present an LSTM-based planning
framework that learns probability distributions over likely footstep locations
using both terrain lookahead and the robot’s dynamics, and leverages the
LSTM’s sequential nature to find footsteps in linear time. Our framework can
also be used as a module to speed up sampling-based planners. We validate our
approach on a simulated one-legged hopper over a variety of uneven terrains.

(a)

(b)

Figure 1: Our footstep planner in action. The green and orange surfaces
represent probability distributions over the terrain for the first and fourth
steps, respectively. Note in particular how the planner accounts for the loss
in kinetic energy on the elevated terrain.

##  I Introduction

Legged robots have significant mobility advantages over their wheeled
counterparts. They can traverse stairs, uneven terrain and other hazards that
would be impassable for more conventional ground robots. However, these
attractive dynamic capabilities come at a cost. First, legged robots with
limited perceptual lookahead must carefully plan motions to move across
potentially rough terrain without crashing. This involves developing an
effective mapping from perception to feasible actions that incorporates
terrain geometry and the robot’s high-dimensional and hybrid state dynamics.
Second, factors such as model mismatch and perception error force frequent
online replanning. These two requirements significantly constrain the possible
approaches. Searching over the full state space would certainly result in a
feasible plan, but would take far too long to be used online, while a planner
using many approximations would operate quickly, but with riskier actions.

One commonly used approach is to plan footstep locations [1, 2, 3]. Footstep
planning frames the problem as a discrete-time search and also allows the
planner to incorporate both the geometry of the terrain and the robot’s
dynamics while considerably lowering the dimensionality of the search space.
Making this search fast enough to run online in dynamic situations is still a
significant challenge.

In this paper, we develop a framework that learns from offline plans to give
explicit and interpretable probability distributions over the terrain
conditioned both on perceptual input and the robot’s dynamics for an arbitrary
number of footsteps. This distribution can be used directly through its mode
(argmax), or to speed up a sampling-based planner by suggesting informed
samples. We demonstrate the merits of our approach using a simulated one-
legged hopper on a variety of terrains. The proposed framework provides a
computationally efficient approach to relating look-ahead perception to action
for these systems.

##  II Related Work

###  II-A Graph Search and Optimization for Footstep Planning

Methods for footstep planning that do not use machine learning are typically
based on solving either graph search or optimization problems. These methods
often generate quasi-static trajectories or are too slow to be used online. On
the graph search side, [4] uses best-first search over input angles for a one-
legged robot, sampling possible leg angles at each impact to find the next
node. For multi-legged robots, [5, 6, 7, 8] use a variety of graph search
algorithms to plan only a Center of Mass (CoM) trajectory and use terrain
heuristics to find footholds along that trajectory, while [1, 9, 10]
explicitly search over footsteps based on stable stance transitions.

Approaches that use optimization often make use of some relaxation or
approximation of the underlying dynamics to speed up computation time. [11]
express step lengths as gait phases to find center-of-mass and footstep
locations using nonlinear optimization, at the cost of not enforcing some
swing foot collisions. [12] formulates footstep planning as a mixed-integer
quadratic program and can solve for short footstep plans in under a second,
but does not consider the robot dynamics. [13] uses a convex relaxation of the
dynamics in order to generate 2 to 4 step plans in roughly one second. [2, 14]
consider more complete dynamic models but the whole body optimizations take
minutes to solve. Most of these optimization schemes could benefit from an
independent system for initializing the footstep locations which our method
could provide.

###  II-B Learning for Footstep Planning

Researchers have also utilized learning-based methods to plan footstep
locations. One popular method is to use Reinforcement Learning (RL) and learn
a policy from visual inputs to select the optimal next footstep or action [15,
16, 17, 18, 19]. These methods can leverage the full robot model, but usually
only plan footsteps or motion primitives over a short horizon, and sometimes
rely on hand-selected terrain features in the reward function. Variational
Autoencoders have also been explored for footstep planning to deal with
multimodality: the fact that there are many feasible choices for steps,
depending on the desired behavior [20].

Another approach is to incorporate learned modules into the more traditional
planning frameworks. Previous methods include learning cost functions to speed
up optimization or search [21, 22] learning forward dynamics models [23],
adaptation of next footholds based on visual information and heuristics [24,
25], and direct regression of footsteps [26].

Recurrent Neural Networks (RNNs) are an interesting architecture for this
problem as they naturally handle the sequential, discrete-time nature of the
problem. While RNNs have been used in policies for blind low-level control of
legged robots [27] and in other planning domains [28, 29], to the authors’
knowledge this is the first application of RNNs to the footstep planning
problem. Our framework has a number of advantages over other learned footstep
planners: no terrain heuristics are used for training, the plan can be
arbitrarily long up to the visual horizon, multimodality is handled by
outputting a probability density map over all possible step locations, and it
can be used as a sub-module in a traditional sampling planner.

##  III Problem Formulation and Approach

We envision a scenario where a legged robot has a limited perceptual lookahead
and must plan its steps in order to cross the terrain in front of it without
crashing. Specifying these step locations can provide enough information to
generate a corresponding CoM trajectory [1]. The locations of the footsteps
must be carefully chosen to be reachable while also avoiding collisions.

First, we set up our problem by describing the dynamics of our simulated
robots. Next, we establish two baseline search-based planners that search for
footsteps over broken terrain while respecting the dynamics. We then show how
we can use these planners to train a recurrent model to output similar plans
in a fraction of the computational time. Lastly, we demonstrate the
performance of our recurrent planner on a variety of terrains.

##  IV Modeling

###  IV-A Spring-Loaded Inverted Pendulum

For our work, we consider the classic planar Spring Loaded Inverted Pendulum
(SLIP) hopper [30]: a one legged machine modeled as a massless, spring-loaded
leg and foot attached to a point mass body. This model is used as a template
[31] to plan trajectories of higher degree of freedom robots such as bipeds
[32].

The SLIP hopper is a hybrid system with two modes. When the hopper is in the
flight mode, the foot is not touching the ground and the only force
experienced by the body is gravity. When the hopper is in the stance mode, the
foot is in contact with the ground and the body experiences gravity and a
spring force acting through the leg. The instantaneous transition from stance
to flight is referred to as liftoff, and the transition from flight to stance
is touchdown.

Figure 2: A typical SLIP hopper trajectory

The passive SLIP model has one degree of freedom: the angle of the leg with
respect to the ground. This input is applied at the apex of flight, where the
vertical velocity is 0, and will affect the body’s trajectory during the
following stance phase by controlling the tradeoff between apex height and
forward velocity. The touchdown transition occurs when the foot makes contact
with the ground. A prototypical trajectory for the SLIP hopper is shown in
Figure 2. For the full dynamical equations, we refer the reader to [33], whose
formulation we used for this work.

An important property of the SLIP model is that there is no closed form
solution for the stance phase dynamics, requiring either an approximation or
explicit forward integration in order to calculate the next state after
applying a control input [34].

###  IV-B SLIP Failure Cases

Although the passive SLIP models are relatively simplistic, there are a number
of failure cases that make planning for the SLIP hopper nontrivial over broken
terrain. The first is the standard kinematic case where the body collides with
the terrain, or the foot collides with a vertical surface. Second, the leg
angle can exit the friction cone during stance phase, causing the foot to
slip. Third, if the hopper’s apex height is too high above the terrain, the
spring will fully compress during touchdown and will bottom-out, also causing
a crash. Finally, because the energy of the passive SLIP model is fixed, there
is an inverse relationship between the apex velocity and apex height. If the
hopper travels too fast, the apex height will not be sufficient for the foot
to swing to its position for the next step, causing the robot to ”trip” on the
ground.

The intersection of the kinematically feasible and dynamically reachable sets
of footsteps is not immediately apparent just by analyzing the terrain.
Therefore, when planning a trajectory, one must either precompute a set of
feasible motion primitives for varying terrains, perform search by sweeping
over control inputs and simulating the dynamics, or solve a nonlinear
optimization problem.

##  V Baseline Planners

###  V-A Angle-space Planner

We formulate our first baseline planner as a best-first search over a tree
that is dynamically constructed by sampling the possible actions at each leaf,
adapted from the approach in [4]. Each node $N$ is a tuple
$(a,x,\theta,P,c,\\{C_{1}...C_{N}\\})$, where $a$ is the apex state at which
the leg angle $\theta$ is applied to reach $x$, the footprint of the CoM at
the start of the subsequent stance phase. The other terms contain information
about the graph structure. $P$ is the parent of $N$, $c$ is the cost of $N$,
and $\\{C_{1}...C_{N}\\}$ is the list of the children of $N$.

Our search algorithm begins with a root node, which is the inevitable
touchdown point from the initial apex. From that node, we sample all the
available actions and simulate the dynamics equations. If an action does not
result in one of the failure cases outlined in Section IV-B, a node
corresponding to the current apex state and subsequent touchdown location is
added to the tree as a leaf. Afterwards, the node with the lowest cost is
fetched from a priority queue and expanded. This process repeats until a
desired number of nodes exceed the goal distance. We refer to this planner as
the ”Angle-space” planner. Pseudocode for this algorithm is shown in Algorithm
1.

1

Inputs : Initial apex state $a$, terrain model $t$, goal $g$, cost function
$h$, forward model $f$, branching factor $B$, desired number of sequences $d$

Output : Up to $d$ sequences of feasible touchdown locations

2 Set $N_{\text{root}}=(a,\,x_{0})$;

3 Initialize empty priority queue $q$;

4 $N_{s}$ $\leftarrow$ $N_{root}$;

5 while  _# successful solns $<$ $d$ and q not empty_ do

6 $a_{s}=N_{s}.a$;

7 Generate $\\{\theta_{1},...,\theta_{B}\\}$ within friction limits of $t$;

8 for  _$i=1$ to $B$_ do

9 if  _successful( f $(a_{s},\,t,\,\theta_{i}$))_ then

10 $a_{s+1},x_{s+1}\leftarrow f(a_{s},\,t,\,\theta_{i})$;

11 $c\leftarrow h(x_{s+1})$;

12 $N_{s+1}\leftarrow(a_{s+1},x_{s+1},\theta_{i},N_{s},c,\\{\\})$;

13 Add $N_{s+1}$ as a child of $N_{s}$;

14 Add $N_{s+1}$ to $q$;

15

16

17 end for

18 $N_{s}\leftarrow q.$pop();

19 if  _atGoal( $N_{s},\,g$)_ then

20 # successful solns++;

21 Add $N_{s}$ to goal list;

22 $N_{s}\leftarrow q.$pop();

23

24

25 end while

26for  _$N$ in goal list_ do

27 Output all $x$ on the path from $N_{root}$ to $N$;

28

29 end for

Algorithm 1 Angle-space Planner

To evaluate the cost of each transition, we use a function that takes the
child node as input. This cost function is formulated as

$\displaystyle
h(N_{i})=w_{1}|x_{i}-x^{\prime}|+w_{2}|\dot{x}_{i}|+w_{3}D(N_{i-1},N_{i},N_{i+1})$
(1)

Where $x_{i}$ is the node $N_{i}$’s location and $x^{\prime}$ is the goal
location. This cost function penalizes the distance of the node to the goal,
high node apex velocity, and the node’s ”isolation”.
$D(N_{i-1},N_{i},N_{i+1})$ is a function calculating the spread between the
nearest neighbors of $N_{i}$. If the $N_{i}$ obtained by applying $\theta_{i}$
is far away from from its closest fellow child, that means a small deviation
from $\theta_{i}$ is more likely to cause a crash in the presence of
obstacles. $(w_{1},w_{2},w_{3})$ are the relative weights of these terms.

###  V-B Low-level Controller

While the planner shown in Algorithm 1 also produces the input angles
necessary to hit the footstep sequence it outputs, it is inadvisable to use
these in practice, since the open-loop angles will be incorrect as soon as
there is any deviation from the reference sequence. Our approach is similar in
spirit to [35]; we train a simple Multi-Layer Perceptron (MLP) that is called
once per apex. The training data for the MLP is generated by gridding over the
space of current velocity $\dot{x}$, height $z$, and leg angle $\theta$, and
running a simulation to obtain the resulting step length $x_{L}$. Then,
$\dot{x},\,z,\,\text{and}\,x_{L}$ are fed as inputs to the MLP and the output
is the required leg angle $\theta$.

Naturally, the learned controller does not perfectly achieve the desired step
lengths. It can produce errors of up to 0.5m on our simulated robot, since at
high velocities small angle errors can cause large position errors.

###  V-C Step-space Planner

One fault of the planner shown in Algorithm 1 is that it has no knowledge of
the underlying controller and will output sequences that are physically
achievable by the robot, but may cause significant errors if provided as
inputs to the actual system consisting of an imperfect controller composed
with the dynamics.

To incorporate the controller model, we alter the sampling procedure used in
line 6 of Algorithm 1. Instead of directly generating leg angles, we instead
generate a grid of possible step lengths ${x_{L}}$, pass those with the
current apex state into the controller to obtain the desired $\theta$, and use
it in the planning algorithm. The branching factor for this variant
corresponds to the size and spacing of the grid ${x_{L}}$. The final sequence
output by this modified planner uses the sampled step lengths $x_{L}$, as
those feedforward inputs are known to result in feasible actions when input to
the controller. This approach has the advantage that steps that encounter
terrain obstacles can be avoided a priori, but requires a model for the low-
level controller which is not always known in practice. We refer to this
modification as the ”Step-space planner”.

##  VI Learned Recurrent Planner

Figure 3: A diagram of our LSTM framework unrolled over time

Both of the search planners described in the previous section operate too
slowly to be used online with frequent replanning. For a fast, online footstep
planner, we instead use a learned sequential framework to generate plans that
mimic the ones output by the search planners.

We use a Long Short-term Memory network [36] (LSTM), a variant of RNNs, as the
core of our learned planner, with a Convolutional Neural Network (CNN) that
jointly processes the terrain and previous step location to create an encoded
vector as input to the LSTM.

Just like in sentence completion (for which RNNs are widely used), a large
history of footstep sequences over a wide variety of terrains and initial
apexes induces a probability distribution over possible next step locations:
$p(s_{i}|t,a,s_{0},...,s_{i-1})$, where $t$ is a discretized encoding of the
perceived terrain, $a$ is the initial apex prior to step $s_{0}$, and
$s_{0},...,s_{i-1}$ are the past steps. This distribution can be used for
planning either by sampling next nodes from the distribution as in [28, 37],
or by taking the mode of the distribution as the next footfall location.

All together, our full LSTM-CNN model is governed by the following equations:

$\displaystyle h_{0}$ $\displaystyle=g_{0}(a)$ $\displaystyle v_{i}$
$\displaystyle=\text{CNN}([\hat{t},\hat{s}_{i-1}])$
$\displaystyle\hat{s}_{i},h_{i}$ $\displaystyle=\text{LSTM}(h_{i-1},v_{i})$

Where $h_{0}$ is the initial apex $a$ projected onto the hidden state space of
the LSTM by $g_{0}$, a single linear layer. $v_{i}$ is the encoded input
vector, calculated by the CNN by processing the previous step $\hat{s}_{i-1}$
and a discretized array representation of the terrain $\hat{t}$. In a typical
call to the LSTM planner, $s_{0}$ is the inevitable touchdown location at the
current apex, and it contains a ”1” at some location and ”0” everywhere else
because its location is fixed. However, the future steps $\hat{s}_{1:n}$ used
for recurrent planning are uncertain, so they are nontrivial discrete
probability densities. For a cell in the heightmap $\hat{t}$ with index $j$,
$\hat{s}_{i}[j]$ is the probability that the $i$-th step lands on $j$. A
diagram of our model is shown in Figure 3.

Also, since the steps $\hat{s}$ share the same underlying support as the
heightmap $\hat{t}$, finding the correct step location becomes a
classification problem among the discrete cells. By encoding the step location
in the terrain, the CNN can use co-located visual features to process both
together as channels of a single image.

The LSTM architecture allows the learned planner to capture the behavior of
the hopper over time without requiring simulation of the forward dynamics,
which is a key to handling the complex dynamics of the system without
excessive computation. Meanwhile the CNN allows the planner to extract
relevant terrain features and to marry that with an aligned representation of
the planned footsteps.

###  VI-A LSTM-Guided Sampling

We can also modify the Step-space planner to sample next footsteps from the
output probability distribution of the LSTM instead of from a fixed grid. To
generate these samples, we fetch the path from the root node to the current
node, and pass the path into the LSTM as the past steps, along with the
initial apex and terrain.

Sampling from the output of the LSTM allows us to reduce the required
branching factor of the Step-space planner by sampling from an informed
distribution, while also incorporating a model of the controller into the LSTM
planner. We use temperature scaling [38] to widen the output distribution and
make it more suitable for sampling.

##  VII Experiments

We test our approach on the robot described in Section IV. For all
experiments, we use a hopper whose body mass is 7kg, leg length is 0.5m, and
spring constant is 3200 $Nm^{-1}$. For simulation, we use a custom simulation
of the SLIP model with a timestep of 0.01 seconds. All of the sequence
generation, model training, experiments, and simulations were done in Python
on a machine with an AMD Ryzen 9 3600 processor with 32 GB of RAM and an
NVidia RTX 2080 Super GPU.

Our LSTM model contains 2 layers each of 110 hidden units, and the input CNNs
use 2 layers of 7x1 filters before being encoded into a 110-dimensional
feature vector that acts as input to the LSTM, making our overall architecture
relatively small. Because we frame planning as a classification problem, we
use Cross-Entropy Loss to train our model.

###  VII-A Training

We generate training data for our LSTM by running the Angle-space planner with
the parameters described in Table I. A single run of the Angle-space planner
can give multiple training sequences as any path from the root node to a leaf
is a feasible sequence of footsteps. In order to still provide reasonably good
training sequences, we only add sequences that make a certain amount of
progress towards the goal to the training set. We use the Angle-space planner
instead of the Step-space planner to prevent the LSTM from overfitting to the
performance of any particular low-level controller.

Each terrain is either a ditches or steps scenario. We model the terrain 8
meters in front of the robot and 3 meters behind, discretized in segments of
10cm. We also use a lower coefficient of friction during training in order to
encourage further robustness by the LSTM. This process generates roughly
50,000 sequences of varying lengths (although a few of the sequences on the
same terrain are usually highly similar to each other) and takes 1.5 hours
with multithreading.

###  VII-B Testing

Our testing data consists of 15 random ditch-world and step-world terrains
coupled with 5 different initial states swept over varying initial velocities
(150 total test cases). Given that the train and test sets use completely
random terrains and initial states, it is highly unlikely that any of the test
terrains appear in the training set. The coefficient of friction used for all
the test experiments is 0.8. Similar to training, the goal for the robot is to
cross a certain $x$ threshold, set to 10 meters.

TABLE I: Training dataset generation parameters Parameter | Value
---|---
# different terrains | 360
# initial states per terrain | 8
Min # steps | 8
# desired goal sequences per instance | 8
Branching Factor | 15
Coefficient of friction | 0.6
$w_{0}$, $w_{1}$, $w_{2}$ | 1, 1, 2

We test 5 different planners: the Angle-space planner, Step-space planner,
LSTM planner, LSTM-Guided sampling planner, and a terrain-heuristic planner.
The terrain-heuristic planner is meant to mimic the approaches of [24, 25],
where steps are selected based on a nominal gait dependent on the initial apex
velocity, and then the planned steps are moved if they land in ditches. All
planners are tested in a receding-horizon fashion, where the planned sequence
is executed by the low-level controller for 3 steps before replanning occurs.

##  VIII Results

(a)

(b)

Figure 4: Probability distributions over possible second step locations
predicted by the LSTM. Increasingly long arrows indicate higher initial
energy. Distributions are plotted such that the mode has height 1.0.

We measure success rate, computation time, and the number of calls made to the
simulator (the ODE solver) by the Angle-space planner, LSTM planner, Step-
space planner, LSTM-Guided planner, and a heuristic baseline planner on ditch
and step test suites. We also discuss some qualitative behaviors of our
planners and cases where they can be improved.

###  VIII-A Quantitative Results

TABLE II: Results on the Ditch Test Suite

Planner |  Success $\%$ $\uparrow$ |  ODE Calls $\downarrow$ |  $t_{\text{plan}}$ $\downarrow$
---|---|---|---
Heuristic | 24 | 0 | 2e-5s
Angle-space | 58.6 | 22661 | 0.15s
Step-space | 86.6 | 30857 | 0.29s
LSTM (Ours) | 56 | 0 | 0.007s
LSTM-Guided (Ours) | 84 | 4885 | 0.04s

TABLE III: Results on the Step Test Suite

Planner |  Success $\%$ $\uparrow$ |  ODE Calls $\downarrow$ |  $t_{\text{plan}}$ $\downarrow$
---|---|---|---
Heuristic | 56 | 0 | 2e-5s
Angle-space | 60 | 27021 | 0.15s
Step-space | 85 | 41146 | 0.34s
LSTM (Ours) | 49 | 0 | 0.007s
LSTM-Guided (Ours) | 96 | 6932 | 0.04s

The success rate of all 5 planners on the ditch and step world scenarios are
shown in Tables III and III. In these results, the Angle-space planner is used
with an initial branching factor of 20 with a fallback branching factor of 30
if the first try fails. The Step-space planner is used with a horizon of 5m
and spacing of 0.5 meters (branching factor of 10), and the LSTM-Guided
planner is used with a branching factor of 3 and fallback factor of 5.

We can see that the Step-space and LSTM-Guided planners have the best overall
performance, succeeding on over 80% of the terrains from both suites. This
makes intuitive sense as they incorporate the controller’s behavior into the
planner. The pure LSTM planner performs slightly worse than the baseline
Angle-space planner in both the ditches and steps scenarios; at low
velocities, it tends to suggest steps that either cause the controller to
violate the friction cone or that are very close to the edges of ditches and
steps. However, the high performance of the LSTM-Guided sampler shows that the
LSTM still suggests a high-quality probability distribution over possible
locations. The heuristic planner sometimes performs well but is highly
sensitive to variations in its parameters.

Tables III and III show that the LSTM-Guided planner achieves high success
rates while making fewer than 1/6 the number of ODE calls than the Step-space
planner, and fewer than 1/4 of the Angle-space planner. Since it guides
sampling to a few areas, the LSTM-Guided planner has to explore fewer nodes to
find a feasible plan, and so has a planning time of 0.04s on average, compared
to 0.3s for the Step-space planner.

###  VIII-B Qualitative Analysis

Figure 4 shows 4-step plans and the probability distributions for the second
step generated by the LSTM over 3 different initial apex states. As we
increase both the apex height and initial velocity, the LSTM alters its plan
accordingly to traverse the terrain. On the ditch terrain, the peaks of the
distribution for the second step move further away as the initial energy
increases. On the step terrain, when starting with too high an initial
velocity it shortens its first two steps due to the tradeoff mentioned in
Section IV-B. In the 3rd subfigure in Figure 4b, with too high an initial
velocity, it will not be able to generate the necessary height to clear the
obstacles, so it takes a short step to slow down.

The LSTM planner does have a number of shortcomings. Although it takes
noticeably shorter steps when the hopper has lower energy, it still tends to
propose more aggressive plans than the Angle-space planner. In addition, many
of the pathological behaviors present in the training data also appear in the
learned sequences, including stepping very close to edges, as seen in Figure
4b. In Figure 4a, there are spikes in the probability distribution around the
edges of the islands, corresponding to training sequences where the Angle-
space planner selects the node that minimizes the distance to the goal. This
occurs in part because we chose not to manually bias the planner using terrain
heuristics.

##  IX Conclusion and Future Work

In this work, we demonstrated how we can use an LSTM model to learn a
distribution for likely footsteps conditioned both on terrain geometry and
robot dynamics, and that this model can be successfully used to quickly
generate footstep plans and to speed up a sampling-based planner.

The most immediate extension of this work is to scale to multi-legged robots
in 3D. We have explored adapting our approach to a 3D SLIP model with 2D
heightmaps, and have promising, yet preliminary results with careful
adjustments to the loss function and network structure. Since sampling-based
planners scale poorly to higher-dimensional systems, we are also experimenting
with using accurate but slow trajectory optimizers for bipeds to generate long
trajectories for our method. Future work remains in understanding how much
data is required to capture the range of behaviors that more complicated
robots are capable of, and implementing our method on real hardware.

## References

  * [1] M. Zucker, N. Ratliff, M. Stolle, J. Chestnutt, J. A. Bagnell, C. G. Atkeson, and J. Kuffner, “Optimization and learning for rough terrain legged locomotion,” _The International Journal of Robotics Research_ , vol. 30, no. 2, pp. 175–191, 2011.
  * [2] S. Kuindersma, R. Deits, M. Fallon, A. Valenzuela, H. Dai, F. Permenter, T. Koolen, P. Marion, and R. Tedrake, “Optimization-Based Locomotion Planning, Estimation, and Control Design for the Atlas Humanoid Robot,” _Auton. Robots_ , vol. 40, no. 3, p. 429–455, Mar. 2016.
  * [3] M. Kalakrishnan, J. Buchli, P. Pastor, and S. Schaal, “Learning locomotion over rough terrain using terrain templates,” in _2009 IEEE/RSJ International Conference on Intelligent Robots and Systems_ , 2009, pp. 167–172.
  * [4] G. Zeglin and B. Brown, “Control of a bow leg hopping robot,” in _Proceedings. 1998 IEEE International Conference on Robotics and Automation_ , vol. 1, May 1998, pp. 793–798 vol.1.
  * [5] M. A. Arain, I. Havoutis, C. Semini, J. Buchli, and D. G. Caldwell, “A comparison of search-based planners for a legged robot,” in _9th International Workshop on Robot Motion and Control_ , Jul. 2013, pp. 104–109.
  * [6] A. W. Winkler, C. Mastalli, I. Havoutis, M. Focchi, D. G. Caldwell, and C. Semini, “Planning and execution of dynamic whole-body locomotion for a hydraulic quadruped on challenging terrain,” in _2015 IEEE International Conference on Robotics and Automation (ICRA)_ , 2015, pp. 5148–5154.
  * [7] M. Kalakrishnan, J. Buchli, P. Pastor, M. Mistry, and S. Schaal, “Fast, robust quadruped locomotion over challenging terrain,” in _2010 IEEE International Conference on Robotics and Automation_ , May 2010, pp. 2665–2670.
  * [8] M. Wermelinger, P. Fankhauser, R. Diethelm, P. Krüsi, R. Siegwart, and M. Hutter, “Navigation planning for legged robots in challenging terrain,” in _2016 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_ , Oct. 2016, pp. 1184–1189.
  * [9] A. Hornung, A. Dornbush, M. Likhachev, and M. Bennewitz, “Anytime search-based footstep planning with suboptimality bounds,” in _2012 12th IEEE-RAS International Conference on Humanoid Robots (Humanoids 2012)_ , 2012, pp. 674–679.
  * [10] P. Vernaza, M. Likhachev, S. Bhattacharya, S. Chitta, A. Kushleyev, and D. D. Lee, “Search-based planning for a legged robot over rough terrain,” in _2009 IEEE International Conference on Robotics and Automation_ , May 2009, pp. 2380–2387, iSSN: 1050-4729.
  * [11] A. W. Winkler, C. D. Bellicoso, M. Hutter, and J. Buchli, “Gait and Trajectory Optimization for Legged Systems Through Phase-Based End-Effector Parameterization,” _IEEE Robotics and Automation Letters_ , vol. 3, no. 3, pp. 1560–1567, Jul. 2018.
  * [12] R. Deits and R. Tedrake, “Footstep planning on uneven terrain with mixed-integer convex optimization,” in _2014 IEEE-RAS International Conference on Humanoid Robots_ , 2014, pp. 279–286.
  * [13] B. Ponton, A. Herzog, S. Schaal, and L. Righetti, “A convex model of humanoid momentum dynamics for multi-contact motion generation,” in _2016 IEEE-RAS 16th International Conference on Humanoid Robots (Humanoids)_ , 2016, pp. 842–849.
  * [14] M. Posa, C. Cantu, and R. Tedrake, “A direct method for trajectory optimization of rigid bodies through contact,” _The International Journal of Robotics Research_ , vol. 33, no. 1, pp. 69–81, 2014. [Online]. Available: https://doi.org/10.1177/0278364913506757
  * [15] V. Tsounis, M. Alge, J. Lee, F. Farshidian, and M. Hutter, “Deepgait: Planning and control of quadrupedal gaits using deep reinforcement learning,” _IEEE Robotics and Automation Letters_ , vol. 5, no. 2, pp. 3699–3706, 2020\.
  * [16] X. Peng, G. Berseth, K. Yin, and M. Van De Panne, “Deeploco: Dynamic locomotion skills using hierarchical deep reinforcement learning,” _ACM Trans. Graph._ , vol. 36, no. 4, Jul. 2017. [Online]. Available: https://doi.org/10.1145/3072959.3073602
  * [17] S. Gangapurwala, M. Geisert, R. Orsolino, M. F. Fallon, and I. Havoutis, “RLOC: terrain-aware legged locomotion using reinforcement learning and optimal control,” _CoRR_ , vol. abs/2012.03094, 2020. [Online]. Available: https://arxiv.org/abs/2012.03094
  * [18] A. Meduri, M. Khadiv, and L. Righetti, “Deepq stepper: A framework for reactive dynamic walking on uneven terrain,” in _2021 IEEE International Conference on Robotics and Automation (ICRA)_ , 2021, pp. 2099–2105.
  * [19] X. Peng, G. Berseth, and M. van de Panne, “Terrain-adaptive locomotion skills using deep reinforcement learning,” _ACM Trans. Graph._ , vol. 35, no. 4, Jul. 2016. [Online]. Available: https://doi.org/10.1145/2897824.2925881
  * [20] O. Melon, R. Orsolino, D. Surovik, M. Geisert, I. Havoutis, and M. F. Fallon, “Receding-horizon perceptive trajectory optimization for dynamic legged locomotion with learned initialization,” in _IEEE International Conference on Robotics and Automation, ICRA 2021, Xi’an, China, May 30 - June 5, 2021_. IEEE, 2021, pp. 9805–9811. [Online]. Available: https://doi.org/10.1109/ICRA48506.2021.9560794
  * [21] R. Deits, T. Koolen, and R. Tedrake, “Lvis: Learning from value function intervals for contact-aware robot controllers,” in _2019 International Conference on Robotics and Automation (ICRA)_ , 2019, pp. 7762–7768.
  * [22] B. Yang, L. Wellhausen, T. Miki, M. Liu, and M. Hutter, “Real-time optimal navigation planning using learned motion costs,” in _2021 IEEE International Conference on Robotics and Automation (ICRA)_ , 2021, pp. 9283–9289.
  * [23] Y.-C. Lin, B. Ponton, L. Righetti, and D. Berenson, “Efficient humanoid contact planning using learned centroidal dynamics prediction,” in _International Conference on Robotics and Automation (ICRA)_. IEEE, May 2019, pp. 5280–5286.
  * [24] O. A. V. Magaña, V. Barasuol, M. Camurri, L. Franceschi, M. Focchi, M. Pontil, D. G. Caldwell, and C. Semini, “Fast and Continuous Foothold Adaptation for Dynamic Locomotion Through CNNs,” _IEEE Robotics and Automation Letters_ , vol. 4, no. 2, pp. 2140–2147, Apr. 2019.
  * [25] D. Kim, D. Carballo, J. D. Carlo, B. Katz, G. Bledt, B. Lim, and S. Kim, “Vision Aided Dynamic Exploration of Unstructured Terrain with a Small-Scale Quadruped Robot,” in _2020 IEEE International Conference on Robotics and Automation (ICRA)_ , May 2020, pp. 2464–2470.
  * [26] O. Melon, M. Geisert, D. Surovik, I. Havoutis, and M. Fallon, “Reliable trajectories for dynamic quadrupeds using analytical costs and learned initializations,” in _2020 IEEE International Conference on Robotics and Automation (ICRA)_ , 2020, pp. 1410–1416.
  * [27] J. Siekmann, K. Green, J. Warila, A. Fern, and J. Hurst, “Blind Bipedal Stair Traversal via Sim-to-Real Reinforcement Learning,” in _Proceedings of Robotics: Science and Systems_ , Virtual, July 2021.
  * [28] Y. Kuo, A. Barbu, and B. Katz, “Deep sequential models for sampling-based planning,” _arXiv:1810.00804 [cs]_ , Oct. 2018.
  * [29] M. J. Bency, A. H. Qureshi, and M. C. Yip, “Neural Path Planning: Fixed Time, Near-Optimal Path Generation via Oracle Imitation,” in _2019 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_ , Nov. 2019, pp. 3965–3972.
  * [30] W. J. Schwind, “Spring loaded inverted pendulum running: A plant model.”
  * [31] R. J. Full and D. E. Koditschek, “Templates and anchors: neuromechanical hypotheses of legged locomotion on land,” _Journal of Experimental Biology_ , vol. 202, no. 23, pp. 3325–3332, Dec. 1999, publisher: The Company of Biologists Ltd Section: Journal Articles.
  * [32] T. Apgar, P. Clary, K. Green, A. Fern, and J. Hurst, “Fast online trajectory optimization for the bipedal robot cassie,” in _Proceedings of Robotics: Science and Systems_ , Pittsburgh, Pennsylvania, June 2018.
  * [33] S. G. Carver, N. J. Cowan, and J. M. Guckenheimer, “Lateral stability of the spring-mass hopper suggests a two-step control strategy for running,” _Chaos (Woodbury, N.Y.)_ , vol. 19, no. 2, Jun. 2009.
  * [34] G. Piovan and K. Byl, “Enforced symmetry of the stance phase for the Spring-Loaded Inverted Pendulum,” in _2012 IEEE International Conference on Robotics and Automation_ , 2012, pp. 1908–1914.
  * [35] J. K. Yim and R. S. Fearing, “Precision jumping limits from flight-phase control in salto-1p,” in _2018 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_ , 2018, pp. 2229–2236.
  * [36] S. Hochreiter and J. Schmidhuber, “Long Short-Term Memory,” _Neural Computation_ , vol. 9, no. 8, pp. 1735–1780, Nov. 1997\.
  * [37] A. H. Qureshi and M. C. Yip, “Deeply Informed Neural Sampling for Robot Motion Planning,” in _2018 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_ , 2018, pp. 6582–6588.
  * [38] C. Guo, G. Pleiss, Y. Sun, and K. Q. Weinberger, “On Calibration of Modern Neural Networks,” in _Proceedings of the 34th International Conference on Machine Learning - Volume 70_ , ser. ICML’17, 2017, p. 1321–1330.