LAMAS (workshop on Logic and MultiAgent Systems) - abstracts of presentations

back to LAMAS main page

In order of presentation

Enrico Franconi, Free University of Bolzano, The logic of information integration: classical vs peer-to-peer approaches

In this talk I will introduce a logical framework that characterises information access and integration in its classical sense. I will show the advantages of such a framework, and its computational shortcomings. I will then show how to tweak the classical logical framework to characterise a peer-to-peer behaviour. The peer-to-peer approach is more suitable in real contexts since it has much nicer computational properties and it can handle large dynamic networks.

Tommie Meyer, National ICT Australia and University of New South Wales, Debugging Logic-Based Ontologies

Description Logics (DLs) are widely accepted as an appropriate class of knowledge representation lanaguages to represent and reason about ontologies. Reasoners that perform satisfiability and consistency checking have grown increasingly powerful and sophisticated in the last decade. But although optimised reasoners such as RACER and FaCT++ are able to handle reasonably large and complex ontologies, comparatively little research effort has gone into resolving logical errors in ontologies. The development of debugging tools to help rectify such errors will greatly facilitate the construction of high-quality ontologies.

In this talk I will give a brief overview of current approaches to logical ontology debugging. One approach is to identify possible sources of the problem and to leave it up to the modeller to rectify them. This typically involves the pinpointing of the possible problematic statements. A more proactive approach is to generate possible resolutions to the problem, obtained by weakening the available information to the extent that the errors are eliminated. The most obvious way to do this is to remove just enough sentences to eliminate all errors. It is not hard to see that these two approaches are related in the sense that solutions for one can be used to generate solutions for the other.

The two approaches mentioned above have much in common with the field of belief base revision. I will argue that ontology debugging can also benefit from results in the related field of theory change. More specifically, I will show that two types of modifications to be made to ontologies during ontology construction and evolution are closely related to the well-studied classes of theory revision and theory contraction operators.

If time permits I will also discuss one of the pressing practical questions in this area - whether implementations should focus on the development of specialised reasoning algorithms, or whether it is better to build solutions on top of existing optimised reasoners. Proponents of specialised algorithms argue that their implementation will ensure maximum efficiency, which is necessary when debugging large and complex ontologies. On the other hand, every DL will most likely require its own specialised reasoner, whereas intelligent strategies for reusing existing reasoners will probably be applicable to all DLs with an implemented reasoner.

Mariusz Nowostawski, University of Otago The concept of autonomy in multi-agent systems

This work concentrates on the notion of autonomy in multi-agent systems. We will initially define an abstract concept of relative autonomy, and absolute autonomy in the context of a computational agent. We will then discuss the objectives of the research community and the motivations regarding the concept of autonomy of a given computational unit (an agent) in the context of open multi-agent systems, adaptability and complexity growth. We argue that, to build an open and adaptable multi-agent system, agents must be subjected to constant external influences, that (possibly indirectly) affect and control a given agent's behaviour, and therefore negate the requirement of absolute autonomy of any computational unit within a system. Therefore, computational agents can never be truly autonomous (in the sense of absolute autonomy) or else the applicability of multi-agent systems in solving pre-defined problems would be constrained or impossible.

To demonstrate and discuss the issues related to autonomy we present results related to an open-ended evolutionary model called Evolvable Virtual Machines. The model is used to investigate properties of asynchronously communicating agents in a parallel multi-agent system. In this context, we discuss the concept of computational complexity, evolutionary learning, and adaptability. We will show that with our computational evolutionary system, a constant flux of external variation is necessary to provide an open-ended increase of complexity of generated (discovered) computational programs. Our results suggest that any closed (or absolutely autonomous) collection of computational agents would be limited in their ability to learn and adapt to new circumstances. We claim that the notion of autonomy should be revisited, and that computational agents should be subjected to direct or indirect external influences, to allow continuous learning and adaptation by the system as a whole.

Bastin Tony Roy Savarimuthu, University of Otago, Multi-Agent Systems and Social Networks - An Overview

Human societies, over large periods of time, have evolved rules and norms that regulate human behaviour. Norms have been found to increase the predictability of individual behaviour and also facilitate cooperation between the members of the society. Some norms become laws while some of them remain as social norms whose violations are dealt through social sanctions and punishments. Multi-Agent Systems (MAS) are well suited for the study of norms as agents are modelled using some of human like behaviours such as autonomy, speech-act etc. Some researchers have worked on the treatment of norms in MAS. One of the key aspects of norm emergence is how agents are connected to each other and the static and dynamic properties of the network structure. To our knowledge, there has been very little work in MAS that make use of social network structures for the emergence of social norms.

