Learning to Identify Graphs from Node Trajectories in Multi-Robot Networks

Eduardo Sebastián, Thai Duong, Nikolay Atanasov, Eduardo Montijano, Carlos Sagüés

Abstract

Identifying the underlying interaction topology of a multi-robot system from observed trajectories is a fundamental challenge in autonomous systems. This paper presents a novel hybrid architecture that combines self-attention neural networks with differentiable convex optimization to solve the graph identification problem. By embedding high-dimensional trajectory data into a simplified feature space and utilizing a differentiable optimization layer, the proposed method achieves an order of magnitude improvement in accuracy over existing state-of-the-art techniques. Furthermore, the model demonstrates significant zero-shot generalization capabilities across varying swarm sizes and movement patterns.

Introduction

In multi-robot networks, such as drone swarms or autonomous warehouse fleets, agents coordinate through specific interaction rules. These rules define who follows, avoids, or communicates with whom, forming a hidden "graph" of dependencies. To an external observer, only the resulting trajectories—positions and velocities over time—are visible. Recovering the interaction graph from these trajectories is known as the graph identification problem.

This task is inherently difficult due to three primary factors. First, coupling ensures that every robot's movement is influenced by its neighbors, creating a complex web of dependencies. Second, the high dimensionality of 2D or 3D trajectories often exceeds the capacity of traditional mathematical tools, which typically assume simpler scalar data. Finally, existing solutions often lack generalization; models trained on a specific number of robots or a specific formation often fail when the network topology or swarm size changes.

Methodology

The authors propose a two-part architecture that bridges deep learning and classical control theory, treating optimization as a functional layer within a neural network.

1. Self-Attention Encoder

Rather than processing raw coordinates directly, the system employs a self-attention mechanism. This choice is strategic: self-attention is "graph-agnostic," allowing it to process an arbitrary number of robots without retraining. The encoder learns to map high-dimensional trajectories into a latent feature space. Crucially, it also predicts the optimal regularization parameters ($\alpha$ and $eta$) required for the subsequent optimization step, effectively "learning how to set up the math problem."

2. Differentiable Convex Optimization

The latent features and predicted parameters are passed into a strongly convex optimization program. Unlike "black-box" neural networks, this layer uses a principled mathematical approach to ensure the resulting graph is sparse (containing only necessary edges) and valid (avoiding isolated agents).

3. End-to-End Training

The core innovation lies in the differentiability of the optimization steps. By using analytical gradients, the researchers can backpropagate errors from the final predicted graph through the proximal gradient iterations and back into the self-attention encoder. To enhance training stability, the authors introduced a loss function based on "adjoint graphs," which compares predicted edges against their complements to prevent the model from converging on trivial, zero-edge solutions.

Experimental Evaluation

The model was evaluated on two distinct simulated scenarios designed to test its limits:

  • Multi-Robot Formation: Using Erdős-Rényi random graphs to define agent connections, the team simulated 50 robots in 2D space. To test generalization, the model (trained on 50 robots) was evaluated on teams ranging from 10 to 60 robots.
  • Nonlinear Flocking: This scenario utilized complex, nonlinear flocking controllers. The dataset featured varying edge densities (from 5% to 95% connectivity) to determine if the model could adapt to different social and spatial structures.

Key Results and Discussion

The hybrid approach demonstrated superior performance across all metrics:

  • Accuracy: In formation tasks, the proposed method outperformed previous state-of-the-art (SOTA) methods by a full order of magnitude in Mean Absolute Error (MAE).
  • Zero-Shot Generalization: The model exhibited remarkable flexibility. A version trained on a 50-robot swarm could accurately identify the topology of a 10-robot or 60-robot swarm without any additional fine-tuning.
  • Robustness: Even in the presence of nonlinear physics and messy flocking dynamics, the model correctly identified interaction weights, whereas static SOTA methods struggled as edge densities shifted.

Limitations and Future Work

Despite its success, the model faces certain constraints. Performance degrades moderately when there is a significant mismatch in edge density between training and testing (e.g., training on a sparse 20% connected graph and testing on a 40% connected graph). Additionally, the computational cost is higher than standard feed-forward networks, as it requires running approximately 2,000 iterations of a proximal gradient method within the training loop.

Future research will focus on ablation studies to quantify the impact of training data variety on generalization. The authors also intend to apply this framework to non-robotic domains, such as identifying functional connectivity in brain imaging or mapping influence in social interaction networks.

Summary updated

Abstract

The graph identification problem consists of discovering the interactions among nodes in a network given their state/feature trajectories. This problem is challenging because the behavior of a node is coupled to all the other nodes by the unknown interaction model. Besides, high-dimensional and nonlinear state trajectories make it difficult to identify if two nodes are connected. Current solutions rely on prior knowledge of the graph topology and the dynamic behavior of the nodes, and hence, have poor generalization to other network configurations. To address these issues, we propose a novel learning-based approach that combines (i) a strongly convex program that efficiently uncovers graph topologies with global convergence guarantees and (ii) a self-attention encoder that learns to embed the original state trajectories into a feature space and predicts appropriate regularizers for the optimization program. In contrast to other works, our approach can identify the graph topology of unseen networks with new configurations in terms of number of nodes, connectivity or state trajectories. We demonstrate the effectiveness of our approach in identifying graphs in multi-robot formation and flocking tasks.
BibTeX
@inproceedings{sebastian2023learning,
  author = {Eduardo Sebastián and Thai Duong and Nikolay Atanasov and Eduardo Montijano and Carlos Sagüés},
  title = {{Learning to Identify Graphs from Node Trajectories in Multi-Robot Networks}},
  booktitle = {MRS},
  year = {2023},
  url = {https://openreview.net/forum?id=Y9QpD6MQOw},
}
Figure