# Entropy-Based Multirobot Active SLAM11footnotemark: 1

Muhammad Farhan Ahmed<EMAIL_ADDRESS>Matteo Maragliano
<EMAIL_ADDRESS>Vincent Frémont<EMAIL_ADDRESS>Carmine Tommaso Recchiuto<EMAIL_ADDRESS>Laboratoire des
Sciences du Numérique de Nantes (LS2N), CNRS, Ecole Centrale de Nantes, 1 Rue
de la Noë, 44300, Nantes, France  University of Genoa, 5 Via Balbi, 16126,
Genova, Italy

###### Abstract

In this article, we present an efficient multi-robot active SLAM framework
that involves a frontier-sharing method for maximum exploration of an unknown
environment. It encourages the robots to spread into the environment while
weighting the goal frontiers with the pose graph SLAM uncertainly and path
entropy. Our approach works on a limited number of frontier points and weights
the goal frontiers with a utility function that encapsulates both the SLAM and
map uncertainties, thus providing an efficient and not computationally
expensive solution. Our approach has been tested on publicly available
simulation environments and on real robots. An accumulative 31% more coverage
than similar state-of-the-art approaches has been obtained, proving the
capability of our approach for efficient environment exploration.

###### keywords:

SLAM , Active SLAM , Frontier Detection , Mapping , Entropy

††journal: Preprint

##  1 Introduction

Simultaneous localization and mapping (SLAM) is an approach where an agent
autonomously localizes itself and simultaneously maps the environment while
navigating through it. The objective is to find the optimal state vector that
minimizes the measurement error between the estimated pose and environmental
landmarks. Most SLAM algorithms are passive, i.e., the robot is controlled
manually and the navigation or path planning algorithm does not actively take
part in robot motion or trajectory. Active SLAM (A-SLAM), however, tries to
solve the optimal exploration problem of the unknown environment by proposing
a navigation strategy that generates future goal/target positions actions
which decrease map and pose uncertainties, thus enabling a fully autonomous
navigation and mapping SLAM system without the need of an external controller
or human effort.

In Active Collaborative SLAM (AC-SLAM) multiple robots interchange information
to improve their localization estimation and map accuracy to achieve some
high-level tasks such as exploration. The exchanged information can be
localization information [1], entropy [2], visual features [3], and frontier
points [4]. In this article, we present a multi-agent AC-SLAM system for
efficient environment exploration using frontiers detected over an Occupancy
Grid (OG) map. In particular, in this work, we aim at:

  1. 1.

Extending the A-SLAM approach of [5] which uses a computationally inexpensive
D-optimality criterion for utility computation to a multi-agent AC-SLAM
framework.

  2. 2.

Proposing a utility function that uses frontier path entropy for computing the
rewards of goal candidate frontiers.

  3. 3.

Introducing a method that coordinates the frontiers sharing among robots to
encourage maximum distance between robots for exploration.

  4. 4.

Implementing the proposed method in ROS using both simulation and real robot
experiments and achieving an accumulative 31% more coverage than state-of-the-
art methods.

The proposed system aims to efficiently maximize the environment exploration
while maintaining good SLAM estimates and provides a not computationally
expensive solution by reducing the number of goal frontiers.

The article is organized as follows: Section 2 summarises the related
literature from selected articles. Section 3 presents a thorough explanation
of our proposed system, with specific emphasis on the methodologies employed
for frontier filtering and management, implementation of the utility function,
and coordination among robots. We show the usefulness and application of the
system in simulations and real robot experiments in Sections 4.1 and 4.2.
Finally, in Section 5 we summarize and conclude this work. Throughout this
article, we will use the words robots or agents interchangeably, and the same
applies to frontiers and points, as they imply the same meaning in the
context.

##  2 Related Work

As previously mentioned, A-SLAM is designed for situations in which a robot
must navigate in an environment that is only partially observable or unknown.
In this context, the robot must choose a sequence of future actions while
dealing with noisy sensor measurements that impact its understanding of both
its state and the map of the environment. This scenario is typically
formalized as a specific case of the Partially Observable Markov Decision
Process (POMDP), as presented in [24], [17], and [19].

The POMDP formulation of A-SLAM, while widely adopted, is computationally
intensive to streamline computation, A-SLAM is usually divided into three key
steps: 1) identifying potential goal positions (frontiers, i.e., boundaries
between visited and unexplored areas), 2) calculating their associated costs
using a utility function where utility is computed using Information Theory
(IT) [10] or Theory of Optimal Experimental Design (TOED) [11], hence
selecting the next action to be performed, and 3) executing the action,
eventually moving the robot to the chosen goal position.

Concerning the first step, a common approach consists of letting the robot
identify potential exploration targets using the frontier-based approach
pioneered by Yamauchi [6]. Figure 1 illustrates frontier detection using lidar
measurements within a simulated AWS Modified Hospital
environment111https://github.com/mlherd/.

