# DLL: Direct LIDAR Localization. A map-based localization approach for aerial
robots

Fernando Caballero1 and Luis Merino1 *This work was partially supported by the
NIx ESMERA H2020 Project (Grant 780265) funded by the European Commission, and
by the Spanish Ministry of Science, Innovation and Universities (COMCISE
RTI2018-100847-B-C22, MCIU/AEI/FEDER, UE)1Fernando Caballero and Luis Merino
are with the Service Robotics Laboratory, Universidad Pablo de Olavide,
Seville, Spain<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

This paper presents DLL, a direct map-based localization technique using 3D
LIDAR for its application to aerial robots. DLL implements a point cloud to
map registration based on non-linear optimization of the distance of the
points and the map, thus not requiring features, neither point
correspondences. Given an initial pose, the method is able to track the pose
of the robot by refining the predicted pose from odometry. Through benchmarks
using real datasets and simulations, we show how the method performs much
better than Monte-Carlo localization methods and achieves comparable precision
to other optimization-based approaches but running one order of magnitude
faster. The method is also robust under odometric errors. The approach has
been implemented under the Robot Operating System (ROS), and it is publicly
available.

##  I Introduction

The operation of Unmanned Aerial Vehicles (UAVs) when there is no global
localization system, like GPS, or other external positioning devices, like
laser reflectors, calls for alternatives for estimating the robot pose. In
applications where it is possible to build a priori a 3D map of the
environment in which the UAV will operate, map-based localization can suffice
if the environment does not change very often. This map can be created and
updated by using SLAM modules (see Fig. 1). We need, thus, efficient 3D map-
based localization systems to be used by UAVs. They should be fast and
reliable, so that the localization information can be used by a robot to plan
its actions.

Figure 1: Scenario of the MBZIRC’20 competition, Challenge 3. UAVs have to put
out fires (top, left) in a high-rise building scenario (top, right). A 3D map
(bottom) built from 3D LIDAR data is used for localization.

3D Light Detection and Ranging (LIDAR) systems are becoming smaller, cheaper
and lighter, allowing UAVs to carry such sensors. They provide rich and
precise long range 3D information that can be leveraged for localization. This
paper presents a map-based position tracking using 3D LIDAR measurements to be
used in aerial robots.

Among the different challenges involved, the 3D LIDAR registration (alignment
with respect to the map) stands as the major technological problem to solve.
Most of the approaches in the state of the art make use of geometric features
such as corners or planes extracted from the sensor point cloud [1, 2, 3]. The
key idea is to select points or areas into the point cloud that are easy to
identify and match when we see again the scene from different points of views
and/or distances. These approaches are fast to compute, and accurate. However,
feature-based 3D LIDAR-to-map registration is a difficult task. Normally, the
3D map has much higher density of points than the LIDAR sensor readings. This
forces to use different approaches for feature detection in LIDAR and map, or
to built virtual views of the map depending on the robot relative position.
Also, feature-based approaches can struggle in scenarios with no distinctive
regions.

Iterative closest points (ICP) approaches [4] use the raw 3D point cloud of
the sensor, and no features or interests points are extracted. Although they
are very accurate, their convergence depends on the goodness of the
initialization and, most importantly, they require lots of computation to deal
with 3D large point clouds. The nearest point search is the main computational
bottleneck of ICP approaches.

The Normal Distribution Transform (NDT) was one the first approaches to
propose a nearest-neighbor-free solution for 3D registration [5, 6], reducing
the computational time with respect to ICP approaches, while keeping the
accuracy. The NDT is used to encode the scan and the map, using a
probabilistic representation. Registration is then performed between these
representations and not the original scans. This representation allows using
numerical optimization methods, and does not require a nearest-neighbor
search. Unfortunately, the numerical solution computation makes the approach
difficult to compute in real-time when large point clouds are considered.

Here we propose a direct approach for registration, and integrate it into a
localization system called Direct LIDAR Localization (DLL). By direct we mean
that the raw point cloud is used and no nearest point search is required. DLL
estimates the transform that aligns the input point cloud and the map by
minimizing the distances of points to the map using non-linear optimization.
While this optimization would be computationally demanding, DLL takes
advantage of the localization setup (in which you need an a priori map of the
environment) to pre-compute a Distance Field (DF) [7] map that boosts the
optimization process. We show in this paper, using datasets from simulated and
real flights, how this approach is more efficient and robust than alternative
methods from the state of the art, achieving similar accuracy. The resultant
system can be used for real-time position tracking of aerial robots using 3D
LIDAR as main sensor.

##  II Related Work

A majority of works from the literature on 3D LIDAR-based localization deal
with odometry and SLAM approaches, while there are less approaches dealing
with map-based localization using 3D LIDARs. A recent review on localization
approaches using 3D LIDAR for intelligent ground vehicles can be found in [8].

The basic procedure is to register the current LIDAR reading into the map
(this map being the last LIDAR reading or a partial submap in the case of
odometry). As mentioned before, many approaches first extract features from
the point clouds and from the map that are then used for registration. One
such approach is LOAM [2, 9]. It uses point features on sharp edges and planar
surfaces extracted from the 3D scans. These features are matched between
consecutive scans for fast odometry, and between the scan and a map that is
being built at a lower rate (without loop closures), leading to an enhanced
odometry estimate. Another example is [10], where the 3D point clouds are
first segmented, and the resulting segments are then used to find matches with
respect to a map using a set of descriptors for localization.

Lately, learning-based methods are being also considered for the problem.
LocNet [11] defines a handcrafted representation of LIDAR frames and then
learns a Siamese network architecture to estimate the similarity between the
representations of local scans and scans stored in the map. The system is
integrated into a Monte-Carlo Localization for 2D pose estimation, which is
then refined to 3D pose estimation through ICP. In [12], the segments in [10]
are augmented with an efficient 3D segment descriptor learned from data for
global mapping and localization.

Closer to our approach are registration-based methods. These methods employ
ICP and its variants directly over the point clouds, and are robust and
accurate. However they use to be computationally expensive, preventing their
use for real time systems. Approximate neighbors search has been proposed to
significantly reduce computation in [13, 14], and combined with a clever point
selection a SLAM system can be built. However, their computation grows (but
slowly) with the size of the map and it is not clear how to extend this
configuration to map-based localization. In [15], nearest point
correspondences between consecutive scans are used to estimate 6 DOF odometry.
The data association step here is crucial, as wrong correspondences can lead
to erroneous pose estimations. The paper proposes point filters and geometric
match rejection steps to reduce the computational burden and improve the
quality of the registration process.

Direct methods that avoid the point association step present advantages in
this regard. In that direction, the NDT representation discussed above has
been used for map-based Monte-Carlo localization using LiDAR [16]. The NDT
representation is itself a likelihood model for the alignment of the cloud and
the map. In [17], Monte-Carlo localization using NDT is mixed with a deep
probabilistic model learned from data that provides prior estimations for the
filter.

A pose tracking method based on 3D Monte Carlo localization and using the raw
point clouds as observations is presented in [18]. 3D Distance Fields (DF) are
used to represent the map. A particle filter is used to track the pose of the
UAV. The likelihood function for each scan is derived from the DF, and no
point correspondences are needed. A similar approach is considered in [19],
where an efficient 3D DF representation is presented to compute those
likelihoods. Also, the method considers potential unmapped measurements to
improve the localization.

Here, we present a novel direct approach based on non-linear optimization
instead of filtering. This has been shown to present advantages with respect
to filter-based approaches for localization in 2D [20]. The method uses a 3D
distance field and an efficient optimization formulation to correct the
predicted position given by odometry using the map. The resultant localization
system only requires a LIDAR and IMU to operate.

##  III DLL: Direct LIDAR Localization

The process of map-based robot localization using point clouds can be
summarized as finding the transform that better aligns the current LIDAR point
cloud with respect to the map. However, assuming we are localizing a robot,
DLL makes use of the following prior information to build a fast and accurate
localization algorithm:

  * •

Robot odometry. This gives us a good prior about how much the robot moved
since we localized the robot for the last time. This prior can be used to give
a good guess of the robot position/orientation into the map, saving
computational time.

  * •

Inertial Measurement Units (IMUs). Nowadays, IMUs are cheap and accurate, they
are installed in all smartphones. It is very common to have an IMU onboard the
robot. Moreover, precise IMUs are mandatory for aerial robots in order to
close the control loops. While yaw angle is subject to significant distortion
due to magnetic field interference in the compass, roll and pitch angles are
observable and accurate. This information can be used to tilt-compensate the
LIDAR point cloud, simplifying the registration process.

DLL proposes a new point cloud registration process that is fast and accurate,
so that in can be used as primary localization system in a real robot
installation. Next paragraphs formulate the problem and provide detailed
information about such registration process.

###  III-A Direct map to point cloud registration

We assume the LIDAR (or any other 3D sensor) provides a point cloud
$\mathbf{pc}^{k}:\\{\mathbf{p}_{0},\mathbf{p}_{1},...\mathbf{p}_{P}\\}$ at
every time step $k$, where $\mathbf{p}_{i}=[px_{i},py_{i},pz_{i}]^{t}$.

A map of the environment is also available as a point cloud
$\mathbf{map}:\\{\mathbf{m}_{0},\mathbf{m}_{1},...\mathbf{m}_{M}\\}$, where
$\mathbf{m}_{i}=[mx_{i},my_{i},mz_{i}]^{t}$. This map is assumed to be static.

Given the 3D map and the point cloud at time $k$, our objective is to compute
the transform $\mathbf{T}_{map}^{k}$ that better aligns $\mathbf{pc}^{k}$ to
the $\mathbf{map}$. This can be achieved by minimizing the following
expression:

$\operatorname*{arg\,min}_{\\{\mathbf{T}_{map}\\}}\left[\sum_{i=1}^{P}\|\mathbf{T}_{map}\mathbf{p}_{i}-\mathbf{m}_{c}(\mathbf{p}_{i})\|^{2}\right]$
(1)

where $\mathbf{m}_{c}(\mathbf{p}_{i})$ is the point of $\mathbf{map}$ closest
to $\mathbf{p}_{i}$.

Solving (1) needs to deal with two major challenges: how to determine the
values of $\mathbf{m}_{c}$, and how to solve a massively overdetermined non-
linear optimization problem.

ICP works by iteratively searching for pairs of nearby points in the two point
clouds and minimising the sum of all point-to-point distances. The main
bottleneck is the nearest neighbor computation. Approximately nearest search
or kd-trees can be used to speed up the process, but still requires
significant computational resources.

On the other hand, NDT models the point cloud as a combination of normal
distributions instead of individual points, describing the probability of
finding a point at a certain position. This is a piecewise smooth
representation of the point cloud, which enables standard numerical
optimization methods for registration. This avoids explicit neighbor search,
with the corresponding computational reduction.

DLL follows NDT’s key idea of modeling the registration process as a non-
linear optimization process, but models the point cloud as a distance field.
Instead of individual points, DLL builds a distance field representation of
the map called $DF(\mathbf{x})$. Given a 3D point $\mathbf{x}=[x,y,z]^{t}$,
$DF(\mathbf{x})$ provides the distance to the closest point into the map. This
way, we transform (1) into the following expression:

$\operatorname*{arg\,min}_{\\{\mathbf{T}_{map}\\}}\left[\sum_{i=1}^{P}DF^{2}(\mathbf{T}_{map}\mathbf{p}_{i})\right]$
(2)

$DF(\mathbf{x})$ is continuous and generally smooth (except in the cut locus
and object boundaries, where the gradient is discontinuous [7]), so we can use
regular optimization processes to solve the expression.

