The dynamics of default reasoning

In this paper we study default reasoning from a dynamic, agent-oriented, semantics-based point of view. In a formal framework used to specify and to reason about rational agents, we introduce actions that model the (attempted) jumping to conclusions that is a fundamental part of reasoning by default. Application of such an action consists of three parts. First it is checked whether the formula that the agent tries to jump to is a default, thereafter it is checked whether the default formula can consistently be incorporated by the agent, and if this is the case the formula is included in the agent's beliefs. As for all actions in our framework, we define the ability and opportunity of agents to apply these actions, and the states of affairs following application. To formalise formulae being defaults, we introduce the modality of common possibility. This modality is related to, but not reducible to, the notions of common knowledge and ‘everybody knows’-knowledge. To model the qualitative difference that exists between hard, factual knowledge and beliefs derived by default, we employ different modalities to represent these concepts, thus combining knowledge, beliefs, and defaults in one framework. Based on the concepts used to model the default reasoning of agents, we look into the dynamics of the supernormal fragment of default logic. We show in particular that by sequences of jumps to conclusions agents can end up with extensions in the sense of default logic of their belief.     

具有可信度的主体信念

本文提出了一种基于可信度逻辑的主体信念程度描述方法，这种方法通过定义信念的可信度描述主体信念的不确定性，允许相互矛盾的主体信念同时存在，并给出了可信度的计算方法与推理规则。信念修正和更新时，根据主体不同的性格采取不同的选择倾向，本文提出的“必要时修正”方法具有很高的效率和实用性。本文选择基于区间的时间逻逻辑描述主体信念中的时间概念，为涉及到大量时间段行为与操作的应用提供了一个新的信念逻辑描述方法。     

基于主Agent信念修正的推测计算及其资源协商

基于假设推理(abduction-based)的推测计算(speculative computation)是在资源信息不能及时到达时,利用缺省假设进行计算的过程.在计算过程中,如果应答和信念不一致,则主Agent将修正它的信念.为了实现目标,在有限时间内使推测计算的结果更精确,主Agent要通过协商获得尽可能多的实际信息,协商是降低决策风险的主要途径.在介绍假设推理和推测计算的基本原理的基础上,提出了基于时间约束的推测计算扩展框架、基于时间约束的进一步协商框架和基于信念修正的协商算法,并将进一步协商框架和协商算法嵌入到推测计算的过程中,在协商过程中赋予主Agent更强的信念修正能力.最后,在货物运输领域的实验中,证实了基于信念修正的推测计算的有效性.     

Default reasoning and belief revision: A syntax-independent approach

As an important variant of Reiter‘s default logic.Poole(1988) developed a nonmonotonic reasoning framework in the classical first-order language,Brewka and Nebel extended Poole‘s approach in order to enable a representation of priorities between defaults.In this paper a general framework for default reasoning is presented,which can be viewed as a generalization of the three approaches above.It is proved that the syntax-independent default reasoning in this framework is identical to the general belief revision operation introduced by Zhang et al.(1997).This esult provides a solution to the problem whether there is a correspondence between belief revision and default logic for the infinite case .As a by-product,an answer to the the question,raised by Mankinson and Gaerdenfors(1991),is also given about whether there is a counterpart contraciton in nonmonotonic logic.     

对称协调博弈问题的多智能体强化学习

针对多机器人协调问题,利用协调博弈中智能体策略相似性,提出智能体的高阶信念修正模型和学习方法PEL,使智能体站在对手角度进行换位推理,进而根据信念修正将客观观察行为和主观信念推理结合起来。证明了信念修正模型的推理置信度只在0和1两个值上调整即可协调成功。以多机器人避碰为实验背景进行仿真,表明算法比现有方法能够取得更好的协调性能。     

A Thorough Axiomatization of a Principle of Conditional Preservation in Belief Revision

