Skip to main content

2006 | Buch

Computational Logic in Multi-Agent Systems

6th International Workshop, CLIMA VI, London, UK, June 27-29, 2005, Revised Selected and Invited Papers

herausgegeben von: Francesca Toni, Paolo Torroni

Verlag: Springer Berlin Heidelberg

Buchreihe : Lecture Notes in Computer Science

insite
SUCHEN

Inhaltsverzeichnis

Frontmatter

The Logical Way to Be Artificially Intelligent

The Logical Way to Be Artificially Intelligent
Abstract
Abductive logic programming (ALP) can be used to model reactive, proactive and pre-active thinking in intelligent agents. Reactive thinking assimilates observations of changes in the environment, whereas proactive thinking reduces goals to sub-goals and ultimately to candidate actions. Pre-active thinking generates logical consequences of candidate actions, to help in deciding between the alternatives. These different ways of thinking are compatible with any way of deciding between alternatives, including the use of both decision theory and heuristics.
The different forms of thinking can be performed as they are needed, or they can be performed in advance, transforming high-level goals and beliefs into lower-level condition-action rule form, which can be implemented in neural networks. Moreover, the higher-level and lower-level representations can operate in tandem, as they do in dual-process models of thinking. In dual process models, intuitive processes form judgements rapidly, sub-consciously and in parallel, while deliberative processes form and monitor judgements slowly, consciously and serially.
ALP used in this way can not only provide a framework for constructing artificial agents, but can also be used as a cognitive model of human agents. As a cognitive model, it combines both a descriptive model of how humans actually think with a normative model of humans can think more effectively.
Robert Kowalski

Foundational Aspects of Agency

Ability in a Multi-agent Context: A Model in the Situation Calculus
Abstract
This paper studies the notion of ability and its relation with the notion of action in a multi-agent context. It introduces the distinction between two notions respectively called “theoretical ability” and “ability”. The main contribution of this paper is a model of these notions in the Situation Calculus.
Laurence Cholvy, Christophe Garion, Claire Saurel
Reasoning About Epistemic States of Agents by Modal Logic Programming
Abstract
Modal logic programming is one of appropriate approaches to deal with reasoning about epistemic states of agents. We specify here the least model semantics, the fixpoint semantics, and an SLD-resolution calculus for modal logic programs in the multimodal logic KD4I g 5 a , which is intended for reasoning about belief and common belief of agents. We prove that the presented SLD-resolution calculus is sound and complete. We also present a formalization of the wise men puzzle using a modal logic program in KD4I g 5 a . This shows that it is worth to study modal logic programming for multi-agent systems.
Linh Anh Nguyen
Strongly Complete Axiomatizations of “Knowing at Most” in Syntactic Structures
Abstract
Syntactic structures based on standard syntactic assignments model knowledge directly rather than as truth in all possible worlds as in modal epistemic logic, by assigning arbitrary truth values to atomic epistemic formulae. This approach to epistemic logic is very general and is used in several logical frameworks modeling multi-agent systems, but has no interesting logical properties — partly because the standard logical language is too weak to express properties of such structures. In this paper we extend the logical language with a new operator used to represent the proposition that an agent “knows at most” a given finite set of formulae and study the problem of strongly complete axiomatization of syntactic structures in this language. Since the logic is not semantically compact, a strongly complete finitary axiomatization is impossible. Instead we present, first, a strongly complete infinitary system, and, second, a strongly complete finitary system for a slightly weaker variant of the language.
Thomas Ågotnes, Michal Walicki
Logical Spaces in Multi-agent Only Knowing Systems
Abstract
We present a weak multi-agent system of Only knowing and an analysis of the logical spaces that can be defined in it. The logic complements the approach to generalizing Levesque‘s All I Know system made by Halpern and Lakemeyer. A novel feature of our approach is that the logic is defined entirely at the object level with no reference to meta-concepts in the definition of the axiom system. We show that the logic of Halpern and Lakemeyer can be encoded in our system in the form of a particular logical space.
Bjørnar Solhaug, Arild Waaler
Trustworthiness by Default
Abstract
We present a framework for reasoning about information sources, with application to conflict resolution and belief formation at various degrees of reliability. On the basis of an assignment of relative trustworthiness to sets of information sources, a lattice of degrees of trustworthiness is constructed; from this, a priority structure is derived and applied to the problem of forming the right opinion. Consolidated with an unquestioned knowledge base, this provides an unambiguous account of what an agent should believe, conditionally on which information sources are trusted. Applications in multi-agent doxastic logic are sketched.
Johan W. Klüwer, Arild Waaler
Decision Procedure for a Fragment of Mutual Belief Logic with Quantified Agent Variables
Abstract
A deduction-based decision procedure is presented for a fragment of mutual belief logic with quantified agent variables (MBQL). The language of MBQL contains belief, everybody believes and mutual belief modalities, variables and constants for agents. The language of MBQL is convenient to describe the properties of rational agents when the number of agents is not known in advance. On the other hand, even if the exact number of agents is known, a language with quantified agent variables allows us to use more compact expressions. For the MBQL a sequent calculus MBQ * with invertible (in some sense) rules is proposed. The presented decision procedure is realized by means of the calculus MBQ * that allows us to simplify a procedure of loop-check sharply. For a fragment of MBQL (without positive occurrences of mutual belief modality), the loop-check-free sequent calculus is proposed. To this end, special rules for belief and everybody believes modalities (introducing marked modalities and indices) and special sequents serving as a termination criterion for non-derivability are introduced. For sequents containing positive occurrences of mutual belief modality sequents of special shape are used to specialize a loop-check and to find non-logical (loop-type) axioms.
Regimantas Pliuškevičius, Aida Pliuškevičienė

