# Multi S-Graphs: an Efficient Real-time Distributed Semantic-Relational
Collaborative SLAM

Miguel Fernandez-Cortizas1,2, Hriday Bavle1, David Perez-Saura2,
Jose Luis Sanchez-Lopez1, Pascual Campoy2 and Holger Voos1 1Authors are with
the Automation and Robotics Research Group, Interdisciplinary Centre for
Security, Reliability, and Trust (SnT), University of Luxembourg, Luxembourg.
Holger Voos is also associated with the Faculty of Science, Technology, and
Medicine, University of Luxembourg, Luxembourg. {hriday.bavle,
joseluis.sanchezlopez<EMAIL_ADDRESS>are with the Computer
Vision and Aerial Robotics Group at Universidad Politécnica de Madrid, Spain
(CVAR-UPM) at the Centre for Automation and Robotics C.A.R. (UPM-CSIC).
{miguel.fernandez.cortizas, david.perez.saura<EMAIL_ADDRESS>work was partially funded by the Fonds National de la Recherche of Luxembourg
(FNR), under the projects C22/IS/17387634/DEUS, by the European Union’s
Horizon 2020 Project No. 101017258 SESAME, by European Union’s Horizon Europe
Project No. 101070254 CORESENSE, as well as project COPILOT ref. 2020/EMT6368,
funded by the Madrid Government under the R&D Synergic Projects Program,
project INSERTION ref. ID2021-127648OBC32 and project RATEC ref:
PDC2022-133643-C22, both funded by the Spanish Ministry of Science and
Innovation.For the purpose of Open Access, and in fulfillment of the
obligations arising from the grant agreement, the author has applied a
Creative Commons Attribution 4.0 International (CC BY 4.0) license to any
Author Accepted Manuscript version arising from this submission.

###### Abstract

Collaborative Simultaneous Localization and Mapping (CSLAM) is critical to
enable multiple robots to operate in complex environments. Most CSLAM
techniques rely on raw sensor measurement or low-level features such as
keyframe descriptors, which can lead to wrong loop closures due to the lack of
deep understanding of the environment. Moreover, the exchange of these
measurements and low-level features among the robots requires the transmission
of a significant amount of data, which limits the scalability of the system.
To overcome these limitations, we present Multi S-Graphs, a decentralized
CSLAM system that utilizes high-level semantic-relational information embedded
in the four-layered hierarchical and optimizable situational graphs for
cooperative map generation and localization while minimizing the information
exchanged between the robots. To support this, we present a novel room-based
descriptor which, along with its connected walls, is used to perform inter-
robot loop closures, addressing the challenges of multi-robot kidnapped
problem initialization. Multiple experiments in simulated and real
environments validate the improvement in accuracy and robustness of the
proposed approach while reducing the amount of data exchanged between robots
compared to other state-of-the-art approaches.

Software available within a docker image: https://github.com/snt-
arg/multi_s_graphs_docker

##  I Introduction

Figure 1: Collaborative graph generated by three robots mapping a building
floor (orange, gray, and blue for robots 1, 2, and 3 respectively). The
collaborative graph is generated from the point of view of Robot 1. Semantic
information gathered by the other robots, such as rooms or walls appears in
transparent colors in the graph layers. The origin of the coordinate systems
of the other robots appears surrounded by a circle. Below is the result of
merging the point clouds obtained from each of the robots. This point cloud is
displayed for visualization purposes and is not utilized in inter-robot
communication.

Collaborative Simultaneous Localization and Mapping (CSLAM) is a technology
that enables multi-robot systems to work together to create a map of their
environment while simultaneously determining their own positions within the
map. Most CSLAM techniques, such as [1], [2], [3], are highly based on the
transmission of low-level features, such as keyframe descriptors, between
robots. With these low-level features, each robot creates its own map and can
match it to integrate them into a common map. This is used for both visual and
LiDAR-based approaches. However, the use of these low-level features usually
leads to incorrect loop closures [4]. Works such as [1] or [5] focus on
robustifying their loop closure algorithms to avoid incorrect loop closures.
The main drawback of these methods emerges from the fact that the system has
limited understanding of the environment.

Novel approaches to single-robot SLAM address this issue of limited
understanding of the environment by incorporating meaningful metric-semantic-
relational information, with works like Hydra [6] which exploits 3D scene
graphs for loop closure, or S-Graphs+ [7], [8], which couple in a situational
graph modeled as a single optimizable factor graph, the 3D scene graph with
the underlying SLAM graph. These works demonstrate that extracting semantic
meaning from metric information and incorporating it with appropriate
relational constraints such as walls, rooms, floors, etc., improve the overall
precision of underlying SLAM while robustifying loop closures and generating
meaningful environmental maps. Recently, Hydra-Multi [9] and CURB-SG [10] took
advantage of 3D scene graphs for collaborative SLAM in a centralized way.
These innovative approaches harness semantic-relational knowledge to exchange
higher-level information between the agents to fortify inter-robot loop
closures. However, these methods, apart from being centralized, explicitly add
loop closure constraints to underlying robot poses instead of implicitly
constraining the same semantic entities detected by different agents.

Thus in this work, we present Multi S-Graphs, a LiDAR-based distributed CSLAM
system harnessing the potential of the multi-layered Situational Graphs
(S-Graphs), a single optimizable factor graph that combines a pose graph (i.e.
with keyframes) and a 3D scene graph with semantic-relational concepts, to
generate precise environmental maps and locating the different robots in this
map while exchanging minimum information between robots. To the best of our
knowledge, we present the first real-time distributed collaborative SLAM
system based on optimizable situational graphs. Fig. 1 shows the Multi
S-Graphs executed on a real experiment.

The main contributions of our system are as follows:

  1. 1.

A novel distributed multi-robot framework, Multi S-Graphs based on four-
layered optimizable hierarchical S-Graphs, exploiting semantic-relational
information for map merging while minimizing the information exchange between
the robots.

  2. 2.

A hybrid room-based descriptor combining fine-grained point cloud information
with semantic knowledge to identify inter-robot loop closures.

  3. 3.

Experimental validation of the proposed approach in simulated and real
environments obtaining improved accuracy compared to state-of-the-art multi-
robot approaches.

##  II Related Work

###  II-A Multi-Agent SLAM

There are two main categories of multi-agent SLAM architectures: centralized
and decentralized.

Centralized. Centralized CSLAM approaches are based on multiple single-robot
front-ends with a common back-end. LAMP 2.0 [11] is a centralized multi-robot
SLAM system that is adaptable to different input odometry sources, with a
robust and scalable loop closure detection module and an outlier-robust back-
end based on Graduated Non-Convexity (GNC) for pose graph optimization. It is
designed for operation in challenging large-scale underground environments.
maplab 2.0 [12] is a large-scale multi-robot multi-session mapping system that
integrates non-visual landmarks and incorporates a semantic object-based loop
closure module into the mapping framework. COVINS-G [13] is a generalized
back-end for collaborative visual-inertial SLAM building upon the COVINS [14]
framework that enables compatibility with any arbitrary VIO front-end. The
drawbacks of centralized architectures are that they require good
communication with the common back-end and, if that node fails, the whole
system fails. In addition, they do not scale up for large robot teams.

Decentralized. Within decentralized approaches, most of them focus on visual-
based SLAM. Deutsch et al. [15] proposed a framework that relies on a Bag of
Words (BoW) of the keyframes obtained with an RGB-D camera to enable
collaborative mapping for existing (single-robot) SLAM systems. Kimera-Multi
[16] also uses BoW and needs a Robust Distributed Initialization to initialize
all robot poses in a shared (global) coordinate frame. It builds a globally
consistent metric-semantic 3D mesh model of the environment in real time,
while being robust to incorrect loop closures and only relying on local
communication. Each robot builds a local trajectory estimate and a local mesh
using Kimera [17], and when two robots are within communication range, they
initiate a distributed place recognition and robust pose graph optimization
protocol based on a distributed GNC algorithm. Swarm-SLAM [18] includes a
novel inter-robot loop closure prioritization technique based on algebraic
connectivity maximization that reduces communication and accelerates
convergence. It also has a decentralized approach to neighbor management and
pose graph optimization suited for sporadic inter-robot communication, and
supports different types of sensors using different descriptors, such as
CosPlace [19] and NetVLAD [20] for images and Scan Context [21] for LiDAR
scans. Decentralized LiDAR SLAM solutions focus on the data-efficient exchange
of observation between robots. DiSCo-SLAM [22] uses the lightweight Scan
Context descriptor and includes a two-stage global and local optimization
framework for distributed multi-robot SLAM which provides stable localization
results that are resilient to the unknown initial conditions that typify the
search for inter-robot loop closures. DCL-SLAM [23] includes a lightweight
global descriptor, LiDAR-Iris [24], for loop closure detection, a three-stage
data-efficient distributed loop closure approach to estimate the relative pose
transformation between robots, and a two-stage distributed Gauss-Seidel (DGS)
approach for optimization.

Figure 2: Multi S-Graph architecture viewed from $Robot_{i}$ perspective.
Odometry measures and 3D Lidar data are the inputs that the robotic platform
provides. Each robot executes its own Local S-Graph system and generates the
Room Descriptors and the Distilled S-Graphs that are exchanged with the rest
of the robotic network. Messages exchanged between robots are represented in
gray. From the point of view of the $Robot_{i}$ the rest of the agents provide
the Distilled graphs and the Room descriptors that are used to generate the
Collaborative S-Graph. The information provided by the rest of the robots
appears in green color.

Current decentralized collaborative SLAM systems struggle to effectively use
well-mapped areas generated by other agents, leading to map redundancy and
costly re-mapping. Bänninger et al [25] propose a strategy to efficiently
share areas mapped by different agents in a decentralized, peer-to-peer
fashion, achieving a globally consistent estimate through distributed bundle
adjustment using the Alternating Direction Method of Multipliers (ADMM). The
method leverages covisibility information between keyframes instantiated by
different agents to transfer local sub-maps on-the-fly, addressing map
redundancy while maintaining consistency and scalability. However, the use of
semantic information from the environment can further reduce the information
exchange.

###  II-B Multi-Agent 3D Scene Graphs

Recent research aims to leverage the use of semantic information by combining
Scene Graphs with SLAM. Hydra-Multi [9] is the first multi-robot spatial
perception system capable of building a hierarchical 3D scene graph online
from different sensor data. Based on Hydra [26], it is a centralized
architecture that includes a hierarchical loop closure detection module based
on 3D scene graphs, a frame alignment module that estimates the initial poses
of the robots, and an alignment-optimize-reconcile framework that uses GNC to
optimize multi-robot 3D scene graphs. Recently, CURB-SG [10] has been
presented as the first solution to create large-scale 3D scene graphs of
dynamic urban scenes for automated driving, using collaborative mapping
techniques and leveraging panoptic LiDAR data. However, none of these
approaches are decentralized, which limits their scalability.

##  III System Overview

In Multi S-Graphs, each robot runs the fully decentralized Multi S-Graphs
system as is shown in Fig 2. Our system architecture is built around a
Situational Graph (S-Graph), a single multi-layered optimizable factor graph
that combines a pose graph and a scene graph with semantic-relational
concepts. This graph contains all the knowledge that is used for extracting
the key information needed for exchange and integrates information from other
agents, leading into a Multi-robot Situational Graph. The information that is
shared between agents is broadcasted into a common communication channel that
exchanges a minimal amount of data between them. In our system, we consider
the multi-robot kidnapped problem, where each robot is unaware of its location
on the map as well as the location of the other robots, so each robot creates
a map of the environment with respect to its starting point (origin) and
localizes the rest of the agents with respect to it. Our proposed system is
composed of four main modules:

1\. Local S-Graph Generation (Section IV). To generate the local S-Graph for
each robot, we use [8] which runs onboard each one using the odometry and 3D
LiDAR measurements of the robot. It also estimates the position and trajectory
followed by the robot while generating it.

2\. S-Graph Distillation (Section V). We marginalize the local S-graph
generated by each robot to only transmit semantic-relational information and
not the low-level information stored on each keyframe. Each distilled graph
includes a reference node that represents the origin of the local coordinated
system of each robot. This distilled S-graph is transmitted to the rest of the
robots.

3\. Room-Based Inter-Robot Loop Closure (Section VI). Relying only on the
generated semantic graph for loop closure can generate alignment errors in the
presence of symmetry in the environment. In order to combine the fine-grained
information of the point clouds and take advantage of the high-level semantic
information that each room contains, we generate a hybrid descriptor for each
room, a Room Descriptor. This module is in charge of two tasks: generating the
descriptors and finding appropriate room matches.

4\. Collaborative S-Graph Generation and Optimization (Section VII). This
module integrates the Distilled S-Graphs received from the other agents with
its own local S-Graph. The different graphs are connected together with the
loop closures generated by the previous module. The connected graphs are
globally optimized to generate the final collaborative situational graph.

##  IV Local Situational Graph

In our system, the situational awareness of each robot is encapsulated within
a situational graph whose entities have been designed to represent the
different elements that make up the layout of a building. In this work, we
rely on the S-Graphs+[8] algorithm for generating this Situational Graph,
based on the LiDAR and odometry measurements of the robots and estimating the
localization of the robot. These S-Graphs are four-layered optimizable
hierarchical graphs that contain the relevant information regarding the
structure of the building:

Keyframes Layer. It consists of robot poses factored as SE(3) nodes in the
agent map frame $A_{i}$ with pairwise odometry measurements constraining them.

Walls Layer. It consists of the planar wall surfaces extracted from the 3D
LiDAR measurements and factored using minimal plane parameterization. The
planes observed by their respective keyframes are factored using pose-plane
constraints.

Rooms Layer. It consists of two-wall rooms (corridors) or four-wall rooms,
each constraining either two or four detected walls, respectively.

Floors Layer. It consists of a floor node positioned in the center of the
current floor.

##  V Situational Graph Distillation

To reduce the amount of data that has to be interchanged between robots, we
extract the most meaningful information from the local S-Graph. This graph
encodes higher-level layers of the S-Graph and locates them with respect to
the origin node of each robot, which enables a minimal but meaningful
information exchange about the structure of the building. The Distilled
S-Graph is organized in the following layers:

Origin Layer. The origin node of each Distilled S-Graph, it represents the
origin of the coordinated system of each robot. All the rest of the elements
of the graph are located with respect to this node.

Walls Layer. The estimation and covariances of the walls extracted from the
S-Graph of each agent. The edges connecting the planes with their
corresponding keyframe nodes are replaced by an edge to the origin vertex.

Rooms Layer. The estimation of the four-wall room vertex detected by each
agent and the edges connecting the rooms to their four respective wall nodes.

Floors Layer. It consists of a floor node positioned in the center of the
current floor.

##  VI Room-Based Loop Closure

In order to connect the Local S-Graph with the external Distilled S-Graphs a
loop closure method is required. To avoid errors aligning the robot positions
in very symmetric situations, like a corridor with multiple rooms, one on side
of the order, we cannot only rely on the structural information stored in the
Distilled S-Graphs, more fine-grained information may be needed to break the
symmetry and decide if two rooms are the same or not.

###  VI-A Room descriptor generator

We present a hybrid descriptor, a Room Descriptor that integrates the semantic
information of each room with a Room Centric point cloud based descriptor,
which enhances the robustness and accuracy of the loop closure algorithm by a
small increase in the data transferred. An example of a Room Descriptor is
shown in Fig. 3.

Figure 3: Room Descriptor (right) obtained from a Room Centric point
cloud(left) by using a Scan Context. The value of each cell in the descriptor
is the maximum height of the points within a corresponding bin.

To generate these descriptors, we rely on the Scan Context descriptor [27].
This is an egocentric, yaw-invariant, point cloud descriptor that has
demonstrated state-of-the-art results, given its simplicity and fast
convergence time. The main drawback of this descriptor is that it is sensitive
to linear motions. To solve this, we take advantage of the semantic
information in the room by generating a Scan Context descriptor from the
center of each room, avoiding translation errors. To generate the room
descriptor, we need a Room Centric point cloud, which is a point cloud built
by combining all the point clouds of the keyframes within a room. Each room
keyframe $R_{k_{i}}$ can be expressed as:

$R_{k_{i}}=U\\{^{R_{i}}K_{j}\\}\quad;\quad\forall j\;|\;K_{j}\in R_{i}$ (1)

where ${}^{R_{i}}K_{j}$ represents the point cloud associated with the
keyframe $K_{j}$ in the $R_{i}$ frame (a frame located in the center of the
room $i$).

To obtain the room descriptor $R_{d_{i}}$ from a room keyframe $R_{k_{i}}$ we
first down-sample $R_{k_{i}}$ with a fixed voxel size to homogenize the number
of points for each room. Finally, the Scan Context descriptor of each room
keyframe $R_{k_{i}}$ is computed to create the room descriptor $R_{d_{i}}$:

$R_{d_{i}}=SC(\phi(R_{k_{i}}))$ (2)

where $\phi(R_{k_{i}})$ represents the down-sampled room keyframe cloud, and
$SC(\vec{X}):R^{n\times 3}\rightarrow R^{n_{s}\times n_{r}}$ is the Scan
Context function obtaining the descriptor for a given point cloud.

###  VI-B Loop Closure detection

In order to generate good candidates for alignment, we leverage the room
descriptors to match rooms that are used for connecting the local S-Graph with
the external distilled graphs, generating a global alignment of each robot
coordinate system. Room matching is performed in a two-step process:

Scan Context Matching: Each robot receives and stores the room descriptors of
the rest of the agents, trying to find a suitable match using the Scan Context
distance [21].

Fine Alignment: Whenever a match is found between the robot and other agents’
room, it tries to obtain an improved transform using the Room Centric Point
cloud that originates the Scan Context. For this, the robot asks for the down-
sampled point cloud and uses a VGICP[28] registration algorithm. The validity
of the relative transform is determined by the alignment distance and the
matching threshold $t_{d}$.

If a match is found, the room match with the relative transformation between
rooms is sent into the following module (Section V) to connect the different
graphs.

##  VII Collaborative Situational Graph

The final module integrates the Local S-Graph with the Distilled S-Graphs,
using the loop closures provided by the previous module, generating a
Collaborative S-Graph. During this Collaborative S-Graph generation, two
different stages can be found:

Isolated Graphs: At startup, this module stores the information from the Local
S-Graph and the Distilled S-Graphs received by the other robots but, since the
robots do not know where each one has started, it cannot combine the different
graphs. At this stage, each external distilled S-Graph has its origin layer
connected to the walls and rooms layer, but this origin layer is “free”, as
there are no connections with the local S-Graph of the robot, resulting in
multiple disconnected graphs. As long as new information is received, these
graphs are updated.

Collaborative Graph: If a room match is found using the room matching step
(Section VI), we formulate the factors between the local s-graph and the
distilled s-graphs in the 2 steps. In the first step, a room-to-room factor is
created for the matched rooms. For the given matched rooms, lower-level wall-
to-wall factors are established, which robustify the alignment of the graphs.
Whenever local S-Graphs and external distilled S-Graphs are connected with
appropriate factors, a common optimization is performed similarly to [8].
After this optimization, the external graphs are aligned with the robot’s
local coordinate frame so that the information provided by the other robots is
integrated into the collaborative S-graph, using the same coordinated frame as
the local robot for representing the different entities of the external
distilled graphs, as can be seen in Fig. 1.

##  VIII Experimental Validation

ATE [cm] | 2 Robots
---|---
Algorithm | C1F0s | C1F2s | SE1 | Avg
LAMP 2.0 | 9.66 | 8.10 | 6.27 | 8.01 $\pm$ 1.69
DCL-SLAM | 31.15 | 33.81 | 38.43 | 34.46 $\pm$ 3.68
Disco-SLAM | 35.81 | 38.45 | 45.03 | 39.76 $\pm$ 4.75
Swarm-SLAM | 119.95 | 78.08 | 213.09 | 137.04 $\pm$ 69.11
Multi S-Graphs (ours) | 3.64 | 1.39 | 1.50 |  2.17 $\pm$ 1.26
TABLE I: Absolute Trajectory Error (ATE) [cm] for our simulation experiments.
The best results are boldfaced.

###  VIII-A Methodology

We have selected the following state-of-the-art lidar-based distributed CSLAM
algorithms for comparison due to the availability of their code: DCL-SLAM
[23], Swarm-SLAM [18], and Disco-SLAM [29]. Additionally, we also challenge
our algorithm against a centralized CSLAM, LAMP 2.0 [11], because centralized
algorithms perform better than distributed ones when the number of robots is
small.

The experiments were conducted with quadruped robots equipped with LiDAR in
structured environments in the context of the “multi-robot kidnapped problem”,
where the initial positions of the robots were unknown, with the exception of
LAMP 2.0, as it requires prior knowledge of the initial positions of the
robots within the environment.

We conducted experiments in simulated and real-world scenarios. In simulation,
we present our results in terms of the Absolute Trajectory Error (ATE)
compared to the provided ground truth. In real-world experiments, we report
the Root Mean Square Error (RMSE) of the estimated 3D maps compared to the
actual 3D map derived from the architectural plans. We also performed an
analysis of the data exchanged between the agents for each scenario. Along
with this, we performed an ablation study to evaluate the contribution of the
different hierarchical factors between the local S-Graph and the distilled
S-Graphs in terms of accuracy and data transmission.

Simulated Data. We employed the Gazebo3 physics simulator to replicate indoor
settings for our experiments. In all these simulated scenarios, we relied on
LiDAR data for odometry estimation. Our study encompassed a total of three
simulated experiments, out of which C1F0 and C1F2 were constructed using 3D
mesh representations of real architectural plans, and SE1 is a simulated
environment mimicking common indoor layouts with varying room configurations.

(a) C1F0s

(b) C1F2s

(c) SE1

Figure 4: Simulated experiments, showing the trajectory and the point cloud map generated for each robot Point Cloud RMSE [cm] | 2 Robots | 3 Robots
---|---|---
Algorithm | C1F1 | C1F2 | C2F2 | C3F1 | C3F2 | Avg | C2F2
LAMP 2.0 | 61.49 | 23.61 | 31.89 | 30.46 | 40.05 | 37.50 $\pm$ 14.63 | 35.34
Swarm-SLAM | 75.45 | 94.60 | 147.22 | 40.36 | 36.42 | 78.81 $\pm$ 45.32 | 158.60
Multi S-Graphs (ours) | 27.03 | 15.12 | 17.73 | 21.04 | 21.58 |  20.18 $\pm$ 4.49 | 20.86
TABLE II: Point cloud RMSE [cm] for our in-house real experiments. The best
results are boldfaced.

Real-world Data. The datasets utilized in our experiments consist of a
collection of in-house datasets acquired from a construction site: C1F1, C1F2,
C3F1, C3F2, and C2F2. In addition, an experiment with 3 robots was performed
on the C2F2 stage enabled by the size of the scenario. To ensure a fair
comparison among the methods, we leverage the robot encoder odometry data,
which is available due to the presence of physical encoders on the robot, and
apply it consistently across all approaches. Unfortunately, our real-world
datasets do not include IMU data and consequently, algorithms that rely
heavily on IMU, such as DCL-SLAM and Disco-SLAM, could not be evaluated.

Ablation Study. In this study, we performed a thorough analysis of the
contribution of the use of hierarchical graph factors (Section VII) and the
influence of the use of Room Centric point cloud (Section VI) in the precision
of the graph alignment, along with the bandwidth exchanged. The ablated stages
are described below.

Rooms: The matched room entities between robots are connected using room-to-
room edges without fine alignment.

Rooms with Fine Alignment: Room-to-room matching is improved with fine
alignment between the room point clouds.

Rooms and Walls: Walls are added to the room-to-room connection using wall-to-
wall edges without fine alignment.

Rooms and Walls with Fine Alignment (Full algorithm): Room-to-room matching
with wall-to-wall edges and fine alignment.

When Fine Alignment (Subsection VI-B) is not performed in loop closure, no
point cloud information of the room is exchanged between robots.

Data Exchange [MB] | 2 Robots
---|---
Algorithm | C1F0s | C1F2s | SE1
LAMP 2.0 | 3.23 | 3.69 | 7.68
DCL-SLAM | 25.20 | 24.89 | 41.54
Disco-SLAM | 30.28 | 32.36 | 45.69
Swarm-SLAM | 11.31 | 14.40 | 20.80
Multi S-Graphs (ours) | 0.53 | 0.95 | 1.08
TABLE III: Data exchanged [MB] between agents in simulation experiments. The
best results are boldfaced.

(a) C1F1

(b) C1F2

(c) C3F1

(d) C3F2

(e) C2F2

Figure 5: Real experiment scenarios, showing the trajectory and the point
cloud map generated for each robot. In (e) the experiment was run with 3
robots.

###  VIII-B Experimental Setup

The robot used for generating the datasets is a Boston Dynamics Spot with a
Velodyne VLP-16 onboard. The experiments were carried out using a laptop
computer with an Intel i7-10870H (8 cores, 2.2 GHz) with 32 GB of RAM memory.
Multi S-Graphs is developed under S-Graphs with some code refactoring in the
implementation and uses g2o library [30] for the factor graphs implementation
and ROS and ROS 2 nodes for implementing the algorithms.

###  VIII-C Results and Discussions

Simulated Data. Fig. 4 shows the qualitative results of Multi S-Graphs
obtained during the simulated experiments. The outcomes presented in Table I
show that Multi S-Graph algorithm exhibits a lower Average Trajectory Error
(ATE) for the aggregated robot trajectory compared with the selected state-of-
the-art (SOTA) CSLAM algorithms. Our approach outperformed all other
decentralized algorithms, reducing the accuracy error by more than $90\%$
($93.7\%$, $94.5\%$, and $98.4\%$ for DCL-SLAM, Disco-SLAM, and Swarm-SLAM
respectively). It also achieved better accuracy than LAMP 2.0, with $72.9\%$
less error, which requires precise initial poses of the robots. The lack of
features in the simulation environment causes measurement errors to adversely
affect optimization. The extraction of semantic information specific to this
type of environment by our algorithm overcomes this source of error.

In addition, our approach reduces the exchange of information between the
agents by $94.50\%$, $97.20\%$, and $97.64\%$ for Swarm-SLAM, DCL-SLAM, and
Disco-SLAM, respectively, and $81.3\%$ for LAMP 2.0 (see Table III). This can
be attributed to the effective use of semantic information to reduce the
amount of data exchanged.

Real-world Data. Table II presents the outcomes of the real-world experiments.
Results from real datasets resemble the previous simulation results, with our
algorithm showing $78.81\%$ improved performance over Swarm-SLAM in map
matching accuracy, and $45.3\%$ over LAMP 2.0. In this case, although the
accuracy of the extracted semantic features slightly decreases due to other
elements present in real environments, the use of semantic-relational
information of room-walls and their point clouds allows our approach to obtain
better results than the other algorithms, achieving average reconstruction
error of 20.5 cm that slightly vary in the different scenarios.

Validation in real experiments concludes what has been demonstrated in
simulations, with our approach achieving a high level of precision in
reconstructing the building map (see Fig. 5). Table IV shows the amount of
data exchanged between agents. In this case, our approach reduces by $84.89\%$
and $93.34\%$ the amount of data exchanged between robots compared to LAMP 2.0
and Swarm-SLAM, respectively.

Data Exchange [MB] | 2 Robots | 3 Robots
---|---|---
Algorithm | C1F1 | C1F2 | C2F2 | C3F1 | C3F2 | C2F2
LAMP 2.0 | 1.89 | 3.72 | 19.03 | 8.18 | 8.59 | 20.48
Swarm-SLAM | 4.31 | 8.80 | 44.84 | 17.53 | 17.65 | 48.79
Multi S-Graphs (ours) | 0.26 | 0.82 | 3.50 | 1.12 | 0.66 | 5.73
TABLE IV: Data exchanged [MB] between agents in real experiments. The best
results are boldfaced.

Ablation Study. The results of this study are collected in Table V. We can see
that the utilization of hierarchical optimization, which establishes
relationships between the walls of two rooms among agents (Rooms and Planes),
means a significant improvement of accuracy, reducing the ATE by $25.6\%$ with
an increase in the amount of data by $77\%$. On the other hand, the use of
Fine alignment improves the performance by $73.6\%$ and $25.6\%$ over the
Rooms and Rooms and Walls configurations, respectively, with a 40 times higher
data exchange requirement. In general, fine alignment techniques perform
better compared to their non-fine alignment counterparts, primarily due to the
limited angular resolution of the Scan Context, which is insufficient for
precise alignment (see Section VI). Furthermore, the use of wall-to-wall
factors contributes to alignment improvement, consequently significantly
enhancing overall performance. Consequently, the best performance is obtained
by combining the semantic information extracted from the walls with fine
alignment using the Room Centric point clouds, Rooms and Walls with Fine
alignment, improving the performance by up to $74.7\%$. However, due to the
larger amount of data exchanged required, when communication channels are
limited, Rooms and Walls, which only use semantic information, may be an
interesting solution. This makes it possible to avoid sending heavy point
cloud messages without a significant decrease in accuracy.

| C1F0s | C1F2s | SE1
---|---|---|---
Algorithm | ATE |  Data Shared | ATE |  Data Shared | ATE |  Data Shared
Rooms | 9.78 | 12.88 | 1.99 | 18.90 | 8.06 | 26.46
Rooms with FA | 3.78 | 524.32 | 1.42 | 946.91 | 1.62 | 1069.03
Rooms $\&$ Walls | 5.33 | 22.81 | 1.72 | 27.38 | 1.73 | 37.85
Rooms $\&$ Walls with FA | 3.64 | 537.53 | 1.39 | 955.39 | 1.50 | 1080.41
TABLE V: Ablation study of the ATE [cm] and data shared [MB] for simulated
datasets with 2 robots, FA means Fine Alignment. The best results are
boldfaced.

In Fig. 6 we can see on a logarithmic scale how the graph information
(composed mainly of walls and room graph nodes) is negligible compared to the
room point clouds. This observation highlights that point clouds lead to a
substantial increase in transmitted data. Although the growth in the graph
data during map exploration does not result in a significant increase in data
volume, the cost associated with point clouds significantly escalates.

Figure 6: Accumulated data shared between agents, consisting of Walls Nodes
(Wall GN) and Room Nodes (Room GN) for the Semantic Graph, and the Room Scan
Contexts (Room SC) and Room Centric point clouds (Room PC) that form the Room
Descriptors.

##  IX Conclusions and Future Work

In this work a distributed CSLAM system is presented, leveraging the semantic-
relational features extracted by the S-Graphs [7], [8], in order to filter and
reduce the amount of data that has to be transmitted between robots while
outperforming state-of-the-art mapping and positioning accuracy in structured
environments.

We tested our algorithm for a map generation task in multiple scenarios,
simulated and real, outperforming other state-of-the-art lidar-based
collaborative SLAM algorithms in terms of precision and bandwidth, reducing
the trajectory and map reconstruction error by more than $90\%$ while saving
$95\%$ of the data exchanged between robots. As our approach reduces the
amount of data exchanged between agents, it makes it suitable for low-
bandwidth scenarios, as well as for a large number of robots using the same
communication channel.

The main drawback is the dependence on semantic-relational structures, defined
in our case as four-walled rooms existing in building-like environments, which
are not always easy to extract.

For future work, a more generic way of finding alignment between Situational
Graphs should be found to increase the variety of scenarios in which Multi
S-Graphs can be used. Including other sensory input for the generation of the
S-Graph and the descriptors is required to allow the use of this system for
heterogeneous robotic systems.

## References

  * [1] P. Y. Lajoie, B. Ramtoula, Y. Chang, L. Carlone, and G. Beltrame, “Door-slam: Distributed, online, and outlier resilient slam for robotic teams,” _IEEE Robotics and Automation Letters_ , vol. 5, pp. 1656–1663, 4 2020.
  * [2] S. Zhong, Y. Qi, Z. Chen, J. Wu, H. Chen, and M. Liu, “Dcl-slam: A distributed collaborative lidar slam framework for a robotic swarm,” _arXiv preprint arXiv:2210.11978_ , 2022.
  * [3] Y. Huang, T. Shan, F. Chen, and B. Englot, “Disco-slam: Distributed scan context-enabled multi-robot lidar slam with two-stage global-local graph optimization,” _IEEE Robotics and Automation Letters_ , vol. 7, pp. 1150–1157, 4 2022.
  * [4] R. Azzam, T. Taha, S. Huang, and Y. Zweiri, “Feature-based visual simultaneous localization and mapping: A survey,” _SN Applied Sciences_ , vol. 2, pp. 1–24, 2020.
  * [5] J. G. Mangelson, D. Dominic, R. M. Eustice, and R. Vasudevan, “Pairwise consistent measurement set maximization for robust multi-robot map merging,” in _2018 IEEE international conference on robotics and automation (ICRA)_. IEEE, 2018, pp. 2916–2923.
  * [6] N. Hughes, Y. Chang, and L. Carlone, “Hydra: A real-time spatial perception system for 3d scene graph construction and optimization,” 1 2022. [Online]. Available: https://arxiv.org/abs/2201.13360v2
  * [7] H. Bavle, J. L. Sanchez-Lopez, M. Shaheer, J. Civera, and H. Voos, “Situational graphs for robot navigation in structured indoor environments,” _IEEE Robotics and Automation Letters_ , vol. 7, no. 4, pp. 9107–9114, 2022.
  * [8] ——, “S-graphs+: Real-time localization and mapping leveraging hierarchical representations,” _IEEE Robotics and Automation Letters_ , vol. 8, no. 8, pp. 4927–4934, 2023.
  * [9] Y. Chang, N. Hughes, A. Ray, and L. Carlone, “Hydra-multi: Collaborative online construction of 3d scene graphs with multi-robot teams,” 2023.
  * [10] E. Greve, M. Büchner, N. Vödisch, W. Burgard, and A. Valada, “Collaborative dynamic 3d scene graphs for automated driving,” 2023.
  * [11] Y. Chang, K. Ebadi, C. E. Denniston, M. F. Ginting, A. Rosinol, A. Reinke, M. Palieri, J. Shi, A. Chatterjee, B. Morrell, A. akbar Agha-mohammadi, and L. Carlone, “Lamp 2.0: A robust multi-robot slam system for operation in challenging large-scale underground environments,” 2022.
  * [12] A. Cramariuc, L. Bernreiter, F. Tschopp, M. Fehr, V. Reijgwart, J. Nieto, R. Siegwart, and C. Cadena, “maplab 2.0 – a modular and multi-modal mapping framework,” _IEEE Robotics and Automation Letters_ , vol. 8, no. 2, p. 520–527, Feb 2023. [Online]. Available: http://dx.doi.org/10.1109/LRA.2022.3227865
  * [13] M. Patel, M. Karrer, P. Bänninger, and M. Chli, “Covins-g: A generic back-end for collaborative visual-inertial slam,” _2023 IEEE International Conference on Robotics and Automation (ICRA)_ , May 2023. [Online]. Available: http://dx.doi.org/10.1109/ICRA48891.2023.10160938
  * [14] P. Schmuck, T. Ziegler, M. Karrer, J. Perraudin, and M. Chli, “Covins: Visual-inertial slam for centralized collaboration,” in _2021 IEEE International Symposium on Mixed and Augmented Reality Adjunct (ISMAR-Adjunct)_ , 2021, pp. 171–176.
  * [15] I. Deutsch, M. Liu, and R. Siegwart, “A framework for multi-robot pose graph slam,” _2016 IEEE International Conference on Real-Time Computing and Robotics, RCAR 2016_ , pp. 567–572, 12 2016.
  * [16] Y. Tian, Y. Chang, F. Herrera Arias, C. Nieto-Granda, J. P. How, and L. Carlone, “Kimera-multi: Robust, distributed, dense metric-semantic slam for multi-robot systems,” _IEEE Transactions on Robotics_ , vol. 38, no. 4, p. 2022–2038, Aug 2022. [Online]. Available: http://dx.doi.org/10.1109/tro.2021.3137751
  * [17] A. Rosinol, M. Abate, Y. Chang, and L. Carlone, “Kimera: an open-source library for real-time metric-semantic localization and mapping,” _2020 IEEE International Conference on Robotics and Automation (ICRA)_ , May 2020. [Online]. Available: http://dx.doi.org/10.1109/ICRA40945.2020.9196885
  * [18] P.-Y. Lajoie and G. Beltrame, “Swarm-slam : Sparse decentralized collaborative simultaneous localization and mapping framework for multi-robot systems,” 2023.
  * [19] G. Berton, C. Masone, and B. Caputo, “Rethinking visual geo-localization for large-scale applications,” _2022 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , Jun 2022. [Online]. Available: http://dx.doi.org/10.1109/CVPR52688.2022.00483
  * [20] R. Arandjelović, P. Gronat, A. Torii, T. Pajdla, and J. Sivic, “Netvlad: Cnn architecture for weakly supervised place recognition,” _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , vol. 40, no. 6, pp. 1437–1451, 2018.
  * [21] G. Kim and A. Kim, “Scan context: Egocentric spatial descriptor for place recognition within 3d point cloud map,” in _2018 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_ , 2018, pp. 4802–4809.
  * [22] Y. Huang, T. Shan, F. Chen, and B. Englot, “Disco-slam: Distributed scan context-enabled multi-robot lidar slam with two-stage global-local graph optimization,” _IEEE Robotics and Automation Letters_ , vol. 7, no. 2, pp. 1150–1157, 2022.
  * [23] S. Zhong, Y. Qi, Z. Chen, J. Wu, H. Chen, and M. Liu, “Dcl-slam: A distributed collaborative lidar slam framework for a robotic swarm,” 2022.
  * [24] Y. Wang, Z. Sun, C.-Z. Xu, S. E. Sarma, J. Yang, and H. Kong, “Lidar iris for loop-closure detection,” _2020 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_ , Oct 2020. [Online]. Available: http://dx.doi.org/10.1109/IROS45743.2020.9341010
  * [25] P. Bänninger, I. Alzugaray, M. Karrer, and M. Chli, “Cross-agent relocalization for decentralized collaborative slam,” in _2023 IEEE International Conference on Robotics and Automation (ICRA)_ , 2023, pp. 5551–5557.
  * [26] N. Hughes, Y. Chang, and L. Carlone, “Hydra: A real-time spatial perception system for 3D scene graph construction and optimization,” 2022.
  * [27] G. Kim and A. Kim, “Scan context: Egocentric spatial descriptor for place recognition within 3d point cloud map,” in _2018 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_. IEEE, 2018, pp. 4802–4809.
  * [28] K. Koide, M. Yokozuka, S. Oishi, and A. Banno, “Voxelized gicp for fast and accurate 3d point cloud registration,” in _2021 IEEE International Conference on Robotics and Automation (ICRA)_. IEEE, 2021, pp. 11 054–11 059.
  * [29] Y. Huang, T. Shan, F. Chen, and B. Englot, “Disco-slam: distributed scan context-enabled multi-robot lidar slam with two-stage global-local graph optimization,” _IEEE Robotics and Automation Letters_ , vol. 7, no. 2, pp. 1150–1157, 2021.
  * [30] R. Kümmerle, G. Grisetti, H. Strasdat, K. Konolige, and W. Burgard, “G2o: A general framework for graph optimization,” in _2011 IEEE International Conference on Robotics and Automation_ , 2011, pp. 3607–3613.


# The Deepest Cycle of a Random Mapping: a Problem Proposed by Steven Finch

Ljuben Mutafchiev
American University in Bulgaria, 2700 Blagoevgrad, Bulgaria
and Institute of Mathematics and Informatics of the
Bulgarian Academy of Sciences
<EMAIL_ADDRESS>
###### Abstract

Let $\mathcal{T}_{n}$ be the set of all mappings
$T:\\{1,2,\ldots,n\\}\to\\{1,2,\ldots,n\\}$. The corresponding graph of $T$ is
a union of disjoint connected unicyclic components. We assume that each
$T\in\mathcal{T}_{n}$ is chosen uniformly at random (i.e., with probability
$n^{-n}$). The cycle of $T$ contained within its largest component is called
the deepest one. For any $T\in\mathcal{T}_{n}$, let $\nu_{n}=\nu_{n}(T)$
denote the length of this cycle. In this paper, we find the limits of the
expectation and variance of $\nu_{n}/\sqrt{n}$ as $n\to\infty$. For $n$ large
enough, we also show that nearly $55\%$ of all cyclic vertices of a random
mapping $T\in\mathcal{T}_{n}$ lie in its deepest cycle and that a vertex from
the longest cycle of $T$ does not belong to its largest component with
approximate probability $0.075$.

Mathematics Subject Classifications: 60C05, 05C80

Key words: random functional graph, deepest cycle, largest component, longest
cycle, aymptotic

##  1 Introduction and Statement of the Main Result

We start with some notation that will be used freely in the text.

For a positive integer $n$, let $\mathcal{T}_{n}$ denote the set of all
mappings $T:[n]\to[n]$, where $[n]:=\\{1,2,\ldots,n\\}$. It is clear that the
cardinality $|\mathcal{T}_{n}|$ of $\mathcal{T}_{n}$ is $n^{n}$. A mapping
$T\in\mathcal{T}_{n}$ corresponds to a directed graph $G_{T}$, called
functional digraph, with edges $(i,T(i)),i\in[n]$, where every vertex
$i\in[n]$ has out-degree $1$. $G_{T}$ is a union of disjoint connected
components. A vertex $i$ is called cyclic if, for the $m$-fold composition
$T^{(m)}$ of $T$, we have $T^{(m)}(i)=i$ for some $m\geq 1$. Since the
vertices of $G_{T}$ have out-degree $1$, each component contains a unique
directed cycle and directed trees attached to the cyclic vertices. Let
$\lambda_{n}=\lambda_{n}(T),T\in\mathcal{T}_{n}$, denote the number of the
cyclic vertices in $G_{T}$. We introduce the uniform probability measure
$\mathbb{P}$ on the set $\mathcal{T}_{n}$. That is, we assign the probability
$n^{-n}$ to each $T\in\mathcal{T}_{n}$. In this way, $\lambda_{n}$, as well as
any other numerical characteristic of $G_{T}$, becomes a random variable (or,
a statistic in the sense of random generation of mappings from
$\mathcal{T}_{n}$). The size of the largest component of $G_{T}$ will be
further denoted by $\mu_{n}=\mu_{n}(T)$. The cycle contained within the
largest component of $G_{T}$ is called the deepest one. Let
$\nu_{n}=\nu_{n}(T)$ denote its length. In [7], Finch suggests to study the
asymptotic behavior of $\nu_{n}$ as $n\to\infty$. The main goal of this work
is to find the asymptotics of the mean and variance of the size of the deepest
cycle $\nu_{n}$.

There is a substantial probabilistic literature on random mappings. Here we
give only references to the popular monographs [20, 14, 2]. For large $n$,
some properties of the functional digraphs $G_{T},T\in\mathcal{T}_{n}$, are
also used in analysis of algorithms. For example, the cyclic structure of
random mappings is closely related to algorithms for integer factorization
and, in particular, to the Pollard’s $\rho$-algorithm; see, e.g., [17, 4, 9,
15]. A comprehensive survey on this subject and related topics, may be found
in [12, Section 4.5.4]. Random mapping statistics are also relevant to some
algorithms for generic attacks on iterated hash constructions; see [3].

Throughout the paper the notation $\mathbb{E}$ and $\mathbb{V}ar$ stand for
the expectation and variance with respect to the uniform probability measure
$\mathbb{P}$ on the set $\mathcal{T}_{n}$, respectively. Below we state our
main result on the deepest cycle of a random mapping.

###### Theorem 1

Let $E_{1}(s)=\int_{s}^{\infty}\frac{e^{-t}}{t}dt,s>0,$ be the exponential
integral function. Then we have

(i)

$\lim_{n\to\infty}\frac{1}{\sqrt{n}}\mathbb{E}(\nu_{n})=\frac{1}{\sqrt{2}}\int_{0}^{\infty}\frac{\exp{(-s-\frac{1}{2}E_{1}(s)})}{\sqrt{s}}ds\approx
0.6884;$

(ii)

$\lim_{n\to\infty}\frac{1}{n}\mathbb{V}ar(\nu_{n})\approx 0.2839.$

The proof of this theorem is given in Section 2. In Section 3, we consider a
sampling experiment: we assume that a vertex of the random functional digraph
$G_{T},T\in\mathcal{T}_{n}$, is chosen uniformly at random from the set $[n]$.
We give interpretations arising from this random choice. We conclude Section 3
with an open problem.

##  2 Proof of Theorem 1

A mapping is said to be indecomposable (or connected) if it possesses exactly
one component. Asymptotic results related to the functional graphs of
indecomposable mappings has been obtained long ago by R$\acute{e}$nyi [19]. We
base our proof on combinatorial and probabilistic arguments and on properties
of the limiting distribution function of the size of the largest component
$\mu_{n}$.

Consider first the subset $\mathcal{T}_{n}^{\prime}\subset\mathcal{T}_{n}$ of
the indecomposable mappings. The cardinality $|\mathcal{T}_{n}^{\prime}|$ of
the set $\mathcal{T}_{n}^{\prime}$ was determined by Katz [11], who showed
that

$|\mathcal{T}_{n}^{\prime}|=(n-1)!\sum_{k=0}^{n-1}\frac{n^{k}}{k!}.$

For the sake of convenience, we set

$A_{n}:=\sum_{k=0}^{n-1}\frac{n^{k}}{k!}=\frac{|\mathcal{T}_{n}^{\prime}|}{(n-1)!}.$
(1)

Multiplying both sides of (1) by $e^{-n}$, we observe that its right-hand side
is a sum of probabilities of a Poisson distributed random variable with mean
$n$. Applying the normal approximation of the Poisson distribution in
conjunction with the Berry-Esseen bound on the rate of convergence in this
approximation (see, e.g., [6, Chapter XVI, Section 5]), we conclude that

$e^{-n}A_{n}=\frac{1}{2}+O\left(\frac{1}{\sqrt{n}}\right)\quad\text{as}\quad
n\to\infty.$ (2)

Now, we introduce the uniform probability measure $\mathcal{P}$ on the set
$\mathcal{T}_{n}^{\prime}$. Let
$\nu_{n}^{\prime}=\nu_{n}^{\prime}(T),T\in\mathcal{T}_{n}^{\prime}$, denote
the count of the cyclic vertices in $T$. R$\acute{e}$nyi [19] showed that,
with respect to $\mathcal{P}$, $\nu_{n}^{\prime}/\sqrt{n}$ converges in
distribution to the random variable $|\xi|$, where $\xi$ has standard normal
distribution. In addition, he also established a local limit theorem for
$\nu_{n}^{\prime}/\sqrt{n}$ and showed that

$\mathcal{E}(\nu_{n}^{\prime})\sim\sqrt{\frac{2n}{\pi}}\quad\text{as}\quad
n\to\infty,$ (3)

where $\mathcal{E}$ denotes the expectation with respect to the probability
measure $\mathcal{P}$.

In the computation of $\mathbb{E}(\nu_{n})$, we shall use conditional
expectations. It is clear that, for $m\leq n$, we have
$\mathbb{E}(\nu_{n}|\mu_{n}=m)=\mathcal{E}(\nu_{m}^{\prime})$, where $\mu_{n}$
stands for the largest component size of a mapping from $\mathcal{T}_{n}$.
Decomposing the expectation of $\nu_{n}$ into a weighted sum of conditional
expectations, we obtain

$\mathbb{E}(\nu_{n})=\sum_{m=1}^{n}\mathbb{E}(\nu_{n}|\mu_{n}=m)\mathbb{P}(\mu_{n}=m)=\sum_{m=1}^{n}\mathcal{E}(\nu_{m}^{\prime})\mathbb{P}(\mu_{n}=m).$
(4)

We now move to the computation of $\mathcal{E}(\nu_{n}^{\prime})$. We notice
that the number of forests on $n$ vertices containing $k$ rooted trees is
${n-1\choose{k-1}}n^{n-k}$, where $1\leq k\leq n$ (see, e.g., [20, Chapter 6,
formula (0.5)]. Multiplying this number by $(k-1)!$ (the number of ways to
construct a cycle on $k$ vertices) and dividing the product by
$|\mathcal{T}_{n}^{\prime}|$, we deduce the probability mass function of
$\nu_{n}^{\prime}$:

$\mathcal{P}(\nu_{n}^{\prime}=k)=\frac{n^{n-k}}{(n-k)!A_{n}},\quad 1\leq k\leq
n,$

where $A_{n}$ is the quantity given by (1). Straightforward computation shows
that

$\mathcal{E}(\nu_{n}^{\prime})=\sum_{k=1}^{n}\frac{kn^{n-k}}{(n-k)!A_{n}}=\frac{n^{n}}{(n-1)!A_{n}}.$
(5)

Applying Stirling’s formula and (2) to the right-hand side of (5), we obtain

$\mathcal{E}(\nu_{n}^{\prime})=\sqrt{\frac{2n}{\pi}}\left(1+O\left(\frac{1}{\sqrt{n}}\right)\right)=\sqrt{\frac{2n}{\pi}}+O(1)\quad\text{as}\quad
n\to\infty.$ (6)

This asymptotic estimate is slightly more precise than that given by (3) due
to the Berry-Esseen bound applied to the normal approximation of a Poisson
distribution with parameter $n$.

We show next that an elementary argument leads to a surprisingly simple exact
expression for the second moment of $\nu_{m}^{\prime},2\leq m\leq n$. We have

$\displaystyle\mathcal{E}(\nu_{m}^{\prime
2})=\frac{1}{A_{m}}\sum_{k=1}^{m}\frac{k^{2}m^{m-k}}{(m-k)!}=\frac{1}{A_{m}}\sum_{l=0}^{m-1}\frac{(m^{2}-2ml+l^{2})m^{l}}{l!}$
$\displaystyle=\frac{1}{A_{m}}\left(\sum_{l=0}^{m-1}\frac{m^{l+2}}{l!}-2\sum_{l=1}^{m-1}\frac{m^{l+1}}{(l-1)!}+\sum_{l=2}^{m-1}\frac{m^{l}}{(l-2)!}+\sum_{l=1}^{m-1}\frac{m^{l}}{(l-1)!}\right)$
$\displaystyle=\frac{1}{A_{m}}\left(\frac{m^{m+1}}{(m-1)!}+\sum_{l=2}^{m}\frac{m^{l}}{(l-2)!}-2\sum_{l=2}^{m}\frac{m^{l}}{(l-2)!}\right)$
$\displaystyle+\frac{1}{A_{m}}\left(\sum_{l=2}^{m}\frac{m^{l}}{(l-2)!}-\frac{m^{m}}{(m-2)!}+\sum_{l=1}^{m-1}\frac{m^{l}}{(l-1)!}\right)$
$\displaystyle=\frac{1}{A_{m}}\left(\frac{m^{m}}{(m-1)!}+\sum_{l=1}^{m-1}\frac{m^{l}}{(l-1)!}\right)=\frac{1}{A_{m}}\sum_{l=1}^{m}\frac{m^{l}}{(l-1)!}$
$\displaystyle=\frac{m}{A_{m}}\sum_{l=1}^{m}\frac{m^{l-1}}{(l-1)!}=\frac{m}{A_{m}}\sum_{k=0}^{m-1}\frac{m^{k}}{k!}=m,$
(7)

where in the last equality we have used (1).

Now, we proceed to the preliminaries concerning the largest component of a
random mapping. The limiting distribution of the size $\mu_{n}$ of the largest
component was first determined by Kolchin [13] (see also [14, Section 1.13]).
Arratia et al. [2] developed a unifying approach to the study of the component
spectrum of a large parametric class of decomposable combinatorial structures,
called logarithmic structures. These structures satisfy a condition, called
there logarithmic. It introduces a dependency on a parameter $\theta>0$. It is
shown [2, Section 6.1] that random mappings satisfy the logarithmic condition
with $\theta=1/2$. Therefore, in the material from [2, Sections 4.2 and 5.5]
that we shall present further, we restrict ourselves to this value of
$\theta$.

Consider the random variable $\eta$ whose probability density function
$p(x),x>0$, is given by

$p(x)=\frac{e^{-\gamma x}}{\sqrt{\pi
x}}\left(1+\sum_{k=1}^{\infty}\frac{(-1)^{k}}{2^{k}k!}\int\ldots\int_{I_{k}(x)}(1-\sum_{j=1}^{k}y_{j})^{-1/2}\frac{dy_{1}\ldots
dy_{k}}{y_{1}\ldots y_{k}}\right),$ (8)

where

$I_{k}(x):=\\{(y_{1},\ldots,y_{k}):y_{1}>x^{-1},\ldots,y_{k}>x^{-1},\sum_{j=1}^{k}y_{j}<1\\},$

and $\gamma\approx 0.5772$ denotes Euler’s constant. From [2, Theorem 4.6] it
follows that

$\varphi(s):=\int_{0}^{\infty}e^{-sx}p(x)dx=\exp{\left(-\frac{1}{2}\int_{0}^{1}\frac{1-e^{-sy}}{y}dy\right)}=\frac{e^{-\gamma/2}}{\sqrt{s}}e^{-\frac{1}{2}E_{1}(s)},$
(9)

where $E_{1}(s)$ denotes the exponential integral function introduced in
Theorem 1(i). The last equality in (9) follows from the classical identity

$\int_{0}^{s}\frac{1-e^{-y}}{y}dy=E_{1}(s)+\log{s}+\gamma,\quad s>0;$

see, e.g., [1, Section 5.1].

Let us now state the integral limit theorem for the size of the largest
component of a random mapping; see [2, Lemma 5.7].

###### Proposition 1

As $n\to\infty$, $\mu_{n}/n$ converges in distribution to a random variable
with distribution function $F$ given by

$F(x)=e^{\gamma/2}\sqrt{\pi/x}p(1/x),\quad x>0,$ (10)

where $p(x)$ is as defined in (8).

Watterson [22] observed that $p(x)$ satisfies the delay differential equation

$xp^{\prime}(x)+\frac{1}{2}p(x)+\frac{1}{2}p(x-1)=0\quad\text{\quad}\text{for}\quad
x>1,\quad p(x)=\frac{e^{-\gamma/2}}{\sqrt{\pi x}}\quad\text{for}\quad 0<x\leq
1.$ (11)

From (10) and (11) one can easily deduce the limiting probability density
function $f(x)$ of $\mu_{n}/n$. We have

$f(x)=\frac{1}{2}e^{\gamma/2}\sqrt{\pi}x^{-3/2}p\left(\frac{1}{x}-1\right),\quad
0<x\leq 1.$ (12)

Arratia et al. [2, Lemma 5.9] derive also a local limit theorem for $\mu_{n}$.
It is stated as follows.

###### Proposition 2

Suppose that $m\leq n$ satisfies $\frac{m}{n}\to x\in(0,1)$ as $n\to\infty$.
Then

$\mathbb{P}(\mu_{n}=m)=\frac{1}{n}f(x)(1+o(1)),$ (13)

where $f(x)$ is given by (12).

Proof of part (i). We divide both sides of (4) by $\sqrt{n}$ and break up the
range of summation writing

$\frac{1}{\sqrt{n}}\mathbb{E}(\nu_{n})=\frac{1}{\sqrt{n}}(S_{1}+S_{2}),$ (14)

where

$S_{1}=\sum_{1\leq
m\leq\frac{1}{4}\log{n}}\mathcal{E}(\nu_{m}^{\prime})\mathbb{P}(\mu_{n}=m)$
(15)

and

$S_{2}=\sum_{\frac{1}{4}\log{n}<m\leq
n}\mathcal{E}(\nu_{m}^{\prime})\mathbb{P}(\mu_{n}=m).$ (16)

For any $a>0$, let $Po(a)$ be a Poisson distributed random variable.
Furthermore, let $\mathbf{P}$ denote the Lebesgue measure on the Borel subsets
of $[0,\infty)$. Then, in view of (1) and (5), we can write

$\mathcal{E}(\nu_{m}^{\prime})=\frac{m^{m}e^{-m}}{(m-1)!\mathbf{P}(Po(m)\leq
m-1)},$ (17)

for any $m$ satisfying $1\leq m\leq n$. To obtain an upper bound for
$\mathcal{E}(\nu_{m}^{\prime})$, we proceed as follows. We multiply the
numerator and the denominator in the right-hand side of (17) by $\sqrt{2\pi
m}e^{1/(12m+1)}$ and then apply the well-known inequality for $m!$:

$m!>m^{m}e^{-m}\sqrt{2\pi m}e^{1/(12m+1)};$

see, for example, [5, Chapter II, Section 9]. Furthermore, for $m\geq 1$, the
Poisson probability in the denominator of (17) is uniformly bounded from below
by $\mathbf{P}(Po(m)=0)=e^{-m}$. Hence, for all $m,1\leq m\leq n$, we have

$\mathcal{E}(\nu_{m}^{\prime})<\frac{m!e^{m}}{(m-1)!\sqrt{2\pi
m}e^{1/(12m+1)}}<\sqrt{\frac{m}{2\pi}}e^{m}.$

It follows from this, for large enough $n$, that

$\displaystyle\frac{1}{\sqrt{n}}S_{1}\leq\frac{1}{\sqrt{2\pi}}\sum_{m\leq\frac{1}{4}\log{n}}\sqrt{\frac{m}{n}}e^{\frac{1}{4}\log{n}}\mathbb{P}(\mu_{n}=m)$
$\displaystyle\leq\frac{1}{2\sqrt{2\pi
n}}n^{1/4}\sqrt{\log{n}}\sum_{m\leq\frac{1}{4}\log{n}}1=O(n^{-1/4}\log^{3/2}{n})=o(1).$
(18)

The estimate of $\frac{1}{\sqrt{n}}S_{2}$ follows from Proposition 2 (the
local limit theorem (13)) in conjunction with (6). Thus, for large enough $n$,
we have

$\displaystyle\frac{1}{\sqrt{n}}S_{2}=\sqrt{\frac{2}{\pi}}\sum_{\frac{1}{4}\log{n}<m\leq
n}\sqrt{\frac{m}{n}}\frac{1}{n}f\left(\frac{m}{n}\right)(1+o(1))$ (19)
$\displaystyle+O\left(\frac{1}{\sqrt{n}}\sum_{\frac{1}{4}\log{n}<m\leq
n}\frac{1}{n}f\left(\frac{m}{n}\right)\right).$

Both integrals in the right-hand side of (19) represent the Riemann sums of
the integrals

$I:=\sqrt{\frac{2}{\pi}}\int_{0}^{1}\sqrt{x}f(x)dx$ (20)

and

$\int_{0}^{1}f(x)dx=1$ (21)

with step size $1/n$, respectively. Hence, combining (14) - (16) and (2) -
(21), we obtain

$\frac{1}{\sqrt{n}}\mathbb{E}(\nu_{n})=I+o(1),\quad n\to\infty.$ (22)

To complete the proof, it remains to evaluate the integral $I$. We first
replace $f(x)$ by its expression (12). Then, we set in (20) $y=\frac{1}{x}-1$.
Since $p(x)$ is the probability density function of the random variable
$\eta>0$, we can rewrite (20) as follows:

$I=\frac{e^{\gamma/2}}{\sqrt{2}}\int_{0}^{\infty}\frac{p(y)}{1+y}dy=\frac{e^{\gamma/2}}{\sqrt{2}}\mathbf{E}((1+\eta)^{-1}),$
(23)

where $\mathbf{E}$ denotes the expectation with respect to the Lebesgue
measure $\mathbf{P}$ on $[0,\infty)$. Recall that the Laplace transform
$\varphi(s)$ of $\eta$ is given by both right side expressions of (9).
Furthermore, an obvious computation shows that

$\int_{0}^{\infty}e^{-s}\varphi(s)ds=\mathbf{E}((1+\eta)^{-1}).$ (24)

Combining the last expression for $\varphi(s)$ in (9) with (23) and (24), we
obtain the required representation of $I$. Using Mathematica, version 12.0,
Finch [8] shows that

$I=0.6884050874956\ldots.$ (25)

Combining (22) and (25) completes the proof of part (i).

Proof of part(ii). The right sides of (4) and (2) imply that, for all $n$, we
have

$\mathbb{E}(\nu_{n}^{2})=\sum_{m=1}^{n}m\mathbb{P}(\mu_{n}=m)=\mathbb{E}(\mu_{n}).$

Hence

$\lim_{n\to\infty}\frac{1}{n}\mathbb{E}(\nu_{n}^{2})=\lim_{n\to\infty}\frac{1}{n}\mathbb{E}(\mu_{n})=0.7578230112\ldots,$

where the last numerical value was found by Gourdon [10, p.152] (see also [2,
Table 5.1]). Since
$\frac{1}{n}\mathbb{V}ar(\nu_{n})=\frac{1}{n}(\mathbb{E}(\nu_{n}^{2})-(\mathbb{E}(\nu_{n}))^{2})$,
the numerical result of part (ii) follows again from (22) and (25). Thus the
proof is complete.

##  3 Concluding Remarks

Suppose that a vertex $i\in[n]$ of the graph $G_{T},T\in\mathcal{T}_{n}$, is
chosen uniformly at random. The probability that $i$ possesses a certain
property (e.g., $i$ is a cyclic vertex, $i$ belongs to the largest component
of $G_{T}$, etc.) can be computed directly, using the total probability
formula. For example, the probability that a randomly chosen vertex is cyclic
equals
$\sum_{k=1}^{n}\frac{k}{n}\mathbb{P}(\lambda_{n}=k)=\frac{1}{n}\mathbb{E}(\lambda_{n})$
(recall that $\lambda_{n}$ is the total number of cyclic vertices in $G_{T}$).
In a similar way, one can interpret the ratio
$\mathbb{E}(\nu_{n})/\mathbb{E}(\lambda_{n})$ as the limiting conditional
probability that a randomly chosen cyclic vertex belongs to the largest
component (deepest cycle). It is well-known that
$\mathbb{E}(\lambda_{n})\sim\sqrt{\pi n/2}$ as $n\to\infty$; for example see
[20, Section 6.3]. Combining this asymptotic equivalence with the numerical
result of Theorem 1(i), we obtain the approximate value of this probability,
namely,

$\lim_{n\to\infty}\frac{\mathbb{E}(\nu_{n})}{\mathbb{E}(\lambda_{n})}=\lim_{n\to\infty}\sqrt{\frac{2}{\pi
n}}\mathbb{E}(\nu_{n})\approx 0.5493.$ (26)

Now, consider the length $\kappa_{n}$ of the longest cycle of a random mapping
from $\mathcal{T}_{n}$. Purdom and Williams [18] showed that
$\lim_{n\to\infty}\frac{1}{\sqrt{n}}\mathbb{E}(\kappa_{n})\approx 0.7825$.
Hence the limiting conditional probability that a randomly chosen cyclic
vertex belongs to the longest cycle is

$\lim_{n\to\infty}\frac{\mathbb{E}(\kappa_{n})}{\mathbb{E}(\lambda_{n})}\approx
0.6243.$ (27)

The difference between (27) and (26) is approximately equal to $0.075$. It can
be interpreted as the approximate limiting probability that the the longest
cycle and the largest component of $G_{T}$ are disjoint. Finch [7] called the
component containing the longest cycle of a random mapping the richest
component. In this terminology, the difference $0.075$ equals the approximate
limiting probability that the richest component is not the largest one. The
problem concerning the average size of the richest component remains unsolved.

In our last remark, we propose another open problem related to the size
$\tau_{n}$ of the largest tree in a random mapping from $\mathcal{T}_{n}$.
Since $\tau_{n}$ does not exceed the size of the component to which the
largest tree belongs and $\mu_{n}$ is the maximum component size of
$T\in\mathcal{T}_{n}$, for all $n\geq 1$, we have $\tau_{n}\leq\mu_{n}$. The
limiting distribution function of $\tau_{n}/n$ as $n\to\infty$ was first
determined by Stepanov [21]. There is another probabilistic proof of this
result due to Pavlov [16] (see also [14, Section 3.3]). The following natural
question arises: what can be said about the probability that the largest tree
is a subgraph of the largest component of a random mapping? It seems the limit
theorems from [21, 16] would be helpful to obtain an asymptotic estimate for
this probability.

## Acknowledgements

I would like to thank Steven Finch for his support in this study. I am
especially grateful to him for the numerical evaluation of the integral in
Theorem 1(i) and for bringing my attention to a numerical result obtained by
X. Gourdon [10]. I am also grateful to Emil Kamenov and Mladen Savov for
helpful discussions. This work was partially supported by Project KP-06-N32/8
with the Bulgarian Ministry of Education and Science.

## References

  * [1] M. Abramovitz and I. A. Stegun. Handbook of Mathemathical Functions with Formulas, Graphs and Mathematical Tables, Dover Publ. Inc., New York, 1965.
  * [2] R. Arratia, A. Barbour and S. Tavaré. Logarithmic Combinatorial Structures: A Probabilistic Approach, European Mathematical Society (Zürich, 2003.
  * [3] Z. Bao, J. Guo and L. Wang. Functional graphs and their applications in generic attacks on iterated hash constructions, IACR Trans. on Symmetric Cryptology 2018(2018), pp. 201–253.
  * [4] R. P. Brent and J. M. Pollard. Factorization of the eighth Fermat number, Math. Comput. 36(1981), 627–630.
  * [5] W. Feller. An Introduction to Probability Theory and Its Applications, Volume I, John Wiley, New York, 1957.
  * [6] W. Feller. An Introduction to Probability Theory and Its Applications, Volume II, John Wiley, New York, 1966.
  * [7] S. Finch. Components and cycles of random mappings. Available at arXiv:2205.05579 (2022).
  * [8] S. Finch. Personal communication, January, 2023.
  * [9] P. Flajolet and A. M. Odlyzko. Random mapping statistics, Advances in Cryptotlogy – EUROCRYPT’89, J.–J. Quisquarter and J. Vanderwalle, eds. Lect. Notes Comp. Sci. 434(1990), pp. 329–354.
  * [10] X. Gourdon. Combinatoire, Algorithmique et Géométrie des Polynômes, Ph. D. Thesis, École Polytechnique, 1996.
  * [11] L. Katz. Probability of indecomposability of a random mapping function, Ann. Math. Statist. 26(1955), 512–517.
  * [12] D. E. Knuth. The Art of Computer Programming, Volume 2: Seminumerical Algorithms, 3rd ed., Addison–Wesley, Boston, 1998.
  * [13] V. F. Kolchin. A problem of the allocation of particles into cells and random mappings, Theory Probab. Appl. 21(1976), 48–63.
  * [14] V. F. Kolchin. Random Mappings, Optimization Software, Inc., New York, 1986.
  * [15] S. V. Konyagin, F. Luca, B. Mans, L. Mathieson, M. Sha and I. E. Shparlinski. Functional graphs of polynomials over finite fields, J. Combin. Theory Ser. B 116(2016), 87–122.
  * [16] Yu. L. Pavlov. The asymptotic distribution of the maximum tree size in a random forest, Theory Probab. Appl. 22(1977), 509–520.
  * [17] J. M. Pollard. A Monte Carlo method for factorization, BIT Numerical Math. 15(1975), 331–334.
  * [18] P. W. Purdom and J. H. Williams. Cycle length in a random mapping function, Trans. Amer. Math. Soc. 133(1968), 547–551.
  * [19] A. R$\acute{e}$nyi. On connected graphs I, Magyar Tud. Akad. Mat. Kutat$\acute{o}$ Int. K$\ddot{o}$zl. 4(1959), 385–388.
  * [20] V. N. Sachkov. Probabilistic Methods in Combinatorial Analysis, Encyclopedia Math. Appl., Vol. 56, Cambridge Univ. Press, Cambridge, 1997.
  * [21] V. E. Stepanov. Limit distributions of certain characteristics of random mappings, Theory Probab. Appl. 14(1969), 612–626.
  * [22] G. A. Watterson. The stationary distribution of the infinitely-many neutral alleles diffusion model, J. Appl. Probab. 13(1976), 639-651.