Although the crucial role of if-then-conditionals for the dynamics of knowledge has been known for several decades, they do not seem to fit well in the framework of classical belief revision theory. In particular, the propositional paradigm of minimal change guiding the AGM-postulates of belief revision proved to be inadequate for preserving conditional beliefs under revision. In this paper, we present a thorough axiomatization of a principle of conditional preservation in a very general framework, considering the revision of epistemic states by sets of conditionals. This axiomatization is based on a nonstandard approach to conditionals, which focuses on their dynamic aspects, and uses the newly introduced notion of conditional valuation functions as representations of epistemic states. In this way, probabilistic revision as well as possibilistic revision and the revision of ranking functions can all be dealt with within one framework. Moreover, we show that our approach can also be applied in a merely qualitative environment, extending AGM-style revision to properly handling conditional beliefs.     

Sharing beliefs among agents with different degrees of credibility

This paper introduces an approach for sharing beliefs in collaborative multi-agent application domains where some agents can be more credible than others. In this context, we propose a formalization where every agent has its own partial order among its peers representing the credibility the agent assigns to its informants; each agent will also have a belief base where each sentence is attached with an agent identifier which represents the credibility of that sentence. We define four different forwarding criteria for computing the credibility information for a belief to be forwarded, and for determining how the receiver should handle the incoming information; the proposal considers both the sender’s and the receiver’s points of view with respect to the credibility of the source of the information.     

Active object tracking using context estimation: handling occlusions and detecting missing targets

When performing visual servoing or object tracking tasks, active sensor planning is essential to keep targets in sight or to relocate them when missing. In particular, when dealing with a known target missing from the sensor’s field of view, we propose using prior knowledge related to contextual information to estimate its possible location. To this end, this study proposes a Dynamic Bayesian Network that uses contextual information to effectively search for targets. Monte Carlo particle filtering is employed to approximate the posterior probability of the target’s state, from which uncertainty is defined. We define the robot’s utility function via information theoretic formalism as seeking the optimal action which reduces uncertainty of a task, prompting robot agents to investigate the location where the target most likely might exist. Using a context state model, we design the agent’s high-level decision framework using a Partially-Observable Markov Decision Process. Based on the estimated belief state of the context via sequential observations, the robot’s navigation actions are determined to conduct exploratory and detection tasks. By using this multi-modal context model, our agent can effectively handle basic dynamic events, such as obstruction of targets or their absence from the field of view. We implement and demonstrate these capabilities on a mobile robot in real-time.

     

Iterated belief change in the situation calculus

John McCarthy's situation calculus has left an enduring mark on artificial intelligence research. This simple yet elegant formalism for modelling and reasoning about dynamic systems is still in common use more than forty years since it was first proposed. The ability to reason about action and change has long been considered a necessary component for any intelligent system. The situation calculus and its numerous extensions as well as the many competing proposals that it has inspired deal with this problem to some extent. In this paper, we offer a new approach to belief change associated with performing actions that addresses some of the shortcomings of these approaches. In particular, our approach is based on a well-developed theory of action in the situation calculus extended to deal with belief. Moreover, by augmenting this approach with a notion of plausibility over situations, our account handles nested belief, belief introspection, mistaken belief, and handles belief revision and belief update together with iterated belief change.     

Reasoning about Actions and Planning with Preferences Using Prioritized Default Theory

This paper shows how action theories, expressed in an extended version of the language     , can be naturally encoded using Prioritized Default Theory . We also show how prioritized default theory can be extended to express preferences between rules . This extension provides a natural framework to introduce different types of preferences in action theories— preferences between actions and preferences between final states . In particular, we demonstrate how these preferences can be expressed within extended prioritized default theory. We also discuss how this framework can be implemented in terms of answer set programming.     

Iterated belief revision, revised

The AGM postulates for belief revision, augmented by the DP postulates for iterated belief revision, provide widely accepted criteria for the design of operators by which intelligent agents adapt their beliefs incrementally to new information. These postulates alone, however, are too permissive: They support operators by which all newly acquired information is canceled as soon as an agent learns a fact that contradicts some of its current beliefs. In this paper, we present a formal analysis of the deficiency of the standard postulates alone, and we show how to solve the problem by an additional postulate of independence. We give a representation theorem for this postulate and prove that it is compatible with AGM and DP.     

Belief Revision as Applied within a Descriptive Model of Jury Deliberations

