# Estimating Map Completeness in Robot Exploration

Matteo Luperto1, Marco Maria Ferrara2, Giacomo Boracchi2, and Francesco
Amigoni2 1M. Luperto is with the Dipartimento di Informatica of the Università
degli Studi di Milano, Italy<EMAIL_ADDRESS>Ferrara, G. Boracchi,
and F. Amigoni are with the Dipartimento di Elettronica, Informazione e
Bioingegneria of the Politecnico di Milano, Italy
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

In this paper, we propose a method that, given a partial grid map of an indoor
environment built by an autonomous mobile robot, estimates the amount of the
explored area represented in the map, as well as whether the uncovered part is
still worth being explored or not. Our method is based on a deep convolutional
neural network trained on data from partially explored environments with
annotations derived from the knowledge of the entire map (which is not
available when the network is used for inference). We show how such a network
can be used to define a stopping criterion to terminate the exploration
process when it is no longer adding relevant details about the environment to
the map, saving, on average, $40\%$ of the total exploration time with respect
to covering all the area of the environment.

##  I Introduction

In exploration for map building, an autonomous mobile robot builds a
representation, or map, of an initially unknown indoor environment by
iteratively performing a sequence of steps [1]. First, the robot identifies a
set of reachable candidate locations within the known portion of the
environment represented by the current map. Usually, these candidate locations
are at the boundaries, called frontiers, between known and unknown parts of
the environment. The robot then selects the most promising location to reach
to progress exploration, according to an exploration strategy. Finally, while
reaching the selected location, the robot updates its map using newly acquired
sensor data. Then, the cycle repeats.

(a) $t=$90\text{\,}\mathrm{min}$$.

(b) $T=$150\text{\,}\mathrm{min}$$.

Figure 1:  The map after $t=$90\text{\,}\mathrm{min}$$ of exploration (a)
already represents almost all of the environment (the portion of the mapped
area is $A_{t}=0.98$), except a few uninteresting corners and portions of
rooms scattered across the whole environment, highlighted in blue in (a). This
exploration run ends at $T=$150\text{\,}\mathrm{min}$$ (b) when all frontiers
have been visited. During the time interval $T-t$, the robot moves back and
forth to explore the remaining frontiers, possibly jeopardizing the whole
mapping process. Our method infers that the map in (a) is almost fully
explored and stops the exploration, reducing the total exploration time.

In some operational contexts, such as Urban Search and Rescue [2], the
exploration process stops after a given (usually not-so-long) amount of time
because the application requires to quickly provide (possibly incomplete)
information about the environment to the human rescuers. In other
applications, the exploration is stopped when the process is no longer
acquiring relevant information, for example, when no frontiers are left above
a given length [3]. A method that decides when an exploration process should
stop is called a _stopping criterion_. While the need for stopping criteria is
recognized, identifying robust stopping criteria is still an open challenge
[4], with limited research in the field [3].

The importance of having a good stopping criterion is paramount. Indeed, the
later stages of a typical exploration process often provide little
contribution to the completion of the final map, at a high cost. As noted in
[5], in some settings, up to 71% of the total exploration time is spent
covering the last 10% of the area (Fig. 1). Moreover, late–stages of the
exploration process can cause a degradation of the mapping performance,
leading to map inconsistencies and unrecoverable states that invalidate the
entire mapping process [3].

In this paper, we present a method that evaluates the partial map of an
environment and estimates the advancement of the exploration process. Our
method processes partial 2D grid maps obtained during exploration as images,
using a Convolutional Neural Network (CNN). We exploit the fact that assessing
the degree of completeness of a map is a task well suited for CNNs, as maps of
indoor environments exhibit very peculiar patterns that allow humans to
correctly assess – in most cases – whether there is still some potentially
large area to explore or not. For example, looking at the partial map of Fig.
1a, it is intuitive to say that it represents the environment almost
completely. Our network, which is trained on an extensive dataset of maps
obtained during the exploration of indoor environments, is used to:

  * •

defining a stopping criterion that determines whether a partial map under
scrutiny can be considered as enough explored or not,

  * •

estimating the status of the exploration process as the percentage of the
total area explored by the robot (without needing the knowledge of the whole
environment), and

  * •

identifying the areas of the map that are of interest (if any) to progress the
exploration.

Results show that employing our method can significantly reduce the
exploration time while ensuring a good level of completeness of the map. As
our method is based on 2D grid maps, it is agnostic of the exploration
strategy employed to build the map and can be used to provide additional
awareness to any exploration strategy. At the same time, we do not require any
previous knowledge or priors on the environment that is explored.

##  II Related Work

