A rough set approach to reasoning under uncertainty

Abstract

Reasoning with uncertain information is a problem of key importance when dealing with information about the real world. Obtaining the precise numbers required by many uncertainty handling formalisms can be a problem. The theory of rough sets makes it possible to handle uncertainty without the need for precise numbers, and so has some advantages in such situations. This paper presents an introduction to various forms of reasoning under uncertainty that are based on rough sets. In particular, a number of sets of numerical and symbolic truth values which may be used to augment propositional logic are developed, and a semantics for these values is provided based upon the notion of possible worlds. Methods of combining the truth values are developed so that they may be propagated when augmented logic formulae are combined, and their use is demonstrated in theorem proving.     

Quantitative temporal reasoning

A substantially large class of programs operate in distributed and real-time environments, and an integral part of their correctness specification requires the expression of time-critical properties that relate the occurrence of events of the system. We focus on the formal specification and reasoning about the correctness of such programs. We propose a system of temporal logic, RTCTL (Real-Time Computation Tree Logic), that allows the melding of qualitative temporal assertions together with real-time constraints to permit specification and reasoning at the twin levels of abstraction: qualitative and quantitative. We argue that many practically useful correctness properties of temporal systems, which need to express timing as an essential part of their functionality requirements, can be expressed in RTCTL. We develop a model-checking algorithm for RTCTL whose complexity is linear in the size of the RTCTL specification formula and in the size of the structure. We also present an essentially optimal, exponential time tableau-based decision procedure for the satisfiability of RTCTL formulae. Finally, we consider several variants and extensions of RTCTL for real-time reasoning.The work of E.A. Emerson was supported in part by NSF grant DCR-8511354, ONR URI contract N00014-86-K-0763, and Netherlands NWO grant nf-3/nfb 62-500. The work of A.K.Mok was supported in part by ONR Grant number N00014-89-J-1472 and Texas Advanced Technology Program Grant 003658-250. A summary of these results was presented at the Workshop on Automatic Verification Methods for Finite State Systems, Grenoble, France, June 12–14, 1989.     

Complexity classification in qualitative temporal constraint reasoning

We study the computational complexity of the qualitative algebra which is a temporal constraint formalism that combines the point algebra, the point-interval algebra and Allen's interval algebra. We identify all tractable fragments and show that every other fragment is NP-complete.     

On point-duration networks for temporal reasoning

We present here a point-duration network formalism which extends the point algebra model to include additional variables that represent durations between points of time. Thereafter the new qualitative model is enlarged for allowing unary metric constraints on points and durations, subsuming in this way several point-based approaches to temporal reasoning. We deal with some reasoning tasks within the new models and we show that the main problem, deciding consistency, is NP-complete. However, tractable special cases are identified and we show efficient algorithms for checking consistency, finding a solution and obtaining the minimal network.     

A rough set approach to knowledge reduction based on inclusion degree and evidence reasoning theory

Abstract: The theory of rough sets is an extension of set theory for studying intelligent systems characterized by insufficient and incomplete information. We discuss the basic concept and properties of knowledge reduction based on inclusion degree and evidence reasoning theory, and propose a knowledge discovery approach based on inclusion degree and evidence reasoning theory.     

Implementation of the temporal reasoning mechanism in modern intelligent systems

A modern approach to temporal reasoning modeling in intelligent systems designed for dynamic subject domains is considered. Purposes, problems, and principles of construction of temporal reasoning systems are defined.     

Applying algorithm selection to abductive diagnostic reasoning

