The Effectiveness of Edge Detection Evaluation Metrics for Automated Coastline Detection

F. M. Lastname

F. M. Lastname

Conor O'Sullivan$^{1,2}$ $^{\dagger}$,
Seamus Coveney$^{3}$,
Xavier Monteys$^{4}$,
and Soumyabrata Dev$^{1,2}$

$^{1}$ADAPT SFI Research Centre, Dublin, Ireland

$^{2}$School of Computer Science, University College Dublin, Ireland

$^{3}$Envo-Geo Environmental Geoinformatics, Skibbereen, Ireland

$^{4}$Geological Survey Ireland, Dublin, Ireland

$^{\dagger}$ Presenting author and corresponding author

We analyse the effectiveness of RMSE, PSNR, SSIM and FOM for evaluating edge detection algorithms used for automated coastline detection. Typically, the accuracy of detected coastlines is assessed visually. This can be impractical on a large scale leading to the need for objective evaluation metrics. Hence, we conduct an experiment to find reliable metrics. We apply Canny edge detection to 95 coastline satellite images across 49 testing locations. We vary the Hysteresis thresholds and compare metric values to a visual analysis of detected edges. We found that FOM was the most reliable metric for selecting the best threshold. It could select a better threshold 92.6% of the time and the best threshold 66.3% of the time. This is compared RMSE, PSNR and SSIM  which could select the best threshold 6.3%, 6.3%  and 11.6% of the time respectively. We provide a reason for these results by reformulating RMSE, PSNR and SSIM in terms of confusion matrix measures. This suggests these metrics not only fail for this experiment but are not useful for evaluating edge detection in general.

Monitoring the coastline is important for coastal management and being prepared for natural disasters. Yet, manually identifying and mapping the coastline can be a time-consuming process. Developing methods for automatically detecting the coastline can improve the efficiency and accuracy of coastal monitoring efforts. Following this, it is crucial to develop metrics for assessing the accuracy of these automated methods. They will allow researchers and practitioners to objectively evaluate automated coastline detection methods and compare their performance across different datasets and conditions. This comparison can also be done on a scale that is not practical with visual analysis.

Related Work
Edge detection is an important aspect of coastal monitoring processes. We can detect the border where land meets water <cit.> or the vegetation line along the coast <cit.>. These lines can be considered prominent edges that we aim to detect using automated edge detection methods. Detecting them is the first step in more complex monitoring processes. For example, by tracking the lines through time we can estimate coastal erosion rates <cit.>.

The most common way for evaluating the accuracy of the edge detection methods is using visual analysis <cit.>. This involves comparing the images of the coastlines to the detected edges and making a subjective evaluation of the performance.  For these studies, visual analysis is an appropriate method. The datasets are small and they lack ground truth edges for which to compare the detected edges too.

More objective evaluation metrics have been applied in studies with larger datasets <cit.>. Here the researchers compared different image segmentation models on a dataset of 98 coastline satellite images. The researchers took a segmentation approach to coastline detection. This means the output of the model was a binary segmentation mask that classified each pixel as either land (0) or water (1). The output was then compared to ground truth masks using metrics such as accuracy, precision and recall. It is not clear if these metrics are appropriate for evaluating edge detection algorithms.

This would involve comparing predicted edges to ground truth edges. Various quality assessment metrics have been proposed to make this comparison. These include root mean square error (RMSE), peak signal-to-noise ratio (PSNR), universal image quality index (UQI), structural similarity (SSIM) <cit.> and figure of merit (FOM) <cit.>. We aim to understand how effective these metrics are for evaluating coastline edge detection methods.

Our main contributions are to:

* Analyse the effectiveness of various edge detection algorithms on a diverse dataset of coastline satellite images.

* Reformulate RMSE, PSNR, SSIM in terms of confusion matrix measures to understand why they are not effective metrics for evaluating edge detection algorithms.