Belief revision is a well-researched topic within Artificial Intelligence (AI). We argue that the new model of belief revision as discussed here is suitable for general modelling of judicial decision making, along with the extant approach as known from jury research. The new approach to belief revision is of general interest, whenever attitudes to information are to be simulated within a multi-agent environment with agents holding local beliefs yet by interacting with, and influencing, other agents who are deliberating collectively. The principle of 'priority to the incoming information', as known from AI models of belief revision, is problematic when applied to factfinding by a jury. The present approach incorporates a computable model for local belief revision, such that a principle of recoverability is adopted. By this principle, any previously held belief must belong to the current cognitive state if consistent with it. For the purposes of jury simulation such a model calls for refinement. Yet, we claim, it constitutes a valid basis for an open system where other AI functionalities (or outer stimuli) could attempt to handle other aspects of the deliberation which are more specific to legal narratives, to argumentation in court, and then to the debate among the jurors.     

Belief revision in structured probabilistic argumentation

In real-world applications, knowledge bases consisting of all the available information for a specific domain, along with the current state of affairs, will typically contain contradictory data, coming from different sources, as well as data with varying degrees of uncertainty attached. An important aspect of the effort associated with maintaining such knowledge bases is deciding what information is no longer useful; pieces of information may be outdated; may come from sources that have recently been discovered to be of low quality; or abundant evidence may be available that contradicts them. In this paper, we propose a probabilistic structured argumentation framework that arises from the extension of Presumptive Defeasible Logic Programming (PreDeLP) with probabilistic models, and argue that this formalism is capable of addressing these basic issues. The formalism is capable of handling contradictory and uncertain data, and we study non-prioritized belief revision over probabilistic PreDeLP programs that can help with knowledge-base maintenance. For belief revision, we propose a set of rationality postulates — based on well-known ones developed for classical knowledge bases — that characterize how these belief revision operations should behave, and study classes of operators along with theoretical relationships with the proposed postulates, including representation theorems stating the equivalence between classes of operators and their associated postulates. We then demonstrate how our framework can be used to address the attribution problem in cyber security/cyber warfare.     

Dynamic Epistemic Logic for Implicit and Explicit Beliefs

Epistemic logic with its possible worlds semantic model is a powerful framework that allows us to represent an agent’s information not only about propositional facts, but also about her own information. Nevertheless, agents represented in this framework are logically omniscient: their information is closed under logical consequence. This property, useful in some applications, is an unrealistic idealisation in some others. Many proposals to solve this problem focus on weakening the properties of the agent’s information, but some authors have argued that solutions of this kind are not completely adequate because they do not look at the heart of the matter: the actions that allow the agent to reach such omniscient state. Recent works have explored how acts of observation, inference, consideration and forgetting affect an agent’s implicit and explicit knowledge; the present work focuses on acts that affect an agent’s implicit and explicit beliefs. It starts by proposing a framework in which these two notions can be represented, and then it looks into their dynamics, first by reviewing the existing notion of belief revision, and then by introducing a rich framework for representing diverse forms of inference that involve both knowledge and beliefs.     

Coherence approach to logic program revision

In this paper, we present a new approach to the problem of revising extended programs; we base this approach on the coherence theory initially advocated by Gardenfors for belief revision. Our approach resolves contradiction by removing only conflicting information, not the believed source of it, and therefore, keeps information loss minimal. Furthermore, since there is no need to search for problematic assumptions, as is done in the traditional assumption-removal approach, our approach provides a skeptical revision semantics that is tractable. We define the skeptical and credulous coherence semantics and show that both semantics can be characterized in terms of the fixpoint semantics of a revised program using a simple program-revision technique. These semantics provide a suitable framework for knowledge and belief revision in the context of logic programs. Semantical properties and advantages of the proposed revision semantics are also analyzed     

基于可能回答集程序的多Agent信念协调

