# Simulating molecules using the VQE algorithm on Qiskit

Alan Anaya and Francisco Delgado  Tecnologico de Monterrey, School of
Engineering and Sciences, México<EMAIL_ADDRESS>
## Introduction

Feynman’s ideas to employ quantum systems for simulating other quantum systems
[1] gave rise to quantum simulation [2]. While current quantum computers are
still prone to decoherence and rely on error correction [3], the development
of hybrid algorithms that employ both quantum and classical computation allow
to perform quantum simulation [4].

Among these algorithms, the Variational Quantum Eigensolver (VQE) algorithm
has permitted to explore the electronic structure of simple atoms and
molecules by exploiting the Rayleigh–Ritz variational principle [5]. This has
enabled theoretical chemists to gain insight about reaction rates, find
chemically stable structures, determine spectroscopic properties of molecules,
among others.

The VQE employs a parameterized circuit that prepares a quantum state that
aims to approach the ground-state of the molecular Hamiltonian. The
expectation value of this Hamiltonian, calculated by a procedure known as
Hamiltonian averaging [6], provides a cost function to minimize by optimizing
the set of parameters. This optimization procedure is performed using a
classical computer. These steps are performed iteratively until convergence is
found. Among some of the main challenges of VQE is it’s dependence on the
variational form to find the global minimum for the energy expectation value.
Both hardware efficient variational forms [7], that employ a limited set of
gates, and chemically inspired [8] that adapt classical computational
chemistry methods and take into account the chemical details, have been
proposed.

In this supplementary material, we introduce the technical application of VQE
in quantum chemistry by calculating the ground-state single point energy of
the $H_{2}$ molecule. Furthermore, we explore the Energy potential surface
over a range of distances and discuss the effect of the variables on the
accuracy of the results. Together, we provide the implementation of the VQE
algorithm for finding the ground-state energy of the H2 molecule on Qiskit [9]
library for python.

##  1 Dictionary of terms

In this section we define the dictionary of terms to be employed on the python
code. This allows reducing the notation and clarifying the code. The
dictionary of terms include the quantum instance to be used for executing the
quantum circuit, the required mapping for measuring the molecular
Hamiltonian’s expectation value and the classical optimizers to be used for
the parameter minimization.

⬇

1# Simulators

2SV = "statevector"

3QA = "qasm"

4

5# Mappings

6PA = "parity"

7JW = "jordan_wigner"

8BK = "bravyi_kitaev"

9

10#Optimizers

11CO = "COBYLA"

12BF = "L_BFGS_B"

13SL = "SLSQP"

14SP = "SPSA"

15

16# Quantum Instances for running the quantum circuit

17quantum_instances = {

18 SV: QuantumInstance(backend=BasicAer.get_backend(’statevector_simulator’)),

19 QA: QuantumInstance(backend=Aer.get_backend(’qasm_simulator’))}

20

21# Mappings for transforming the molecular Hamiltonian into a set of Pauli
products acting on qubits

22map_types = {

23 PA: "parity",

24 JW: "jordan_wigner",

25 BK: "bravyi_kitaev"}

26

27# Classical Optimizers for parameter minimization

28MAX_ITER = 500

29optimizers = {

30 CO: COBYLA(maxiter=MAX_ITER),

31 BF: L_BFGS_B(maxiter=MAX_ITER),

32 SL: SLSQP(maxiter=MAX_ITER),

33 SP: SPSA(max_trials=MAX_ITER,save_steps=100)}

##  2 Functions

In the current section, we provide a series of functions which will allow to
implement the VQE algorithm. We separated different stages of the
implementation in the following form:

1) A function generating the qubit operators of the molecular Hamiltonian with
the relevant information of the system (number of particles, number of spin
orbitals and energy shift) given as inputs the inter-atomic distance between
hydrogen atoms, the basis set to perform the one and two body integrals and
the map to be implemented. If you desire to get the qubit operator details set
verbose to true. The two qubit reduction (tqr) is set to false and can be used
to reduce the number of qubits by exploiting the symmetries of the Hamiltonian
[10, 11].

⬇

1def get_qubit_op_H2(dist, basis, map_type, verbose=False,tqr=False):

2 driver = PySCFDriver(atom="H .0 .0 .0; H .0 .0 " + str(dist),
unit=UnitsType.ANGSTROM, charge=0, spin=0, basis=basis)

3 molecule = driver.run()

4 #Calculate nuclear repulsion energy

5 repulsion_energy = molecule.nuclear_repulsion_energy

6 num_particles = molecule.num_alpha + molecule.num_beta

7 num_spin_orbitals = molecule.num_orbitals * 2

8 #Calculate one and two body integrals

9 h1=molecule.one_body_integrals

10 h2=molecule.two_body_integrals

11 ferOp = FermionicOperator(h1=h1, h2=h2)

12 #Perform the Mapping from Fermionic operators to Qubit operators

13 qubitOp = ferOp.mapping(map_type=map_type, threshold=0.00000001)

14 shift = repulsion_energy

15 if verbose:

16 print(h1)

17 print(h2)

18 print(qubitOp)

19 print(qubitOp.print_details())

20 if tqr:

21 qubitOp = Z2Symmetries.two_qubit_reduction(qubitOp, num_particles)

22 if verbose:

23 print(qubitOp)

24 print(qubitOp.print_details())

25 return qubitOp, num_particles, num_spin_orbitals, shift

2) A function that constructs an ansatz consisting of a variational circuit
and an initial reference state. This ansatz will be used to prepare a
parameterized quantum state. As inputs, the function requires the outputs
obtained from the previous stage (qubit operators, number of orbitals and
number of particles).

⬇

1def build_ansatz(qubitOp, num_orbitals, num_particles, map_type="parity",
initial_state="HartreeFock", var_form="UCCSD", depth=1,tqr=False):

2 # Specify your initial state

3 initial_states = {

4 ’Zero’: Zero(qubitOp.num_qubits),

5 ’HartreeFock’: HartreeFock(num_orbitals, num_particles, map_type)}

6 # Select a state preparation ansatz

7 # Equivalently, choose a parameterization for the trial wave function.

8 var_forms = {

9 ’UCCSD’: UCCSD(num_orbitals=num_orbitals,
num_particles=num_particles,initial_state=initial_states[initial_state],
qubit_mapping=map_type, reps=depth,two_qubit_reduction=tqr),

10 ’RealAmplitudes’: RealAmplitudes(qubitOp.num_qubits,
reps=depth,initial_state=initial_states[initial_state]),

11 ’EfficientSU2’: EfficientSU2(qubitOp.num_qubits,
reps=depth,initial_state=initial_states[initial_state]),

12 ’TwoLocal’: TwoLocal(qubitOp.num_qubits,[’ry’,’rz’], ’cz’, ’full’,
reps=depth,initial_state=initial_states[initial_state]),

13 ’ExcitationPreserving’:
ExcitationPreserving(qubitOp.num_qubits,mode=’iswap’,
entanglement=’full’,reps=depth,initial_state=initial_states[initial_state])}

14 return var_forms[var_form]

3) A function that calculates the exact eigenvalues of the Hamiltonian
calculated with NumPy. As output, it returns the lowest eigenvalue
corresponding to the ground-state energy.

⬇

1def exact_solver(qubitOp, verbose=False):

2 ee = NumPyEigensolver(qubitOp)

3 result = ee.run()

4 ref = result[’eigenvalues’].real[0]

5 if verbose:

6 print(’Reference value: {}’.format(ref))

7 return ref

Finally, we also provide a function that generates a random set of parameters
to be set as initial points for the variational circuit.

⬇

1def random_initial_point(ansatz, interval=[0,1]):

2 initial_point = []

3 if len(interval)>1:

4 for i in range(ansatz._num_parameters): # For UCCSD

5 initial_point.append(random(interval[0], interval[1]))

6 else:

7 for i in range(ansatz._num_parameters):

8 initial_point.append(random(0, interval[0]))

9 return initial_point

and another function that saves the convergence information about the VQE
execution.

⬇

1def callback(nfev, parameters, energy, stddev):

2 intermediate_info[’nfev’].append(nfev)

3 intermediate_info[’parameters’].append(parameters)

4 intermediate_info[’energy’].append(energy)

5 intermediate_info[’stddev’].append(stddev)

##  3 VQE Implementation on Qiskit for a single point calculation

In this section, we provide the implementation of the VQE for a single point
calculation at the inter-atomic equilibrium distance of 0.74 Å. First we start
by importing the required python libraries.

⬇

1# Import from Qiskit

2from qiskit import BasicAer, Aer, IBMQ

3from qiskit.circuit.library import RealAmplitudes, EfficientSU2, TwoLocal,
ExcitationPreserving

4# Import from Qiskit Aqua

5from qiskit.aqua import QuantumInstance

6from qiskit.aqua.algorithms import VQE, NumPyEigensolver

7from qiskit.aqua.components.initial_states import Zero

8from qiskit.aqua.components.optimizers import COBYLA, L_BFGS_B, SLSQP, SPSA

9from qiskit.aqua.operators import Z2Symmetries

10# Import from Qiskit Chemistry

11from qiskit.chemistry import FermionicOperator

12from qiskit.chemistry.drivers import PySCFDriver, UnitsType

13from qiskit.chemistry.components.variational_forms import UCCSD

14from qiskit.chemistry.components.initial_states import HartreeFock

15

16# Import from other python libraries

17import numpy as np

18import matplotlib.pyplot as plt

19import pylab as py

Then, we define the set of variables required for executing the algorithm. The
basis set chosen for calculating the one and two body integrals was a minimal
basis set of 3 Gaussian orbitals fitted to a Slater Orbital, denoted as
STO-3G. We choose to map the Molecular Hamiltonian to Pauli operators by using
the Parity mapping, this allow us to do a two-qubit reduction process. The
Hartree-Fock state was chosen as initial reference state. The variational form
and the classical optimizer can be changed to wish in order to observe the
difference between methods. For this particular case, we chose to employ the
Unitary Couple Cluster (UCCSD) as our variational form and the Sequential
Least Squares Programming (SLSQP) optimizer. For the calculations, the
variational quantum circuit is executed on a state-vector simulator.