To manage exploration, IT strategies are based on the use of information as a
measure of utility for taking exploration control actions. As the
uncertainties related to the map and robot pose increase over time, the goal
is to reduce the uncertainties in the belief space [21] about the unknown
environments. The existing approaches propose solutions that make use of
particle filters [2][7], Mutual Information [8] [9], Bayesian Optimization
[9], and entropy [2]. In IT, entropy measures the amount of uncertainty
associated with a random variable or random quantity. Higher entropy leads to
less information gain and vice versa. The authors in [2] formulate the Shannon
entropy of the Map $M$ as in Equation 1 where the map is represented as an
occupancy grid and each cell $m_{i,j}$ is associated with a Bernoulli
distribution $P(m_{i,j})$. The objective is to reduce both the robot pose and
map entropy.

$\mathcal{H}[p(M)]=-\sum_{i,j}(p(m_{i,j})log(p(m_{i,j}))+(1-p(m_{i,j}))log(1-p(m_{i,j}))$
(1)

(a) Simulated environment

(b) Computed occupancy grid map and frontiers detection

Figure 1: (1(a)) AWS Modified Hospital environment. (1(b)) Frontier detection
on the occupancy grid map, red = robot, green = detected frontiers
(centroids), white = free space, gray = unknown map area, black = obstacles

Alternatively, TOED defines many “optimality criteria”, which give a mapping
of the covariance matrix to a scalar value. Hence, the priority of a set of
actions is based on the amount of covariance in the joint posterior. Less
covariance contributes to a higher weight of the action set. The “optimality
criterion” deals with the minimization of average variance, minimizing the
volume of the covariance ellipsoid (D-optimality), and minimization of the
maximum eigenvalue [13].

Many of the concepts previously discussed can be found even in the case of
Active Collaborative SLAM (AC-SLAM) with the additional constraint of managing
inter-robot robust communications. Typical application scenarios include
collaborative localization [18][22], exploration and exploitation tasks
[26][26] and trajectory planning [15][16].

In detail, multi-agent frontier-based strategies assess information gain and
detect frontiers through interactions, as seen in [28] and in wireless sensing
networks [30]. The method described by [26] formulates the problem in an
environment represented by primitive geometric shapes. The cost function is
somewhat similar to [27], which takes into consideration the discovery of the
target area of a robot by another member of the swarm and switches from a
frontier to a distance-based navigation function to guide the robot toward the
goal frontier.

Other research works have implemented frontiers-based coverage approaches that
divide the perception task into a broad exploration layer and a detailed
mapping layer, making use of heterogeneous robots to carry out the two tasks
[3] while solving a Fixed Start Open Traveling Salesman Problem (FSOTSP) for
frontier-based viewpoints has been proven as a valid solution to build a
volumetric model of the environment with multiple agents [4].

With a similar approach, the authors in [27] and [1] describe frontier-based
exploration as an optimization problem where the information gain and
localization efficiency (measured as a trace of the covariance matrix) is
maximized while navigation cost towards the frontier is penalized.

More recently another method for quantifying uncertainty, based on the graph
connectivity indices underlying the pose graph SLAM structure, has emerged as
a valid approach in the AC-SLAM scenario. Graph connectivity indices are
computationally less expensive to measure SLAM uncertainty as compared to TOED
and IT approaches discussed previously. In [22], the authors propose a method
for identifying weak connections in pose graphs to strategically enhance
information exchange when robots are in proximity. In other words, the
proposed system identifies the weak connections in the target robot pose-
graph, and when the covariance increases to a certain threshold, other agents
help to rectify these weak connections and generate trajectories using Rapidly
Exploring Random Trees (RRT) [20] to decrease uncertainty and improve
localization. This method uses continuous refinement along with the
D-optimally criterion to collaboratively plan trajectories. A bidding strategy
is defined, which selects the winning host robot based on the least
computational cost, feasible trajectory, and resource-friendly criteria.

##  3 Methodology

###  3.1 Overview of the proposed approach

Overall, the AC-SLAM approaches discussed in Section 2 quantify the
uncertainty using the entire map entropy and by using the full covariance
matrix which renders them computationally expensive. Further, they do not
favour the spread of agents for maximum coverage requirements. For these
reasons, here we propose an AC-SLAM method that encourages sparsity between
agents while utilizing a utility function that takes into account the
uncertain propagation not only of the pose-graph (D-optimality) but also of
the map (frontier path). Indeed, using our approach we manage to spread the
agents while maintaining a good SLAM estimate. Also, when compared to the
state-of-the-art methods described in Section 2 our method provides a
computationally efficient solution by working on fewer frontiers, maximizing
the exploration while using a utility function incorporating modern
D-Optimality along with path entropy.

Figure 2 shows the architecture and communication pipeline of our proposed
approach. We have built our method upon [5] which uses a Lidar-based SLAM
back-end and proposes a utility function based on the D-Optimality criterion
as a maximum number of spanning trees of the graph Laplacian of the pose-
graph. Each robot performs its SLAM using Open Karto
222https://github.com/ros-perception/slam_karto. and detects local frontiers
regarding its map. A map merging node 333https://github.com/robo-
friends/m-explore-ros2 (map-merging-node) merges local maps into a global map,
so that all the computed frontiers are referenced to the global map. Frontiers
from each agent are concatenated into a list and further processed by the
Filtering and Classification (merge-points-server) module (Section 3.2). This
module removes redundant frontiers and further filters the frontiers/points by
keeping only those points that are at (or near to) the border of the merged
map (global map). This new list of points is given back to each agent which
computes its utility and reward matrix for each point as we will see in the
Utility Computation (assigner node) module (Section 3.3). This reward matrix
is further processed by the Update Rewards & Goal Selection (choose-goals-
server) module (Section 3.4) which updates the rewards keeping into account
the sparsity and number of already selected goal points for each agent.
Finally, the selected goal for each agent is sent to the Path planning &
control module (ROS Navigation stack) which uses Dijkstra’s algorithm [12] for
global and Dynamic Window Approach (DWA) [33] as local planners.

Figure 2: Architecture of the proposed method. Local nodes of each robot
(blue), ROS server (red), map-merging mode (black)

Since the approach has been implemented in ROS and involves a centralized
frontiers sharing system as shown in Figure 2 each agent uses two main nodes
responsible for utility computation and frontier detection: the assigner node
computes the proposed utility function and assigns the goal points to the
agent, while the detector nodes use OpenCV and RRT-based frontier detection
from [5]. The following nodes are a part of the central server of the system:
1) the map-manager node, responsible for the communication among the entire
server and each agent in the system, 2) the merge-points-server node,
responsible for merging lists of points acquired by different agents, and 3)
the choose-goals-server node, which chooses a specific target point in the
list. By adopting a specific policy (Section 3.4), the server also tries to
distribute the robots in the environment and reduce the exploration time.

