• Sorted by Date • Classified by Publication Type • Classified by Topic • Grouped by Student (current) • Grouped by Former Students •
Gery Gutnik. Monitoring large-scale multi-agent systems using overhearing.
Ph.D. Thesis, Bar Ilan University, 2006.
[PDF]1.4MB [gzipped postscript]1.4MB
Overhearing is fast gaining attention as a generic method for monitoring open, distributed multi-agent systems. In such settings, agents' internal structure is not generally known to a monitoring agent, but overhearing does not require such knowledge. Instead, the monitoring agent uses the overheard routine communications as a basis for inference about the other agents. Our work focuses on cooperative overhearing, in which the overheard agents usually know they are being overheard, and do not in any way intend to disrupt the monitor. Previous work on overhearing investigated an extensive set of techniques and implementations of overhearing. However, focusing mainly on its potential applications, those investigations often rely on assumptions related to the fundamentals of overhearing. In contrast, we dedicate our research to a comprehensive study of the fundamental building blocks that allow overhearing in the first place. In doing so, we systematically tackle various assumptions made by previous investigations. In particular, our study focuses on overhearing in large-scale multi-agent systems and addresses the specific challenges and limitations that characterize such settings. The first overhearing building block, addressed by our research, is the representation of multi-agent conversations. Various formalism have been proposed for that purpose. In particular, recent investigations showed Petri nets to provide a viable representation approach for modelling multi-agent interactions. By analyzing the strengths and weaknesses of the rather radical Petri net approaches introduced by previous work, we propose a novel representation technique especially suitable for overhearing. Furthermore, we show this representation to be more scalable than previous representations, and thus more appropriate for monitoring conversations in large-scale settings. We show that this new representation offers a comprehensive coverage of essentially all conversation features needed to represent complex multi-agent conversations. We also present a procedure for transforming human-readable AUML conversation protocol diagrams to our machine-readable Petri net representation. Next, we addressed the building block of conversation recognition. Conversation recognition is the process of identifying the actual conversation based on a sequence of overheard messages. In the process, the overhearing agent extracts various parameters of the overheard conversation such as the set of conversing agents, the corresponding conversation protocol, etc. In addition, it also handles possible errors caused by differences between the conversation as it was overheard and as it was actually carried out by the agents (e.g., in cases where the overhearer was not able to overhear some of the exchanged messages). Although conversation recognition is a key step in overhearing prior to any possible inference based on overheard communications, it is often discarded by previous investigations. Our work addresses the challenges related to conversation recognition by first introducing a formal model of overhearing. Most previous works focus on potential applications of overhearing. Therefore, the proposed model was the first to formalize the general problem of overhearing unrelated to any specific task. Then, based on this model, we provide a skeleton algorithm for conversation recognition, and provide instantiations of it for lossless and lossy settings. Since in large-scale multi-agent systems overhearing agent has to process large quantities of intercepted messages, conversation recognition algorithms must be efficient. Accordingly, the time-complexity of these algorithms was analyzed. We show that handling conversation recognition of systematic message loss, which is unique to overhearing, is significantly more efficient than handling the general case of randomly lost messages (which is intractable). The final building block addressed in this work is selective overhearing, i.e. overhearing under the restriction of selectivity. The restriction of selectivity is mainly compelled by the specific characteristics of large-scale multi-agent systems. In such settings, it is reasonable to assume that the overhearing resources will be essentially limited, thus allowing the overhearing agent to overhear only a subset of inter-agent communications carried out in the monitored settings. Accordingly, the overhearer must be careful in choosing which targets to overhear on account of other potential targets. Most previous investigations on overhearing ignore the limitation of selectivity, assuming that all relevant inter-agent communications can be overheard. Tackling this problematic assumption, our work provides an empirical study of selective overhearing focusing on widely common hierarchical organizations. Here, we first propose a model for selective overhearing of such organizations. Then, using a simulation of this model, we perform an extensive set of experiments in which we empirically evaluate and compare performance of various overhearing policies taking into consideration both the limitations of selectivity and the specific characteristics of hierarchical organizations. We empirically study both centralized and distributed selective overhearing policies. In doing so, we tackle another problematic assumption by previous investigations. Those investigations either assume a single overhearer or a group of non-cooperative overhearing agents that perform overhearing out of their own interest. In contrast, our work considers overhearing committed by a group of collaborative overhearers. First, we consider centrally-coordinated overhearing groups which are equivalent to a single centrally-located overhearer. But, then, we empirically study the transition to a group of overhearing agents acting collaboratively in a distributed manner. Based on the performed experiments, we were able to isolate the factors influencing the behavior of those policies and reach several qualitative conclusions. With respect to centralized overhearing policies, we have found a classical value-volume tradeoff. This tradeoff was found to be surprisingly robust to many characteristics of hierarchical organizations. However, what was more surprising is that the combination of two types of policies (value and volume) in addition to being fully robust, outperformed each of the policies separately. Addressing distributed policies, we considered the transition from effective centralized policies to distributed ones by gradually decreasing the level of collaboration between the overhearing agents. Here, we found some factors to significantly influence the performance of the examined policies, while finding that others can simply be neglected or only partially solved.
@PhdThesis{gutnik-phd,
author = {Gery Gutnik},
title = {Monitoring large-scale multi-agent systems using overhearing},
school = {{B}ar {I}lan {U}niversity},
year = {2006},
OPTkey = {},
OPTtype = {},
OPTaddress = {},
OPTmonth = {},
OPTnote = {},
abstract = {
Overhearing is fast gaining attention as a generic method for monitoring open, distributed multi-agent systems.
In such settings, agents' internal structure is not generally known to a monitoring agent, but overhearing does
not require such knowledge. Instead, the monitoring agent uses the overheard routine communications as a basis
for inference about the other agents. Our work focuses on cooperative overhearing, in which the overheard agents
usually know they are being overheard, and do not in any way intend to disrupt the monitor.
Previous work on overhearing investigated an extensive set of techniques and implementations of overhearing.
However, focusing mainly on its potential applications, those investigations often rely on assumptions related
to the fundamentals of overhearing. In contrast, we dedicate our research to a comprehensive study of the
fundamental building blocks that allow overhearing in the first place. In doing so, we systematically tackle
various assumptions made by previous investigations. In particular, our study focuses on overhearing in
large-scale multi-agent systems and addresses the specific challenges and limitations that characterize such
settings.
The first overhearing building block, addressed by our research, is the representation of multi-agent
conversations. Various formalism have been proposed for that purpose. In particular, recent investigations
showed Petri nets to provide a viable representation approach for modelling multi-agent interactions. By
analyzing the strengths and weaknesses of the rather radical Petri net approaches introduced by previous work,
we propose a novel representation technique especially suitable for overhearing. Furthermore, we show this
representation to be more scalable than previous representations, and thus more appropriate for monitoring
conversations in large-scale settings. We show that this new representation offers a comprehensive coverage of
essentially all conversation features needed to represent complex multi-agent conversations. We also present a
procedure for transforming human-readable AUML conversation protocol diagrams to our machine-readable Petri net
representation.
Next, we addressed the building block of conversation recognition. Conversation recognition is the process of
identifying the actual conversation based on a sequence of overheard messages. In the process, the overhearing
agent extracts various parameters of the overheard conversation such as the set of conversing agents, the
corresponding conversation protocol, etc. In addition, it also handles possible errors caused by differences
between the conversation as it was overheard and as it was actually carried out by the agents (e.g., in cases
where the overhearer was not able to overhear some of the exchanged messages).
Although conversation recognition is a key step in overhearing prior to any possible inference based on
overheard communications, it is often discarded by previous investigations. Our work addresses the challenges
related to conversation recognition by first introducing a formal model of overhearing. Most previous works
focus on potential applications of overhearing. Therefore, the proposed model was the first to formalize the
general problem of overhearing unrelated to any specific task.
Then, based on this model, we provide a skeleton algorithm for conversation recognition, and provide
instantiations of it for lossless and lossy settings. Since in large-scale multi-agent systems overhearing agent
has to process large quantities of intercepted messages, conversation recognition algorithms must be efficient.
Accordingly, the time-complexity of these algorithms was analyzed. We show that handling conversation
recognition of systematic message loss, which is unique to overhearing, is significantly more efficient than
handling the general case of randomly lost messages (which is intractable).
The final building block addressed in this work is selective overhearing, i.e. overhearing under the restriction
of selectivity. The restriction of selectivity is mainly compelled by the specific characteristics of
large-scale multi-agent systems. In such settings, it is reasonable to assume that the overhearing resources
will be essentially limited, thus allowing the overhearing agent to overhear only a subset of inter-agent
communications carried out in the monitored settings. Accordingly, the overhearer must be careful in choosing
which targets to overhear on account of other potential targets.
Most previous investigations on overhearing ignore the limitation of selectivity, assuming that all relevant
inter-agent communications can be overheard. Tackling this problematic assumption, our work provides an
empirical study of selective overhearing focusing on widely common hierarchical organizations. Here, we first
propose a model for selective overhearing of such organizations. Then, using a simulation of this model, we
perform an extensive set of experiments in which we empirically evaluate and compare performance of various
overhearing policies taking into consideration both the limitations of selectivity and the specific
characteristics of hierarchical organizations.
We empirically study both centralized and distributed selective overhearing policies. In doing so, we tackle
another problematic assumption by previous investigations. Those investigations either assume a single
overhearer or a group of non-cooperative overhearing agents that perform overhearing out of their own interest.
In contrast, our work considers overhearing committed by a group of collaborative overhearers. First, we
consider centrally-coordinated overhearing groups which are equivalent to a single centrally-located overhearer.
But, then, we empirically study the transition to a group of overhearing agents acting collaboratively in a
distributed manner.
Based on the performed experiments, we were able to isolate the factors influencing the behavior of those
policies and reach several qualitative conclusions. With respect to centralized overhearing policies, we have
found a classical value-volume tradeoff. This tradeoff was found to be surprisingly robust to many
characteristics of hierarchical organizations. However, what was more surprising is that the combination of two
types of policies (value and volume) in addition to being fully robust, outperformed each of the policies
separately.
Addressing distributed policies, we considered the transition from effective centralized policies to distributed
ones by gradually decreasing the level of collaboration between the overhearing agents. Here, we found some
factors to significantly influence the performance of the examined policies, while finding that others can
simply be neglected or only partially solved.
},
wwwnote = {},
OPTannote = {}
}
Generated by bib2html.pl (written by Patrick Riley ) on Fri Apr 19, 2024 19:01:33