Bikramjit Banerjee's Publications
• Selected Publications • All Sorted by Date • All Classified by Publication Type •
The complexity of multi-agent plan recognition
B. Banerjee, J. Lyle, and L. Kraemer. The complexity of multi-agent plan recognition. Autonomous Agents and Multi-Agent Systems, 29(1):40–72, Springer, 2015.
Download
Abstract
Multi-agent plan recognition (MAPR) seeks to identify the dynamic team structures and team plans from observations of the action sequences of a set of intelligent agents, based on a library of known team plans (plan library), and an evaluation function. It has important applications in decision support, team work, analyzing data from automated monitoring, surveillance, and intelligence analysis in general. We introduce a general model for MAPR that accommodates different representations of the plan library, and includes single agent plan recognition as a special case. Thus it provides an ideal substrate to investigate and contrast the complexities of single and multi-agent plan recognition. Using this model we generate theoretical insights on hardness, with practical implications. A key feature of these results is that they are baseline, i.e., the polynomial solvability results are given in terms of a compact and expressive plan language (context free language), while the hardness results are given in terms of a less compact language. Consequently the hardness results continue to hold in virtually all realistic plan languages, while the polynomial solvability results extend to the subsets of the context free plan language. In particular, we show that MAPR is in P (polynomial in the size of the plan library and the observation trace) if the number of agents is fixed (in particular 1) but NP-complete otherwise. If the number of agents is a variable, then even the one step MAPR problem is NP-complete. While these results pertain to abduction, we also investigate a related question: adaptation, i.e., the problem of refining the evaluation function based on feedback. We show that adaptation is also NP-hard for a variable number of agents, but easy for a single agent. These results establish a clear distinction between the hardnesses of single and multi-agent plan recognition even in idealized settings, indicating the necessity of a fundamentally different set of techniques for the latter.
BibTeX
@Article{Banerjee15:Complexity,
author = {B. Banerjee and J. Lyle and L. Kraemer},
title = {The complexity of multi-agent plan recognition},
journal = {Autonomous Agents and Multi-Agent Systems},
year = {2015},
volume = {29},
number = {1},
pages = {40--72},
publisher = {Springer},
abstract = {Multi-agent plan recognition (MAPR) seeks to identify
the dynamic team structures and team plans from observations of the
action sequences of a set of intelligent agents, based on a library of
known team plans (plan library), and an evaluation function. It has
important applications in decision support, team work, analyzing data
from automated monitoring, surveillance, and intelligence analysis in
general. We introduce a general model for MAPR that accommodates
different representations of the plan library, and includes single agent
plan recognition as a special case. Thus it provides an ideal substrate
to investigate and contrast the complexities of single and multi-agent
plan recognition. Using this model we generate theoretical insights on
hardness, with practical implications. A key feature of these results is
that they are baseline, i.e., the polynomial solvability results are
given in terms of a compact and expressive plan language (context free
language), while the hardness results are given in terms of a less
compact language. Consequently the hardness results continue to hold in
virtually all realistic plan languages, while the polynomial solvability
results extend to the subsets of the context free plan language. In
particular, we show that MAPR is in P (polynomial in the size of the
plan library and the observation trace) if the number of agents is fixed
(in particular 1) but NP-complete otherwise. If the number of agents is
a variable, then even the one step MAPR problem is NP-complete. While
these results pertain to abduction, we also investigate a related
question: adaptation, i.e., the problem of refining the evaluation
function based on feedback. We show that adaptation is also NP-hard for
a variable number of agents, but easy for a single agent. These results
establish a clear distinction between the hardnesses of single and
multi-agent plan recognition even in idealized settings, indicating the
necessity of a fundamentally different set of techniques for the
latter.},
}
Generated by bib2html.pl (written by Patrick Riley ) on Sat May 29, 2021 15:48:22