In the light of the research carried out by physicists and mathematicians in the area of network topologies, researchers have observed that human societal interactions exhibit certain topological characteristics. They have studied how ideas, diseases etc. are spread using different topologies or the network structures of the societies such as the random networks, small world networks and the scale free networks.

The first step towards incorporating the idea of network structures in the study of norm emergence in agent societies is to review research works that make use of MAS and social networks. Our objective in this paper is to study and review research literature in MAS, where agents are connected to each other using various social network topologies.

Stephen Cranefield, University of Otago, A temporal logic and rule language for modelling and monitoring social expectations

In this talk I will describe the hyMITL+- temporal logic and a rule language using this logic that is designed for the modelling and run-time checking of social expectations. In this language, rules express how expectations on future events are triggered by observations of the present and the history of past states. hyMITL+- is a first order temporal logic (with bounded quantification) combining features of CTL*, Metric Interval Temporal Logic (MITL) and hybrid logic, and therefore allows the definition of social expectations with a rich temporal structure. However, despite this expressiveness, the conformance of sequences of observed events with a set of rules can be performed at run time using the technique of formula progression from the AI planner TLPlan.

I will also compare hyMITL+- with other approaches to modelling social expectations and norms, and discuss practical issues in the use of the language.

Guido Governatori, University of Queensland, The cost of social agents

We follow the BOID (Belief, Obligation, Intention, Desire) architecture to describe agents and agent types in Defeasible Logic. We argue that the introduction of obligations can provide a new reading of the concepts of intention and intentionality. Then we examine the notion of social agent (i.e., an agent where obligations prevail over intentions) and discuss some computational and philosophical issues related to it. We show that the notion of social agent either requires more complex computations or has some philosophical drawbacks.

Katarina Britz, Johannes Heidema, and Willem Labuschagne, University of South Africa and University of Otago, Abduction and dual defeasible entailment

This paper explores the neglected area of duality in defeasible entailment relations, and demonstrates its relevance for BDI agents.

An agent's cognition is captured in logic by entailment. Entailment is a relation between information-bearers X and Y induced by a relation E between representations P(X) and Q(Y) of X and Y. The relation E is chosen so as to embody some form of the idea that antecedent X lends justification for belief in succedent Y .

In the familiar case of classical entailment, X |= Y iff P(X)EQ(Y) where P(X) = Mod(X), the set of models of X, and Q(Y) = Mod(Y), while the relation E is set-theoretical inclusion. Truth is preserved because Y introduces no information beyond that contained in X.

In supraclassical entailment we allow more pairs (X, Y) into the entailment relation than can be justified classically, permitting Y to contain new information, and the result is an entailment relation that is defeasible; it may have a counterexample, an (unexpected) state in which X is true but Y is false.

One of the best-studied frameworks for defeasible entailment is nonmonotonic logic with semantics co-determined by a preference order in the manner first elucidated by Shoham and then refined by Kraus, Lehmann, and Magidor. Here the classical entailment relation X |= Y is expanded to a larger set of pairs (X, Y) by shrinking P(X) to the smaller set of most preferred models of X, capable of fitting into more different sets Q(Y) = Mod(Y). Now X |~ Y iff P(X) is a subset of or equal to Mod(Y). The canonical Tweety example illustrates that |~ formalises what psychologists call categorical induction, i.e. the agent's prediction that since an item belongs to a category (e.g. Bird) it will have a feature (e.g. Fly) possessed by typical members.

We shall investigate the dual defeasible entailment relation |~*, defined by taking P(X) = Mod(X), E equals the subset relation, and dilating Q(Y) to comprise all but the most preferred nonmodels of Y. The properties of |~ and |~* form an elegant contrast, and moreover cast light on the relationship between induction and abduction.

Intuitively, abduction involves the generation of explanatory hypotheses. What counts as an explanation of Y? We propose that X potentially explains Y iff no model of X is a typical model of ~Y. Now |~* formalises abduction because we may read X |~* Y as 'X potentially explains Y'. We compare this formalisation to those of Hintikka, Aliseda, Magnani, and Gabbay.

Pietro Abate and Rajeev Goré, Australian National University, A Cut-free Tableau Calculus for the Logic of Common Knowledge