Concerning following Sections and Algorithms, we can summarize the workflow
as:

  1. 1.

Each agent detects the points $p$ and passes them to the central server
(subject to its availability) on a dedicated topic.

  2. 2.

The manager node takes the list of points $p_{list}$ passed by the agents and
sends it to merge-points-server.

  3. 3.

The merge-points-server takes as input the lists received by all robots,
merging the points into a unique list using Algorithm 1, also checking the
actual frontiers on the merged map $M$ through the Algorithm 2 and limiting
the dimension of the list using the procedure explained in Algorithm 3.
Eventually, it gives back the list to each agent.

  4. 4.

Each agent computes the reward matrix $R_{m}$ on the received list, with the
approach described in Section 3.4, sending it to the choose-goals-server.

  5. 5.

The choose-goals-server server updates the reward through Algorithms 4 and 5
to take into account all the points already assigned. The selected target
point is fed back to the robot.

  6. 6.

The global and local planners of the ROS package $move\\_base$ are responsible
for driving each agent to the selected frontier. Once the agent reaches the
target, the workflow restarts from step 1.

In the following Sections, we describe comprehensively steps 3, 4, and 5,
which represent the core of the proposed approach.

###  3.2 Filtering and classification

Each agent is responsible for building its map and merging local frontier
points as shown in Algorithm 1. Some parts of the map from each agent can be
overlapped and the frontiers could lie in an already mapped area when
considering the merged map. Since usually the goal of an exploration task is
to cover the entire area by minimizing the exploration time, the frontiers
lying in the middle of the merged map are not significant because moving an
agent to them would not increase the overall discovered area.

To avoid the need to consider these points as goal-like points, we decided to
filter the points considering only the actual frontiers of the merged map. To
this purpose, Algorithm 1 takes a list of points $P_{list}$ and the merged map
$M$ and it checks if each point has enough unknown cells (PRC_UNK) around it,
in a radius (RAD) (line 5), i.e., if the point is near the border. If so, the
point is added to the global list $uni_{pts}$. This process (line 5) of
Algorithm 1 is detailed in Algorithm 2. In particular, it may be observed how
the percentage PER_UNK of unknown cells (Line 18) contained in the radius RAD
is used to discriminate whether to keep a point in the list or not (Line 19).

(a) Discretized circle around a point P.

(b) Discretized circle around points P & Q.

Figure 3: General 3(a) and Occupancy Grid Map Representation 3(b) of the
Discretized circle  Algorithm 1 Merge Points

1:$p_{list}$, $M$ $\triangleright$
$p_{list}=\\{x_{1},y_{1},...x_{N},y_{N}\\}$, merged_map = $M$

2:

3:$uni_{pts}\leftarrow 0$

4:for $p$ $\in$ $p_{list}$ do

5: if $N_{bdr}$$(p,M,\texttt{RAD},\texttt{PRC\\_UNK})$ then

6: if $p\notin uni_{pts}$ then

7: $uni_{pts}\leftarrow p$ $\triangleright$ add $p$ to unique list of points

8: end if

9: end if

10:end for

Algorithm 2 Check if a Point is Near the Map Border

1:function $N_{bdr}$($p,M,rad,\texttt{PRC\\_UNK}$)

2: $c_{x}\leftarrow(p_{x}-M_{origx})/M_{res}$

3: $c_{y}\leftarrow(p_{y}-M_{origy})/M_{res}$

4: $Rad_{c}\leftarrow\text{rad}/M_{res}$

5: $Cir_{c}\leftarrow\\{\\}$, $unk_{cnt}$, $tot_{c}\leftarrow 0$

6: for $i$,$j$ $\in$ $Rad_{c}$ do

7: $cel_{i}\leftarrow c_{x}+i$, $cel_{j}\leftarrow c_{y}+j$