The complexity of technical systems requires increasingly advanced fault diagnosis methods to ensure safety and reliability during operation. Particularly in domains where maintenance constitutes an extensive portion of the entire operation cost, efficient and effective failure identification holds the potential to provide large economic value. Abduction offers an intuitive concept for diagnostic reasoning relying on the notion of logical entailment. Nevertheless, abductive reasoning is an intractable problem and computing solutions for instances of reasonable size and complexity persists to pose a challenge. In this paper, we investigate algorithm selection as a mechanism to predict the “best” performing technique for a specific abduction scenario within the framework of model-based diagnosis. Based on a set of structural attributes extracted from the system models, our meta-approach trains a machine learning classifier that forecasts the most runtime efficient abduction technique given a new diagnosis problem. To assess the predictor’s selection capabilities and the suitability of the meta-approach in general, we conducted an empirical analysis featuring seven abductive reasoning approaches. The results obtained indicate that applying algorithm selection is competitive in comparison to always choosing a single abductive reasoning method.     

Extending constraint logic programming for temporal reasoning

In recent years, several constraint‐based temporal reasoning frameworks have been proposed. They consider temporal points or intervals as domain elements linked by temporal constraints. Temporal reasoning in these systems is based on constraint propagation. In this paper, we argue that a language based on constraint propagation can be a suitable tool for expressing and reasoning about temporal problems. We concentrate on Constraint Logic Programming (CLP) which is a powerful programming paradigm combining the advantages of Logic Programming and the efficiency of constraint solving. However, CLP presents some limitations in dealing with temporal reasoning. First, it uses an “arc consistency” propagation algorithm which is embedded in the inference engine, cannot be changed by the user, and is too weak in many temporal frameworks. Second, CLP is not able to deal with qualitative temporal constraints. We present a general meta CLP architecture which maintains the advantages of CLP, but overcomes these two main limitations. Each architectural level is a finite domain constraint solver(CLP(FD)) that reasons about constraints of the underlying level. Based on this conceptual architecture, we extend the CLP(FD)language and we specialize the extension proposed on Vilain and Kautz’sPoint Algebra, on Allen’s Interval Algebra and on the STP framework by Dechter, Meiri and Pearl. In particular, we show that we can cope effectively with disjunctive constraints even in an interval‐based framework. This revised version was published online in June 2006 with corrections to the Cover Date.     

On the modelling and optimization of preferences in constraint-based temporal reasoning

In this paper, we consider both the modelling and optimization of preferences in problems of constraint-based temporal reasoning. The Disjunctive Temporal Problems with Preferences (DTPP) – a formulation that combines the rich expressive power of the Disjunctive Temporal Problem with the introduction of metric preference functions – is studied, and transformed into a corresponding constraint system that we name the Valued DTP (VDTP). We show that for a broad family of optimization criteria, the VDTP can express the same solution space as the DTPP, under the assumption of arbitrary piecewise-constant preference functions. We then generalize the powerful search strategies from decision-based DTP literature to accomplish the efficient optimization of temporal preferences. In contrast to the previous state-of-the-art system (which addresses the optimization of temporal preferences using a SAT formulation), we instead employ a meta-CSP search space that has traditionally been used to solve DTPs without preferences. Our approach supports a variety of objective functions (such as utilitarian optimality or maximin optimality) and can accommodate any compliant valuation structure. We also demonstrate that key pruning techniques commonly used for temporal satisfiability (particularly, the removal of subsumed variables and semantic branching) are naturally suited to prevent the exploration of redundant search nodes during optimization that may otherwise be encountered when resolving a typical VDTP derived from a DTPP. Finally, we present empirical results showing that an implementation of our approach consistently outperforms prior algorithms by orders of magnitude.     

Realistic model for temporal reasoning in real-time patient monitoring

Time is a central factor in patient monitoring. Introduction of domain-dependent knowledge is essential to ensure efficiency of time managers, especially when embedded into systems that interact with the real world. We present a realistic temporal reasoning model based on two basic cognitive mechanisms: aggregation of similar observed situations and forgetting of non-relevant information. We describe in detail how we represented the proposed model and how, by refinement of domain-independent temporal entities and inferences, we added domain specific knowledge to manage a clinical therapy. The model allows clinical observations to be incrementally interpreted as they are acquired by an intelligent system, mainly reactive in its reasoning, for the management of patients receiving respiratory support.     

Applying case-based reasoning for product configuration in mass customization environments

