Representing Multi-Robot Structure through Multimodal Graph Embedding for the Selection of Robot Teams
Brian Reily Christopher Reardon Hao Zhang
cs.RO

Efficient photo-induced second harmonic generation in silicon photonics
    Kartik Srinivasan
    December 30, 2023
=======================================================================

empty
empty





Multi-robot systems of increasing size and complexity
are used to solve large-scale problems, such as area exploration and search and rescue.
A key decision in human-robot teaming is dividing a multi-robot system into teams to address
separate issues or to accomplish a task over a large area.
In order to address the problem of selecting teams in a multi-robot system,
we propose a new multimodal graph embedding method
to construct a unified representation
that fuses multiple information modalities to describe and divide a multi-robot system.
The relationship modalities are encoded as directed graphs that can encode
asymmetrical relationships,
which are embedded into a unified representation for each robot.
Then, the constructed multimodal representation is used to determine teams
based upon unsupervised learning.
We perform experiments to evaluate our approach on
expert-defined team formations,
large-scale simulated multi-robot systems, and a system of physical robots.
Experimental results show that
our method successfully decides correct teams based on
the multifaceted internal structures describing multi-robot systems,
and outperforms baseline methods based upon only one mode of information,
as well as other graph embedding-based division methods.








§ INTRODUCTION



Because of their robustness and flexibility,
multi-robot systems are being increasingly researched and used in large-scale applications,
such as disaster response <cit.>,
search and rescue <cit.>,
and area exploration <cit.>.
Accomplishing complex operations using multi-robot systems typically
requires the division of a system into effective teams that are capable of achieving multiple
separate tasks simultaneously
or accomplishing mission objectives over a large
area <cit.>.
However, as the number of robots in a system increases,
it becomes
cognitively more difficult for humans to understand and command
<cit.>.



Successful division of a large multi-robot system into effective teams
is a
particularly difficult problem as the size and complexity
of the interaction between robots increases.
At scale, the complexities of internal relationships become difficult
for human operators to conceptualize and integrate <cit.>.
Figure <ref> provides an illustration of how robots can appear organized in physical space,
but also contain hierarchical relationships
or communication capabilities within a system that are more difficult to
perceive.
These relationships are further complicated by robot interactions with obstacles and the
surrounding environment.
When combined, these challenges result in robotic system states that are both difficult for
a human operator to accurately perceive and
for a system to display <cit.>.
Thus, effective representations of multi-robot structure are critical for
understanding and selecting team divisions.


Due to the importance of multi-robot teams, division approaches have
been widely studied in the literature.
A commonly used paradigm approached the division of a multi-robot
system based solely on spatial locations of members,
assigning territories to each
robot <cit.>.
These methods have the drawbacks of relying on spatial
information only and assigning agents to individual territories,
without the ability to identify teams or grouped divisions.
Another paradigm views multi-robot division as a task
allocation problem, e.g., based on
task sequencing <cit.>,
game theory <cit.>,
and Markov chains <cit.>.
These techniques require
explicit knowledge about the tasks,
such as task sequences, requirements, or priorities,
as well as knowledge of opponent behaviors,
which may not be available to a human operator.
In addition,
methods were also implemented
that are inspired by biological swarms such as
ants <cit.>
or wasps <cit.>.
These techniques often assume simple agents,
often without the ability to communicate,
and are not capable of creating a complete representation of
multi-robot structure by addressing multiple relationship modalities.


To address the selection of multi-robot teams,
we propose a novel multimodal graph embedding approach
to encode diverse relationships of multiple robots as graphs
and integrate these multiple graphs
into a unified representation that is applied to
divide a multi-robot system into teams.
We model each internal relationship of the robots
using a directed graph
as an information modality.
Given a set of member relationships,
we construct multiple graphs that are applied as the input to our approach.
Then, we propose a new multimodal Katz index to integrate
multiple graphs of robot relationships and embed them into a
unified representation for each robot.
Then, the constructed representation is used to identify multi-robot teams
through unsupervised learning.
Our multimodal graph-embedded robot division approach is capable of
fusing diverse robotic relationships
and identifying team divisions without requiring explicit knowledge of tasks.


This paper has two major contributions.


  * First, we propose a novel multimodal graph embedding approach
that formulates robot team selection as a graph-based embedding and clustering problem,
models multiple asymmetrical relationships of robots using directed graphs,
and fuses them into a unified representation to identify robotic teams.

  * Second, we perform a comprehensive evaluation of the proposed method in