8: if $cel_{i},cel_{j}\geq 0\textbf{ \&}\newline \hskip
54.00009pt<M_{w},M_{h}$ then

9: $idx\leftarrow cel_{i}+cel_{j}\times M_{width}$

10: $Cir_{c}\leftarrow cel_{i},cel_{j}$

11: if $M_{data}[idx]=-1$ then

12: $unk_{cnt}\leftarrow unk_{cnt}+1$

13: end if

14: $tot_{cells}\leftarrow tot_{cells}+1$

15: end if

16: end for

17: if $tot_{cells}\neq 0$ then

18: $unk_{perc}\leftarrow\left(\frac{unk_{cnt}}{tot_{cells}}\right)\times 100$

19: if $unk_{perc}\geq\texttt{PRC\\_UNK}$ then

20: return True

21: end if

22: end if

23: return False

24:end function

Algorithm 3 Check list dimension

1:$p_{list}$, $M$, $rad$, PRC_UNK

2:

3:while $uni_{pts}\leq\texttt{MIN\\_PTS}$ or
$\geq\texttt{NUM\\_PTS}$ do

4: if $uni_{pts}\leq\texttt{MIN\\_PTS}$ then

5: $uni_{ptsN}\leftarrow\text{list}$,$uni_{pts}\leftarrow\\{\\}$

6: $perc=perc-10$

7: for $p\in uni_{ptsN}$ do

8: if $N_{bdr}(p,M,rad,\texttt{PRC\\_UNK}$) then

9: if $p\notin uni_{pts}$ then

10: $uni_{pts}\leftarrow p$

11: end if

12: end if

13: end for

14: else if $uni_{pts}\geq\texttt{NUM\\_PTS}$ then

15: $uni_{ptsN}\leftarrow uni_{pts}$

16: $uni_{pts}\leftarrow\\{\\}$

17: $rad=rad+0.25$

18: for $p\in uni_{ptsN}$ do

19: if $N_{bdr}(p,M,rad,\texttt{PRC\\_UNK}$) then

20: if $p\notin uni_{pts}$ then

21: $uni_{pts}\leftarrow p$

22: end if

23: end if

24: end for

25: end if

26:end while

To provide an example of this approach, Figure 3(b) shows an example list of
two points P and Q in a partially discovered map. The Algorithm 1 in
conjunction with Algorithm 2 identifies, for both points, a circle as shown in
Figure 3(a) and computes the percentage of the unknown cells over the total
one contained inside the circle. Once the percentage is computed, this point
is kept or discarded based on the threshold of PER_UNK set during the program
execution. In the specific case, opportunely setting PER_UNK, point P will be
added to the global list, i.e., considered as a border point, whereas point Q
will be discarded.

Even discarding points that are not on the border, having many agents may lead
to having extensive lists of points that need to be processed; to avoid this
problem, we decided to bind the number of points to process using Algorithm 3.
After the list is created, there is another check to validate the boundaries
of the list dimension as described in Algorithm 3. Concerning this algorithm,
if the list has fewer points than the minimum required (i.e., MIN_PTS), the
same is recomputed by decreasing the threshold PER_UNK used in Algorithm 2 by
$10\%$ as shown in Line 6. On the other hand, if the list has more points than
a maximum threshold NUM_PTS, the list is reprocessed by increasing the radius
RAD (Algorithm 2) by 0.25m (Line 17 of Algorithm 3).

###  3.3 Utility computation

Once the global list of frontier points is created, it is sent to the assigner
node of each agent for the computation of the utility function for each
frontier candidate, by applying the Bresenham’s line algorithm [34] to get the
occupancy values of all the pixels within the straight path from the agent to
the frontier location. For computing the Entropy, we assign a probability
value equal to $P_{unknown}=0.1$ to the occupancy values of unknown pixels, to
quantify low entropy and high information gain (as we are more interested in
unknown areas of the environment). Occupancy values of obstacles and free
space are mapped with a probability $P_{known}=0.45$, quantifying high entropy
and low information gain.

Using these probability values and Equation 1, the path entropy $E$ for each
frontier candidate is computed. The path entropy is then normalized with the
number of pixels/cells within the frontier path $L$. We apply an exponential
decay operator $\gamma=\exp^{-(\lambda*dist)}$ with decay factor $\lambda=0.6$
(kept constant as we assume static environment) and Euclidean distance $dist$
for penalizing frontiers with large distances. Finally, the proposed utility
$U_{2}$ as shown in Equation 2 is computed by weighing normalized entropy with
$\rho=10^{\beta}$, where $\beta$ is a factor which depends on the number of
spanning trees of the weighted graph Laplacian $L_{w}$ computed in Equation 3
and adopted from [5]. More explicitly $\beta$ is the the number of digits
before the decimal places of $U_{1}$ and acts as a balancing factor between
entropy and the number of spanning trees.

Eventually, we obtain the proposed utility function $U$ in Equation 4, which
not only provides a good SLAM estimate based on the modern D-Optimality
criterion but also increases the coverage of the unknown map by reducing the
frontier path entropy.

$U_{2}=(1-E/L)*\rho+\gamma$ (2)

$U_{1}=\text{Spann}(L_{w})$ (3)