Estimating the corresponding distance transform of the 3D map can be
computationally demanding, specially for large maps. However, this only needs
to be computed once, and we can compute it offline as part of the map building
process for map-based localization.

Next Section details the process of approximating the distance function of the
3D point cloud used as map.

###  III-B Approximated distance field

The distance function is computed from the 3D map and stored as a 3D grid of
fixed resolution. The size of the grid is determined by the spacial
distribution of 3D points. Every grid cell contains the distance to the
closest point of the 3D map to that cell.

The 3D grid is build by systematically computing the distance to the closest
map point in all the cells. We use a kd-tree in order to speed up the
computation, although other methods for approximately nearest point search can
be applied. This process is computationally expensive, but it is performed
offline prior to robot localization.

Once built, trilinear interpolation parameters are computed for each cell. The
eight distance values surrounding each cell are used to calculate these
parameters. They allow interpolating the DF values for positions within a
given cell as:

$DF(\mathbf{x})=a_{0}+a_{1}x+a_{2}y+a_{3}z+a_{4}xy+a_{5}xz+a_{6}yz+a_{7}xyz$
(3)

where $\mathbf{x}=[x,y,z]^{t}$ represents a 3D point belonging to the grid
cell.

The objective of this interpolation is twofold: First, it allows reducing the
impact of the 3D grid space quantization, which may lead to gradient
instabilities during the optimization process. Second, and more importantly,
this enables analytic gradient computation of the distance with respect to the
point under evaluation, accelerating the gradient computation and, hence, the
full optimization process.

###  III-C Outlier rejection

The 3D LIDAR might sense objects that are not mapped (static or dynamic), or
some of the points might fall out of the map. We need to deal with these
points to prevent degenerated solutions or even divergence in the optimization
process. Two main actions are taken to prevent these outliers:

  * •

Points out of the map. In this case, the distance function returns a set of
interpolation parameters equal to zero. This produce both error and gradient
equal to zero, avoiding influencing the optimization process.

  * •

Unmapped objects. A robust Cauchy Kernel with scaling factor set to $0.1$ is
applied to each point of the LIDAR. Thus, when the distance to the closest
point is large, the kernel penalizes this constraint reducing its influence
into the whole optimization process.

###  III-D Implementation details

(a)

(b)

(c)

(d)