多Agent系统(Multi-Agent System,MAS)是人工智能领域的一个非常活跃的研究方向。在多Agent系统中,由于Agent之间信念的差异,会不可避免地造成行动冲突。Sakama等提出的严格协调方法只适用于各Agent之间有共同信念的情境,当不存在共同信念时,此协调方法无解。针对该问题,文中提出了一种基于可能回答集程序(Possibilistic Answer Set Programming,PASP)的信念协调方法。首先,针对各Agent的不同信念集,基于加权定量的方法计算PASP的回答集相对Agent信念的满足度,以此来弱化某些信念,并且引入缺省决策理论推理得到Agent信念协调的一致解。然后,根据一致解建立一致的协调程序,将其作为Agent共同认同的背景知识库。最后,以dlv求解器为基础实现了多Agent信念协调算法,使Agent之间可以自主完成信念协调。文中以旅游推荐系统为例,说明该算法能够打破严格协调方法的局限,有效解决各Agent之间无共同信念时的协调问题。     

Update by means of inference rules

Katsuno and Mendelzon have distinguished two abstract frameworks for reasoning about change: theory revision and theory update. Theory revision involves a change in knowledge or belief with respect to a static world. By contrast, theory update involves a change of knowledge or belief in a changing world. In this paper, we are concerned with theory update. Winslett has shown that theory update should be computed “one model at a time.” Accordingly, we focus exclusively on the update of interpretations. We begin with a study of revision programming, introduced by Marek and Truszcyński to formulize interpretation update in a language similar to logic programming. While revision programs provide a useful and natural definition of interpretation update, they are limited to a fairly restricted set of update rules. Accordingly, we introduce the more general notion of rule update—interpretation update by arbitrary sets of inference rules. We show that Winslett's approach to update by means of arbitrary sets of formulas corresponds to a simple subclass of rule update. We also specify a simple embedding of rule update in Reiter’s default logic, obtained by augmenting the original update rules with default rules encoding the commonsense law of inertia—the principle that things change only when they are made to.     

A networked transferable belief model approach for distributed data aggregation

This paper focuses on the extension of the transferable belief model (TBM) to a multiagent-distributed context where no central aggregation unit is available and the information can be exchanged only locally among agents. In this framework, agents are assumed to be independent reliable sources which collect data and collaborate to reach a common knowledge about an event of interest. Two different scenarios are considered: In the first one, agents are supposed to provide observations which do not change over time (static scenario), while in the second one agents are assumed to dynamically gather data over time (dynamic scenario). A protocol for distributed data aggregation, which is proved to converge to the basic belief assignment given by an equivalent centralized aggregation schema based on the TBM, is provided. Since multiagent systems represent an ideal abstraction of actual networks of mobile robots or sensor nodes, which are envisioned to perform the most various kind of tasks, we believe that the proposed protocol paves the way to the application of the TBM in important engineering fields such as multirobot systems or sensor networks, where the distributed collaboration among players is a critical and yet crucial aspect.     

Distributed Belief Revision

In this paper, a distributed approach to belief revision is presented. It is conceived as a collective activity of a group of interacting agents, in which each component contributes with its own local beliefs. The integration of the different opinions is performed not by an external supervisor, but by the entire group through an election mechanism. Each agent exchanges information with the other components and uses a local belief revision mechanism to maintain its cognitive state consistent. We propose a model for local belief revision/integration based on what we called: Principle of Recoverability. Computationally, our way to belief revision consists of three steps acting on the symbolic part of the information, so as to deal with consistency and derivation, and two other steps working with the numerical weight of the information, so as to deal with uncertainty. In order to evaluate and compare the characteristics and performance of the centralized and of the distributed approaches, we made five different experiments simulating a simple society in which each agent is characterized by a degree of competence, communicates with some others, and revise its cognitive state. The results of these experiments are presented in the paper.     

一种基于可信度的迭代信念修正方法

信念修正主要解决在接收到新信息时,如何对原有知识库进行操作的问题．经典的迭代信念修正主要关注信念修正的一致性,并未考虑多agent系统中信息具有不可靠性,以及信念修正过程对修正结果的影响．基于可信度的迭代信念修正方法,通过证据理论以及信度函数方法估计信息的可信度,并由此确定最优的最大协调子集作为信念修正的结果．基于可信度的迭代信念修正算子具有历史依赖性,即修正结果不仅与当前的信念集和接收到的新信息有关,也与信念集中曾经接收到的信息相关．