While the generic goal of an autonomous mobile robot exploring initially
unknown (static) environments is to obtain complete maps of the environments,
there are often additional desiderata to address, such as maximizing the
explored area within a time budget [6] or maximizing the quality of the
reconstructed map [7]. In this context, the main (and most studied) issue a
robot faces is to decide which is the next location to reach to progress the
exploration [8, 9]. Over the years, different approaches to exploration have
been proposed [10]. A common one is to identify a few candidate locations at
the boundaries between the explored and unexplored portions of the
environment, and to select the most promising location to reach according to
some exploration strategy. These boundaries are defined as _frontiers_ , and
their ranking is commonly based on their expected _information gain_ , i.e.,
an estimate of the amount of knowledge to be acquired by the robot when
visiting the locations, and on their distance from the current location of the
robot [11, 8, 12].

Some works highlight that deciding when to stop exploration is a particularly
relevant, yet under-investigated and still open, problem [4, 3, 7]. In [3] an
overview of the stopping criteria that are commonly used to end exploration is
presented, as well as a discussion of their limitations. A straightforward
criterion is to stop the exploration process when a time budget is reached
[13]; however, the time budget should be tuned for each environment and
exploration strategy, and there is no guarantee that the map obtained by the
robot when the time budget expires is complete.

Other works end the exploration when no candidate location is left [14]. A
positive aspect of this stopping criterion is that it guarantees that the map
is complete; on the negative side, this completeness is obtained at the
expense of a long exploration time, where most of the time is spent reaching
far–away uninteresting locations that have been left behind in the initial
part of exploration [5, 15]. This issue is often the result of fast
exploration strategies that prioritize reaching frontiers with large
information gains and, consequently, encourage aggressive choices to quickly
explore unobserved parts of the environments [16, 17, 18, 15]. As pointed out
in [5], these strategies allow a robot to make greedy choices to map most of
the environment in a short time but, from that moment on, the robot can spend
up to $70\%$ of the total time in exploring marginal details of the
environment that have been left behind, but that constitute about $10\%$ of
the area of the environment. An example is shown in Fig. 1.

Some works assess the percentage of the total explored area to stop the
exploration [6]. However, this criterion requires either the a priori
knowledge of the size of the map or a way to infer it. Moreover, the fact that
most of the area is already explored does not guarantee that all the areas of
interest in the environment have been mapped. In [19], the authors apply a
strategy based on rapidly-exploring random trees (RRT) to exploration, using
the size of the RRT as a stopping criterion. An alternative approach is to
compare maps acquired at different times (e.g. after 10 minutes) and measure
changes in the map[20]. When the two maps are identical, the robot did not
observe any new areas during the interval, and the exploration can be stopped.
However, this stopping criterion does not ensure the successful completion of
the exploration task, in particular when the robot travels between two
far–away frontiers.

Other works, like [21], are based on Information Theory and consider the map
entropy as a stopping criterion: if the map entropy is below a given
threshold, or if the map entropy increases without adding new area, the
exploration can be stopped. A similar approach is applied in [22], where
entropy saturation in the current map is considered as a stopping criterion.
In [9], these methods are used to stop the exploration process and mapping in
dynamic environments. However, also these techniques do not guarantee that the
exploration task is really completed, and often require additional knowledge
about the environment.

The work of [3] proposed to use the Theory of Optimal Experimental Design
(TOED) – which estimates the utility of a variable by a statistical analysis
of its variance – to overcome some of the above limitations, defining a
stopping criterion that considers the completion of the task assigned to the
robot. Authors in [3] use a D-optimality criterion, a statistical measure of
the map utility, to stop the exploration when no new knowledge is added to the
map. However, such a stopping criterion is intertwined with an exploration
process that uses TOED, making the approach difficult to generalize to other
exploration strategies, for example, those that are frontier-based.

Very recently, the work of [23] used a DNN, called _Floorist_ , to predict
unseen walls from partial maps to improve exploration performance. Differently
from us, such a network is not used to infer knowledge about the status of the
exploration run. To the best of our knowledge, we are the first to leverage
the visual representation of the current explored map to assess whether the
remaining unexplored part of the environment is worth exploring or not. We
address this decision by training a deep CNN in a supervised manner on a
dataset of images generated during simulated robot explorations. The resulting
solution is very practical, as it does not need any previous knowledge of the
environment being explored, it is not task–dependent, and it is agnostic of
the exploration strategy employed to build the maps.

##  III The Problem

In this paper, we propose a method that evaluates the current status of the
exploration process performed by an autonomous mobile robot in an initially
unknown environment. We consider a frontier-based exploration strategy [11].
However, our method relies only on an image depicting the current grid map
built by the robot and could be used with any exploration strategy. Our
approach consists of two aspects:

  * ($a$)

Classifying a partial map as sufficient (or not) to represent the environment,
thus defining the stopping criterion.

  * ($b$)

Estimating the portion of the area of an environment that is represented in
the current partial map.

Our solution can significantly improve the awareness of the robot about the
map during exploration. While ($a$) can be used to stop the exploration
earlier than conventional methods, thus saving time (Section IV-D), ($b$) can
be used by a high-level decision-making process of single- and multi-robot
systems, to plan the robot activity.