⬇

1# 1. Set the Configuration needed to run VQE on Qiskit

2

3# Interatomic distance.

4dist = 0.74

5# Basis set for calculating the one and two body integrals.

6basis=’sto3g’

7# Mapping type.

8map_type = map_types[PA]

9# Initial reference state to be evolved on the VQE circuit.

10initial_state=’HartreeFock’

11# Variational form to be used.

12var_form=’UCCSD’

13# Quantum simulator

14quantum_instance = quantum_instances[SV]

15# Classical optimizer.

16optimizer=optimizers[SL]

17# Two qubit reduction set to True

18tqr=True

In the next step, we obtain the qubit operators, the number of particles,
number of orbitals and the energy shift from the nuclear repulsion energy.

⬇

1# 2. Get the Hamiltonian in terms of Pauli matrices and the variables to
build the ansatz.

2

3qubitOp, num_particles, num_orbitals, shift = get_qubit_op_H2(dist, basis,
map_type, verbose=False,tqr=tqr)

Then, we construct the variational circuit to be implemented. A random initial
set of points can be given to the VQE circuit. Moreover, callback of the
intermediate information can be done in order to get the convergence of the
parameters and the energy during the simulation.

⬇

1# 3. Bulid the ansatz for the given variational form and initial reference
state.

2ansatz= build_ansatz(qubitOp, num_orbitals, num_particles, map_type=map_type,
initial_state=initial_state, var_form=var_form,tqr=tqr)

3

4# 4. Set an initial random set of parameters for the quantum circuit

5initial_point = np.random.random(ansatz.num_parameters)

6

7

8# 5. Save the intermediate information (number of evaluations, parameters,
energies and standard deviation) of the VQE Algorithm.

9

10intermediate_info = {

11 ’nfev’: [],

12 ’parameters’: [],

13 ’energy’: [],

14 ’stddev’: []

15}

Finally, the VQE algorithm is executed and compared to the exact results. For
setting random initial points to parameters and callback the intermediate
information, write down the last two arguments.

⬇

1# 6. Run VQE on a quantum instance.

2

3vqe = VQE(qubitOp, ansatz,
optimizer,initial_point=initial_point,callback=callback)

4result= vqe.run(quantum_instance)

5

6# 7. Extract the VQE energy calculation.

7

8vqe_result = np.real(vqe.run(quantum_instance)[’eigenvalue’] + shift)

9

10# 8. Compare the VQE energy with the exact result.

11

12ref=exact_solver(qubitOp, verbose=False)

13print("Exact Result:", ref + shift)

14print("VQE Result:", vqe_result)

Results of the the energy convergence and the parameter optimization can be
plotted as a function of the number of iterations. In figure 1, we show an
example of these results for the single point calculation of $H_{2}$ molecule
as described above-. Convergence will vary depending on the initial set of
parameters.

|
---|---

(a)

(b)

Figure 1: (a) Energy convergence of the VQE implemented using the UCCSD
variational form. (b) Parameter optimization of the VQE circuit.

## References

## References

  * [1] Feynman R 1982 Int. J. Theor. Phys. 21 467
  * [2] Lloyd S 1996 Science 273 1073
  * [3] Ladd, T, Jelezko F, Laflamme R et al 2010 Nat. 464 45
  * [4] Jarrod R McClean et al 2016 New J. Phys. 18 023023
  * [5] Peruzzo A, McClean J and Shadbolt P et al 2014 Nat. Commun. 5 4213
  * [6] McClean J et al 2016 New J. Phys 18 023023
  * [7] Kandala A, Mezzacapo A, Temme K et al 2017 Nat. 549 242
  * [8] Romero J et al 2018 Quant. Sci. Technol. 4 014008
  * [9] Gadi Aleksandrowicz et al 2019 Qiskit: An Open-source Framework for Quantum Computing (0.7.2) Zenodo https://doi.org/10.5281/zenodo.2562111
  * [10] Bravyi S, Gambetta J, Mezzacapo A, and Temme K 2017 arXiv: Quantum Phys.
  * [11] McArdle S, Endo S, Aspuru-Guzik A, Benjamin S, Yuan X 2020 Rev. Mod. Phys. 92 15003


# Active Information Gathering for Long-Horizon Navigation Under Uncertainty
by Learning the Value of Information

