An efficient LP-based admissible heuristic for cost-based abduction

Cost-based abduction (CBA) is an important problem in reasoning under uncertainty. The CBA problem is NP-hard, and existing techniques have exponential worst-case complexity. This paper presents an admissible heuristic for CBA based on the use of linear programming to obtain an optimistic estimate of the cost-to-goal. The article then presents empirical results that indicate that the authors' method is efficient in comparison to Santos‘ integer linear programming method.     

Extending abstract argumentation systems theory

In this paper, we extend the theory of abstract argumentation systems proposed by Vreeswijk (1997). This framework stands at a high abstraction level and provides a general model for argumentation activity. However, the theory reveals an inherent limitation in that the premises of the argumentation process are assumed to be indefeasible, and this introduces the need of an implicit constraint on the strength of the arguments, in order to preserve correctness. In many application contexts the information available to start reasoning is not guaranteed to be completely reliable, therefore it is natural to assume that premises can be discarded during the argumentation process. We extend the theory by admitting that premises can be defeated and relaxing the implicit assumption about their strength.Besides fixing the technical problems related to this hidden assumption (e.g., ensuring that warranted arguments are compatible), our proposal provides an integrated model for belief revision and defeasible reasoning, confirming the suitability of argumentation as a general model for the activity of intelligent reasoning in presence of various kinds of uncertainty.     

On the revision of probabilistic beliefs using uncertain evidence

We revisit the problem of revising probabilistic beliefs using uncertain evidence, and report results on several major issues relating to this problem: how should one specify uncertain evidence? How should one revise a probability distribution? How should one interpret informal evidential statements? Should, and do, iterated belief revisions commute? And what guarantees can be offered on the amount of belief change induced by a particular revision? Our discussion is focused on two main methods for probabilistic revision: Jeffrey's rule of probability kinematics and Pearl's method of virtual evidence, where we analyze and unify these methods from the perspective of the questions posed above.     

Belief extrapolation (or how to reason about observations and unpredicted change)

We give a logical framework for reasoning with observations at different time points. We call belief extrapolation the process of completing initial belief sets stemming from observations by assuming minimal change. We give a general semantics and we propose several extrapolation operators. We study some key properties verified by these operators and we address computational issues. We study in detail the position of belief extrapolation with respect to revision and update: in particular, belief extrapolation is shown to be a specific form of time-stamped belief revision. Several related lines of work are positioned with respect to belief extrapolation.     

Simulating belief systems of autonomous agents

Autonomous agents in computer simulations do not have the usual mechanisms to acquire information as do their human counterparts. In many such simulations, it is not desirable that the agent have access to complete and correct information about its environment. We examine how imperfection in available information may be simulated in the case of autonomous agents. We determine probabilistically what the agent may detect, through hypothetical sensors, in a given situation. These detections are combined with the agent's knowledge base to infer observations and beliefs. Inherent in this task is a degree of uncertainty in choosing the most appropriate observation or belief. We describe and compare two approaches — a numerical approach and one based on defeasible logic — for simulating an appropriate belief in light of conflicting detection values at a given point in time. We discuss the application of this technique to autonomous forces in combat simulation systems.     

An AGM-style belief revision mechanism for probabilistic spatio-temporal logics

There is now extensive interest in reasoning about moving objects. A probabilistic spatio-temporal (PST) knowledge base (KB) contains atomic statements of the form “Object o is/was/will be in region r at time t with probability in the interval [?,u]”. In this paper, we study mechanisms for belief revision in PST KBs. We propose multiple methods for revising PST KBs. These methods involve finding maximally consistent subsets and maximal cardinality consistent subsets. In addition, there may be applications where the user has doubts about the accuracy of the spatial information, or the temporal aspects, or about the ability to recognize objects in such statements. We study belief revision mechanisms that allow changes to the KB in each of these three components. Finally, there may be doubts about the assignment of probabilities in the KB. Allowing changes to the probability of statements in the KB yields another belief revision mechanism. Each of these belief revision methods may be epistemically desirable for some applications, but not for others. We show that some of these approaches cannot satisfy AGM-style axioms for belief revision under certain conditions. We also perform a detailed complexity analysis of each of these approaches. Simply put, all belief revision methods proposed that satisfy AGM-style axioms turn out to be intractable with the exception of the method that revises beliefs by changing the probabilities (minimally) in the KB. We also propose two hybrids of these basic approaches to revision and analyze the complexity of these hybrid methods.     