Product variation and customization is a trend in current market-oriented manufacturing environment. Companies produce products in order to satisfy customer's needs. In the customization environment, the R&D sector in an enterprise should be able to offer differentiation in product selection after they take the order. Such product differentiation should meet the requirement of cost and manufacturing procedure. In the light of this, how to generate an accurate bill of material (BOM) that meets the customer's needs and gets ready for the production is an important issue in the intensely competitive market.The purpose of this study is to reduce effectively the time and cost of design under the premise to manufacture an accurate new product. In this study, the Case-Based Reasoning (CBR) algorithm was used to construct the new BOM. Retrieving previous cases that resemble the current problem can save a lot of time in figuring out the problem and offer a correct direction for designers. When solving a new problem, CBR technique can quickly help generate a right BOM that fits the present situation.     

Applying case-based reasoning for product configuration in mass customization environments

Product variation and customization is a trend in current market-oriented manufacturing environment. Companies produce products in order to satisfy customer's needs. In the customization environment, the R&D sector in an enterprise should be able to offer differentiation in product selection after they take the order. Such product differentiation should meet the requirement of cost and manufacturing procedure. In the light of this, how to generate an accurate bill of material (BOM) that meets the customer's needs and gets ready for the production is an important issue in the intensely competitive market.

The purpose of this study is to reduce effectively the time and cost of design under the premise to manufacture an accurate new product. In this study, the Case-Based Reasoning (CBR) algorithm was used to construct the new BOM. Retrieving previous cases that resemble the current problem can save a lot of time in figuring out the problem and offer a correct direction for designers. When solving a new problem, CBR technique can quickly help generate a right BOM that fits the present situation.     

Automated reasoning in differential geometry and mechanics using the characteristic set method

This is the first paper of a series of three papers under the same title. It presents an improved version of Ritt-Wu's decomposition algorithm which is the basis of our methods of mechanical theorem proving and mechanical formula derivation in differential geometry and elementary mechanics. We improve the original algorithm in two aspects. First, by using the weak ascending chain and W-perm, the sizes of the differential polynomials occurring in the decomposition can be reduced. Second, by using a special reduction procedure, the number of branches in the decomposition can be controlled effectively. The improved version significantly enhances the efficiency of the original algorithm.The work reported here was supported in part by NSF Grants CCR-8702108 and CCR-9117870.     

Modelling and solving temporal reasoning as propositional satisfiability

Representing and reasoning about time dependent information is a key research issue in many areas of computer science and artificial intelligence. One of the best known and widely used formalisms for representing interval-based qualitative temporal information is Allen's interval algebra (IA). The fundamental reasoning task in IA is to find a scenario that is consistent with the given information. This problem is in general NP-complete.In this paper, we investigate how an interval-based representation, or IA network, can be encoded into a propositional formula of Boolean variables and/or predicates in decidable theories. Our task is to discover whether satisfying such a formula can be more efficient than finding a consistent scenario for the original problem. There are two basic approaches to modelling an IA network: one represents the relations between intervals as variables and the other represents the end-points of each interval as variables. By combining these two approaches with three different Boolean satisfiability (SAT) encoding schemes, we produced six encoding schemes for converting IA to SAT. In addition, we also showed how IA networks can be formulated into satisfiability modulo theories (SMT) formulae based on the quantifier-free integer difference logic (QF-IDL). These encodings were empirically studied using randomly generated IA problems of sizes ranging from 20 to 100 nodes. A general conclusion we draw from these experimental results is that encoding IA into SAT produces better results than existing approaches. More specifically, we show that the new point-based 1-D support SAT encoding of IA produces consistently better results than the other alternatives considered. In comparison with the six different SAT encodings, the SMT encoding came fourth after the point-based and interval-based 1-D support schemes and the point-based direct scheme. Further, we observe that the phase transition region maps directly from the IA encoding to each SAT or SMT encoding, but, surprisingly, the location of the hard region varies according to the encoding scheme. Our results also show a fixed performance ranking order over the various encoding schemes.     