$\text{Reward}=U=\text{max}(U_{1}+U_{2})$ (4)

The Reward $r_{0:N}$ is assigned through the matrix $R_{m}$ for each agent, as
shown in Equation 10, where $N$ is the number of points detected.

$\displaystyle
R_{m}=\left[\begin{array}[]{ccc}\text{{Reward}}&\text{{X}}&\text{{Y}}\\\
\hline\cr r_{0}&x_{0}&y_{0}\\\ r_{1}&x_{1}&y_{1}\\\ \vdots&\vdots&\vdots\\\
r_{N}&x_{N}&y_{N}\\\ \end{array}\right]$ (10)

###  3.4 Update Rewards and Goal selection

Once each agent has computed its reward matrix, each matrix is sent to the
choose-goals-server (hereafter referred to as server) to opportunely update
the rewards and select the goal point of each agent. Since the server can
manage one reward matrix at a time, it is asynchronously handled by the
various agents, with a priority approach: assuming to have a system of $M>1$
agents, taking two general agents $i$ and $j$, which request the server at the
same time, the goal of $i$ is processed before $j$’s if $i<j$.

Moreover, the server also stores the already assigned locations, to avoid
reusing them. Indeed, to explore the biggest possible area of the environment,
the goals for the agents need to be spread. To foster this sparsity, since
there are many agents, we decided to update the reward function using
Algorithm 5 and Equations 11-13, where $d$ is the distance between the chosen
goal and all other goal points.

$K=\frac{\texttt{max reward in matrix}}{\texttt{number of already chosen
points}}$ (11)

$k=\frac{K}{d^{2}}$ (12)

$R_{new}=R_{old}-k$ (13)

It may be observed (Equation 13) how $k$ represents a subtracting factor for
the Reward matrix elements, updated when a target goal for one agent is
selected. Since $k$ is inversely dependent on the distance computed between
the last chosen goal and the considered frontier point (Equation 12), the
closer the point is closer to the already chosen goal, the higher will $k$,
decreasing the probability that the point will be chosen as the next goal,
thus achieving the task of spreading the goals in the environment.

The complete procedure for the selection of points (goals) is described in
Algorithm 4, also including the relative function to update rewards when a
goal is selected, described in Algorithm 5.

Algorithm 4 Select Points

1:function $sel_{pts}$($PRewards,N_{goals}$)

2: $goals\leftarrow\\{\\}$

3: $Mat\leftarrow$ Equation 10 using $PRewards$ and $N_{goals}$

4: if $Mat\neq\\{\\}$ then

5: $p\leftarrow$ Point2D()

6: if $cho_{cords}\neq\\{\\}$ then

7: $Mat$ $\leftarrow$ $upd\\_rewards$($cho_{cords}$, $Mat$)

8: end if

9: $MaxRew_{ID}\leftarrow\text{get maximum reward index in }Mat$

10: $p.x,p.y\leftarrow\text{x,y value in $Mat$ at }MaxRew_{ID}$

11: for $pt\in cho_{cords}$ do

12: if $pt.x,pt.y=p.x,p.y$ then

13: $Mat[MaxRew_{ID},0]\leftarrow-\infty$

14: $MaxRew_{ID}\leftarrow\text{get maximum reward index in }Mat$

15: $p.x,p.y\leftarrow\text{x,y value at }MaxRew_{ID}$

16: end if

17: end for

18: $cho_{cords}\leftarrow p$

19: $goals\leftarrow p$

20: end if

21: return $goals$

22:end function

Algorithm 5 Update Rewards

1:function $upd\\_rewards$($cho_{cords}$, $Mat$)

2: $MaxRew_{val}\leftarrow\text{max. reward in $Mat$}$

3: $K\leftarrow\text{Equation \ref{eq: K}}$

4: for $c\in cho_{cords}$ & $g\in Mat$ do

5: if $c_{x,y}=g_{x,y}$ then

6: $Mat[g]=-\infty$

7: end if

8: if $Mat[g]\neq-\infty$ then $\triangleright$ compute distance from chosen
goals

9: $d2\leftarrow\sqrt{(c_{x}-g_{x})^{2}+(c_{y}-g_{y})^{2}}$

10: if $d2\neq 0$ then

11: $Mat[g]\leftarrow$ Equation 13

12: else

13: $Mat[g]=-\infty$

14: end if

15: end if

16: end for

17: return $Mat$

18:end function

Algorithm 4 takes as input a list of points along with their rewards
$PRewards=\\{r_{1},x_{1},y_{1},.....,r_{N},x_{n},y_{n}\\}$ (computed with
Equation 5, line 3), and updates the $R_{m}$ matrix using Algorithm 5 (line
7), which first checks whether the frontier corresponds with the already
selected goal, discarding the point in this case, and then updates the reward
as described in Equations 11-13. The goal corresponding to the higher reward
for the current agent, updated with the described policies, is eventually
passed back to the agent.