New model for system behavior prediction based on belief rule based systems

To predict the behavior of a complex engineering system, a model can be built and trained using historical data. However, it may be difficult to obtain a complete and accurate set of data to train the model. Consequently, the model may be incapable of predicting the future behavior of the system with reasonable accuracy. On the other hand, expert knowledge of a qualitative nature and partial historical information about system behavior may be available which can be converted into a belief rule base (BRB). Based on the unique features of BRB, this paper is devoted to overcoming the above mentioned difficulty by developing a forecasting model composed of two BRBs and two recursive learning algorithms, which operate together in an integrated manner. An initially constructed forecasting model has some unknown parameters which may be manually tuned and then trained or updated using the learning algorithms once data become available. Based on expert intervention which can reflect system operation patterns, two algorithms are developed on the basis of the evidential reasoning (ER) algorithm and the recursive expectation maximization (EM) algorithm with the former used for handling judgmental outputs and the latter for processing numerical outputs, respectively. Using the proposed algorithms, the training of the forecasting model can be started as soon as there are some data available, without having to wait until a complete set of data are all collected, which is critical when the forecasting model needs to be updated in real-time within a given time limit. A numerical simulation study shows that under expert intervention, the forecasting model is flexible, can be automatically tuned to predict the behavior of a complicated system, and may be applied widely in engineering. It is demonstrated that if certain conditions are met, the proposed recursive algorithms can converge to a local optimum. A case study is also conducted to show the wide potential applications of the forecasting model.     

An experimental evaluation of simplicity in rule learning

While recent research on rule learning has focused largely on finding highly accurate hypotheses, we evaluate the degree to which these hypotheses are also simple, that is small. To realize this, we compare well-known rule learners, such as CN2, RIPPER, PART, FOIL and C5.0 rules, with the benchmark system SL² that explicitly aims at computing small rule sets with few literals. The results show that it is possible to obtain a similar level of accuracy as state-of-the-art rule learners using much smaller rule sets.     

Large neighbourhood search algorithms for the founder sequence reconstruction problem

The reconstruction of founder genetic sequences of a population is a relevant issue in evolutionary biology research. The problem consists in finding a biologically plausible set of genetic sequences (founders), which can be recombined to obtain the genetic sequences of the individuals of a given population. The reconstruction of these sequences can be modelled as a combinatorial optimisation problem in which one has to find a set of genetic sequences such that the individuals of the population under study can be obtained by recombining founder sequences minimising the number of recombinations. This problem is called the founder sequence reconstruction problem. Solving this problem can contribute to research in understanding the origins of specific genotypic traits. In this paper, we present large neighbourhood search algorithms to tackle this problem. The proposed algorithms combine a stochastic local search with a branch-and-bound algorithm devoted to neighbourhood exploration. The developed algorithms are thoroughly evaluated on three different benchmark sets and they establish the new state of the art for realistic problem instances.     

Satisfiability Testing of Boolean Combinations of Pseudo-Boolean Constraints using Local-search Techniques