We train a deep convolutional neural network for each of the two tasks ($a$)
and ($b$). The stopping criterion ($a$) is modeled as a visual recognition
problem where the classification task is to distinguish between maps that are
not-explored yet from those that are sufficiently explored. The first class
contains maps that a human (who knows the full map of the environment) would
consider still to be explored, typically because of missing areas that are of
interest like one or more rooms that have not been mapped. The second class
contains maps that a human would consider complete enough to represent the
full environment. In this second case, some small parts of the environments
(like corners) may not be entirely mapped yet, but such parts are not so
relevant. An example of such an explored map can be seen in Fig. 1a. The
second task ($b$), which is estimating the portion of the area already
explored, is modeled as a regression problem using the CNN backbone adopted
for solving the first task.

The input for our method is a partial grid map $M_{t}$ built up to time $t$,
where each cell can have three possible values: free (white), obstacle
(black), or unknown (grey). In this sense, our method can be applied to any
grid map $M_{t}$ regardless of how it has been obtained.

Formally, given an autonomous mobile robot that explores an initially unknown
environment, we indicate with $A_{t}\in[0,1]$ the actual portion of the area
that is covered in the current map $M_{t}$ at time $t$, and with
$\hat{A}_{t}\in[0,1]$ the predicted portion of the explored area that is
returned by our method. To formulate our problem, consider an exploration
process that takes $T$ time steps to obtain a complete map $M_{T}=M$ (namely,
$M_{T}$ is a map for which $A_{T}=1$). An oracle with full knowledge of the
complete map $M$ could stop the exploration run at time $\bar{t}\leq T$ when
all the relevant knowledge about the environment is contained in the map
$M_{\bar{t}}$, namely when $M_{\bar{t}}\approx M$. Our method, without knowing
$M$, defines a stopping criterion that estimates the timestamp $\hat{t}\leq T$
when the exploration can be interrupted and for which $M_{\hat{t}}\approx M$.
Note that different partial maps $M_{t}$ with the same portion of the explored
area $A_{t}$ can be considered as adequately representing the whole
environment or not according to how the unexplored portion of the area is
distributed across the space (e.g., spread in many corners or concentrated in
an unexplored room).

To solve the task ($a$) above, the stopping criterion, our method attempts to
identify the first map classified as explored to minimize the normalized time
error $err_{t}=|\bar{t}-\hat{t}|/T$. Note that our goal is to avoid cases
where the stopping criterion is triggered too soon, namely when
$\hat{t}<\bar{t}$, to avoid missing some interesting parts of the map. At the
same time, triggering the stopping criterion at a time $\hat{t}>\bar{t}$ is
less critical, as it only reduces the amount of time saved without affecting
relevant knowledge.

To solve the second task ($b$), explored area estimation, the goal is to
reduce the area estimation error $err_{A}=|A_{t}-\hat{A}_{t}|$.

##  IV The Proposed Solution

###  IV-A Input Definition and CNN Models

Our main intuition consists in casting the assessment of the status of the
exploration in a visual recognition problem. There are two arguments
supporting our choice. First of all, maps of indoor environments exhibit very
peculiar patterns that allow humans to correctly assess – in most cases –
whether there is still some potentially large area to explore or not, which is
the case when the unexplored areas are little, sparse, or in regions where it
is not possible to have another room (e.g., considering the adjacent explored
regions). Second, tackling the problem from a visual recognition perspective
allows us to leverage deep learning models, and in particular Convolutional
Neural Networks (CNNs), which are very powerful also considering pre-trained
architectures.

The first step of our solution consists of creating an image $I_{t}$
associated with a partial map $M_{t}$. This is rather straightforward as the
maps $M_{t}$ are already defined over a grid and thus can be easily centred,
scaled, and resized into a $500\times 500$ pixels grayscale image. Each pixel
can take only 3 different values, 0 (black) for obstacles, 1 (white) for free
areas, and 0.5 (grey) for unexplored areas (see Fig. 2).

To solve the classification ($a$) and explored area estimation ($b$) tasks
previously described, we train two different CNNs, which however share the
vast majority of their layers and differ only for their output layers, as they
address different tasks (classification and regression). In particular, the
binary classification network $\mathcal{C}$ has as output a dense layer with
two neurons (corresponding to the explored and not-explored classes) with a
softmax activation function. We use a threshold $\theta$ to distinguish
between the two classes. This network is trained by minimizing the binary
cross-entropy as a loss function. The estimation network $\mathcal{R}$ has a
single output neuron with a ReLU activation function and is trained to
minimize the MSE. The feature extraction component of the network is from the
EfficientNet B1 [24] pre-trained on ImageNet [25] and when training both
$\mathcal{C}$ and $\mathcal{R}$ we perform transfer learning by freezing all
the parameters of the first 200 layers. We selected the EfficientNet B1 model
as a good tradeoff between accuracy and computational complexity (enabling
timely inference even on a CPU), even though it is possible to consider other
backbone networks.

