%% This LaTeX-file was created by <galk> Fri Feb 25 15:35:13 2000
%% LyX 1.0 (C) 1995-1999 by Matthias Ettrich and the LyX Team

%% Do not edit this file unless you know what you are doing.
\documentclass[twoside,11pt]{article}
\usepackage[T1]{fontenc}
%\setcounter{secnumdepth}{2}
%\setcounter{tocdepth}{2}
\usepackage{color}
\usepackage{graphics}
\usepackage{algorithm}
\usepackage{subfigure}
\usepackage{amsmath}
\usepackage{amsthm}


\makeatletter


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% LyX specific LaTeX commands.
\providecommand{\LyX}{L\kern-.1667em\lower.25em\hbox{Y}\kern-.125emX\@}
\newcommand{\noun}[1]{\textsc{#1}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Textclass specific LaTeX commands.

\theoremstyle{plain}    
\newtheorem{thm}{Theorem} 
\theoremstyle{plain}    
\newtheorem*{thm*}{Theorem} 
\theoremstyle{plain}    
\newtheorem{lem}{Lemma} 
\theoremstyle{plain}    
\newtheorem*{lem*}{Lemma} %%Delete [thm] to re-start numbering
\theoremstyle{definition}
\newtheorem{defn}{Definition}
\theoremstyle{definition}
\newtheorem{example}{Example}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% User specified LaTeX commands.

\usepackage{algorithm}
\usepackage{algorithmic}
\usepackage{theapa}
\usepackage{jair}


\ShortHeadings{Robust Agent Teams via Socially-Attentive Monitoring}{Kaminka and Tambe}  
\jairheading{12}{2000}{105-147}{10/99}{3/00}
\firstpageno{105}
\makeatother

\begin{document}


\title{Robust Agent Teams via Socially-Attentive Monitoring}


\author{\name Gal A. Kaminka \email galk@isi.edu \\
       \name Milind Tambe \email tambe@isi.edu \\
\addr Information Sciences Institute and Computer Science Department \\
University of Southern California \\
4676 Admiralty Way \\
Los Angeles, CA 90292, USA}

\maketitle

\begin{abstract}
Agents in dynamic multi-agent environments must monitor their peers
to execute individual and group plans. A key open question is how much monitoring
of other agents' states is required to be effective: \emph{The
Monitoring Selectivity Problem}. We investigate this question in
the context of detecting failures in teams of cooperating agents, via \emph{Socially-Attentive
Monitoring,} which focuses on monitoring for failures in the social
relationships between the agents. We empirically and analytically explore a
family of socially-attentive teamwork monitoring algorithms in two dynamic,
complex, multi-agent domains, under varying conditions of task distribution
and uncertainty. We show that a centralized scheme using a complex algorithm
trades correctness for completeness and requires monitoring all teammates. In
contrast, a simple distributed teamwork monitoring algorithm results in correct
and complete detection of teamwork failures, despite relying on limited, uncertain
knowledge, and monitoring only key agents in a team. In addition, we report
on the design of a socially-attentive monitoring system and demonstrate its
generality in monitoring several coordination relationships, diagnosing detected
failures, and both on-line and off-line applications.
\end{abstract}

\section{Introduction}

Agents in complex, dynamic, multi-agent environments must be able to detect,
diagnose, and recover from failures at run-time \cite{toyama97}. For instance,
a robot's grip may be slippery, opponents' behavior may be intentionally difficult
to predict, communications may fail, etc. Examples of such environments include
virtual environments for training \cite{steve,modsaf}, high-fidelity distributed
simulations \cite{ifor,robocup-challenge97}, and multi-agent robotics \cite{parker93,balch-thesis}.
The first key step in this process is execution-monitoring \cite{doyle86,ipem,envelopes92,reece94,atkins97,veloso98}. 

Monitoring execution in multi-agent settings requires an agent to monitor its
peers, since its own correct execution depends also on the state of its peers
\cite{jif-nous,jennings93,parker93,jennings95,sharedplans96,STEAM-jair}. Monitoring
peers is of particular importance in teams, since team-members rely on each
other and work closely together on related tasks: 

\begin{itemize}
\item Monitoring allows team-members to coordinate their actions and plans with teammates,
to help teammates and cooperate without interference. For example, drivers of
cars in a convoy cannot drive without monitoring other cars in the convoy, so
as to not disband the convoy, and to help other drivers if cars break down.
\item Monitoring allows team-members to use peers as dynamic information sources,
for learning new information. For instance, if a driver in a convoy sees that
the other cars in front of it suddenly turn to the left, she can infer the existence
of an obstacle or milestone despite not directly seeing it herself.
\end{itemize}
Previous work has investigated different ways of monitoring in the context of
teams of cooperating agents. For example, theoretical work on SharedPlans \cite{sharedplans99}
has distinguished between \emph{passive monitoring}, in which an agent is notified
when a proposition changes (e.g., via communications), and \emph{active monitoring},
in which an agent actively seeks to find out when a proposition changes (e.g.,
via observations and inference of unobservable attributes). Practical implementations
have investigated the use of passive monitoring via communications \cite{jennings95},
active monitoring via plan-recognition \cite{huber-jif95}, active implicit monitoring
via the environment \cite{fenster95}, and different combinations of these methods \cite{parker93,jennings93,STEAM-jair,lesh99}.
No approach is clearly superior to another: Passive monitoring is generally
perceived as being less costly than active monitoring, but also less reliable \cite{sharedplans99,huber-jif95,aaai98}.

Regardless of the monitoring method, bandwidth and computational limitations
prohibit a monitoring agent from monitoring all other agents to full extent,
all the time \cite{jennings95,durfee95,sharedplans96}. Thus a key open question
is how much monitoring of other agents is required to be effective (in teams)
\cite{jennings93,sharedplans96,sharedplans99}. We call this challenging problem
the \emph{Monitoring Selectivity Problem}, i.e., the problem of selectivity
in observing others and inferring their state (based on the observations) for
monitoring. Although it has been raised in the past, only a framework and minimal
constraints for answers were provided \cite{jennings93,sharedplans96}. For
instance, the theory of SharedPlans requires agents to verify that their intentions
do not conflict with those of teammates \cite{sharedplans96}. However, the methods
by which such verification can take place are left for further investigation
\cite[p. 308]{sharedplans96}. Section \ref{sec:related-work} provides more
details on related work.

This paper begins to address the monitoring selectivity problem in teams, by
investigating monitoring requirements for effective failure detection. We focus
our investigation on detecting failures in the social relationships that ideally
hold between agents in a monitored team. We call such monitoring of social relationships
\emph{socially-attentive} \emph{monitoring}, to differentiate it from other
types of monitoring, such as monitoring for failures in the progress of agents
towards their goals. Here, the term social relationship is used to denote a
relation on attributes of multiple agents' states. Socially-attentive monitoring
in the convoy example involves verifying that agents have common destination
and heading, that their beliefs in driving as a convoy are mutual, etc. For
instance, if the agents are observed to head in different directions, they clearly
do not have a common heading. This is different than monitoring whether their
chosen (common) heading leads towards their (agreed upon) destination.

Monitoring relationships in a team (socially-attentive monitoring) is a critical
task in monitoring team-members. Failures to maintain the team's relationships
can often lead to catastrophic failures on the part of the team, lack of cooperative
behavior and lack of coordination. Such failures are often the result of individual
agent failures, such as failures in an agent's sensors and actuators. Thus socially-attentive
monitoring covers a large class of failures, and promotes robust individual
operation.

We explore socially-attentive monitoring algorithms for detecting teamwork failures
under various conditions of uncertainty. We analytically show that despite the
presence of uncertainty about the actual state of monitored agents, a centralized
\emph{active} monitoring scheme can guarantee failure detection that is either
sound and incomplete, or complete and unsound. However, this requires reasoning
about multiple hypotheses as to the actual state of monitored agents, and monitoring
all agents in the team. We show that active distributed teamwork monitoring
results in both sound and complete detection capabilities, despite using a much
simpler algorithm. This distributed algorithm: (a) uses only a single, possibly
incorrect hypothesis of the actual state of monitored agents, and (b) involves
monitoring only key agents in a team, not necessarily all team-members. Using
a transformation on the analytical constructs, we show analogous results for
centralized failure-detection in mutual-exclusion coordination relationships.

We also conduct an empirical investigation of socially-attentive monitoring
in teams. We present an implemented general socially-attentive monitoring framework
in which the expected ideal social relationships that are to be maintained by
the agents are compared to the actual social relationships. Discrepancies are
detected as possible failures and diagnosed. We apply this framework to two
different complex, dynamic, multi-agent domains, in service of monitoring various
social relationships, both on-line and off-line. Both of these domains involve
multiple interacting agents in collaborative and adversarial settings, with
uncertainties in both perception and action. In one domain, we provide empirical
results for active monitoring which confirm our analytical results. In another
domain we show how off-line socially-attentive monitoring can provide quantitative
teamwork quality feedback to a designer. We also provide initial diagnosis procedures
for detected failures. 

Our focus in these explorations is on practical algorithms that have guarantees
on performance in real-world applications. The algorithms we present seek to
complement the use of passive communications-based monitoring (which is unreliable
in many domains) and explore the use of unintrusive key-hole plan-recognition
as an alternative. However, we do not rule out the use of communications---we
simply seek to provide techniques that can work even when communications fail.
Our analytical guarantees of failure-detection soundness and completeness hold
whether monitoring is done through communications or plan-recognition. 

This paper is organized as follows: Section \ref{sec:motivation} presents motivating
examples and background. Section \ref{sec:sam} presents the socially-attentive
monitoring framework. Section \ref{sec:centralized-eval} explores monitoring
selectivity in centralized teamwork monitoring. Section \ref{sec:distributed-sam}
explores monitoring selectivity in distributed teamwork monitoring. Section
\ref{sec:offline} demonstrates the generality of our framework by applying
it in an off-line configuration. Section \ref{sec:discussion} presents investigations
of additional relationship models. Section \ref{sec:related-work} presents
related work, and Section \ref{sec:conclusions} concludes. The two appendices
contain the proofs for theorems presented (Appendix \ref{proofs}), and pseudo-code
for the socially-attentive monitoring algorithms (Appendix \ref{algorithms}). 


\section{\label{sec:motivation}Motivation and Background}

The monitoring selectivity problem this paper addresses---how much monitoring
is required for failure-detection in teams---rose out of growing frustration
with the significant software maintenance efforts in two of our application
domains. In the ModSAF domain, a high-fidelity battlefield virtual environment
\cite{modsaf}, we have been involved in the development of synthetic helicopter
pilots \cite{ifor}. In the RoboCup soccer simulation domain \cite{robocup-challenge97}
we have been involved in developing synthetic soccer players \cite{isis-agents99}.
The environments in both domains are dynamic and complex, and have many uncertainties:
the behavior of other agents (some of it adversarial, some cooperative), unreliable
communications and sensors, actions which may not execute as intended, etc.
Agents in these environments are therefore presented with countless opportunities
for failure despite the designers' best efforts. 

Some examples may serve to illustrate. The following two examples are actual
failures that occurred in the ModSAF domain. We will use these two to illustrate
and explore socially-attentive monitoring throughout this paper:

\begin{example}
Here, a team of three helicopter pilot agents were to fly to a specified way-point
(a given position), where one of the team-members, the \emph{scout}, was to
fly forward towards the enemy, while its teammates (\emph{attackers}) land and
wait for its signal. All of the agents monitored for the way-point. However,
due to an unexpected sensor failure, one of the attackers failed to sense the
way-point. So while the other attacker correctly landed, the failing attacker
continued to fly forward with the scout (see Figure \ref{fig:modsaf-screen}
for a screen shot illustrating this failure).
\end{example}
\begin{example}

In a different run, after all three agents reached the way-point and detected it, the scout has gone forward and identified the enemy. It then sent a message to the waiting attackers to join it and attack the enemy. One of the attackers did not receive the message, and so it remained behind indefinitely while the scout and the other attacker continued the mission alone.

\end{example}

\begin{figure}[htb]
\resizebox*{0.9\textwidth}{!}{\includegraphics{example-1.eps}} 


\caption{\label{fig:modsaf-screen}A plan-view display (the ModSAF domain) illustrating
the failure in Example 1. The thick wavy lines are contour lines.}
\end{figure}
We have collected dozens of similar reports in both the ModSAF and RoboCup domain.
In general, such failures are difficult to anticipate in design time, due to
the huge number of possible states. The agents therefore easily find themselves
in novel states which have not been foreseen by the developer, and the monitoring
conditions and communications in place proved insufficient: In none of the failure
cases reported did the agents involved detect, let alone correct, their erroneous
behavior. Each agent believed the other agents to be acting in coordination
with it, since no communication was received from the other agents to indicate
otherwise. However, the agents were violating the collaboration relationships
between them, as the agents came to disagree on what plan is being executed---a
collaboration relationship failure had occurred. Preliminary empirical results
show that upwards of 30\% of failures reported involved relationship violations
(relationship failures). 

Human observers, however, were typically quick to notice these failures, because
of the clear social misbehavior of the agents in these cases. They were able
to infer that a failure has occurred despite not knowing what exactly happened.
For instance, seeing an attacker continuing to fly ahead despite its teammates'
switching to a different plan (which the human observers inferred from the fact
that one of the teammates, the other attacker, has landed) is sufficient for
an observer to detect that something has gone amiss---without knowing what the
different plan was.

Our analysis showed that the agents were not monitoring each other sufficiently.
However, a naive solution of continuous communications between the agents was
clearly impractical since: (i) the agents are operating in a hostile environment;
(ii) the communications overheads would have been prohibitive; and (iii) in
fact, it was the communications equipment itself that broke down in some cases.
We therefore sought practical ways to achieve quick detection of failure, based
on the limited ambiguous knowledge that was available to a monitoring agent.


\section{\label{sec:sam}Socially-Attentive Monitoring}

We begin with an overview of the general structure of a socially-attentive monitoring
system, shown in Figure \ref{fig:sam-structure}. It consists of: (1) a social
relationship knowledge-base containing models of the relationships that should
hold among the monitored agents, enabling generation of \emph{expected ideal
behavior} in terms of relationships (Section \ref{knowledge-base}); (2) an
agent and team modeling component, responsible for collecting and representing
knowledge about the monitored agents' \emph{actual behavior} (Section \ref{agent modeling});
(3) a relationship failure-detection component that monitors for violations
of relationships among monitored agents by contrasting the expected and actual
behavior (Section \ref{detector}); and (4) a relationship diagnosis component
that verifies the failures, and provides an explanation for them (Section \ref{diagnoser}).
The resulting explanation (diagnosis) is then used for recovery, e.g., by a
negotiations system \cite{kraus98}, or a general (re)planner \cite{ipem}.

\begin{figure}[htb]
{\par\centering \resizebox*{0.9\columnwidth}{!}{\includegraphics{sam-structure.eps}} \par}


\caption{\label{fig:sam-structure}The general structure of a socially-attentive monitoring
system.}
\end{figure}



\subsection{\label{knowledge-base}A Knowledge-Base of Relationship Models }

We take a relationship among agents to be a relation on their state attributes.
A relationship model thus specifies how different attributes of an agent's state
are related to those of other agents in a multi-agent system. These attributes
can include the beliefs held by the agents, their goals, plans, actions, etc.
For example, many teamwork relationship models require that team-members have
mutual belief in a joint goal \cite{jif-nous,jennings95}. A spatial formation
relationship \cite{parker93,balch-thesis} specifies relative distances, and
velocities that are to be maintained by a group of agents (in our domain, helicopter
pilots). Coordination relationships may specify temporal relationships that
are to hold among the actions of two agents, e.g., business contractors \cite{malone91}.
All such relationships are \emph{social}---they explicitly specify how multiple
agents are to act and what they are to believe if they are to maintain the relationships
between them. 

The relationship knowledge-base contains models of the relationships that are
supposed to hold in the system, and specifies the agents that are participating
in the relationships. The knowledge-base guides the agent-modeling component
in selecting agents to be monitored, and what attributes of their state need
be represented (for detection and diagnosis). It is used by the failure detection
component to generate expectations which are contrasted with actual relationships
maintained by the agents. And it provides the diagnosis component with detailed
information about how agents' states' attributes are related, to drive the diagnosis
process. Our implementation of socially-attentive monitoring in teams uses four
types of relationships: \emph{formations}, \emph{role-similarity}, \emph{mutual
exclusion}, and \emph{teamwork}. 

\begin{sloppypar}
For teamwork monitoring we use the STEAM \cite{STEAM-jair} general domain-independent
model of teamwork, which is based on Cohen and Levesque's Joint Intentions Framework
\cite{jif-aaai,jif-nous} and Grosz, Sidner, and Kraus's SharedPlans \cite{sharedplans90,sharedplans96,sharedplans99}.
However, other teamwork models may be used instead of STEAM. Although STEAM
is used by our pilot and soccer agents to generate collaborative behavior, it
is reused here independently in service of monitoring, i.e., monitored agents
are assumed to be a team, and STEAM is used in monitoring their teamwork. STEAM
and other teamwork models \cite<e.g.,\ >{jif-nous,jennings95,collagen97} require
mutual belief by team members in their joint goals and plans. This characteristic
is used to monitor teamwork in our system. The other relationship models are
used only in a secondary monitoring role. They will be discussed in greater
length in Section \ref{sec:discussion}. 
\end{sloppypar}

\subsection{Knowledge of Monitored Agents and Team}

\label{agent modeling}The agent modeling component is responsible for acquiring
and maintaining knowledge about monitored agents. This knowledge is used to
construct the \emph{actual} relations that exist between agents' states' attributes,
which are compared to the \emph{ideal expected} relations. In this section,
we describe the plan-recognition capabilities of the agent-modeling component
in our implementation and experiments, i.e., the extent of the knowledge that
could be maintained about monitored agents' plans if necessary. Later sections
show that in fact limited, possibly inaccurate, knowledge is sufficient for
effective failure detection. Thus implementations may use optimized agent-modeling
algorithms rather than these full capabilities. Section \ref{diagnoser} will
discuss additional agent-modeling capabilities, necessary for diagnosis.


\subsubsection{Representation}

For monitoring teamwork relationships, we have found that representing agents
in terms of their selected hierarchical reactive plans enables quick monitoring
of their state, and also facilitates further inference of the monitored agents'
beliefs, goals, and unobservable actions, since they capture the agents' decision
processes. 

In this representation, reactive plans \cite{firby87,utc} form a single decomposition
hierarchy (a tree) that represents the alternative controlling processes of
each agent. Each reactive plan in the hierarchy (hereafter referred to simply
as a plan) has selection conditions (also referred to as preconditions) for
when it is applicable, and termination conditions which are used to terminate
or suspend plans. At each given moment, the agent is executing a single path
(root to a leaf) through the hierarchy. This path is composed of plans at different
levels. 

Figure \ref{modsaf-hierarchy} presents a small portion of such a hierarchy,
created for the ModSAF domain. In the case of Example 1, prior to the way-point,
\emph{each of the agents} was executing the path beginning with \texttt{execute-mission}
as highest-level plan, through~\texttt{fly-flight-plan}, \texttt{fly-route},
\texttt{traveling} and \texttt{low-level}. Upon reaching the way-point, they
were all supposed to switch from \texttt{fly-flight-plan} and its descendents
to \texttt{wait-at-point}. The attackers would then select \texttt{just-wait}
as a child of \texttt{wait-at-point}, while the scout would select \texttt{scout-forward}
and its descendents. Of course, the failing attacker did not detect the way-point
and so the termination conditions for \texttt{fly-flight-plan} and the selection
conditions for \texttt{wait-at-point} were not satisfied and the failing attacker
continued to execute \texttt{fly-flight-plan} and its descendents. 

\begin{figure}[htb]
\resizebox*{0.9\columnwidth}{!}{\includegraphics{modsaf-hierarchy.eps}} 


\caption{\label{modsaf-hierarchy}Portion of Hierarchical Reactive Plan Library for
ModSAF Domain (Team plans are boxed. These are explained in Section \ref{detector}).}
\end{figure}
 


\subsubsection{Acquisition}

From a practical perspective, while the agents may cooperatively report to the
monitoring agent on their own state using communications, it requires communication
channels to be sufficiently fast, reliable and secure. This is unfortunately
not possible in many realistic domains, as our examples demonstrate (Section
\ref{sec:motivation}).

Alternatively, a monitor may use plan-recognition to infer the agents' unobservable
state from their observable behavior. This approach is unintrusive and robust
in face of communication failures. Of course, the monitor may still benefit
from focused communications with the other agents, but would not be critically
dependent on them.

To enable plan-recognition using reactive plans (our chosen representation),
we have employed a reactive plan-recognition algorithm called RESL (REal-time
Situated Least-commitments). The key capability required is to allow explicit
maintenance of hierarchical plan hypotheses matching each agent's observed behavior,
while pruning of hypotheses which are deemed incorrect or useless for monitoring
purposes. RESL works by expanding the entire plan-library hierarchy for each
modeled agent, and tagging all paths matching the observed behavior of the agent
being modeled (see Appendix \ref{algorithms} for pseudo-code for the algorithm).
Heuristics and external knowledge may be used to eliminate paths (hypotheses)
which are deemed inappropriate---indeed such heuristics will be explored shortly.
RESL's basic approach is very similar to previous work in reactive plan recognition
\cite{rao94} and team-tracking \cite{rescteam}, which have been used successfully
in the ModSAF domain, and share many of RESL's properties. However, RESL adds
belief-inference capabilities which are used in the diagnosis process, discussed
below (Section \ref{diagnoser}).

Figure \ref{fig:resl} gives a simplified presentation of the plan hierarchies
for a variation of Example 1, in which all the agents correctly detected the
way-point, i.e., no failure has occurred (note that some plans at intermediate
levels have been abstracted out in the figure). The scout (Figure \ref{fig:resl}a)
and the two attackers (Figures \ref{fig:resl}b, \ref{fig:resl}c) switched
from the \texttt{fly-flight-plan} plan (denoted by \texttt{F)} to the \texttt{wait-at-point}
plan (denoted by \texttt{W}). An outside observer using RESL infers explanations
for each agent's behavior by observing the agents. The scout continues to fly
ahead, its speed and altitude matching \texttt{low-level}, one of the possible
flight-methods under both the \texttt{fly-flight-plan} (\texttt{F}) and \texttt{wait-at-point}
(\texttt{W}) plans. Thus they are both tagged as possible hypotheses for the
scout's executing plan hierarchy. Similarly, as the attackers land, RESL recognizes
that they are executing the \texttt{just-wait} plan. However, this plan can
be used in service of either the \texttt{W} or the \texttt{ordered-halt} (\texttt{H})
plan---a plan in which the helicopters are ordered by their headquarters to
land immediately. Thus both \texttt{H} and \texttt{W} are tagged as explanations
for each of the attackers' states (at the second level of the hierarchies).
For all agents, RESL identifies the plan \texttt{execute-mission} as the top-level
plan. In this illustration, the actual executing paths of the agents are marked
with filled arrows. Other \emph{individual modeling} hypotheses that match the
observed behavior are marked using dashed arrows. An outside observer, of course,
has no way of knowing which of the possible hypotheses is correct. 

\begin{figure}[htb]
{\par\centering \resizebox*{0.9\textwidth}{!}{\includegraphics{resl-full.eps}} \par}


\caption{\label{fig:resl}Scout (a) and Attackers' (b, c) actual and recognized \emph{abbreviated}
reactive plan hierarchies.}
\end{figure}
 \begin{sloppypar}

Once individual modeling hypotheses are acquired for each individual agent (using
plan-recognition in our implementation, but potentially also by communications),
the monitoring agent must combine them to create team-modeling hypotheses as
to the state of the team as a whole. The monitoring agent selects a single individual
modeling hypothesis for each individual agent and combines them into a single
team-modeling hypothesis. Several such team-modeling hypotheses are possible
given multiple hypotheses for individual agents. For instance, in Figure \ref{fig:resl},
while all team-hypotheses will have \texttt{execution-mission} as the top-level
plan, there are eight different team-hypotheses which can be differentiated
by their second-level plan: (\texttt{W},\texttt{W},\texttt{W}), (\texttt{W},\texttt{W},\texttt{H}),
(\texttt{W},\texttt{H},\texttt{W}), (\texttt{W},\texttt{H},\texttt{H}), (\texttt{F},\texttt{W},\texttt{W}),
(\texttt{F},\texttt{W},\texttt{H}), (\texttt{F},\texttt{H},\texttt{W}), (\texttt{F},\texttt{H},\texttt{H}).
If the observer is a member of the team, it knows what it is executing itself,
but would still have multiple-hypotheses about its teammates' states. For instance,
if the attacker in Figure \ref{fig:resl}b is monitoring its teammates, its
hypotheses at the second level would be (\texttt{W},\texttt{W},\texttt{W}),
(\texttt{W},\texttt{W},\texttt{H}), (\texttt{F},\texttt{W},\texttt{W}), (\texttt{F},\texttt{W},\texttt{H}). 

\end{sloppypar}

To avoid explicitly representing a combinatorial number of hypotheses, RESL
explicitly maintains all candidate hypotheses for each agent individually, but
not all combinations of individual models as team hypotheses. Instead, these
combinations are implicitly represented. Thus the number of hypotheses explicitly
maintained grows linearly in the number of agents. 


\subsection{\label{detector}Relationship Violation Detection}

\begin{sloppypar}The failure-detection component detects violations of the social relationships
that should hold among agents. This is done by comparing the ideal expected
relationships to their actual maintenance by the agents. For teamwork specifically,
the relationship model requires team-members to always agree on which \emph{team}
plan is jointly executed by the team, similarly to Joint Responsibility \cite{jennings95},
and SharedPlans \cite{sharedplans96}. If this requirement fails in actuality
(i.e., the agents are executing different team plans) then a teamwork failure
has occurred. \end{sloppypar}

The basic teamwork failure detection algorithm is as follows. The monitored
agents' plan-hierarchies are processed in a top-down manner. The detection component
uses the teamwork model to tag specific plans as team plans, explicitly representing
joint activity by the team (these plans are boxed in Figures \ref{modsaf-hierarchy},
\ref{fig:comparison} and \ref{fig:resl}). The team-plans in equal depths of
the hierarchies are used to create team-modeling hypotheses. For each hypothesis,
the plans of different agents are compared to detect disagreements. Any difference
found is an indication of failure. If no differences are found, or if the comparison
reaches individual plans (non-team, therefore non-boxed in the figures) no failure
is detected. Individual plans, which may be chosen by an agent individually
in service of team plans are not boxed in these figures, and are handled using
other relationships as discussed in Section \ref{sec:discussion}

For instance, suppose the failing attacker from Example 1 is monitoring the
other attacker. Figure \ref{fig:comparison} shows its view of its own hierarchical
plan on the left. The path on the right represents the state of the other attacker
(who has landed). This state has been inferred in this example from observations
made by the monitoring attacker (here, we are assuming that the plan-recognition
process has resulted in one correct hypothesis for each agent. We will discuss
more realistic settings below). In Figure \ref{fig:comparison}, the difference
that would be detected is marked by the arrow between the two plans at the second
level from the top. While the failing attacker is executing the \texttt{fly-flight-plan}
team-plan (on the left), the other attacker is executing the \texttt{wait-at-point}
team-plan (on the right). The disagreement on which team-plan is to be executed
is a failure of teamwork.

\begin{figure}[htb]
{\par\centering \includegraphics{comparison.eps} \par}


\caption{\label{fig:comparison}Comparing two hierarchical plans. The top-most difference
is at level 2.}
\end{figure}


Detecting disagreements is difficult with multiple team-modeling hypotheses,
since they may imply contradictory results with respect to failure detection:
Some hypotheses may imply that a failure had occurred in the team, while others
may not. Unfortunately, this is to be expected in realistic applications. For
instance, Figure \ref{fig:resl} (Section \ref{agent modeling}) shows several
hypotheses that are possible based on the same observations. However, one of
the hypotheses, (\texttt{W},\texttt{W},\texttt{W}), implies no failure has occurred---all
the agents are in agreement on which team-plan is executing---while another
hypothesis, (\texttt{F},\texttt{W},\texttt{H}), implies failures have occurred. 

To limit reasoning to only a small number of team hypotheses, while not restricting
failure-detection capabilities, we use a disambiguation heuristic that ranks
team-modeling hypotheses by the level of \emph{coherence} they represent. This
heuristic is provided as an initial solution. Later sections will examine additional
heuristics.

\begin{defn}
\label{def:incoherence level}The \emph{coherence} level of a multi-agent modeling
hypothesis is defined as the ratio of the number of agents modeled to the number
of plans contained in the hypothesis.
\end{defn}
This definition results in a partial ordering of the hypotheses set, from the
least coherent hypothesis (one that assigns each agent a different plan than
its team-mates), to the most coherent hypothesis (that assigns the same plan
to all team members). For instance, the hypothesis (\texttt{F},\texttt{W},\texttt{H})
would have the lowest level of coherence, 1, since it implies complete breakdown
of teamwork---every agent is executing a different plan. The hypothesis (\texttt{W},\texttt{W},\texttt{W})
would have a coherence level of 3, the highest level of coherence for the group
of three agents, since they are all assigned the same plan. Ranked between them
would be the hypothesis (\texttt{W},\texttt{W},\texttt{H}), with a single teamwork
failure (disagreement on W and H) and a coherence level of 3/2. 

The detection component selects a single maximally-coherent team-modeling hypothesis
(ties broken randomly). The intuition for using coherence is that failures to
agree occur despite the agents' attempts at teamwork. Thus we expect more agreements
than disagreements in the team. The coherence level of a team-hypothesis is
inversely related to the number of teamwork failures implied by the hypothesis.
Selecting a maximally-coherent hypothesis therefore corresponds to the minimum-number-of-failures
heuristic commonly used in diagnosis \cite{modelbaseddiagnosis}. 

For the case depicted in Figure \ref{fig:resl}, the complete detection process
may be conceptualized as follows\footnote{%
Other implementations may make use of optimized algorithms in which the heuristics
are integrated into the agent-modeling algorithm.
}. Suppose that one of the attackers, whose hierarchy is described in Figure
\ref{fig:resl}b, is monitoring the team. First, it collects the plan hypotheses
at the top of the hierarchy for each agent (including itself). In this case,
they are \{\texttt{execute-mission}\}, \{\texttt{execute-mission}\}, \{\texttt{execute-mission}\}.
Only one team-modeling hypothesis can be built from these: (\texttt{execute-mission},
\texttt{execute-mission}, \texttt{execute-mission)}. Since this hypothesis shows
no disagreement occurs at this level, the process continues to the second level.
Here, the hypotheses for the first agent on the left are \{\texttt{F},\texttt{W}\},
for the monitoring second agent (since it knows its own state) there is only
one possibility \{\texttt{W}\}, and for the third agent \{\texttt{W},\texttt{H}\}.
As we saw above, the maximally team-coherent hypothesis is (\texttt{W},\texttt{W},\texttt{W})
which is selected. Since it does not indicate failure, the process continues
to the third level. Here the agents are executing individual plans, and so the
comparison process stops. Algorithm \ref{alg:compare} in Appendix \ref{algorithms}
provides greater details about this process.

When sub-teams are introduced, a difference between team-plans may be explained
by the agents in question being a part of different sub-teams. Sub-team members
still have to agree between themselves on the joint sub-team plans, but these
may differ from one sub-team to the next. For now, let us assume that the teams
under consideration are \emph{simple teams}, as defined in Definition \ref{def:simple-team}.
We make this definition in service of later analytical results in which it will
appear as a condition. We return to the issue of sub-teams in Section \ref{sec:dissimilarity}. 

\begin{defn}
\label{def:simple-team}We say that a team $T$ is \emph{simple}, if its plan-hierarchy
involves no different team plans which are to be executed by different sub-teams.
\end{defn}
Intuitively, the idea is that in a simple team, all members of the team jointly
execute each of the team plans in the hierarchy. This definition is somewhat
similar to the definition of a \emph{ground team} in \cite{kinny92}, but it
does not allow sub-team members of a team to have a joint plan which is different
than that of other members.


\subsection{\label{diagnoser}Relationship Diagnosis}

The diagnosis component constructs an explanation for the detected failure,
identifying the failure state and facilitating recovery. The diagnosis is given
in terms of a set of agent belief differences (inconsistencies) that explains
the failure to maintain the relationship. The starting point for this process
is the detected failure (e.g., the difference in team-plans). The diagnosis
process then compares the beliefs of the agents involved to produce a set of
inconsistent beliefs that explain the failure.

Two problems exist in practical applications of this procedure. First, the monitoring
agent is not likely to have access to all of the beliefs held by the monitored
agents, since it is not feasible in practice to communicate all the agents'
beliefs to each other. Second, each agent in a real-world domain may have many
beliefs, and many of them will vary among the agents, though most of them will
be irrelevant to the diagnosis. Thus relevant knowledge may be simply not be
accessible, or may be hidden in mountains of irrelevant facts.

To gain knowledge of the beliefs of monitored agents without relying on communications,
the diagnosis process uses a process of belief ascription. The agent-modeling
component (using RESL in our implementation) maintains knowledge about the selection
and termination conditions of recognized plans (hypotheses). For each recognized
plan hypothesis, the modeling component infers that any termination conditions
for the plan are believed to be false by the monitored agent (since it has not
terminated the plan). We have also found it useful to use an additional heuristic,
and infer that the selection conditions (preconditions) for any plan which \emph{has
just begun execution} are true. The idea is that when a plan is selected for
execution, its preconditions are likely to hold, at least for a short period
of time. This heuristic involves an explicit assumption on the part of our system
that the new plan is recognized as soon as it begins execution. Designers in
other domains will need to verify that this assumption holds. 

For each agent $i$, the inferred termination and selection conditions make up
a set of beliefs $B_i$ for the agent. For instance, suppose an agent is hypothesized
to have just switched from executing \texttt{fly-flight-plan} to \texttt{wait-at-point}.
RESL infers that the agent believes that the way-point was just detected (a
selection condition for \texttt{wait-at-point}). In addition, RESL infers that
the agent believes that an enemy was not seen, and that no order was received
from base to halt the mission (negated termination conditions of \texttt{wait-at-point}). 

To determine the facts that are relevant to the failure, the diagnosis component
uses the teamwork model. The teamwork model dictates which beliefs the agents
hold must be mutually believed by all the agents in the team. Any difference
that is detected in those beliefs is a certain failure, as the team members
do not agree on issues on which agreement is mandatory to participation in the
team. The teamwork model thus specifies that the beliefs contained in the $B_i$
sets should be mutual, and should therefore be consistent: 


\[
\bigcup _{i}B_{i}\not \vdash \perp \]
 If an inconsistency is detected, the diagnosis procedure looks for contradictions
(disagreements) that would cause the difference in team-plan selection. A difference
in beliefs serves as the diagnosis, allowing the monitoring agent to initiate
a process of recovery, e.g., by negotiating about the conflicting beliefs \cite{kraus98}.

For example, as shown in Section \ref{detector}, the two attackers in Example
1 (Section \ref{sec:motivation}) differ in their choice of a team-plan: One
attacker is continuing execution of the \texttt{fly-flight-plan} plan, in which
the helicopters fly in formation. The other attacker has detected the way-point,
terminated \texttt{fly-flight-plan} and has switched to \texttt{wait-at-point},
landing immediately (Figure \ref{fig:comparison}). When the failing attacker
monitors its team-mate, it detects a difference in the team-plans (Section \ref{detector}),
and the detected difference is passed to diagnosis. The failing attacker makes
the following inferences:

\begin{enumerate}
\item \texttt{Fly-flight-plan} has three termination conditions: (a) seeing the enemy,
(b) detecting the way-point, or (c) receiving an order to halt. The failing
attacker (left hierarchy in Figure \ref{fig:comparison}) knows its own belief
that none of these conditions hold, and thus 
\[
B_{1}=\{\neg WayPoint,\neg Enemy,\neg HaltOrder\}\]

\item \texttt{Wait-at-point} has one selection condition: the way-point has been detected.
Its termination condition is that the scout has sent a message to join it, having
identified the enemy's position. The diagnosis component in this case therefore
infers that for the other attacker (right hierarchy in Figure \ref{fig:comparison})
\[
B_{2}=\{WayPoint,\neg ScoutMessageReceived\}\]
  
\end{enumerate}
\begin{sloppypar}Then,  
\[ B_{1}\cup B_{2}=\{\neg WayPoint,WayPoint,\neg Enemy,\neg ScoutMessageReceived,\neg HaltOrder\} \]
which is inconsistent. The inconsistency (disagreement between the attackers)
is \( \{\neg WayPoint,WayPoint\} \), i.e., contradictory beliefs about \( Waypoint \).
Thus now the failing attacker knows that its team-mate has seen the way-point.
It can choose to quietly adapt this belief, thereby terminating its own \texttt{fly-flight-plan}
and selecting \texttt{wait-at-point}, or it may choose other recovery actions,
such as negotiating with the other attacker on whether the way-point has been
reached. \end{sloppypar}

We have found these diagnosis procedures to be useful in many of the failures
detected by socially-attentive monitoring (see Section \ref{sec:centralized-eval}
for evaluation and discussion). However, since this paper focuses on the monitoring
selectivity problem in \emph{detection}, we leave further investigation of the
diagnosis procedures to future work. 


\section{\label{sec:centralized-eval}Monitoring Selectivity in Centralized Teamwork
Monitoring}

Using the socially-attentive framework of Section \ref{sec:sam} we systematically
examine all failure permutations of Examples 1 and 2 (Section \ref{sec:motivation})
under a centralized teamwork monitoring configuration, where a single team-member
is monitoring the team. We vary the agents failing (attacker, attacker and scout,
etc.) and the role of the monitoring agent (attacker or scout). We report on
the empirical results of detecting and diagnosing failures in all cases. Using
these empirical results as a guide, we explore centralized teamwork monitoring
analytically. We show that even under monitoring uncertainty, centralized teamwork
monitoring can provide either sound or complete detection results (but not both). 

As a starting point for our exploration, the monitoring agent uses a single
maximally-coherent team-modeling hypothesis as discussed in Section \ref{detector}.
We begin with Example 2. The normal order of execution is \texttt{wait-at-point}
(\texttt{W}), followed by \texttt{join-scout} (\texttt{J}). During the execution
of \texttt{W}, the two attackers land and wait for the scout to visually identify
the enemy's position. Upon identification, the scout sends them a message to
join it, which triggers the selection of the \texttt{J} plan, and the termination
of the \texttt{W} plan. When executing \texttt{J}, the scout hovers at low altitude,
waiting for the attackers to join it. Any failures here are on the part of the
attackers (they cannot receive the message) or on the part of the scout (it
cannot send it). These failures arise, for instance, if the radio is broken
or team-members are out of range. When an agent fails, it continues to execute
\texttt{W} instead of switching to \texttt{J}.

Table \ref{table:example-2} summarizes the permutations of Example 2. The permutation
number appear in the first column. The next three columns show the actual plans
selected by the three agents A1, A2 and A3 in each permutation. The second-to-last
column shows whether a relationship failure has occurred in each case, i.e.,
whether disagreement exists between the agents. Finally, the last column details
the physical conditions in each case. There are five possible failure permutations:
In case 1, none of the agents failed. In cases 2 and 3 one attacker failed.
In case 4 the scout failed to send a message or both attackers failed to receive
it. In case 5 the scout does not identify the enemy's position (so no message
is sent, and all three agents continue to execute the \texttt{W} plan). Other
permutations are not possible, since no attacker can switch to the \texttt{J}
plan without the scout. 

