The Linear Sum Assignment Problem (LSAP) is a frequent problem in many of these applications. An optimal goal assignment as shown in Fig. 1 must minimize a given cost metric, such as the total distance traveled or time required for completion, while satisfying a one-to-one matching constraint. An efficient assignment is crucial to leverage the collaborative capabilities of multi-robot systems, expedite task completion, and reduce conflicts and collision risks.

Optimal solutions exist and are provided by well-known centralized algorithms such as the Hungarian algorithm [6]. However, these centralized methods are often impractical in real-world scenarios because they still rely on the global knowledge of the team's state. This is generally not available due to environment constraints or sparse communication among the agents, and results in a single point of failure. Therefore, this pushed to the design of decentralized solutions. For comprehensive reviews, the readers can refer to [7], [8], [9]. Many works explore decentralized optimization-based algorithms and market-based algorithms which often require numerous communication exchanges to guarantee the convergence to a consensus. Recently, deep learning methods as in [10], [11] have shown promising results in solving the LSAP using a Graph Neural Network (GNN) on a bipartite graph where edges connect the agent nodes to their possible task assignments. These techniques leverage the structure knowledge of the problem and optimize the information sharing between the nodes. However, they have not been designed to model and solve multi-robot systems problems with communication restrictions, and thus require full communication between all nodes of the graph.

In this work, we propose a novel approach for decentralized multi-robot LSAP using a GNN. We adopt a heterogeneous graph structure to model both the inter-robot communication links and the assignment relations between robots and goals. We design a GNN that achieves competitive performances by learning how to optimize the shared information. It demonstrates good zero-shot generalizability to large teams and greater robustness in highly restricted communication scenarios compared to existing methods.

The main contributions of this paper are the following r We design a novel GNN architecture, namely DGNN-GA, acting on a heterogeneous graph model to solve the decentralized LSAP for multi-robot teams.

r We analyze the performance and zero-shot generalizability of the proposed DGNN-GA with respect to the number of agents and the communication topology. Additionally, we investigate the influence of the number of communication rounds and its impact on the trade-off between performance and communication burden. We also conduct an ablation study to discern the roles of the different neural network architecture's components.

r We evaluate our solution in simulation and real-world settings for a general multi-robot planning objective minimizing the total distance squared traveled. We compare our solution with four other decentralized methods, namely a Local Hungarian algorithm (LH) [12], the D-CAPT pair-wise switching algorithm [4], the Consensus-Based Auction Algorithm (CBAA) [13], and the Decentralized-Based Hungarian Algorithm (DHBA) [14]. We show that DGNN-GA outperforms CBAA with an equal number of communication exchanges and improves the performance compared to DHBA when the number of communication rounds is minimal, while devoid of the strong assumption of an initial conflict-free guess contrary to LH and D-CAPT.

Task or goal assignment is widely used in various multi-robot applications [9], [15] such as exploration [16], formation control [17] and search and rescue [18]. This section focuses on decentralized optimization-based, market-based, and centralized or decentralized learning-based approaches.

Optimization-based Methods: Several works like [14], [19], [20] propose decentralized versions of the Hungarian algorithm. After O(N 3 ) iterations, equivalent to O(N 3 ) communication rounds (N the number of agents) the robots are guaranteed to converge to an optimal solution, albeit with considerable communication requirements. Alternatively, heuristic approaches [21] and genetic algorithms [22] are also employed. Especially, the authors in [21] introduce a greedy algorithm for one-to-one assignment, guaranteeing a 2-approximation to the optimal with O(N ) communication rounds. Multi-robot path planning applications also leverage multiple iterative methods that rely on online improvements of the assignment during the robots' motion, with one-hop communication round at each time step. In particular, D-CAPT [4] uses a pair-wise switching policy, and the authors in [12] apply the Hungarian algorithm locally every time a subset of robots communicate. These methods achieve near-optimal assignments in practice and are communication efficient. However, they rely on an initial conflict-free guess.

Market-based Methods: These approaches are mostly auction-based methods [13], [17], [23]. Each robot shares its list of task preferences along with bids, and the winning bid is determined once the team reaches a consensus. For example, the Consensus-Based Auction Algorithm (CBAA) [13] represents a baseline for multiple other auction algorithms due to its communication efficiency. CBAA guarantees to converge to a suboptimal conflict-free assignment after O(N d) iterations (or communication rounds), where d represents the diameter (i.e., the longest path connecting two robots) of the network, but needs much less in practice.