Extending CLIPS to support temporal representation and reasoning

Applications using expert systems for monitoring and control problems often require the ability to represent temporal knowledge and to apply reasoning based on that knowledge. Incorporating temporal representation and reasoning into expert systems leads to two problems in development: dealing with an implied temporal order of events using a non-procedural tool; and maintaining the large number of temporal relations that can occur among facts in the knowledge base. In this paper we explore these problems by using an expert system shell, CLIPS (C Language Integrated Production System), to create temporal relations using common knowledge-based constructs. We also build an extension to CLIPS through a user-defined function which generates the temporal relations from those facts. We use the extension to create and maintain temporal relations in a workflow application that monitors and controls an engineering design change review process. We also propose a solution to ensure truth maintenance among temporally related facts that links our temporal extension to the CLIPS facility for truth maintenance.     

Exact and approximate reasoning about temporal relations1

Allen gives an algebra for representing qualitative temporal information about the relationships between pairs of intervals. In this paper, we address a fundamental reasoning task that arises in applications of the algebra: Given (possibly indefinite) knowledge about the relationships between intervals, find all feasible relationships between two intervals. We call this the minimal labels problem. Finding the minimal labels can be viewed as computing the deductive consequences of our knowledge. Determining exact solutions to this problem has been shown to be (almost assuredly) intractable. Allen gives an approximation algorithm based on constraint propagation. We present new approximation algorithms; determine analytically under what conditions the algorithms are exact; and examine, through some computational experiments, the quality of the approximate solutions produced by the algorithms. We also give a simple test for predicting when the approximation algorithms will and will not produce good quality approximations. Finally, we survey three example applications of the interval algebra chosen from the literature to show where the results of this paper could be useful.     

Applying temporal constraints to the dynamic stereo problem

An algorithm is presented for the problem of the stereopsis of time-varuing images (the dynamic stereo problem). Dynamic stereopsis is the integration of two problems; static stereopsis and temporal correspondence. Rather than finding the intersection of these problems to be more difficult, it was found that by solving the two problem simultaneously, and thus incorporating the spatio-temporal context within which a scene exists, some of the hard subproblems belonging to stereopsis and temporal correspondence could be avoided. The algorithm relies on a general smoothness assumption to assign both disparity and temporal matches. A simple model of the motion of three-dimensional features is used to guide the matching process and to identify conditional matches which violate a general smoothness assumption. A spatial proximity rule is used to further restrict possible matches. The algorithm has been tested on both synthetic and real input sequences. Input sequences were chosen from three-dimensional moving light displays and from “real” grey-level digitized images.     

Computing the minimal relations in point-based qualitative temporal reasoning through metagraph closure

Computing the minimal representation of a given set of constraints (a CSP) over the Point Algebra (PA) is a fundamental temporal reasoning problem. The main property of a minimal CSP over PA is that the strongest entailed relation between any pair of variables in the CSP can be derived in constant time. We study some new methods for solving this problem which exploit and extend two prominent graph-based representations of a CSP over PA: the timegraph and the series-parallel (SP) metagraph. Essentially, these are graphs partitioned into sets of chains and series-parallel subgraphs, respectively, on which the search is supported by a metagraph data structure. The proposed approach is based on computing the metagraph closure for these representations, which can be accomplished by some methods studied in the paper.In comparison with the known techniques based on enforcing path consistency, under certain conditions about the structure of the input CSP and the size of the generated metagraph, the proposed metagraph closure approach has better worst-case time and space complexity. Moreover, for every sparse CSP over the convex PA, the time complexity is reduced to O(n²) from O(n³), where n is the number of variables involved in the CSP.An extensive experimental analysis presented in the paper compares the proposed techniques and other known algorithms. These experimental results identify the best performing methods and show that, in practice, for CSPs exhibiting chain or SP-graph structure and randomly generated (both sparse and dense) CSPs, the metagraph closure approach is significantly faster than the approach based on enforcing path consistency.