the scenarios using expert-defined team formations,
large-scale simulated multi-robot systems, and
teams of physical robots.
We validate that our multimodal graph embedding approach is effective in identifying
robotic teams, and obtains superior performance over existing graph-based division methods.





§ RELATED WORK
 


In this section, we review previous approaches to multi-robot division,
representation of multi-robot systems as graphs,
and existing graph embedding methods.



 §.§ Multi-Robot Division


Dividing multi-robot systems to accomplish
multiple objectives simultaneously
has been approached previously from three main perspectives:
spatial-based division, task allocation, and biologically inspired
methods.

Spatial-based division was implemented by assigning robots to their
own territories <cit.>.
It was typically formulated as an optimization problem, where a group of robots
diffuses to optimize coverage of an area <cit.>.
This spatial-based perspective has two main drawbacks.
First, it relies solely on the spatial locations of robots, omitting
other information available that could be utilized to better divide
the system.
Second, it assigns members to areas individually, and is unable to divide
a multi-robot system into teams, each still capable of working together.

Task allocation was implemented for multi-robot division in a variety of ways.
Explicit assignment was designed based on sub-goals <cit.>,
or the temporal relationships between tasks 
<cit.>.
Markov chains were also developed to schedule task
assignments <cit.>.
Agents were designed to negotiate with each other for
sub-tasks <cit.>, and game theory was applied to
find optimal task assignments <cit.>.
Multi-robot division based on task allocation has the major drawback
of requiring explicit information about the task.
This can range from requiring task dependency information in order
to schedule sequences, task composition in order to assign
sub-tasks, or task priorities and requirements in order to determine
the best robot to assign the task to.
Many approaches also assign tasks to individual robots, as opposed to
tasking groups to accomplish a single task.

Methods inspired by biological swarms were also designed for
multi-robot division, inspired by how insects divide into sub-groups.
Methods were introduced based on ant foraging <cit.>
and division of labor in wasp colonies <cit.>
and ant colonies <cit.>.
Biological approaches generally
assume swarm agents are extremely limited in their ability to
sense, communicate, and process information.
Previous bio-inspired methods cannot incorporate multimodal relationships of swarm members.



 §.§ Graph Representations of Multi-Agent Systems


Many previous works used graphs to represent multi-agent systems,
by representing agents in the team with
vertices and relationships between agents as edges.
Control laws were first applied as edges between agents, where these
laws controlled spacing between agents and were applied to construct group
trajectories around obstacles <cit.>.
Graphs that described multiple nearest neighbors through control laws
were applied in <cit.> and <cit.>.
Communication channels between robots were represented graphically in <cit.>.
Graph rigidity was used in
<cit.> in
an optimization-based method to perform split and
rejoin maneuvers around obstacles.

Methods to find communities in graphs are mainly based on analyzing edges between vertices.
Cut-based methods cut the graph to form the best two
clusters, and include min-max cuts <cit.> and
normalized cuts <cit.>.
Communities based on the probability of new links were used in <cit.>,
later extended with the idea of modularity <cit.>,
which constructs a segmentation metric and uses this to create divisions.


These community-finding algorithms are unable to operate on
multiple graphs, and often cannot divide a graph into an arbitrary
number of communities but instead rely on the structure
of the graph
to define the number of communities.



 §.§ Graph Embedding


Graph embedding is the representation of graph structure in vector space,
allowing typical machine learning techniques to be applied
<cit.>.
Techniques including node2vec <cit.> employ random walks,
representing nodes based upon their transition probabilities to and from
other nodes.



Methods based on matrix descriptions of graphs, such as adjacency matrices and
similarity matrices, include structure preserving embedding <cit.>,
graph factorization <cit.>,
and High-Order Proximity preserved Embedding (HOPE) <cit.>.
Most graph embedding techniques focused on single graphs
representation, e.g., to encode social networks or academic citation networks,
without the ability to integrate multiple relationships.
The effectiveness of graph embedding for multi-robot division has also not
well studied in the literature.




§ APPROACH




We propose a new multimodal graph embedding approach to integrate multiple
directed graphs
that encode relationships in a multi-robot system
into a unified representation
that is used to identify multi-robot teams.



 §.§ Multimodal Robotic Structure Embedding