Agent Programming

Implementing Temporal Logics: Tools for Execution and Proof
Abstract
In this article I will present an overview of a selection of tools for execution and proof based on temporal logic, and outline both the general techniques used and problems encountered in implementing them. This selection is quite subjective, mainly concerning work that has involved researchers I have collaborated with at Liverpool (and, previously, Manchester). The tools considered will mainly be theorem-provers and (logic-based) agent programming languages
Michael Fisher
BDI Agent Programming in AgentSpeak Using Jason
Abstract
This paper is based on the tutorial given as part of the tutorial programme of CLIMA-VI. The tutorial aimed at giving an overview of the various features available in Jason, a multi-agent systems development platform that is based on an interpreter for an extended version of AgentSpeak. The BDI architecture is the best known and most studied architecture for cognitive agents, and AgentSpeak is an elegant, logic-based programming language inspired by the BDI architecture.
Rafael H. Bordini, Jomi F. Hübner
Using the KGP Model of Agency to Design Applications
Abstract
This paper is a tutorial describing the main features of the KGP (Knowledge-Goals-Plan) model of agency and giving user guidance on how the model can be used to develop applications. The KGP model is based on computational logic. It consists of an abstract component, a computational component and an implementation. This paper concentrates on the abstract component, which consists of formal specifications of a number of different modules, including the knowledge bases, capabilities, transitions and control. For each of these we summarise what is provided by the model, and through the platform implementing the model, and what is left to the users to specify according to the requirements of the applications for which they wish to use the KGP model to design agents.
Fariba Sadri
Multi-threaded Communicating Agents in Qu-Prolog
Abstract
In this tutorial paper we summarise the key features of the multi-threaded Qu-Prolog language for implementing multi-threaded communicating agent applications. Internal threads of an agent communicate using the shared dynamic database used as a generalisation of Linda tuple store. Threads in different agents, perhaps on different hosts, communicate using either a thread-to-thread store and forward communication system, or by a publish and subscribe mechanism in which messages are routed to their destinations based on content test subscriptions.
We illustrate the features using an auction house application. This is fully distributed with multiple auctioneers and bidders which participate in simultaneous auctions. The application makes essential use of the three forms of inter-thread communication of Qu-Prolog. The agent bidding behaviour is specified graphically as a finite state automaton and its implementation is essentially the execution of its state transition function. The paper assumes familiarity with Prolog and the basic concepts of multi-agent systems.
Keith L. Clark, Peter J. Robinson, Silvana Zappacosta Amboldi
Variety of Behaviours Through Profiles in Logic-Based Agents
Abstract
In an earlier paper we [6] presented a declarative approach for agent control. In that work we described how control can be specified in terms of cycle theories, which define declaratively the possible alternative behaviours of agents, depending on their internal state and (their perception of) the external environment in which they are situated. This form of control has been adopted for logic-based KGP agents [8, 2]. In this paper we show how using this form of control specification we can specify different profiles of agents, how they would vary the behaviour of agents and what advantages they have with respect to factors in the application and in the environment, such as time-criticality.
Fariba Sadri, Francesca Toni
Contract-Related Agents
Abstract
We propose a simple event calculus representation of contracts and a reactive belief-desire-intention agent architecture to enable the monitoring and execution of contract terms and conditions. We use the event calculus to deduce current and past obligations, obligation fulfilment and violation. By associating meta-information with the contracts, the agent is able to select which of its contracts with other agents are relevant to solving its goals by outsourcing. The agent is able to handle an extendable set of contract types such as standing contracts, purchase contracts and service contracts without the need for a first-principles planner.
John Knottenbelt, Keith Clark