###  IV-B Datasets

To train and test our models, we use a set of partial maps $M_{t}$ collected
at different exploration stages, each one paired with the corresponding label
(explored or not-explored) and the percentage of explored area $A_{t}$.

The partial maps are acquired incrementally during the robot explorations
performed for a previous work [20, 26], where we collected over $20,000$
partial maps at different stages of exploration from 100 different large–scale
indoor environments. All the maps in our dataset are free from clutter (e.g.,
objects, furniture, …). Every environment is autonomously explored multiple
times by a simulated robot using the method of [11]; in each run, due to
simulated noise in perception, the robot makes different choices during
exploration, follows different trajectories, and ultimately builds different
maps. During exploration, partial maps of the environments are saved every 10
minutes. The number of runs for each environment depends on the complexity of
the environment; on average, we collected $36$ runs for each environment. See
[20, 26] for further details.

We automatically label each partial map $M_{t}$ as explored and not-explored
using a rule–based approach, which employs the full map $M$ of the environment
as a reference.

(a) not-explored
$A_{t}=0.77$.

(b) explored
$A_{t}=0.99$.

(c) Complete map.

Figure 2: Examples of partial maps and labels from our dataset.

First, for each partial map $M_{t}$, we compute the portion $A_{t}$ of the
explored area by comparing $M_{t}$ with the complete map $M$ of the
corresponding environment. When $A_{t}$ is smaller than a threshold
$\alpha=0.7$, the map is safely labeled as not-explored. The remaining partial
maps (having less than $30\%$ of the area unexplored) can be either labeled as
explored or not depending on the spatial distribution of the unexplored
pixels. More precisely, if the unexplored area is scattered in multiple small
locations across the environment, as in the example of Fig. 1a, the map is
considered explored. Instead, if there is a large unexplored area, like a full
unexplored room, the map is labeled as not-explored. To distinguish between
the two cases automatically during the training set preparation procedure, we
cluster the unexplored cells in the partial map $M_{t}$ using DBSCAN [27]. If
the unexplored area corresponding to the largest cluster is greater than a
threshold $\beta=$1\text{\,}{\mathrm{m}}^{2}$$, the map is labeled as not-
explored; otherwise, we consider it explored. We have validated the
correctness of the automated labeling process by visually inspecting its
results. Examples of maps belonging to the two classes are shown in Fig. 2.

Figure 3:  Incremental examples of our method applied to partial maps obtained
after 10, 20, 30, and 40 minutes of exploration of two environments, from
batch-wise assessment. In the environment in the first row (a)-(d), the
exploration with the baseline stopping criterion ends after
$T=$70\text{\,}\mathrm{min}$$; with our method, we can reduce such time by 30
minutes (d). In the environment in the second row (e)-(h), the exploration
with the baseline stopping criterion is concluded after
$T=$90\text{\,}\mathrm{min}$$; we reduce such time by 50 minutes (h). The
areas highlighted in the partial maps are the locations that the neural
network of our method identifies as relevant to make its prediction (red and
blue denotes the most and the least relevant regions, respectively).

###  IV-C Model Training

The environments in the dataset are split into the training, validation, and
test set in a $70:15:15$ ratio. To artificially increase the size of our
training and validation sets and lower the risk of overfitting, we use image
augmentation by changing the orientation and zoom of the original images. We
use a batch size of $8$ and we train the model for 24 epochs, using a learning
rate of $1\cdot e^{-4}$ and the Adam optimizer [28].

###  IV-D Stopping Criterion

Our stopping criterion is triggered when a partial map obtained during the
exploration process is labeled as explored by our model. A more conservative
approach can be developed when different factors are considered, for example
when multiple consecutive partial maps are labeled as explored or
$\hat{A}_{t}$ is above a threshold. In this sense, the estimated percentage of
the explored area can be exploited to inform the exploration strategy as
discussed in Section I.

An additional benefit of our method is that we can leverage saliency maps on
the trained CNN classifier to design new exploration strategies. Saliency
maps, like Grad-CAM [29], are explainability techniques that provide, for each
input image, a heatmap that highlights which regions have primarily influenced
the network to decide a specific class. Therefore, saliency maps associated
with the class not-explored can suggest which region to prioritize in the
exploration, as shown in Fig. 3. However, the investigation of novel
exploration strategies based on the returned exploration percentage and the
saliency maps is left for future work.

##  V Experimental Evaluation

In this section, we first assess the performance of using our CNN
$\mathcal{C}$ for classifying maps in explored / not-explored (Section V-A),
as well as the corresponding exploration time saved by adopting our stopping
criterion (Section V-B). We then evaluate the performance of our CNN
$\mathcal{R}$ in estimating the portion of area explored (Section V-C).
Moreover, we show some qualitative results that give insights into how our
method works (Section V-D), and we discuss how our method can be applied to
data obtained from real-world environments (Section V-E).

