On the Semantics of Deliberation in IndiGolog — from Theory to Implementation

We develop an account of the kind of deliberation that an agent that is doing planning or executing high-level programs under incomplete information must be able to perform. The deliberator's job is to produce a kind of plan that does not itself require deliberation to interpret. We characterize these as epistemically feasible programs: programs for which the executing agent, at every stage of execution, by virtue of what it knew initially and the subsequent readings of its sensors, always knows what step to take next towards the goal of completing the entire program. We formalize this notion and characterize deliberation in the situation calculus based IndiGolog agent programming language in terms of it. We also show that for certain classes of problems, which correspond to those with bounded solutions and those with solutions without sensing, the search for epistemically feasible programs can be limited to programs of a simple syntactic form. Finally, we discuss implementation issues and execution monitoring and replanning too.     

Model Checking for Combined Logics with an Application to Mobile Systems

In this paper, we develop model checking procedures for three ways of combining (temporal) logics: temporalization, independent combination, and join. We prove that they are terminating, sound, and complete, we analyze their computational complexity, and we report on experiments with implementations. We take a close look at mobile systems and show how the proposed combined model checking framework can be successfully applied to the specification and verification of their properties.     

Certifying assembly programs with trails

In this paper, we introduce a new way of certifying assembly programs. Unlike previous program logics, we extract the control-flow information from the code and generate an intermediate trail between the specification and the real code. Trails are auxiliary specifications and treated as modules in the certification process. We define a simple modular program logic called trail-based certified assembly programming (TCAP) to certify and link different parts of a program using the corresponding trails. Because the control flow information in trails is explicit, the rules are easier to design. We show that our logic is powerful enough to prove partial correctness of assembly programs with features including stack-based abstractions and self-modifying code.We also provide a semantics for TCAP and prove that the logic is sound with respect to the semantics.     

Toward a programming theory for rational agents

An important problem in agent verification is a lack of proper understanding of the relation between agent programs on the one hand and agent logics on the other. Understanding this relation would help to establish that an agent programming language is both conceptually well-founded and well-behaved, as well as yield a way to reason about agent programs by means of agent logics. As a step toward bridging this gap, we study several issues that need to be resolved in order to establish a precise mathematical relation between a modal agent logic and an agent programming language specified by means of an operational semantics. In this paper, we present an agent programming theory that provides both an agent programming language as well as a corresponding agent verification logic to verify agent programs. The theory is developed in stages to show, first, how a modal semantics can be grounded in a state-based semantics, and, second, how denotational semantics can be used to define the mathematical relation connecting the logic and agent programming language. Additionally, it is shown how to integrate declarative goals and add precompiled plans to the programming theory. In particular, we discuss the use of the concept of higher-order goals in our theory. Other issues such as a complete axiomatization and the complexity of decision procedures for the verification logic are not the focus of this paper and remain for future investigation. Part of this research was carried out while the first author was affiliated with the Nijmegen Institute for Cognition and Information, Radboud University Nijmegen.     

Tableau Methods for a Logic with Term Declarations

We study free variable tableau methods for logics with term declarations. We show how to define a substitutivity rule preserving the soundness of the tableaux and we prove that some other attempts lead to unsound systems. Based on this rule, we define a sound and complete free variable tableau system and we show how to restrict its application to close branches by defining a sorted unification calculus.     

Distributed Knowledge Justification Logics

Justification logics are a family of modal epistemic logics which enables us to reasoning about justifications and evidences. In this paper, we introduce evidence-based multi-agent distributed knowledge logics, called distributed knowledge justification logics. The language of our justification logics contain evidence-based knowledge operators for individual agents and for distributed knowledge , which are interpreted respectively as “t is a justification that agent i accepts for F”, and “t is a justification that all agents accept for F if they combine their knowledge and justifications”. We study basic properties of our logics and prove the conservativity of distributed knowledge justification logics over multi-agent justification logics. We present Kripke style models, pseudo-Fitting and Fitting models, as well as Mkrtychev models (single world Fitting models) and prove soundness and completeness theorems. We also find a class of Fitting models which satisfies the principle of full communication. Finally, we establish the realization theorem, which states that distributed knowledge justification logics can be embedded into the modal distributed knowledge logics, and vise versa.     

Contextual Deontic Logic: Normative Agents, Violations and Independence