Reasoning about knowledge, in particular about the knowledge of agents who reason about the world and each other's knowledge, plays an important role in several areas of computer science, philosophy, game theory and many other fields. The notion of Common Knowledge (CK), where everybody knows, every- one knows that everyone knows, etc has also proved fundamental in the analysis of interacting groups of agents (see [FHMV95] for an extensive overview).

We focus on the development of a cut-free finitary tableau calculus with histories for n-agent modal logics with common knowledge (LCK). Thus, we get a proof system where proof-search becomes feasible and we lay the basis for developing a uniform framework for the treatment of the family of logics of common knowledge. Our calculus gives a single-pass decision procedure which is space-optimal and uses histories and variables [Gor99, HSZ96, Sch98].

The modularity of the system makes it easy to extend it to the logic of common knowledge based upon T , S4 and S5. An implementation of LCK with two agents using the tableaux workbench (TWB) [AG03] is available at and can be queried over the Internet.


[AG03] P Abate and R Goré. System description: The tableaux workbench (TWB). In TABLEAUX, LNCS, Springer, 2003.

[FHMV95] R. Fagin, J. Halpern, Y. Moses, and M. Vardi. Reasoning about Knowledge. The MIT Press, 1995.

[Gor99] R Goré. Chapter 6: Tableau methods for modal and temporal logics. In Handbook of Tableau Methods, pages 297-396. Kluwer, 1999.

[HSZ96] A Heuerding, M Seyfried, and H Zimmermann. Efficient loop-check for backward proof search in some non-classical propositional logics. In Proc. TABLEAUX'96, pages 210-225, 1996.

[Sch98] S Schwendimann. A new one-pass tableau calculus for PLTL. In TABLEAUX'98, LNCS 1397:277-291. Springer, 1998.

Rod Girle, Auckland University, Dialogue Logic and Disaster: the original idea

The original idea, which led to Robo-Cup, was that teams of small robots be used in disaster situations for assessment, to aid in relief and rescue. The originators of this humanitarian ideal then looked for some popular activity which would arouse interest in robotic teams and assist in raising money for the project. Team sport was seen as an ideal activity, and robo-soccer was settled on.

Team sport requires interactive reasoning of the kind which leads to team activity. The usual theoretical approach to reasoning and interaction is based on the knowledge and beliefs of team members, and what they know and believe about each others knowledge and belief relevant to the practical outcome of playing a game. This approach is the dynamic epistemic and doxastic approach. This paper will propose an alternative approach through the theoretical base of dialogue logic, and in particular, the logic of command dialogue.

There are certain preliminary issues which need to be discussed before going on to consider the logic of command dialogue. The issues concern the analogies and dysanalogies between team sports and disaster aid and rescue teamwork. The contrasts between skills and knowledge are of central importance. These can be seen in terms of the common terminological contrast between 'knowing that' and 'knowing how.' The contrast between deliberative and 'hot' action is also important in this context.

There are formal systems for command dialogue. These can all loosely be called logics, although they do not conform to the usual expectations about the requirements for a logic. A system of multiple authority command dialogue will be discussed. Consideration will be given to the extent to which the system addresses the issues raised above.

In particular there will be discussion of the object or content of command. Segerberg's dynamic logic of command will be discussed. Examples and issues which may well arise in the course of team action will be used to show how a command dialogue would both deal with such example and issues, and to what extent a logic of command dialogue is satisfactory.

Hans van Ditmarsch, University of Otago, Arbitrary announcement logic

In collaboration with Philippe Balbiani (Institut de Recherche en Informatique de Toulouse - IRIT), Alexandru Baltag (Oxford University), Andreas Herzig (IRIT), Tomohiro Hoshi (Stanford University) and Tiago de Lima (IRIT)

Public announcement logic is an extension of multi-agent epistemic logic with dynamic operators to model the informational consequences of announcements to the entire group of agents. We propose an extension of public announcement logic, called arbitrary announcement logic, with a dynamic modal operator that expresses what is true after arbitrary announcements. Intuitively, [] phi expresses that phi is true after an arbitrary announcement psi.

For an example, let us work our way upwards from a concrete announcement. When an atomic proposition p is true, it becomes known by announcing it. Formally, in public announcement logic, p & [p] K p. This is equivalent to

which stands for 'the announcement of p can be made and after that the agent knows p'. More abstractly this means that there is a announcement psi, namely psi = p, that makes the agent know p, slightly more formal: We introduce a dynamic modal operator that expresses exactly that: Obviously, the truth of this expression depends on the model: p has to be true. In case p is false, we can achieve <> K ~p instead. The formula <> (K p v K ~p) is valid.

back to LAMAS main page