Our evaluation is performed by using a set of maps obtained by the incremental
exploration of indoor environments as explained in Section IV-B. The
environments considered for evaluation have not been used for training and are
of different sizes and shapes to represent all possible types of environments.
They vary from small-scale environments with less than 10 rooms and smaller
than $100\text{\,}{\mathrm{m}}^{2}$ to large-scale environments with more than
100 rooms covering more than $10\,000\text{\,}{\mathrm{m}}^{2}$. To assess the
benefits of our approach, we run both a batch-wise (B) and an online (O)
assessment.

The _batch-wise_ evaluation allows us to understand the performance of the
proposed solution when processing maps that are visually different from each
other, thus ensuring the generalization capabilities of our solution. Batch-
wise evaluation is performed over a test set containing 3009 maps obtained
from 15 environments. Overall, we performed 613 robot exploration runs; during
each run, every 10 minutes, a snapshot of the current map of the environment
was saved. The time interval between two snapshots ensures that two
consecutive maps obtained by the robot are significantly different, as can be
seen in the example of Fig. 3, where maps obtained in two different robot runs
are shown.

The _online_ evaluation aims at assessing the benefits of using our method
during the exploration when the robot frequently decides whether to continue
exploring, based on its current map. To replicate this setting, we consider
maps that are collected during an exploration run at a higher frequency,
namely every $30\text{\,}\mathrm{s}$. We consider 10 environments and we
perform 5 exploration runs in each environment, for a total of 50, obtaining
2255 maps. Note that online assessment cannot be used for a fair evaluation of
the map classification performance, as consecutive maps are very similar, due
to the higher sampling frequency. Our classifier can easily distinguish that
all maps obtained during the early (late) stages of explorations are
unexplored (explored), resulting in an optimistic performance assessment. At
the same time, batch evaluation cannot provide a precise estimate of the
stopping criterion, due to the interval of time spent between the acquisition
of two maps.

All exploration runs of our experimental evaluation continue until a
_baseline_ stopping criterion is met, which consists of ending the exploration
at time $T$ when two partial maps, obtained at a time difference of
$10\text{\,}\mathrm{min}$, are similar enough. We measure map similarity by
the vector norm of the difference between the two images, as in [20]. We
manually inspected all exploration runs to ensure that the baseline stopping
criterion is triggered only when the environment is fully explored; if the
baseline stopping criterion is triggered too early, the run is removed and
another run is performed. Note that this baseline stopping criterion is more
efficient than others considered in the literature. As an example, we do not
require the robot to visit all of the remaining frontiers, as in [14]: when
two partial maps are similar enough and the environment is considered as fully
explored according to manual inspection, the baseline exploration criterion is
triggered even when uninteresting frontiers are still present in the
environment. We do not consider other baseline stopping criteria as they
either achieve worse performance (e.g., they require a large time budget to
guarantee that the full environment is mapped, as in [13]) or require the
robot to follow a specific exploration strategy (e.g., [3]).

We analyze the impact of varying the threshold $\theta$ for classifying a map
as explored or not (Section IV-A). We use a value of $\theta=0.5$ as a
reference and we also present results with a more conservative parameter value
$\theta=0.8$, which reduces the number of partial maps that are wrongly
considered as explored.

The training and testing of our CNNs are performed on a computer with an i7
3770k CPU, 16 GB RAM, and RTX 2070 GPU. The task of evaluating the status of
the exploration process from a partial map requires less than
$0.1\text{\,}\mathrm{s}$ and can be performed online. Further experimental
results and details are available in our online
repository***https://aislabunimi.github.io/explore-stop/. Since partial maps
$M_{t}$ need to be processed at a relatively low frequency, and since the
EfficientNetB1 is a lightweight network, our method can be directly executed
on a CPU with an inference time of less than $4\text{\,}\mathrm{s}$ [24], thus
not requiring robots to be equipped with a GPU.

Figure 4: The error in predicting the percentage of explored area while the
percentage of the area increases. The standard deviation is in light blue.
Figure 5: Examples of real-world maps, all labeled as not-explored. Our method
can highlight the parts relevant to explore as well as predict the explored
area $\hat{A}$.

###  V-A Map Classification Performance

We indicate as a True Explored (True Not-Explored) or TE (TN) the percentage
of test maps correctly classified as explored (not-explored), and as False
Explored (False Not-Explored), or FE (FN), the classification errors. We
report accuracy (A), precision (P), and recall (R) of the classification.