\begin{table}[htb]
\vspace{0.3cm}
{\centering \begin{tabular}{|c|c|c|c|c|c|}
\hline 
\textbf{\noun{\tiny Case}}&
\multicolumn{3}{|c|}{ \textbf{\noun{\tiny Actual Executing Plans}}}&
\textbf{\noun{\tiny Relationship Failure}}&
\textbf{\noun{\tiny Physical}} \textbf{\tiny }\\
\cline{2-4} 
\textbf{\tiny \#}&
\textbf{\noun{\tiny Attacker A1}}\textbf{\tiny }&
\textbf{\noun{\tiny Attacker A2}}\textbf{\tiny }&
\textbf{\noun{\tiny Scout A3}}\textbf{\tiny }&
\textbf{\noun{\tiny Occurred}}\textbf{\tiny ?}&
\textbf{\noun{\tiny Failure}}\textbf{\tiny }\\
\hline 
{\tiny 1}&
{\tiny J}&
{\tiny J}&
{\tiny J}&
{\tiny -}&
{\tiny -}\\
\hline 
{\tiny 2}&
{\tiny W}&
{\tiny J}&
{\tiny J}&
{\tiny +}&
{\tiny A1 fails to receive}\\
\hline 
{\tiny 3}&
{\tiny J}&
{\tiny W}&
{\tiny J}&
{\tiny +}&
{\tiny A2 fails to receive}\\
\hline 
{\tiny 4}&
{\tiny W}&
{\tiny W}&
{\tiny J}&
{\tiny +}&
{\tiny A3's message lost}\\
\hline 
{\tiny 5}&
{\tiny W}&
{\tiny W}&
{\tiny W}&
{\tiny -}&
{\tiny Enemy not identified}\\
\hline 
\end{tabular}\tiny \par}\vspace{0.3cm}


\caption{\label{table:example-2}All possible failure permutations of the broken radio-link
scenario (Example 2).}
\end{table}


For instance, case 2 in Table \ref{table:example-2} corresponds to Example
2. The scout (A3) has detected the enemy, switched to plan \texttt{J}, and sent
a message to the attackers to join it. One attacker (A2) received the message,
switched to plan \texttt{J}, and began flying towards the scout. However, the
remaining attacker (A1) failed to receive the message, and so it maintains its
position, continuing to execute \texttt{W} and failing to switch to \texttt{J}.
Since the agents are no longer in agreement on which team plan should be jointly
executed, a teamwork failure has occurred. Condition monitors were used in the
original failure case to monitor for the scout's message. However failures in
communications resulted in these monitoring conditions to be rendered useless. 

One key issue is raised by case 5 in Table \ref{table:example-2}. Here, due
to the scout's inability to identify the enemy's position (perhaps due to failure
on the scout's part, perhaps because the enemy is simply not there), the three
helicopter pilots remain in agreement that the enemy has not been identified.
Here, even though clearly the pilots are failing to make progress towards the
task goals (the scout continues to search for the enemy indefinitely), no relationship
failure is taking place, since the agents are maintaining the teamwork relationship
while failing to make progress. This clearly demonstrates that not all failures
are necessarily relationship failures. 

Table \ref{table:example2scout} presents the results of the scout monitoring
its teammates in Example 2, using a maximally team-coherent hypothesis as the
basis for detection. The first column again shows the case number, for reference
into Table \ref{table:example-2}. The next three columns show the scout's (A3's)
hypothesis about what plan each agent is executing according to the maximal
coherence heuristic. The next two columns show whether a failure was detected,
and whether it was diagnosed correctly. The last column shows the detection
class (discussed below). 

\begin{table}[htb]
{\centering \begin{tabular}{|c|c|c|c|c|c|c|}
\hline 
\textbf{\noun{\tiny Case}}\textbf{\tiny }&
\multicolumn{3}{|c|}{\textbf{\noun{\tiny A3's Hypothesized Executing Plans}} \textbf{\tiny }}&
\textbf{\noun{\tiny Relationship Failure}}\textbf{\tiny }&
\textbf{\noun{\tiny Diagnosis}}&
\textbf{\noun{\tiny Detection}}\\
\cline{2-4} 
\textbf{\tiny \#}\textbf{\noun{\tiny }}&
\textbf{\noun{\tiny Attacker A1}}&
\textbf{\noun{\tiny Attacker A2}}&
\textbf{\noun{\tiny Scout A3}}&
\textbf{\noun{\tiny Detected?}}\textbf{\tiny }&
\textbf{\noun{\tiny Success?}}\textbf{\tiny }&
\textbf{\noun{\tiny Class}}\\
\hline 
{\tiny 1}&
{\tiny J}&
{\tiny J}&
{\tiny J}&
{\tiny -}&
{\tiny n/a}&
{\tiny True Negative}\\
\hline 
{\tiny 2}&
{\tiny W}&
{\tiny J}&
{\tiny J}&
{\tiny +}&
{\tiny +}&
{\tiny True Positive}\\
\hline 
{\tiny 3}&
{\tiny J}&
{\tiny W}&
{\tiny J}&
{\tiny +}&
{\tiny +}&
{\tiny True Positive}\\
\hline 
{\tiny 4}&
{\tiny H}&
{\tiny H}&
{\tiny J}&
{\tiny +}&
{\tiny -}&
{\tiny True Positive}\\
\hline 
{\tiny 5}&
{\tiny W}&
{\tiny W}&
{\tiny W}&
{\tiny -}&
{\tiny n/a}&
{\tiny True Negative}\\
\hline 
\end{tabular}\tiny \par}

\caption{\label{table:example2scout}Scout's (A3) monitoring results in all permutations
of Example 2.}
\end{table}


For example, case 2 in Table \ref{table:example2scout} shows the results of
the scout monitoring in the original failure in Example 2 (Section \ref{sec:motivation}).
Using RESL, and selecting a maximally-coherent hypothesis, the scout hypothesizes
that the non-moving attacker is executing \texttt{W} (case 2, column 2), while
the moving attacker is executing \texttt{J} (case 2, column 3). The scout of
course knows that its own selected plan \texttt{J} (case 2, column 4). A violation
of the teamwork relationship is thus detected (case 2, column 5), since A1's
\texttt{W} is not in agreement with the rest of the team's \texttt{J}. Furthermore,
the diagnosis was successful in identifying the cause for the failure, i.e.,
the fact that the enemy's position has been identified by the scout, but no
knowledge of this was passed on to the failing attacker (case 2, column 6).

The last column of Table \ref{table:example2scout} shows the detection class
of each failure. The detection class of a case can be one of: true positive,
true negative, false positive, and false negative. These correspond to the following
possible monitoring outcomes: A true positive is an outcome where a relationship
failure has actually occurred, and has been detected. A true negative is where
no failure has occurred, and the system correctly reports none is being detected.
A false positive is where no failure has occurred, but the system nevertheless
incorrectly detects one, and a false negative is where a failure has occurred,
but the system fails to detect it. Table \ref{table:example2scout} shows that
in all permutations of Example 2 the teamwork monitoring techniques did not
encounter the problematic false positive or false negative cases.

A closer look at these results hints at a key contribution of this paper in
addressing the monitoring selectivity problem: Effective failure detection can
take place despite the use of uncertain, limited, knowledge about monitored
agents. In case 4 of Table \ref{table:example2scout}, the monitoring agent
was able to detect the failure \emph{despite being wrong about the state of
the agents involved}.~\texttt{}The scout believes that the two attackers are
executing the \texttt{H} (\texttt{ordered-halt}) plan, but they are actually
executing, \texttt{W}. \texttt{H} is selected when a command is received from
headquarters to halt execution and hover in place. From the scout's perspective,
a hovering attacker can therefore be inferred to be executing \texttt{H} or
\texttt{W.} Thus two equally-ranked maximally-coherent hypotheses exist: the
two attackers are either both executing \texttt{W} or both executing \texttt{H}.
A random selection was made, and in this case resulted in the wrong hypothesis
being selected. Nevertheless, a violation of the teamwork relationships was
detected, as neither \texttt{H} or \texttt{W} agrees with the scout's \texttt{J}. 

However, as the last column of case 4 shows (in Table \ref{table:example2scout}),
the diagnosis procedures are sensitive to the selection of the team-modeling
hypothesis. The hypothesis used in this case does not correctly reflect the
true state of the agents, and so despite the scout's success to detect a failure
in this case, the diagnosis procedures fail to provide correct diagnosis (the
diagnosis was successful in the two other failure cases). This phenomenon repeats
in other empirical results we provide below: diagnosis failed whenever the hypothesis
chosen was incorrect, although it was sufficient for detection. We intend to
explore ways to improve the accuracy of the hypotheses in future work, and therefore
will not address this issue in this paper anymore. The failure detection capabilities
are a significant improvement in themselves, since the agents know with certainty
that a failure has occurred, even if their diagnosis of it is incorrect.

Many social and physical failures are successfully captured using the team-coherence
heuristic for monitoring selectivity. In fact, in our permutations of Example
2, no matter which one of the agents was the monitor, all failures to maintain
relationship (i.e., all physical failures except for one in which the team remains
in agreement) were detected reliably, although sometimes diagnosis failed. This
result is especially surprising considering that only a single agent did the
monitoring. Previous monitoring methods (condition monitors and communications)
were unable to detect the failures, despite being used by all three agents .

Tables \ref{table:example1} and \ref{table:example1attacker} present further
empirical results, on the basis of Example 1. Table \ref{table:example1} presents
all failure permutations of Example 1 in the same format as Table \ref{table:example-2}.
The normal order of execution of these plans is as follows: All agents jointly
execute the \texttt{fly-flight-plan} (\texttt{F}) plan until they detect the
way-point. They then switch to the \texttt{wait-at-point} (\texttt{W}) plan,
in which the two attackers land while the scout continues to fly ahead to identify
the enemy. The failures here are all on the part of the agents to detect the
way-point, and thus to switch to the \texttt{W} plan. 

\begin{table}[htb]
\vspace{0.3cm}
{\centering \begin{tabular}{|c|c|c|c|c|c|}
\hline 
\textbf{\noun{\tiny Case}}&
\multicolumn{3}{|c|}{ \textbf{\noun{\tiny Actual Executing Plans}}}&
\textbf{\noun{\tiny Relationship Failure}}&
\textbf{\noun{\tiny Physical}} \textbf{\tiny }\\
\cline{2-4} 
\textbf{\tiny \#}&
\textbf{\noun{\tiny Attacker A1}}\textbf{\tiny }&
\textbf{\noun{\tiny Attacker A2}}\textbf{\tiny }&
\textbf{\noun{\tiny Scout A3}}\textbf{\tiny }&
\textbf{\noun{\tiny Occurred}}\textbf{\tiny ?}&
\textbf{\noun{\tiny Failure}}{\tiny }\\
\hline 
{\tiny 1}&
{\tiny W}&
{\tiny W}&
{\tiny W}&
{\tiny -}&
{\tiny -}\\
\hline 
{\tiny 2}&
{\tiny F}&
{\tiny W}&
{\tiny W}&
{\tiny +}&
{\tiny A1 vision fails}\\
\hline 
{\tiny 3}&
{\tiny W}&
{\tiny F}&
{\tiny W}&
{\tiny +}&
{\tiny A2 vision fails}\\
\hline 
{\tiny 4}&
{\tiny F}&
{\tiny F}&
{\tiny W}&
{\tiny +}&
\textcolor{black}{\tiny A1, A2 vision fails}{\tiny }\\
\hline 
{\tiny 5}&
{\tiny W}&
{\tiny W}&
{\tiny F}&
{\tiny +}&
\textcolor{black}{\tiny A3 vision fails}{\tiny }\\
\hline 
{\tiny 6}&
{\tiny F}&
{\tiny W}&
{\tiny F}&
{\tiny +}&
{\tiny A1, A3 vision fails}\\
\hline 
{\tiny 7}&
{\tiny W}&
{\tiny F}&
{\tiny F}&
{\tiny +}&
{\tiny A2, A3 vision fails}\\
\hline 
{\tiny 8}&
{\tiny F}&
{\tiny F}&
{\tiny F}&
{\tiny -}&
{\tiny A1,2,3 vision fails}\\
\hline 
\end{tabular}\tiny \par}\vspace{0.3cm}


\caption{\label{table:example1}All failure permutations of the undetected way-point
scenario (Example 1).}
\end{table}


\begin{table}[htb]
{\centering \begin{tabular}{|c|c|c|c|c|c|}
\hline 
\textbf{\noun{\tiny Case}}\textbf{\tiny }&
\multicolumn{3}{|c|}{\textbf{\noun{\tiny A1's Hypothesized Executing Plans}} \textbf{\tiny }}&
\textbf{\noun{\tiny Relationship Failure}}\textbf{\tiny }&
\textbf{\noun{\tiny Detection}}\textbf{\tiny }\\
\cline{2-4} 
\textbf{\tiny \#}\textbf{\noun{\tiny }}&
\textbf{\noun{\tiny Attacker A1}}&
\textbf{\noun{\tiny Attacker A2}}&
\textbf{\noun{\tiny Scout A3}}&
\textbf{\noun{\tiny Detected?}}\textbf{\tiny }&
\textbf{\noun{\tiny Class}}\\
\hline 
{\tiny 1}&
{\tiny W}&
{\tiny W}&
{\tiny W}&
{\tiny -}&
{\tiny True Negative}\\
\hline 
{\tiny 2}&
{\tiny F}&
{\tiny W}&
{\tiny F}&
{\tiny +}&
{\tiny True Positive}\\
\hline 
{\tiny 3}&
{\tiny W}&
{\tiny F}&
{\tiny W}&
{\tiny +}&
{\tiny True Positive}\\
\hline 
\textbf{\tiny 4}&
\textbf{\tiny F}&
\textbf{\tiny F}&
\textbf{\tiny F}&
\textbf{\tiny -}&
\textbf{\tiny False Negative}\\
\hline 
\textbf{\tiny 5}&
\textbf{\tiny W}&
\textbf{\tiny W}&
\textbf{\tiny W}&
\textbf{\tiny -}&
\textbf{\tiny False Negative}{\tiny }\\
\hline 
{\tiny 6}&
{\tiny F}&
{\tiny W}&
{\tiny F}&
{\tiny +}&
{\tiny True Positive}\\
\hline 
{\tiny 7}&
{\tiny W}&
{\tiny F}&
{\tiny F}&
{\tiny +}&
{\tiny True Positive}\\
\hline 
{\tiny 8}&
{\tiny F}&
{\tiny F}&
{\tiny F}&
{\tiny -}&
{\tiny True Negative}\\
\hline 
\end{tabular}\tiny \par}

\caption{\label{table:example1attacker}Attacker's (A1) monitoring results in all permutations
of Example 1.}
\end{table}


Table \ref{table:example1attacker} present the monitoring results for all permutations
of Example 1. Here the attacker A1 is monitoring the team using again a maximally
team-coherent hypothesis in detecting failures. The results show that A1 is
successful in detecting all teamwork failures but two (cases 4-5, highlighted
in bold face). 

These two false outcomes are both false negatives. In both these cases, the
monitoring attacker A1 picked an incorrect hypothesis for the scout, since the
scout's actions lead to ambiguous interpretations. The scout is to fly forward
(to scout the enemy) if it detected the way-point (plan \texttt{W}), but also
if it did not (then it would be flying ``in formation''--plan \texttt{F}).
The use of the maximal team-coherence heuristic causes A1 to prefer a hypothesis
in which the scout is in agreement with the attackers when in fact it is not.
For example, in case 4, the two attackers have failed to detect the way-point
and are executing \texttt{F}. Observing the scout, the monitoring attacker A1
is not sure whether the scout is executing \texttt{F} or \texttt{W}. However,
believing that the scout is executing \texttt{F} results in a maximally-coherent
team-modeling hypothesis (all the agents are in agreement), while believing
that the scout is executing \texttt{W} results in a less coherent hypothesis.
Thus A1 selects a wrong hypothesis, which in this case fails to detect the teamwork
failure.

The maximal team-coherence heuristic can detect failures despite using incorrect
hypotheses. Unfortunately, such hypotheses can also lead to false-negatives
as we have seen in Table \ref{table:example1attacker}. However, none of our
experiments resulted in a false-positive result, i.e., a result in which the
system detected a failure but in reality none had occurred. Thus the heuristic
provided sound results in these cases. We are able to formally prove this property
holds in general when the maximal team-coherence heuristic is used.

First, we address a matter of notation. Let an agent $A$ monitor an agent $B$,
which is executing some plan $P$. We denote by $M(A,B/P)$ the set of agent-modeling
hypotheses that $A$'s agent-modeling component constructs based on $B$'s observable
behavior during the execution of $P$. In other words, $M(A,B/P)$ is $A$'s set
of all plans that match $B$'s observable behavior. Note that when $A$ monitors
itself, it has direct access to its own state and so $M(A,A/P)=$\( \{P\} \).
Using the modeling notation, we make the following definitions which ground
our assumptions about the underlying knowledge used in monitoring:

\begin{defn}
\label{def:complete agent modeling}Given a monitoring agent $A$, and a monitored
agent $B$, we say that $A$'s \emph{agent-modeling} of agent $B$ is \emph{complete}
if for any plan $P$ that may be executed by B, \( P\in M(A,B/P) \).
\end{defn}
The set $M(A,B/P)$ will typically include other matching hypotheses besides
the correct hypothesis P, but is guaranteed to include P. Following this definition
of \emph{individual} agent-modeling completeness, we can define group-wide team-modeling
completeness:

\begin{defn}
\label{def:complete team modeling}Let $A$ be an agent monitoring a team $T$
of agents \( B_{1},\cdots ,B_{n} \). We say that $A$'s \emph{team-modeling}
of the team $T$ is \emph{complete} if $A$'s agent-modeling of each of \( B_{1},\cdots ,B_{n} \)
is complete.
\end{defn}
Definition \ref{def:complete team modeling} is critical to guarantee the capabilities
we will explore analytically in this section and the next. It generally holds
in our use of RESL in the ModSAF and RoboCup domains, and we make it explicit
here in service of applications of the techniques in other domains.

Armed with these definitions, we now formalize the failure detection capabilities
suggested by the empirical evidence in Theorem \ref{thm:team-coherence leads to soundness}. 

\begin{thm}
\label{thm:team-coherence leads to soundness}Let a monitoring agent $A$ monitor
a simple team $T$. If $A$'s team-modeling of $T$ is complete, and $A$ uses a
maximally team-coherent hypothesis for detection, then the teamwork failure
detection results are sound.
\end{thm}
\begin{proof}
We will show that if no failure has occurred, none will be detected, and thus
that any failure that is detected is in fact a failure. Let $a_1,\hdots,a_n$
be the agent members of $T$. Each agent $a_i$ is executing some plan $P_i$ \( (1\leq i\leq n) \).
Thus collectively, the group is executing $(P_1,\hdots,P_n)$. If no failure
has occurred, then all the agents are executing the same plan $P_0$, i.e., \( \forall i,P_{i}=P_{0} \).
Since $A$'s team-modeling is complete, the correct hypothesis \( (P_{0},\ldots ,P_{0}) \)
is going to be in the set of team-modeling hypotheses $H$. Since it is a maximally
team-coherent hypothesis, either it will be selected, or that a different hypothesis
\emph{of the same coherence level} will be selected. Any hypothesis with the
same coherence level as the correct one implies no failure is detected. Thus
the detection procedure is sound.
\end{proof}
Despite uncertainty in the knowledge used, sound failure-detection can be guaranteed
using the maximal team-coherence heuristic. This is one answer to the monitoring
selectivity problem. However, as we have seen in Table \ref{table:example1attacker},
some failures may pass undetected using this heuristic (i.e., it may result
in false-negatives). Detection using maximal team-coherence may therefore unfortunately
be \emph{incomplete.} We may prefer our monitoring system to be \emph{complete}---guaranteed
to detect all teamwork failures. 

We therefore experimented with the maximal team-\emph{incoherence} heuristic,
the inverse of the maximal team-coherence heuristic. This heuristic prefers
hypotheses that suggest \emph{more} failures, rather than less. Table \ref{table:attacker-incoherent}
gives the monitoring attacker A1's view of the team, similar to Table \ref{table:example1attacker},
but using a maximally team-\emph{incoherent} hypothesis. It shows that indeed
using a maximally team-incoherent hypothesis will not lead to the false-negative
detections in cases 4 and 5 (in contrast to these cases in Table \ref{table:example1attacker}). 

\begin{table}[htb]
{\centering \begin{tabular}{|c|c|c|c|c|c|}
\hline 
\textbf{\noun{\tiny Case}}\textbf{\tiny }&
\multicolumn{3}{|c|}{\textbf{\noun{\tiny A1's Hypothesized Executing Plans}} \textbf{\tiny }}&
\textbf{\noun{\tiny Relationship Failure}}\textbf{\tiny }&
\textbf{\noun{\tiny Detection}}\textbf{\tiny }\\
\cline{2-4} 
\textbf{\tiny \#}\textbf{\noun{\tiny }}&
\textbf{\noun{\tiny Attacker A1}}&
\textbf{\noun{\tiny Attacker A2}}&
\textbf{\noun{\tiny Scout A3}}&
\textbf{\noun{\tiny Detected?}}\textbf{\tiny }&
\textbf{\noun{\tiny Class}}\\
\hline 
{\tiny 1}&
\textbf{\tiny W}{\tiny }&
\textbf{\tiny H}{\tiny }&
\textbf{\tiny F}{\tiny }&
\textbf{\tiny +}{\tiny }&
\textbf{\tiny False Positive}{\tiny }\\
\hline 
{\tiny 2}&
{\tiny F}&
{\tiny H}&
{\tiny W}&
{\tiny +}&
{\tiny True Positive}\\
\hline 
{\tiny 3}&
{\tiny W}&
{\tiny F}&
{\tiny F}&
{\tiny +}&
{\tiny True Positive}\\
\hline 
\textbf{\tiny 4}&
\textcolor{black}{\tiny F}\textbf{\tiny }&
\textcolor{black}{\tiny F}\textbf{\tiny }&
\textcolor{black}{\tiny W}\textbf{\tiny }&
\textcolor{black}{\tiny +}\textbf{\tiny }&
\textcolor{black}{\tiny True Positive}\textbf{\tiny }\\
\hline 
\textbf{\tiny 5}&
\textcolor{black}{\tiny W}\textbf{\tiny }&
\textcolor{black}{\tiny H}\textbf{\tiny }&
\textcolor{black}{\tiny F}\textbf{\tiny }&
\textcolor{black}{\tiny +}\textbf{\tiny }&
\textcolor{black}{\tiny True Positive}{\tiny }\\
\hline 
{\tiny 6}&
{\tiny F}&
{\tiny H}&
{\tiny W}&
{\tiny +}&
{\tiny True Positive}\\
\hline 
{\tiny 7}&
{\tiny W}&
{\tiny F}&
{\tiny F}&
{\tiny +}&
{\tiny True Positive}\\
\hline 
{\tiny 8}&
\textbf{\tiny F}{\tiny }&
\textbf{\tiny F}{\tiny }&
\textbf{\tiny W}{\tiny }&
\textbf{\tiny +}{\tiny }&
\textbf{\tiny False Positive}\\
\hline 
\end{tabular}\tiny \par}

\caption{\label{table:attacker-incoherent}Attacker's (A1) monitoring results in all
permutations of Example 1, using team-\emph{incoherence}.}
\end{table}


Guided by these results, we formally show that the team-incoherence heuristic
leads to a detection procedure that is \emph{complete.}

\begin{thm}
\label{thm:team-incoherence leads to completeness}Let a monitoring agent $A$ monitor
a simple team $T$. If the $A$'s team-modeling of $T$ is complete, and $A$ uses
a maximally team-\emph{in}coherent hypothesis for detection, then the teamwork
failure detection results are complete.
\end{thm}
\begin{proof}
Analogous to that of Theorem \ref{thm:team-coherence leads to soundness}, the
proof is provided in appendix A.
\end{proof}
However, these successes are offset by false positive outcomes in cases 1 and
8 of Table \ref{table:attacker-incoherent}. In these cases, no failures have
occurred, but the monitoring system falsely reported detected failures. In practice,
this may lead to costly processing of many false alarms. 

Ideally, the detection capabilities should be sound \emph{and} complete. Unfortunately,
we can show that no coherence-based disambiguation scheme exists that results
in both sound and complete detection. We show in Theorem \ref{thm:trade completeness for soundess}
that to provide sound and complete detection, a disambiguation method will have
to be inconsistent: Given the same set of possible matching hypotheses, it will
have to sometimes rank one hypothesis on top, and sometimes another.

\begin{thm}
\label{thm:trade completeness for soundess}Let $H$ be a complete team-modeling
hypotheses set, modeling a simple team. There does not exists a disambiguation
scheme $S$ that (1) uses coherence alone as the basis for disambiguation of
$H$, and (2) is deterministic in its selection, and (3) results in sound and
complete failure detection.
\end{thm}
\begin{proof}
Let $S$ be a disambiguation scheme that leads to complete and sound detection
and uses only knowledge of the coherence of the hypotheses in selecting a disambiguated
hypothesis. Suppose for contradiction that it is deterministic, and thus consistent,
in its selection of an hypothesis out of $H$, i.e., given $H$, a set of candidate
hypotheses, it applies some deterministic procedure to choose one hypothesis
based on its coherence. Since it does not use any other knowledge outside of
the coherence of the candidate hypotheses, given the same set of candidates,
it will always choose the same hypothesis. Let $A_m$ be the monitoring agent
using $S$. Let $B$ be a monitored agent, whose actions are identical when executing
team plans $P_1, P_2$. Thus, $A_m$ cannot determine whether $B$ is executing
$P_1$ or $P_2$, \( M(A_{m},B/P_{1})=M(A_{m},B/P_{2})=\{P_{1},P_{2}\} \). If
$A_m$ and $B$ are both executing $P_1$, $A_m$'s hypotheses set is 
\[
H=\{(P_{1},P_{1}),(P_{1},P_{2})\}\]
 Since $S$ leads to complete and sound detection, it will choose $(P_1,P_1)$.
Now, when $A_m$ and $B$ are executing $P_1$ and $P_2$, respectively, the matching
hypothesis set is again $H$ as defined above. But now $S$ must select $(P_1,P_2)$.
Since the same set of candidate hypothesis $H$ was used in each case, and no
other information was supplied, $S$ must be non-deterministic in its selection
of a disambiguated hypothesis, contradicting the assumption.
\end{proof}
The empirical and analytical results show that our use of a single disambiguated
hypothesis leads to improved, but imperfect, failure-detection results, compared
to the monitoring conditions and communications previously used. The empirical
results in Tables \ref{table:example2scout}, \ref{table:example1attacker},
and \ref{table:attacker-incoherent} establish the benefits of the teamwork
monitoring technique: Most physical failures were detected. However, the analytical
results (Theorems \ref{thm:team-coherence leads to soundness}, \ref{thm:team-incoherence leads to completeness},
\ref{thm:trade completeness for soundess}) show that the results are less than
perfect. The algorithms are either sound or complete, but not both. For complete
monitoring, we would require additional procedures that can differentiate the
true positives from the false ones, e.g., by focused communication. These procedures
are often very expensive. 

We can reduce the need for costly verification by letting go of our insistence
on a single hypothesis, focusing instead of maintaining two hypotheses: a maximally-coherent
hypothesis and a maximally-incoherent hypothesis. Table \ref{tab:example1exponential}
shows a portion of the full set of team-hypotheses available when the attacker
A1 is monitoring the team. The total number of hypotheses presented in the table
is 24, with as many as 4 co-existing in a single case, and thus maintaining
a full set of hypotheses would be expensive. However, the two inverse heuristics---team-coherence
and incoherence---represent two extremes of the space of these hypotheses. If
they agree that a failure exists, then a failure actually occurred, since the
team-coherent hypothesis guarantees soundness (Theorem \ref{thm:team-coherence leads to soundness}).
If they agree that no failure exists, then no failure took place, since the
team-incoherent hypothesis guarantees completeness (Theorem \ref{thm:team-incoherence leads to completeness}).
If they disagree (i.e., the team-coherent hypothesis does not imply a failure,
but the team-incoherent hypothesis does), the monitoring system cannot be sure
either way, and must revert back to verification. 

\begin{table}[htb]
{\centering \begin{tabular}{|c|c|c|c|c|c|}
\hline 
\textbf{\noun{\tiny Case}}\textbf{\tiny }&
\multicolumn{3}{|c|}{\textbf{\noun{\tiny A1's Hypothesized Executing Plans}} \textbf{\tiny }}&
\textbf{\noun{\tiny Relationship Failure}}\textbf{\tiny }&
\textbf{\noun{\tiny Detection}}\textbf{\tiny }\\
\cline{2-4} 
\textbf{\tiny \#}\textbf{\noun{\tiny }}&
\textbf{\noun{\tiny Attacker A1}}&
\textbf{\noun{\tiny Attacker A2}}&
\textbf{\noun{\tiny Scout A3}}&
\textbf{\noun{\tiny Detected?}}\textbf{\tiny }&
\textbf{\noun{\tiny Class}}\\
\hline 
{\tiny 1}&
{\tiny W}&
{\tiny H}&
{\tiny F}&
{\tiny +}&
{\tiny False Positive}\\
{\tiny }&
{\tiny W}&
{\tiny H}&
{\tiny W}&
{\tiny +}&
{\tiny False Positive}\\
{\tiny }&
{\tiny W}&
{\tiny W}&
{\tiny F}&
{\tiny +}&
{\tiny False Positive}\\
{\tiny }&
{\tiny W}&
{\tiny W}&
{\tiny W}&
{\tiny -}&
{\tiny True Negative}\\
\hline 
{\tiny 2}&
{\tiny F}&
{\tiny H}&
{\tiny F}&
{\tiny +}&
{\tiny True Positive}\\
{\tiny }&
{\tiny F}&
{\tiny H}&
{\tiny W}&
{\tiny +}&
{\tiny True Positive}\\
{\tiny }&
{\tiny F}&
{\tiny W}&
{\tiny F}&
{\tiny +}&
{\tiny True Positive}\\
{\tiny }&
{\tiny F}&
{\tiny W}&
{\tiny W}&
{\tiny +}&
{\tiny True Positive}\\
\hline 
{\tiny 3}&
{\tiny W}&
{\tiny F}&
{\tiny F}&
{\tiny +}&
{\tiny True Positive}\\
{\tiny }&
{\tiny W}&
{\tiny F}&
{\tiny W}&
{\tiny +}&
{\tiny True Positive}\\
\hline 
{\tiny 4}&
\textcolor{black}{\tiny F}{\tiny }&
\textcolor{black}{\tiny F}{\tiny }&
\textcolor{black}{\tiny W}{\tiny }&
\textcolor{black}{\tiny +}{\tiny }&
\textcolor{black}{\tiny True Positive}{\tiny }\\
{\tiny }&
{\tiny F}&
{\tiny F}&
{\tiny F}&
{\tiny -}&
{\tiny False Negative}\\
\hline 
{\tiny 5}&
\textcolor{black}{\tiny W}{\tiny }&
\textcolor{black}{\tiny H}{\tiny }&
\textcolor{black}{\tiny F}{\tiny }&
\textcolor{black}{\tiny +}{\tiny }&
\textcolor{black}{\tiny True Positive}{\tiny }\\
{\tiny }&
{\tiny W}&
{\tiny H}&
{\tiny W}&
{\tiny +}&
\textcolor{black}{\tiny True Positive}{\tiny }\\
{\tiny }&
\textcolor{black}{\tiny W}{\tiny }&
{\tiny W}&
\textcolor{black}{\tiny F}{\tiny }&
\textcolor{black}{\tiny +}{\tiny }&
\textcolor{black}{\tiny True Positive}{\tiny }\\
{\tiny }&
{\tiny W}&
{\tiny W}&
{\tiny W}&
{\tiny -}&
{\tiny False Negative}\\
\hline 
{\tiny 6}&
{\tiny F}&
{\tiny H}&
{\tiny W}&
{\tiny +}&
\textcolor{black}{\tiny True Positive}{\tiny }\\
{\tiny }&
{\tiny F}&
{\tiny H}&
{\tiny F}&
{\tiny +}&
\textcolor{black}{\tiny True Positive}{\tiny }\\
{\tiny }&
{\tiny F}&
{\tiny W}&
{\tiny W}&
{\tiny +}&
\textcolor{black}{\tiny True Positive}{\tiny }\\
{\tiny }&
{\tiny F}&
{\tiny W}&
{\tiny F}&
{\tiny +}&
\textcolor{black}{\tiny True Positive}{\tiny }\\
\hline 
{\tiny 7}&
{\tiny W}&
{\tiny F}&
{\tiny F}&
{\tiny +}&
\textcolor{black}{\tiny True Positive}{\tiny }\\
{\tiny }&
{\tiny W}&
{\tiny F}&
{\tiny W}&
{\tiny +}&
\textcolor{black}{\tiny True Positive}{\tiny }\\
\hline 
{\tiny 8}&
{\tiny F}&
{\tiny F}&
{\tiny W}&
{\tiny +}&
{\tiny False Positive}\\
{\tiny }&
{\tiny F}&
{\tiny F}&
{\tiny F}&
{\tiny -}&
{\tiny True Negative}\\
\hline 
\end{tabular}\tiny \par}

\caption{\label{tab:example1exponential}A portion of the attacker's (A1) monitoring
hypotheses and implied results when no ranking is used to select a single hypothesis
for each case.}
\end{table}


This revised detection algorithm offers significant computational savings compared
to the single team-incoherent hypothesis approach. It is complete and unsound,
but significantly reduces the need for verification, since at least when the
team-coherent hypothesis implies failures, verification is not necessary. It
requires representing only two hypotheses, and is thus still computationally
cheaper than maintaining an exponential number of hypotheses.

For example, using a maximally team-incoherent hypothesis on permutations of
Example 1 results in a need to verify in all eight cases as we have seen (\ref{table:attacker-incoherent}).
However, when we combine such an hypothesis with a maximally team-coherent hypothesis
(e.g., as in Table \ref{table:example1attacker}), we only need to verify four
(50\% ) of the cases. In cases 2, 3, 6, 7 there is agreement between the two
hypotheses that a failure has occurred, and thus no verification is required. 

A monitoring agent can therefore address the monitoring selectivity problem
by balancing its resource usage against the guaranteed performance of the monitoring
algorithm used. Either of the simpler single-hypothesis algorithms would utilize
only one hypothesis in each case, with detection capabilities that are guaranteed
to be sound or complete, but not both. In the more complex algorithm, two hypotheses
would be reasoned about in each case, and the algorithm would be complete and
require verification in fewer cases compared to the simple-hypothesis complete
algorithm.


\section{\label{sec:distributed-sam} Monitoring Selectivity in Distributed Teamwork
Monitoring}

This section focuses on monitoring selectivity when exploiting a key opportunity
for execution monitoring in multi-agent environments---it is not only the monitored
agents that are distributed, but the monitoring agents can be distributed as
well. We begin with the simple scheme of selecting a single maximally team-coherent
hypothesis. Since centralized teamwork monitoring was successful in addressing
all permutations of Example 2, we focus here on the permutations of Example
1 (Table \ref{table:example1}), in which centralized teamwork monitoring by
the attacker resulted in false-negative detections (cases 4-5 in Table \ref{table:example1attacker}).

In a distributed teamwork monitoring scheme, not only will a single attacker
monitor its teammates, but the scout (and the other attacker) will also engage
in monitoring. Table \ref{table:scout-coherent} presents the monitoring results
of the same failure permutations, with the scout as the monitoring agent. We
find that the scout successfully detects the two failure cases that the attacker
failed to detect, compensating for the attackers' monitoring mistakes. Furthermore,
since the scout used the the maximal-coherence heuristic, detection is sound
and no verification is required. The reason for the scout's success is that
the attackers' actions in this case, although ambiguous, do not support any
hypothesis that can be matched to the scout's plan. In other words, regardless
of what plan the attackers are executing in these two cases, it is different
that the plan executed by the scout. 

\begin{table}[htb]
{\centering \begin{tabular}{|c|c|c|c|c|c|}
\hline 
\textbf{\noun{\tiny Case}}\textbf{\tiny }&
\multicolumn{3}{|c|}{\textbf{\noun{\tiny A3's Hypothesized Executing Plans}} \textbf{\tiny }}&
\textbf{\noun{\tiny Relationship Failure}}\textbf{\tiny }&
\textbf{\noun{\tiny Detection}}\textbf{\tiny }\\
\cline{2-4} 
\textbf{\tiny \#}\textbf{\noun{\tiny }}&
\textbf{\noun{\tiny Attacker A1}}&
\textbf{\noun{\tiny Attacker A2}}&
\textbf{\noun{\tiny Scout A3}}&
\textbf{\noun{\tiny Detected?}}\textbf{\tiny }&
\textbf{\noun{\tiny Class}}\\
\hline 
{\tiny 1}&
{\tiny W}&
{\tiny W}&
{\tiny W}&
{\tiny -}&
{\tiny True Negative}\\
\hline 
{\tiny 2}&
{\tiny F}&
{\tiny W}&
{\tiny F}&
{\tiny +}&
{\tiny True Positive}\\
\hline 
{\tiny 3}&
{\tiny W}&
{\tiny F}&
{\tiny W}&
{\tiny +}&
{\tiny True Positive}\\
\hline 
{\tiny 4}&
{\tiny F}&
{\tiny F}&
{\tiny W}&
{\tiny +}&
{\tiny True Positive}\\
\hline 
{\tiny 5}&
{\tiny H}&
{\tiny H}&
{\tiny F}&
{\tiny +}&
{\tiny True Positive}\\
\hline 
{\tiny 6}&
{\tiny F}&
{\tiny H}&
{\tiny F}&
{\tiny +}&
{\tiny True Positive}\\
\hline 
{\tiny 7}&
{\tiny H}&
{\tiny F}&
{\tiny F}&
{\tiny +}&
{\tiny True Positive}\\
\hline 
{\tiny 8}&
{\tiny F}&
{\tiny F}&
{\tiny F}&
{\tiny -}&
{\tiny True Negative}\\
\hline 
\end{tabular}\tiny \par}

\caption{\label{table:scout-coherent}Scout's (A3) monitoring results in all permutations
of Example 1, using team-coherence.}
\end{table}


Thus if all agents engaged in monitoring in permutations of Example 1, detection
would be sound and complete. In all actual failure cases (and only in those)
there would at least one team-member who detects the failure. We attempt to
formally define the general conditions under which this phenomenon holds. 

\begin{defn}
\label{def:observably-different plans}We say that two team-plans $P_1,P_2$,
have \emph{observably-different roles} $R_1, R_2$ if given an agent $B$ who
fulfills the roles $R_1, R_2$ in the two plans, resp., any monitoring agent
$A$ (different than $B$) will have \( M(A,B/P_{1})\cap M(A,B/P_{2})=\emptyset  \).
We then say that $B$ has observably-different roles in $P_1$ and $P_2$, and
call $B$ a \emph{key agent}.
\end{defn}
Intuitively, $B$ is a key agent that has observably different roles in the two
plans if a monitoring agent can differentiate between $B$'s behavior in executing
$P_1$ and in executing $P_2$. For instance, both attackers have observably different
roles in \texttt{F} (in which they fly) and \texttt{W} (in which they land).
However, they do not have observably different roles in \texttt{W} and \texttt{H},
both of which require them to land. The scout has observably different roles
in \texttt{W} (flying) and \texttt{H} (landing).

The key-agent is the basis for the conditions under which a self-monitoring
team will detect a failure with each agent using only team-coherence. We first
prove a lemma on the conditions in which a single given agent will detect a
failure. We then use this lemma to prove the conditions under which at least
one agent in a given team will detect a failure.

\begin{lem}
\label{lemma:detection in observably different plans}Suppose a simple team
$T$ is self-monitoring (all members of the team monitor each other) using the
maximally team-coherent heuristic (and under the assumption that for each agent,
team-modeling is complete). Let $A_1, A_2$ be monitoring agents who are members
of $T$ and are executing $P_1, P_2$, respectively. $A_1$ would detect a failure
in maintaining teamwork relationships with an agent $A_2$, if $A_2$ is a key-agent
in $P_1, P_2$.
\end{lem}
\begin{proof}
See appendix A.
\end{proof}
$A_1$ knows that it is executing $P_1$. If $A_2$ is executing $P_2$, and is
a key-agent in $P_1$ and $P_2$, then $A_1$ is guaranteed to notice that a difference
exists between itself and $A_2$, since $A_2$ is acting observably different
than it would if it had been executing $P_1$. Note, however, that $A_2$ may
or may not detect this difference, since from $A_2$'s perspective, $A_1$'s behavior
may or may not be explained by $P_2$. $A_2$ will detect a difference only if
$A_1$'s roles in $P_1$ and $P_2$ are also observably-different. However, since
$A_1$ has detected the failure, it can now alert its teammates, diagnose the
failure, or choose corrective action. 

If we want to guarantee that a teamwork failure will always be detected by at
least one agent, we must make sure that in each possible combination of plans,
there has to be at least one key-agent whose roles are observably different.
The lemma shows that other agents monitoring this agent will notice a failure
if one occurs. To this aim, we define an observably-partitioned set of plans
employed by a team.

\begin{defn}
\label{def:observably-partitioned}A set $P$ of team-plans is said to be \emph{observably-partitioned}
if for any two plans \( P_{i},P_{j}\in P \) there exists a key-agent $A_{ij}$.
The set of these $A_{ij}$ agents is called the \emph{key agents set of $P$}.
\end{defn}
For instance, the set of team-plans our helicopter pilots team has been using
in the examples (\texttt{Fly-Flight-Plan} (\texttt{F}), \texttt{Wait-at-Point}
(\texttt{W}), \texttt{Ordered-Halt} (\texttt{H}), and \texttt{Join-Scout} (\texttt{J}))
is observably-partitioned. The attackers land in \texttt{W} and \texttt{H},
but fly in \texttt{F} and \texttt{J}. The scout lands in \texttt{J} and \texttt{H},
but flies in \texttt{W} and \texttt{F}. Table \ref{table:observably-partitioned}
shows which agents have observably different roles in any two plans in the set.
For instance, by finding the cell at the intersection of the \texttt{H} row
and the \texttt{W} column, we find that the scout has observably different roles
in these two plans. Indeed, the scout lands when a command is received to halt
execution (\texttt{H}), but flies out to scout the enemy's position when executing
\texttt{W}. Here, since all agents have observably-different roles in at least
two plans, the key agents set of \{ \texttt{W}, \texttt{F}, \texttt{H}, \texttt{J}
\} includes all members of the team---attackers and scout.

\begin{table}[htb]
{\centering \begin{tabular}{|c|c|c|c|c|}
\hline 
{\footnotesize }&
\texttt{\footnotesize Fly-Flight-Plan~(F)}&
\texttt{\footnotesize Wait-at-Point~(W)}&
\texttt{\footnotesize Ordered-Halt~(H)}&
\texttt{\footnotesize Join-Scout~(J)}{\footnotesize }\\
\hline 
\hline 
\texttt{\footnotesize F}{\footnotesize }&
{\footnotesize -}&
{\footnotesize Attackers}&
{\footnotesize Attackers}&
{\footnotesize Scout}\\
\hline 
\texttt{\footnotesize W}{\footnotesize }&
{\footnotesize Attackers}&
{\footnotesize -}&
{\footnotesize Scout}&
{\footnotesize Scout and Attackers}\\
\hline 
\texttt{\footnotesize H}{\footnotesize }&
{\footnotesize Attackers}&
{\footnotesize Scout}&
{\footnotesize -}&
{\footnotesize Attackers}\\
\hline 
\texttt{\footnotesize J}{\footnotesize }&
{\footnotesize Scout}&
{\footnotesize Scout and Attackers}&
{\footnotesize Attackers}&
{\footnotesize -}\\
\hline 
\end{tabular}\footnotesize \par}

\caption{\label{table:observably-partitioned}Observable partitioning of the helicopter
pilot team in ModSAF.}
\end{table}


\begin{thm}
\label{thm:distributed monitoring}If a simple team (1) employs an observably-partitioned
set of team-plans $O$, and all team-members monitor \emph{members of the key
agents set of} $O$, (2) using complete team-modeling and (3) maximally team-coherent
hypotheses, then the teamwork failure detection results are sound and complete.
\end{thm}
\begin{proof}
From theorem \ref{thm:team-coherence leads to soundness} we know that detection
would be sound. To show that it is complete, we will prove at least one agent
will detect a difference between itself and others whenever team-members are
not all executing the same plan (i.e., a failure is occurring). Suppose the
team is currently divided on the team-plans that must be executed, i.e., there
are agents $a_i, a_j$ in the team that are executing team plans $P_i, P_j$,
respectively, such that \( P_{i}\neq P_{j} \). Thus a failure has occurred.
Let $K$ be the key agents set of $O$. Since the team is observably-partitioned,
for $P_i, P_j$ there exists at least one key agent \( a_{1}\in K \). There
are three cases: \\
\textbf{case (i).} $a_1$ is executing $P_i$. In this case any agent executing
$P_j$ would detect a difference with $a_1$ and would therefore detect the failure
(lemma \ref{lemma:detection in observably different plans}).\\
\textbf{case (ii).} $a_1$ is executing $P_j$. In this case any agent executing
$P_i$ would detect a difference with $a_1$ and would therefore detect the failure
(lemma \ref{lemma:detection in observably different plans}).\\
\textbf{case (iii).} $a_1$ is executing some other plan $Q$. Its roles must
be observably different in $Q$ and $P_i$, or in $Q$ and $P_j$ (or in both),
and thus any agent executing $P_j$ and/or $P_i$ would detect the failure. The
case that $a_1$'s roles are not observably different in $Q$ and $P_i$ \emph{and}
in $Q$ and $P_j$ is impossible, since then for a monitoring agent $A_m$ 
\[
M(A_{m},a_{1}/P_{i})\cap M(A_{m},a_{1}/Pj)\supseteq \{Q\}\neq \emptyset \]
 Contradicting $a_1$ being a key agent for $P_i, P_j$. 

Since in all three cases, at least one agent would detect a failure where one
occurred. Therefore, failure detection is complete. Since it is also sound as
we have seen, detection is sound and complete.
\end{proof}
The theorem shows that distributed teamwork monitoring can result in \emph{sound
and complete} failure-detection, while using a simple algorithm. Each team-member
monitors \emph{only} \emph{the key agents}\footnote{%
If the monitoring team-member does not know who the key agents are, but knows
they exist, it can monitor all other team-members. This increases monitoring,
but sound and complete failure detection is still guaranteed.
}, using a maximally team-coherent hypothesis. If it detects a failure, then
certainly one has occurred. If no agent detects a failure, then indeed no failure
has occurred. 

This simple distributed algorithm, with its attention-focusing features and
guaranteed soundness and completeness contrasts with the more complex centralized
algorithm which we discussed in the previous section (Section \ref{sec:centralized-eval}).
The algorithm's effectiveness relies on the condition of an observably-partitioned
set of plans, and on the distribution of the monitoring. A corollary of Theorems
\ref{thm:trade completeness for soundess} and \ref{thm:distributed monitoring}
is that if key agents are not available in the distributed case, failure detection
is either sound or complete, but not both. And even when key agents are available,
centralized teamwork monitoring is still not complete and sound. 

Fortunately, observable-partitioning is not a difficult property to design:
Teams are very often composed such that not all agents have the same role in
the same plan, and in general, roles do have observable differences between
them. For instance, our helicopter pilot team in the ModSAF domain typically
executes a set of plans with this property, as Table \ref{table:observably-partitioned}
demonstrates. 

If the team, however, is not observably-partitioned, there may be a case where
two agents are each executing a different plan, but no agent will be able to
detect it using the team-coherence heuristic. The minimal case where this occurs
is when two agents, $A_1$ and $A_2$ are executing plans $P_1$ and $P_2$, respectively,
and $P_1$ and $P_2$ are not observably different, such that 
\[
M(A_{2},A_{1}/P_{1})\cap M(A_{1},A_{2}/P2)=\{P_{1},P_{2}\}\]
 This will result in $A_1$ and $A_2$ each believing that the other is in agreement
with them. A check for such a situation can be made a part of the plan design
process, marking \emph{risky points} in the execution in which detection is
either sound or complete (Theorem \ref{thm:trade completeness for soundess}),
and verification (e.g., by communications) can be prescribed pro-actively. Or,
the check could be inserted into the protocol for run-time analysis---the agent
would simulate the other's hypotheses matching their own actions, and detect
risky points dynamically.


\section{\label{sec:offline}Using Socially-Attentive Monitoring in an Off-Line Configuration}

To further demonstrate the generality of our socially-attentive monitoring framework,
this section examines re-use of teamwork monitoring in domains in which diagnosis
and recovery from every failure are infeasible during execution. Examples of
such domains include team sports, military human team training \cite{volpe96},
and other multi-agent domains. The dynamic nature of the domain, hard real-time
deadlines, and complexity of the agents involved (e.g., human team members)
make diagnosis and recovery difficult. Even if a failure can be diagnosed, it
is often too late for effective recovery. In such environments, the monitoring
agent is often concerned with trends of performance. This information is important
for long-term design evaluation and analysis, and need not necessarily be calculated
on-line. The results of the analysis are meant as feedback to the agents' designer
(coach or supervisor, for humans). 

To this end, we are developing an off-line socially-attentive monitoring system
called {\sc Teamore} (TEAmwork MOnitoring REview). {\sc Teamore} currently uses execution
traces of the monitored agents to perform the monitoring, rather than using
plan recognition. Thus it does not need to worry about the uncertainty in plan-recognition,
nor about real-time performance. Instead, it knows with certainty each agent's
plans during execution. {\sc Teamore} accumulates several quantitative measures related
to teamwork, including the Average-Time-to-Agreement measure (ATA, for short),
and a measure of the level of agreement in a team. These build on the failure
detection algorithm, but aggregate failures in quantitatively. We focus here
on the ATA measure. 

{\sc Teamore} defines a \emph{switch} as the time interval beginning at the point
where any team-member (at least one) selects a new team plan for execution by
the team, and ending at the point where the team is again in agreement on the
team-plan being executed. In perfect teamwork, all team-members select a new
team-plan jointly, and so always remain in agreement. In more realistic scenario,
some agents will take longer to switch, and so initially a teamwork failure
will occur. The first team-member to select a new plan will be in disagreement
with some of its teammates, until either it rejoins them in executing the original
plan, or they join it in selecting the new plan. Such a switch begins with a
detected failure and ends when no more failures are detected. 

Figure \ref{fig:switch} shows an illustration of a switch. The three agents
begin in an initial state of agreement on joint execution of Plan 1 (filled
line). Agent 1 is the first agent to switch to Plan 2 (dotted line), and is
followed by Agent 3, and finally Agent 2. The switch is the interval which begins
at the instance Agents 1 selected Plan 2, to the time all three agents regained
their agreement (but this time on Plan 2).

\begin{figure}[htb]
{\par\centering \resizebox*{0.7\columnwidth}{!}{\includegraphics{switch.eps}} \par}


\caption{\label{fig:switch}An illustration of a switch. The three agents switch from
plan 1 to plan 2.}
\end{figure}


{\sc Teamore} keeps track of the lengths of time in which failures are detected until
they are resolved. The ATA measure is the average switch length (in time ``ticks'')
per a complete team run (e.g., a mission in ModSAF, a game in RoboCup). A perfect
team would have all switches of length zero, and therefore an ATA of 0. The
worst team would be one that from the very beginning of their task execution
to the very end of it, would not agree on the team plan being executed. For
instance, each RoboCup game lasts for 6000 ``ticks''. The worst possible team
would have only one switch during the game, of length 6000. Thus the ATA scale
in RoboCup goes from 0 (perfect) to 6000 (worst).

We used the ATA measure to analyze a series of games of our two RoboCup simulation-league
teams, ISIS'97 and ISIS'98 \cite{isis-agents99} against a fixed opponent, Andhill'97
\cite{andhill97}. In these games, we varied the use of communications by our
teams to evaluate design decisions on the use of communications. In approximately
half of the games, players were allowed to use communications in service of
teamwork. In the other half, all communications between agents were disabled.
ISIS'97 played approximately 15 games in each settings, and ISIS'98 played 30
games in each communication settings. 

Table \ref{tab:isis97-98 teamore (low)} shows the mean ATA values over these
games, for two sub-teams (each having three members) of ISIS'97 and ISIS'98
(ATA values are calculated separately for each sub-team). The first column shows
which sub-team the results refer to in each row. The second columns shows the
mean ATA for each sub-team, when no communications were used. The third column
shows the mean ATA when communications were used. The next column shows the
size of the ATA reduction---the drop in the mean ATA values when communications
are introduced. The last column shows the probability of the null hypothesis
in a two-tailed t-test of the difference in the ATA means. This is the probability
that the difference is due to chance, thus smaller numbers indicate greater
significance.

\begin{table}[htb]
{\centering \begin{tabular}{|l|c|c|c||c|}
\hline 
ISIS &
Mean ATA &
Mean ATA &
ATA &
t-test prob.\\
sub-team&
No comm.&
Comm.&
Reduction&
null-hypothesis\\
\hline 
\hline 
'97 Goalies&
32.80&
5.79&
27.01&
7.13e-13\\
\hline 
'97 Defenders&
57.5&
6.81&
50.69&
.45e-10\\
\hline 
'98 Goalies&
13.28&
3.65&
9.63&
9.26e-16\\
\hline 
'98 Defenders&
12.99&
3.98&
9.01&
7.13e-5\\
\hline 
\end{tabular}\par}

\caption{\label{tab:isis97-98 teamore (low)}Average-Time-to-Agreement (ATA) for games
against Andhill'97.}
\end{table}


\begin{sloppypar}Clearly, a very significant difference emerges between the communicating and
non-communicating versions of each sub-team. The ATA values indicate that sharing
information by way of communications significantly decreases the time it takes
team-members to come to agreement on a selected plan. This result agrees with
our intuitions about the role of communications, and in that sense, may not
be surprising.\end{sloppypar}

However, the ATA reduction magnitudes indicate that ISIS'98 may be much less
sensitive to loss of communications than ISIS'97. The differences in ATA values
for ISIS'97 are approximately triple, nearly four times, as great as for ISIS'98.
Our explanation for this phenomenon is that ISIS'98 is composed of players with
improved capabilities for monitoring the environment (such that they have better
knowledge of the environment). ISIS'98 is therefore not as dependent on communications
as are teams, such as ISIS'97, composed of players with lesser environment monitoring
capabilities. ISIS'98 players are better able to select the correct plan without
relying on their teammates. Thus, they would be able to maintain the same level
of performance when communications are not used. In contrast, ISIS'97 players
rely on passing information to and from each other (monitoring each other) through
communications, and so took much longer to establish agreement when communications
were not available. 

We can validate the hypothesis suggested by ATA measurements by looking at the
overall team-performance in the games, measured by the score difference at the
end of the game. Table \ref{tab:isis97-98 against andhill and cmu} shows the
mean score difference from the same series of games against Andhill'97. The
first column lists the communications settings (with or without). The second
and third columns show the \emph{mean} score-difference in the games for ISIS'97
and ISIS'98. The bottom row summarizes the results of t-tests run on each set
of games, to determine the significance level of the difference between the
mean score-differences. The score-difference results corroborate the ATA results.
While the difference in mean score-difference is indeed statistically significant
in ISIS'97 games, it is not significant in ISIS'98 games. This supports our
explanation that the more situationally aware ISIS'98 is indeed better able
to handle loss of communications than ISIS'97. 

\begin{table}[htb]
{\centering \begin{tabular}{|c|c|c|}
\hline 
&
ISIS'97&
ISIS'98\\
\hline 
\hline 
Communication Used&
-3.38&
-1.53\\
\hline 
Communication Not Used&
-4.36&
-2.13\\
\hline 
\hline 
t-test p/null hypothesis&
p=0.032&
p=0.13\\
\hline 
\end{tabular}\par}

\caption{\label{tab:isis97-98 against andhill and cmu}ISIS'97 and ISIS'98 mean score
difference against Andhill'97, with changing communications settings}
\end{table}


The general lesson emerging from these experiments is that a trade-off exists
in addressing the monitoring selectivity problem. The knowledge that is maintained
about teammates (here, via communications) can be traded, to an extent, with
knowledge maintained about the environment. A designer therefore has a range
of alternative capabilities that it can choose for its agents. Different domains
may better facilitate implicit coordination by monitoring the environment, while
others require agents to rely on communications or explicit knowledge of team-members
to handle the coordination.

The ATA results support additional conclusions, especially when combined with
a general performance measure such as the score-difference. To illustrate, consider
the plots of the actual data from these games. Figure \ref{fig:ata values plot}
plots all the ATA values for all four variants, for the Goalies sub-team. The
graph plots approximately 60 data-points. We see in Figure \ref{fig:ata values plot}
that when communications are used, ISIS'97's ATA values are still generally
better than ISIS'98's ATA without communications. Thus, despite its importance,
individual situational awareness is not able to fully compensate for lack of
communications. 

\begin{figure}[htb]
{\par\centering \subfigure[ATA Values for Goalies subteam]{\resizebox*{0.7\textwidth}{!}{\rotatebox{-90}{\includegraphics{ATA-compare-goalies.ps}}}}  \par}


\caption{\label{fig:ata values plot}ATA values for the Goalies sub-teams in games against
Andhill'97.}
\end{figure}


{\sc Teamore} demonstrates the reuse of the teamwork monitoring techniques developed
in earlier sections in an off-line configuration. The designer of ISIS'97 should
set its agents to use communications, since those will have significant improvement
on the score-difference. In contrast, with or without communications, ISIS'98
players are able to maintain their collaboration. Thus if communications takes
precious resources, it can be relatively safely eliminated from the ISIS'98
agents' design, and the development efforts can be directed at some other components
of the agents.


\section{\label{sec:discussion}Beyond Teamwork}

We have presented a general socially-attentive monitoring framework to detect
failures in maintaining agreement on joint team plans. However, effective operation
in teams often relies on additional relationships, which we briefly address
in this section. 


\subsection{\label{sec:dissimilarity}A Richer Agreement Model: Agreeing to Disagree}

The teamwork model requires joint execution of team plans. In service of such
agreed-upon joint plans, agents may sometimes agree to execute different sub-plans
individually, or split into sub-teams to execute different sub-team plans. Two
examples may serve to illustrate. 

\begin{example}
\label{ex:modsaf-dissimilarity}In the ModSAF domain, helicopters engage the
enemy by repeatedly following the following three steps: hiding behind a hill
or trees (\emph{masking}), then popping up (\emph{unmasking}), then shooting
missiles at the enemy, and back to hiding. In some variations of this plan,
they are required to make sure that no two helicopters are shooting at the same
time. Of course, due to limits of communications, helicopters do fail and unmask
at the same time.
\end{example}
\begin{example}\label{ex:robocup-dissimilar}In the RoboCup domain, our 11 players
in both ISIS'97 and ISIS'98 \cite{isis-agents99} are divided into four sub-teams:
mid-fielders, attackers, defenders, and goalies (the goalie and two close defenders).
This division into sub-teams is modeled by the agents selecting one of four
team plans in service of the \texttt{play} team plan (see Figure \ref{fig:robocup-hierarchy}).
Mid-fielders must select the \texttt{midfield} plan, goalies must select the
\texttt{defend-goal} plan, etc. Again, ideally an attacker would never select
any other plan but \texttt{attack}, a defender would select no other plan but
\texttt{defend}, etc. However, due to communication failures, players may sometimes
accidently abandon their intended sub-team, and execute a team-plan of another
sub-team.

\begin{figure}[htb]
{\par\centering \resizebox*{0.5\textwidth}{!}{\includegraphics{soccer-hierarchy.ps}} \par}


\caption{\label{fig:robocup-hierarchy}A Portion of the plan-hierarchy used by ISIS
RoboCup agents.}
\end{figure}


\end{example}

In both of these examples, certain differences between agents are agreed upon
and are a sign of correct execution, not of failure. Indeed, it is the lack
of difference in selected plans that would indicate failure in these cases.
We use the term \emph{mutual-exclusion coordination} to refer to these relationships.
In Example \ref{ex:modsaf-dissimilarity}, ideally no two pilots are executing
the \texttt{shooting} plan at the same time. In Example \ref{ex:robocup-dissimilar},
no two members of different sub-teams (e.g., an attacker and a defender) are
executing the same plan in service of \texttt{play} (e.g., \texttt{defend}).
As the examples demonstrate, there is a clear need for monitoring mutual-exclusion
coordination. 

Our results of previous sections are re-used in service of socially-attentive
monitoring of mutual-exclusion relationships. They require a transformation
both in implementation and theory. The hierarchies are compared in the usual
manner, except that failures are signified by equalities, rather than differences.
For instance, if an attacker is staying in the team's own half of the field,
its teammates may come to suspect that it mistakenly ``defected'' the attackers'
sub-team and believes itself to be a defender.

The analytical results are inverted as well. The maximal team-coherence heuristic
will now lead to completeness, since it prefers hypotheses that contain equalities
among agents, which are failures in mutual-exclusion coordination. The maximal
team-incoherence heuristic will now lead to sound detection, as it prefers hypotheses
that imply no equalities have occurred. These properties can be proven formally.

\begin{thm}
\label{thm:incohrence-is-sound-in-mutual-ex}Let a monitoring agent $A$ monitor
mutual-exclusion relationships in a group of agents $G$. If $A$'s modeling of
$G$ is complete, and $A$ uses a maximally team-\emph{in}coherent hypothesis
for detection, then the failure detection results are sound.
\end{thm}
\begin{proof}
Provided in appendix A.
\end{proof}
\begin{thm}
\label{thm:cohrence-is-complete-in-mutual-ex}Let a monitoring agent $A$ monitor
mutual-exclusion relationships in a group of agents $G$. If $A$'s modeling of
$G$ is complete, and $A$ uses a maximally team-coherent hypothesis for detection,
then the failure detection results are complete.
\end{thm}
\begin{proof}
Provided in appendix A.
\end{proof}
Thus in mutual-exclusion relationships, as in teamwork relationships, guaranteed
failure-detection results may still be provided despite the use of limited,
uncertain knowledge about monitored agents. The centralized teamwork monitoring
algorithms can now be easily transformed for monitoring mutual-exclusion relationships.
Unfortunately, the results in the distributed case (Theorem \ref{thm:distributed monitoring})
cannot be so easily transformed, since they rely on the property of observable-partitioning,
which is associated with differences, not with equalities. We leave this issue
for future work.


\subsection{\label{sec:role-similarity}Monitoring Using Role-Similarity Relationships}

This section applies socially-attentive monitoring to role-similarity relationships,
for monitoring individual performance within teams. In particular, in service
of team-plans agents may select individual sub-plans, which do not necessitate
agreement by team-members, but are constrained by the agents' roles. For instance,
in service of executing the team-plan \texttt{fly-flight-plan} (Figure \ref{modsaf-hierarchy})
pilots individually select their own individual plans which set the velocity
and heading within the constraints of the formation and flight method specified
in the mission. 

Role similarity relationships specify the ways in which given individual plans
are similar, and to what extent. Two agents of the same role who are executing
dissimilar plans can be considered to be in violation of the role-similarity
relationships. This enables a socially-attentive monitoring system to detect
failure in role-execution. To monitor individual plans the agent is executing,
it compares its selection with that of other agents of \emph{the same role},
similarly to the method we used for teamwork. If the plans are considered similar
by the role-similarity relationship model, no failure is detected. Otherwise,
a failure may have occurred, and the diagnosis component is called to verify
it and provide an explanation.

Let us illustrate with a failure from the ModSAF domain which our system was
able to detect using the role-similarity relationship: 

\begin{example}
A team of three helicopters was to take off from the base and head out on a
mission. However, one of the pilot agents failed to correctly process the mission
statement. It therefore kept its helicopter hovering above the base, while its
teammates left to execute the mission by themselves. 
\end{example}
This failures was detected using role-similarity relationship monitoring. The
agreed-upon team-plan was selected by all the agents, and so no problem with
teamwork relationship was detected. This team-plan involved each agent then
selecting individual methods of flight, which determine altitude and velocity.
Here the agents differed. The failing helicopter remained hovering, while its
teammates moved forward. Using a role similarity relationship, the failing helicopter
compared its own selected plan to that of its teammate (who shared its role
of a subordinate in the formation), and realized that their plans were dissimilar
enough to announce a possible failure. 

Unfortunately, the actual similarity metrics seem to be domain- and task-specific,
and thus are not as easy to re-use across domains. Furthermore, detected failures
are not necessarily real failures, nor do all detected failures have the same
weight. We are currently investigating ways to address these challenging issues.


\section{\label{sec:related-work}Related Work}

Our investigation of socially-attentive monitoring, and the relationship between
knowledge maintained of agents' states and monitoring effectiveness builds on
research in different sub-fields of multi-agent systems. We address these sub-fields
in this section, and explain how our investigation is related to existing literature. 


\subsection{Related Work on Teamwork }

Previous work in teamwork has recognized that monitoring other agents is critical
to teams. Past investigations have raised the monitoring selectivity problem,
but have not addressed it in depth. Building upon these investigations, this
paper begins to provide some in-depth answers to this problem.

The theory of SharedPlans \cite{sharedplans96,sharedplans99} touches on the
teamwork monitoring selectivity problem in several ways, but provides only some
initial answers. First, the theory requires agents to know that their teammates
are capable of carrying out their tasks in the team. The authors note that agents
must communicate enough about their plans to convince their teammates of their
ability to carry out actions \cite[p. 314]{sharedplans96}. Second, the theory
requires agents to have mutual-belief in the shared recipe, a state that requires
agents to reason to infinite recursion about other agent's beliefs. Unfortunately,
attainment of mutual belief is undecidable in theory \cite{halpern90} and hence
must be approximated in practice \cite{jennings95,collagen97}. Such approximations
may still impose strong monitoring requirements. Third, theory introduces the
intention-that construct in service of coordination and helpful behavior, implying
monitoring of others' progress to assess the the need for such behavior \cite[Axiom A5-A7]{sharedplans96}.
Fourth, SharedPlans requires that intentions of an agent must not conflict \cite[Axiom A1]{sharedplans96},
and since some of these intentions (in particular, intentions-that) may involve
the attitudes of other agents, some monitoring of others to detect and avoid
conflicts is implied. The authors point out that while theoretically all such
conflicts can be detected, this is infeasible in practice \cite[p. 307]{sharedplans96}.
They suggest that conflict detection and prevention be investigated in a problem-specific
manner within the minimal constraints (i.e., monitoring for capabilities, mutual-belief,
progress, lack of conflicts) provided by the SharedPlans framework (p. 308 and
314). 

Joint-Intentions \cite{jif-aaai,jif-nous} requires an agent who privately comes
to believe that a joint-goal is either achieved, unachievable, or irrelevant,
must commit to having the entire team mutually believe it to be the case. As
in the theory of SharedPlans, Joint-Intentions' use of mutual belief can only
be approximated in practice, and imposes strong monitoring requirements. Thus,
the monitoring selectivity problem is raised for practical implementations of
Joint-Intentions.

Jennings has hypothesized that two central constructs in cooperative multi-agent
coordination are \emph{commitments} made by the agents, and \emph{conventions},
rules used to monitor these commitments \cite{jennings93}. Such conventions
are used to decide what information needs to be monitored about agents, and
how it is to be monitored. For instance, a convention may require an agent to
report to its teammates any changes it privately detects with respect to the
attainability of the team goal. Jennings raises the monitoring selectivity problem
and provides an example of specific conventions for high- and low-bandwidth
situations in which some knowledge is not communicated to all agents if the
bandwidth is not available. However, Jennings does not explore in-depth the
question of how such conventions are selected, and what are the trade-offs and
guarantees associated with the selection of particular conventions. For instance,
there are no guarantees on the effects of using the low-bandwidth convention
in the example.

The theoretical investigations described above all raise the monitoring selectivity
problem (implicitly or explicitly). Our work builds upon these to address this
problem in depth, in the context of socially-attentive monitoring in teams.
This paper reports on soundness and/or completeness properties of teamwork relationship
failure-detection that can be analytically guaranteed, despite uncertainty in
knowledge acquired about monitored agents. The analytical guarantees are applicable
to plan-recognition and communications, and are corroborated by empirical results.

Building on theoretical work, practical teamwork systems include \cite{jennings95,collagen97}
and \cite{STEAM-jair}. Jennings' investigation of the Joint-Responsibility teamwork
model in GRATE{*} \cite{jennings95} builds on Joint-Intentions, and similarly
to our own implementation, requires agents to agree on the team-plans which
are to execute. However, GRATE{*} is used in industrial settings in which foolproof
communications can be assumed \cite[p. 211]{jennings95}, and thus only passive
monitoring (via communications) is used. Although Jennings provides an evaluation
of GRATE{*}'s performance with respect to communication delays, no guarantees
are provided with respect to failure detection. GRATE{*} maintains knowledge
about other agents through acquaintances models, which are used to keep track
of what team-members' capabilities are (in service of forming teams). However,
the question of how much knowledge should be used in these models is left unaddressed.

Rich and Sidner investigate COLLAGEN in a collaborative user-interface system,
in which communications are reliable \cite{collagen97}. However, from a human-usability
perspective, limiting the amount of communications is still desirable. To address
this issue, recent empirical work by Lesh, Sidner and Rich \citeyear{lesh99}
utilizes plan recognition in COLLAGEN; the focus of that work is on using the
collaborative settings to make the plan-recognition tractable. For instance,
ambiguities in plan-recognition may be resolved by asking the user for clarification.
Work on COLLAGEN does not investigate how much knowledge is to be maintained
for effective collaborative dialogue with the user. In contrast, we are able
to provide guarantees on the failure-detection results of our algorithms. Also,
analysizing the dialogue plans for \emph{risky points} may allow systems such
as COLLAGEN to decide whether to use communications for clarification regardless
of plan-recognition ambiguity.

\begin{sloppypar} STEAM \cite{STEAM-jair} maintains limited information about the ability of team-members
to carry out their roles. STEAM also allows team-members to reason explicitly
about the cost of communication in deciding whether to communicate or not. Our
work significantly extends these capabilities via plan-recognition, and provides
analytically-guaranteed fault-detection results. Furthermore, our teamwork failure-detection
capabilities can be useful to trigger STEAM's re-planning capabilities. \end{sloppypar}


\subsection{Related Work on Coordination}

Huber \citeyear{huber-jif95} investigated the use of probabilistic plan-recognition
in service of active teamwork monitoring, motivated by the unreliability and
costs of passive communications-based monitoring in military applications. Washington
explores observation-based coordination using Markov Models \cite{washington98},
focusing on making the computations tractable. In contrast to Huber and Washington,
our work focuses on the monitoring selectivity problem. We showed strengths
and limitations of centralized and distributed approaches that guaranteed failure-detection
results using coherence-based disambiguation of plan-recognition hypotheses. 

Durfee \citeyear{durfee95} discusses various methods of reducing the amount
of knowledge that agents need to consider in coordinating with others. The methods
discussed involve pruning parts of the nested models, using communications,
using hierarchies and abstractions, etc. While the focus of this work is on
methods by which modeling can be limited, the focus of our work is on the question
of how much modeling is required for guaranteed performance--the monitoring
selectivity problem. We provide analytical guarantees on trade-offs involved
in using limited knowledge of agents for failure-detection purposes.

Sugawara and Lesser \citeyear{sugawara99} report on the use of comparative reasoning/analysis
techniques in service of learning and specializing coordination rules for a
system in which distributed agents coordinate in diagnosing a faulty network.
The investigation is focused on optimizing coordination rules to minimize inefficiency
and redundancy in the agent's coordinating messages. Upon detecting sub-optimal
coordination (via a fault model), the agents exchange information on their local
views of the system and the problem solving activity, and construct a global
view. They then compare the local view to the global view to find critical values/attributes
which were missing from the local view and therefore gave rise to the sub-optimal
performance problem. These values and attributes are used in constructing situation-specific
rules that optimize coordination in particular situations. For example, network
diagnosis agents may learn a rule that guides them to choose a coordination
strategy in which only one agent performs the diagnosis and shares its result
with the rest of the diagnosis agents. Our work on socially-attentive monitoring
similarly uses comparison between agents views to drive the monitoring process.
However, our use of comparison is a product of the relationship we are monitoring.
While Sugawara and Lesser's work can be viewed as letting the agents incrementally
optimize their monitoring requirements, our results analytically explore the
level of monitoring required for effective failure-detection, in different configurations.
Our teamwork monitoring technique addresses uncertainty in the acquired information,
and does not construct a global view of all attributes the system---as that
would be extremely expensive. Instead, our technique focuses on triggering failure
detection via contrasting of plans, then incrementally expanding the search
for differences in the diagnosis process. 

Robotics literature has also raised the monitoring selectivity problem. Parker
\citeyear{parker93} investigated the monitoring selectivity problem from a different
perspective, for a formation-maintenance task. She empirically examined the
effects of combining socially-attentive information (which she referred to as
local) and knowledge of the team's goals, and concludes that the most fault-tolerant
strategy is one where the agents monitor each other as well as progress towards
the goals. Kuniyoshi et al. \cite{kuniyoshi94} present a framework for cooperation
by observations, in which robots visually attend to others as a prerequisite
to coordination. The framework presents several standard attentional templates,
i.e., who monitors whom. They define a team attentional structure as one in
which all agents monitor each other. Our work focuses on the monitoring selectivity
problem within socially-attentive monitoring of teamwork relationships, and
provides analytical as well as empirical results. We treat the attentional templates
as a product of the relationships that hold in the system. Our results show
that monitoring in teams may not necessarily require monitoring all team-members.


\subsection{Other Related Work }

Horling et al. \cite{horling99} present a distributed diagnosis system for a
multi-agent intelligent home environment.The system uses fault-models to identify
failures and inefficiencies in components, and to guide recovery. Schroeder
and Wagner \citeyear{schroeder97} proposed a distributed diagnosis technique
in which cooperating agents receive requests for tests and diagnoses, and send
responses to other agents. They each construct a global diagnosis based on the
local ones they produce and receive---with the assumption that no conflicts
will occur. Frohlich and Nejdl \citeyear{frohlich96} investigates a scheme in
which multiple diagnosis agents cooperate via a blackboard architecture in diagnosing
a physical system. The agents may use different diagnosis models or systems,
but a centralized conflict-resolution agent is employed to handle any conflicts
in diagnoses found. All three approaches do not address the monitoring selectivity
problem. 

There are a few social measures related to the ATA. Goldberg and Mataric \citeyear{goldberg97}
investigate a multi-robot foraging task and measure \emph{interference}---the
amount of time robots spend avoiding each other. Balch \citeyear{balch-thesis}
uses social entropy \cite{socialentropy} to measure \emph{behavioral diversity}
in multi-agent tasks of soccer, foraging, and formation-maintenance. Both investigations
focus on characterizing heterogeneity in multi-agent systems and its relation
to performance. In contrast, the focus of our work is on providing useful feedback
to the designer. Possible correlation between task performance and ATA values remains to be investigated.


\section{\label{sec:conclusions}Conclusions and Future Work}

The work presented in this paper is motivated by practical concerns. We have
begun our investigation of the monitoring selectivity problem as a result of
our observation that failures continue to occur despite our agents' use of monitoring
conditions and communications. Analysis of the failures revealed that agents
were not sufficiently informed about each other's state. While the need to monitor
one's teammates has been recognized repeatedly in the past \cite{jennings93,sharedplans96,STEAM-jair},
the monitoring selectivity problem---the question of how much monitoring is
required---remained largely unaddressed \cite{jennings93,sharedplans96}. 

We provide key answers to the monitoring selectivity problem. Within the context
of socially-attentive monitoring in teams, we demonstrate that teamwork relationship
failures can be detected effectively even with uncertain, limited, knowledge
of team-members' states. We show analytically that centralized active teamwork
monitoring provides failure-detection that is either complete and unsound, or
sound and incomplete. However, centralized teamwork monitoring requires multiple
hypotheses and monitoring of all team-members. In contrast, distributed active
teamwork monitoring results in complete and sound failure-detection, despite
using a simpler algorithm and monitoring only key agents in a team. 

Using an implemented general framework for socially-attentive monitoring, we
empirically validate these results in the ModSAF domain. We also provide initial
results in monitoring mutual-exclusion and role-similarity relationships, and
initial diagnosis procedures. We further demonstrate the generality of the framework
by applying it in the RoboCup domain, in which we show how useful quantitative
analysis can be generated off-line. Both ModSAF and RoboCup are dynamic, complex,
multi-agent domains that involve many uncertainties in perception and action. 

We attempted to demonstrate how the results and techniques can be applied in
other domains. We have explicitly pointed out necessary conditions for the theorems
to hold, such as observable-partitioning and team-modeling completeness. The
presented diagnosis algorithm is sensitive to the accuracy of the knowledge
used, and may require assuming that plans can be recognized as soon as they
are selected. These conditions should be verified by the designer in the target
application domain. Reactive plans (our chosen representation) are commonly
used in many dynamic multi-agent domains. Our focus on monitoring agreements
on joint plans stems from the centrality of similar notions of agreement in
agent and human teamwork literature \cite{jennings95,sharedplans96,volpe96,STEAM-jair}. 

We made several references to additional areas in which we would like to conduct
further investigations. One important topic which we plan to investigate in
depth is the strong requirements of the distributed teamwork monitoring algorithm
in terms of observability. In order to provide its soundness and completeness
guarantees, the distributed algorithm relies on the ability of all team-members
to monitor the key agents. We are investigating ways to relax this requirement
while still providing guaranteed results. In addition, the diagnosis procedures
should be extended and formalized, and we would like to investigate ways to
alleviate the sensitivity of these procedures to the choice of team-modeling
hypothesis. 


\section*{Acknowledgments}

This article is partially based on an AAAI-98 paper \cite{aaai98}, and an Agents-99
paper \cite{agents99} by the same authors. This research was supported in part
by NSF Grant ISI-9711665, and in part by AFOSR contract \#F49620-97-1-0501.
We thank Jeff Rickel, George Bekey, Victor Lesser, Dan O'Leary, and David Pynadath
for many useful comments. The anonymous reviewers have our thanks for helping
us to crystallize our ideas and contributions in revisions of this paper.

\appendix


\section{\label{proofs} Proofs}

\begin{thm*}
\emph{(\# \ref{thm:team-incoherence leads to completeness}, page \pageref{thm:team-incoherence leads to completeness}).}
Let a monitoring agent $A$ monitor a simple team $T$. If $A$'s team-modeling
of $T$ is complete, and $A$ uses a maximally team-coherent hypothesis for detection,
then the teamwork failure detection results are sound.
\end{thm*}
\begin{proof}
We will show that any failure that occurs is detected, and thus that all failures
will be detected. Let $a_1,\hdots,a_n$ be the agent members of $T$. Each agent
$a_i$ is executing some plan $P_i$ \( (1\leq i\leq n) \). Thus collectively,
the group is executing $(P_1,\hdots,P_n)$. If a failure has occurred, then there
are two agents \( a_{k},a_{j},1\leq j,k\leq n \) such that $a_j$ is executing
plan $P_j$ and $a_k$ is executing plan $P_k$ and \( P_{j}\neq P_{k} \). Since
$A$'s team-modeling is complete, the correct hypothesis \( (P_{1},\ldots ,P_{j},\ldots ,P_{k},\ldots P_{n}) \)
will in the set of team-modeling hypotheses. Since $A$ will choose a maximally
team-incoherent hypothesis, either it will choose the correct hypothesis, which
is more incoherent than a hypothesis implying no failure has occurred, or that
it will select a hypothesis with greater incoherence hypothesis (or equivalent
level). In any case, a failure would be detected, and the detection procedure
is complete.
\end{proof}
\begin{lem*}
(\# \emph{\ref{lemma:detection in observably different plans}, page \pageref{lemma:detection in observably different plans}).}
Suppose a simple team $T$ is self-monitoring (all members of the team monitor
each other) using the maximally team-coherent heuristic (and under the assumption
that for each agent, team-modeling is complete). A monitoring agent $A_1$ who
is a member of $T$ and is executing $P_1$ would detect a failure in maintaining
teamwork relationships with an agent $A_2$ (also a member of $T$) executing
a different plan $P_2$, if $A_2$ has an observably different role in $P_1$ and
$P_2$.
\end{lem*}
\begin{proof}
$A_1$ knows that it is executing $P_1$. Since all members of $T$ monitor each
other and themselves, $A_1$ is monitoring $A_2$, who has an observably different
role in $P_1$ and $P_2$. Since $A_2$ is executing $P_2$, and following the observably
different role, \( P_{1}\notin M(A_{1},A_{2}/P_{2}) \). Therefore from the
perspective of $A_1$, it cannot be the case that it assigns $P_1$ in any \emph{agent-modeling}
hypothesis, and therefore any \emph{team-modeling} hypothesis that $A_1$ has
will have $A_1$ executing $P_1$, and $A_2$ executing some plan other than $P_1$.
In other words, from $A_1$'s perspective there is no team-coherent hypothesis,
and so a difference would be detected between $A_1$ and $A_2$. 
\end{proof}
\begin{thm*}
(\# \ref{thm:incohrence-is-sound-in-mutual-ex}, page \pageref{thm:incohrence-is-sound-in-mutual-ex}).
Let a monitoring agent $A$ monitor mutual-exclusion relationships in a group
of agents $G$. If $A$'s modeling of $G$ is complete, and $A$ uses a maximally
team-\emph{in}coherent hypothesis for detection, then the failure detection
results are sound.
\end{thm*}
\begin{proof}
We will show that if no failure has occurred, none will be detected, and thus
that any failure that is detected is in fact a failure. Let $a_1,\hdots,a_n$
be the agent members of $G$. Each agent $a_i$ is executing some plan $P_i$ \( (1\leq i\leq n) \).
Thus collectively, the group is executing $(P_1,\hdots,P_n)$. If no failure
has occurred, then each agent is executing a different plan (\( i\neq j\Rightarrow P_{i}\neq P_{j} \)).
Since $A$'s group-modeling is complete, the correct hypothesis is going to be
in the set of group-modeling hypotheses $H$. Since it is a maximally incoherent
hypothesis, either it will be selected, or that a different hypothesis \emph{of
the same coherence level} will be selected. Any hypothesis with the same coherence
level as the correct one implies no failure is detected. Thus the detection
procedure is sound.
\end{proof}
\begin{thm*}
(\# \ref{thm:cohrence-is-complete-in-mutual-ex}, page \pageref{thm:cohrence-is-complete-in-mutual-ex}).
Let a monitoring agent $A$ monitor mutual-exclusion relationships in a group
of agents $G$. If $A$'s modeling of $G$ is complete, and $A$ uses a maximally
team-coherent hypothesis for detection, then the failure detection results are
complete.
\end{thm*}
\begin{proof}
We will show that any failure that occurs is detected, and thus that the procedure
is complete. Let $a_1,\hdots,a_n$ be the agent members of $G$. Each agent $a_i$
is executing some plan $P_i$ \( (1\leq i\leq n) \). Thus collectively, the
group is executing $(P_1,\hdots,P_n)$. If a failure has occurred, then there
are two agents \( a_{k},a_{j},1\leq j,k\leq n \) such that $a_j$ is executing
plan $P_j$ and $a_k$ is executing plan $P_k$ and \( P_{j}=P_{k} \). Since $A$'s
group-modeling is complete, the correct hypothesis \( (P_{1},\ldots ,P_{j},\ldots ,P_{k},\ldots P_{n}) \)
will in the set of group-modeling hypotheses. Since $A$ will choose a maximally
team-coherent hypothesis, either it will choose the correct hypothesis, which
is more coherent than a hypothesis implying no failure has occurred, or that
it will select a hypothesis with greater coherence hypothesis (or equivalent
level). In any case, a failure would be detected. Therefore, the detection procedure
is complete.
\end{proof}

\section{\label{algorithms} Socially-Attentive Monitoring Algorithms}

We bring here the algorithms (in pseudo-code) for the RESL plan-recognition
algorithm, the comparison test supporting detection in both simple and non-simple
teams, and the monitoring algorithms for the centralized and distributed cases.


\subsection{RESL}

RESL works by first expanding the complete operator hierarchy for the agents
being modeled, tagging all plans as non-matching. All plans' preconditions and
termination conditions are flagged as non-matching as well. All plans' actions
are set to be used as expectations on behavior. After initializing the plan-recognition
hierarchy for each monitored agent, observations of an agent are continuously
matched against the actions expected by the plans. Plans whose expectations
match observations are tagged as matching, and these flags are propagated along
the hierarchy, up and down, so that complete paths through the hierarchy are
flagged as matching or not. These paths specify the possible matching interpretations
of the observations. In addition, precondition and termination conditions are
flagged as true or not, signifying the inferred appropriate belief by the modeled
agents. This process is described in Algorithm \ref{alg:resl}. 

\begin{algorithm}
\begin{enumerate}
\item \textsf{Get observations about agent }
\item \textsf{For each plan that has a set of expected observations:\begin{enumerate}}
\item \textsf{Compare observations to expectations}
\item \textsf{If succeed, flag plan as matching successfully, otherwise flag plan
as failing to match\end{enumerate}}
\item \textsf{For each plan that is flagged as matching successfully\begin{enumerate}}
\item \textsf{Flag its parents as matching successfully //} propagate matching\textsf{\end{enumerate}}
\item \textsf{For each plan whose children (all of them) are flagged as failing to
match\begin{enumerate}}
\item \textsf{Flag it as failing to match //} propagate non-matching\textsf{\end{enumerate}}
\end{enumerate}

\caption{\label{alg:resl}RESL's main loop, matching observation and making inferences
for a given plan-recognition hierarchy (a single agent).}
\end{algorithm}



\subsection{Detection of Failure, Centralized and Distributed Teamwork Monitoring}

Algorithm \ref{alg:compare} shows how comparison of hierarchical plans is carried
out. We limit ourselves here to simple-teams. The algorithm accepts as input
two sets of hierarchical plan hypotheses, and their two associated agents (for
clarity, the algorithms assume only two agents. The generalization to $n$ agents
is straightforward). The algorithm also accepts a policy flag, \texttt{Policy}.
An \texttt{OPTIMISTIC} policy causes the algorithm to use maximal team-coherence
to provide sound, but incomplete detection. A \texttt{PESSIMISTIC} policy causes
the algorithm to use maximal team-incoherence to provide complete, but unsound
detection.

The set of hierarchical plans are marked \texttt{hierarchy\_1} and \texttt{hierarchy\_2}.
The two agents are marked \texttt{agent\_1} and \texttt{agent\_2}. The algorithm
makes use of the predicate \texttt{Sub-team}, which is true if the two agents
\texttt{(Agent1,~Agent2}) belong to different sub-teams at the given level of
the hierarchy (\texttt{Depth)}. 

\begin{algorithm}
\begin{enumerate}
\item \textsf{Set}~\texttt{Depth} \textsf{to}~\texttt{0} \textsf{//} look for top-most
difference first
\item \textsf{While both plans at depth Depth are team-plans Do}\begin{enumerate}
\item \textsf{if}~\texttt{Policy} \textsf{==}~\texttt{OPTIMISTIC} \textsf{\begin{enumerate}}
\item \textsf{then Let}~\texttt{Plan\_1,~Plan\_2} \textsf{be maximally team-coherent
plans at level}~\texttt{Depth} \textsf{of}~\texttt{hierarchy\_1} \textsf{and}
\texttt{hierarchy\_2}\textsf{, respectively.}
\item \textsf{else Let}~\texttt{Plan\_1,~Plan\_2} \textsf{be maximally team-}\textsf{\emph{in}}\textsf{coherent
plans at level}~\texttt{Depth} \textsf{of}~\texttt{hierarchy\_1} \textsf{and}
\texttt{hierarchy\_2}\textsf{, respectively.\end{enumerate}}
\item \textsf{If}~\texttt{Plan\_1} \textsf{is} \textsf{\emph{not equal}} \textsf{to}
\texttt{Plan\_2} \textsf{\begin{enumerate}}
\item \textsf{then return}~\texttt{FAILURE}
\item \textsf{else if bottom of hierarchies reached, return}~\texttt{NO\_FAILURE}\textsf{,
otherwise increase}~\texttt{Depth} \textsf{and go to 2.\end{enumerate}\end{enumerate}}
\item \textsf{If only one plan is a team-plan, return}~\texttt{FAILURE}, \textsf{else
return}~\texttt{NO\_FAILURE}.
\end{enumerate}

\caption{\label{alg:compare}Hierarchical comparison of two agents, allowing for sub-teams.}
\end{algorithm}
With the aid of Algorithm \ref{alg:compare}, we can now define the centralized
and distributed failure detection algorithms. The centralized teamwork monitoring
algorithm (Algorithm \ref{alg:centralized-monitoring}) utilizes Algorithm \ref{alg:compare}
twice, checking for failures with both \texttt{PESSIMISTIC} and \texttt{OPTIMISTIC}
policies. If the results of both policies agree, they are certain. If the results
do not agree, (i.e., the \texttt{PESSIMISTIC} policy causes a failure to be
detected, while the \texttt{OPTIMISTIC} policy causes no failure to be detected),
then the monitoring agent cannot be certain that a failure has taken place,
and therefore needs to verify the failure. Algorithm \ref{alg:centralized-monitoring}
therefore returns \texttt{FAILURE,~NO\_FAILURE,~POSSIBLE\_FAILURE}.

\begin{algorithm}
\begin{enumerate}
\item {\par\raggedright \textsf{Let}~\texttt{Optimistic\_Result} \textsf{=}~\texttt{Detect(agent\_1,~agent\_2,~hierarchies\_1,
hierarchies\_2,~OPTIMISTIC)} \textsf{}\\
\textsf{/{*}} algorithm \ref{alg:compare} \textsf{{*}/}\par}
\item {\par\raggedright \textsf{Let}~\texttt{Pessimistic\_Result} \textsf{=}~\texttt{Detect(agent\_1,~agent\_2,~hierarchies\_1,
hierarchies\_2,~PESSIMISTIC)} \textsf{}\\
\textsf{/{*}} algorithm \ref{alg:compare} \textsf{{*}/}\par}
\item {\par\raggedright \textsf{if}~\texttt{Optimistic\_Result} \textsf{==}~\texttt{Pessimistic\_Result} \textsf{}\par}
\item {\par\raggedright \textsf{then return}~\texttt{Optimistic\_Result} \textsf{/{*}}
either \textsf{}\texttt{FAILURE}, or \textsf{}\texttt{NO\_FAILURE} \textsf{{*}/}\par}
\item {\par\raggedright \textsf{else return}~\texttt{POSSIBLE\_FAILURE}\par}
\end{enumerate}

\caption{\label{alg:centralized-monitoring}Centralized Teamwork Monitoring, applying
both optimistic and pessimistic views.}
\end{algorithm}


The distributed monitoring algorithm is not given in pseudo-code form, because
it is nothing more than a call to Algorithm \ref{alg:compare} with an \texttt{OPTIMISTIC}
policy parameter. Its power is derived from the fact that all members of the
team are using it to monitor the key agents of the team.

\bibliographystyle{theapa}
\bibliography{/home/galk/Work/bib/full.bib,/home/galk/Work/bib/all.bib}


\end{document}
