MULTI-AGENT SYSTEMS: OBSERVABILITY, CLASSIFICATION AND CLUSTERING PREDICTION
Johns Hopkins University
This thesis studies three aspects of multi-agent systems, including clustering prediction, observability analysis and classification benchmarking. We introduce an auxiliary implicit sampling (AIS) algorithm for efficient Bayesian prediction of clusters, show that randomization enhances observability, and provide an optimality benchmark for time series classification (TSC) algorithms by the likelihood ratio test (LRT). Firstly, we present a Bayesian approach to predict the clustering of a multi-agent system from short-time partial observations. We characterize the clustering by the posterior of the clusters' sizes and centers, and introduce the AIS algorithm to sample the posterior. This algorithm leads to accurate predictions for the leading cluster, and overcomes the challenge of unobservability and high-dimensional sampling. Secondly, we propose a new observation strategy: we randomly select agents to be observed at each time. We prove that such randomization enhances observability. We provide an exact probability of being observable for linear systems. Toward this general result, we introduce two probabilistic extensions of the classical variational definition of observability: a likelihood-based definition and a Bayesian definition. Additionally, the Bayesian definition enables us to study observability of nonlinear systems. We show by numerical tests that randomization significantly improves the data assimilation of a nonlinear multi-agent system, particularly in its clustering prediction. Thirdly, we provide an optimality benchmark for TSC algorithms, which is more reliable than empirical benchmarks because the LRT is a theory-guaranteed optimal classifier. We test three scalable state-of-the-art TSC algorithms in distinguishing multi-agent systems and four more diffusions. These model-agnostic algorithms are suboptimal in classifying multi-agent systems, and are optimal or near optimal for the other simpler diffusions.
Multi-agent systems, Clustering prediction, Sequential Monte Carlo, Observability, Times series classification, Likelihood ratio test, Optimal benchmark