Learning-based Methods: These approaches have been widely explored to address multi-robot task assignment and trajectory planning problems using imitation learning [24], [25], [26] or reinforcement learning [27], [28], [29]. Notably, Graph Neural Networks (GNNs) gained significant attention due to their intrinsic ability to model and process graph-structured data, composed of nodes and edges, using graph filters [30], [31], [32]. Naturally decentralized, they offer an effective representation for multi-robot systems with robot nodes and communication edges [33]. Through a message-passing framework, robots share information with their neighbors and make predictions locally. Successful applications include collaborative perception [25], [34], [35], [36], flocking [26], [37], path planning [24], [36] or formation control [38] problems.

Learning-based approaches have also been used to tackle the LSAP as demonstrated in works such as [39] or [10], [11], which employ GNNs on a bipartite graph model constructed from agent and task nodes. The GNN is trained in a supervised-learning fashion to predict the classes of nodes or edges, demonstrating competitive performances with compact architectures. However, these methods do not address multi-robot problems with communication restrictions which are typical in real-world settings for multi-robot systems. Conversely, in this paper, we leverage the GNN benefits to solve the challenging general LSAP problem in decentralized settings while considering communication restrictions.

In the following, we denote column vectors with bold notation like h, matrices with capital notation like A, and scalars with unbold notation like c. Let R = {r 1 , r 2 , . . ., r N } be the set of robots, and G = {g 1 , g 2 , . . ., g N } be the set of goals. We assume an equal number of robots and goals (i.e., N ). All robots are homogeneous and possess identical communication capabilities. We denote with c ij the cost of the assignment of the robot r i to the goal g j , which is arbitrarily chosen depending on the application. The term s ij is the assignment label between r i and g j that equals to 1 if r i is assigned to g j , and 0 otherwise. The variables i and j will be used to refer respectively to robots' indices and goals' indices. The LSAP is formulated as

subject to