Raihan Islam Arnob and Gregory J. Stein R. Arnob and G. Stein are with the
Department of Computer Science, George Mason University, USA, {rarnob,
<EMAIL_ADDRESS>
###### Abstract

We address the task of long-horizon navigation in partially mapped
environments for which active gathering of information about faraway unseen
space is essential for good behavior. We present a novel planning strategy
that, at training time, affords tractable computation of the value of
information associated with revealing potentially informative regions of
unseen space, data used to train a graph neural network to predict the
goodness of temporally-extended exploratory actions. Our learning-augmented
model-based planning approach predicts the expected value of information of
revealing unseen space and is capable of using these predictions to actively
seek information and so improve long-horizon navigation. Across two simulated
office-like environments, our planner outperforms competitive learned and non-
learned baseline navigation strategies, achieving improvements of up to 63.76%
and 36.68%, demonstrating its capacity to actively seek performance-critical
information.

##  I Introduction

We focus on the task of point-goal navigation in partially mapped large
building scale environments. In particular, we focus on environments in which
active gathering of information is essential to reach the goal quickly: i.e.,
in minimum expected cost in terms of distance traveled. Consider the example
of a human walking through a building that they have never been in before. The
human looking for a particular location in unseen space is uncertain about how
best to get there, since they do not know the surrounding building layout. If
they are sufficiently uncertain about where to go next, it may be valuable to
seek out a map of the building, often located in the security offices or near
the elevator bays.

We show this information-seeking behavior in the scenario in Fig. 1, where a
robot with a partial map aims to reach a faraway point goal in a large
unmapped office building. An uninformed approach (left) often heads right,
following the hallway in greedy pursuit of the goal; in the absence of
additional information, this strategy encounters many dead-end rooms as it
searches for a passage through to the next hallway needed to reach the unseen
goal. Instead, a more effective strategy in this environment is to go out of
the way to the end of the hallway in search of valuable information: in this
case a map of the environment, found in a _map room_ near the start. Once the
map is found, the robot can use it to quickly reach the goal. This map is
valuable because of the information it provides. Thus, good behavior in
general involves seeking out the map (or other navigation-relevant
information) when the cost-savings that information is expected to provide
outweighs the time the robot expects to spend locating or reaching the source
of information.

It is the aim of this work to imbue a robot with the general purpose ability
to estimate the long-horizon value of information associated with revealing
regions of unseen space and to use those estimates to encourage information
seeking behavior when expected to improve performance, affording both high-
performance navigation with a sound and complete planning in large partially-
mapped environments.

Figure 1:  Overview: actively gathering information is essential for good
navigation in a partial map. Baseline approach reaches the goal slowly,
encountering many dead-ends, while our approach (LSP-AIG) actively gathers
useful information that lets it quickly reach the goal.

In general, incentivizing information gathering via classical approaches
requires belief space planning, in which the robot envisions/imagines all
possible observations and its subsequent behavior. But belief based planning
is canonically doubly exponential in time [1] and so reasoning about long-
horizon information gathering is intractable in general. However, considering
the importance of information gathering actions for effective navigation in
large-scale environments, we want to enable that ability in our robot.

Many approaches rely on learning for planning under uncertainty to mitigate
the computational complexity of belief-space planning. Learning-driven
approaches—including many model-free approaches trained via deep reinforcement
learning [2, 3, 4]—have demonstrated the capacity to perform well in
navigational planning under uncertainty and can exhibit information seeking
behavior to complete their objectives. However, in the absence of an explicit
map to keep track of where the robot has yet to explore, many such approaches
are incomplete, lacking guarantees that they will reach the goal [5], and can
perform poorly in large environments.

The recent Learning over Subgoals Planning (LSP) abstraction [6, 7] uses a
learning-augmented model-based strategy that has proven effective for
performant and reliable planning under uncertainty. The approach uses
_frontiers_ , boundaries between free and unseen space, to define temporally-
extended exploratory actions and leverages learning to help determine the
goodness of each. Despite the advantages of the LSP approach, it is not
straightforward to determine how much value revealing a region of unseen space
will provide and thus how the expected value of information provided by an
exploratory action might be estimated during deployment and incorporated into
planning.

We present a novel general purpose approach for long-horizon point-goal
navigation in a partial map that (i) allows us to compute the value of
information for an exploratory action—the improvement to the robots plan if
some part of the environment were revealed—at training time, that (ii) can
estimate and use value of information at planning time to encourage
information seeking behavior when appropriate to improve plan performance, and
(iii) is complete and sound. We show the effectiveness of our approach in
procedural, simulated office-like environments, demonstrating improvements in
average cost of up to 63.76% and 36.68% over non-learned and learned LSP-based
baselines respectively, and reaches the unseen goal in 100% of the trials.

##  II Related Works

Planning under Uncertainty POMDPs [8, 9, 10, 11] have been used to represent
navigation and exploration tasks under uncertainty, yet direct solution of the
model implicit in the POMDP is computationally infeasible. To mitigate this
difficulty, many approaches to planning rely on learning to inform behavior
[5, 12, 13], yet many [12, 14] only plan a few time steps into the future and
so are not well-suited to long-horizon navigation. Some reinforcement learning
approaches that target partially observed environments [15, 16, 17, 18, 19,
20] are also limited to planning in fairly small-scale environments. The
MERLIN agent [2] uses a differentiable neural computer to recall information
over much longer time horizons than is typically possible for end-to-end-
trained model-free deep reinforcement learning systems. The DD-PPO [4]
approach uses over 2.5 billions of images to train an end-to-end learning
agent for indoor navigation under uncertainty. However, such approaches [2,
21, 22] can be difficult to train and lack plan completeness, making them
somewhat brittle in practice.

Information Gathering Most approaches that explicitly aim to encourage
information gathering behavior focus on relatively short-time-horizon
objectives—such as maximizing exploration [23, 24], or helping to improve
progress towards a vision-language navigation objective [25], or to reveal
uncertain object properties—or otherwise seek only to reveal the environment,
maximizing coverage within a time budget [26, 27, 28, 29]. Another approach
from Zhang et al. [30] focuses on very localized uncertainty: i.e., uncertain
object properties and taking actions to reveal those uncertain properties,
trading off between information gathering (about that particular object) and
the cost of doing so. Our proposed work improves long-horizon navigation under
uncertainty by estimating long-horizon value of information for unseen spaces
and actively gathering the information that is expected to improve
performance.

##  III Problem Formulation

Our robot is tasked to find an unseen goal in a partially-mapped environment
in minimum expected cost (distance). The simulated robot is equipped with a
semantically-aware planar laser scanner, which it can use to both localize and
update its partial semantic-occupancy-grid map of its local surroundings,
limited by range and obstacle occlusion. As the robot navigates the partially-
mapped environment, it updates its belief state $b_{t}$ to include newly-
revealed space and its semantic class. Our belief state $b_{t}$ can be
represented as a two-element tuple consisting of the partially observed map
$m_{t}$ and the robot pose $q_{t}$ : $b_{t}=\\{m_{t},q_{t}\\}$. At each time
step $t$, the action $a_{t}$ specifies which of a set of dynamically-feasible
motion primitives the robot executes.

Formally, we represent this problem as a Partially Observable Markov Decision
Process [8, 9] (POMDP). The expected cost $Q$ under this model can be written
via a belief space variant of the Bellman equation [1]:

$\split
Q(b_{t},a_{t})=\sum_{b_{t+1}}P(b_{t+1}|b_{t},a_{t})\Big{[}R(b_{t+1},b_{t},a_{t})\\\
\quad\quad\quad+\min_{a_{t+1}\in\mathcal{A}(b_{t}+1)}Q(b_{t+1},a_{t+1})\Big{]},$
(1)

where $R(b_{t+1},b_{t},a_{t})$ is the cost to reach belief $b_{t+1}$ from
$b_{t}$ via action $a_{t}$ and $P(b_{t+1}|b_{t},a_{t})$ is the transition
probability.

##  IV Motivating Example: Illustrating the Importance of Active Information
Gathering

Figure 2:  Low cost navigation in our J-Intersection environment requires
active gathering of information. When the goal is either on left or right from
the intersection, knowing the information contained at the center of the map
allows us to decide correctly at the intersection. Choosing always left or
right or even choosing one color over another will not reliably succeed.

We present a motivating example where active information gathering is needed
to make good predictions about the environment while trying to reach an unseen
goal. Our _J-Intersection_ environment, as shown in Fig. 2, has either a red
or blue square region inside of it and around the corner occluded from that
square region far away at the intersection that colored region leads to the
goal (bottom). The environment is structured so that the color of the hallway
the robot should follow matches the color at the center.

In this setting, it is impossible to make an informed decision at the
intersection without the information that lies around the corner at the
center. Thus, optimal behavior in this environment requires that the robot go
out of its way and explore downwards to reveal the center of the map,
accumulating a short-term cost of exploration so that it may later benefit
from the knowledge it gains from doing so.

For this motivating example, it is straightforward to determine how much value
revealing the center region of the map provides. More generally, quantifying
the value of revealing a region of unseen space is incredibly difficult; doing
so may require computing how the robot’s behavior would change over the course
of a lengthy deployment for all possible configurations of unseen space,
motivating the need for a novel approach that can tractably quantify or
estimate the value of information.

##  V Approach: Computing, Estimating, and Using Long-Horizon Value of
Information to Navigate

We present an approach to navigation under uncertainty that allows a robot to
actively gather information specifically useful in improving its planning
performance. This section describes (i) the learning-augmented model-based
_Learning over Subgoals_ state and action abstraction of Stein et al. [6] upon
which our approach relies (Sec. V-A), (ii) our additions to this abstraction
to encourage information-seeking behavior (Sec. V-B), and (iii) our novel
methodology for computing this value of information at training time (Sec.
V-C) so that the expected value of revealing unseen space can be estimated
during deployment.

Figure 3: Our robot’s actions correspond to boundaries between free and unseen
space. The robot can leave observed space through either boundary: via subgoal
$s_{1}$ or $s_{2}$. Upon selecting action $a_{2}$, the robot reaches the goal
with probability $P_{S}$ and incurs an expected cost $R_{S}$, or is turned
back (probability $1-P_{S}$), accumulates cost $R_{E}$ and selects another
action.

###  V-A Preliminaries: Long-Horizon Model-based Navigation under Uncertainty
via Learning over Subgoals Planning

Our robot relies on the learning-augmented model-based planning abstraction of
Stein et al. [6] for high-level navigation through partially-revealed
environments. Under this abstraction, high-level _exploratory actions_
correspond to _frontiers_ —boundaries between free and unseen space; each such
action consists of navigating to a _subgoal_ (a point on the frontier) and
then revealing the region of space beyond, often in an effort to reach the
unseen goal.

Consistent with the LSP action abstraction, planning under the LSP model is
done over an abstract belief state: a tuple $b_{t}=\\{m_{t},q_{t}\\}$, where
$m_{t}$ is the current map of the environment, and $q_{t}$ is the robot pose.
Each high-level action $a_{t}\in\mathcal{A}(\\{m_{t},q_{t}\\})$ has a binary
outcome: with probability $P_{S}(a_{t})$, the robot _succeeds_ in reaching the
goal or (with the inverse probability $1-P_{S}(a_{t})$) fails to reach the
goal.

Upon selecting an action $a_{t}$, the robot must first move through known
space to the boundary, accumulating a cost $D(m_{t},q_{t},a_{t})$. If the
robot succeeds in reaching the goal, it accumulates a _success cost_
$R_{S}(a_{t})$, the expected cost for the robot to reach the goal, and no
further navigation is necessary. Otherwise, the robot accumulates an
_exploration cost_ $R_{E}(a_{t})$, the expected cost of revealing the region
beyond the subgoal of interest and needing to turn back. The robot must
subsequently choose another action $a_{t+1}\in
A_{t+1}\equiv\mathcal{A}(\\{m_{t},q(a_{t})\\})\setminus\\{a_{t}\\}$. Fig. 3
shows a schematic overview of the LSP state and action abstraction.

Determining the goodness of an exploratory action requires making predictions
about what lies in unseen space. So as to avoid the computational and
practical challenges of exhaustive belief-space planning, the LSP abstraction
relies on learning to estimate the statistics of unseen space for each
exploratory action—the _subgoal properties_ $P_{S}$, $R_{S}$, and $R_{E}$. We
are interested in utilizing available sparse knowledge in the partial map to
make quick relational inference about the unseen spaces for which the graph
neural network [31] shows promising performance. So, we adopt a similar
strategy as Arnob and Stein [7] where a graph neural network variant with
dynamic attention mechanism GATv2Conv [32] is used to estimate the subgoal
properties. The subgoal property estimator consumes a sparse graphical
representation of the entire map, so that predictions about unseen space are
informed by all of the robot’s knowledge and experience thus far.

Under the LSP planning model, the expected cost of taking an action $a_{t}$
from belief state $b_{t}=\\{m_{t},q_{t}\\}$ is

$\split
Q(&\\{m_{t},q_{t}\\},a_{t}\in\mathcal{A})=D(m_{t},q_{t},a_{t})+P_{S}(a_{t})R_{S}(a_{t})\\\
+(1-P_{S}(a_{t}))\left[R_{E}(a_{t})+\min_{a_{t+1}}Q(\\{m_{t},q(a_{t})\\},a_{t+1})\right]$
(2)

Planning via this abstraction is _reliable by design_ and _complete_ , as the
robot is always traversing known space and making progress towards revealing
unseen space.

It is thus the role of high-level planning via the LSP planning abstraction to
select the exploratory action (and thus space to reveal) that will minimize
expected cost. Once a high-level action is chosen, the robot selects the low-
level primitive action that most makes progress towards that frontier through
known space, updating the map as space is revealed and replanning when
necessary; we use the notation
$\pi^{\text{\tiny{}LSP}}_{\textit{\tiny{}mp}}(m_{t}))$ to mean the policy that
returns the primitive action specified by LSP given the partial map $m_{t}$.

###  V-B Planning: Actively Seeking Valuable Information

Under the LSP abstraction, temporally-extended _exploratory actions_
correspond to revealing a part of unseen space beyond its corresponding
frontier. Under the LSP model, this begets only an exploration _cost_ ,
neglecting the possible benefits associated with revealing this region and the
information it contains. It is a key insight of our approach that the cost
associated with each exploratory action should be offset by the value of the
information revealed during the exploration, $V_{I}(a_{t})$, which represents
how much performance would improve if the planner were provided an updated map
with the target area revealed.

Thus our planning abstraction augments Learning over Subgoals planning Eq.
eq:lsp-planning to incentivize selection of actions that provide information
valuable to improving planning performance:

$\split
Q(&\\{m_{t},q_{t}\\},a_{t}\in\mathcal{A})=D(m_{t},q_{t},a_{t})+P_{S}(a_{t})R_{S}(a_{t})\\\
+(1-P_{S}(a_{t}))\Big{[}R_{E}(a_{t})-V_{I}(a_{t})\\\
+\min_{a_{t+1}}Q(\\{m_{t},q(a_{t})\\},a_{t+1})\Big{]}$ (3)

Our Eq. eq:lsp-aig-planning allows reliable navigation in partially-revealed
environments and affords active information gathering to improve long-horizon
behavior. However, making use of Eq. eq:lsp-aig-planning would require knowing
the expected value of information associated with revealing each region of
unseen space, an onerous task that in general requires significant computation
and access to the underlying distribution over environments. Instead, we will
estimate $V_{I}(a_{t})$ via a learned model, leveraging a data generation
procedure described in the next section.

###  V-C Determining the Value of Information of an Action