Table I shows the results for both the batch and online evaluation. For the
batch evaluation (B) with $\theta=0.5$, the accuracy A is 92.9%, and only
1.76% of the examples are false positives FE. Minimizing FE is particularly
important as a map that is wrongly considered as explored (false positives,
FE) can result in loss of relevant information in the map. In contrast, FNs
are less harmful, as it is acceptable to consider as not finished the
exploration of an actually explored map. However, in our experiments, false
positives FE have a minimal impact on the performance metric; a map wrongly
labeled as explored covers, on average, 2.51% less area than the first truly
explored map obtained in the same run. Increasing $\theta$ to $0.8$ further
reduces FE errors, at the cost of slightly reducing the value of TE. To
evaluate the effects, we manually inspect all 21 false positives FE with
$\theta=0.8$. They come from 15 of the 613 runs and refer to 7 of the 15
environments, indicating that some features of the environment can lead to an
FE. In fact, in all cases, the FE is caused by an entire room that is missing
from the map, without any single beam of the robot’s lidar entering its door.
Similar remarks can be made by looking at the metrics computed on the maps
used for the online evaluation O.

| $\theta$ | TE (%) | FE (%) | TN (%) | FN (%) | A | P | R
---|---|---|---|---|---|---|---|---
B | 0.5 | 1472 (48.91) | 53 (1.76) | 1324 (44.00) | 160 (5.31) | 0.92 | 0.97 | 0.91
0.8 | 1376 (45.73) | 21 (0.70) | 1352 (44.93) | 260 (8.60) | 0.91 | 0.99 | 0.84
O | 0.5 | 970 (43.00) | 48 (2.12) | 1116 (49.49) | 121 (5.37) | 0.93 | 0.95 | 0.89
0.8 | 926 (41.06) | 28 (1.24) | 1136 (50.38) | 165 (7.32) | 0.91 | 0.97 | 0.85

TABLE I: Map classification as (not)-explored during batch (B) or online (O)
evaluation.

###  V-B Stopping Criterion Evaluation

To assess the effectiveness of our stopping criterion (with $\theta=0.5$),
which stops the exploration when a partial map $M_{t}$ is labeled as explored,
we compute the percentage of the time saved compared to an exploration ending
with the baseline stopping criterion $\Delta\hat{t}=|T-\hat{t}|/T$, as well as
the average of $\Delta\hat{t}$ across all runs in all environments. Table II
(left) shows the results of the batch evaluation, averaged across all runs for
each test environment. Our stopping criterion can reduce the total exploration
time (against the baseline) by 31.62%, on average. Note how our performance is
close to those of an ideal stopping criterion (as defined in Section III),
which for our test environments of the batch evaluation has an average time
saved of $\Delta\bar{t}=|T-\bar{t}|/T=33.46\%$. As a consequence, $err_{t}$ of
Section III is small, under $2\%$.

While already promising, we emphasize that the batch evaluation reported in
Table II (left) provides a rough estimation of the actual performance of our
stopping criterion, as the test dataset for B contains maps that are saved
every 10 minutes during a run. Indeed, during an exploration run, it is likely
that the stopping criterion should be triggered at a time that lies within the
10-minute interval.

Results on the online settings, where maps are saved every 30 seconds during
each run, provide a more realistic evaluation of the speed up enabled by our
stopping criterion, which can save about $40\%$ of exploration time, and are
reported in Table II (right). This significant decrease in the exploration
time comes at the small cost of stopping the exploration when less than 1% of
the total area of the environment is still to be mapped. Remarkably, our
stopping criterion is triggered in all runs at the same time as the ideal
stopping criterion $\bar{t}$, thus having a $err_{t}=|\bar{t}-\hat{t}|/T=0$. A
more conservative $\theta=0.8$ result in $\Delta\bar{t}=35\%$ and
$err_{t}=1.92\%$.

envs # runs $\Delta\hat{t}$ $err_{A}$ b1 41 43.54% 4.57% b2 36 19.57% 4.40% b3
43 41.23% 5.04% b4 44 29.09% 3.70% b5 39 48.71% 3.60% b6 30 24.16% 5.90% b7 40
24.40% 4.40% b8 47 31.48% 4.50% b9 39 50.00% 5.30% b10 46 14.40% 7.03% b11 52
21.20% 7.80% b12 36 27.00% 2.20% b13 34 23.77% 5.40% b14 56 48.21% 2.20% b15
30 27.63% 4.10% all 613 31.62% 4.68% envs # runs $\Delta\hat{t}$ o1 5 29.8% o2
5 59% o3 5 40.69% o4 5 31.3% o5 5 37% o6 5 34% o7 5 36% o8 5 26.88% o9 5
36.83% o10 5 41.17% all 50 37.37%

TABLE II: Saved time with our stopping criterion and error in predicting the
explored area for each environment of the batch (B, left) and online (O,
right) evaluation.

###  V-C Map Completion Percentage Prediction

The fourth column of Table II (left) reports the average error $err_{A}$ in
estimating the area covered by the map $M_{t}$ (Section III). Overall, we
observe an average value of $err_{A}=4.68\%$, which is low and stable across
all 15 test environments. To enable a fair comparison, we report only the data
collected with the batch evaluation as, during the late stages of the online
evaluation, we typically have multiple almost-complete maps which are
correctly identified by our method, thus overestimating its performance.

