Role Discovery in Observed Multi-Agent Systems Over Time through Matrix Factorization (MRS 2021)

[pdf] [See below for dataset information.]

Update: This work was a Best Paper finalist at MRS 2021.

Our approach discovers roles within a multi-agent system and assigns each agent a role. In (a), a multi-agent system is observed over time, and a unified temporal representation is learned. In (b), a shared role matrix learned from the unified representation is factored into role probability matrices. In (c), the role probability matrix is used to discover roles for each agent and discover the number of roles in the multi-agent system.

Understanding unknown multi-agent systems solely from observations without prior knowledge of the system’s composition or structure is critical for effectively responding to and interacting with it. Whether the unknown system consists of humans, robots, or other entities, the capability to discover the roles that various agents play in the multi-agent system is necessary to fully understand it. While existing work often focuses on predicting future trajectories or behaviors, there has been little research on identifying agents that share roles within a multi-agent system. Discovering shared roles enables a fuller understanding of the system and its future behavior, i.e., agents that share a role could be expected to behave similarly. In this paper, we propose a novel approach for role discovery in an observed multi-agent system. We first present a method to learn a unified temporal representation of the multi-agent system through a temporally weighted approximation of graphs describing relationships between agents at each time step. We then present our main contribution, where we formulate role discovery as a regularized optimization problem with the goal of learning the optimal role assignment based on the unified temporal representation. Our approach learns probabilities that agents play different roles while also discovering the number of distinct roles that exist in the multi-agent system, and is proven to converge to the optimal solution. We also introduce a new role recognition dataset and evaluate on an existing dataset, showing that our approach outperforms existing methods in discovering roles in an observed multi-agent system.

The Swarm Red Team dataset for this paper is available here (~70MB, .mat file). If used, please cite this paper:

Citation: Role Discovery in Observed Multi-Agent Systems Over Time through Matrix Factorization. Brian Reily, Michael Don, John G. Rogers, and Christopher Reardon. International Symposium on Multi-Robot and Multi-Agent Systems (MRS), 2021.