The value of information $V_{I}$ associated with exploratory action $a_{t}$ is
the cumulative difference in performance between LSP-driven plans that do and
do not have access to the unseen space that would be revealed via execution of
high-level action $a_{t}$ from the partial map $m_{t}$. To compute this value
at training time, we recognize that the value of information associated with
action $a_{t}$ can be approximately computed as the sum of individual “one
step” values of information $v_{I}$ along a trajectory, where $v_{I}$ is how
much more progress towards the goal the robot could have made in one time step
if the space corresponding to $a_{t}$ been revealed to it.

This _one-step value of information_ $v_{I}$ is defined via the policy
$\pi^{\text{\tiny{}LSP}}_{\textit{\tiny{}mp}}$, which returns the primitive
action that best makes progress towards the high-level action chosen by the
high-level planner, as described in Sec. V-A. The value $v_{I}$ corresponds to
the difference in cost-to-go (progress towards the goal measured via the known
map $m_{\text{\tiny{}known}}$) between the policy given only the partial map
$m_{t}$ and the one in which the space corresponding to $a_{t}$ is revealed,
notated as $m_{t}\cup a_{t}$. Formally, this is written as follows:

$v_{I}(m_{t},a_{t})=Q(m_{\text{\tiny{}known}},\leavevmode\hbox to0pt{\vbox
to0pt{\pgfpicture\makeatletter\hbox{\hskip 0.0pt\lower 0.0pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hbox
to0.0pt{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}\pi^{\text{\tiny{}LSP}}_{\textit{\tiny{}mp}}(m_{t}))-Q(m_{\text{\tiny{}known}},\leavevmode\hbox
to0pt{\vbox to0pt{\pgfpicture\makeatletter\hbox{\hskip 0.0pt\lower 0.0pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hbox
to0.0pt{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}\pi^{\text{\tiny{}LSP}}_{\textit{\tiny{}mp}}(m_{t}\cup
a_{t}))$ (4)

The total value of information $V_{I}$ for action $a_{t}$ is thus the sum of
each one-step contribution $v_{I}$ for the remainder of travel. Training data
is computed by deploying the base LSP policy, which plans via Eq. eq:lsp-
planning, and computing the one step value of information $v_{I}$ for all
steps along the trajectory for each exploratory action that does not lead to
the goal. Fig. 4 shows an example of the total computed $V_{I}$ over time for
an action $a_{t}$ that contains the map room in our parallel hallway
environment.

Figure 4:  Value of information training data example. We show the total value
of information $V_{I}$ (cumulatively summed over the one step value of
information $v_{I}$) for the action that contains the map information. Color
signifies time step in both plots, enabling easy visual correspondence between
the two.

###  V-D Data Generation and Training

To train our graph neural network, we require training data collected via
offline navigation trials from which we can learn to estimate the subgoal
properties ($P_{S}$, $R_{S}$, $R_{E}$, and $V_{I}$) for each subgoal node in
the graph. During an offline training phase, we conduct trials in which the
robot navigates from start to goal and generates labeled data at each time
step. Training data consists of environment graphs $G$—with input features and
labels associated with each subgoal node.

Each graph node is given an observation—a node feature—from which the subgoal
properties ($P_{S}$ , $R_{S}$ , $R_{E}$, and $V_{I}$) in Eq. 2 will be
estimated via the graph neural network. Node features are 7-element vectors:
(i) a 4-element one-hot semantic class (or color) at the location of the node,
(ii) the number of neighbors of that node, (iii) a binary indicator of whether
or not the node is a subgoal, and (iv) a binary indicator of whether the node
is the goal node. We additionally include a single edge feature, associated
with each edge in the graph: the geodesic distance between the nodes it
connects. Owing to the presence of a goal node connected to every other node,
the edge features provides each node its distance to the goal. See [7] for
more details.

To compute the labels for our training data, we use the underlying known map
$m_{\text{\tiny{}known}}$ to determine whether or not a path to the goal
exists through a subgoal. Using this information, we record a label for each
subgoal that corresponds to a sample of the probability of success $P_{S}$ and
from which we can learn to estimate $P_{S}$ using cross-entropy loss. Labels
for the other subgoal properties are computed similarly: labels for the
success cost $R_{S}$ correspond to the travel distance through unknown space
to reach the goal, for when the goal can be reached, and the exploration cost
$R_{E}$ is a heuristic cost corresponding to how long it will take a robot to
realize a region is a dead end, approximated as the round-trip travel time to
reach the farthest reachable point in unseen space beyond the chosen frontier.
We compute the label value of information as described in Sec. V-C This data
and collection process mirrors that of LSP-GNN [7]; readers are referred to
their paper for additional details.

We repeat the data collection process for each step over hundreds of trials
for each training environment. So as to generate more diverse data, we switch
between the known-space planner and an optimistic (non-learned) planner to
guide navigation during data generation. The details of each environment can
be found in Sec. VI.

##  VI Experimental Results

We conduct simulated experiments in our _J-Intersection_ (Sec. IV, Sec. VI-A),
_Parallel Office_ (Sec. VI-C), and _Ring Office_ environments. For each trial,
we evaluate the performance of these planners:

Optimistically assumes the unseen space to be free and plans via grid-based
A${}^{\\!*}$ search.

Plans via Eq. eq:lsp-planning using a graph neural network learning backend
that consumes a sparse graphical representation of the entire (partially-
revealed) map to estimate subgoal properties.

Plans via Eq. eq:lsp-aig-planning, using an additional graph neural network to
estimate the value of information for each exploratory action, and so seeks to
reveal parts of the environment containing knowledge expected to improve
planning performance.

This approach, exclusive to the parallel hallway environment, seeks the map in
the closer end of the top hallway first and then the other before it finds the
map to head to the goal. For each planner, we compute the average navigation
cost across many (at least 100) random maps from each environment.

TABLE I: Avg. Cost over Multiple Trials in all Tested Environments Planners | Naive | LSP-GNN | LSP-AIG | Map-
---|---|---|---|---
Environment | Non-Learned | Learned | Ours | seeker
J-Intersection | $133.59$ | $107.82$ | 93.84 | -
Ring-Office | $542.64$ | $310.57$ | 196.65 | -
Parallel-Hallway | $252.35$ | $253.95$ | 228.11 | $257.99$

###  VI-A J-Intersection Environment

We first demonstrate that our LSP-AIG planner exhibits the information seeking
behavior we expect in our motivating J-Intersection environment, as described
in Sec. IV. We conduct 100 trials for each planner in this environment and
evaluate their performance. We report the average cost for each in Table I.
Across all trials, our LSP-AIG planner _always_ correctly pursues the
innermost part of the map and the information it contains; it subsequently
makes use of to more quickly reach the unseen goal than is possible for either
other planner, neither of which both reveal and make use of the hidden
information. As such our LSP-AIG exhibits improvements of 36.9% and 13.0% over
the non-learned baseline and LSP-GNN learned baseline, respectively.

###  VI-B The Ring Office Environment

Figure 5: Ring Office environment Results: scatter-plots and example trials.
Our LSP-AIG planner outperforms both the non-learned baseline and the LSP-GNN
planners in 100 trials by actively gathering the information required to
efficiently navigate in our Ring Office environment.

Our _Ring-Office_ environment (see Fig. 5) is, at a high-level, similarly
structured to our _J-Intersection_ environment, in that, for both, an out-of-
the-way region of unseen space contains information key to selecting the
proper-color hallway to more quickly reach the goal. The _Ring-Office_
environment is both much larger than the _J-Intersection_ and additionally
contains many dead-end rooms that flank the hallways, making the environment
more challenging for all planning approaches. For all trials, the robot begins
at the center of a three way intersection, from which it can choose to follow
either hallway or to reveal the space that contains key information about
which hallway is best.

We train the simulated robot on data from 200 maps and evaluate it in a
separate set of 100 maps. We show the average performance of each planning
strategy in Table I and include scatterplots of the relative performance of
different planners for each trial in Fig. 5. The robot planning with our LSP-
AIG approach knows to actively gather the information it needs to reduce its
uncertainty about how best to reach the goal, and so achieves a 63.76%
improvement in average cost versus the optimistic Non-Learned baseline
planner, and a 36.68% improvement over the LSP-GNN baseline planner.

We highlight one trial in Fig. 5, in which the robot is tasked to navigate
from the intersection to the goal. From the intersection, the information
about which hallway will lead to the goal is unavailable and the probability
that either hallway leads to the goal is 50% each. The information is kept out
of view from the intersection in the bottom right that our planner LSP-AIG
actively seeks and then makes informed choice in the direction of the goal
(left) from the intersection. The non-learned baseline runs into many dead-end
rooms, optimistically assuming anything it cannot see to be free space. While
the learned baseline LSP-GNN avoids dead-end rooms, it does not actively
gather information and so selects the incorrect hallway.

###  VI-C The Parallel Hallway Environment

Our _Parallel Hallway_ environment (see Fig. 6) consists of parallel hallways
with rooms that border and connect them. Our procedurally-generated maps
contain three room types: (i) _dead-end_ rooms, (ii) _passage_ rooms that
provide connections between neighboring parallel hallways, and (iii) a single
_map_ room that contains a map of the entire environment.

Only one passage room exists between a pair of hallways, and so the robot must
discover this room if it is to travel to a neighboring hallway. Environments
are generated such that the dead-end rooms and the passage rooms are of the
same semantic “color” (red) distinct from that of the map room (blue). The
environment is such that traveling between hallways frequently requires a non-
trivial amount of trial and error: as the passages and dead-ends are
indistinguishable without entering them, the robot must enter many dead-end
rooms before discovering the passage that allows it to make progress towards
the goal, placed far away from the robot’s starting location.

Critically, when the robot enters the map room the entire environment is
revealed as well. While the map room will never contain the goal—and will
routinely involve traveling away from the goal to find it—seeking out the map
room when appropriate is a prime example of active information seeking
behavior; once the map room (and thus the remainder of the environment) is
revealed, the robot can make quick progress towards the goal without the need
to seek out the passages between hallways. As shown in Fig. 1, good behavior
in this environment involves first seeking out the map room, requiring that
the robot understand the value of the information it provides.

Figure 6: Parallel Hallway Results: scatter-plots and example trials. Our
learning-informed LSP-AIG planner outperforms the non-learned baseline and the
learned baseline LSP-GNN planners by actively gathering the map information
required to efficiently navigate in our Parallel Hallway environment.

We train the simulated robot on data from 500 distinct procedurally generated
maps and evaluate it in a separate set of 250 distinct procedurally generated
maps. We show the average performance of each planning strategy in Table I and
include scatterplots of the relative performance of different planners for
each trial in Fig. 6. The robot planning with our LSP-AIG approach achieves a
10.62% improvement in average cost versus the optimistic Non-Learned Baseline
planner, and a 11.33% improvement over the base LSP-GNN planner, owing to our
planner’s ability to recognize the expected value of actively seeking out the
map room early in navigation, going out of its way to improve performance
overall. Critically, though our planner is not told that there exists a map
room nor what it’s purpose is, it discovers during training that revealing
this part of the environment will meaningfully improve planning performance
and so actively gathers the information it provides during deployment. We show
a representative trial in Fig. 6.

Figure 7:  Our LSP-AIG planner only seeks information when expected to be of
sufficient value to improve performance. We show one such trial in our
_Parallel Hallway_ environment where our robot begins in the hallway next to
the goal. The robot decides not to seek the map room, since it knows the
expense would not justify the benefit.

We additionally note that our planner does not learn a policy that _blindly_
seeks the information the map room provides; instead, it seeks the map room
when appropriate to improve its plan: when the value of information is
sufficient to justify the expense of going out of its way to reveal it. To
illustrate this point, we conducted additional trials in which the robot is
deployed in the hallway next to the goal, and so is both closer to the goal
(so that there are fewer dead-end rooms to encounter, reducing the value of
the information) and farther from the map room increasing the cost to reach
it. In Fig. 7, the robot is uncertain and heads in the direction of the map
room, yet quickly realizes the effort is not worth the cost and turns back to
seek the goal.

In summary, our results highlight the effectiveness of our planner, which has
learned the value associated with revealing unseen regions of space, without
any human-provided policy or guidance, and takes action to actively seek out
valuable information when appropriate.

##  VII Conclusion and Future Work

We present a reliable model-based approach to navigation under uncertainty
capable of actively gathering information to improve long-horizon performance.
Our planning approach uses a graph neural network to estimate the value of
information of exploratory actions that reveal regions of unseen space and
uses those estimates to encourage information seeking behavior when
appropriate to improve performance. Our approach includes a process for
efficiently generating the data necessary for training our planner during an
offline training phase. Substantiating our theoretical contributions, we
demonstrate improved performance in simulated large-scale office-like
environments. In future work, we envision passing more complex sensory input
to the robot, allowing it to estimate the goodness of exploratory actions
using inputs from image sensors or semantically-segmented images.

##  VIII Acknowledgement

We would like to thank Jana Kosecka, George Konidaris and Kevin Doherty for
their thoughtful feedback on this work. This material is based upon work
supported by the National Science Foundation under Grant No. 2232733.

## References

  * [1] J. Pineau and S. Thrun, “An integrated approach to hierarchy and abstraction for POMDPs,” Carnegie Mellon University, Tech. Rep. CMU-RI-TR-02-21, 2002.
  * [2] G. Wayne, C. Hung, D. Amos, M. Mirza, A. Ahuja, A. Grabska-Barwinska, J. W. Rae, P. Mirowski, J. Z. Leibo, A. Santoro, M. Gemici, M. Reynolds, T. Harley, J. Abramson, S. Mohamed, D. J. Rezende, D. Saxton, A. Cain, C. Hillier, D. Silver, K. Kavukcuoglu, M. M. Botvinick, D. Hassabis, and T. P. Lillicrap, “Unsupervised predictive memory in a goal-directed agent,” _CoRR_ , vol. abs/1803.10760, 2018.
  * [3] P. Mirowski, M. K. Grimes, M. Malinowski, K. M. Hermann, K. Anderson, D. Teplyashin, K. Simonyan, K. Kavukcuoglu, A. Zisserman, and R. Hadsell, “Learning to navigate in cities without a map,” _CoRR_ , vol. abs/1804.00168, 2018.
  * [4] E. Wijmans, A. Kadian, A. Morcos, S. Lee, I. Essa, D. Parikh, M. Savva, and D. Batra, “Decentralized distributed PPO: Learning near-perfect pointgoal navigators from 2.5 billion frames,” in _ICLR_ , 2020.
  * [5] M. Pfeiffer, M. Schaeuble, J. I. Nieto, R. Siegwart, and C. Cadena, “From perception to decision: A data-driven approach to end-to-end motion planning for autonomous ground robots,” _CoRR_ , vol. abs/1609.07910, 2016\.
  * [6] G. J. Stein, C. Bradley, and N. Roy, “Learning over subgoals for efficient navigation of structured, unknown environments,” in _Proceedings of The 2nd Conference on Robot Learning_ , ser. Proceedings of Machine Learning Research, A. Billard, A. Dragan, J. Peters, and J. Morimoto, Eds., vol. 87. PMLR, 29–31 Oct 2018, pp. 213–222.
  * [7] R. I. Arnob and G. J. Stein, “Improving reliable navigation under uncertainty via predictions informed by non-local information,” in _International Conference on Intelligent Robots and Systems (IROS)_ , 2023, in press.
  * [8] L. P. Kaelbling, M. L. Littman, and A. R. Cassandra, “Planning and acting in partially observable stochastic domains,” _Artif. Intell._ , vol. 101, no. 1–2, p. 99–134, 1998.
  * [9] M. L. Littman, A. R. Cassandra, and L. P. Kaelbling, _Learning Policies for Partially Observable Environments: Scaling Up_. Morgan Kaufmann Publishers Inc., 1997.
  * [10] S. Thrun, W. Burgard, and D. Fox, _Probabilistic Robotics (Intelligent Robotics and Autonomous Agents)_. The MIT Press, 2005.
  * [11] G. Parascandolo, L. Buesing, J. Merel, L. Hasenclever, J. Aslanides, J. B. Hamrick, N. Heess, A. Neitz, and T. Weber, “Divide-and-conquer monte carlo tree search for goal-directed planning,” 2020.
  * [12] C. Richter, J. Ware, and N. Roy, “High-speed autonomous navigation of unknown environments using learned probabilities of collision,” in _ICRA_ , 2014, pp. 6114–6121.
  * [13] S. Ross, N. Melik-Barkhudarov, K. S. Shankar, A. Wendel, D. Dey, J. A. Bagnell, and M. Hebert, “Learning monocular reactive uav control in cluttered natural environments,” in _2013 IEEE international conference on robotics and automation_. IEEE, 2013, pp. 1765–1772.
  * [14] C. A. Richter, “Autonomous navigation in unknown environments using machine learning,” PhD thesis, Massachusetts Institute of Technology, Cambridge, MA, 2017\.
  * [15] Y. Duan, J. Schulman, X. Chen, P. L. Bartlett, I. Sutskever, and P. Abbeel, “RL2: Fast reinforcement learning via slow reinforcement learning,” in _International Conference on Learning Representations_ , 2017.
  * [16] Y. Yang, J. P. Inala, O. Bastani, Y. Pu, A. Solar-Lezama, and M. Rinard, “Program synthesis guided reinforcement learning for partially observed environments,” _Advances in neural information processing systems_ , vol. 34, pp. 29 669–29 683, 2021.
  * [17] S. Gupta, J. Davidson, S. Levine, R. Sukthankar, and J. Malik, “Cognitive mapping and planning for visual navigation,” in _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2017, pp. 2616–2625.
  * [18] J. Zhang, J. T. Springenberg, J. Boedecker, and W. Burgard, “Deep reinforcement learning with successor features for navigation across similar environments,” in _2017 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_. IEEE, 2017, pp. 2371–2378.
  * [19] L. Tai, G. Paolo, and M. Liu, “Virtual-to-real deep reinforcement learning: Continuous control of mobile robots for mapless navigation,” in _2017 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_. IEEE, 2017, pp. 31–36.
  * [20] P. Mirowski, R. Pascanu, F. Viola, H. Soyer, A. J. Ballard, A. Banino, M. Denil, R. Goroshin, L. Sifre, K. Kavukcuoglu, D. Kumaran, and R. Hadsell, “Learning to navigate in complex environments,” _CoRR_ , vol. abs/1611.03673, 2016.
  * [21] J. Kober and J. Peters, _Reinforcement Learning in Robotics: A Survey_. Cham: Springer International Publishing, 2014, pp. 9–67.
  * [22] P. Henderson, R. Islam, P. Bachman, J. Pineau, D. Precup, and D. Meger, “Deep reinforcement learning that matters,” in _Proceedings of the AAAI conference on artificial intelligence_ , vol. 32, no. 1, 2018.
  * [23] M. Lodel, B. Brito, Álvaro Serra-Gómez, L. Ferranti, R. Babuška, and J. Alonso-Mora, “Where to look next: Learning viewpoint recommendations for informative trajectory planning,” 2022.
  * [24] J. Velez, G. Hemann, A. Huang, I. Posner, and N. Roy, “Planning to perceive: Exploiting mobility for robust object detection,” _Proceedings of the International Conference on Automated Planning and Scheduling_ , vol. 21, no. 1, pp. 266–273, Mar. 2011.
  * [25] H. Wang, W. Wang, T. Shu, W. Liang, and J. Shen, “Active visual information gathering for vision-language navigation,” in _Computer Vision–ECCV 2020: 16th European Conference, Glasgow, UK, August 23–28, 2020, Proceedings, Part XXII 16_. Springer, 2020, pp. 307–322.
  * [26] S. Choudhury, A. Kapoor, G. Ranade, and D. Dey, “Learning to gather information via imitation,” in _2017 IEEE International Conference on Robotics and Automation (ICRA)_. IEEE, 2017, pp. 908–915.
  * [27] B. Schlotfeldt, D. Thakur, N. Atanasov, V. Kumar, and G. J. Pappas, “Anytime planning for decentralized multirobot active information gathering,” _IEEE Robotics and Automation Letters_ , vol. 3, no. 2, pp. 1025–1032, 2018\.
  * [28] Y. Li, A. Debnath, G. J. Stein, and J. Kosecka, “Learning-augmented model-based planning for visual exploration,” in _International Conference on Intelligent Robots and Systems (IROS)_ , 2023, in press.
  * [29] S. K. Ramakrishnan, D. Jayaraman, and K. Grauman, “An exploration of embodied visual exploration,” _International Journal of Computer Vision_ , vol. 129, pp. 1616–1649, 2021.
  * [30] X. Zhang, S. Amiri, J. Sinapov, J. Thomason, P. Stone, and S. Zhang, “Multimodal embodied attribute learning by robots for object-centric action policies,” _Auton. Robots_ , vol. 47, no. 5, p. 505–528, mar 2023.
  * [31] P. W. Battaglia, J. B. Hamrick, V. Bapst, A. Sanchez-Gonzalez, V. F. Zambaldi, M. Malinowski, A. Tacchetti, D. Raposo, A. Santoro, R. Faulkner, Ç. Gülçehre, H. F. Song, A. J. Ballard, J. Gilmer, G. E. Dahl, A. Vaswani, K. R. Allen, C. Nash, V. Langston, C. Dyer, N. Heess, D. Wierstra, P. Kohli, M. M. Botvinick, O. Vinyals, Y. Li, and R. Pascanu, “Relational inductive biases, deep learning, and graph networks,” _CoRR_ , vol. abs/1806.01261, 2018.
  * [32] S. Brody, U. Alon, and E. Yahav, “How attentive are graph attention networks?” in _International Conference on Learning Representations_ , 2021\.


# MGBPv2: Scaling Up Multi-Grid Back-Projection Networks

Pablo Navarrete Michelini, Wenbin Chen, Hanwen Liu, Dan Zhu
BOE Technology Co., Ltd.
{pnavarre, chenwb, liuhanwen<EMAIL_ADDRESS>
###### Abstract

Here, we describe our solution111Code available at
https://github.com/pnavarre/mgbpv2 for the AIM–2019 Extreme Super–Resolution
Challenge, where we won the $\boldsymbol{1^{st}}$ place in terms of perceptual
quality (MOS) similar to the ground truth and achieved the $5^{th}$ place in
terms of high–fidelity (PSNR). To tackle this challenge, we introduce the
second generation of MultiGrid BackProjection networks (MGBPv2) whose major
modifications make the system scalable and more general than its predecessor.
It combines the scalability of the multigrid algorithm and the performance of
iterative backprojections. In its original form, MGBP is limited to a small
number of parameters due to a strongly recursive structure. In MGBPv2, we make
full use of the multigrid recursion from the beginning of the network; we
allow different parameters in every module of the network; we simplify the
main modules; and finally, we allow adjustments of the number of network
features based on the scale of operation. For inference tasks, we introduce an
overlapping patch approach to further allow processing of very large images
(e.g. 8K). Our training strategies make use of a multiscale loss, combining
distortion and/or perception losses on the output as well as downscaled output
images. The final system can balance between high quality and high
performance.

Figure 1:  Large upscaling factors are needed to convert standard–definition
(SD) to ultra–high–definition (UHD) resolutions. In the task of Extreme
Super–Resolution (zooming $16\times$), our proposed MGBPv2 system can achieve
a good balance between high fidelity (images close to the original content)
and high perceptual quality (images that look real through artificial
details).

##  1 Introduction

Image upscaling has been studied for decades and remains an active topic of
research because of constant technological advances in digital imaging. One
scenario where image upscaling is now more demanding arises in digital display
technologies, where new standards like BT.2020 [18] are introduced. The
resolution of digital displays has experienced a tremendous growth over the
past few decades, as shown in Figure 2. The transition between different
formats leads to a challenging problem. On one hand, large amount of digital
content still exist in popular old standards such as standard–definition (SD).
On the other hand, the latest display technologies (e.g. 4K, 8K and above) are
expected to show this content with reasonable quality. Standard upscaling
technologies are clearly insufficient for this purpose. While a $2\times$
upscaler maps $1$ input pixel into $4$ output pixels, a $16\times$ upscaler
maps $1$ input pixel into $256$ output pixels, which already contain small
images. The problem demands advanced solutions that are capable of
understanding the image content and filling in these large pieces of images
with visually appealing and consistent information. In particular, large
upscaling factors are needed to convert SD to ultra high–definition (UHD)
resolutions. For example, to upscale from a popular width of $640$ pixels
(VGA) to $8,192$ (8K) we need a factor greater than $12\times$. And from $640$
pixels to $10,240$ (10K), which is used by some of the most advanced modern
displays [4, 3], we need a $16\times$ factor. Thus, extreme upscaling
represents a real problem in current market and it is expected to persist and
become even more challenging with the rapid development of new technologies.

Figure 2: Extreme Super–Resolution is a technology necessary to connect the
extremes in the dramatic growth of standard resolutions. Source: Wikimedia CC
BY-SA.

The challenge on Extreme Super–Resolution proposed at the 2019 ICCV workshop
on Advances in Image Manipulation (AIM–2019) [17] was the first of its kind to
tackle this problem. That is, the task of increasing the resolution of an
input image with a magnification factor $16\times$ based on a set of prior
examples of low and corresponding high resolution images. The challenge
provided a novel DIVerse up to 8K resolution images dataset (DIV8K) with a
large diversity of content. Two targets were proposed:

  * •

Track 1: Fidelity, the aim is to obtain a solution capable to produce high
resolution results with the best fidelity (PSNR) to the ground truth.

  * •

Track 2: Perceptual, the aim is to obtain a solution capable to produce high
resolution results with the best perceptual quality similar to the ground
truth.

These two targets are motivated by the so–called _perception–distortion_
trade–off established by Blau and Michaeli in [2]. That is, both targets
cannot be achieved at the same time, one must compromise perceptual quality to
improve fidelity and vice versa. The trade–off motivated the Perceptual Image
Restoration and Manipulation (PIRM) workshop at ECCV–2018 [1] that strongly
confirmed and gave further insight into this fundamental principle.

In the Extreme–SR competitions, we identified two major challenges:
performance scalability, due to the large size of the output images; and
content scalability, due to the diverse scale of image content. Our solution
was built upon the MultiGrid BackProjection (MGBP) network proposed in [16,
15], combining both the iterative backprojection and multigrid algorithms.
First, the iterative backprojection algorithm provides performance. With solid
ground in the classical theory of image super–resolution (SR), its
deep–learning versions have succeeded in competitions. Examples include DBPN
[5] (which won the NTIRE–2018 challenge on $8\times$ SR and the Region–2 track
of PIRM–SR 2018[1]) and MGBP [15] (which won the $2^{nd}$ place in the
Region–3 track, i.e. best perception, of PIRM–SR 2018[1]). Second, the
multigrid algorithm provides scalability. Here, it is worth noting that
_multigrid_ is one of the most popular algorithms in the field of PDE and
numerical solvers[19], but its name is often misinterpreted in other fields as
merely meaning “multilevel”. Multigrid is one of the few known methods that
can solve numerical systems of linear equations with optimal computational
complexity (linear in the number of unknowns). The MGBP algorithm does not
work as a linear solver, but borrows the multigrid recursion to scale the
iterative backprojection algorithm. The recursion unfolds into a convenient
structure, in which the computational complexity grows linearly with the image
size. This is visible in the diagram of the system (see for example Figure 3),
where the number of modules is maximum at the lowest resolution and decreases
exponentially as the resolution increases.

Despite its convenient properties, the original formulation of MGBP does not
scale well for extreme upscaling factors. This is due to two problems: first,
the small number of parameters in MGBP limits its performance on image quality
compared to large models; second, the recursive structure forces the number of
network features to remain constant along scales. Our main contribution is to
redesign MGBP to fix these problems. We summarize our contributions as
follows:

  * •

We propose to make full use of the multigrid recursion from the beginning of
the network.

  * •

We propose to simplify the main modules and allow different parameters for
every instance in the network.

  * •

We propose a strategy to merge overlapping patches in inference to further
allow processing of very large images.

  * •

We propose training strategies at multiple scales, combining distortion and/or
perception losses on the output as well as downscaled output images.

##  2 System Architecture

Figure 3: Diagram of the MultiGrid BackProjection version 2 (MGBPv2) network unfolded from Algorithm 1 with $\mu=2$.  Algorithm 1 Multi–Grid Back–Projection version 2 (MGBPv2) MGBPv2$(X,W,\mu,L)$: |  $\boldsymbol{BP^{\mu}_{k}}(u\;|\;y_{1},\ldots,y_{k-1};\text{tag}_{1},\ldots,\text{tag}_{k-1})$:
---|---
0: Input image $X$.  0: Steps $\mu$, levels $L$ and noise amplitude $W$.  0: Output image $Y$.  1: $x=[X,\;W\cdot\mathcal{N}(0,1)]$ 2: for $k=1,\ldots,L$ do 3: $y_{k}=\text{Analysis}_{k}(x)$ 4: end for 5: for $k=1,\ldots,L$ do 6: $\text{tag}_{k}=0$ 7: end for 8: $y=BP^{\mu}_{L}(y_{L}\;|\;y_{1},\ldots,y_{L-1};\text{tag}_{1},\ldots,\text{tag}_{L-1})$ 9: $Y=\text{Synthesis}(y)$ |  0: Input image $u$, level index $k$, steps $\mu$.  0: Images $y_{1},\ldots,y_{k-1}$ and $\text{tag}_{1},\ldots,\text{tag}_{k-1}$ (for $k>1$).  0: Image $out$ 1: $out=u$ 2: if $k>1$ then 3: for $s=1,\ldots,\mu$ do 4: $\text{tag}_{k-1}=s$ 5: $LR=\text{Downscale}_{tag}(out)$ 6: $c=BP^{\mu}_{k-1}(LR\;|\;y_{1},\ldots,y_{k-2};\text{tag}_{1},\ldots,\text{tag}_{k-2})$ 7: $out=out+\text{Upscale}_{tag}([\;y_{k-1},c\;])$ 8: end for 9: end if
Figure 4: Discriminator system used for adversarial training. The high
resolution input image is downsized with standard bicubic downscalers to enter
the system at different scales. CNN modules do not share parameters.

Without loss of generality, we tackle the image enhancement problem with an
input resolution equal to the output resolution. For the super–resolution task
we input the low resolution image upscaled $16\times$ using a bicubic method.
This helps to make the system become more general for applications and
simplifies the process of generating pairs of input/output patches during
training.

We propose the MGBPv2 algorithm shown in Algorithm 1. In Figure 3 we display
the diagram of the algorithm unfolded for $\mu=2$ and $L=5$. The _Analysis_
and _Synthesis_ modules covert an image into features space and vice–versa
using single convolutional layers. The _Upscaler_ and _Downscaler_ modules are
composed of single strided (transposed and conventional) convolutional layers.
An important observation in Algorithm 1 that makes a significant difference
with the original MGBP is the use of a tag label to differentiate each
_Upscaler_ and _Downscaler_ module. This simple trick makes every _Upscaler_
and _Downscaler_ module different in terms of parameters and hyper–parameters.
In particular, we now set the number of features in convolutional layers to
$256$, $192$, $128$, $92$, $48$ and $9$ from low to high resolution levels,
allowing large images to be processed at high resolutions. The system can be
initialized by a _dry run_ of Algorithm 1 where no computation is performed
and modules are defined with their correspondent tag labels.

For the Perceptual track we used a single MGBPv2 system configured with
filters of $3\times 3$. For the Fidelity track we used an ensemble solution
that sums the outputs of $3$ systems with identical configuration except for
different filter sizes: $3\times 3$, $5\times 5$ and $7\times 7$.

We concatenate a single noise channel, $W\cdot\mathcal{N}(0,1)$, to the
bicubic upscaled input. The amplitude of the noise, $W\in\mathbb{R}$, is set
to zero in the Fidelity track and its purpose is to help in the adversarial
training for the Perceptual track. Following the design of the generative MGBP
algorithm in [15], the noise activates and deactivates the generation of
artificial details. As opposed to [15] we now generate a single noise channel
at the highest resolution, that moves along with the input image to enter the
network at different scales by using _Analysis_ modules with different
strides. In [15], different i.i.d. noise channels are generated at each
resolution. This change becomes necessary during inference, where we merge the
output of several overlapping patches and therefore we need to use noise
images that overlap in the same way as the input image.

For the discriminator in adversarial training we use the system shown in
Figure 4. Here, we use $4$–layer sequential CNNs with $3\times 3$ filters and
stride $1$ except for the last layer that uses stride $2$ to downscale the
features. The system resembles the design of the discriminator in [15] with
two major differences: first, the system in Figure 4 is not recursive (all
CNNs have different parameters); and second, the system uses a single
high–resolution input that is downsized using fixed bicubic downscalers to
enter at different levels of the system. We use the same _variance
normalization and shift correlator_ (VN+SC) module from [15].

##  3 Training Strategies

We denote $Y_{W=0}$ and $Y_{W=1}$ the outputs of the generator architecture
using noise amplitudes $W=0$ and $W=1$, respectively. Let $S_{f}$ represent a
bicubic downscaler that reduces the resolution by a factor $f$. We know that
the original image was downscaled with $S_{16}$. Then, our training strategies
in terms of loss functions are defined follows:

Fidelity Track: We use $\mathcal{L}^{L1}(x,y)=\mathbb{E}\left[|x-y|\right]$ at
several resolutions to define the total loss function:

$\displaystyle\mathcal{L}(Y,X;\theta)=\;$
$\displaystyle\mathcal{L}^{L1}(Y_{W=0},X)\;+$
$\displaystyle\mathcal{L}^{L1}(S_{2}(Y_{W=0}),S_{2}(X))\;+$
$\displaystyle\mathcal{L}^{L1}(S_{4}(Y_{W=0}),S_{4}(X))\;+$
$\displaystyle\mathcal{L}^{L1}(S_{8}(Y_{W=0}),S_{8}(X))\;+$
$\displaystyle\mathcal{L}^{L1}(S_{16}(Y_{W=0}),S_{16}(X))\;.$ (1)

After every epoch we evaluate the current model using
$\mathcal{L}^{L2}(x,y)=\mathbb{E}\left[(x-y)^{2}\right]$ in the validation
metric:

$\displaystyle\mathcal{V}(Y;\theta)=\mathcal{L}^{L2}(Y_{W=0},X)\;.$ (2)

We recorded the best models according to this metric (directly related to
PSNR) during the training process and we performed further manual tests on
larger images afterwards.

Figure 5: Example outputs and performance metrics for images in the DIV8K
training set that were used only for validation.

Perceptual Track: We follow the design of multi–scale loss from the generative
MGBP in [15] with some simplifications to improve training performance. One
significant change is in the adversarial loss. We changed the standard GAN
used in [15] to a Relativistic GAN [7] following the recommendation in [20].
Our total loss is given by:

$\displaystyle\mathcal{L}(Y,X;\theta)=\;$ $\displaystyle
0.001\cdot\mathcal{L}^{RSGAN}_{G}(Y_{W=1})\;+$ $\displaystyle
10\cdot\mathcal{L}^{L1}(S_{16}(Y_{W=1}),S_{16}(X))\;+$ $\displaystyle
0.1\cdot\mathcal{L}^{CX}(Y_{W=1},X)\;+$ $\displaystyle
10\cdot\mathcal{L}^{L1}(Y_{W=0},X)\;+$ $\displaystyle
10\cdot\mathcal{L}^{L1}(S_{16}(Y_{W=0}),S_{16}(X))\;.$ (3)

Here, $\mathcal{L}^{CX}$ is the _contextual loss_ as defined in [12] using
features from _conv3–4_ of a VGG–19 network as suggested in [11]. Ablation
tests in [15] have shown the effectiveness of this loss function to improve
perceptual quality while maintaining a reasonable level of distortion. Next,
the Relativistic GAN loss follows the definition in [7], given by:

$\displaystyle\mathcal{L}_{D}^{RSGAN}=$
$\displaystyle-\mathbb{E}_{(R,F)}\left[\log(\text{sigmoid}(C(R)-C(F)))\right]\;,$
$\displaystyle\mathcal{L}_{G}^{RSGAN}=$
$\displaystyle-\mathbb{E}_{(R,F)}\left[\log(\text{sigmoid}(C(F)-C(R)))\right]\;.$
(4)

Here, $C$ is the output of the discriminator before the sigmoid function, as
shown in Figure 4. And $R$ and $F$ are the sets of real and fake inputs to the
discriminator, given by:

$\displaystyle F=$
$\displaystyle\left\\{Y_{W=1},S_{2}(Y_{W=1}),S_{4}(Y_{W=1}),S_{8}(Y_{W=1})\right\\}\;,$
$\displaystyle R=$
$\displaystyle\left\\{X,S_{2}(X),S_{4}(X),S_{8}(X)\right\\}\;.$ (5)

After every epoch we evaluated the current model according to the validation
metric based on the NIQE[13] index:

$\displaystyle\mathcal{V}(Y;\theta)=\mathbb{E}\Big{[}$ $\displaystyle
NIQE(Y_{W=1})+NIQE(S_{2}(Y_{W=1}))\;+$ $\displaystyle
NIQE(S_{4}(Y_{W=1}))\Big{]}\;.$ (6)

This metric works as a simple rule to help identify models that generate
realistic images in the full resolution, as well as two levels of resolutions
below. In other words, we want output images to look real as seen in a display
device both from close and far away distances. We performed further subjective
tests on larger images to select the best models.

##  4 Inference Strategies

To upscale large images we propose a patch based approach in which we average
the output of overlapping patches taken from the bicubic upscaled input.
First, we divide input images into overlapping patches (of same size as
training patches) as shown in Figure 6; second, we multiply each output by a
weight decreasing as the distance to the center of a patch increases (we
recommend a Hamming window [6]); and third, we average the results. In our
experiments we used overlapping patches separated by $64$ and $128$ pixels in
vertical and horizontal directions for the Perceptual and Fidelity tracks,
respectively. The weighted average helps to avoid blocking artifacts.

Figure 6: We average overlapping output patches to allow processing
arbitrarily large images during inference.

Another problem arise in the training process because reading several 8K
images to form a minibatch becomes much slower than running the training step
on the minibatch. A popular solution is to save image arrays in a binary
format that is much faster to decode (e.g. EDSR [8]). This solution is not
practical here since the amount of space required for the whole dataset
exceeds reasonable storage resources. We propose a solution by pre–processing
the dataset, creating folders for every image in the training set and saving
overlapping patches as image files inside each folder, as shown in Figure 7.
During training we: first, select images randomly; second, enter the directory
and randomly select an image file; third, open the image file and randomly
select a patch inside (having similar sizes).

Figure 7: To improve the reading speed in the training process, we replaced
images by folders with pre–selected image patches of similar but larger size
than training patches.

##  5 Experiments

Settings: We run training tasks on Tesla V100 GPUs and testing on Titan X
GPUs. We used $100$ images from the training set for validation during
training. We trained using patch size $667\times 667$ (Fidelity Track) and
$767\times 767$ (Perceptual Track) at high resolution. We trained our systems
using a Quasi-hyperbolic Adam optimizer [10] with constant learning rate
$10^{-4}$, and changed to Lookahead [21] combined with RAdam [9] in later
stages of development. We set the minibatch size to $16$ patches. After every
epoch we run the validation metrics described above on the center patch of our
$100$ validation images.

Performance: We report a running time of $47.11$ [s] to process a standard 8K
image ($7689\times 4320$) on a Titan X (Maxwell) GPU, without using the
overlapping patch approach. It takes $1.42[s]$ in average to process
$1000\times 1000$ images used in the validation stage. For our submissions we
use the system in the slowest mode, which uses overlapping patches with small
distances between the center of the patches ($64$ or $128$ pixels). By using
this approach it takes $4.16[s]$ to process a $1000\times 1000$ image using
$667\times 667$ overlapping patches with centers separated by $128$ pixels
(used in the Fidelity track). It takes $2.06[s]$ to process a $1000\times
1000$ image using $767\times 767$ overlapping patches with centers separated
by $64$ pixels (used in the Perceptual track). Overall, in both the Fidelity
and Perceptual tracks, it takes approximately $16$ minutes to generate one 8K
output image using the slowest mode. The overlapping patch approach gives
marginal improvements in PSNR and also allows the network to run on devices
with low memory resources. The settings used for the competition are purposely
not practical for applications as they focus exclusively on image quality.
Nevertheless, our empirical tests show that by using larger distances between
overlapping patches and multiple GPU devices we can output an 8K image in less
than $10$ seconds without significant loss in quality.

Figure 8: Deep filter visualization (DFV)[16, 14] experiments on our model for
the Fidelity track using a patch of size $767\times 767$. The model shows good
knowledge of the geometry and large receptive fields.  Figure 9: Example
outputs and performance metrics for images in the DIV8K training set that were
used only for validation.  Figure 10: Evolution of perceptual and fidelity
metrics when moving the input noise amplitude from $W=0$ to $W=1$.

Challenge Results: The Fidelity track of the Extreme-SR AIM 2019 challenge had
$70$ participants, with $9$ finalists submitting results for the test stage.
Our results obtained the $\boldsymbol{5^{th}}$ place, with an average PSNR of
$26.59$ dB in the full output images of the test set. This is, $0.2$ dB below
the top score winning this track.

The Perceptual track of the Extreme–SR AIM 2019 challenge had $52$
participants, with $6$ finalists submitting results for the test stage. Our
results obtained the $\boldsymbol{1^{st}}$ place in terms of a subjective
ranking based on mean opinion scores (MOS) to measure perceptual quality. Our
results obtained an average PSNR of $25.44$ dB in the full output images of
the test set. This is, $0.18$ dB above the $2^{nd}$ place and $1.35$ dB below
the best PSNR value in the Fidelity track.

Figures 5 and 9 show examples of our best results for the Fidelity and
Perceptual tracks on images used for validation during our training process.
These images show the values of RMSE (measuring fidelity) as well as the
Perceptual index proposed in [1] to objectively measure perceptual quality.
Overall, the results are consistent with the perception/distortion trade–off
in [2]. For the images 142 and 622 we observe that our results for the
Perceptual track achieve a Perceptual index better than original images. In
image 622 we attribute this result to a blurred background in the original
image, that our system shows more focused and with sharper features. In image
622 the results seem to reflect a failure of the Perceptual index as the
original image clearly displays a face that our output shows with ambiguous
characteristics. This shows that our system does not go as far as to fake
people’s identities, but it seems to correctly identify a person by adding
skin and body textures. For images 472, 808 and 1466, the Perceptual indexes
are clearly below those of the original image. According to our subjective
evaluation, we observe clear differences in the fine level features like: tree
leaves and water for image 472; hair, eyebrows and eyelashes in 808; and
textbook spines in 1466. From a far away look these details become less
perceptible, indicating that the Perceptual index correlates better with a
close distance observer. This is probably caused by the resolution of example
images used to adjust the Perceptual index, that are much smaller than 8K.

Figure 10 shows the effect of continuously adding noise in the input of our
model for the Perceptual track. We observe that our model has correctly
interpreted the target of our loss function, aiming at high fidelity with zero
noise amplitude and high perceptual quality for unit noise amplitude. The
trajectory in the perception distortion plot is mostly concave, except for the
high perception corner. This trajectory is not meant to be optimal as
perception/distortion optimality is far from being represented in the loss
function. Our loss function only considers the corner cases of zero and unit
noise amplitudes. The transition from high fidelity to high perceptual quality
is smoother than similar tests performed with MGBP in [15]. The plot for the
contextual similarity, as defined in [12], shows the best result in the
beginning of the strong transition from high fidelity to high perceptual
quality. Before this point it behaves as the perceptual index (improving as
noise increases) and after this point it changes to a behavior closer to a
fidelity score (worsening as noise increases). Compared to similar experiments
performed in [15], the contextual loss here seems to be more focused on
preventing low fidelity scores.

Finally, Figure 8 shows interpretability results obtained by using the Deep
Filter Visualization (DFV) method from [16]. To perform this complex analysis
on a large model such as MGBPv2, with more than $20$ million parameters, we
use the so–called _Linearscope_ method recently introduced in [14]. For a
given pixel in the input image (blue circles on the left side), Figure 8
displays the impulse response for the network model with frozen activations
(all ReLU’s acting as if the input image did not change). This represents the
equivalent to an upscaling filter that adapts to the pixel location. In flat
areas (example at the bottom of Figure 8) the upscaling filter looks isotropic
and similar to a bicubic upscaler. In other locations, the filter strongly
follows edges in hair and fingers, with receptive fields that extend for
several hundred pixels. Overall, this confirms that the system has learned the
geometry of the content.

##  6 Conclusions

The second generation of Multi–Grid Back–Projection (MGBPv2) networks improves
its predecessor by: making better use of the multigrid recursion; simplifying
its modules; and redesigning training and inference strategies to improve
scalability. MGBPv2 achieves state–of–the–art performance by winning the
Perceptual track of the ICCV AIM Extreme-SR Challenge 2019.

## References

  * [1] Yochai Blau, Roey Mechrez, Radu Timofte, Tomer Michaeli, and Lihi Zelnik-Manor.  2018 PIRM challenge on perceptual image super-resolution, 2018.
  * [2] Yochai Blau and Tomer Michaeli.  The perception-distortion tradeoff.  In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2018.
  * [3] Ran Duan and Pablo Navarrete Michelini.  P-47: 10K Ultra–High–Definition display system.  In SID Symposium Digest of Technical Papers, volume 47, pages 1294–1296. Wiley Online Library, 2016.
  * [4] The Society for Information Display (SID).  2015 award winners: BOE technology group for its 82-in. 10K display.  https://www.sid.org/About/Awards/PeoplesChoiceAwards.aspx, 2015\.  [Online; accessed 18-Sept-2019].
  * [5] Muhammad Haris, Greg Shakhnarovich, and Norimichi Ukita.  Deep back–projection networks for super–resolution.  In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2018.
  * [6] Fredric J Harris.  On the use of windows for harmonic analysis with the discrete fourier transform.  Proceedings of the IEEE, 66(1):51–83, 1978.
  * [7] Alexia Jolicoeur-Martineau.  The relativistic discriminator: a key element missing from standard GAN.  arXiv preprint arXiv:1807.00734, 2018.
  * [8] Bee Lim, Sanghyun Son, Heewon Kim, Seungjun Nah, and Kyoung Mu Lee.  Enhanced deep residual networks for single image super–resolution.  In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR) Workshops, July 2017.
  * [9] Liyuan Liu, Haoming Jiang, Pengcheng He, Weizhu Chen, Xiaodong Liu, Jianfeng Gao, and Jiawei Han.  On the variance of the adaptive learning rate and beyond.  arXiv preprint arXiv:1908.03265, 2019.
  * [10] Jerry Ma and Denis Yarats.  Quasi-hyperbolic momentum and adam for deep learning.  arXiv preprint arXiv:1810.06801, 2018.
  * [11] Roey Mechrez, Itamar Talmi, Firas Shama, and Lihi Zelnik-Manor.  Learning to maintain natural image statistics, [arxiv](https://arxiv.org/abs/1803.04626).  arXiv preprint arXiv:1803.04626, 2018.
  * [12] Roey Mechrez, Itamar Talmi, and Lihi Zelnik-Manor.  The contextual loss for image transformation with non-aligned data.  arXiv preprint arXiv:1803.02077, 2018.
  * [13] A. Mittal, R. Soundararajan, and A. C. Bovik.  Making a “Completely Blind” Image Quality Analyzer.  IEEE Signal Processing Letters, 20:209–212, Mar. 2013.
  * [14] Pablo Navarrete Michelini, Hanwen Liu, Yunhua Lu, and Xingqun Jiang.  A tour of convolutional networks guided by linear interpreters.  In The IEEE International Conference on Computer Vision (ICCV). IEEE, Oct 2019.
  * [15] Pablo Navarrete Michelini, Hanwen Liu, and Dan Zhu.  Multi–scale recursive and perception–distortion controllable image super–resolution.  In The European Conference on Computer Vision Workshops (ECCVW), September 2018.
  * [16] Pablo Navarrete Michelini, Hanwen Liu, and Dan Zhu.  Multigrid backprojection super–resolution and deep filter visualization.  In Proceedings of the Thirty–Third AAAI Conference on Artificial Intelligence (AAAI 2019). AAAI, 2019.
  * [17] Gu Shuhang, Martin Danelljan, Radu Timofte, et al.  AIM 2019 challenge on image extreme super–resolution: Methods and results.  In The IEEE International Conference on Computer Vision (ICCV) Workshops, October 2019.
  * [18] M. Sugawara, Choi S-Y, and D. Wood.  Ultra–high–definition television (Rec. ITU-R BT.2020): A generational leap in the evolution of television.  Signal Processing Magazine, IEEE, 31(3):170–174, May 2014.
  * [19] Ulrich Trottenberg, Cornelius W Oosterlee, and Anton Schuller.  Multigrid.  Academic Press, Inc., Orlando, FL, USA, 2001.
  * [20] Xintao Wang, Ke Yu, Shixiang Wu, Jinjin Gu, Yihao Liu, Chao Dong, Yu Qiao, and Chen Change Loy.  ESRGAN: Enhanced super-resolution generative adversarial networks.  In Proceedings of the European Conference on Computer Vision (ECCV), pages 0–0, 2018.
  * [21] Michael R Zhang, James Lucas, Geoffrey Hinton, and Jimmy Ba.  Lookahead optimizer: k steps forward, 1 step back.  arXiv preprint arXiv:1907.08610, 2019.