In this paper we discuss when and how to use deontic logic in multi-agent systems. Our central question is how to proceed once a norm has been violated or defeated, a key issue of deontic logic applications in multi-agent systems. To bridge the logical analysis of norms in philosophy with applications in agent theory, we propose a practical approach based on violation contexts and independence statements. In particular, we introduce a combination of two traditional deontic logics, which we extend with so-called deontic and factual independence assumptions. We show how different notions of violability and defeasibility can be encoded in the logic by defining different ways in which independence assumptions are derived from the explicit manner of presentation. We also show how our approach can be used to give a new analysis of several notorious paradoxes of deontic logic.     

Outlier detection using default reasoning

Default logics are usually used to describe the regular behavior and normal properties of domain elements. In this paper we suggest, conversely, that the framework of default logics can be exploited for detecting outliers. Outliers are observations expressed by sets of literals that feature unexpected semantical characteristics. These sets of literals are selected among those explicitly embodied in the given knowledge base. Hence, essentially we perceive outlier detection as a knowledge discovery technique. This paper defines the notion of outlier in two related formalisms for specifying defaults: Reiter's default logic and extended disjunctive logic programs. For each of the two formalisms, we show that finding outliers is quite complex. Indeed, we prove that several versions of the outlier detection problem lie over the second level of the polynomial hierarchy. We believe that a thorough complexity analysis, as done here, is a useful preliminary step towards developing effective heuristics and exploring tractable subsets of outlier detection problems.     

Argumentative Agent Deliberation, Roles and Context

This paper presents an argumentation based framework to support an agent's deliberation process for drawing conclusions under a given policy. The argumentative policy of the agent is able to take into account the roles agents can have within a context pertaining to an environment of interaction. The framework uses roles and context to define policy preferences at different levels of deliberation allowing a modular representation of the agent's knowledge that avoids the need for explicit qualification of the agent's decision rules. We also employ a simple form of abduction to deal with the incompleteness and evolving nature of the agent's knowledge of the external environment and illustrate how an agent's self deliberation can affect the mode of interaction between agents. The high degree of modularity of the framework gives it a simple computational model in which the agent's deliberation can be naturally implemented.     

Endogenous Neighborhood Selection and the Attainment of Cooperation in a Spatial Prisoner’s Dilemma Game

There is a large literature in economics and elsewhere on the emergence and evolution of cooperation in the repeated Prisoner’s Dilemma. Recently this literature has expanded to include games in a setting where agents play only with local neighbors in a specified geography. In this paper we explore how the ability of agents to move and choose new locations and new neighbors influences the emergence of cooperation. First, we explore the dynamics of cooperation by investigating agent strategies that yield Markov transition probabilities. We show how different agent strategies yield different Markov chains which generate different asymptotic behaviors in regard to the attainment of cooperation. Second, we investigate how agent movement affects the attainment of cooperation in various networks using agent-based simulations. We show how network structure and density can affect cooperation with and without agent movement.     

A hoare-like proof system for analysing the computation time of programs

Versions of Hoare logic have been introduced to prove partial and total correctness properties of programs. In this paper it is shown how a Hoare-like proof system for while programs may be extended to prove properties of the computation time as well. It should be stressed that the system does not require the programs to be modified by inserting explicit operations upon a clock variable. We generalize the notions of arithmetically sound and complete and show that the proof system satisfies these. Also we derive formal rules corresponding to the informal rules for determining the computation time of while programs. The applicability of the proof system is illustrated by an example, the bubble sorting algorithm.     

Reasoning about plan revision in BDI agent programs

Facilities for handling plan execution failures are essential for agents which must cope with the effects of nondeterministic actions, and some form of failure handling can be found in most mature agent programming languages and platforms. While such features simplify the development of more robust agents, they make it hard to reason about the execution of agent programs, e.g., to verify their correctness. In this paper, we present an approach to the verification of agent programs which admit exceptional executions. We consider executions of the BDI-based agent programming language 3APL in which plans containing non-executable actions can be revised using plan revision rules, and present a logic for reasoning about normal and exceptional executions of 3APL programs. We provide a complete axiomatization for the logic and, using a simple example, show how to express properties of 3APL programs as formulas of the logic.     

A generic complete dynamic logic for reasoning about purity and effects