Agent Interaction and Normative Systems

Specification and Verification of Agent Interaction Using Abductive Reasoning
Abstract
Amongst several fundamental aspects in multi-agent systems design, the definition of the agent interaction space is of the utmost importance. The specification of the agent interaction has several facets: syntax, semantics, and compliance verification.
In an open society, heterogenous agents can participate without showing any credentials. Accessing their internals or their knowledge bases is typically impossible, thus it is impossible to prove a priori that agents will indeed behave according to the society rules.
Within the SOCS (Societies Of ComputeeS) project, a language based on abductive semantics has been proposed as a mean to define interactions in open societies. The proposed language allows the designer to define open, extensible and not over-constrained protocols. Beside the definition language, a software tool has been developed with the purpose of verifying at execution time if the agents behave correctly with respect to the defined protocols.
This paper provides a tutorial overview of the theory and of the tools the SOCS project provided to design, define and test agent interaction protocols.
Federico Chesani, Marco Gavanelli, Marco Alberti, Evelina Lamma, Paola Mello, Paolo Torroni
Verification of Protocol Conformance and Agent Interoperability
Abstract
In open multi-agent systems agent interaction is usually ruled by public protocols defining the rules the agents should respect in message exchanging. The respect of such rules guarantees interoperability. Given two agents that agree on using a certain protocol for their interaction, a crucial issue (known as “a priori conformance test”) is verifying if their interaction policies, i.e. the programs that encode their communicative behavior, will actually produce interactions which are conformant to the agreed protocol. An issue that is not always made clear in the existing proposals for conformance tests is whether the test preserves agents’ capability of interacting, besides certifying the legality of their possible conversations. This work proposes an approach to the verification of a priori conformance, of an agent’s conversation policy to a protocol, which is based on the theory of formal languages. The conformance test is based on the acceptance of both the policy and the protocol by a special finite state automaton and it guarantees the interoperability of agents that are individually proved conformant. Many protocols used in multi-agent systems can be expressed as finite state automata, so this approach can be applied to a wide variety of cases with the proviso that both the protocol specification and the protocol implementation can be translated into finite state automata. In this sense the approach is general. Easy applicability to the case when a logic-based language is used to implement the policies is shown by means of a concrete example, in which the language DyLOG, based on computational logic, is used.
Matteo Baldoni, Cristina Baroglio, Alberto Martelli, Viviana Patti
Contextual Terminologies
Abstract
The paper addresses the issue of contextual representations of ontologies, as it arises in the area of normative system specifications for modeling multiagent systems. To this aim, the paper proposes a formalization of a notion of contextual terminology, that is to say, a terminology holding only with respect to a specific context. The formalization is obtained by means of a formal semantics framework which enables the expressivity of common description logics to reason within contexts (intra-contextual reasoning), allowing at the same time the possibility to reason also about contexts and their interplay (inter-contextual reasoning). Using this framework, two complex scenarios are discussed in detail and formalized.
Davide Grossi, Frank Dignum, John-Jules Ch. Meyer
Constitutive Norms in the Design of Normative Multiagent Systems
Abstract
In this paper, we consider the design of normative multiagent systems composed of both constitutive and regulative norms. We analyze the properties of constitutive norms, in particular their lack of reflexivity, and the trade-off between constitutive and regulative norms in the design of normative systems. As methodology we use the metaphor of describing social entities as agents and of attributing them mental attitudes. In this agent metaphor, regulative norms expressing obligations and permissions are modelled as goals of social entities, and constitutive norms expressing “counts-as” relations are their beliefs.
Guido Boella, Leendert van der Torre
Combining Answer Sets of Nonmonotonic Logic Programs
Abstract
This paper studies compositional semantics of nonmonotonic logic programs. We suppose the answer set semantics of extended disjunctive programs and consider the following problem. Given two programs P 1 and P 2, which have the sets of answer sets AS(P 1) and AS(P 2), respectively; find a program Q which has answer sets as minimal sets ST for S from AS(P 1) and T from AS(P 2). The program Q combines answer sets of P 1 and P 2, and provides a compositional semantics of two programs. Such program composition has application to coordinating knowledge bases in multi-agent environments. We provide methods for computing program composition and discuss their properties.
Chiaki Sakama, Katsumi Inoue
Speculative Constraint Processing with Iterative Revision for Disjunctive Answers
Abstract
In multi-agents systems, incompleteness, due to either communication failure or response delay, is a major problem to handle. To face incompleteness, frameworks for speculative computation were proposed (see references [5, 6, 7]). The idea developed in such frameworks is to allow the asking agent, while waiting for the slave agents to reply, to reason using default beliefs until replies are sent.
In particular, K. Satoh and K. Yamamoto [7] proposed a framework that allows an agent not only to perform speculative computation, but also to accept iterative answer revision for yes/no questions. In this paper, we present an extension of the framework for more general types of questions using constraint logic programming (CLP).
Martine Ceberio, Hiroshi Hosobe, Ken Satoh
Intention Recognition in the Situation Calculus and Probability Theory Frameworks
Abstract
A method to recognize agent’s intentions is presented in a framework that combines the logic of Situation Calculus and Probability Theory. The method is restricted to contexts where the agent only performs procedures in a given library of procedures, and where the system that intends to recognize the agent’s intentions has a complete knowledge of the actions performed by the agent.
An original aspect is that the procedures are defined for human agents and not for artificial agents. The consequence is that the procedures may offer the possibility to do any kind of actions between two given actions, and they also may forbid to perform some specific actions. Then, the problem is different and more complex than the standard problem of plan recognition.
To select the procedures that partially match the observations we consider the procedures that have the greatest estimated probability. This estimation is based on the application of Bayes’ theorem and on specific heuristics. These heuristics depend on the history and not just on the last observation.
A PROLOG prototype of the presented method has been implemented.
Robert Demolombe, Ana Mara Otermin Fernandez