* We open source the code to reproduce the results of this paper. This can be found in the GitHub repository [In the spirit of reproducible research, the codes to reproduce the results of this paper can be found here: <https://github.com/conorosully/edge-detection-metrics>.].

We base our analysis on the Sentinel-2 Water Edges Dataset (SWED) <cit.>. This contains satellite images and binary segmentation masks from a variety of coastlines. We consider the 98 test images and labels from SWED as a reference dataset.  We do not consider the training set as it has been labelled using semi-supervised methods. In comparison, more care has been taken when labelling the test set. Although, we did identify 3 images in the test set with erroneous binary masks (see appendix for details). We removed these leaving us with 95 images.

As input, 12 spectral bands are available from sentinel-2 imagery. They include visible red, green and blue wavelengths. The example image in Figure <ref> has been created by combining these three bands. The bands also include shortwave inferred wavelengths. We considered each of the bands separately and treat them as grayscale images.

As seen in Figure <ref> the dataset contains a mask for each image. The pixels in the mask are given a value of 0 for land and 1 for water. We obtain edge maps by applying the Canny edge detection algorithm discussed in the next section to the masks. We take these edge maps as our ground truth.

Input images and ground truth masks obtained from SWED <cit.>. The ground truth edge map has been obtained by applying canny edge detection to the ground truth mask.

Edge detection
The Canny edge detection algorithm is a multistage algorithm used to identify prominent edges in images <cit.>. The steps include:

* Noise reduction using Gaussian smoothing

* Calculating gradients by considering changes in pixel intensity

* Non-maximum suppression to produce thin edges

* Hysteresis thresholding to select the final edges

The final step is of particular importance to this paper. Two thresholds are used. Pixels with an intensity above the upper threshold are considered strong edges. Pixels below the upper threshold but above the lower threshold are considered weak edges. Finally, all strong edges and weak edges connected to strong edges are labelled as edges.

We apply Canny using different Hysteresis thresholds—[50,100], [50,150], [100,200], [100,300], [200,400], [200,600] with the lower and upper bounds given respectively. By varying the thresholds, we change the sensitivity of the algorithm. Ideally, as we increase the thresholds the algorithm should become less sensitive to noisy edges caused by factors like ocean swell and land development. Then, at some point, even  prominent coastal edges should be excluded. We then compare the detected edges to the ground truth using a variety of metrics.

Evaluation metrics

Route Mean Square Error (RMSE) is defined as:

$$ RMSE(E,G) = \sqrt{MSE(E,G)} $$

$$ MSE(E,G) = \frac{1}{MN}  \sum_{i=0}^{M-1} \sum_{j=0}^{N-1} (E_{i,j} - G_{i,j})^2 $$

$E_{i,j}$ and $G_{i,j}$ are the pixel values in the $i,jth$ position in the detected edge map (E) and the ground truth (G). In general, both images will consist of MxN pixels. In our case, both M and N are equal to 256.

Peak Signal-to-noise Ratio (PSNR) is defined as:

$$ PSNR(E,G) = 10log_{10}\frac{255^2}{MSE(E,G)} $$

Smaller values for RMSE indicate better performance. In comparison, larger values for PSNR indicate better performance. As both metrics are based on MSE, we should expect them to identify similar Hysteresis thresholds as the best performers.

Structural Similarity Index (SSIM) is defined as:

$$ SSIM(G, E) = [l(G, E)]^\alpha.[c(G, E)]^\beta.[s(G, E)]^\gamma $$

$$ l(G,E)={\frac {2\mu _{G}\mu _{E}+c_{1}}{\mu _{G}^{2}+\mu _{E}^{2}+c_{1}}} $$

$$ c(G,E)={\frac {2\sigma _{G}\sigma _{E}+c_{2}}{\sigma _{G}^{2}+\sigma _{E}^{2}+c_{2}}} $$

$$ s(G,E)={\frac {\sigma _{G,E}+c_{3}}{\sigma _{G}\sigma _{E}+c_{3}}} $$

$\mu _{G}$ and $\mu _{E}$ are the average pixel values, $\sigma _{G}$ and $\sigma _{E}$ are the standard deviations of the image pixel values and $\sigma _{G,E}$ is the covariance of the pixel values. SSIM will fall between -1 and 1 with 1 indicating that the images are perfectly identical. RMSE and PSNR both considered pixels on an individual basis. Whereas, SSIM attempts to base the similarity measure on the luminance (l), contrast (c), and structure (s) of the two images. The result is a metric that is more similar to the human visual system for identifying symmetry <cit.>.

Figure of merit (FOM) is defined as:

$$ FOM(E,G) = \frac{1}{max(N_E, N_G)} \sum_{k=1}^{N_E} \frac{1}{1+\alpha d^2(k)} $$

$N_G$ is the number of the actual edge pixels, $N_E$ is the number of the detected edge pixels, $\alpha$ is the scaling constant, and $d(k)$ is the minimum distance between the detected edge pixel and an actual edge pixel <cit.>.

We also consider Confusion Matrix-based Measures based on the values in Table <ref>. TP is the count of cases where $E_{i,j} = G_{i,j} = 1$, TN is the count where $E_{i,j} = G_{i,j} = 0$, FP is the count where $E_{i,j} = 1, G_{i,j} = 0 $ and FN is the count where $E_{i,j} = 0, G_{i,j} = 1$. We do not evaluate the Canny edge detection algorithm directly with these measures but we considered them when reasoning about the effectiveness of the other metrics.

1l|               1l|1                  1l|0
1c|Actual     1l|1     1l|True Positive (TP)          1l|False Negative (FN)         1l|Actual Positive (P)
1c|Value      1l|0     1l|False Positive (FP)         1l|True Negative (TN)          1l|Actual Negative (N)
2l|                                                      1l|Predicted Positive (P')     1l|Predicted Negative (N')     1l|Total (T)

Confusion matrix for pixel classification. Water pixels are represented by a value of 1 and land pixels are represented by a value of 0.

Other well-known metrics have been excluded from this study. This includes UQI as it is a special case of SSIM where the stabilizing constants are set to 0 <cit.>. We also excluded the Edge-based structural similarity measure (ESSIM) as it was developed for comparing blurry images  <cit.>.

Visual analysis
We evaluate the effectiveness of the above metrics to select the best Hysteresis threshold using visual analysis. For each of the 95 test images, we select the threshold that produces the edge map that is visually the most similar to the ground truth edge map. This is done without looking at the evaluation metric values. We can then compare these to the threshold selected by the evaluation metrics. This allows us to calculate the percentages of images correctly identified by each metric. We restrict the visual analysis to the NIR band as it has been shown to be effective for extracting water bodies <cit.>.

Results and Discussion

Metric trends by threshold
Figure <ref> shows the trends in RMSE, PSNR, SSIM and FOM as we increase the thresholds. For all 12 spectral bands, RMSE, PSNR and SSIM indicate a monotonic improvement as the thresholds are increased and the highest threshold produces the best results. In addition, compared to the other bands, these metrics indicate that NIR had the worse average performance at all threshold levels. In comparison, the best threshold for each band varied when using FOM with [100,200], [100,300] being the most common. The NIR band is also not the worse overall performing band.

Average RMSE, PSNR, SSIM and FOM for each spectral band with error bars given by the standard deviation. Based on RMSE, PSNR and SSIM, the performance improves as we increase the thresholds and the NIR band is the worst-performing band. For FOM, we do not see a monotonic improvement for any of the spectral bands.

Figure <ref> shows that FOM had a larger standard deviation when compared to the other metrics. A potential reason for this is that the best threshold for each image does vary and FOM has a high standard deviation as it is able to identify the most appropriate threshold. We can see this in Table <ref>. This gives the counts of test images if we selected the best-performing threshold across all 12 spectral bands. For RMSE, PSNR and SSIM, the counts are skewed towards the higher thresholds. For FOM, the counts are more evenly distributed.

Visual analysis

Ultimately, the monotonic improvement for RMSE, PSNR and SSIM is suspicious.  It suggests that as we decrease the sensitivity of the Canny algorithm we get better results. Additionally, the poor performance of the NIR bands indicated by the metrics is contrary to prior research. To confirm that FOM is the only metric able to identify appropriate thresholds we performed a visual analysis. This showed that FOM could select the best threshold for 66.3% of the 95 test images. In comparison, RMSE, PSNR and SSIM selected the best image 6.3%, 6.3%  and 11.6% of the time respectively.

We can see some examples of this analysis in Figure <ref>. Here we compare the reference edge maps of 4 test images to the predicted edge map using the NIR band at the varying threshold levels. You can see that as we increase the thresholds fewer noisy edges are detected and then later the algorithm detects fewer coastline edges. In each case, FOM selected the edge map that is visually the most similar to the ground truth. In comparison, RMSE, PSNR, and SSIM tend to select the maps with fewer edges.

Examples of where FOM correctly identifies the detected edge map that is visually the most similar to the ground truth. Each row gives a different example image. The columns give the edge maps detected using the increasing Hysterious thresholds. In each case, the NIR band is used as the input to Canny. The bold numbers give the best value for each metric.

In Figure <ref>, Example 5 shows an example of where FOM does not clearly select the best edge map. Based on the visual analysis, the threshold of [100,200] was selected whereas FOM selects a threshold of [100,300]. However, the map selected by FOM is visually more similar to the ground truth than the one selected by the other metrics. If we consider all these cases, we found that FOM could select the same or better edge map for 92.6% of the images.

Examples of where FOM fails to identify the best-detected edge map. The bold numbers give the best value for each metric. The NIR band is used as input for Canny.

Figure <ref> also gives Example 6. Here we do not see the expected behaviour of less noisy edges being detected and the coastline edges remaining as we increase the threshold. We could consider these cases too noisy as the non-coastal edges are more prominent than coastal edges. We identified 15 of these cases. When they were removed form the analysis, we get similar results to before. That is RMSE, PSNR, SSIM and FOM could identify the best edge maps for 5.0%, 5.0%, 11.3% and 73.8% of the 80 images respectively. Additionally, FOM could identify the same or better map 93.8% of the time.

Reasons for trends
From the above analysis, it is clear that the metrics based on MSE fail to identify the best edge map. When understanding why they fail, we should consider that comparing edge maps is a special case of comparing two images. The pixel values can only take on values of 1 or 0. This means that $(E_{i,j} - G_{i,j})^2$ will take on a value of 1 for incorrectly labelled pixels and 0 otherwise and we can reformulate MSE in terms of the confusion-matrix-based measures:

$$MSE \propto FP +FN $$

$$RMSE \propto FP +FN $$

$$PSNR \propto \frac{1}{FP + FN} $$

Figure <ref> shows that as we increase the thresholds fewer pixels are labelled as edges. This leads to fewer FPs and more FNs. These effects will have opposite impacts on MSE. In Figure <ref>, we can see that FPs tend to decrease at a higher rate than FNs increase. This leads to an improvement in MSE as we increase the thresholds.

The effect on confusion matrix measures as we increase the Hysteresis. Only the minimum and maximum thresholds are given. The NIR band is used as input for Canny.

The average sum of FP and FN for each band. The value decreases as we increase the thresholds. This indicates that FPs tend to decrease at a higher rate than FNs increase.

SSIM can also be reformulated in terms of confusion-matrix measures (see the appendix for proof). In this case, the relationship is not as clear but SSIM has likely been affected in a similar way to MSE. That is by the monotonic changes in the confusion matrix measures as we increase the thresholds.

$$ SSIM(G, E) \approx  \frac{4P'P (N.TP - P'P)} {({P'}^2 + P^2)(P'(N-P') +P(N-P))} $$

These monotonic changes will not necessarily be present in all edge detection experiments. Yet, the reformulation of the MSE and SSIM suggests that, for evaluating edge detection algorithms, these metrics have no advantage over those based on confusion matrix measures. The downside to these measures is they give the same weighting to incorrectly labelled pixels regardless of their distance from ground truth edges. We can see this in Figure <ref>, where FPs appear close to ground truth edges.In comparison, FOM incorporates the distance between pixels. This difference is potentially the reason FOM has shown to be the most effective metric for evaluating this edge detection problem.

Conclusions and future work

From our experiment, we've seen that FOM was the only reliable metric used to evaluate edge detection algorithms. Based on a visual analysis of 95 coastline satellite images, FOM could select the best detected edge map 66.3% of the time. This is compared to RMSE, PSNR and SSIM which could select the best map 6.3%, 6.3%  and 11.6% of the time respectively. Additionally, FOM could select a map that was visually better than the other metrics 92.6% of the time. We argued that the reason for this is FOM considered the distance between pixels. In comparison, RMSE, PSNR and SSIM give equal weight to incorrectly labelled edges regardless of their distance from true edges.

It is not clear if the results of our experiments would extend to all edge detection approaches. By varying the Hysterious threshold of the Canny edge detection algorithm, we were able to compare trends in the metrics to changes in the algorithm's sensitivity to edges. Other approaches, such as deep learning,  will not have this sensitivity mechanism. Nonetheless, we were able to reformulate RMSE, PSNR and SSIM in terms of confusion-matrix metrics. This suggests that for any edge detection evaluation, these metrics do not provide advantages over confusion-matrix metrics. Following from this, it is best to use a combination of FOM and confusion-matrix metrics to evaluate edge detection algorithms.

By considering the distance between pixels, FOM also has a meaningful interpretation for coastline detection problems—the average distance between the detected coastline and the actual coastline. If we compare the same coastline through time, this interpretation changes. FOM now quantifies the change in the coastline. It follows that FOM could be used as a proxy for coastal erosion rates and we plan to investigate this in future research.

This publication has emanated from research conducted with the financial support of Science Foundation Ireland under Grant number 18/CRT/6183. For the purpose of Open Access, the author has applied a CC BY public copyright licence to any Author Accepted Manuscript version arising from this submission. This research was conducted with the financial support of Science Foundation Ireland under Grant Agreement No. 13/RC/2106_P2 at the ADAPT SFI Research Centre at University College Dublin. The ADAPT Centre for Digital Content Technology is partially supported by the SFI Research Centres Programme (Grant 13/RC/2106_P2) and is co-funded under the European Regional Development Fund.

§ APPENDIX

§.§ Mean Square Error

$$ MSE(E,G) = \frac{1}{N}  \sum_{j=1}^{N} (E_{i} - G_{i})^2  $$

$$ (E_{i} - G_{i})^2 =
\begin{cases}
0 & \text{if } E_{i} = G_{i} \\
1 & \text{if } E_{i} \neq  G_{i}
\end{cases} $$

Referring to the confusion matrix metrics in Table <ref>, when $E_{i} \neq  G_{i}$ we have either a false positive (FP) or false negative (FN). This means we can reformulate MSE as:

$$ MSE(E,G) = \frac{FP+FN}{N}    $$

If follows that:

$$ RMSE(E,G) = \sqrt{MSE(E,G)} =  \sqrt{\frac{FP+FN}{N}}$$

$$ PSNR(E,G)  = 10log_{10}\frac{255^2}{MSE(E,G)} = 10log_{10}\frac{N*255^2}{FP+FN} $$

§.§ Structural Similarity Index

$$\mu_E = \frac{1}{N} \sum_{i=1}^{N} E_i = \frac{P'}{N} $$

$$\mu_G = \frac{1}{N} \sum_{i=1}^{N} G_i = \frac{P}{N}$$

\begin{align*}
\sigma_E^2 &= \frac{1}{N-1} \sum_{i=1}^{N} (E_i-\mu_E)^2 \\
&= \frac{1}{N-1} \sum_{i=1}^{N} (E_i^2-2\mu_E E_i +\mu_E^2)\\
&= \frac{1}{N-1} \sum_{i=1}^{N} (E_i-2\mu_E E_i +\mu_E^2) & \text{as } E_i\in \{0,1\}\\
&= \frac{1}{N-1} (P' -2\mu_EP' +N\mu_E^2) \\
&= \frac{1}{N-1} (P' -2\frac{{P'}^2}{N} +\frac{{P'}^2}{N}) & \text{as } \mu_E = \frac{P'}{N} \\
&= \frac{P'(N-P')}{N(N-1)}
\end{align*}

$$ \sigma_G^2  =  \frac{P(N-P)}{N(N-1)} $$

\begin{align*}
\sigma_{E,G} &= \frac{1}{N-1} \sum_{i=1}^{N} (E_i-\mu_E)(G_i-\mu_G) \\
&= \frac{1}{N-1} \sum_{i=1}^{N} (E_iG_i-\mu_E G_i-\mu_G E_i +\mu_E \mu_G)\\
&= \frac{1}{N-1}(TP-\mu_E P-\mu_G P' +N\mu_E \mu_G)\\
&= \frac{1}{N-1}(TP-\frac{P'P}{N} -\frac{P'P}{N} +\frac{P'P}{N}) \\
&= \frac{N.TP-P'P}{N(N-1)}
\end{align*}

$$ SSIM(G, E) = [l(G, E)]^\alpha.[c(G, E)]^\beta.[s(G, E)]^\gamma $$

Following from <cit.>, if we set $\alpha = \beta = \gamma = 1 $ and $ C_3 = C_2 /2 $ then the equation simplies to:

\begin{align*}
SSIM(G, E) &= \frac{(2\mu_E\mu_G+C1)(2\sigma_{E,G}+C2)}{(\mu_E^2+\mu_G^2+C1)(\sigma_E^2+\sigma_G^2+C2)}\\
& \approx  \frac{(2\mu_E\mu_G)(2\sigma_{E,G})}{(\mu_E^2+\mu_G^2)(\sigma_E^2+\sigma_G^2)} \\
&= \frac{4P'P (N.TP - P'P)}{({P'}^2 + P^2)(P'(N-P') +P(N-P))}
\end{align*}

§.§ Remove images

The images listed below were removed from the SWED test set for this analysis. The first image  was removed as the mask is flipped—land is labelled as 1 and water 0. The other two are removed as part of the land has not been labelled as land.


# Visual scoping operations for physical assembly

Felix Binder
Dept. of Cognitive Science
UC San Diego
<EMAIL_ADDRESS>Marcelo Mattar
Dept. of Cognitive Science
UC San Diego
<EMAIL_ADDRESS>David Kirsh
Dept. of Cognitive Science
UC San Diego
<EMAIL_ADDRESS>Judith Fan
Dept. of Psychology
UC San Diego
<EMAIL_ADDRESS>
###### Abstract

Planning is hard. The use of subgoals can make planning more tractable, but
selecting these subgoals is computationally costly. What algorithms might
enable us to reap the benefits of planning using subgoals while minimizing the
computational overhead of selecting them? We propose visual scoping, a
strategy that interleaves planning and acting by alternately defining a
spatial region as the next subgoal and selecting actions to achieve it. We
evaluated our visual scoping algorithm on a variety of physical assembly
problems against two baselines: planning all subgoals in advance and planning
without subgoals. We found that visual scoping achieves comparable task
performance to the subgoal planner while requiring only a fraction of the
total computational cost. Together, these results contribute to our
understanding of how humans might make efficient use of cognitive resources to
solve complex planning problems.

Keywords: planning; problem solving; physical reasoning; spatial reasoning;
task decomposition; hierarchical reinforcement learning

## Introduction

Imagine you are preparing a meal. You need to wash, chop, heat, sauté, move
around, boil. How do you know what to do next? Planning every action in
advance is practically impossible: the number of potential sequences of
actions grows exponentially with one’s action repertoire and the number of
steps needed to reach the goal state. Not planning at all is no better: some
actions must precede others (you can’t sauté without heating the pan), and
timing matters too (e.g., adding sauce to uncooked pasta). How do humans
manage to routinely solve such complex planning problems in everyday life?

Classical approaches to planning formulate such problems as search over a
space of actions (?, ?, ?), augmented with heuristics and stochastic methods
to more selectively search the space of possible actions (?, ?). Even with
heuristics and stochastic methods, planning complex tasks in a rich
environment is computationally prohibitive, because the space of potential
plans that needs to be searched grows rapidly with both the number of possible
actions available and the number of actions required to achieve the task (?,
?). The computational complexity predicted by the classical approach is at
odds with the effortlessness with which people act in the real world (?, ?).

A promising alternative approach from hierarchical reinforcement learning (?,
?) permits an agent to learn abstractions over sequences of actions, which can
then be invoked as subgoals during planning (?, ?, ?, ?). However, while
proposing good subgoals can reduce the computational cost of planning the
sequences of actions (?, ?), actually choosing which subgoals to propose can
itself be highly costly. How might people manage these costs?

What these formal approaches tend to ignore is that when people confront such
tasks they are often embedded in physical environments that can be
reconfigured to suit their current goals (?, ?). For example, one could gather
all the vegetables on the cutting board and then focus on chopping what is
there, ignoring what could be done elsewhere in the kitchen. After achieving
this subgoal, it may be worth considering what the next subgoal should be
(e.g., sautéing the vegetables), then focusing on that task (e.g., only
considering actions available near the stove), and so on. We call this visual
scoping—manipulating the visual environment to select the next subgoal. While
such a strategy would not be expected to always identify the optimal sequence
of subgoals, it may reduce the overall cost of jointly inferring subgoals and
actions without leading to devastating consequences. This paper aims to
establish a basic understanding of how such a visual scoping mechanism
constrains planning behavior and impacts the overall computational cost of
planning. Our investigation of visual scoping takes inspiration from recent
work exploring how agents intervene on the world to aid in physical reasoning
and planning (?, ?, ?). Unlike these studies, we focus not on experimental or
perceptual interventions which yield new information, but rather on
interventions that select already present information to aid physical and
spatial reasoning (?, ?).

As a case study, we consider planning in block-tower reconstruction problems,
in which an agent uses an inventory of rectangular blocks to recreate a
specific block tower. The combinatorial nature of construction leads to an
explosion in the number of possible states to consider when planning block
placements. To explore how visual scoping may influence problem solving in
this challenging domain, we conducted a set of computational experiments
comparing its behavior to that of both classical planning algorithms and more
recent approaches which decompose the task into subgoals in advance of action-
level planning (?, ?). We discovered that visual scoping can approximate the
success and efficiency of full task decomposition on a block-tower
reconstruction task while requiring a much smaller computational budget
overall. We also find that in trading off quick progress and low planning cost
in choosing the next subgoals, valuing minimizing planning costs leads to more
subgoals and poorer performance. Together, these findings help advance our
knowledge of how perceptual and cognitive constraints interact to support
efficient problem solving.

## Approach

Figure 1:  We relate three different strategies for planning using subgoals:
no subgoals, planning only the next subgoal (scoping) and planning all
subgoals in advance (full-subgoal planning). A schematic search tree of
potential actions is shown at the bottom. Both the number of possible
different actions (breadth of tree) and the length of sequences of action
(depth) increases with the size of the subgoal.

### Block-tower reconstruction task

Three specific considerations motivated the choice of block-tower
reconstruction for our experiments: (1) it requires planning over somewhat
extended time horizons, (2) it is familiar enough to people that they can
easily predict the consequence of their actions, and (3) it is inherently
spatial, enabling visual scoping to select regions of the environment to focus
on that could constitute plausible subgoals. Here we use the block tower
reconstruction task, which entails assembly of two-dimensional block towers in
a gridworld running simulated physics (?, ?). Similar block tower construction
tasks have been used to study planning and physical reasoning in artificial
agents (?, ?, ?) and humans (?, ?, ?, ?).

On each trial, the planner is presented with an outline of a shape and has to
recreate it by placing blocks from a fixed inventory in a building area. An
action consists of the choice of a block (eg. 2x1) and a horizontal location.
The block is then placed on top of the highest block or the ground in that
horizontal location. Once a block has been placed it cannot be removed,
necessitating planning in order to not get stuck in dead ends.111If actions
can be undone, planning is not technically necessary (?, ?): one could just
try out actions and backtrack if they fail. However, placing and then undoing
physical parts is costly and not always possible. Reasoning about the
consequences of actions is thus important, particularly in domains where most
paths do not lead to the goal. As a simplification in our current experiments,
blocks were also “glued down” after they were placed, preventing towers from
toppling over. The trial ends either when the target shape is perfectly
reconstructed, when no further block can be placed or when the planner chooses
to not place a further block. The trial is considered successful if the target
shape has been exactly reconstructed. 16 unique silhouettes were used in our
experiments, spanning a range of difficulty levels for the planner. This is a
challenging task for human participants: human subjects average 22.4% perfect
reconstruction, albeit without glued blocks (?, ?).

### Visual scoping

The use of subgoals can reduce both the number of possible different actions
and the length of sequences of actions needed to reach the (sub)goal (see
Figure 1). Visual scoping attempts to reap this computational benefit while
minimizing the cost of subgoal selection by only choosing the next subgoal
depending on the current state of the environment. Our visual scoping planner
works by interleaving two operations: (1) identifying the next subgoal to
achieve, and (2) using an action-level search algorithm to plan the sequence
of actions to achieve that immediate subgoal (Algorithm 1, Figure 1). Subgoals
are defined spatially: a subgoal is defined as a region of space rather than
as a specific state of the world. The set of potential subgoals we consider
are horizontal layers, eg. the first or the first three rows of the target
shape. Splitting a construction problem into horizontal layers is sensible
given the incremental nature of building: it is easier to place blocks on top
of other blocks rather than below them. ? (?) show that young children
naturally adopt a layerwise strategy on a related block construction task. In
our block-tower reconstruction setting, this corresponds to identifying the
height of the subtower the agent seeks to reconstruct, then searching over
potential action plans for doing so.

### Planners

Input: action-level search algorithm $LLP$, target shape $G$, environment $E$

Parameters: weight parameter $\lambda$, computational budget $b$

$c^{total}\leftarrow 0$

Run once:  Full -4pt  While $E\neq G$:  Scoping
$\Phi\leftarrow\\{(g_{1:m1}),(g_{1:m2}),\dots,(g_{1:mn})~{}where~{}g_{m1}=g_{m2}=\dots=g_{nm}=G\\}$
possible complete sequences of subgoals given $E$ Full
$\Phi\leftarrow\\{(g_{1}),(g_{2}),\dots,(g_{n})~{}where~{}g_{1},g_{2},\dots,g_{n}>E\\}$
possible sequences of subgoals given $E$ of length $1$

Scoping For each $(g)$ in $\Phi$:

$s$ = Empty

For each $g$ in $(g)$:

$r_{g}$ $\leftarrow$ $Area(g)-Area(s)$

While $s_{final}\neq g$ and $c^{planning}_{g}<b$:

$c^{solution}=0$

$[(a_{1},\dots,a_{l})_{g},~{}c^{solution}_{g},~{}s_{final}]\leftarrow
LLP(s,g)$

$c^{planning}_{g}~{}+=~{}c^{solution}_{g}$

$c^{total}+=c^{planning}_{g}$

if $s_{final}=g$: if subgoal is solved

$s$ $\leftarrow$ $s_{final}$

else:

$c^{planning}_{g}=\infty$

Continue to next $(g_{k})\in\Phi$

For each $(g)$ in $\Phi$:

$V_{(g)}\leftarrow$ $\sum_{g\in(g)}r_{g}-\lambda*c^{planning}_{g}$

Apply $(a_{1},\dots,a_{l})_{g\in argmax(V_{(g)})}$ to $E$ Choose sequence with
highest score and apply all actions Full Apply $(a_{1})_{g\in
argmax(V_{(g)})}$ to $E$ Choose sequence with highest score and apply only the
first action Scoping define $LLP(s,g)$:

Attempts to find a sequence of actions from $s$ to $g$

return $[(a_{1},a_{2},\dots,a_{n}),c^{solution},s^{final}]$

Algorithm 1 Full-subgoal & scoping planner

#### Subgoal level planners

We implemented two hierarchical subgoal planners, scoping and full-subgoal
planning (see Algorithm 1 for a comparison of the algorithms), as well as a
baseline of not using subgoals at all. The scoping planner considers all
potential next subgoals given the current state of the environment. After a
subgoal has been chosen, the subgoal is passed on to the action-level search
algorithms and the actions it returns are applied to the environment. The
process repeats until the target shape is completed or no subgoal that is
perfectly solvable can be found. It has to trade off immediate progress and
computational cost when selecting a subgoal: does it prefer more substantial
subgoals (i.e., making rapid progress) even at the cost of higher
computational cost, or more modest subgoals that are easier to solve? This
tradeoff is controlled by the $\lambda$ parameter. The higher the value of
$\lambda$, the more the scoping planner works to minimize action-planning
cost. When $\lambda=0$, the scoping planner maximizes progress no matter the
cost. The full-subgoal planner finds one sequence of subgoals from the
beginning of building to the final structure in one go. It first considers all
possible sequences of subgoals that end in the full target shape, selects the
one that minimizes the action-level search algorithm computational cost and
builds the structure from start to finish, as in ? (?). Finally, to compare
the use of subgoal planners to a baseline of pure action-level search not
using subgoals at all we also apply the pure action-level search algorithm
directly on the target structure without decomposing it into subgoals.

These planners use a given action-level search algorithm to determine for each
potential subgoal the computational cost of solving the subgoal with the
action-level search algorithm. This is done by running the action-level search
algorithm repeatedly on a subgoal until a solution is found or the cost
threshold $b$ is exceeded. It is necessary to sample repeatedly, since the
action-level search algorithms used here break ties randomly between equally
good plans and therefore might yield different results. Since not all subgoals
are achievable for a certain action-level search algorithm, a threshold is
needed after which the subgoal is considered unsolvable. Only solvable
subgoals are considered by the subgoal level planner. Finally, the subgoal
planner selects the subgoal or sequence of subgoals that maximizes progress
(the proportion of the target shape solved) while minimizing the cost of
solving the subgoals using the action-level search algorithm. Because the
subgoal planners minimize the planning cost of the action-level search
algorithm, they perform resource-rational task decomposition. (?, ?). Our
implementation of resource-rational task decomposition differs from ? (?) in
three specific ways: (1) the use of abstract subgoal states (rather than
specific world states serving as subgoals), (2) the ability to only plan a
certain number of steps ahead as mediated through $\lambda$, and (3) the
ability to handle impossible subgoals and stochastic action-level search
algorithms.

#### Action-level search algorithms

The subgoals planners are hierarchical agents: they find a subgoal
decomposition both using a particular action-level search algorithm, and
specifically for that particular algorithm. An action-level search algorithm
searches the space of possible actions to find a sequence of actions to reach
a certain goal. Since the space of potential states (different placements of
blocks in the building area) is very large—there are roughly $35^{15}\approx
1.5\times 10^{23}$ different states—exhaustively searching the entire space of
states for a complete sequence of actions is not feasible. Therefore, the
action-level search algorithms are implemented as lookahead planners: if a
path to the solution cannot be found within a certain computational budget,
the planner plans a sequence of actions as long as it can given a
computational constraint with ties broken randomly, then takes the first
action of that sequence and plans again, now on the basis of the state
resulting from the action just taken. We chose two classical search
algorithms: one performing brute search, the other performing search informed
by a heuristic.

Breadth first search lookahead (BFS) exhaustively explores all possible
placements of blocks in the target shape $n$ steps into the future or until a
perfect reconstruction is found, then chooses the sequence of actions that
maximizes the area of the target shape filled out.

A* lookahead runs the A* search algorithm (?, ?) either until a sequence of
actions resulting in a perfect reconstruction is found or until a specified
computational budget is exceeded. A* chooses to explore the action that
minimizes $f(s)=g(s)+h(s)$, where $g(s)$ is the cost of reaching the current
state from the start measured in number of blocks placed down and $h(s)$ is
the heuristic for how expensive the target is to reach from the current state.
Here, $h(n)$ is the number of cells left in the target shape divided by the
size of the smallest block, so it provides a upper bound for the number of
blocks left to fill out the target shape.222Note that the heuristic $h(s)$ is
not strictly admissible: for states that cannot possible reach a perfect
reconstruction (for example, if a hole has been left and covered by a block),
this locked in dead end is not going to be apparent in the heuristic.

#### Hypotheses

The full-subgoal planners considers the largest set of subgoal decompositions,
so we expect that it has the highest rate of perfect reconstruction as well as
the lowest action planning cost of the solutions themselves compared to the
scoping planner. However, we hypothesize that this optimality comes at a steep
cost: we expect the subgoal-planning cost incurred by the full-subgoal planner
to be higher than that incurred by the other two. By contrast, we predict that
the scoping planner will trade off higher performance and cheaper action-level
planning for a large decrease in the cost of finding the subgoals. Finally, we
predict that not using subgoals at all will lead to a much lower rate of
perfect reconstruction and higher action-level algorithmic cost of the
solution that is found.

#### Experiments

We ran each planner $32$ times on each of the $16$ structures using different
random seeds. For the scoping planner, we used $64$ different values of
$\lambda$ each.

## Results

Figure 2:  Scoping can approximate the success and action planning cost of
full-subgoal planning while requiring a much smaller cost in choosing
subgoals. (A) Each dot corresponds to a combination of subgoal planner (no
subgoals, scoping, full-subgoal planning) and action-level search algorithm
(A*, BFS). The cost of planning the actions given the sequence of subgoals and
the rate of perfect reconstruction is shown. (B) Same as (A), but with the
cost of selecting the subgoals shown instead. Costs are measured in evaluated
number of states. Error bars represent bootstrapped 95% confidence intervals.

#### Pure action-level search

To establish a baseline for both success and planning cost, the action-level
search algorithms were used to try to find solutions to the 16 target shapes.
Table 1 shows the success and planning cost of solutions found for a number of
configurations of BFS lookahead and A* lookahead without resampling. Two
particular action-level search algorithms will be used in conjunction with the
scoping and full-subgoal planner: BFS lookahead with a search depth of $3$ and
A* lookahead with a budget of $4096$ iterations. Using pure-action level
search with resampling, BFS achieves a rate of perfect reconstruction of
$0.4375$ ($95\%$ confidence interval (CI): $[$0.4375$,$0.4375$]$; CI derived
by computing the mean reconstruction rate across towers on each of 1000
iterations, where each iteration is defined by a novel permutation of the
random seeds used to initialize search); A* achieves $0.3125$ ($95\%$ CI:
$[$0.3125$,$0.3125$]$). Block construction is a challenging task: pure action-
level search is far from performing at ceiling. Increasing the search budget
of the action-level search algorithms leads to an increase in success, but
with it comes a ballooning of planning costs.

Search | Budget | Accuracy | 95% CI | Cost | 95% CI
---|---|---|---|---|---
Random | None | $0.038\,312\,5$ | [$0.0$, $0.125$] | 0 | [0, 0]
BFS | Depth 1 | $0.099\,625$ | [$0.0$, $0.25$] | $82.9436$ | [$82.0$, $84.8$]
BFS | Depth 2 | $0.186\,562$ | [$0.0625$, $0.3125$] | $1520.14$ | [$1447.0$, $1593.25$]
BFS | Depth 3 | $0.263\,188$ | [$0.125$, $0.4375$] | $24\,544.5$ | [$22\,164.994\,444\,444\,445$, $26\,918.513\,888\,888\,887$]
BFS | Depth 4 | $0.41$ | [$0.1875$, $0.625$] | $351\,777$ | [$314\,981.303\,333\,333\,34$, $383\,280.968\,333\,333\,3$]
A* |  $8$ Iterations | $0.0615$ | [$0.0$, $0.1875$] | $120.15$ | [$114.75$, $126.0$]
A* |  $64$ Iterations | $0.083\,375$ | [$0.0$, $0.1875$] | $342.018$ | [$327.666\,666\,666\,666\,7$, $370.666\,666\,666\,666\,7$]
A* |  $4096$ Iterations | $0.122\,563$ | [$0.0$, $0.25$] | $16\,533.2$ | [$14\,530.111\,111\,111\,111$, $18\,527.888\,888\,888\,89$]
A* |  $65536$ Iterations | $0.100\,125$ | [$0.0$, $0.25$] | $157\,444$ | [$139\,316.333\,333\,333\,34$, $173\,152.333\,333\,333\,34$]

Table 1: Increasing the budget of action-level search increases success
somewhat, but costs grow exponentially. The table shows the cost and accuracy
of various action-level search algorithms without resampling on a single
attempt on the block construction task.

#### Full-subgoal planning

We sought to replicate the finding that using subgoals in planning can reduce
action planning cost (?, ?). We apply the full-subgoal planner to the same
$16$ structures, using both BFS lookahead and A* lookahead as action-level
search algorithms. The full-subgoal planner achieves a perfect reconstruction
on every attempt. The action planning cost of those solutions is cheaper
compared to pure action-level search ($19\,030.836\,151\,785\,716$ fewer
states evaluated, $95\%$ CI:
$[$17\,898.981\,919\,64$,$23\,536.666\,071\,43$]$, $p<0.001$; A*:
$26\,506.25$, $95\%$ CI: $[$26\,506.25$,$26\,506.25$]$, $p<0.001$; CI derived
by computing the mean paired difference in planning cost between agents on
each of 1000 iterations, where each iteration is defined by a new set of
random seeds) compared to the respective action-level search algorithm without
subgoals. While the chosen subgoals themselves are easy to solve, the cost of
coming up with the sequence of subgoals is very large (BFS:
$M=$1.028\,07\text{\times}{10}^{07}$$ states evaluated, $95\%$ CI:
$[$10\,007\,232.0$,$11\,394\,938.410\,937\,5$]$; A*:
$1.393\,78\text{\times}{10}^{07}$, $95\%$ CI:
$[$13\,937\,763.0625$,$13\,937\,763.0625$]$).

#### Scoping

To capture the planning behavior over a broad range of values for $\lambda$,
we average over the dynamic range of $\lambda$ (BFS: $[0,0.008]$, A*:
$[0,0.003]$) for the following analysis. The scoping planner achieves a
slightly lower success compared to full-subgoal decompositions perfect success
rate (BFS: $0.104$ lower rate of perfect reconstruction compared to full-
subgoal planner, $95\%$ CI: $[$0.0$,$0.1875$]$, $p=$0.0415$$; A*:
$0.145\,375$, $95\%$ CI: $[$0.0625$,$0.25$]$, $p=$0.0075$$). The scoping
planner finds more expensive solutions (BFS: $9107.298\,562\,5$ more states
evaluated, $95\%$ CI: $[$3767.076\,562\,5$,$17\,013.914\,062\,5$]$, $p<0.001$;
A*: $14\,842.357\,062\,5$, $95\%$ CI: $[$8268.4375$,$25\,458.181\,25$]$,
$p<0.001$). However, the subgoal planning cost is dramatically lower (BFS:
$9\,527\,501.560\,812\,5$ fewer states evaluated, $95\%$ CI:
$[$9\,079\,226.628\,125$,$10\,673\,451.054\,687\,5$]$, $p<0.001$; A*:
$13\,060\,800.555\,812\,5$, $95\%$ CI:
$[$12\,992\,823.25$,$13\,161\,382.368\,75$]$, $p<0.001$) —see Figure 2. Figure
3 shows the chosen task decompositions made by the planners.

When building block towers, the planner can choose to use large blocks, making
progress quickly, or to apply a more conservative strategy of using smaller
blocks. The average number of blocks in a successful solution measures this
tendency. Using BFS lookahead, the scoping planner uses more blocks on average
compared to pure action-level search ($5.330\,562\,5$ more blocks used per
solution, $95\%$ CI: $[$2.6875$,$7.875$]$, $p<0.001$), but insignificantly
fewer than the full-subgoal planner ($2.272\,437\,5$ fewer blocks, $95\%$ CI:
$[$-1.689\,062\,5$,$6.064\,062\,5$]$, $p=$0.064$$). Thus, the scoping planner
using BFS lookahead finds somewhat longer solution solution compared to pure
action-level search, but not full subgoal decomposition. Under A* lookahead,
the scoping planner uses fewer blocks than both pure action-level search
($1.4135$ fewer blocks, $95\%$ CI: $[$-0.25$,$3.3125$]$, $p=$0.027$$) and
full-subgoal planning ($3.095\,437\,5$ fewer blocks, $95\%$ CI:
$[$1.5625\text{\times}{10}^{-03}$,$6.1875\text{\times}{10}^{00}$]$,
$p=$0.015$$).

Figure 3: An overview over the different decompositions chosen by each
planner. Each vertical stripe corresponds to a single attempt of the planner
to build a certain target shape. Each chosen subgoal is marked in a different
color, with blue indicating a the first and orange the eight chosen subgoal.
The columns are organized by target shape and for the scoping planners sorted
by $\lambda$.

#### Trading off immediate progress and action planning cost

Figure 4:  Parameter $\lambda$ governs the tradeoff between choosing a subgoal
that is easy to solve and one that maximizes progress. (A) A higher emphasis
on minimizing action planning cost as opposed to maximizing progress
(increasing $\lambda$) leads to a decrease in action planning cost, (B) a
lower rate of perfect reconstruction, (C) an increase in the number of
subgoals the planner actually ends up using, (D) as well as the total subgoal
planning cost, since the scoping planners need to find the next subgoal more
often. (E) It increases the number of blocks used for BFS lookahead, but not
for A* lookahead.

To analyze the tradeoff between avoiding costs and making progress, we apply
the scoping planner under a range of values for $\lambda$—see Figure 4. As
expected, valuing reducing planning cost indeed results in a reduction in
action planning cost (BFS: Pearson’s r($62$) = $-0.927\,056\,312\,707\,038$,
$95\%$ CI: $[$-0.928\,986\,24$,$-0.925\,307\,24$]$, $p<0.001$; A*: r($62$) =
$-0.580\,604\,115\,227\,357\,8$, $95\%$ CI:
$[$-0.580\,604\,12$,$-0.580\,604\,12$]$, $p<0.001$, all confidence intervals
bootstrapped). Along with this comes a reduction in success (BFS: r($62$) =
$-0.954\,868\,684\,193\,613\,3$, $95\%$ CI:
$[$-0.954\,868\,68$,$-0.954\,868\,68$]$, $p<0.001$; A*: r($62$) =
$-0.839\,852\,574\,429\,553\,4$, $95\%$ CI:
$[$-0.839\,852\,57$,$-0.839\,852\,57$]$, $p<0.001$): with lower action
planning costs comes an increased chance of building oneself into a corner.
When increasing $\lambda$, the number of subgoals also increases (BFS: r($62$)
= $0.981\,818\,227\,548\,850\,7$, $95\%$ CI:
$[$0.976\,310\,14$,$0.986\,020\,1$]$, $p<0.001$; A*: r($62$) =
$0.964\,289\,655\,679\,577\,7$, $95\%$ CI:
$[$0.964\,289\,66$,$0.964\,289\,66$]$, $p<0.001$. Paradoxically, trying to
minimize action planning costs increases the total subgoal planning cost (BFS:
r($62$) = $0.961\,095\,646\,730\,768\,6$, $95\%$ CI:
$[$0.949\,805\,28$,$0.970\,136\,98$]$, $p<0.001$; A*: r($62$) =
$0.920\,284\,113\,225\,175\,1$, $95\%$ CI:
$[$0.920\,284\,11$,$0.920\,284\,11$]$, $p<0.001$. This is due to the increase
in the number of subgoals, as smaller subgoals tend to be easier to plan. More
subgoals means that the costly subgoal planning cost needs to be performed
more often. This illustrates that cognitive resource limitations can lead to a
larger total of cognitive resources used, albeit in smaller increments.

Finally, the found solutions themselves qualitatively differ across values of
$\lambda$ as well as action-level search algorithms. Increasing $\lambda$
leads to more blocks being placed when using BFS as a action-level search
algorithm, but a slight decrease with A* (BFS: r($62$) =
$0.560\,252\,748\,340\,526\,4$, $95\%$ CI: $[$0.420\,267$,$0.677\,684\,39$]$,
$p<0.001$; A*: r($62$) = $-0.054\,436\,919\,591\,866\,08$, $95\%$ CI:
$[$-0.247\,589\,46$,$0.131\,608\,65$]$ $p=$0.143$$). Valuing making progress
over avoiding planning cost thus leads the scoping planner with BFS lookahead
to shorter solutions, whereas avoiding costs leads to more conservative,
longer solutions.

## Discussion

We found that both scoping and full-subgoal planning outperformed pure action-
level search, consistent with the notion that decomposing complex problems can
be beneficial. While full-subgoal planning succeeds in finding the best task
decompositions, the cost of finding this decomposition into subgoals is much
higher than the scoping planner requires to achieve comparable task
performance. In order to be a plausible proposal for how people approach these
planning problems, both kinds of costs need to be taken into account. Here we
assume that subgoal planning cost as defined is a plausible proxy for the
actual cost of finding subgoals: while humans likely don’t fully search for
actions for all potential subgoals, the cost of subgoal planning arguably
depends on the number of potential subgoals as well as their difficulty. Taken
together, our findings suggest that visual scoping may be a promising way to
reap the benefits of utilizing subgoals while minimizing the overhead of
subgoal planning, thereby making efficient use of limited cognitive resources.

Given the way that scoping exploits spatial information to manage the
computational overhead involved in planning, it may also be a useful source of
insight into how people solve similar spatial reasoning problems. Towards this
end, we are developing a novel behavioral paradigm allowing people to visually
define subgoals during planning, enabling us both to make inferences about
cognitive resource constraints and to observe how they interleave planning and
action over time. A promising direction for future work is the evaluation of a
broader array of scoping strategies, such as those forms of scoping closer to
full-subgoal planning that plan more than one subgoal into the future at a
time before taking action. Likewise, we aim to extend visual scoping from
simple two-dimensional grid worlds to richer three-dimensional environments,
where effective use of cognitive resources is crucial. In the block tower
reconstruction task, the environment is deterministic. When the effect of the
actions are uncertain—when the environment is stochastic or its dynamics
aren’t fully known to the planner—the benefit of only planning subgoals into
the near future is likely going to be more relevant. A future direction is to
investigate how people scope in non-deterministic environments. Finally,
visual scoping understands the planners as embedded in space and time: the
planner exploits the structure of its environment to propose subgoals, and
those subgoals are proposed on the basis of actions the planner has taken
before. In this sense, visual scoping connects classical algorithmic models of
problem solving with the notion of cognition being always situated in and
dependent on an environment (?, ?).

## Acknowledgments

The authors would like to thank Will McCarthy for his development of the block
tower reconstruction task, as well as members of the Cognitive Tools Lab at UC
San Diego for their comments and support. This work was supported by NSF
CAREER Award #2047191 to J.E.F.

All code and materials available at:
https://github.com/cogtoolslab/tools_block_construction

## References

  * Allen, Smith, TenenbaumAllen et al. Allen, K. R., Smith, K. A., Tenenbaum, J. B.  (2020).  Rapid trial-and-error learning with simulation supports flexible tool use and physical reasoning.  _Proceedings of the National Academy of Sciences_ , _117_(47), 29302–29310.
  * Bapst, Sanchez-Gonzalez, Doersch, et al.Bapst, Sanchez-Gonzalez, Doersch, et al. Bapst, V., Sanchez-Gonzalez, A., Doersch, C., Stachenfeld, K. L., Kohli, P., Battaglia, P. W., Hamrick, J. B.  (2019).  Structured agents for physical construction.  _arXiv:1904.03177 [cs]_.
  * Bapst, Sanchez-Gonzalez, Shams, et al.Bapst, Sanchez-Gonzalez, Shams, et al. Bapst, V., Sanchez-Gonzalez, A., Shams, O., Stachenfeld, K., Battaglia, P. W., Singh, S., Hamrick, J. B.  (2019).  Object-oriented state editing for HRL.  _arXiv:1910.14361 [cs, stat]_.
  * BellmanBellman Bellman, R.  (1957).  _Dynamic programming_ (1st ed.).  Princeton, NJ, USA: Princeton University Press.
  * Botvinick, Niv, BartoBotvinick et al. Botvinick, M. M., Niv, Y., Barto, A. G.  (2009).  Hierarchically organized behavior and its neural foundations: a reinforcement learning perspective.  _Cognition_ , _113_(3), 262–280.
  * Correa, Ho, Callaway, GriffithsCorrea et al. Correa, C. G., Ho, M. K., Callaway, F., Griffiths, T. L.  (2020).  Resource-rational Task Decomposition to Minimize Planning Costs.  _arXiv:2007.13862 [cs]_.
  * Cortesa, Jones, Hager, KhudanpurCortesa et al. Cortesa, C. S., Jones, J. D., Hager, G. D., Khudanpur, S.  (2018).  Constraints and Development in Children’s Block Construction.  _Proc. 40nd Annu. Meet. Cogn. Sci. Soc_ , 6.
  * Cortesa, Jones, Hager, Khudanpur, SheltonCortesa et al. Cortesa, C. S., Jones, J. D., Hager, G. D., Khudanpur, S., Shelton, A. L.  (2017).  Characterizing spatial construction processes: Toward computational tools to understand cognition.  _Proc. 39nd Annu. Meet. Cogn. Sci. Soc_ , 6.
  * Dasgupta, Smith, Schulz, Tenenbaum, GershmanDasgupta et al. Dasgupta, I., Smith, K. A., Schulz, E., Tenenbaum, J. B., Gershman, S. J.  (2018).  _Learning to act by integrating mental simulations and physical experiments_ (Tech. Rep.).
  * Dietz, Landay, GweonDietz et al. Dietz, G., Landay, J. A., Gweon, H.  (2019).  Building blocks of computational thinking: Young children’s developing capacities for problem decomposition.  _Proc. 41st Annu. Meet. Cogn. Sci. Soc_ , 7.
  * GeffnerGeffner Geffner, H.  (2013).  Computational models of planning.  _Wiley Interdisciplinary Reviews: Cognitive Science_ , _4_(4), 341–356.
  * Hart, Nilsson, RaphaelHart et al. Hart, P., Nilsson, N., Raphael, B.  (1968).  A Formal Basis for the Heuristic Determination of Minimum Cost Paths.  _IEEE Transactions on Systems Science and Cybernetics_ , _4_(2), 100–107.
  * KirshKirsh Kirsh, D.  (1995).  The intelligent use of space.  _Artificial intelligence_ , _73_(1-2), 31–68.
  * KirshKirsh Kirsh, D.  (2009).  Problem Solving and Situated Cognition.  _The Cambridge Handbook of Situated Cognition_ , 264–306.
  * Kirsh MaglioKirsh Maglio Kirsh, D., Maglio, P.  (1994).  On Distinguishing Epistemic from Pragmatic Action.  _Cognitive Science_ , _18_(4), 513–549.
  * Maisto, Donnarumma, PezzuloMaisto et al. Maisto, D., Donnarumma, F., Pezzulo, G.  (2015).  Divide et impera: Subgoaling reduces the complexity of probabilistic inference and problem solving.  _Journal of The Royal Society Interface_ , _12_(104), 20141335.
  * McCarthy, Kirsh, FanMcCarthy et al. McCarthy, W., Kirsh, D., Fan, J.  (2020).  Learning to build physical structures better over time.  _Proc. 42nd Annu. Meet. Cogn. Sci. Soc_.
  * Newell SimonNewell Simon Newell, A., Simon, H. A.  (1972).  _Human problem solving_ (Vol. 104).  Prentice-Hall Englewood Cliffs, NJ.
  * SussmanSussman Sussman, G. J.  (1975).  _A computer model of skill acquisition_.  New York; London: American Elsevier ; Elsevier.
  * Zhang, Lerer, Sukhbaatar, Fergus, SzlamZhang et al. Zhang, A., Lerer, A., Sukhbaatar, S., Fergus, R., Szlam, A.  (2019).  Composable Planning with Attributes.  _arXiv:1803.00512 [cs]_.


# Towards Self-Attention Based Visual Navigation in the Real World

Jaime Ruiz-Serra1,*, Jack White1, Stephen Petrie1,
Tatiana Kameneva1,2 Chris McCarthy1
1Swinburne University of Technology, Australia
2Melbourne University, Australia
<EMAIL_ADDRESS>
###### Abstract

Vision guided navigation requires processing complex visual information to
inform task-orientated decisions. Applications include autonomous robots,
self-driving cars, and assistive vision for humans. A key element is the
extraction and selection of relevant features in pixel space upon which to
base action choices, for which Machine Learning techniques are well suited.
However, Deep Reinforcement Learning agents trained in simulation often
exhibit unsatisfactory results when deployed in the real-world due to
perceptual differences known as the _reality gap_. An approach that is yet to
be explored to bridge this gap is self-attention. In this paper we (1) perform
a systematic exploration of the hyperparameter space for self-attention based
navigation of 3D environments and qualitatively appraise behaviour observed
from different hyperparameter sets, including their ability to generalise; (2)
present strategies to improve the agents’ generalisation abilities and
navigation behaviour; and (3) show how models trained in simulation are
capable of processing real world images meaningfully in real time. To our
knowledge, this is the first demonstration of a self-attention based agent
successfully trained in navigating a 3D action space, using less than 4000
parameters.

##  1 Introduction

Figure 1: Trained agents are capable of selecting important features of the
environment in both simulation and the real world, in real time. Left Column:
unprocessed frames. Center Column: the $K$ most important patches overlaid on
frames. Right Column: the $K$ most important patches in isolation. Top Row:
frame from simulation training environment, $K=10$. Bottom Row: real-world
image, $K=80$.

Vision-based navigation is a challenging task that requires perceiving and
rapidly processing highly complex information to determine actions. In the
context of vision-guided robotics, visual navigation requires extracting
features of the environment that directly inform behaviour choices, and/or or
serve as direct inputs to control in order to reach an intended goal or
destination. More broadly, such vision processing may also serve to support
human activity in tele-operation contexts, as well as in assistive
technologies for human mobility.

The problem of navigation can be framed as a function that maps sensor-
acquired input information at a given time step (e.g. camera-captured pixels),
to an action choice that both progresses towards a pre-determined goal, while
also satisfying constraints such as avoiding collision, and minimising
distance travelled. This framing entails the reduction of a high-dimensional
space into a single vector of actions, which Reinforcement Learning (RL)
algorithms are particularly well suited to do. These algorithms are capable of
learning complex behaviours over many iterations of loss or fitness evaluation
and parameter adjustments, requiring a repeatable, controlled environment in
which to train. Training in simulation offers multiple advantages over
training in the real world in terms of speed, repeatability, safety, and
ability to modify the environment. Once controllers are trained or evolved,
they need to be appraised for performance—and eventually deployed—in the real
world.

The difference in complexity between simulation and real-world environments,
known in the literature as the _reality gap_ , is a major challenge that
controllers trained in simulation face when deployed in the real world [?].
The most common approaches to narrow the gap are to increase the fidelity of
the simulation environment to bring it “closer” to the real world [?; ?], and
randomising visual aspects of the simulation with the intention to have the
real world seem like just another variation of the simulation [?; ?]. The
additional computational steps required by these methods increases the time
required to train agents [?].

Biological vision employs saccades to gather information in sequence,
subsequently contrasted with (and used to update) our conceptual models of the
world [?]. This gives rise to _inattentional blindness_ , whereby humans focus
only on important parts of the visual scene, largely ignoring the rest [?].
Ignoring task-irrelevant information reduces the complexity of the inputs that
need to be processed. From this angle, instead of learning to adapt to
differences by using larger models, we can have agents learn to focus on the
most important parts of the input, which are likely to be similar across a
range of different environments (both simulation and real-world).

_Self-attention_ , a means to compute sequence representations based on
internal relationships popularised by [?], can be used to enforce an
information bottleneck to remove task-irrelevant parts from agent inputs,
mimicking inattentional blindness. Additionally, self-attention is more
parameter- and compute-efficient [?], making it more suitable for hardware-
constrained applications.

In this paper we show the potential for self-attention as a means to bridge
the reality gap for real-world navigation. Specifically, we assess the
feasibility of a simulation-trained self-attention model to generate simple
representations of real-world states that are relevant to the task of
navigation. We thus adapt the agent from [?] to the context of vision- and
depth-based navigation of 3D spaces. The agent, as in the original
implementation, is trained by means of _neuroevolution_ , a class of
evolutionary algorithms used to iteratively improve neural networks based on a
fitness score. This is possible due to the low parameter count facilitated by
self-attention.

In summary, we (1) perform a systematic exploration of the hyperparameter
space for self-attention based navigation of 3D environments and qualitatively
appraise behaviour observed from different hyperparameter sets, including
their ability to generalise; (2) present strategies to improve the agents’
generalisation abilities and navigation behaviour; and (3) show how models
trained in simulation are capable of processing real world images meaningfully
in real time. To the best of our knowledge, this is the first self-attention
based agent successfully trained in navigating a 3D action space.

##  2 Background

_Reinforcement Learning_ (RL) is a class of ML algorithms wherein agents learn
to perform actions based on the observed state of the environment they exist
in and the expected future rewards of available actions. To perform vision-
based RL, algorithms must be capable of processing images as environment
observations (i.e. high-dimensional inputs). To this end, Deep RL (DRL),
originally presented in [?], incorporates deep learning algorithms into the RL
paradigm. The most popular DRL algorithms for vision-based navigation are
model-free: value-based (Deep Q-Learning [?] and variants) or policy-based
(TRPO [?] and variants). A limitation of these algorithms is their requiring
fully-differentiable components in order to be trained using gradient descent.

The complexity of DRL models requires thousands of iterations to train them,
thus training them in real world systems is prohibitively slow. Instead, DRL
models are usually trained in simulation environments and later deployed in
the real world. This offers several advantages: training episodes can be
considerably sped up beyond real time, allowing for many training iterations
at a marginal extra cost; episodes are undertaken in a controlled, repeatable
environment; agents are not at risk of damaging the environment or themselves;
environments can be modified for different tests [?].

On the other hand, a major disadvantage of simulation environments is their
lack of fidelity in modelling the real world. This discrepancy in
observations, known as the _reality gap_ , poses a challenge for simulation-
trained models acting in the real world [?]. Increasing the fidelity of the
simulation environment is the intuitive approach [?]. Other approaches include
domain randomisation [?; ?]; abstraction of sensory inputs and actions [?];
combining simulation with off-policy data [?]; and Hebbian plasticity and
online adaptation [?]. Of relevance to our study is the approach of separating
perception and decision-making, by downsampling and encoding the input images
to a lower-dimensional latent space (perception) for use by a downstream
controller (decision-making), e.g. [?; ?; ?; ?].

Feature extraction is an essential element of vision processing. In machine
learning-driven work, the most tried and tested visual feature extraction
method are Convolutional Neural Networks, as they encode rich and complex
visual representations. Despite their history as the standard vision
processing primitive, their receptive fields do not scale well enough to model
spatially long-range dependencies in the inputs [?]. Further, the number of
parameters scales quadratically with input size, quickly increasing the
computational cost [?].

The RL agent proposed by [?] that we further develop here incorporates a
bottleneck to mimic inattentional blindness. This bottleneck is achieved by
means of SA as an importance voting mechanism on image patches and
subsequently selecting only the most important regions of the image for action
decision-making. By ignoring irrelevant parts of the input, the hypothesis is
that the agents should be more robust to variations in the environments visual
attributes and thus generalise better, albeit at a cost in performance [?].
This makes self-attention a promising method for narrowing the reality gap.
Along similar lines, [?] use a saliency filter to attenuate parts of the
images deemed less salient. [?], use a retina-inspired module before a
convolutional neural network to navigate 3D simulation environments. SA
represents a highly parameter-efficient solution that is suitable in low-
computational-resource settings, as well as evolutionary strategy training
[?].

_Neuroevolution_ algorithms apply evolutionary optimisation to neural
networks. It has been proven to be “effective in training a feature extractor”
to be used in conjunction with other ML techniques [?]. The main advantage of
evolutionary processes is that they are able to train architectures containing
non-differentiable components [?]. Additionally, as a Monte Carlo method they
are well suited to distributed computing, thus being more scalable. This is an
advantage over other existing DRL training methods.

##  3 Methodology

Our approach is centered around the self-attention agent proposed by [?],
described in more detail in this section. Their work, in a similar fashion to
[?], is limited to 2D simulation environments. To obtain results that are
relevant to our use case of real world navigation, we adapted the method for
3D navigation, trained and tested the agent in a 3D environment, and
subsequently evaluated its performance on real-world images.

###  3.1 Simulation Environment

We train the agent in _DeepMind Lab_ (DML) [?], which offers 3D environments
with differences in appearance and task goals. The agent’s task is to navigate
through a maze to reach a goal, collecting apples along the way. Rewards are
considerably sparser in DML as compared with the environments used by [?] and
[?], forcing the agent to learn temporally long-range consequences of its
actions. Agents are trained in one of NavMazeStatic01 or NavMazeRandomGoal03
environments, and tested in others as discussed in Section 3.3.

_Observation space:_ The environment generates an observation at each
timestep, in the form of a tensor $\mathbf{O}_{t}\in\mathbb{R}^{64\times
64\times C}$, with $C=3$ for RGB and $4$ for RGB-D. We train RGB and RGB-D
agents, as well as agents with depth-only observations ($C=1$) and agents with
grayscale \+ depth observations ($C=2$); and explore the differences in their
performance.

_Action space:_ For this study, we use an action space dimensionality of three
(_look left/right_ , _strafe left/right_ , _move forward/backward_), thus
reducing the agent’s parameter space and thereby facilitating the search for
an optimal set of parameters in training. Our three-dimensional action space
is larger than that of [?]. This, together with higher reward sparsity and
observation variability, represents a considerably more challenging task for
the agent to solve, bringing results closer to the ultimate goal of real-world
navigation.

_Episode length and frame skip:_ The number of observations in a training
episode is determined by the episode length, the frame rate (fps), and the
frame skip rate. The agent “sees” every fourth observation (frame skip),
holding actions for that long. We use a 60 sec training episode length at 60
fps for direct comparison with other work (e.g. [?; ?; ?]), resulting in
$(60\times 60)/4=900$ observations/episode.

_Rewards:_ Agents receive a reward of 10 points each time they reach a goal,
and 1 point for each apple collected along the way. To address the sparsity of
rewards in the environment, and with the intention to correct some of the
undesirable behaviours exhibited by agents, we conducted experiments
incorporating an exploration reward ($r_{expl}$) whereby the agent gets
rewarded each time it visits a location in the training environment for the
first time, as determined by a grid; as well as penalties (i.e. negative
rewards) each time the agent collides with a wall ($p_{col}$), as in [?].
Baseline agents are configured with $r_{expl}=0.1$ and $p_{col}=0$.

###  3.2 Self-attention Agent

The agent, introduced by [?], partitions the input images into patches and
ranks the patches by their perceived importance by means of self-attention.
All action control decisions by the agent are made based solely on the
_location_ of the $K$ most important patches within the image.

_Preprocessing and partitioning the input:_ The observations produced by the
task environment at each time step are $(64,64,C)$ pixel tensors. These values
are normalised and partitioned into patches, each of shape $(M,M,C)$, using a
sliding window method. Patches are employed in order to reduce the number of
computations performed by the agent with each observation. The number of
patches from an input image is given by
$n=(\lfloor\frac{L-M}{S}+1\rfloor)^{2}$, with input image size $L$, stride
$S$, and patch size $M$. They are subsequently flattened into
$d_{in}$-dimensional vectors and combined into a single matrix
$\mathbf{X}\in\mathbb{R}^{n\times d_{in}}$. Agents that utilise the depth
channel in observations convert depth values into disparity values (inverse of
depth) prior to partitioning into patches.

_Ranking by salience:_ The self-attention mechanism, in combination with
_softmax_ —explained in detail in [?]— acts as a voting system for the
importance of patches. At its core are two matrices of learnable parameters
$W_{k},W_{q}\in\mathbf{R}^{d_{in}\times d}$, where $d$ is the dimension of the
latent space and has an integer value of small magnitude. The voting yields an
importance vector assigning an importance score to each patch. Only the $K$
most important patches are used in later parts of the network.

_Feature retrieval:_ Having selected the $K$ most important patches by means
of self-attention, features at the patch locations can be retrieved to serve
as inputs to the controller. We follow the original agent implementation [?]
in using the _location_ of the patches on the input image only.

_Controller:_ The agent’s controller is a single-layer, 16-cell LSTM that
combines the self-attention output with its hidden state. Its output is passed
through a fully connected layer, yielding a vector of normalised action values
for the actions defined. The normalised action values are interpolated to the
action ranges and rounded to the nearest integer prior to their application to
the environment.

###  3.3 Training and Testing

The agents were trained by means of neuroevolution with the CMA-ES algorithm
[?], as in [?]. Agents were evolved over 1200 generations, with a population
of 64 members and 8 training episodes per member per iteration. To increase
the scalability and efficiency of training, we completely decoupled the CMA
population from the training task queue. Task requests, including population
member identifier and agent parameters for the given population member are
placed in a queue and undertaken by compute workers on a FIFO basis. This
makes the training more flexible and suitable for distributed computing.

Upon training, we selected the agents with best performance and tested them in
each of the DML NavMaze environments, consisting of mazes of different sizes,
color schemes and textures, where the goal may be always in the same location
(Static), or randomly placed (RandomGoal). The visual differences amongst the
environments make them good candidates to test the agents’ ability to
generalise. The agents that showed better generalisation abilities were tested
for processing real-world scenes using images and video. We show simulation
score distributions and processed real-world images for select agents in
Section 4.

##  4 Results and Discussion

All experiments involve training and testing agents with the architecture from
[?], adapted to 3D navigation. In this section, we use the term _agent_ to
refer to an instance of the self-attention agent configured by a given set of
hyperparameters. The hyperparameters within the scope of this paper are
summarised in Table 1, agent C3 being our baseline agent. We present
quantitative analysis of the learning curves of the agents and their
performance in different environments, and a qualitative assessment in pixel
space of the agents’ learnt patch selection and resultant behaviours.

We found that self-attention agents are capable of navigating 3D spaces
effectively, with very efficient training. Agents reached scores above $60$ in
NavMazeStatic01 with under $0.1\mathrm{E}9$ training steps, and were able to
navigate environments with different visual qualities to the training
environment. As shown in Figure 1, agents learn to select image patches that
are relevant to the task of navigation in both simulation environments and
real-world images.

###  4.1 Simulation Environments

Figure 2: Agent score distributions over 200 trials in each selected DML
environment. Key hyperparameters for each of the agents are listed in Table 1.
Agents marked with “*” were trained in NavMazeRandomGoal03. All other agents
were trained in NavMazeStatic01.

We tested the agents in both the training environment and other environments
with similar tasks but different visual and structural qualities. We observed
their scores, patch selection, and behaviour. Overall, agents are able to
translate the representations learnt in the training environment to other
environments. Results are shown in Figure 2.

Agent | $C$ | $M$ | $S$ | $d$ | $K$ | $r_{expl}$ | $p_{col}$
---|---|---|---|---|---|---|---
C3 (baseline) | 3 | 7 | 4 | 4 | 10 | 0.1 | 0
C4 | 4 | 7 | 4 | 4 | 10 | 0.1 | 0
C2 | 2 | 7 | 4 | 4 | 10 | 0.1 | 0
C1 | 1 | 7 | 4 | 4 | 10 | 0.1 | 0
C3-r0 | 3 | 7 | 4 | 4 | 10 | 0 | 0
C3-p0.02 | 3 | 7 | 4 | 4 | 10 | 0.1 | -0.02
M3 | 3 | 3 | 4 | 4 | 10 | 0.1 | 0
S8 | 3 | 7 | 8 | 4 | 10 | 0.1 | 0
d2 | 3 | 7 | 4 | 2 | 10 | 0.1 | 0
d12 | 3 | 7 | 4 | 12 | 10 | 0.1 | 0
K5 | 3 | 7 | 4 | 4 | 5 | 0.1 | 0
K5-r0 | 3 | 7 | 4 | 4 | 5 | 0 | 0
Table 1:  Agent hyperparameters selected for comparison. $C$: input channels,
$M$: patch size, $S$: stride, $d$: latent space dimensionality, $K$: number of
patches selected, $r_{expl}$: exploration reward, $p_{col}$: collision
penalty. More details in Sections 3.1 and 3.2. Agent names are based on
changed hyperparameters, highlighted in bold.

_Depth perception:_ Results demonstrate that adding depth to data input
enabled the agent to focus on structural characteristics of the environment
over more specific features of the DML environment such as its highly
contrasting walls/floor/sky planes. This results in more “human-like” patch
selection of apples, floor (as opposed to floor/wall boundaries), and vertical
corner edges. Agents are less distracted by the patterns on the walls and the
score panels on the bottom part of the screen. Depth-only agents ($C=1$)
proved to be competitive in generalising to other environments, both from
simpler to more complex environments and vice versa. When comparing agents
with both depth and RGB/grayscale perception ($C=4$ and $C=2$), 4-channel
agents trained in difficult environments (i.e. NavMazeRandomGoal03 which is
larger, more complex and has sparser, more randomised rewards than
NavMazeStatic01) generalise better to other environments, but 2-channel agents
trained in easier environments generalise better to difficult environments.
This may be because by removing color information, the observation
distributions are closer between environments.

_Patch overlap:_ The patch size $M$ and stride $S$ have a direct impact in the
number of trainable parameters, and therefore the complexity of training.
Smaller patches and larger strides result in less overlap between patches as
well as less parameters to be learnt. Agents with no overlap achieved scores
as high as any others, and showed better generalisation to other environments.
This may be due to the fact that no overlap prevents the selected patches to
be in clusters over a single region of the image, forcing them to be
distributed in a grid-like manner over the image.

_Latent space:_ The size of the self-attention matrices $d$ determines the
complexity of single patch representations used for importance voting. A
higher-dimensional latent space does not result in higher scores or better
generalisation.

_Patch count:_ Smaller $K$ obtains higher scores, but it appears to cause the
agent to overfit to the training environment, as generalisability is lower.
This aligns with the fact that the LSTM controller receives a smaller input.

_Exploration rewards_ $r_{expl}$ seem to help agents learn faster than those
without, with total reward plateauing at high levels about 2 times faster
during training on NavMazeStatic01 (score plots in Figure 3), and about 4
times faster during training on NavMazeRandomGoal03. This suggests that
curiosity rewards are particularly helpful in larger, more complex
environments with sparser rewards. On the other hand, agents with exploration
reward obtained lower scores overall, suggesting that exploration rewards may
be beneficial early on in the training process, but detrimental in the long
run. Exploration reward does not affect generalisability, with the exception
of RGB agents trained on NavMazeRandomGoal03. The addition of exploration
reward enhances these agents’ generalisation ability in larger levels: when
tested on NavMazeStatic02 and NavMazeRandomGoal02, K5* and C3* outperform
their r0 counterparts, as shown in Figure 2.

Agents with smaller $K$ trained quicker without exploration reward than agents
with exploration reward, suggesting limitations of the controller. Further
work on self-attention agents may focus on addressing the network’s LSTM
controller, with an emphasis on its inputs.

_Collision penalties_ $p_{col}$ hinder learning speed, overall scores, and
generalisation. Agents trained from scratch with collision penalties
successfully learn to avoid collisions with walls, but this results in
undesired “stuck in place” behaviour. Extending agent training with collision
penalties resulted in marginal improvements in training environment
performance.

Additional rewards or penalties such as the ones described above may be
helpful in curriculum learning settings, with exploration reward speeding up
the initial part of the training, and collision penalties addressing agent
limitations later on in the process.

_Training in more complex environments_ , in our case NavMazeRandomGoal03,
resulted in agents achieving better generalisation (marked “*” in Figure 2
legend). Our assertion is that the randomisation of the goal location, in
addition to the increased structural variation of the environment, resulted in
policies that relied on general environmental features more heavily, and thus
overfitted less to the environment they were trained on. This supports the
idea of using self-attention in combination with other methods such as domain
randomisation or more realistic environments to bridge the reality gap.

Figure 3: Training progress in NavMazeStatic01 from agents with different
rewards. Exploration rewards help learn faster but result in lower scores in
the long run (C3). Collision penalties address behaviour but result in lower
scores (C3-p0.02).

###  4.2 Real-world Images

We found that processing real images using our best performing agents
effectively highlights task-relevant features in the real world. Sample
results are shown in Figure 4, where it can be seen that, despite the image
being of low contrast, and of a completely different color scheme to that of
the training environment, the model is able to rank and select the most
important regions of the image. These can be further processed with other
feature retrieval methods including depth sampling or convolutions to increase
the amount of information they convey to downstream parts of the system. In
addition to this, the temporal dimension in non-static inputs (i.e. video)
increases interpretability considerably.

Worth noting is the ability to change hyperparameters (e.g. $K$) of already-
trained models at image processing time, in real time. This can be performed
adaptively by later parts of the system, increasing the expressivity of the
self-attention component. Examples of this are shown in Figure 4 (bottom two
rows).

Figure 4: Real-world images processed by the self-attention network. Agents
trained in simulation are able to select useful features from real-world
images with different color schemes and contrast levels. Patch intensities map
to their relative importance. Top: Different agents processing the same image
for comparison, with agent names. Bottom: Images processed by agent C2*, with
hyperparameters changed post training as described in the legend.

##  5 Conclusions and Future Work

In this paper, we demonstrate that self-attention agents trained in simulation
are capable of selecting relevant visual features and using them to navigate
3D maze environments, being, to our knowledge, the first to do so. The agents,
comprising less than 4000 learnable parameters, learned sensible navigation
behaviours with less than $0.1\mathrm{E}9$ training environment steps.
Furthermore, we show that the agents’ learnt patch selection can be used to
identify useful features in real-world scenes, proving to be a promising
approach to aid in bridging the reality gap.

Self-attention agents may be used in combination with other approaches from
the reality gap literature—such as more realistic simulations and domain
randomisation—and as a saliency or attention layer to be added to more complex
agent architectures. Both suggestions are to be explored in future work, along
with further agent enhancements. Specifically, depth information and/or
convolutional layers may be used in the feature retrieval part of the network,
providing richer information to the LSTM controller.

## References

  * [Beattie et al., 2016] Charles Beattie, Joel Z. Leibo, Denis Teplyashin, Tom Ward, Marcus Wainwright, Heinrich Küttler, Andrew Lefrancq, Simon Green, Víctor Valdés, Amir Sadik, Julian Schrittwieser, Keith Anderson, Sarah York, Max Cant, Adam Cain, Adrian Bolton, Stephen Gaffney, Helen King, Demis Hassabis, Shane Legg, and Stig Petersen.  DeepMind Lab, 2016.
  * [Bharadhwaj et al., 2019] Homanga Bharadhwaj, Zihan Wang, Yoshua Bengio, and Liam Paull.  A Data-Efficient Framework for Training and Sim-to-Real Transfer of Navigation Policies.  In 2019 International Conference on Robotics and Automation (ICRA), pages 782–788, May 2019.
  * [Bousmalis et al., 2018] Konstantinos Bousmalis, Alex Irpan, Paul Wohlhart, Yunfei Bai, Matthew Kelcey, Mrinal Kalakrishnan, Laura Downs, Julian Ibarz, Peter Pastor, Kurt Konolige, Sergey Levine, and Vincent Vanhoucke.  Using Simulation and Domain Adaptation to Improve Efficiency of Deep Robotic Grasping.  In Proceedings - IEEE International Conference on Robotics and Automation, pages 4243–4250, 2018.
  * [Brunner et al., 2018] Gino Brunner, Oliver Richter, Yuyi Wang, and Roger Wattenhofer.  Teaching a machine to read maps with deep reinforcement learning.  32nd AAAI Conference on Artificial Intelligence, AAAI 2018, pages 2763–2770, 2018.
  * [Gordon et al., 2019] Daniel Gordon, Abhishek Kadian, Devi Parikh, Judy Hoffman, and Dhruv Batra.  SplitNet: Sim2Sim and Task2Task transfer for embodied visual navigation.  arXiv, pages 1022–1031, 2019.
  * [Hansen, 2016] Nikolaus Hansen.  The CMA Evolution Strategy: A Tutorial, April 2016.
  * [Jakobi, 1998] Nick Jakobi.  Running across the reality gap: Octopod locomotion evolved in a minimal simulation.  Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 1468:39–58, 1998.
  * [Khetarpal and Precup, 2018] Khimya Khetarpal and Doina Precup.  Attend Before you Act: Leveraging human visual attention for continual learning, July 2018.
  * [Lehnert et al., 2019] Hans Lehnert, Maria Jose Escobar, and Mauricio Araya.  Retina-inspired Visual Module for Robot Navigation in Complex Environments.  Proceedings of the International Joint Conference on Neural Networks, 2019-July(July):1–8, 2019.
  * [Lobos-Tsunekawa et al., 2018] Kenzo Lobos-Tsunekawa, Francisco Leiva, and Javier Ruiz-Del-Solar.  Visual navigation for biped humanoid robots using deep reinforcement learning.  IEEE Robotics and Automation Letters, 3(4):3247–3254, 2018.
  * [Ma et al., 2019] Liulong Ma, Yanjie Liu, and Jiao Chen.  Using rgb image as visual input for mapless robot navigation, 2019.
  * [Mnih et al., 2013] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wierstra, and Martin Riedmiller.  Playing Atari with Deep Reinforcement Learning.  Deep Reinforcement Learning: Fundamentals, Research and Applications, 2013.
  * [Mott et al., 2019] Alex Mott, Daniel Zoran, Mike Chrzanowski, Daan Wierstra, and Danilo J. Rezende.  Towards interpretable reinforcement learning using attention augmented agents.  In Advances in Neural Information Processing Systems, volume 32, June 2019.
  * [Peng et al., 2018] Xue Bin Peng, Marcin Andrychowicz, Wojciech Zaremba, and Pieter Abbeel.  Sim-to-Real Transfer of Robotic Control with Dynamics Randomization.  In 2018 IEEE International Conference on Robotics and Automation (ICRA), pages 3803–3810, May 2018.
  * [Qiu et al., 2020] Huanneng Qiu, Matthew Garratt, David Howard, and Sreenatha Anavatti.  Towards crossing the reality gap with evolved plastic neurocontrollers.  In Proceedings of the 2020 Genetic and Evolutionary Computation Conference, GECCO ’20, pages 130–138, New York, NY, USA, June 2020. Association for Computing Machinery.
  * [Ramachandran et al., 2019] Prajit Ramachandran, Niki Parmar, Ashish Vaswani, Irwan Bello, Anselm Levskaya, and Jon Shlens.  Stand-Alone Self-Attention in Vision Models.  In Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
  * [Scheper and de Croon, 2017] Kirk Y. W. Scheper and Guido C. H. E. de Croon.  Abstraction, Sensory-Motor Coordination, and the Reality Gap in Evolutionary Robotics.  Artificial Life, 23(2):124–141, 2017.
  * [Schulman et al., 2015] John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz.  Trust Region Policy Optimization.  In Proceedings of the 32nd International Conference on Machine Learning, pages 1889–1897. PMLR, June 2015.
  * [Simons and Chabris, 1999] Daniel J Simons and Christopher F Chabris.  Gorillas in our midst: Sustained inattentional blindness for dynamic events.  Perception, 28(9):1059–74, 1999.
  * [Stein and Roy, 2018] Gregory J. Stein and Nicholas Roy.  GeneSIS-Rt: Generating Synthetic Images for Training Secondary Real-World Tasks.  In 2018 IEEE International Conference on Robotics and Automation (ICRA), pages 7151–7158, May 2018.
  * [Tang et al., 2020] Yujin Tang, Duong Nguyen, and David Ha.  Neuroevolution of Self-Interpretable Agents.  In GECCO ’20: Proceedings of the 2020 Genetic and Evolutionary Computation Conference, pages 414–424, 2020.
  * [Tobin et al., 2017] Josh Tobin, Rachel Fong, Alex Ray, Jonas Schneider, Wojciech Zaremba, and Pieter Abbeel.  Domain randomization for transferring deep neural networks from simulation to the real world.  IEEE International Conference on Intelligent Robots and Systems, 2017-Septe:23–30, 2017.
  * [Tremblay et al., 2018] Jonathan Tremblay, Aayush Prakash, David Acuna, Mark Brophy, Varun Jampani, Cem Anil, Thang To, Eric Cameracci, Shaad Boochoon, and Stan Birchfield.  Training Deep Networks with Synthetic Data: Bridging the Reality Gap by Domain Randomization.  In 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops (CVPRW), pages 1082–10828, June 2018.
  * [Vaswani et al., 2017] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Łukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  Advances in Neural Information Processing Systems, 2017-Decem(Nips):5999–6009, 2017.
  * [Verbancsics and Harguess, 2013] Phillip Verbancsics and Josh Harguess.  Generative NeuroEvolution for Deep Learning, December 2013.
  * [White et al., 2019] Jack White, Tatiana Kameneva, and Chris McCarthy.  Deep reinforcement learning for task-based feature learning in prosthetic vision.  In Proceedings of the Annual International Conference of the IEEE Engineering in Medicine and Biology Society, EMBS, pages 2809–2812, 2019.
  * [Zhang et al., 2019] Jingwei Zhang, Lei Tai, Peng Yun, Yufeng Xiong, Ming Liu, Joschka Boedecker, and Wolfram Burgard.  VR-Goggles for Robots: Real-to-Sim Domain Adaptation for Visual Control.  IEEE Robotics and Automation Letters, 4(2):1148–1155, 2019.