For a number of programming languages, among them Eiffel, C, Java, and Ruby, Hoare-style logics and dynamic logics have been developed. In these logics, pre- and postconditions are typically formulated using potentially effectful programs. In order to ensure that these pre- and postconditions behave like logical formulae (that is, enjoy some kind of referential transparency), a notion of purity is needed. Here, we introduce a generic framework for reasoning about purity and effects. Effects are modelled abstractly and axiomatically, using Moggi’s idea of encapsulation of effects as monads. We introduce a dynamic logic (from which, as usual, a Hoare logic can be derived) whose logical formulae are pure programs in a strong sense. We formulate a set of proof rules for this logic, and prove it to be complete with respect to a categorical semantics. Using dynamic logic, we then develop a relaxed notion of purity which allows for observationally neutral effects such writing on newly allocated memory.     

Model checking agent programming languages

In this paper we describe a verification system for multi-agent programs. This is the first comprehensive approach to the verification of programs developed using programming languages based on the BDI (belief-desire-intention) model of agency. In particular, we have developed a specific layer of abstraction, sitting between the underlying verification system and the agent programming language, that maps the semantics of agent programs into the relevant model-checking framework. Crucially, this abstraction layer is both flexible and extensible; not only can a variety of different agent programming languages be implemented and verified, but even heterogeneous multi-agent programs can be captured semantically. In addition to describing this layer, and the semantic mapping inherent within it, we describe how the underlying model-checker is driven and how agent properties are checked. We also present several examples showing how the system can be used. As this is the first system of its kind, it is relatively slow, so we also indicate further work that needs to be tackled to improve performance.     

Reasoning about Minimal Knowledge in Nonmonotonic Modal Logics

We study the problem of embedding Halpern and Moses's modal logic of minimal knowledge states into two families of modal formalism for nonmonotonic reasoning, McDermott and Doyle's nonmonotonic modal logics and ground nonmonotonic modal logics. First, we prove that Halpern and Moses's logic can be embedded into all ground logics; moreover, the translation employed allows for establishing a lower bound (3p) for the problem of skeptical reasoning in all ground logics. Then, we show a translation of Halpern and Moses's logic into a significant subset of McDermott and Doyle's formalisms. Such a translation both indicates the ability of Halpern and Moses's logic of expressing minimal knowledge states in a more compact way than McDermott and Doyle's logics, and allows for a comparison of the epistemological properties of such nonmonotonic modal formalisms.     

Concurrent imitation dynamics in congestion games

Imitating successful behavior is a natural and frequently applied approach when facing complex decision problems. In this paper, we design protocols for distributed latency minimization in atomic congestion games based on imitation. We propose to study concurrent dynamics that emerge when each agent samples another agent and possibly imitates this agent’s strategy if the anticipated latency gain is sufficiently large. Our focus is on convergence properties. We show convergence in a monotonic fashion to stable states, in which none of the agents can improve their latency by imitating others. As our main result, we show rapid convergence to approximate equilibria, in which only a small fraction of agents sustains a latency significantly above or below average. Imitation dynamics behave like an FPTAS, and the convergence time depends only logarithmically on the number of agents. Imitation processes cannot discover unused strategies, and strategies may become extinct with non-zero probability. For singleton games we show that the probability of this event occurring is negligible. Additionally, we prove that the social cost of a stable state reached by our dynamics is not much worse than an optimal state in singleton games with linear latency functions. We concentrate on the case of symmetric network congestion games, but our results do not use the network structure and continue to hold accordingly for general symmetric games. They even apply to asymmetric games when agents sample within the set of agents with the same strategy space. Finally, we discuss how the protocol can be extended such that, in the long run, dynamics converge to a pure Nash equilibrium.     

Semantic forgetting in answer set programming

The notion of forgetting, also known as variable elimination, has been investigated extensively in the context of classical logic, but less so in (nonmonotonic) logic programming and nonmonotonic reasoning. The few approaches that exist are based on syntactic modifications of a program at hand. In this paper, we establish a declarative theory of forgetting for disjunctive logic programs under answer set semantics that is fully based on semantic grounds. The suitability of this theory is justified by a number of desirable properties. In particular, one of our results shows that our notion of forgetting can be entirely captured by classical forgetting. We present several algorithms for computing a representation of the result of forgetting, and provide a characterization of the computational complexity of reasoning from a logic program under forgetting. As applications of our approach, we present a fairly general framework for resolving conflicts in inconsistent knowledge bases that are represented by disjunctive logic programs, and we show how the semantics of inheritance logic programs and update logic programs from the literature can be characterized through forgetting. The basic idea of the conflict resolution framework is to weaken the preferences of each agent by forgetting certain knowledge that causes inconsistency. In particular, we show how to use the notion of forgetting to provide an elegant solution for preference elicitation in disjunctive logic programming.