Given a specified relationship (e.g., communication connectivity)
of a multi-robot system including N members,
we represent a relationship among robots as a
graph 𝒢 = ( 𝒱, ℰ ), where
𝒱 = { v_1, …, v_N } denotes the
set of vertices, each corresponding to a robot,
and ℰ denotes the
set of directed edges between these vertices.
The direction and weight of each edge e_ij = ( v_i, v_j ) ∈ℰ
depends on the type of relation the graph is representing.

In real-world deployment,
robotic members within a system typically have multiple various relationships
(e.g., spatial relationships, communication connectivity, and organization hierarchy).
When multiple robotic relationships are available,
we encode the system with M graphs, where 𝒢_m is the graph
describing the m-th relationship between robots.
Each graph 𝒢_m is described by an adjacency matrix
𝐀_m ∈ℛ^N × N, where each element
a_ij is the weight of the edge connecting vertex v_i to
vertex v_j.
The proposed method is able to represent both directed (e.g. communication from one
member to others) and undirected (e.g., spatial distances) relationships.
In the case of representing undirected relationships, the weight
of edges satisfies a_ij = a_ji.

To represent graphs in vector space (i.e., graph embedding),
the Katz index <cit.> has shown to be a promising method
that has been used to address real-world graph problems.
The Katz index represents the similarity of a pair of vertices given a graph,
by summing the weights of edges along all paths between the two vertices
to represent how closely connected the two vertices are.
Given a decay parameter
α>0 that weights paths based on their length L, the Katz index can produce
a similarity matrix 𝐒 to describe a graph:

    𝐒 = ∑_l = 1^Lα^l𝐀^l


This equation can be rewritten as

    𝐒 = ( 𝐈 - α𝐀 )^-1 - 𝐈

where 𝐈 is the identity matrix.

To achieve our objective of encoding multiple graphs
and embedding them into a single vector representation,
we propose a new multimodal Katz index
that is able to take multiple graphs as the multimodal input modalities
and form a single similarity matrix
𝐒∈ℛ^N × N that integrates the information
of all graphs.
To do this,
we implement an adjacency matrix 𝐀_m for each graph 𝒢_m,
where m = 1, …, M, and introduce
a weight w_m for each 𝐀_m describing the importance
of the relationship encoded by 𝒢_m, where
1 = ∑_m=1^M w_m.
Values of w_m can be specified by human experts to incorporate prior knowledge
and preferences, or estimated by hyperparameter selection methods (e.g., grid search).
We then construct the multimodal similarity matrix 𝐒
that embeds information of all graphs as follows:

    𝐒 = ( 𝐈 - α∑_m = 1^M w_m 𝐀_m )^-1 - 𝐈



( 𝐈 - α∑_m=1^M w_m 𝐀_m ) is invertible
when  α^-1 is greater than the largest eigenvalue of 𝐀^*, where 𝐀^* = ∑_m=1^M w_m 𝐀_m.


For ( 𝐈 - α𝐀^*) to not be invertible,
det(𝐈 - α𝐀^*) = 0.
This is equivalent to det( 𝐀^* - α^-1𝐈) = 0.
This determinant is only zero if α^-1 is equal to the largest
eigenvalue of 𝐀^*, denoted as e_1.
When α < 1/e_1, the inverse is valid.




In order to create a lower-dimensional representation than 𝐒,
which is necessary when embedding big graphs of a large-scale multi-robot system,
we perform Singular
Value Decomposition (SVD) <cit.> to factor 𝐒:

    𝐒 = 𝐔Σ𝐕^T

The columns of 𝐔 are the left singular vectors of
𝐒, the rows of 𝐕^T are the right singular
vectors, and Σ is a diagonal matrix whose entries are
the singular values.
As 𝐒 is a square N × N matrix, all of these are ∈ℛ^N × N when a full SVD is performed.
The columns of 𝐔 are also the eigenvectors of
𝐒𝐒^T, and similarly the rows of 𝐕^T
are the eigenvectors of 𝐒^T 𝐒.

To further reduce the dimensionality of the representation, given
a desired dimensionality D,
we propose to use the
first K left singular vectors and the first K right singular vectors
to approximate 𝐒,
where K = D / 2, half of the desired dimensionality.
As we only use the first K singular vectors on each side, we can perform
a reduced SVD of 𝐒.
This results in 𝐔∈ℛ^N × K and
𝐕∈ℛ^N × K.

