Search Performance of Multi-Agent Plan Recognition In a General Model
Document Type
Conference Proceeding
Publication Date
7-11-2010
School
Computing Sciences and Computer Engineering
Abstract
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.
Publication Title
Twenty-Fourth AAAI Conference On Artificial Intelligence
First Page
2
Last Page
9
Recommended Citation
Banerjee, B.,
Kraemer, L.
(2010). Search Performance of Multi-Agent Plan Recognition In a General Model. Twenty-Fourth AAAI Conference On Artificial Intelligence, 2-9.
Available at: https://aquila.usm.edu/fac_pubs/20627
COinS