Fig. 4 shows how the average $err_{A}$ progresses during an exploration run.
While at the beginning of the exploration, the error is higher (as the portion
of the map known to the robot is too little to make an accurate estimation),
$err_{A}$ becomes stable and under $10\%$ when half or more of the environment
is explored. Overall, our method can provide a reliable estimate of the amount
of the explored area represented in a map.

###  V-D Qualitative Evaluation

Fig. 3 shows two examples of maps that are incrementally obtained during
exploration runs from the batch evaluation B, as processed by our framework.
Figs. 3(a-c) and Figs. 3(e-g) show how saliency maps from Grad-CAM can
identify relevant areas to be explored. Figs. 3d and 3h show the maps when the
stopping criterion is triggered. The maps are correctly considered as
complete, 30 and 50 minutes before the actual end of the exploration runs when
using the baseline stopping criterion, thus saving $\approx 40\%$ of the time.
Also, our method can robustly predict the percentage of the explored area,
increasing the accuracy of the estimate as the exploration progresses.

###  V-E Real-World Maps

As our method uses simulated and empty maps for training, we run the following
test to assess whether some domain adaptation technique is needed when
adopting it in real-world maps acquired in cluttered environments. More
precisely, we test our solution on 64 maps of real-world environments. 54 maps
are obtained during the incremental mapping process of 3 real-world
environments, as recorded in the publicly-available dataset of [30]. The
remaining 10 maps are obtained during the frontier-based exploration process
of a large-scale real-world environment from Matterport [31]. We label all the
64 maps as not-explored by a visual inspection, as in all these maps some
relevant portions of the environments are not yet mapped by the robot.

We remark that these maps are significantly different from those used to train
our model, which are obtained in empty environments without clutter. Despite
this domain shift, our model shows robust performance by correctly classifying
all the maps as not-explored. Fig. 5 shows Grad-CAMs for four examples,
highlighting how in all cases our model can accurately identify what is still
left to explore, while also estimating the explored area $\hat{A}$. As we do
not know the actual area $A$ of these environments, we cannot compute
$err_{A}$. Still, we can observe how in all 64 maps our method correctly
highlights the parts of the environments that are relevant to explore and
provides a plausible monotonically increasing estimate of $\hat{A}$.

##  VI Conclusion

In this work, we have presented a method to increase the awareness of an
autonomous mobile robot during the process of exploration for map building of
unknown environments. Our method, given the partial grid map of an
environment, provides a reliable estimate of the explored area and predicts if
the exploration run can be stopped (or not) because the map contains all the
relevant knowledge about the environment (or not). Results show that we reduce
the total time required for exploration up to $40\%$.

Future work involves using the output of our method to inform exploration
strategies, improving the quality of the resulting map in tasks like Active
SLAM, and using the estimate $\hat{A}$ to support the exploration process with
a time budget, e.g., by switching between different strategies [32]. In
general, our method can be used to define different stopping criteria that can
be used in conjunction with different desiderata of the exploration process.
We will also investigate how a similar pipeline can be applied to other
spatial representation methods, such as 3D maps and Truncated Signed Distance
Fields maps.