Figure 2: Catec dataset scenario. (a) Picture of the scenario (source
http://www.catec.aero). (b) 3D map of the scenario, 15x15x5 meters volume.
Airsim dataset scenario. (c) Picture of the scenario. (d) 3D map of the
scenario, 50x50x10 meters volume.

DLL has been implemented in C++ and integrated into the ROS framework. We used
Ceres Solver [21] to implement the non-linear optimization process. The
Jacobians have been analytically computed and included into the optimization.

As previously introduced, DLL makes use of robot odometry and IMU for faster
computation. Thus, DLL does not compute roll and pitch angles, the point cloud
is tilt compensated before registration instead. Therefore, only X, Y and Z
translation, together with yaw angle are estimated during alignment. Please
notice that DLL is a general approach, so that estimating roll and pitch is
just a matter of adding the corresponding states and Jacobian into the
optimizer.

When a new point cloud must be registered, DLL computes the odometric shift
since the last map registration computation and uses it as initial guess for
alignment.

##  IV Experimental Results

This section presents the experimental validation of the proposed approach.
The method has been tested using a publicly available real indoor dataset, and
a simulated outdoor dataset using Airsim [22]. The approach has been
benchmarked against other three methods. The DLL ROS software implementation,
and the Airsim simulated dataset can be downloaded
here111https://github.com/robotics-upo/dll.

###  IV-A Datasets

We can find a good number of datasets involving ground robots and multiple
sensors (cameras, 3D-LIDAR, RADAR, etc) in the state of the art. However, the
number of datasets involving aerial robots and 3D LIDAR is limited in the
literature. This is mainly motivated by the weight constraints of these
systems.

The indoor dataset is composed by two fights released together with the
_AMCL3D ROS_ 222http://wiki.ros.org/amcl3d module [18] for aerial robot
localization indoors333The dataset can be downloaded from
https://github.com/fada-catec/amcl3d/releases. The scenario is shown in Fig.
2(a), and consists of a $15\times 15\times 5$ meters indoors volume. The XY
trajectory of both flights are shown in Figs. 3(a) and 3(b). The catec1
trajectory is $31.40$ meter-long, while catec2 is $56.69$ meters. The dataset
contains the ground-truth robot position provided by a VICON motion capture
system with millimeter accuracy, and the 3D LIDAR data of a 16 channel sensor
attached to the vehicle.

In order to validate the method in a different environment, a dataset using
Airsim [22] has been created (which can be downloaded together with DLL code).
Airsim provides simulated realistic images and sensors from both aerial and
ground robots. The scenario is a $50\times 50\times 10$ meters volume, shown
in Fig. 2(c). It contains two flights of a simulated drone with a 16 channel
3D LIDAR attached. Figure 3(c) shows the XY trajectory performed by the drone
in the airsim1 flight, and Fig. 3(d) the corresponding trajectory of the
airsim2 flight. The total length of the trajectories are $191.94$ and $164.92$
meters respectively. The ground-truth in this case is provided by the
simulator, so we assume it is error free.

(a)

(b)

(c)

(d)

Figure 3: Dataset ground-truth trajectories (dashed blue line), DLL
estimations (solid red line) and odometry estimation (dashed green line). Top:
X-Y view. Middle: Z coordinate. Bottom: Yaw angle evolution. (a) catec1
trajectory. (b) catec2 trajectory. (c) airsim1 trajectory. (d) airsim2
trajectory.

###  IV-B Benchmarks

Three other localization solutions have been tested in order to put in context
the localization results of DLL:

  * •

ICP: an ICP-based localization system has been implemented using the ICP
solution provided by the PCL library [23]. It was setup with $50$ iterations,
$0.1$ meters of max correspondence distance and outlier rejection with $1.0$
meters threshold. The target cloud for ICP (the map) was computed offline and
not included into the processing time computation. This method has been
integrated into the DLL ROS module as a different point cloud registration
mechanism, and it is publicly available together with the rest of the source
code.

  * •

NDT: an NDT-based [5] localization system has been implemented using the
solution provided by the PCL library [23]. It was setup with $50$ iterations,
$1.0$ meters resolution of the NDT grid, $0.01$ meter of transformation
epsilon and $0.1$ meter for the maximum step size for the More-Thuente line
search. The NDT representation of the map was computed offline and not
included into the processing time computation. This method has been integrated
into the DLL ROS module as a different point cloud registration mechanism, and
it is publicly available together with the rest of the source code.

  * •

AMCL3D: the Montecarlo Localization approach implemented in _AMCL3D ROS_ has
been used. This code implements the method described in [18]. It was
configured with $1000$ particles, $0.2$ meters/radians for additive noise in
prediction function for X, Y, Z and yaw, and $0$ resample interval. These are
the parameters provided for catec1 and catec2 trajectories in the paper.

As mentioned in Section III, DLL (and most localization approaches) makes use
of the robot odometry to obtain a prior about the robot position into the map.
For these experiments, the LiDAR odometry and mapping method
LOAM444https://github.com/HKUST-Aerial-Robotics/A-LOAM was used to compute the
odometry. The method was configured to perform only odometry, the mapping has
been deactivated to prevent jumps in the LiDAR-to-LiDAR pose estimation. This
odometry was computed for each of the datasets, and served to each of the
methods above mentioned as initial solution.

The map resolution in both scenarios is the same, $0.05$ meters. The point-
cloud size and density of the 3D LIDAR was also the same for all the
approaches, except for NDT. As pointed out in [19], we needed to apply a $2$
meters voxel grid filter to the LIDAR point cloud, otherwise the PCL NDT
implementation did not converge to a solution.

Finally, all the implementations make use of LIDAR tilt-compensation based on
the onboard IMU. Thus, the point clouds used for registration are already
compensated according to the roll and pitch angles provided by the drone IMU.

All the tests were carried out in the same computer, a 10th generation Intel
Core i7 laptop with 16 GB of RAM running Ubuntu 18.04. Although the Ceres
Solver can be configured to run in multiple threads, all the methods have been
configured to be single threaded in order to have a common baseline.

The trajectory computed by DLL is presented together with the ground-truth and
the odometry in Fig 3. The results of the benchmarks are shown in Table I. The
table shows the computed RMSE in position and yaw angle. It also shows the
averaged processing time per point cloud $\Delta t$. It can be seen how the
computed errors in DLL are small, in the same order of NDT and ICP, and for
some experiments DLL provides the smallest error. It is also worth to mention
that the computation time per point-cloud is about one order of magnitude
smaller than all the other approaches.

Thus, according to the benchmark results, DLL presents an accuracy at the same
level of other approaches in the state of the art, and even better with very
small impact in computation. Even more, the DLL computational time can be
improved about $30\%$ just increasing the number of threads used by the Ceres
Solver.

Scenario |  | DLL | ICP | NDT | AMCL3D
---|---|---|---|---|---
catec1 | rmset (dev) | 0.0548 (0.0556) | 0.0578 (0.0619) | 0.0602 (0.0638) | 0.1674 (0.1828)
| rmsea (dev) | 0.0030 (0.0018) | 0.0025 (0.0016) | 0.0044 (0.0025) | 0.0271 (0.0033)
|  $\Delta t$ (dev) | 0.0731 (0.0237) | 2.1327 (0.1231) | 0.4917 (0.0616) | 0.5367 (0.0621)
catec2 | rmset (dev) | 0.0580 (0.0480) | 0.0571 (0.0554) | 0.0605 (0.0542) | 0.8715 (1.0778)
| rmsea (dev) | 0.0116 (0.0067) | 0.0185 (0.0117) | 0.0077 (0.0046) | 0.7512 (0.4854)
|  $\Delta t$ (dev) | 0.0763 (0.0242 ) | 2.2236 (0.1470) | 0.6299 (0.1420) | 0.5702 (0.0674)
airsim1 | rmset (dev) | 0.0920 (0.0795) | 0.1161 (0.0805) | 0.0696 (0.0692) | 1.3302 (12.4577)
| rmsea (dev) | 0.0181 (0.0137) | 0.0211 (0.0170) | 0.0185 (0.0151) | 0.1142 (0.1047)
|  $\Delta t$ (dev) | 0.0370 (0.0141) | 0.7908 (0.1630) | 0.5211 (0.3055) | 0.3686 (0.1270)
airsim2 | rmset (dev) | 0.1027 (0.1445) | 0.0753 (0.0878) | 0.0719 (0.0815) | 2.9354 (9.8130)
| rmsea (dev) | 0.0142 (0.0106) | 0.0165 (0.0146) | 0.0154 (0.0135) | 0.7407 (0.0978)
|  $\Delta t$ (dev) | 0.0372 (0.0135) | 0.7917 (0.1408) | 0.5427 (0.3855) | 0.3942 (0.0915)
Table I: Localization benchmark results. rmset in meters, rmsea in radians and
$\Delta t$ in seconds.

###  IV-C Robustness study

Most localization approaches, direct or feature-based, work well and
efficiently when the robot odometry is accurate. A good prior about the robot
position helps to reduce the searching space for the solution, impacting both
accuracy and computational time. However, in real-world applications the
odometry estimation might be temporally noisy or even jumpy. This section will
benchmark the proposed approach focusing in robustness.

Thus, the following experiment has been conceived to evaluate the robustness
of the approach against noisy odometry: the four algorithms have been run over
the same experiments under three different setups. Particularly, the catec1
trajectory has been selected. In each trial, random noise has been added to
the translation and yaw angle increment computed from odometry. The following
setups have been implemented:

  * •

Baseline: This is the setup presented in Table I in scenario catec1.

  * •

NoOdom: In this setup, no odometry is used for localization. The filters are
initialized in the correct position. Then, in each filter iteration, they use
the previous solution as initial guess for the new update.

  * •

MidNoise: In this setup, Gaussian noise is added to the translation and yaw
angle increments computed from odometry. This noise is centered in the actual
translation/rotation computed from odometry and it has a standard deviation of
$0.25$ meters in each axis and $0.05$ radians in yaw.

  * •

LargeNoise: Similar to MidNoise setup, but with a standard deviation of $0.5$
meters in each axis and $0.1$ radians in yaw.

Table II summarizes the errors and computation time of the different
approaches in the setup previously described. It can be seen how DLL provides
the smallest error in many cases, and also provides errors very close to the
best solution in the rest of the cases. It is worth to mention that DLL and
NDT are the only approaches able to stand with mid and large errors in
odometry. Notice that DLL and NDT were able to compute a solution even with
jumps of $0.75$ meters and $0.12$ radians in the odometry. Among all the
approaches, DLL provides the fastest solution, roughly an order of magnitude
faster.

Setup |  | DLL | ICP | NDT | AMCL3D
---|---|---|---|---|---
Baseline | rmset (dev) | 0.0548 (0.0556) | 0.0578 (0.0619) | 0.0602 (0.0638) | 0.1674 (0.1828)
| rmsea (dev) | 0.0030 (0.0018) | 0.0025 (0.0016) | 0.0044 (0.0025) | 0.0271 (0.0033)
|  $\Delta t$ (dev) | 0.0731 (0.0237) | 2.1327 (0.1231) | 0.4917 (0.0616) | 0.5367 (0.0621)
NoOdom | rmset (dev) | 0.0766 (0.0525) | 0.0612 (0.0494) | 0.0838 (0.0648) | 0.4242 (0.2346)
| rmsea (dev) | 0.0032 (0.0019) | 0.0030 (0.0016) | 0.0049 (0.0027) | 0.1109 (0.0376)
|  $\Delta t$ (dev) | 0.0903 (0.0268) | 2.1954 (0.0952) | 0.4958 (0.0651) | 0.4535 (0.1072)
MidNoise | rmset (dev) | 0.0899 (0.0547) | * | 0.1061 (0.0761) | *
| rmsea (dev) | 0.0050 (0.0032) | * | 0.0048 (0.0027) | *
|  $\Delta t$ (dev) | 0.1168 (0.0260) | * | 1.2133 (0.4142) | *
LargeNoise | rmset (dev) | 0.1457 (0.1923) | * | 0.4951 (0.6200) | *
| rmsea (dev) | 0.0103 (0.0092) | * | 0.1337 (0.1223) | *
|  $\Delta t$ (dev) | 0.1381 (0.0313) | * | 1.9501 (0.7216) | *
Table II: Robustness benchmark results. rmset in meters, rmsea in radians and
$\Delta t$ in seconds. Entries with * indicate that the method diverged during
the execution in such setup.

###  IV-D Validation in MBZIRC2020 dataset

The approach has been also validated using data from a real outdoor flight
carried out by our SkyEye Team during the Mohamed Bin Zayed International
Robotics Challenge 2020, Challenge 3555http://www.mbzirc.com/challenge/2020.
This experiment was not used as benchmark because the available reference is
based on GPS in single configuration, so the accuracy was not enough to
guarantee a fair comparison among approaches. However, it can be used to show
that DLL is able to also perform well outdoors in a large environment.

Figures 1 and 4 show the environment where the dataset was gathered. It is a
volume of $60\times 30\times 20$ meters approximately. It is composed by a
$15$ meters high building in the center of an arena surrounded by four towers.

Figure 4: Top view of the 3D map of the MBZIRC 2020 real outdoor dataset.

The estimation by DLL compared to the baseline is presented in Fig. 5. The
baseline XY position is provided by the UAV (DJI’s M210v2) GPS in single
configuration, the Z reference is provided by a barometric altimeter and the
yaw angle is compared against the UAV compass. It can be seen how the DLL
estimation closely follows the baseline.

Figure 5: Estimated UAV position in MBZIRC2020 dataset. GPS baseline (dashed
blue line) and DLL estimation (solid red line).

##  V Conclusions

The paper presents a direct map-based pose tracking approach using 3D LIDAR.
The method uses the raw point clouds and avoids the search for point
correspondences. The predicted pose from odometry is refined by directly
optimizing the distance of the points to the map, using a distance field
representation of the latter.

The results show how the approach achieves similar precision as competing
methods like NDT and ICP for the scenarios considered, but runs one order of
magnitude faster, allowing real-time execution. Furthermore, the optimization-
based approaches NDT and DLL behave better than the Monte-Carlo localization
approach in the case of noisy odometry, following also the findings of [20].
DLL is able to handle larger noise than NDT, achieving lower errors in this
case.

Future work will consider improving the space efficiency of the method. One of
the main drawbacks of the proposed method is the amount of memory required by
the 3D grid representation of the distance field. More efficient structures
for the distance field like in [19] will be considered.

## References

  * [1] H. Liu, Q. Ye, H. Wang, L. Chen, and J. Yang, “A precise and robust segmentation-based lidar localization system for automated urban driving,” _Remote Sensing_ , vol. 11, no. 11, 2019.
  * [2] Zhang and S. Singh, “LOAM: Lidar Odometry and Mapping in Real-time,” in _Robotics: Science and Systems Conference (RSS)_ , 2014.
  * [3] C. Ulas and H. Temeltaş, “A fast and robust feature-based scan-matching method in 3d slam and the effect of sampling strategies,” _International Journal of Advanced Robotic Systems_ , vol. 10, 2013.
  * [4] Y. Chen and G. G. Medioni, “Object modelling by registration of multiple range images.” _Image Vis. Comput._ , vol. 10, no. 3, pp. 145–155, 1992.
  * [5] M. Magnusson, A. Lilienthal, and T. Duckett, “Scan registration for autonomous mining vehicles using 3d-ndt,” _Journal of Field Robotics_ , vol. 24, no. 10, pp. 803–827, 2007.
  * [6] H. Hong and B. H. Lee, “Probabilistic normal distributions transform representation for accurate 3d point cloud registration,” in _2017 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_ , 2017, pp. 3333–3338.
  * [7] M. W. Jones, J. A. Baerentzen, and M. Sramek, “3d distance fields: A survey of techniques and applications,” _IEEE Transactions on visualization and Computer Graphics_ , vol. 12, no. 4, pp. 581–599, 2006.
  * [8] M. Elhousni and X. Huang, “A survey on 3d lidar localization for autonomous vehicles,” in _2020 IEEE Intelligent Vehicles Symposium (IV)_. IEEE, pp. 1879–1884.
  * [9] J. Zhang and S. Singh, “Low-drift and real-time lidar odometry and mapping,” _Auton. Robots_ , pp. 401–416, 2017.
  * [10] R. Dubé, M. G. Gollub, H. Sommer, I. Gilitschenski, R. Siegwart, C. Cadena, and J. Nieto, “Incremental-segment-based localization in 3-d point clouds,” _IEEE Robotics and Automation Letters_ , vol. 3, no. 3, pp. 1832–1839, 2018\.
  * [11] H. Yin, L. Tang, X. Ding, Y. Wang, and R. Xiong, “Locnet: Global localization in 3d point clouds for mobile vehicles,” in _2018 IEEE Intelligent Vehicles Symposium (IV)_. IEEE, 2018, pp. 728–733.
  * [12] R. Dubé, A. Cramariuc, D. Dugas, H. Sommer, M. Dymczyk, J. Nieto, R. Siegwart, and C. Cadena, “Segmap: Segment-based mapping and localization using data-driven descriptors,” _The International Journal of Robotics Research_ , vol. 39, no. 2-3, pp. 339–355, 2020.
  * [13] M. Muja and D. G. Lowe, “Fast approximate nearest neighbors with automatic algorithm configuration,” in _International Conference on Computer Vision Theory and Applications_ , vol. 1. Scitepress, 2009, pp. 331–340.
  * [14] J. Elseberg, S. Magnenat, R. Siegwart, and A. Nüchter, “Comparison of nearest-neighbor-search strategies and implementations for efficient shape registration,” _Journal of Software Engineering for Robotics (JOSER)_ , vol. 3, no. 1, pp. 2–12, 2012.
  * [15] D. Kovalenko, M. Korobkin, and A. Minin, “Sensor aware lidar odometry,” in _2019 European Conference on Mobile Robots (ECMR)_. IEEE, 2019, pp. 1–6.
  * [16] J. Saarinen, H. Andreasson, T. Stoyanov, and A. J. Lilienthal, “Normal distributions transform monte-carlo localization (ndt-mcl),” in _2013 IEEE/RSJ International Conference on Intelligent Robots and Systems_ , 2013, pp. 382–389.
  * [17] L. Sun, D. Adolfsson, M. Magnusson, H. Andreasson, I. Posner, and T. Duckett, “Localising faster: Efficient and precise lidar-based robot localisation in large-scale environments,” in _2020 IEEE International Conference on Robotics and Automation (ICRA)_. IEEE, 2020, pp. 4386–4392.
  * [18] F. Perez-Grau, F. Caballero, A. Viguria, and A. Ollero, “Multi-sensor three-dimensional Monte Carlo localization for long-term aerial robot navigation,” _International Journal of Advanced Robotic Systems_ , vol. 14, no. 5, 2017.
  * [19] N. Akai, T. Hirayama, and H. Murase, “3d monte carlo localization with efficient distance field representation for automated driving in dynamic environments,” in _2020 IEEE Intelligent Vehicles Symposium (IV)_ , 2020, pp. 1859–1866.
  * [20] L. Dantanarayana, G. Dissanayake, and R. Ranasinge, “C-log: A chamfer distance based algorithm for localisation in occupancy grid-maps,” _CAAI transactions on intelligence technology_ , vol. 1, no. 3, pp. 272–284, 2016.
  * [21] S. Agarwal, K. Mierle, and Others, “Ceres solver,” http://ceres-solver.org.
  * [22] S. Shah, D. Dey, C. Lovett, and A. Kapoor, “Airsim: High-fidelity visual and physical simulation for autonomous vehicles,” in _Field and Service Robotics_ , 2017. [Online]. Available: https://arxiv.org/abs/1705.05065
  * [23] R. B. Rusu and S. Cousins, “3D is here: Point Cloud Library (PCL),” in _IEEE International Conference on Robotics and Automation (ICRA)_ , Shanghai, China, May 9-13 2011.


# MemoNav: Selecting Informative Memories for Visual Navigation

Hongxin Li
CASIA
<EMAIL_ADDRESS>
&Xu Yang
CASIA
<EMAIL_ADDRESS>
Yuran Yang
Tencent Map, T Lab
<EMAIL_ADDRESS>
&Shuqi Mei
Tencent Map, T Lab
<EMAIL_ADDRESS>
&Zhaoxiang Zhang
CASIA
<EMAIL_ADDRESS>

###### Abstract

Image-goal navigation is a challenging task, as it requires the agent to
navigate to a target indicated by an image in a previously unseen scene.
Current methods introduce diverse memory mechanisms which save navigation
history to solve this task. However, these methods use all observations in the
memory for generating navigation actions without considering which fraction of
this memory is informative. To address this limitation, we present the
MemoNav, a novel memory mechanism for image-goal navigation, which retains the
agent’s informative short-term memory and long-term memory to improve the
navigation performance on a multi-goal task. The node features on the agent’s
topological map are stored in the short-term memory, as these features are
dynamically updated. To aid the short-term memory, we also generate long-term
memory by continuously aggregating the short-term memory via a graph attention
module. The MemoNav retains the informative fraction of the short-term memory
via a forgetting module based on a Transformer decoder and then incorporates
this retained short-term memory and the long-term memory into working memory.
Lastly, the agent uses the working memory for action generation. We evaluate
our model on a new multi-goal navigation dataset. The experimental results
show that the MemoNav outperforms the SoTA methods by a large margin with a
smaller fraction of navigation history. The results also empirically show that
our model is less likely to be trapped in a deadlock, which further validates
that the MemoNav improves the agent’s navigation efficiency by reducing
redundant steps.

##  1 Introduction

Human beings plan their routes by recalling detailed experiences of the past
[37, 35, 23]. When we get into a new environment, the first thing is usually
to explore our surroundings to get familiar with the scene layout. This
exploration behavior enables us to quickly plan new routes with the help of
the so-called _working memory_ [39, 12].

Recent neuroscience research [29, 24, 6] has found that working memory is
essential for organizing goal-directed behaviors including navigation, as it
maintains task-relevant information. Several models [13, 12, 3] of working
memory have been constructed to explain the relationships among short-term
memory (STM), long-term memory (LTM), and working memory (WM). Particularly,
the model by Cowan et al. [12] (shown in the Appendix) demonstrates that the
human brain selects short-term memory as part of working memory by focusing
attention on task-relevant experiences to avoid distractions. It is also
noticed that working memory is not a simple extension of short-term memory,
but an incorporation of selected short-term memory and long-term memory in
goal-oriented tasks [3].

Inspired by the above neuroscience research, we propose a MemoNav for image-
goal visual navigation (ImageNav) agents, which is built upon a SoTA
topological map-based method VGM [20]. The MemoNav simulates the working
memory mechanism of the human brain and improves the agent’s ability to
complete multi-goal navigation tasks. Recently, a number of ImageNav methods
[20, 9, 8, 14, 19] have introduced memory mechanisms. According to the
structure of memory, these methods can be classified into three categories:
(a) metric map-based methods [8, 11] that reconstruct local top-down maps and
aggregate them into a global map, (b) stacked memory-based methods [27, 25,
14] that stack the past observations and pose sensor data in chronological
order, and (c) topological map-based methods [20, 9, 4, 32] that store sparse
landmark features in the graph nodes. Comparatively speaking, the metric map-
based methods store every detail of the scene, thus consuming large memory
when the agent encounters large scenes; the stacked memory-based methods
utilize all past data without differentiating useful information and noise;
the topological map-based methods benefit from the memory sparsity of
topological maps, but still suffer from all memory computation without
considering the contribution of each graph node.

To overcome these limitations, the MemoNav enables the agent to flexibly
retain informative navigation experience. In our design, the MemoNav utilizes
the aforementioned three types of memory: STM, LTM, and WM. STM represents the
local node features in a topological map; LTM is a global node continuously
aggregating short-term memory; WM incorporates the informative fraction of the
STM and the LTM. Technically, the MemoNav consists of four steps: map update,
selective forgetting, memory encoding and decoding, and action generation. (1)
Firstly, the map update module stores landmark features on the map as the STM.
(2) To incorporate informative STM into the WM, a selective forgetting module
temporarily removes nodes whose attention scores assigned by the memory
decoder rank below a predefined percentage. After forgetting, the navigation
pipeline will not compute the forgotten node features at subsequent time
steps. To assist the STM, we add a global node [1, 5] to the map as the LTM.
The global node links to all map nodes and continuously aggregates the
features of these nodes at each time step. (3) The retained STM and the LTM
form the WM, which is then processed by a GATv2 [7] encoder. Afterward, two
Transformer [38] decoders use the embeddings of the goal image and the current
observation to decode the processed WM. (4) Lastly, the decoded features are
used for generating navigation actions.

The MemoNav enables the agent to utilize task-relevant experiences to find a
short path to the goal without being intervened by misleading information.
With the synergy of these three types of memory, the MemoNav achieves
considerable progress in multi-goal ImageNav tasks. The results show that
compared with the SoTA method [20], the MemoNav increased the success rate by
5%, 9%, and 3% on 2-goal, 3-goal, and 4-goal test datasets, respectively. The
main contributions of this paper are as follows:

  * •

We propose the MemoNav, which utilizes a forgetting module to select
informative short-term memory stored in the topological map for generating
navigation actions.

  * •

We introduce a global node to represent long-term memory as a supplement to
the short-term memory.

  * •

We evaluate the proposed model on a multi-goal task. The results demonstrate
that our model outperforms the SoTA baseline by a large margin on a multi-goal
task.

##  2 Related Work

ImageNav models based on topological maps. Cognitive research [40, 15, 17]
suggests that humans save landmark features in their memory for navigation,
instead of detailed scene layouts. Several methods [32, 4, 9, 20, 10] utilize
this theory and propose topological memory for visual navigation. SPTM [32] is
an early attempt to use topological maps in ImageNav. It proposes a semi-
parametric topological memory that is pre-built before navigation. Beeching et
al. [4] introduced a graph processing method inspired by dynamic programming-
based shortest path algorithms. This method also needs to explore the scene in
advance. NTS [9] and VGM [20] incrementally build the topological map during
navigation. VGM uses no pose sensor data and is more robust to sensor noise
than NTS. The two methods utilize all features in the map, while the MemoNav
flexibly utilizes the informative fraction of these features.

Memory mechanisms for reinforcement learning. Several studies [30, 21, 36, 22]
draw inspiration from memory mechanisms of the human brain and design
reinforcement learning models for reasoning over long time horizons. Ritter et
al. [30] proposed an episodic memory storing state transitions for navigation
tasks. Lampinen et al. [21] presented hierarchical attention memory as a form
of “mental time-travel” [37], which means recovering goal-oriented information
from past experiences. Unlike this method, our model retains such information
via a novel forgetting module. Expire-span [36] predicts life spans for each
memory fragment and permanently deletes expired ones. Our model is different
from it in that we restore forgotten memory if the agent returns to visited
places. The most similar work is WMG [22] which also uses theories of working
memory. However, its memory capacity is fixed. In contrast, our model retains
a certain proportion of short-term memory in the working memory and adjusts
the memory capacity when the navigation episode contains more goals.

##  3 Background

###  3.1 Task Definition

We consider image-goal navigation (ImageNav) in this paper. As shown in Figure
1 (left), the objective of the agent is to learn a policy
$\pi(a_{t}|s_{t},\mathbf{I}_{target})$ to reach a target, given an image
$\mathbf{I}_{target}$ that contains a view of the target and a series of
observations, $\left\\{\mathbf{I}_{t}\right\\}$, captured during the
navigation. At the beginning of navigation, the agent receives an RGB image,
$\mathbf{I}_{target}$, of the target. At each time step, it captures an RGB-D
panoramic image, $\mathbf{I}_{t}$ of the current location and generates a
navigational action. Following [20], any additional sensory data, e.g. GPS and
IMU, are not available.

Figure 1: Example episodes for 1-goal and three-goal tasks. In the 1-goal task
(left), the agent simply explores the scene, finds a path leading to the
destination. In the three-goal task (right), the agent continues to navigate
to two more successive goals that are probably set in visited areas.

###  3.2 Brief Review of Visual Graph Memory

The MemoNav is mainly built upon VGM [20], which is briefly introduced below.

VGM incrementally builds a topological map $G=\left\\{V,E\right\\}$ from the
agent’s past observations where $V$ and $E$ denote nodes and edges,
respectively. The node features (STM) $\mathbf{V}\in\mathbb{R}^{d\times
N_{t}}$ are generated from observations by a pretrained encoder
$\mathcal{F}_{loc}$ where $d$ denotes the dimension of feature and $N_{t}$ the
number of nodes at time $t$.

VGM updates the map in two steps: localization and graph update. Localization
is implemented by calculating embedding similarity. VGM first uses
$\mathcal{F}_{loc}$ to map the current observation $\rm{I}_{\emph{t}}$ to an
embedding $e_{t}\in\mathbb{R}^{d}$, and then calculates the similarities
$\left\\{s_{i}\mid s_{i}=\frac{n_{i}\cdot
e_{t}}{\left\|n_{i}\right\|\left\|e_{t}\right\|},i=1,2,\ldots,N_{t}\right\\}$
between $e_{t}$ and each node feature
$\mathbf{V}=\left\\{n_{1},n_{2},...,n_{N_{t}}\right\\}$. If the similarity of
a node $s_{i}$ is higher than a threshold $s_{th}$, this node is seen as near
the agent. Graph Update depends on three cases. (i) If the agent is localized
at the last node, the map will not be updated. (ii) If the localized node is
different from the last one, a new edge connecting these two nodes will be
created, and the feature of the localized node will be replaced with the new
embedding. (iii) If the agent fails to be localized, a new node with the
current observation embedding will be created, and a new edge will connect
this new node with the last node.

VGM utilizes a three-layer graph convolutional network (GCN) to process the
topological map and obtain the encoded memory $\mathbf{M}$ (i.e., a sequence
of feature vectors). Before the first layer, VGM fuses each feature of a node
with the target image embedding
$e_{target}=\mathcal{F}_{enc}(\mathbf{I}_{target})$ using a linear layer.

The encoded memory is then decoded by two Transformer decoders,
$\mathcal{D}ec_{cur}$ and $\mathcal{D}ec_{target}$. $\mathcal{D}ec_{cur}$
takes the current observation embedding
$e_{cur}=\mathcal{F}_{enc}(\mathbf{I}_{cur})$ as the query and the feature
vectors of the encoded memory $\mathbf{M}$ as the keys and values, generating
a feature vector $f_{cur}$. Similarly, $\mathcal{D}ec_{target}$ takes the
target embedding $e_{target}$ as the query and generates $f_{target}$. Lastly,
an LSTM-based policy network takes as input the concatenation of $f_{cur}$,
$f_{target}$ and $e_{cur}$, and outputs an action distribution.

##  4 Method

In this section, We expand the definition of ImageNav and describe our MemoNav
designed for multi-goal navigation tasks.

###  4.1 Multi-goal ImageNav

Single-goal tasks are not sufficient for thoroughly evaluating the potential
of memory mechanisms, since finding a single goal may not need all navigation
history. Hence, it remains unclear which fraction of navigation history is
useful for finding the goal. To further investigate how memory mechanisms
assist the agent in exploring the environment and locating the target, we
borrow the idea of MultiON [41] and collect multi-goal test datasets (an
example in Figure 1). In a multi-goal task, the agent navigates to an ordered
sequence of $N$ destinations $\left\\{\rm{T}\right\\}_{1}^{N}$ in the
environment. We place the final target within the vicinity of previous ones to
form a loop. By letting the agent return to visited places, we are able to
test whether memory mechanisms can help the agent plan a short path. If not,
the agent will probably waste its time re-exploring the scene or traveling
randomly.

Figure 2: Overview of the MemoNav. (a) The memory update module builds (b) a
topological map using $e_{t}$, the embedding of the current image
$\mathbf{I}_{t}$. The node features in the map form the short-term memory
while a global node that links to each of these map nodes acts as the long-
term memory. (c) The forgetting module temporarily excludes a fraction of
short-term memory whose attention scores rank below a threshold $p$. (d) The
working memory $\mathbf{H}_{t}$ incorporates the retained fraction of the
short-term memory and long-term memory for (e) the subsequent memory encoding
and decoding (details in the Appendix). Lastly, the output of the decoding
process is input to (f) the policy network.

###  4.2 Model Components

The MemoNav comprises three key components: the forgetting module, the global
node, and the GATv2-based memory encoder. We show the pipeline of the MemoNav
in Figure 2 and describe these components in the remainder of this section.

####  4.2.1 Working Memory Mechanism via Selective Forgetting

VGM (Section 3.2) decodes all STM in the map, thus introducing redundancy.
Inspired by previous studies on the forgetting mechanisms of animal brains
[23, 26, 31, 35, 37], we devise a forgetting module that instructs the agent
to forget uninformative experiences. Here, ‘forgetting’ means that nodes with
attention scores lower than a threshold are temporarily excluded from the
navigation pipeline. This means of forgetting via attention is evidenced by
research [2, 16] revealing that the optimal performance of working memory
relies on humans’ ability to focus attention on task-relevant information and
to avoid distractions. In Figure 3, we visualize the attention scores
calculated in $\mathcal{D}ec_{target}$ for the encoded STM. The figure shows
that the agent assigns high attention scores to nodes close to targets while
paying little to no attention to remote ones. This phenomenon indicates that
not all node features in the STM are helpful and that it is more efficient to
incorporate a small number of them in the WM for navigation.

With these insights, we propose a selective forgetting module that helps to
select STM to form WM according to the attention scores
$\left\\{\alpha_{i}\right\\}_{i=1}^{N_{t}}$ the goal embedding $e_{target}$
assigns to all nodes in $\mathcal{D}ec_{target}$. Each time
$\mathcal{D}ec_{target}$ finishes decoding, the agent temporarily ‘forgets’ a
fraction of nodes whose scores rank below a predefined percentage $p$. In
other words, these nodes will be disconnected from their neighbors, and not be
processed by the navigation pipeline at the subsequent time steps. If the
agent returns to a forgotten node, this node will be added to the map and
processed by the pipeline again. In a multi-goal task, once the agent has
reached a target, all forgotten nodes will be restored, as the nodes that are
uninformative for finding the last target may lead the agent to the next one.

The proposed forgetting mechanism is used in a plug-and-play manner. Our
default model sets $p$ as 20%. We train our model without forgetting in order
for it to learn to assign high attention scores to the informative fraction of
STM. When evaluating and deploying the agent, we switch on the forgetting
mechanism. With this mechanism, the agent can selectively incorporate the most
informative STM in the WM, while avoiding misleading experiences.

####  4.2.2 Long-term Memory Generation

Figure 3: VGM calculates redundant node features. The figure visualizes the
attention scores in $\mathcal{D}ec_{target}$ for an example episode.

In addition to STM, knowledge from LTM also forms part of WM [13]. Inspired by
ETC [1] and LongFormer [5], we add a zero-initialized global node
$n_{global}\in\mathbb{R}^{d}$ to the topological map as the LTM. This global
node is respawned at the beginning of each episode and continuously fuses the
STM via memory encoding (Figure 2 (e)), thereby storing past observations of
the agent. Moreover, the global node acts as the LTM in that it contains a
scene-level feature. A recent study [28] suggests that embodied agents must
learn higher-level representations of the 3D environment. From this viewpoint,
the LTM stores a high-level spatial representation of the scene by aggregating
local node features.

Another merit of the LTM is facilitating feature fusing. The topological map
is divided into several sub-graphs when forgotten nodes are removed.
Consequently, direct message passing between the nodes separated in different
sub-graphs no longer exists. The global node links to every node in the map,
thereby acting as a bypath that facilitates feature fusing between these
isolated sub-graphs.

####  4.2.3 GATv2-based Memory Processor

To generate LTM from STM that is dynamically updated by the agent, we change
the backbone of the memory encoder in VGM (Section 3.2) from GCN to GATv2 [7].
GATv2 differs from GCN [18] in that the weights for neighboring nodes are
derived from node features, instead of the Laplacian matrix.

Brody et al. [7] claimed that GATv2 is powerful when different nodes have
different rankings of neighbors. This is exactly the case in multi-goal
ImageNav: the extents to which different nodes contribute to leading the agent
to the goal are diverse. When the LTM aggregates the STM via the attention
mechanism in GATv2, the STM features that contain information about the target
or a path leading to the target should obtain high attention, while those of
irrelevant places should receive lower attention. Furthermore, the node
features in the STM are dynamically updated during navigation, as the agent
replaces these features with new ones when revisiting these nodes. Therefore,
the dynamic attention mechanism of GATv2 is more suitable for processing the
STM that dynamically varies during navigation.

Combining the STM $\mathbf{V}$, LTM $n_{global}$ and GATv2-based processor
$\mathcal{F}_{proc}$, the memory processing is formulated as follows:

$\left\\{\mathbf{V}^{l+1},n_{global}^{l+1}\right\\}=\operatorname{GATv2}\left(\left\\{\mathbf{V}^{l},n_{global}^{l}\right\\}\right),\quad\mathbf{M}^{\prime}=\mathcal{F}_{proc}(G;\psi)=\left\\{\mathbf{V}^{3},n_{global}^{3}\right\\}$
(1)

where $l=0,1,2$ represents the layer number, $\mathbf{M}^{\prime}$ the encoded
working memory, and $\psi$ the processor parameters.
$\left\\{\cdot,\cdot\right\\}$ denotes concatenation along the sequence
dimension.

After the processing of GATv2, the decoders $\mathcal{D}ec_{cur}$ and
$\mathcal{D}ec_{target}$ take $\mathbf{M}^{\prime}$ as keys and queries,
generating $f_{target}$ and $f_{cur}$, which fuse both LTM and STM.

##  5 Experiments

###  5.1 Simulation Settings

All experiments are conducted in the Habitat [33] simulator with the Gibson
[42] scene dataset. Following VGM [20], we train all models with 72 scenes,
and evaluate them on a public 1-goal dataset [25] that comprises 1400 episodes
for 14 unseen scenes. For a fair comparison, 1007 sampled episodes are used
for evaluating our model on 1-goal tasks, while 1400 episodes are used for
conducting ablation studies. In addition, we generate 700-episode datasets for
a multi-goal task by ourselves (see the Appendix). The difficulty of an
episode is indicated by the number of goals 111The 1-goal difficulty level
here denotes the hard level in the public test dataset All baselines and our
model are trained on the 1-goal dataset and tested on other difficulty levels.

The action space of the agent consists of four options: `stop`, `forward`,
`turn_left`, and `turn_right`. When the agent performs a `forward` action, the
agent moves 0.25m forward. A turning action rotates the agent by 10 degrees.
The agent is allowed to take at most 500 steps in either 1-goal or multi-goal
tasks. The agent succeeds in an episode if it performs `stop` within a 1m
radius of each target location. The agent fails if it performs `stop` anywhere
else or runs out of time step budget.

###  5.2 Training Techniques

Following VGM [20], we first train the agent using imitation learning,
minimizing the negative log-likelihood of the ground-truth actions. Next, we
finetune the agent’s policy with proximal policy optimization (PPO) [34] to
improve the exploratory ability of the agent. The reward setting and auxiliary
losses remain the same as in VGM. All our models are obtained on a TITAN RTX
GPU.

###  5.3 Baselines

We compare the proposed model with baselines that also utilize memory
mechanisms. Random is an agent taking random actions with oracle stopping. ANS
[8] and Exp4nav [11] are metric map-based models proposed for the task of
exploration. They are adapted for ImageNav in the experiments of VGM [20]. SMT
[14] stacks past observations in chronological order and uses a Transformer
decoder to further process them. Neural Planner [4] needs to explore the scene
first to pre-build a topological map. Once the map is built, this method
performs a hierarchical planning strategy to generate navigation actions. NTS
[9] incrementally builds a topological map without pre-exploring. Its
navigation strategy follows two steps: a global policy samples a subgoal, and
then a local policy takes navigational actions to reach the subgoal. VGM [20]
(see Section 3.2) is the baseline the MemoNav is built on. The quantitative
results of these baselines on 1-goal tasks are from [20]. We re-evaluate VGM
and report the new results.

###  5.4 Evaluation Metrics

In 1-goal tasks, the success rate (SR) and success weighted by path length
(SPL) [2] are used. In a multi-goal task, we borrow two metrics from [41]: the
Progress (PR) and progress weighted by path length (PPL). PR is the fraction
of goals that are successfully reached, equal to the SR for 1-goal tasks. PPL
indicates navigation efficiency and is defined as
$PPL=\frac{1}{E}\sum_{i=1}^{E}Progress_{i}\frac{l_{i}}{\max\left(p_{i},l_{i}\right)}$,
where $E$ is the total number of test episodes, $l_{i}$ and $p_{i}$ are the
shortest path distance to the final goal via midway ones, and the actual path
length taken by the agent, respectively.

###  5.5 Quantitative Results

Table 1: Evaluation results of the baselines and our model on the 1-goal test dataset. (SR: success rate, SPL: success weighted by path length) Methods | Memory Type | SR | SPL | Methods | Memory Type | SR | SPL
---|---|---|---|---|---|---|---
Random | - | 0.17 | 0.05 |  Neural Planner [4] | graph | 0.42 | 0.27
ANS [8] | metric map | 0.30 | 0.11 |  NTS [9] | graph | 0.43 | 0.26
Exp4nav [11] | metric map | 0.47 | 0.39 |  VGM [20] | graph | 0.75 | 0.58
SMT [14] | stack | 0.56 | 0.40 | MemoNav (ours) | graph | 0.78 | 0.54
Table 2: Evaluation results of the VGM and our model on the multi-goal test datasets. (PR: progress, PPL: progress weighted by path length) Methods | 2-goal | 3-goal | 4-goal
---|---|---|---
PR | PPL | PR | PPL | PR | PPL
Random | 0.05 | 0.01 | 0.03 | 0.00 | 0.02 | 0.00
VGM [20] | 0.45 | 0.18 | 0.33 | 0.08 | 0.28 | 0.05
MemoNav (ours) | 0.50 | 0.17 | 0.42 | 0.09 | 0.31 | 0.05

Comparison on 1-goal tasks. Table 1 shows that the proposed method outperforms
all the baselines in SR on the 1-goal dataset. Compared with the metric map-
based methods (Exp4nav [11] and Neural Planner [4]), our model enjoys a large
improvement in SR (from 0.47 to 0.78) and SPL (from 0.39 to 0.54). The two
baselines require pre-built maps but exhibit lower SR and SPL. This is partly
because the explored areas fail to cover the target place. Compared with VGM
[20], our model exhibits a slight performance gain, increasing the SR by 0.03
while using 20% fewer node features. This result indicates that VGM uses
redundant past observations that probably interfere with the agent’s
navigation. In contrast, our agent uses the informative fraction of these
observation, obtaining a higher success rate with less past information. The
SPL slightly decreases, probably because the agent forgets a certain
proportion of explored places and spends more time re-exploring.

Comparison on a multi-goal task. In Table 2, we compare the MemoNav with VGM
[20] on a multi-goal task. As the difficulty level rises from 1 goal to 4
goals, both methods witness drops in the navigation success rate, but the
MemoNav is more robust and more competent to complete a multi-goal task. At
the 2-goal level, the MemoNav outperforms VGM in PR by 0.05 (11.1%). When the
number of goals increases to 3, the performance gap widens: the improvement in
PR rises to 0.09 (27.2%). At the 4-goal level, the two methods both perform
worse, but our method still surpasses VGM in PR by a noticeable margin of 0.03
(10.7%).

###  5.6 Ablation Studies and Analysis

Table 3: Network component ablation results. Row 1 is the baseline model VGM [20], and row 7 is our full model. (GATv2: the GATv2-based memory encoder, LTM: the long-term memory, FG20%: forgetting nodes whose attention scores rank below 20%)  | Components | 1-goal | 2-goal | 3-goal | 4-goal
---|---|---|---|---|---
GATv2 | LTM | FG20% | SR | SPL | PR | PPL | PR | PPL | PR | PPL
1 |  |  |  | 0.621 | 0.494 | 0.449 | 0.178 | 0.329 | 0.080 | 0.276 | 0.054
2 | ✓ |  |  | 0.618 | 0.533 | 0.452 | 0.193 | 0.377 | 0.080 | 0.307 | 0.060
3 |  | ✓ |  | 0.617 | 0.521 | 0.489 | 0.207 | 0.385 | 0.092 | 0.311 | 0.057
4 |  |  | ✓ | 0.611 | 0.478 | 0.472 | 0.187 | 0.327 | 0.079 | 0.279 | 0.056
5 |  | ✓ | ✓ | 0.617 | 0.527 | 0.491 | 0.202 | 0.403 | 0.098 | 0.301 | 0.056
6 | ✓ | ✓ |  | 0.623 | 0.462 | 0.496 | 0.163 | 0.417 | 0.084 | 0.313 | 0.050
7 | ✓ | ✓ | ✓ | 0.610 | 0.461 | 0.498 | 0.171 | 0.421 | 0.087 | 0.314 | 0.049

The performance gain of each proposed component. We ablate the three key
components described in Section 4.2, and show the results in Table 3.
Comparing rows 2, 3, and 4 with row 1 (VGM), we can see that the LTM brings
the largest improvement over the baseline at the 2, 3, and 4-goal levels among
the three components. For example, the LTM brings an increase in PR by 0.056
at the 3-goal level. Although applying the forgetting module only achieves
improvements at the 2 and 4-goal levels, its cooperation with the LTM
witnesses a significant increase in the SR/PR at the 1, 2, and 3-goal levels.
More importantly, compared with VGM (row 1), the synergy of the three
components (row 7) increases the PR by 0.049 (10.9%), 0.092 (21.9%), 0.038
(13.8%) at the 2, 3 and 4-goal levels respectively. These results demonstrate
that the three components are helpful for solving long-time navigation tasks
with multiple sequential goals.

The importance of the LTM. Table 4 presents the results of ablation
experiments that demonstrate the importance of the LTM (described in Section
4.2.2). The first ablation (row 2) is to replace the feature in the LTM with
that of a randomly selected node in the STM once the GATv2 encoding is
finished so that the LTM is disabled. Row 2 shows that the agent’s performance
decreases at all difficulty levels compared with the full model (row 1).
Furthermore, when the LTM feature is not incorporated into the WM (row 3), the
performance also deteriorates. In summary, the LTM stores a scene-level
feature essential for improving the success rate.

Table 4: Ablation study of the LTM. | Methods | 1-goal | 2-goal | 3-goal | 4-goal
---|---|---|---|---|---
SR | SPL | PR | PPL | PR | PPL | PR | PPL
1 | Ours | 0.610 | 0.461 | 0.498 | 0.171 | 0.421 | 0.087 | 0.314 | 0.049
2 | Ours w. random replace | 0.602 | 0.365 | 0.464 | 0.122 | 0.373 | 0.065 | 0.306 | 0.046
3 | Ours w.o. decoding LTM | 0.604 | 0.456 | 0.492 | 0.169 | 0.393 | 0.083 | 0.309 | 0.048

(a) SPL/PPL v.s. $p$

(b) SR/PR v.s. $p$

(c) Average steps v.s. $p$

Figure 4: The agent’s navigation performance at different forgetting threshold
$p$.

The correlation between the difficulty level and forgetting threshold. We
evaluate our model with different forgetting thresholds $p$ used by the WM
(see Section 4.2.1). The results are shown in Figure 4. For clarity, the
figure shows the performance differences between our default model (row 7 in
Table 3) and the variants. The four levels exhibit different trends: when $p$
increases (i.e., a larger fraction of STM is not incorporated into the WM),
our model first witnesses increases and then drops in the SR/PR and SPL/PPL at
the 3 and 4-goal levels while enjoying slight gains in these metrics at the 1
and 2-goal levels. At the 1-goal level, our model obtains the highest SR and
SPL when $p=80\%$, which means that a large fraction of node features in the
map are useless when the navigation task is easy. A similar trend can also be
seen at the 2-goal level. In contrast, our model exhibits an increase in the
PR (from 0.313 to 0.321) and PPL (from 0.049 to 0.050) at the 4-goal level
when $p$ rises from 0% to 40%. However, if $p$ rises to 80%, the two metrics
see a precipitous decline, and the agent takes more than 20 steps to complete
the tasks. These results suggest that excluding unimportant STM from the WM
improves navigation performance in multi-goal navigation tasks. However,
excluding an excessive fraction forces the agent not to utilize what it has
explored, thus reducing the navigation efficiency.

Figure 5: Visualization of example episodes. we compare selected episodes of
the VGM (top row) and our MemoNav (bottom row) at four difficulty levels and
visualize the top-down views. The number of navigation steps are shown at the
bottom of each top-down view. Best viewed in color.

###  5.7 Visualization Results

To observe how the MemoNav improves the navigation performance, we show
example episodes of VGM and our model at the four difficulty levels in Fig 5
(more examples are provided in the Appendix). We can see that the MemoNav
agent takes fewer steps and its trajectories are smoother. VGM tends to spend
a large proportion of time going in circles in narrow pathways. For instance,
the 1st and 3rd columns in Figure 5 show that the VGM agent is trapped in a
bottleneck connecting two rooms, while our agent uses the time steps wasted by
VGM to efficiently explore the scene. This comparison shows that the MemoNav
is more capable of avoiding deadlock.

Figure 6: Histogram of normalized path lengths of successful episodes for VGM
[20] and our model. Our model has more short trajectories while VGM has a
larger proportion of long episodes.

We next draw a histogram of the normalized path lengths of successful episodes
for VGM and our model to further investigate to what degree our model avoids
deadlock. The normalized path length is calculated as
$l_{norm}=l_{i}/\max\left(p_{i},l_{i}\right)-1$ where $p_{i}$ and $l_{i}$ are
defined in Section 5.4. $l_{norm}$ indicates how many extra steps the agent
takes compared to the shortest path. A larger $l_{norm}$ represents a less
efficient navigation episode. Figure 6 shows that the histogram of our model
exhibits a less heavier-tailed distribution, especially on the 3-goal dataset.
This distribution means that our model has fewer episodes with an extremely
large number of steps. This result agrees with the visualization in Figure 5 ,
as it suggests that our model utilizes goal-relevant navigation history stored
in the WM to reduce the number of wasted steps.

Analyzing these results, the reason why our model helps the agent escape from
loops is twofold. Firstly, the WM excludes misleading node features and
reduces the interference of irrelevant past observations. Secondly, the LTM
provides the agent with a scene-level context that helps it locate the target
from a global view.

##  6 Conclusion

This paper proposes MemoNav, a memory mechanism for ImageNav. This model
flexibly retains the informative fraction of the short-term navigation memory
via a forgetting module. We also add an extra global node to the topological
map as a long-term memory that aggregates features in the short-term memory.
The retained short-term memory and the long-term memory form the working
memory that is used for generating action, Our model is only trained on a
1-goal dataset. Nevertheless, it is capable of solving a multi-goal navigation
task. The results show that the MemoNav outperforms the baselines in 1-goal
and multi-goal tasks and is more capable of escaping from deadlock.

## Acknowledgements

We would like to acknowledge Yuxi Wang, Yuqi Wang, Lue Fan, He Guan, Jiawei
He, Zeyu Wang and the anonymous reviewers for their help, comments and
suggestions.

## Licenses for Referenced Datasets

Gibson: http://svl.stanford.edu/gibson2/assets/GDS_agreement.pdf

## References

  * Ainslie et al. [2020] J. Ainslie, S. Ontanon, C. Alberti, V. Cvicek, Z. Fisher, P. Pham, A. Ravula, S. Sanghai, Q. Wang, and L. Yang.  Etc: Encoding long and structured inputs in transformers.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 268–284, 2020.
  * Anderson et al. [2018] P. Anderson, A. Chang, D. S. Chaplot, A. Dosovitskiy, S. Gupta, V. Koltun, J. Kosecka, J. Malik, R. Mottaghi, M. Savva, et al.  On evaluation of embodied navigation agents.  _arXiv preprint arXiv:1807.06757_ , 2018.
  * Baddeley [2012] A. Baddeley.  Working memory: theories, models, and controversies.  _Annual review of psychology_ , 63:1–29, 2012.
  * Beeching et al. [2020] E. Beeching, J. Dibangoye, O. Simonin, and C. Wolf.  Learning to plan with uncertain topological maps.  In _ECCV 2020-16th European Conference on Computer Vision_ , pages 1–24, 2020.
  * Beltagy et al. [2020] I. Beltagy, M. E. Peters, and A. Cohan.  Longformer: The long-document transformer.  _arXiv preprint arXiv:2004.05150_ , 2020.
  * Blacker et al. [2017] K. J. Blacker, S. M. Weisberg, N. S. Newcombe, and S. M. Courtney.  Keeping track of where we are: Spatial working memory in navigation.  _Visual Cognition_ , 25(7-8):691–702, 2017.
  * Brody et al. [2022] S. Brody, U. Alon, and E. Yahav.  How attentive are graph attention networks?  In _International Conference on Learning Representations_ , 2022.  URL https://openreview.net/forum?id=F72ximsx7C1.
  * Chaplot et al. [2020a] D. S. Chaplot, D. Gandhi, S. Gupta, A. Gupta, and R. Salakhutdinov.  Learning to explore using active neural slam.  In _International Conference on Learning Representations (ICLR)_ , 2020a.
  * Chaplot et al. [2020b] D. S. Chaplot, R. Salakhutdinov, A. Gupta, and S. Gupta.  Neural topological slam for visual navigation.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 12875–12884, 2020b.
  * Chen et al. [2021] K. Chen, J. K. Chen, J. Chuang, M. Vázquez, and S. Savarese.  Topological planning with transformers for vision-and-language navigation.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 11276–11286, 2021.
  * Chen et al. [2019] T. Chen, S. Gupta, and A. Gupta.  Learning exploration policies for navigation.  In _International Conference on Learning Representations_ , 2019.  URL https://openreview.net/pdf?id=SyMWn05F7.
  * Cowan [2008] N. Cowan.  What are the differences between long-term, short-term, and working memory?  _Progress in brain research_ , 169:323–338, 2008.
  * Ericsson and Kintsch [1995] K. A. Ericsson and W. Kintsch.  Long-term working memory.  _Psychological review_ , 102(2):211, 1995.
  * Fang et al. [2019] K. Fang, A. Toshev, L. Fei-Fei, and S. Savarese.  Scene memory transformer for embodied agents in long-horizon tasks.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 538–547, 2019.
  * Foo et al. [2005] P. Foo, W. H. Warren, A. Duchon, and M. J. Tarr.  Do humans integrate routes into a cognitive map? map-versus landmark-based navigation of novel shortcuts.  _Journal of Experimental Psychology: Learning, Memory, and Cognition_ , 31(2):195, 2005.
  * Fukuda and Vogel [2009] K. Fukuda and E. K. Vogel.  Human variation in overriding attentional capture.  _Journal of Neuroscience_ , 29(27):8726–8733, 2009.
  * Gillner and Mallot [1998] S. Gillner and H. A. Mallot.  Navigation and acquisition of spatial knowledge in a virtual maze.  _Journal of cognitive neuroscience_ , 10(4):445–463, 1998.
  * Kipf and Welling [2017] T. N. Kipf and M. Welling.  Semi-supervised classification with graph convolutional networks.  In _International Conference on Learning Representations (ICLR)_ , 2017.
  * Kumar et al. [2018] A. Kumar, S. Gupta, D. Fouhey, S. Levine, and J. Malik.  Visual memory for robust path following.  _Advances in neural information processing systems_ , 31, 2018.
  * Kwon et al. [2021] O. Kwon, N. Kim, Y. Choi, H. Yoo, J. Park, and S. Oh.  Visual graph memory with unsupervised representation for visual navigation.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , pages 15890–15899, 2021.
  * Lampinen et al. [2021] A. Lampinen, S. Chan, A. Banino, and F. Hill.  Towards mental time travel: a hierarchical memory for reinforcement learning agents.  _Advances in Neural Information Processing Systems_ , 34, 2021.
  * Loynd et al. [2020] R. Loynd, R. Fernandez, A. Celikyilmaz, A. Swaminathan, and M. Hausknecht.  Working memory graphs.  In _International Conference on Machine Learning_ , pages 6404–6414. PMLR, 2020.
  * Manning [2021] J. R. Manning.  Episodic memory: Mental time travel or a quantum “memory wave” function?  _Psychological review_ , 128(4):711, 2021.
  * Mansouri et al. [2015] F. A. Mansouri, M. G. Rosa, and N. Atapour.  Working memory in the service of executive control functions.  _Frontiers in Systems Neuroscience_ , 9:166, 2015.
  * Mezghani et al. [2021] L. Mezghani, S. Sukhbaatar, T. Lavril, O. Maksymets, D. Batra, P. Bojanowski, and K. Alahari.  Memory-augmented reinforcement learning for image-goal navigation.  _arXiv preprint arXiv:2101.05181_ , 2021.
  * Nematzadeh et al. [2020] A. Nematzadeh, S. Ruder, and D. Yogatama.  On memory in human and artificial language processing systems.  In _Proceedings of ICLR Workshop on Bridging AI and Cognitive Science_ , 2020.
  * Pashevich et al. [2021] A. Pashevich, C. Schmid, and C. Sun.  Episodic transformer for vision-and-language navigation.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , pages 15942–15952, 2021.
  * Ramakrishnan et al. [2022] S. K. Ramakrishnan, T. Nagarajan, Z. Al-Halah, and K. Grauman.  Environment predictive coding for visual navigation.  In _International Conference on Learning Representations_ , 2022.  URL https://openreview.net/forum?id=DBiQQYWykyy.
  * Ravizza et al. [2021] S. M. Ravizza, T. J. Pleskac, and T. Liu.  Working memory prioritization: Goal-driven attention, physical salience, and implicit learning.  _Journal of Memory and Language_ , 121:104287, 2021.
  * Ritter et al. [2021] S. Ritter, R. Faulkner, L. Sartran, A. Santoro, M. Botvinick, and D. Raposo.  Rapid task-solving in novel environments.  In _International Conference on Learning Representations_ , 2021.  URL https://openreview.net/forum?id=F-mvpFpn_0q.
  * Sabandal et al. [2021] J. M. Sabandal, J. A. Berry, and R. L. Davis.  Dopamine-based mechanism for transient forgetting.  _Nature_ , 591(7850):426–430, 2021.
  * Savinov et al. [2018] N. Savinov, A. Dosovitskiy, and V. Koltun.  Semi-parametric topological memory for navigation.  In _International Conference on Learning Representations_ , 2018.
  * Savva et al. [2019] M. Savva, A. Kadian, O. Maksymets, Y. Zhao, E. Wijmans, B. Jain, J. Straub, J. Liu, V. Koltun, J. Malik, et al.  Habitat: A platform for embodied ai research.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , pages 9339–9347, 2019.
  * Schulman et al. [2017] J. Schulman, F. Wolski, P. Dhariwal, A. Radford, and O. Klimov.  Proximal policy optimization algorithms.  _arXiv preprint arXiv:1707.06347_ , 2017.
  * Suddendorf et al. [2009] T. Suddendorf, D. R. Addis, and M. C. Corballis.  Mental time travel and the shaping of the human mind.  _Philosophical Transactions of the Royal Society B: Biological Sciences_ , 364(1521):1317–1324, 2009.
  * Sukhbaatar et al. [2021] S. Sukhbaatar, D. Ju, S. Poff, S. Roller, A. Szlam, J. Weston, and A. Fan.  Not all memories are created equal: Learning to forget by expiring.  In _International Conference on Machine Learning_ , pages 9902–9912. PMLR, 2021.
  * Tulving [1985] E. Tulving.  Memory and consciousness.  _Canadian Psychology/Psychologie canadienne_ , 26(1):1, 1985.
  * Vaswani et al. [2017] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, Ł. Kaiser, and I. Polosukhin.  Attention is all you need.  _Advances in neural information processing systems_ , 30, 2017.
  * Wallace [1960] A. Wallace.  Plans and the structure of behavior . george a. miller, eugene galanter, karl h. pribram.  _American Anthropologist_ , 62(6):1065–1067, 1960\.
  * Wang and Spelke [2002] R. F. Wang and E. S. Spelke.  Human spatial representation: Insights from animals.  _Trends in cognitive sciences_ , 6(9):376–382, 2002.
  * Wani et al. [2020] S. Wani, S. Patel, U. Jain, A. Chang, and M. Savva.  Multion: Benchmarking semantic map memory using multi-object navigation.  _Advances in Neural Information Processing Systems_ , 33:9700–9712, 2020.
  * Xia et al. [2018] F. Xia, A. R. Zamir, Z. He, A. Sax, J. Malik, and S. Savarese.  Gibson env: Real-world perception for embodied agents.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 9068–9079, 2018.

## Checklist

  1. 1.

For all authors…

    1. (a)

Do the main claims made in the abstract and introduction accurately reflect
the paper’s contributions and scope? [Yes] See Figure 1 right and Figure‘2.

    2. (b)

Did you describe the limitations of your work? [Yes] Refer to Section 5.6 for
the discussion about how the forgetting module probably undermines navigation
efficiency. Additional description of the limitations of the proposed model is
placed in the supplementary materials.

    3. (c)

Did you discuss any potential negative societal impacts of your work? [N/A]

    4. (d)

Have you read the ethics review guidelines and ensured that your paper
conforms to them? [Yes]

  2. 2.

If you are including theoretical results…

    1. (a)

Did you state the full set of assumptions of all theoretical results? [N/A]

    2. (b)

Did you include complete proofs of all theoretical results? [N/A]

  3. 3.

If you ran experiments…

    1. (a)

Did you include the code, data, and instructions needed to reproduce the main
experimental results (either in the supplemental material or as a URL)? [Yes]
Refer to the supplementary materials for detailed instructions of how to
reproduce the results, which include hyperparameters, implementation details
and data generation process.

    2. (b)

Did you specify all the training details (e.g., data splits, hyperparameters,
how they were chosen)? [Yes]

    3. (c)

Did you report error bars (e.g., with respect to the random seed after running
experiments multiple times)? [No] We decided not to report error bars with
respect to multiple random seeds, since multiple experiments on training the
proposed model and the baselines exhibit large performance diversity. In
addition, training the proposed model and the baselines is time-consuming and
expensive.

    4. (d)

Did you include the total amount of compute and the type of resources used
(e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See the
supplementary materials.

  4. 4.

If you are using existing assets (e.g., code, data, models) or
curating/releasing new assets…

    1. (a)

If your work uses existing assets, did you cite the creators? [Yes]

    2. (b)

Did you mention the license of the assets? [Yes]

    3. (c)

Did you include any new assets either in the supplemental material or as a
URL? [N/A]

    4. (d)

Did you discuss whether and how consent was obtained from people whose data
you’re using/curating? [N/A]

    5. (e)

Did you discuss whether the data you are using/curating contains personally
identifiable information or offensive content? [N/A]

  5. 5.

If you used crowdsourcing or conducted research with human subjects…

    1. (a)

Did you include the full text of instructions given to participants and
screenshots, if applicable? [N/A]

    2. (b)

Did you describe any potential participant risks, with links to Institutional
Review Board (IRB) approvals, if applicable? [N/A]

    3. (c)

Did you include the estimated hourly wage paid to participants and the total
amount spent on participant compensation? [N/A]

##  Appendix A Appendix

###  A.1 Open-sourced Code

We have open-sourced the implementation of the MemoNav, which can be found at:
*

###  A.2 Limitations

While the MemoNav witnesses a large improvement in the navigation success rate
in multi-goal navigation tasks, it still encounters limitations. The proposed
forgetting module is a post-processing method, as it has to obtain the
attention scores of the decoder before deciding which nodes are to be
forgotten. Future work can explore trainable forgetting modules. The second
limitation is that our forgetting module does not reduce memory footprint,
since the features of the forgotten nodes still exist in the map for
localization. Moreover, the forgetting threshold in our experiments is fixed.
Future work can merge our idea with Expire-span [36] to learn an adaptive
forgetting threshold.

###  A.3 Representative Models of Human Memory

Cowan et al. [12] proposed a typical model describing the relationships among
long-term memory (LTM), short-term memory (STM), and working memory (WM) of
the human brain. According to their definitions, LTM is a large knowledge base
and a record of prior experience; STM reflects faculties of the human mind
that hold a limited amount of information in a very accessible state
temporarily; WM includes part of STM and other processing mechanisms that help
to utilize STM. Cowan et al. designed a framework depicting how WM is formed
from STM and LTM (shown in Figure 7). This framework demonstrates that STM is
derived from a temporarily activated subset of LTM. This activated subset may
decay as a function of time unless it is refreshed. The useful fraction of STM
is incorporated into WM via an attention mechanism to avoid misleading
distractions. Subsequent work by Baddeley et al. [3] suggests that the central
executive manipulates memory by incorporating not only part of STM but also
part of LTM to assist in making a decision.

We draw inspirations from the work by Cowan et al. [12] and Baddeley et al.
[3] and reformulate the agent’s navigation experience as the three types of
memory defined above. The agent’s current observations are analogous to STM
since they are temporarily stored in the topological map; the global node
aggregates graph node features and saves navigation history, thereby acting as
LTM; the forgetting module retains the goal-relevant fraction of STM and
incorporates the retained STM and LTM into WM, which is then input to the
policy network.

Figure 7: The memory model by Cowan et al. [12]. This figure is borrowed and
adapted from its original paper.

###  A.4 Implementation Details

####  A.4.1 Model Architecture

Table 5: Network architecture of our model Param | Meaning | Value
---|---|---
$\mathcal{F}_{loc}$ | The pre-trained encoder used for map update | ResNet18
$d$ | The dimension of node feature | 512
$\mathcal{F}_{enc}$ |  | The trainable encoder for embedding
---
observation and target images
ResNet18
$L$ | The number of GATv2 layers | 3
$H$ | The number of decoder heads | 4

The structure of the memory encoding and decoding module (Figure 2(e) in the
main paper) in the MemoNav remains the same as in the VGM [20] and is shown in
Figure 8. We maintain the module hyper-parameters specified in the
supplementary of the VGM paper and list them in Table 5 for convenience.

Figure 8: The structure of the memory encoding and decoding module displayed
in Figure 2 of the main paper. $\mathbf{H}_{t}$ and $\mathbf{M}_{t}^{\prime}$
are the working memory before and after encoding. The attention scores
$\mathbf{\alpha}$ generated in $\mathcal{D}ec_{target}$ are used in the
forgetting module to retain informative STM.

####  A.4.2 Implementation of the MemoNav

The forgetting module on the MemoNav requires the attention scores generated
in the decoder $\mathcal{D}ec_{target}$. Therefore, our model needs to
calculate the whole navigation pipeline before deciding which fraction of the
STM should be retained. This lag means that the retained STM is incorporated
into the WM at the next time step. The pseudo-code of the MemoNav is shown in
Algorithm 1

Data: Empty topological map $G=\left\\{V,E\right\\}$, target image
$\mathbf{I}_{target}$, current time step $t$, forgetting percentage $p$,
trainable observation encoder $\mathcal{F}_{enc}$, GATv2-based encoder
$\operatorname{GATv2}$, Transformer decoders $\mathcal{D}ec_{target}$ and
$\mathcal{D}ec_{cur}$, LSTM-based policy network $\operatorname{LSTM}$

Result: Navigation action $a_{t}$

1 Long-term memory $n_{global}\leftarrow\mathbf{0}\in\mathbb{R}^{d}$;

2 Attention scores for graph nodes $V$:
$\mathbf{\alpha}\leftarrow\mathbf{0}\in\mathbb{R}^{\lvert V\rvert}$;

3 while  _not $\operatorname{AgentCallStop}\left(\right)$_ do

// Step 1: Update the topological map

4 $\mathbf{I}_{t}\leftarrow\operatorname{GetCurrentPanorama}()$;

5 $G.\operatorname{UpdateMap}\left(\mathbf{I}_{t}\right)$;

6

// Step 2: Retain the informative fraction of the STM

7 Forgotten number $n\leftarrow\operatorname{Floor}\left(p\cdot\lvert
V\rvert\right)$;

8 Sorted indices
$i\leftarrow\operatorname{Argsort}\left(\mathbf{\alpha}\right)$;

9

10 Forgotten indices $i_{for}\leftarrow i\left[0\colon n\right]$;

11 $G.\operatorname{RemoveNodes}\left(i_{for}\right)$;

12

// Step 3: Memory encoding and decoding

13 $\mathbf{V}\in\mathbb{R}^{\lvert V\rvert\times d}\leftarrow
G.\operatorname{GetNodeFeatures}\left(\right)$;

14 Encoded memory
$\mathbf{M}^{\prime}\leftarrow\operatorname{GATv2}\left(\left\\{\mathbf{V},n_{global}\right\\}\right)$;

15 $e_{cur}\leftarrow\mathcal{F}_{enc}(\mathbf{I}_{t}),\
e_{target}\leftarrow\mathcal{F}_{enc}(\mathbf{I}_{target})$;

16
$f_{cur}\leftarrow\mathcal{D}ec_{cur}\left(e_{cur},\mathbf{M}^{\prime}\right),\
f_{target}\leftarrow\mathcal{D}ec_{target}\left(e_{target},\mathbf{M}^{\prime}\right)$;

17
$\mathbf{\alpha}\leftarrow\mathcal{D}ec_{target}.\operatorname{GetAttScores}\left(\right)$

// Step 4: Action generation

18
$x\leftarrow\operatorname{LSTM}\left(\operatorname{FC}\left(\left[f_{cur},f_{target},e_{cur}\right]\right)\right)$;

19 $p\left(a_{t}\mid
x\right)=\sigma\left(\operatorname{FC}\left(x\right)\right)$;

20 $a_{t}\leftarrow\operatorname{SampleFromDistribution}\left(p\left(a_{t}\mid
x\right)\right)$;

21

22 end while

23

Algorithm 1 The implementation of the MemoNav

####  A.4.3 Training Details

We follow the two-step training routine and maintain the training hyper-
parameters shown in Table 5 of the VGM paper [20]. Our model is trained using
imitation learning for 20k steps. Afterward, we finetune our model using PPO
[34] for 10M steps. Due to the performance fluctuation intrinsic to
reinforcement learning, the model at the 10M-th step is probably not the best.
Therefore, we evaluate all checkpoints in the step range [9M, 10.4M] and
select the best one. Our model compared with the baselines is the checkpoint
at the 9.4M-th step.

####  A.4.4 Details of Collecting Multi-goal Datasets

We follow the format of the public 1-goal dataset in [25] and create 2-goal,
3goal, and 4-goal test datasets on the Gibson [42] scene dataset. We generate
50 samples for each of the 14 test scenes. In each sample, we randomly choose
target positions while still following five rules: (1) no obstacles appear
inside a circle with a radius of 0.75 meters centered at each target; (2) the
distance between two successive targets is no more than 10 meters; (3) all
targets are placed on the same layer without altitude differences. (4) all
targets are reachable from each other. (5) The final target is placed near a
certain previous one with the distance between them smaller than 1.5 meters.
The distributions of the total geodesic distances for the three difficulty
levels are shown in Figure 9.

####  A.4.5 Compute Requirements

We utilize an RTX TITAN GPU for training and evaluating our models. The
imitation learning phase takes 1.5 days to train while the reinforcement
learning takes 5 days.

The computation in the GATv2-based encoder and the two Transformer decoders
occupy the largest proportion of the run-time of the MemoNav. The computation
complexity of the encoder and the decoders are $\mathcal{O}\left(\lvert
V\rvert d^{2}+\lvert E\rvert d\right)$ and $\mathcal{O}\left(\lvert V\rvert
d\right)$, respectively. Using the forgetting module with a percentage
threshold $p$, the computation complexity of the MemoNav can be flexibly
decreased by reducing the number of nodes to $p\lvert V\rvert$.

Figure 9: Histograms of geodesic distances for the multi-goal test datasets.

###  A.5 Extra Ablation Studies

We conduct extra ablation experiments on the forgetting module in the MemoNav
to further investigate how its design affects the agent’s navigation
performance. The results are shown in Table 6.

The origin of the attention scores used by the forgetting module. The
forgetting module in the MemoNav removes the uninformative STM according to
the attention scores generated in $\mathcal{D}ec_{target}$, as described in
Section 4.2.1. We change these scores to those generated in
$\mathcal{D}ec_{cur}$. The result (row 2) shows that using the attention
scores generated in $\mathcal{D}ec_{cur}$ as in $\mathcal{D}ec_{target}$,
which means that the two decoders can both decide which fraction of the STM is
informative. We choose $\mathcal{D}ec_{target}$ since it brings larger
performance gains.

The effectiveness of the forgetting module. This ablation investigates whether
it is effective to exclude the STM with attention scores ranking below the
predefined percentage $p$. In this experiment,the forgetting module excludes a
random fraction of the STM. We test this ablation model over five random seeds
and report the average metrics. The result (row 3) shows that incorporating a
random fraction of the STM into the WM leads to decreases in all metrics,
which validates the effectiveness of our design for retaining informative STM.

Training the MemoNav with the forgetting module. As described in Section
4.2.1, the MemoNav is trained without the forgetting module. Here, we test the
performance of the MemoNav trained with this module. The result (row 3) shows
that training the MemoNav with the forgetting module leads to worse
performance at the four difficulty levels.

Table 6: Extra ablation studies of the forgetting module. | Methods | 1-goal | 2-goal | 3-goal | 4-goal
---|---|---|---|---|---
SR | SPL | PR | PPL | PR | PPL | PR | PPL
1 | Ours | 0.610 | 0.461 | 0.498 | 0.171 | 0.421 | 0.087 | 0.314 | 0.049
2 |  Ours w. $\mathcal{D}ec_{cur}$ att. scores | 0.616 | 0.453 | 0.513 | 0.175 | 0.413 | 0.084 | 0.323 | 0.051
3 | Ours w. Random STM | 0.597 | 0.446 | 0.479 | 0.153 | 0.391 | 0.081 | 0.307 | 0.048
4 | Ours w. Training forgetting | 0.601 | 0.416 | 0.462 | 0.132 | 0.375 | 0.068 | 0.266 | 0.039

###  A.6 Extra Visualization Results

We demonstrate more examples of multi-goal episodes in Figure 10. The agent
efficiently explores the scenes and finds sequential goals using the
informative fraction of the node features in the map. These examples show that
the MemoNav agent focuses high attention only on a small fraction of nodes and
excludes nodes that are far away from the current goal. For example, in the
3-goal example, the agent forgets the topmost node when navigating to the 1st
goal since this node is the farthest from the goal; the agent forgets the
nodes at the bottom left corner when navigating to the 2nd and 3rd goals since
these nodes are remote and uninformative. The comparison with the baseline for
these examples is recorded in the supplementary videos.

We present examples of failed episodes in Figure 10 and record the proportions
of various failure modes at all difficulty levels. The failure modes can
mainly be categorized into four types: _Stopping mistakenly_ , _Missing the
goal_ , _Not close enough_ , and _Over-exploring_. The mode _Stopping
mistakenly_ (34.2%) means that the agent implements `stop` at the wrong place.
The mode _Missing the goal_ (13.5%) means that the agent has observed the goal
but passes it. The mode _Not close enough_ (3.2%) means that the agent
attempts to reach the goal it sees but implements `stop` outside the
successful range. The mode _Over-exploring_ (49.1%) means that the agent
spends too much time exploring open areas without any goals. The largest
probability lies in _Over-exploring_ cases, most of which occur when the agent
explores a large proportion of the scene but still fails to get close to the
target area in a limited time.

Figure 10: (a) Examples of multi-goal navigation episodes. Each example shows
both the topological map and the trajectory. The graph nodes are incrementally
added to the map by the agent and selectively retained by the forgetting
module in the MemoNav. The yellow downward arrow denotes the current localized
node of the agent. (b) Examples of failed episodes. The agent encounters three
major failure mode: _Stopping mistakenly_ , _Missing the goal_ , _Not close
enough_ , and _Over-exploring_.

###  A.7 The Variation of the LTM

To investigate how the feature in the LTM changes during navigation, we
calculate the L2 distance between the features at every two successive time
steps and show the curves for two examples in Figure 11. The two curves show
similar trends: the L2 difference rapidly increases and then gradually
converges to 0 while several peaks appear. To understand why the LTM variation
shows such a trend, we visualize the agent’s observations at the time steps of
the peaks in Figure 11. Comparing these observations, we can see that the
trend of the LTM variation exhibits two traits: (1) the LTM feature remains
stable (the L2 difference is close to 0) if the agent is traveling in visited
areas. For instance, in the 2-goal example (top row), the L2 difference
steadily decreases in $t=31\sim 55$ during which the agent turns around and
travels to visited areas; (2) the LTM feature significantly changes (a peak
appears) if the agent captures novel views of the scene. For instance, in the
3-goal example (bottom row), the L2 difference curve exhibits peaks at $t=68$
when the agent passes a corner and at $t=88$ when the agent observes a novel
open area. These results indicate that the LTM focuses higher attention on the
agent’s novel observations when aggregating the STM and stores the agent’s
exploration experience.

Figure 11: Visualization of the LTM variation. We show the agent’s
trajectories in two example episodes and visualize the agent’s observations at
the time steps when peaks appear on the LTM variation curves. The green arrows
denote when the agent sets a new goal while the orange ones denote when peaks
appear.