Graph-based methods for the analysis of large-scale multiagent systems

Multiagent systems are often characterized by complex, and sometimes unpredictable interactions amongst their autonomous components. While these systems can provide robust and scalable solutions to a variety of problems, the inherent complexity presents a barrier to their analysis, understanding, debugging and modification. In the work presented here, we seek to overcome this problem by modeling the execution of a multiagent system as a graph, which admits the application of techniques from the well-established field of algorithmic graph theory. In particular, we employ graph search and isomorphism computation to find repeating patterns of communication within a multiagent simulation. We argue, and demonstrate empirically, that the graph, even if it is too large to fit into main memory, carries useful properties, which allow these operations to be performed efficiently. We further show that the resulting patterns (which tend to be manageable in size) present a useful view of a simulation, and facilitate the comparison of different simulations against one another. This is specifically illustrated by applying a tool called IntelliTrace, which implements our approach, to multiagent models of the national airspace. At the same time, the tool, and its underlying methodology, is domain-independent, and can be used for the analysis, development and testing of a variety of multiagent systems.