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

Eduardo Sebastian, Thai Duong, Nikolay Atanasov, Eduardo Montijano and Carlos Sagues

Departamento de Informatica e Ingenieria de Sistemas,
Universidad de Zaragoza

Department of Electrical and Computer Engineering,
University of California, San Diego

Accepted at IEEE MRS 2023

[Paper]

[Code]

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 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.

Paper

Eduardo Sebastian, Thai Duong, Nikolay Atanasov, Eduardo Montijano and Carlos Sagues

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

IEEE MRS 2023.

[pdf]

Details and Multimedia

A time-varying graph with unknown connectivity and node dynamics generates a dataset of trajectories (left). A self-attention encoder generates node trajectories in a feature space and computes the regularization parameters. These outputs are the input for an adjacency matrix optimization problem (middle). A fast strongly convex optimization algorithm identifies the weighted adjacency matrix that best describes the observed node trajectories (right).

The state trajectory encoder (left) consists of four blocks: (i) a fully connected layer that encodes each individual state to a feature state of a single dimension; (ii) a self-attention layer that finds the relationships among features; (iii) a fully connected series of layers that finds the distances among feature trajectories; and (iv) two separate fully connected layers to find the regularization parameters for the subsequent graph identification optimization.

Besides the global convergence to the best graph topology in the smooth state trajectory sense, Algorithm 1 (right) is efficient to compute so, at each instant, sufficient iterations can be run to ensure convergence to the weighted adjacency matrix that best describes the node state trajectories defined over the Euclidean space.

Results from a multi-robot formation tasks, from left to right: ground-truth weighted adjacency matrix, identified weighted adjacency matrix, difference between ground-truth and identified matrices, and the same difference but with a threshold on the weights that are small so that they are zero and one otherwise. It is seen that the learned neural network is able to accurately identify all the weights, except some outliers that explain the differences in color scale.

The neural network is only trained with a single trajectory of a single multi-robot formation graph. The neural network generalizes to different numbers of robots and formation configurations with the same density of connections, also called edge density.

Multi-robot formation task: Mean Absolute Error between ground-truth and identified weighted adjacency matrices as a function of the number of robots and edge density. Each configuration is run 20 times, computing the mean and standard deviation. Diamond dashed lines are the state-of-the-art (reference [28] in the paper), whereas the circle solid lines are ours. Our proposed approach surpasses the state-of-the-art in one order of magnitude for all the configurations, considering that the neural network has only been trained with a single graph and associated trajectory.

Multi-robot formation task: Our approach moderately generalizes to other edge densities during evaluation because the training set only consists of a single graph with an edge density of 0.2. Top row shows a case with an edge density of 0.1, and the bottom row shows a case with an edge density of 0.4.

Multi-robot flocking task: Mean Absolute Error between ground-truth and identified weighted adjacency matrices as a function of the edge density. Each configuration is run 20 times, computing the mean and standard deviation. Diamond dashed lines are the state-of-the-art (reference [28] in the paper), whereas the circle solid lines are ours. Our proposed approach surpasses the state-of-the-art in more than one order of magnitude for all the configurations. Compared to the formation task, the learned neural network achieves a good performance for the different edge densities because the training set is diverse in this aspect.

Multi-robot flocking task: The relative value among the discovered weights is correctly identified, whereas the value of these weights with respect to the ground-truth vary depending on the edge density of the graph. For sparse, medium and dense graphs the identified weights tend to be lower, similar and greater than in the ground-truth graph. Besides, the neural network predicts a greater number of cliques, as in the middle row of the figure. These behaviors require further investigation.

Citation

If you find our papers/code useful for your research, please cite our work as follows.

E. Sebastian, T. Duong, N. Atanasov, E. Montijano, C. Sagues. Learning to Identify Graphs from Node Trajectories in Multi-Robot Networks. Under review at IEEE MRS 2023.

@inproceedings{sebastian23LIGMRS,
                                    

                                    author = {Eduardo Sebasti\'{a}n AND Thai Duong AND Nikolay Atanasov AND Eduardo Montijano AND Carlos Sag\"{u}\'{e}s},
                                  

                                  title = {{Learning to Identify Graphs from Node Trajectories in Multi-Robot Networks}},
                                  

                                    booktitle={IEEE International Symposium on Multi-robot \& Multi-agent Systems},
                                  

                                    pages={1--7},
                                   

                                    year = {2023}
                                    }

Acknowledgements

This work has been supported by NSF CCF-2112665 (TILOS) and via Spanish projects PID2021-125514NB-I00, PID2021-124137OBI00 and TED2021-130224B-I00 funded by MCIN/AEI/10.13039/501100011033, by ERDF A way of making Europe and by the European Union NextGenerationEU/PRTR, DGA T45-23R, and Spanish grant FPU19-05700 and EST22/00253.

This webpage template was borrowed from https://thaipduong.github.io/SE3HamDL/.