Finally, we construct the final representation matrix 𝐗∈ℛ^N × D
for all N robots by combining
𝐔 and 𝐕:

    𝐗 = ( 𝐔, 𝐕)

where each row 𝐱_n ∈ℛ^D of 𝐗
represents the n-th robot, which is then used for division.







 §.§ Selection of Multi-Robot Teams


Given the multimodal graph embedding results,
we propose to perform selection of multi-robot teams
through unsupervised learning (i.e., clustering).
Specifically, given
𝐗 = {𝐱_1; …; 𝐱_N },
and given the number C of
robot teams the human operator needs to accomplish the mission,
the goal is to assign each robot a cluster label
𝐱_n^( c ) that indicates it belongs to team c,
thus dividing the robotic system into C total teams.

This unsupervised learning problem can be formulated by:

    𝐱_n^( c )arg   min ∑_n=1^N
    || 𝐱_n^( c ) - ϕ_c ||^2

where Φ = {ϕ_1, …, ϕ_C } are
the centroids of all divisions, initially chosen at random.
The formulated optimization problem can be solved iteratively.
First, labels are assigned to each robot 𝐱_n.
Then, each centroid ϕ_c is recalculated based
on the robots assigned to that cluster.
This process is repeated until the assigned cluster labels 𝐱_n^( c )
converge.

The algorithmic implementation of both multimodal multi-robot
structure embedding and multi-robot
division is summarized in Algorithm <ref>.






§ EXPERIMENTS
 




To evaluate the performance of the proposed multimodal
graph embedding approach for selection of multi-robot teams,
we conduct experiments using robotic systems at multiple scales.
We evaluate the accuracy of multi-robot team selection and
score the quality of the robot clusters.
We also compare with previous graph-based division techniques.



 §.§ Experimental Setup


Our approach was experimentally evaluated and validated in
two different scenarios.
First, we evaluate on Scenario I: Expert-defined Team Formations.
This experiment is based on a set of expert-defined graphs that
represent relationships in field operations teams at two scales.
Second, we evaluate on
Scenario II: Simulated Large-Scale Multi-Robot Systems.
We generate large-scale multi-robot systems
to demonstrate that our method scales beyond the
size of small groups.
These simulated systems do not have ground truth teams, and instead
our identified teams are scored by a clustering metric.
We demonstrate our approach can be deployed in real-world robotic applications
by deploying some of these simulated robotic systems as physical TurtleBot robots.





Simulations of the expert-defined teams and the large-scale multi-robot systems were performed
with the Webots robot simulator <cit.> in an application of area exploration.
We created a simulated environment of the Colorado School of Mines campus for the experiments.
Figure <ref> displays the real campus environment, its simulated Webots map and the simulated robot used.
In the experiments on all scenarios,
three types of graphs are used as input information modalities,
describing spatial positions, known
communication connectivity, and a set hierarchy.
For quantitative evaluation,
we present the clustering accuracy when dividing the expert-defined teams
and utilize
silhouette scores <cit.> for all robotic divisions.
Silhouette scores rate the quality of a clustering, with values closer
to 1 being better and values closer to -1 being worse.

To validate the superior performance of our approach,
we compare it with previous methods:
(1) Girvan-Newman (GN) <cit.>, a single-modality graph community finding algorithm;
(2) Local Linear Embedding (LLE)
<cit.>, a single-modality graph embedding approach;
(3)  High-Order Proximity preserved Embedding (HOPE)
<cit.>, a single-modality graph embedding approach;
and (4) Concatenated Combination HOPE, which applies the HOPE graph embedding on each individual graph and
concatenates these vectors from three separate graphs into a single representation.





 §.§ Results on Expert-Defined Team Formations (Scenario I)


We first evaluate our approach on the
expert-defined team formations known as
the platoon column, platoon wedge, and platoon vee
and the squad column, squad file, and squad line,
based on the field operations teaming protocol in <cit.>.
This protocol contains correct, expert-defined
sub-divisions for these formations.
Platoon formations incorporate three squads and two separate
leadership agents.
Squad formations incorporate two teams and one separate leadership
agent.
Figure <ref> displays the squad column
and platoon column in the Webots simulator, with correct
sub-divisions labeled.



