Estimating Map Completeness in Robot Exploration

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.

We consider an autonomous mobile robot that is exploring an unseen environment in order to obtain a full map of it. The robot is equipped with a 2D laser scanner, and it is able to build a partial grid map of the environment as it moves around. While several exploration strategy have been proposed to guide the robot in the environment, the robot should also know when to stop the exploration process. A method that decides when an exploration process should stop is called a stopping criterion. The importance of having a good stopping criterion is paramount. Indeed, the later stages of a typical exploration process often provide little contribution, and they can cause a degradation of the mapping performance, leading to map inconsistencies and unrecoverable states that invalidate the entire mapping process.

We evaluate 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. More precisely, we:

• define a stopping criterion that determines whether a partial map under scrutiny can be considered as enough explored or not,
• estimate the status of the exploration process as the percentage of the total area explored by the robot (with- out needing the knowledge of the whole environment), and
• identify the areas of the map that are of interest (if any) to progress the exploration.

Our main intuition consists in casting the assessment of the status of the exploration in a visual recognition problem. We train a deep convolutional neural network for each of the tasks of stopping the exploration run and estimate the percentage of the explored area. The stopping criterion 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. The second task, 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. For both tasks we rely on a EfficientNet B1 architecture, pre-trained on ImageNet, and fine-tuned on our dataset.

Our method is tested both online and offline by considering an extensive set of thousands of maps as acquired during exploration runs by an autonomoous robot. We show that our method is able to correctly estimate the percentage of the explored area and to stop the exploration process when the map is almost fully explored. Our method is able to save, on average, 40% of the total exploration time with respect to covering all the area of the environment. The DNN model is able to distinguish between fully-explored and partially-explored maps with an accuracy above 90%. Interestingly, we can keep the rate of false positives (i.e., maps that are considered fully explored but are not) below 2%.

The example image shows our method applied to partial maps obtained after 10, 20, 30, and 40 minutes of exploration of two environments. In the environment in the first row (a)-(d), the exploration ends after T = 70 min; with our method, we can reduce such time by 30 minutes (d). In the environment in the second row (e)-(h), the exploration is concluded after T = 90 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).

Overall, can estimate the percentage of the explored area with an error of just 4.68%, which is low and stable across all 15 test environments. The figure above shows how the average error of estimating the percentage of the area progresses during exploration runs. 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), the error 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.

Finally, we tested our method on real data collected by an autonomous robot. Despite this domain shift, our model shows robust performance by correctly classifying all the maps as not-explored. This result is particularly relevant as it shows the genralization of our results to real-world settings.