Search Performance of Multi-Agent Plan Recognition in a General Model

Multi-Agent Plan Recognition (MAPR) seeks to identify the dynamic team structures and team behaviors from the observations of the activity-sequences of a set of intelligent agents, based on a library of known team-activities (plan library). It has important applications in analyzing data from automated monitoring, surveillance, and intelligence analysis in general. Recently, we have introduced a model for MAPR with a flat library structure, to study the complexity of basic MAPR, and also possibly its extensions in the future. Interestingly, this model makes fewer assumptions than existing models, and hence is more general. Therefore, as no existing algorithm would apply to this model, we have developed an hypothesis generation algorithm for this model, and adapted Knuth's Algorithm X for branch and bound search in the resulting hypothesis space. In this paper, we establish the time complexity of hypothesis generation in this model, propose and evaluate 3 different bounding criteria, and also empirically study the dependence of runtimes (hypothesis generation, and search times separately) on the model parameters.