The spatial relationships, communication
capabilities, and structured hierarchy of these formations are
defined by the field operations teaming protocol.
We encode each of these relationship modalities as a separate graph in order
to compare our approach to previous methods.
Table <ref> reports the clustering accuracy for our
approach versus these baseline approaches.
Out of a possible 306 agents in the six different formations, our
approach clusters 96.73% of the agents correctly.
The second best is the concatenated combination of HOPE embeddings,
clustering 93.14% of agents correctly, showing that extending
existing graph embedding methods to leverage multiple information
modalities can significantly improve their performance from using
a single modality.

Table <ref> displays the silhouette scores for
each sub-division of each formation.
Our approach achieves the highest score, with an average silhouette
score of 0.680.
Again, second highest is the concatenated combination of HOPE
embeddings, scoring 0.518.
We note that our approach achieves its best results on the platoon
formations, which contain over three times as many agents as the squad formations.
This suggests that our approach's performance will extend to
larger multi-robot systems.
There also exists a linear relationship between clustering accuracy and
silhouette scores, visualized in Figure <ref>.
This validates the silhouette score as a metric for dividing the simulated
robotic systems in Scenario II, where the ground truth divisions are unknown.

For these expert-defined teams, we also evaluated the effect of simulated
sensor noise, where robots no longer have exact knowledge of where
their robotic teammates are.
Figure <ref> shows both the effect on clustering accuracy of adding up to 50% error
into the distances between robots and the effect
of this noise on silhouette score.
Our approach, able to utilize information from other modalities,
is robust to this error, declining in accuracy only slightly for
the smaller squad formations and maintaining 100% accuracy
on the larger platoon formations.
Our approach is similarly consistent in maintaining a high silhouette
score despite the simulated sensor noise.
The HOPE embedding, based on the spatial graph, is affected significantly.
On the squad formations, this method declines from an average
accuracy of 76.47% with no sensor noise to 61.77% with 50% noise.
A similar decline in performance occurs with the platoon formations,
from 88.24% to 72.95% accuracy.
The HOPE embedding also produces clusters with lower silhouette scores
as the simulated sensor noise increases.







 §.§ Results on Simulated Large-scale Multi-Robot Systems (Scenario II)


To evaluate the effectiveness of our approach on a larger scale,
we simulated larger multi-robot systems in Webots.
These large-scale systems have the same relationship modalities
as the expert-defined teams.
Spatial relationships are calculated from their simulated physical
locations, communication capabilities are based on each simulated
robot being capable of short-range, line-of-sight communication
to nearby robots, and hierarchical relationships were defined
based on heuristics from field operations teams (i.e., robots near
the center of the overall system are higher in the hierarchy than
robots on the perimeter).
Figure <ref> displays a simulated system of 50
robots in Webots.

We repeatedly generated these large multi-robot systems
and performed team selection based on each evaluated approach.
Table <ref> shows results for simulated
systems of 10, 20, 30, 40 and 50 robots divided into three, four and five teams, with
comparisons to existing graph embedding approaches.
Each combination of size and number of clusters was run 100
times.
As seen in the experimental results in Table <ref>,
our approach achieves the highest silhouette score of 0.676.
This is consistent with our score of 0.680 on the expert-defined teams, where
our approach achieved the highest clustering accuracy, suggesting
that our identified sub-divisions of large-scale simulated multi-robot systems
outperform the divisions identified by other methods.



To demonstrate the ability and potential of our approach to work on physical
robots in the real world, we implemented systems of
10 physical Turtlebot
robots in a proof-of-concept case study.
We labeled these 10 Turtlebots with tracking tags, and utilized an overhead camera
to track the robots and
construct their spatial relationship graph from their positions.
Communication and hierarchy graphs were defined as they were in the Webots
simulator.

We applied our proposed multimodal graph embedding approach to identify teams within
the Turtlebot system, with the objective to divide the physical robot system
into three teams.
Figure <ref> illustrates four executions of this as a case study, with bounding boxes identifying the positions and team labelings.





§ CONCLUSION
 


In this paper, we introduce a novel approach to representing multi-robot
structure in order to divide a multi-robot
system into teams.
The proposed approach represents robotic relationships as directed graphs,
and constructs a vector representation from multiple graphs through
a novel multimodal graph embedding method.
Our approach is able to integrate multiple information modalities to describe
and divide a multi-robot system,
allowing our approach to create teams that are more comprehensive and effective.
We demonstrate the effectiveness of our approach over expert-defined team
formations



and evaluate our approach on
large-scale simulated multi-robot systems and on physical robot teams.





ieeetr