To solve this centralized problem in a decentralized fashion, we build an heterogeneous graph represented in Fig. 2 from the network of robots and goals. The graph is composed of robot nodes {r i } ∈ R and goal nodes {g j } ∈ G. We define two types of edges: E ass = {e ass ij } 1≤i,j≤N is the set of assignment edges connecting each robot to its possible assigned goals, whereas E com = {e com ij } i,j∈1,..,N is the set of communication edges between robots. These depend on the communication availability between two robots (i.e., if they are within each other's communication range).

We denote E ass (r i ) the set of assignment edges connected to r i . Additionally, we define N c (r i ) the set of neighboring robots that can communicate with r i . Similarly, N a (r i ) and N a (g j ) represent the set of neighboring goals that can be assigned to robot r i and the set of neighboring robots that can be assigned to goal g j respectively as shown in Fig. 2. To characterize the connectivity of the communication topology of a team, we define the communication adjacency matrix A, of size N × N whose components are

and the corresponding communication density

D com is equal to zero if all robots are isolated, and to 100% if all robots can communicate with each other.

In this section, we introduce the proposed DGNN-GA architecture design. It is decomposed in three modules (see Fig. 2): the Encoder, the GNN module, and the Decoder detailed below. For the purpose of predicting assignments, the optimization problem is solved via an edge binary classification framework. The DGNN-GA predicts a label for each assignment edge (see Fig. 2) namely 1 if a node is assigned to a specific goal and 0 otherwise. The nodes and assignment edges are embedded with feature vectors. We denote h r i , h g j , h e ij respectively for robot node r i , goal node g j , and edge e ass ij . In the following, the notation φ * refers to multi-layer perceptron (MLP) functions with two linear layers and a ReLU activation function in between. Initially, the nodes' embeddings are zero vectors, and the assignment edges' equal to their corresponding cost: ∀i, j, h e ij = c ij . Encoder: The encoder at the robot r i transforms its assignment edges' costs into embedding vectors of size F

where

The superscript 0 indicates the initial value of the embeddings before the GNN Module is applied.

The GNN module is composed of a series of L (layers) node and edge convolutions. Through a messagepassing framework, information is shared between neighbors L times. In other words, L corresponds also to the number of communication rounds among the robots.

One convolution at a node level is composed of a message function that creates a message from nodes and edges' embeddings (m * or M * ), an average function that is permutation invariant to aggregate the messages from other nodes and edges together ( h * or H * ), and an update function that updates the nodes' embedding. Moreover, DGNN-GA uses generalized convolutions with nonlinear functions, which were used in diverse applications to improve the performance of a GNN [40], [41], [42]. At one layer l and at a robot node r i level, we apply the following steps. The superscript l indicates the value of the embeddings at layer l.

Step 1: An agent assignment convolution (AAC) aggregates information from the goal nodes connected to r i and updates r i 's embedding

The notation || refers to the concatenation operation at the channel dimension. Additionally, the assignment edges' information is concatenated at the node r i 's level in another embedding vector l H i,edges of size

where g j 1 , . . ., g j M i ∈ N a (r i ). H i,edges helps differentiate information related to different goals.

Step 2: An Agent Communication Convolution (ACC) aggregates information from neighboring agent nodes about their possible assignments

where f map is a mapping function that retrieves information from l H i ,edges about common goals of interests between r i and r i .

Step 3: A Goal Assignment Convolution (GAC) updates the embedding of each g j connected to r i given H i,edges

Step 4: Assignment edges' embeddings are updated (AEU)

Decoder: The decoder at r i 's level predicts the assignment edges' labels from their final embeddings and is designed as

V. RESULTS AND ANALYSIS

The DGNN-GA is trained in a supervised fashion, imitating the Hungarian algorithm [6] in distributed fashion. To speed up the training, the model is trained on a graph where goal nodes are not duplicated for different robots and the communication adjacency matrix is used to enforce the communication restrictions in the convolutions. Then the model is deployed and executed as shown in Fig. 2. We build training datasets of 22000 graphs, each with a fixed number N of robots and goals and a fixed number L of communication rounds. The assignment costs are randomly initialized and communication topologies uniformly distributed between 20% (sparse communication) and 100% (full communication). We also employ 50 test sets of 1000 graphs each, for different team sizes (i.e., 5, 10, 15, 20, 50) and multiple communication densities (between 15% and 99%). For training, the number of assignment edges is limited to the top 5 for each goal to reduce the size of the graph without impacting the overall performance, since the optimal solution is likely to be found within the top 5 possibilities.

To achieve a binary classification task, we choose to minimize the Balanced Cross-Entropy (BCE) loss function

TABLE I MINIMUM TESTING ACCURACY IN % DEPENDING ON THE NUMBER OF ROBOTS FOR TRAINING N T AND TESTING N E

where y * is the flattened optimal assignment matrix S * by the Hungarian algorithm, and Ŷ the flattened assignment matrix Ŝ predicted by the DGNN-GA. We choose α 0.9 to account for the imbalance in the distribution of zero and one labels. Moreover, inspired by [10], we use an additional loss to help the neural network learn a one-to-one matching, satisfying the constraints in eq. ( 1)

The total loss to minimize is therefore

where β weights the importance given to one loss with respect to the other. We empirically set β = 0.8. The lower is β the more the DGNN-GA will prioritize finding a one-to-one matching rather than an optimal solution. Finally, the accuracy metric chosen to evaluate the classification performance is the Binary F1-score, which is well-suited for class-imbalanced data. In the following subsections, all training runs and comparisons were conducted using the random seed 1215, a batch size of 200 graphs and 40 epochs on a 12 th generation Intel CPU I9-12900H.

First, we train the model with N = 10 robots and L = 5 convolution rounds. After 2 hours, we achieve a training classification accuracy of 81.02%. We then evaluate the GNN on the test and obtain the results shown in Fig. 3.

The average testing accuracy on all possible communication densities is between 70% and 82% for 5 to 50 robots. Even with a communication density 20% or lower, the DGNN-GA is able to achieve an accuracy greater than 70%, which demonstrates that the heuristic learned by our DGNN-GA is robust to sparsely connected networks which is an extremely important property in multiple real-world settings and deployment cases. Moreover, the DGNN-GA also demonstrates zero-shot generalizability to larger teams of robots, up to 50, with an overall minimum accuracy of 70.47% and a fixed number of communication rounds L = 5.

To further analyze the generalizability properties of our solution, we train the DGNN-GA with different fixed numbers of agents, from 5 to 10, and report in Table I the minimum accuracy obtained for each test set with 5 to 50 robots. In most cases, the minimum testing accuracy is obtained for 50 robots with a communication density lower than 20%. For large teams (N ≥ 10), the minimum performance increases with the number of robots used for training. Therefore, a trade-off can be made between the team size for training and the zero-shot generalizability performance.

We test several convolutions rounds (L = 1, 3, 5, 8, 10) on a 10 robots team. The results are presented in Fig. 4.

The number of layers defines the number of communication exchanges between the neighboring robots. As we can see, the performance increases with L. Therefore, its value strikes a balance between performance and communication burden. In any case, we notice that with only 5 rounds, the network reaches a 75% accuracy for sparse communication networks and more than 82% for well-connected networks.

We conduct an ablation study on our DGNN-GA architecture. Specifically, we compare the testing accuracy obtained if we use linear functions instead of nonlinear MLPs for both update and message functions used in the convolutions performed in steps 1, 2, and 3 presented in Section IV. We compare and analyze our nonlinear DGNN-GA with several variants of the same architecture, where specific modules are replaced to clearly identify their benefits As we can see, nonlinear functions improve the expressiveness of our DGNN-GA. The classification performance is significantly better compared to DGNN-GA-MFUFlinear that has fully linear convolutions. DGNN-GA-UFlinear and DGNN-GA-MFlinear perform similarly and lead to a worse but closer performance to our DGNN-GA's performance. We can conclude that at least one nonlinear function is needed to get a satisfying result, and nonlinear functions for both message and update functions provide the best performances.

We evaluate our DGNN-GA in simulation for a common multi-robot goal assignment problem. We run 100 Monte Carlo simulations of duration T = 10 s with N = 5, 10, 15, 20 robots and goals whose positions are randomly initialized, respecting an initial safety relative distance of 1.0 m, and in variable communication topologies defined by different communication ranges. The cost to minimize in eq. ( 1) is chosen as the sum of distances traveled squared, thus

, where d ij is the Euclidian distance between r i and g j . Indeed, distance costs are widely used in multi-robot applications, as in [4], [12], They have shown great utility to minimize the execution time of a mission and to reduce the risk of collision. We assume the robots move at a constant velocity of v = 2 m/s.

We compare our DGNN-GA with respect to four decentralized approaches commonly used in multi-robot goal assignment problems and that have shown great performances with limited communication exchanges r The pair-wise switching policy (D-CAPT) [4]: Neighbor- ing robots communicate by pair and switch their goals if the sum of their costs decreases. The assignment is improved iteratively during the robots' motion. The approach requires one communication round at each time step and an initial random assignment satisfying the one-to-one matching constraint.

r The Local Hungarian algorithm (LH) [12]: Similar to D- CAPT, the assignment is improved iteratively during the robots' motion. It performs one communication round at each time step and assumes an initial random one-to-one assignment. However, LH applies the Hungarian algorithm on each subset of neighboring robots.

r The Consensus-Based Auction Algorithm (CBAA) [13]:

Conversely to LH and D-CAPT, CBAA applies multiple communication rounds at once, without any initial assumption. The robots start moving when a consensus is found. CBAA is a baseline state-of-the-art approach among auction algorithms due to its efficiency. It guarantees to converge to a consensus after O(N d) communication rounds, but is much faster in practice.

r The Decentralized Hungarian-Based Algorithm (DHBA) [14]: DHBA also applies multiple communication rounds at once and does not require any initial assumption. In the algorithm, each robot buffers an estimation of the global cost matrix, updates it with the neighbors' cost matrices at each communication round, and applies the Hungarian algorithm. After multiple rounds, all robots' cost matrices are equal and the algorithm converges to the optimal solution. We compare the average total cost across variable communication densities and different L. Fig. 6 reports the error in % to the optimal solution, provided by the centralized Hungarian algorithm, i.e. the percentage increase in total cost

where s * ij are the components of the optimal assignment matrix S * given by the Hungarian algorithm, and ŝij the components of the predicted assignment matrix Ŝ provided by the different decentralized solutions. The associated minimum and maximum values of the third quartile q are reported in Table II as it represents a more intuitive dispersion measure owing to the non-Gaussian data distribution. It corresponds to the value under which 75% of the errors are found. Minimum values are obtained in low connectivity (low L and D com ) and maximum values in high connectivity (high L and D com ). In general, a high dispersion of E about the average is observed for all methods, reflecting the diversity of the scenarios tested using our simulation setup, especially in low connectivity.

Before comparing and discussing the methods, we notice that the errors reported increase significantly over 100% when N ≥ 10. The reason is that the errors accumulate with the number of robots, especially for low values of L and sparse communication densities (D com ≤ 30%), where more conflicts occur and more robots need to be reassigned.

Comparison with LH and D-CAPT: LH converges quickly to the optimal solution when the network is well connected (i.e. D com ≥ 40%), contrary to D-CAPT. Indeed, while the pair-wise strategy is efficient, it leads to more frequent reassignments than LH. DGNN-GA provides competitive results compared to with L = 5 communication rounds, but predicts worse assignments than LH and D-CAPT for lower L. Indeed, our method DGNN-GA is devoid of any one-to-one initial assumption and thus, as expected, needs more communication rounds to find a consensus. However, in practice, an initial one-to-one assignment represents a strong assumption since it requires some initial global knowledge of the team's state that is not available in many multi-robot applications. On the other hand, our approach, similarly to CBAA and DHBA in restricted communication as discussed in the following, does not always guarantee a conflict-free assignment because the one-to-one matching constraint is enforced as a soft constraint in the training loss. Regarding the dispersion of the errors in Table II, our DGNN-GA provides lower quartiles compared to D-CAPT in both low and high connectivity scenarios. For well-connected networks (high values of L and D com ) and N ≤ 15, 75% of our DGNN-GA's assignments reach the optimal solution.

Comparison with CBAA and DHBA: DGNN-GA outperforms CBAA in every scenario in terms of average percentage increase and dispersion. Therefore, the heuristic learnt the DGNN-GA, implicitely leveraging the structure knowledge

TABLE II MINIMUM AND MAXIMUM THIRD QUARTILES q(%) OF THE PERCENTAGE INCREASE E FOR THE DIFFERENT ASSIGNMENT ALGORITHMS AND TEAM SIZES N

of the graph, improves the performance compared to CBAA with the same number of communication exchanges. Regarding DHBA method, it outperforms DGNN-GA for L ≥ 3 and in that case converges to a near-optimal solution (E ≤ 10% and q = 0%) for D com ≥ 40%. However, for L < 3, the average error of DHBA is similar to CBAA, but worse than DGNN-GA. Moreover, for low values of both L and D com , DHBA generates higher quartiles. Therefore, DGNN-GA is better suited than DHBA for highly restricted communication scenarios. CBAA and DHBA can guarantee the convergence to a conflict-free assignment contrary to our DGNN-GA, but to achieve this goal they need a sufficient number of communication rounds depending on the topology of the network and the number of robots. However, in many real-world scenarios, we need to limit the number of communication rounds, because of time constraints to complete the task, or because of unpractical communication delays or drops due to environment constraints or interferences. In these cases, the conflict-free assignment is not guaranteed anymore for both CBAA and DHBA. In the simulation tests, the comparison is made considering only L communication iterations, and we leverage a conflict resolution module for CBAA, DHBA, and our DGNN-GA in case a consensus is not found. A greedy approach detects and handles locally a conflict between two neighboring robots. The further robot from the goal of interest is reassigned to the second goal with minimum cost. Besides, a random assignment policy was evaluated as a lower bound. Each robot chooses initially a random goal and conflicts are resolved using the same greedy approach. For team sizes from 5 to 20, the average error generated goes from 100% to 230% in high connectivity and explodes from 320% to 2080% in low connectivity. As a conclusion, our DGNN-GA outperforms CBAA and DHBA in highly restricted number of communication rounds, and does not leverage any assumption of an initial one-to-one assignment available compared to LH and D-CAPT.

To demonstrate the practical applicability of our solution, we deploy it in real-world settings in an indoor testbed of 10 6 × 4 m 3 with a Viconfoot_1 system for localization. We employ 3 custom built quadrotors equipped with a Qualcomm Snapdragon TM VOXL 2foot_2 board and based on our previous work [43]. Three goals are chosen randomly in the flying arena. In the example shown Fig. 7, two scenarios are tested. In the first one, all robots can communicate and in the second one, r 3 only communicate with r 1 . In both cases, each robot effectively computes the optimal assignment.

In this work, we presented a novel DGNN-GA architecture to solve the decentralized LSAP for multi-robot systems. Interrobot communication and goal assignments are modeled by one heterogeneous graph and the optimal solution is learned by imitating the expert Hungarian algorithm. The approach optimizes the information sharing process between the robots, leveraging the structure knowledge of the graph, to generate assignment predictions with restricted communication exchanges. We analyzed its zero-shot generalizability for team sizes up to 50 robots. The DGNN-GA was deployed in simulation and real-world for a multi-robot minimum distance traveled squared objective. It demonstrates competitive performances compared to existing approaches with a fixed number of communication rounds. Compared to LH and D-CAPT, it is devoid of the assumption to have an initial one-to-one assignment. It outperforms CBAA in every scenario and DHBA when the number of communication rounds is minimal. DGNN-GA can be used for multiple applications.

In the future, DGNN-GA will be combined with a local motion planner to optimize the robots' motion considering their dynamics and ensuring safe navigation. Moreover, the method will be extended considering more goals than robots.