The First CLIMA Contest

The First Contest on Multi-agent Systems Based on Computational Logic
Abstract
This is a short report about the first contest of Multi-Agent Systems (MASs) that are based on computational logic. The CLIMA workshop series (which started in 1999) is a forum to discuss techniques, based on computational logic, for representing, programming, and reasoning about Multi-Agent Systems in a formal way. Now in its seventh year, it was felt that organising a competition for evaluating MASs based on computational logic was appropriate. The authors took on this task, which turned out to be quite difficult under the given time frame. We believe that this competition is a first (modest) step towards (1) collecting important benchmarks, (2) identifying advantages/shortcomings and, finally, (3) advertising the use of Computational Logic to the broader MAS audience, and foster integration of Computational Logic into existing agent-oriented software engineering frameworks.
Mehdi Dastani, Jürgen Dix, Peter Novak
Implementing Pheromone-Based, Negotiating Forager Agents
Abstract
We describe an implementation of distributed, multi-threaded BDI-style [RG95] agents cooperating efficiently in a foraging scenario. Using ant-style pheromone trails as the basis for a pseudo-random walk procedure, they explore the world uniformly and negotiate to allocate collection and delivery tasks. Global information is disseminated via a publish/subscribe mechanism. The system is implemented using the concurrent logic programming language Qu-Prolog.
Simon Coffey, Dorian Gaertner
Extending Tropos for a Prolog Implementation: A Case Study Using the Food Collecting Agent Problem
Abstract
There is a recognized lack of Agent-Oriented Methodologies to translate a design into a computational logic implementation. In this paper we address this problem by extending Tropos, which is one of the most used methodologies to design agent systems. We show our proposal with the Food Collecting Agent Problem in which a team has to collect food in a grid-like world. Our solution includes autonomous behaviour, beliefs, multiple roles playing, communication and cooperation. The main contribution is the proposal to generate a Prolog implementation from a Tropos design by first extending the Tropos detailed design and second illustrating how to get a set of Prolog clauses for this design. In addition we show a performance evaluation of our Prolog implementation which confirms that our solution for the case study is effective and allows a simple configuration of the resulting program.
Carlos Cares, Xavier Franch, Enric Mayol
Reactive Food Gathering
Abstract
This short paper describes a simple agent system aimed at addressing the food gathering problem set for the 2005 CLIMA contest. Our system is implemented as a collection of reactive agents which dynamically switch between a number of behaviours depending on interaction with their environment. Our agents maintain no internal representation of their environment and operate purely in response to their immediate surroundings. The agents collectively map the environment co-operating indirectly via environmental markers and they use these markers to assist them in locating the depot when they discover food. The required behaviour emerges from the interaction between agents and the marked environment. Despite the simplicity of the agents and their behaviours formal description is difficult. We concentrate more on identifying interesting problems in characterising system exhibiting emergent behaviour and outline possible logic approaches to dealing with them.
The application (and one or two other systems addressing the same problem in a different manner) can be downloaded from: http://219.1.164.219/~robert/pwBlog/wp-content/CLIMAbuild.zip
Robert Logie, Jon G. Hall, Kevin G. Waugh
Strategies for Multi-agent Coordination in a Grid World Using Petri Nets
Abstract
In this work, we describe strategies for multi-agent coordination, where adequate coordination means a system performance increase. In the main strategy, when an agent cannot perform an action, for whatever reason, it chooses the agent more capable in the environment to execute this action. All the specification of the multi-agent system, from the social strategy to the actions in the environment, is made using a particular Petri Net model. The results show the strategy efficacy especially when the environment increases the necessity for a reaction.
Eder Mateus Nunes Gonçalves, Guilherme Bittencourt

Project Report

Multi-agent Systems in Computational Logic: Challenges and Outcomes of the SOCS Project
Abstract
The SOCS project (A computational logic model for the description, analysis and verification of global and open SOcieties of heterogeneous ComputeeS), funded by the European Commission under the Fifth Framework, Future and Emerging Technologies programme, has been one of the main sponsors of CLIMA VI. This short article outlines the project’s main challenges and its main outcomes.
Francesca Toni
Backmatter
Metadaten
Titel
Computational Logic in Multi-Agent Systems
herausgegeben von
Francesca Toni
Paolo Torroni
Copyright-Jahr
2006
Verlag
Springer Berlin Heidelberg
Electronic ISBN
978-3-540-33997-7
Print ISBN
978-3-540-33996-0
DOI
https://doi.org/10.1007/11750734