## References

  * [1] S. Thrun, “Robotic mapping: A survey,” in _Exploring Artificial Intelligence in the New Millenium_ , 2002, pp. 1–35.
  * [2] Y. Liu and G. Nejat, “Robotic urban search and rescue: A survey from the control perspective,” _J Intell Robot Syst_ , vol. 72, no. 2, pp. 147–165, 2013.
  * [3] J. Placed and J. Castellanos, “Enough is enough: Towards autonomous uncertainty-driven stopping criteria,” _Proc. IAV_ , 2022.
  * [4] C. Cadena, L. Carlone, H. Carrillo, Y. Latif, D. Scaramuzza, J. Neira, I. Reid, and J. Leonard, “Past, present, and future of simultaneous localization and mapping: Toward the robust-perception age,” _IEEE T Robot_ , vol. 32, no. 6, pp. 1309–1332, 2016.
  * [5] L. Ericson, D. Duberg, and P. Jensfelt, “Understanding greediness in map-predictive exploration planning,” in _Proc. ECMR_ , 2021, pp. 1–7.
  * [6] F. Amigoni, A. Quattrini Li, and D. Holz, “Evaluating the impact of perception and decision timing on autonomous robotic exploration,” in _Proc. ECMR_ , 2013, pp. 68–73.
  * [7] J. Placed, J. Strader, H. Carrillo, N. Atanasov, V. Indelman, L. Carlone, and J. A. Castellanos, “A survey on active simultaneous localization and mapping: State of the art and new frontiers,” _IEEE T Robot_ , vol. 39, no. 3, 2023.
  * [8] I. Lluvia, E. Lazkano, and A. Ansuategi, “Active mapping and robot exploration: A survey,” _Sensors_ , vol. 21, no. 7, p. 2445, 2021.
  * [9] C. Stachniss and W. Burgard, “Mobile robot mapping and localization in non-static environments,” in _Proc. AAAI_ , 2005, pp. 1324–1329.
  * [10] C. Stachniss, _Robotic mapping and exploration_. Springer, 2009, vol. 55.
  * [11] B. Yamauchi, “A frontier-based approach for autonomous exploration,” in _Proc. CIRA_ , 1997, pp. 146–151.
  * [12] F. Amigoni, J. Banfi, and N. Basilico, “Multirobot exploration of communication-restricted environments: A survey,” _IEEE Intell Syst_ , vol. 32, no. 6, pp. 48–57, 2017.
  * [13] C. Leung, S. Huang, and G. Dissanayake, “Active slam in structured environments,” in _Proc ICRA_ , 2008, pp. 1898–1903.
  * [14] B. Yamauchi, A. Schultz, and W. Adams, “Integrating exploration and localization for mobile robots,” _Adapt Behav_ , vol. 7, no. 2, pp. 217–229, 1999.
  * [15] M. Luperto, M. Antonazzi, F. Amigoni, and N. A. Borghese, “Robot exploration of indoor environments using incomplete and inaccurate prior knowledge,” _Robot Auton Syst_ , vol. 133, 2020.
  * [16] M. Luperto, L. Fochetta, and F. Amigoni, “Exploration of indoor environments through predicting the layout of partially observed rooms,” in _Proc. AAMAS_ , 2021, pp. 836–843.
  * [17] Y. Katsumata, A. Kanechika, A. Taniguchi, L. El Hafi, Y. Hagiwara, and T. Taniguchi, “Map completion from partial observation using the global structure of multiple environmental maps,” _Adv Robot_ , vol. 36, no. 5-6, pp. 279–290, 2022.
  * [18] R. Shrestha, F.-P. Tian, W. Feng, P. Tan, and R. Vaughan, “Learned map prediction for enhanced mobile robot exploration,” in _Proc. ICRA_ , 2019, pp. 1197–1204.
  * [19] A. Bircher, M. Kamel, K. Alexis, H. Oleynikova, and R. Siegwart, “Receding horizon path planning for 3d exploration and surface inspection,” _Auton Robots_ , vol. 42, pp. 291–306, 2018.
  * [20] F. Amigoni, V. Castelli, and M. Luperto, “Improving repeatability of experiments by automatic evaluation of slam algorithms,” in _Proc. IROS_ , 2018, pp. 7237–7243.
  * [21] C. Stachniss and W. Burgard, “Exploring unknown environments with mobile robots using coverage maps,” in _Proc. IJCAI_ , 2003, pp. 1127–1134.
  * [22] M. Ghaffari Jadidi, J. Valls Miro, and G. Dissanayake, “Sampling-based incremental information gathering with applications to robotic exploration and environmental monitoring,” _Int J Robot Res_ , vol. 38, no. 6, pp. 658–685, 2019.
  * [23] L. Ericson and P. Jensfelt, “Beyond the frontier: Predicting unseen walls from occupancy grids by learning from floor plans,” _IEEE RAL_ , 2024.
  * [24] M. Tan and Q. Le, “Efficientnet: Rethinking model scaling for convolutional neural networks,” in _Proc. ICML_ , 2019, pp. 6105–6114.
  * [25] J. Deng, W. Dong, R. Socher, L.-J. Li, K. Li, and L. Fei-Fei, “Imagenet: A large-scale hierarchical image database,” in _Proc. CVPR_ , 2009, pp. 248–255.
  * [26] M. Luperto, V. Castelli, and F. Amigoni, “Predicting performance of slam algorithms,” _arXiv preprint arXiv:2109.02329_ , 2021.
  * [27] M. Ester, H.-P. Kriegel, J. Sander, and X. Xu, “A density-based algorithm for discovering clusters in large spatial databases with noise,” in _Proc. KDD_ , 1996, pp. 226–231.
  * [28] D. P. Kingma and J. Ba, “Adam: A method for stochastic optimization,” _arXiv preprint arXiv:1412.6980_ , 2014.
  * [29] R. Selvaraju, M. Cogswell, A. Das, R. Vedantam, D. Parikh, and D. Batra, “Grad-cam: Visual explanations from deep networks via gradient-based localization,” in _Proc. ICCV_ , 2017, pp. 618–626.
  * [30] A. Howard and N. Roy, “The robotics data set repository (Radish),” 2003. [Online]. Available: http://radish.sourceforge.net/
  * [31] A. Chang, A. Dai, T. Funkhouser, M. Halber, M. Nießner, M. Savva, S. Song, A. Zeng, and Y. Zhang, “Matterport3D: Learning from RGB-D data in indoor environments,” _arXiv preprint arXiv:1709.06158_ , 2017.
  * [32] F. Amigoni, J. Banfi, A. Longoni, and M. Luperto, “Online switch of communication modalities for efficient multirobot exploration,” in _Proc. ECMR_ , 2017, pp. 1–6.