The choice of the parameter $K$ (Equation 11 is mainly motivating by two
reasons:

  * 1.

the term max reward in matrix allows for scaling $K$ concerning the Reward
Matrix of each single agent, normalizing the subtractive factor;

  * 2.

the term number of already chosen points allows for distributing the reward
update also taking into account the number of already selected points. Indeed,
when the number of targets already explored becomes significant, each point
will only receive a smaller portion of the total reward, resulting in a more
limited effect of the subtractive parameter.

As described before, agents are managed asynchronously with a priority
approach. The priority assigned to robots can lead to having one or more
robots with low priority being stuck because they are always prioritized by
higher-priority agents. To avoid this issue, the server also takes into
account the number of requests not related to each agent. Once this number
exceeds a certain predefined threshold, the corresponding agent will be
associated with the higher priority. This approach will avoid having robots
stuck, distributing goals more uniformly and is more effective then
synchronous approach presented in our previous work [35].

##  4 Experimental Evaluation

###  4.1 Simulation Environment

To evaluate the proposed approach, simulations were performed with the
simulation environment Gazebo on a PC with an Intel Core i7® (32GB RAM) and
NVIDIA RTX 1000 GPU, equipped with Ubuntu 20.04 and ROS Noetic. Practically, a
team of RosBots 2, equipped with lidar sensors were deployed in a modified
version of the Willow Garage (W.G)444https://github.com/arpg/Gazebo/
environment and of the AWS Hospital222https://github.com/aws-robotics/aws-
robomaker-hospital-world, with area of 2071 and 1243 $m^{2}$ respectively.

Since our proposed approach aims at environment exploration while working on
minimum frontier points with efficient AC-SLAM, we decided to use the
following performance metrics:

  * 1.

percentage of map coverage, to quantify the evolution of the covered map
concerning the ground truth map;

  * 2.

number of frontier points, to measure the average points reduction
(corresponding to a decreased computational cost) achieved with the method
described in Section 3.2.

Figure 4 shows the resultant Occupancy Grid map along with the pose graphs of
3 agents in the AWS Hospital environment, ctrconsidering 30 minutes of
exploration time. We can observe that the proposed method provides an accurate
map with 80% coverage while maintaining good SLAM accuracy. Figure 5 shows the
resulting individual pose graphs from Open Karto SLAM, also indicating the
loop closures performed by robots, which helps in reducing uncertainty.

Figure 4: AWS Modified Hospital with 3 robots.

(a) Pose graph of Robot 1.

(b) Pose graph of Robot 2.

(c) Pose graph of Robot 3.

Figure 5: Resulting pose graphs of individual robots.

Figure 6(a) shows the results of 4 simulations (S1 to S4) using 2 and 3
robots, with and without the proposed utility function, again related to 30
minutes of exploration time, in the Willow Garage environment. In this
scenario, we compared our proposed approach (designed as ‘our’) with the one
using the utility function proposed by [5], as shown in Equation 3
(hereinafter referred as ‘MAGS’).

We can observe that with our approach (S2, S4) we manage to get 11% and 8%
more area covered as compared to MAGS (S1, S3) respectively. This implies an
area of 228$m^{2}$ and 166$m^{2}$ covered. As far as dealing with the
computational complexity, i.e., in terms of reducing the number of processed
frontier points, Figure 6(b) provides an insight into how the number of points
used is reduced. We can deduce that using the methods in Section 3.2 and
setting PER_UNK $=60\%$, RAD$=1m$ we manage to drastically reduce the average
number of points processed from 31 to 6 for S1 (81%), 37 to 7 for S2 (82%), 58
to 9 for S3 (85%), and 48 to 2 for S4 (96%) respectively, also exploring the
environment more efficiently. This reduction in points is directly related to
the computational complexity, as fewer points require computing the utility
function with lesser frequency, hence accelerating the overall performance of
the proposed system.

The same comparison has been carried out in the smaller AWS environment, with
a simulation time of 25 minutes. Figure 7 shows the area coverage and points
reduction with ’our’ (S2, S4) and ’MAGS’ (S1, S3) approaches. We can observe
that with the proposed approach (S2, S4) we managed to get a higher percentage
(3% - 9%) of the area covered. This implies an increased coverage area between
37$m^{2}$ and 112$m^{2}$. Since the AWS Hospital environment is much smaller
than the Willow Garage one, results related to map coverage are quite high for
both MAGS and our approach, but the small increase in coverage seems to
confirm the effectiveness of our approach. Also in this case, the usage of the
Filtering and Classification method described in Section 3.2 leads to a
meaningful reduction in the number of points processed from 36 to 1 for S1
(98%), 29 to 4 for S2 (87%), 43 to 1 for S3 (98%), and 76 to 0 (no new points
detected) for S4 respectively. The average values are smaller compared to
those in Figure 6(b) (1.5 vs 6) since also the environment is smaller than
before. Hence, the system is saturated with an average coverage of 80%, and no
further exploration and coverage task is required.

The above-mentioned simulation results indicate the efficiency of our approach
as compared to the state-of-the-art methods. To further evaluate the
methodology, we performed tests with a team of ground robots in a real
environment, whose results are presented in the following section.

(a) % area coverage comparison

(b) Points filtering

Figure 6: Willow Garage (W.G) % area coverage and points reduction comparison

(a) % area coverage comparison.

(b) Points filtering

.

Figure 7: AWS Hospital % area coverage and points reduction comparison.

###  4.2 Real Environment

Experiments in a real environment were performed using two ROSBot 2R
robots555https://husarion.com/manuals/rosbot/. with RPLidar A2 (Figure 8(a))
with ROS on Ubuntu 20.04.6 (LTS). The robots are equipped with an Intel Xeon®
W-2235 CPU 3.80GHz x 12, with 64Gb RAM and Nvidia Quadro RTX 4000 GPU. The
environment consists of a room and two corridors measuring 81$m^{2}$ in total
as shown in Figure 8(b). Figure 8(c) shows the resultant Occupancy Grid map
along with SLAM pose graphs, using the proposed approach with a team composed
of two robots (red circles).

Figure 9(a) shows the percentage of maps discovered over time. As for
simulation results, we compared the proposed utility function with the ’MAGS’
one in eight experiments, considering an exploration time of 2 minutes. It can
be shown that the proposed approach achieves a coverage of 98.85%, higher than
the coverage percentage achieved with MAGS (94.25%). This implies a higher
portion of map covered with the proposed approach (4.6%) and hence proves the
effectiveness of the proposed method.

Figure 9(b) compares the number of points processed and detected in the four
experiments. We can observe a significant reduction in the number of used
points, from 6 to 5 for Exp 1 (17%), 7 to 3 for Exp 2 (58%), 3 to 2 for Exp 3
(34%), and 6 to 2 for Exp 4 (67%), resulting again in a reduction of the
computational load.

Since the area of the experimental environment is much smaller, the
exploration time was limited to only 2 minutes. Still, the increase of the map
coverage (4.6%) was similar to the one achieved within the simulation (3% -
11%). The maximum number of points detected and processed is smaller
concerning the simulation results, with an average reduction in the frontier
points used equal to 44%.

(a) ROSbot 2R

(b) Experimental environment

(c) Mapped environment

Figure 8: Robot and experimental environment used.

(a) Comparison of mean values

(b) Points filtering.

Figure 9: (9(a)) Comparison of mean values of map discovered with and without
the proposed utility function. (9(b)) Total points detected vs the actual
points used.

##  5 Conclusion

In this article, we presented a multi-robot collaborative active SLAM
framework for an environment exploration task. The proposed framework provides
a utility function that incorporates the SLAM uncertainty and path entropy for
the efficient selection of goal frontier candidates. We also propose an
efficient frontier filtering method that encourages sparsity while working on
a reduced number of frontier candidates, hence providing a less
computationally expensive solution. The implementation exploits a ROS-based
client-server paradigm in a modular software architecture.

Through various simulation results on publicly available environments and
experiments in a real environment, we have proven the usefulness and
applicability of our method as compared to selected state-of-the-art
approaches and manage to achieve an accumulative 31% more coverage. In the
future, we plan to extend our approach to visual AC-SLAM using heterogeneous
robots to exploit the visual features and viewpoint changes of the
environment.

## Acknowledgement

This work was carried out in the framework of the NExT Senior Talent Chair
DeepCoSLAM, which was funded by the French Government, through the program
Investments for the Future managed by the National Agency for Research
ANR-16-IDEX-0007, and with the support of Région Pays de la Loire and Nantes
Métropole. This research was also supported by the DIONISO project (progetto
SCN_00320-INVITALIA), which is funded by the Italian Government.

## References

  * [1] Pham, V. C., Juang, J. C. (2011). An Improved Active SLAM Algorithm for Multi-robot Exploration . SICE Annual Conference 2011, 1660–1665.
  * [2] Stachniss, C., Grisetti, G., Burgard, W. Information Gain-Based Exploration Using Rao-Blackwellized Particle Filters. In Proceedings of the Robotics: Science and Systems I; Robotics: Science and Systems Foundation, June 8 2005.
  * [3] Qin, H., Meng, Z., Meng, W., Chen, X., Sun, H., Lin, F., , Ang, M. H. (2019). Autonomous exploration and mapping system using heterogeneous UAVs and UGVs in GPS-denied environments. IEEE Transactions on Vehicular Technology, 68(2), 1339–1350.
  * [4] Meng, Z., Sun, H., Qin, H., Chen, Z., Zhou, C., Ang, M. H. (2017). Intelligent robotic system for autonomous exploration and active slam in unknown environments. SII.
  * [5] Placed, J.A., Castellanos, J.A. Fast Autonomous Robotic Exploration Using the Underlying Graph Structure. (2021) IROS, Prague, Czech Republic, September 27 2021, pp. 6672–6679.
  * [6] Yamauchi, B. A Frontier-Based Approach for Autonomous Exploration. (1997). CIRA’97. Monterey, CA, USA, 1997; pp. 146–151.
  * [7] J. Du, L. Carlone, M. Kaouk Ng, B. Bona and M. Indri, ”A comparative study on active SLAM and autonomous exploration with Particle Filters,” 2011 IEEE/ASME AIM, Budapest, Hungary, pp. 916-923.
  * [8] Brian J. Julian, Sertac Karaman, and Daniela Rus. “On mutual information-based control of range sensing robots for mapping applications”.2013 IROS, pp. 5156–5163.
  * [9] Shi Bai et al. “Information-theoretic exploration with Bayesian optimization”. 2016 IROS. pp. 1816–1822.
  * [10] Shannon, C. E. (1948). A mathematical theory of communication. The bell system technical journal, 27, 623–656.
  * [11] A. P$a^{{}^{\prime}}$zman, Foundations of optimum experimantal design. Springer, 1996, vol. 14.
  * [12] Dijkstra EW. A note on two problems in connexion with graphs. Numerische mathematik. 1959;1(1):269–71.
  * [13] Carrillo, H., Reid, I., Castellanos, J. A. (2012, May). On the comparison of uncertainty criteria for active SLAM. In 2012 IEEE International Conference on Robotics and Automation: pp. 2080-2087.
  * [14] Indelman, V. (2018). Towards cooperative multi-robot belief space planning in unknown environments. Springer Proceedings in Advanced Robotics, 441–457.
  * [15] Ossenkopf, M., Castro, G., Pessacg, F., Geihs, K., & De Cristoforis, P. (2019). Long-Horizon Active Slam system for multi-agent coordinated exploration. ECMR.
  * [16] Kontitsis, M., Theodorou, E. A., & Todorov, E. (2013). Multi-robot active slam with relative entropy optimization. 2013 American Control Conference.
  * [17] Placed, J.A.; Castellanos, J.A. A Deep Reinforcement Learning Approach for Active SLAM. Applied Sciences 2020, 10, 8386.
  * [18] Pei, Z., Piao, S., Souidi, M., Qadir, M., & Li, G. (2018). Slam for humanoid multi-robot active cooperation based on relative observation. Sustainability, 10(8), 2946.
  * [19] Placed, J. A., Strader, J., Carrillo, H., Atanasov, N., Indelman, V., Carlone, L., Castellanos, J. A. (2023). A survey on active simultaneous localization and mapping: State of the art and new frontiers. IEEE Transactions on Robotics (T-RO)
  * [20] K. Naderi, J. Rajamäki, P. Hämäläinen, RT-RRT*: a real-time path planning algorithm based on RRT*, 8th ACM, Paris France, 2015: pp. 113–118.
  * [21] Indelman, V. (2015). Towards multi-robot active collaborative state estimation via belief space planning. 2015 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS).
  * [22] Chen, Y., Zhao, L., Lee, K. M., Yoo, C., Huang, S., Fitch, R. (2020). Broadcast your weaknesses: cooperative active pose-graph slam for multiple robots. IEEE Robotics and Automation Letters, 5(2), 2200–2207.
  * [23] Li, J., Cheng, Y., Zhou, J., Chen, J., Liu, Z., Hu, S., Leung, V. C. (2022). Energy-efficient ground traversability mapping based on UAV-UGV collaborative system. IEEE Transactions on Green Communications and Networking, 6(1), 69–78.
  * [24] Fox, D.; Burgard, W.; Thrun, S. Active Markov Localization for Mobile Robots. Robotics and Autonomous Systems 1998, 25, 195–207,
  * [25] N. Mohamad Yatim, N. Buniyamin, Particle filter in simulatneous localization and mapping (SLAM) using differential drive mobile robot, Jurnal Teknologi. 77 (2015).
  * [26] Arvanitakis, I., Tzes, A. (2017). Collaborative mapping and navigation for a mobile robot swarm. 2017 25th Mediterranean Conference on Control and Automation (MED).
  * [27] Pham, V. C., Juang, J. C. (2013). A multi-robot, cooperative, and active SLAM algorithm for exploration. International Journal of Innovative Computing, Information and Control, 9(6), 2567–2583.
  * [28] Batinović, A., Oršulić, J., Petrović, T., Bogdan, S. Decentralized Strategy for Cooperative Multi-Robot Exploration and Mapping. IFAC-PapersOnLine 2020, 53, 9682–9687.
  * [29] H. W. Kuhn, ‘The Hungarian method for the assignment problem’, (1955) Naval Research Logistics, vol. 2, no. 1–2, pp. 83–97.
  * [30] Jadhav, N., Behari, M., Wood, R., Gil, S. Multi-Robot Exploration without Explicit Information Exchange.
  * [31] Khosoussi, K., Huang, S., Dissanayake, G. Novel Insights into the Impact of Graph Structure on SLAM. (2014) IROS, Chicago, IL, USA, pp. 2707–2714.
  * [32] Khosoussi, K.; Giamou, M.; Sukhatme, G.S.; Huang, S.; Dissanayake, G.; How, J.P. Reliable Graphs for SLAM. The International Journal of Robotics Research 2019, 38, 260–298.
  * [33] Fox, D.; Burgard, W.; Thrun, S. The Dynamic Window Approach to Collision Avoidance. IEEE Robot. Automat. Mag. 1997, 4, 23–33.
  * [34] Kuzmin, Y. P., Bresenham’s Line Generation Algorithm with Built-in Clipping. (1995). Comput. Graph. Forum 14 , no. 5 : 275-280.
  * [35] Maragliano, M., Ahmed, M.F., Recchiuto, C.T., Sgorbissa, A. and Fremont, V., 2023. Collaborative Active SLAM: Synchronous and Asynchronous Coordination Among Agents. arXiv preprint arXiv:2310.01967.