Some search problems are most directly specified by conjunctions of (sets of) disjunctions of pseudo-Boolean (PB) constraints. We study a logic PL ^PB whose formulas are of such form, and design local-search methods to compute models of PL ^PB theories. In our approach we view a PL ^PB theory T as a data structure, a concise representation of a certain propositional conjunctive normal form (CNF) theory cl(T) logically equivalent to T. The key idea is an observation that parameters needed by local-search algorithms for CNF theories, such as walksat, can be estimated on the basis of T without the need to compute cl(T) explicitly. We compare our methods to a local-search algorithm wsat(oip). The experiments demonstrate that our approach performs better. In order for wsat(oip) to handle arbitrary PL ^PB theories, it is necessary to represent disjunctions of PB constraints by sets of PB constraints, which often increases the size of the theory dramatically. A better performance of our method underscores the importance of developing solvers that work directly on PL ^PB theories. This paper combines and extends results included in conference papers [14, 15].     

A model-based belief revision system

Numerous belief revision and update semantics have been proposed in the literature in the past few years, but until recently, no work in the belief revision literature has focussed on the problem of implementing these semantics, and little attention has been paid to algorithmic questions. In this paper, we present and analyze our update algorithms built in Immortal, a model-based belief revision system. These algorithms can work for a variety of model-based belief revision semantics proposed to date. We also extend previously proposed semantics to handle updates involving the equality predicate and function symbols and incorporate these extensions in our algorithms. As an example, we discuss the use of belief revision semantics to model the action-augmented envisioning problem in qualitative simulation, and we show the experimental results of running an example simulation in Immortal.     

基于ATMS和证据理论的不确定性推理方法

本文提出了一种新的不确定性推理方法ＨＵＩＭ．这种方法把基于假设的真值维持系统（ＡＴＭＳ）和Ｄｅｍｐｓｔｅｒ—Ｓｈａｆｅｒ的证据理论有机地结合在一起,使得ＡＴＭＳ这种符号代数系统可用来处理以数值形式表示的不确定性信息．将该方法应用于基于规则的系统,可以弥补这类系统在不确定性推理方面所存在的某些不足．     

Towards a temporal coherence management in real-time knowledge-based systems

The multi-agent system paradigm emerges as an interesting approach in the Knowledge-Based System (KBS) field when distributed problem-solving techniques are required. On the other hand, temporal representation and reasoning problems arise in a wide range of KBS application areas where time plays a crucial role. In this paper, we show that when agents run concurrently and access common temporal data, some problems of coherence arise. We analyse the different cases in which an incoherence in temporal information can occur and provide a method to tackle this problem. In this method, conflict management is handled by means of exception handlers and control rules allowing the users to explicitly define their own strategy for temporal coherence solving.     

多Agent信念修正研究

Belief Revision is a theory that studies how to integrate new information into original belief set.Classical BR theory uses AGM frame,but it only resolves problems in single agent BR system.Multi-agent BR faces problems such as the collision of many information sources and how to maximize the logic consistence of multi-agent system.On the basis of game theory model,we form profit matrix under different BR strategies in muhi-agent system and try to get the best strategy that satisfies logic consistence of the system through negotiation.     

Conciliation through Iterated Belief Merging

Two families of conciliation processes for intelligent agentsbased on an iterated merge-then-revise change function for beliefprofiles are introduced and studied. The processes from thefirst family are sceptical in the sense that at any revisionstep, each agent considers that her current beliefs are moreimportant than the current beliefs of the group, while the processesfrom the other family are credulous. Some key features of suchconciliation processes are pointed out for several merging operators;especially, the stationarity issue, the existence of consensusand the properties of the induced iterated merging operatorsare investigated.     

Heuristics for the probabilistic traveling salesman problem with deadlines based on quasi-parallel Monte Carlo sampling

The Probabilistic Traveling Salesman Problem with Deadlines (PTSPD) is a Stochastic Vehicle Routing Problem with a computationally demanding objective function. In this work we propose an approximation for that objective function based on Monte Carlo Sampling and using the novel approach of quasi-parallel evaluation of samples. We perform comprehensive computational studies that reveal the efficiency of this approximation. Additionally, we examine different Local Search Algorithms and present a Random Restart Local Search Algorithm for solving the PTSPD together with an extensive computational study on a large set of benchmark instances.