مکالمات عامل داده کاوی: یک رویکرد کیفی به تجزیه و تحلیل سیستم چندعاملی

This paper presents a novel method for analysing the behaviour of multiagent systems on the basis of the semantically rich information provided by agent communication languages and interaction protocols specified at the knowledge level. More low-level communication mechanisms only allow for a quantitative analysis of the occurrence of message types, the frequency of message sequences, and the empirical distributions of parameter values. Quite differently, the semantics of languages and protocols in multiagent systems can help to extract qualitative properties of observed conversations among agents. This can be achieved by interpreting the logical constraints associated with protocol execution paths or individual messages as the context of an observed interaction, and using them as features of learning samples. The contexts “mined” from such analyses, or context models, can then be used for various tasks, e.g. for predicting others’ future responses (useful when trying to make strategic communication decisions to achieve a particular outcome), to support ontological alignment (by comparing the properties of logical constraints attached to messages across participating agents), or to assess the trustworthiness of agents (by verifying the logical coherence of their behaviour). This paper details a formal approach that describes our notion of context models in multiagent conversations, an implementation of this approach in a practical tool for mining qualitative context models, and experimental results to illustrate its use and utility.

One of the cornerstones of agent technology is the loose coupling between agents achieved by introducing standardised high-level agent communication languages (ACLs, e.g. FIPA-ACL [6]) and interaction protocols. As opposed to low-level interaction mechanisms for computer systems (like those used in traditional distributed computing), these advanced languages and protocols attempt to capture shared meaning for messages exchanged in multiagent systems. This helps to ensure that, despite the heterogeneity among individual agents who cannot observe each other’s internal states, some level of interoperability can be achieved in practice, so that large-scale open multiagent systems can be implemented in the real world. At the same time, when it comes to analysing agent-based systems, the openness of these systems limits the available data to what goes on among agents (i.e. observations of message exchanges, at least if we assume that the observer does not have access to all internal details of all agents in the system [15]). However, the structure and “knowledge-level” assumptions captured in ACLs and interaction protocols is semantically rich and can be used to partially compensate for the loss of transparency caused by agent-level encapsulation, which makes the mental states of an agent opaque to others. As an example of this, consider a message inform(A,B,X)inform(A,B,X) with the usual meaning that agent A informs B of a fact X (where X is taken from some domain ontology or “content language”). The use of this message type is usually tied to preconditions like View the MathML source(BelAX) stating that A in fact believes X to be true. While B is unable to verify whether this is actually the case (or A is lying/has a different interpretation of the BelBel modality), the use of the message entitles B to operate under the assumption that View the MathML source(BelAX) is true for A. For example, if B contested X, it would be unreasonable for a protocol to allow A to state that she never claimed X. Therefore, at a pragmatic level, any semantic “annotations” (pre- and post-conditions) of messages that an agent is uttering can be used as assumptions about that agent’s mental state (or, e.g. in commitment-based semantics [7], about their perception of a social state). Quite surprisingly, this aspect of data analysis has been overlooked in the existing literature (see Section 2). Existing approaches remain at the quantitative level, i.e. any measurements they take are based on assessing the observed values of some attributes of the interaction. A binary distinction between “interaction was successful or not” is often employed, sometimes also a measurement of the quality of different attributes along numerical scales, e.g. speed, price, reliability, etc. While in non-agent scenarios this may be the only kind of data that is available, if one focuses only on quantitative analysis, a lot of additional structural information goes “to waste” in a sense when considering ACL-based multiagent system interactions. The contribution of this paper is to fill this gap by exploring the use of data mining techniques over semantically rich interaction protocols defined using typical ACLs. By using semantic elements of protocols as features of interaction traces, which are available as data samples from past interactions, we can inductively derive what we call context models, i.e. logical theories that capture regularities in previously observed interactions. Note that the protocol definition or protocol model needs to include semantic annotations to allow the approach presented in this paper to build an effective context model automatically, and, in this paper, we will make the assumption that protocol specifications include such annotations. Context models, which essentially capture generalised information about the conditions under which a protocol reaches a certain outcome, can be used for various purposes: (1) to make predictions about future behaviour (e.g. under what circumstances a peer is likely to deliver a product of reasonable quality); (2) to infer the definitions other agents use when validating logical constraints during an interaction (e.g. when acceptance of a certain type of offer indicates the range of a variable X for which the predicate acceptable(X)acceptable(X) holds true for an agent); and (3) to analyse the reliability and trustworthiness of agents based on the logical coherence of their utterances (e.g. if an agent has been observed to suggest that both P(o)P(o) and ¬P(o)¬P(o) are true of the same object o). Moreover, by simply grouping the data from interactions with several agents together and analysing it with a data mining algorithm, it is easy to generalise over individual “theories” held by them to develop a more global picture of the views held by an entire set of agents. The remainder of the paper is structured as follows: After reviewing related work in Section 2, we define the formal machinery that is needed to develop qualitative data mining methods for interaction protocols in Section 3. Sections 4 and 5 discuss an implemented system for qualitative data mining over interaction protocols, and empirical results obtained in a case study, respectively. Section 6 concludes.

In this paper, we have presented a novel mechanism to exploit qualitative information provided by high-level ACLs and interaction protocols, in which messages are associated with logical constraints, which can be used as “semantic” annotations of communication in a natural way. Our work was motivated by a lack in existing multiagent systems analysis methods which mostly ignore this rich source of contextual information when analysing run-time multiagent interactions. We presented a formal approach that allows us to make interaction data available for qualitative data mining using information about the shared protocol models as background knowledge. The main advantage of using the additional structure available in agent-based communication protocols is that it allows for the use of data mining methods to infer qualitative information from observed message exchanges at a higher level than this is possible using traditional distributed systems protocol. We discussed different alternatives for dealing with the specific nature of agent interaction protocols when converting interaction experiences to training data, addressing issues such as the presence of multiple agents, varying-length execution paths, and loops that are commonly present in common multiagent interaction protocols. Subsequently, we presented an implementation of our techniques with the ProtocolMiner tool, and a case study which hinted at the potential of applying data mining in multiagent systems. In the future, we aim to apply our analysis methods to more real-world examples in order to extract guidelines for making appropriate choices when selecting training data extraction strategies and appropriate data mining algorithms. We would also like to explore the use of more advanced machine learning methods to learn logical theories of, for example, the internal ontological conceptualisations agents use, and to rate their competence and trustworthiness based on the knowledge they appear to have based on their interaction behaviour. We believe these to be promising practical avenues for addressing one of the fundamental problems of open systems, which is to be able to derive knowledge of the internal workings of other agents without being able to observe their internal state.