A discrete formalism for reasoning about action and change

This paper presents a discrete formalism for temporal reasoning about actions and change, which enjoys an explicit representation of time and action/event occurrences. The formalism allows the expression of truth values for given fluents over various times including nondecomposable points/moments and decomposable intervals. Two major problems which beset most existing interval-based theories of action and change, i.e., the so-called dividing instant problem and the intermingling problem, are absent from this new formalism. The dividing instant problem is overcome by excluding the concepts of ending points of intervals, and the intermingling problem is bypassed by means of characterising the fundamental time structure as a well-ordered discrete set of non-decomposable times (points and moments), from which decomposable intervals are constructed. A comprehensive characterisation about the relationship between the negation of fluents and the negation of involved sentences is formally provided. The formalism provides a flexible expression of temporal relationships between effects and their causal events, including delayed effects of events which remains a problematic question in most existing theories about action and change.

Reasoning about change over time: Actions, events and their effects

This paper presents a new formalism for reasoning about change over time. The formalism derives a clean separation between the notion of states and situations. It allows more flexible temporal causal relationships than do other formalisms for reasoning about causal change, such as the situation calculus and the event calculus. It includes effects that start during, immediately after, or some time after their causes, and which end before, simultaneously with, or after their causes. A formal distinction between actions, action-types and events is proposed, which allows the expression of common-sense causal laws at high level. It is shown how these laws can be used to deduce state change over time at low level, when events occur under certain preconditions hold. Two problems that beset most interval-based temporal systems, i.e., the so-called dividing instant problem and intermingling problem, are absent from the formalism.

A forum on case-based reasoning. Guest editorial

Guest editorial

Representing temporal relationships between events and their effects

Temporal relationships between events and their effects are complex. As the effects of a given event, a proposition may change its truth value immediately after the occurrence of the event and remain true until some other events occur, while another proposition may only become true/false from some time after the causal event has occurred. Expressing delayed effects of events has been a problematic question in most existing theories of action and change. This paper presents a new formalism for representing general temporal causal relationships between events and their effects. It allows expressions of both immediate and delayed effects of events, and supports common-sense assertions such as "effects cannot precede their causes".

A case based reasoning system capturing fire modelling expertise

This paper describes the architecture of the case based reasoning (CBR) component of Smartfire, a fire field modelling tool for use by members of the Fire Safety Engineering community who are not expert in modelling techniques. The CBR system captures the qualitative reasoning of an experienced modeller in the assessment of room geometries so as to set up the important initial parameters of the problem. The system relies on two important reasoning principles obtained from the expert: 1) there is a natural hierarchical retrieval mechanism which may be employed; and 2) much of the reasoning on a qualitative level is linear in nature, although the computational solution of the problem is non-linear. The paper describes the qualitative representation of geometric room information on which the system is based, and the principles on which the CBR system operates.

Intelligent design assistant (IDA): a case base reasoning system for material and design

This paper describes the approach to the modelling of experiential knowledge in an industrial application of Case-Based Reasoning (CBR). The CBR involves retrieval techniques in conjunction with a relational database. The database is especially designed as a repository of experiential knowledge, and includes qualitative search indices. The system is intended to help design engineers and material engineers in the submarine cable industry. It consists of three parts: a materials database; a database of experiential knowledge; and a CBR system used to retrieve similar past designs based upon component and material qualitative descriptions. The system is currently undergoing user testing at the Alcatel Submarine Networks site in Greenwich.

A knowledge-based system to represent spatial reasoning for fire modelling

This paper describes the architecture of the knowledge based system (KBS) component of Smartfire, a fire field modelling tool for use by members of the fire safety engineering community who are not expert in modelling techniques. The KBS captures the qualitative reasoning of an experienced modeller in the assessment of room geometries, so as to set up the important initial parameters of the problem. Fire modelling expertise is an example of geometric and spatial reasoning, which raises representational problems. The approach taken in this project is a qualitative representation of geometric room information based on Forbus’ concept of a metric diagram. This takes the form of a coarse grid, partitioning the domain in each of the three spatial dimensions. Inference over the representation is performed using a case-based reasoning (CBR) component. The CBR component stores example partitions with key set-up parameters; this paper concentrates on the key parameter of grid cell distribution.

A framework for historical case-based reasoning

This paper presents a framework for Historical Case-Based Reasoning (HCBR) which allows the expression of both relative and absolute temporal knowledge, representing case histories in the real world. The formalism is founded on a general temporal theory that accommodates both points and intervals as primitive time elements. A case history is formally defined as a collection of (time-independent) elemental cases, together with its corresponding temporal reference. Case history matching is two-fold, i.e., there are two similarity values need to be computed: the non-temporal similarity degree and the temporal similarity degree. On the one hand, based on elemental case matching, the non-temporal similarity degree between case histories is defined by means of computing the unions and intersections of the involved elemental cases. On the other hand, by means of the graphical presentation of temporal references, the temporal similarity degree in case history matching is transformed into conventional graph similarity measurement.

Enhancing the usability of numerical models with case-based reasoning

Numerical models are important tools used in engineering fields to predict the behaviour and the impact of physical elements. There may be advantages to be gained by combining Case-Based Reasoning (CBR) techniques with numerical models. This paper considers how CBR can be used as a flexible query engine to improve the usability of numerical models. Particularly they can help to solve inverse and mixed problems, and to solve constraint problems. We discuss this idea with reference to the illustrative example of a pneumatic conveyor problem. The paper describes example problems faced by design engineers in this context and the issues that need to be considered in this approach. Solution of these problems require methods to handle constraints in both the retrieval phase and the adaptation phase of a typical CBR cycle. We show approaches to the solution of these problesm via a CBR tool.

Towards heterogeneous multiple case-based reasoning: an investigation

The traditional approach of dealing with cases from Multiple Case Bases is to map these to one central case base that is used for knowledge extraction and problem solving. Accessing Multiple Case Bases should not require a change to their data structure. This paper presents an investigation into applying Case-Based Reasoning to Multiple Heterogeneous Case Bases. A case study is presented to illustrate and evaluate the approach.

A versatile characterization of causal relationships

This paper introduces a framework for representing versatile temporal relationships between events and their effects. The framework is based on a simple time model which characterizes each time element as a subset of the set of real numbers and allows expression of both absolute time values and relative temporal relations. The formalism presented here formally specifies the so-called most general temporal constraint (GTC), which guarantees the common-sense assertion that “the beginning of the effect cannot precede the beginning of the cause”. It is shown that there are in fact 8 possible causal relationships which satisfy GTC, including cases where, on the one hand, effects start simultaneously with, during, immediately after, or some time after their causes, and on the other hand, events end before, simultaneously with, or after their causes. The causal relationships characterized in this paper are versatile enough to subsume those representatives in the literature.

Matching case history patterns in case-based reasoning

This paper introduces a mechanism for representing and recognizing case history patterns with rich internal temporal aspects. A case history is characterized as a collection of elemental cases as in conventional case-based reasoning systems, together with the corresponding temporal constraints that can be relative and/or with absolute values. A graphical representation for case histories is proposed as a directed, partially weighted and labeled simple graph. In terms of such a graphical representation, an eigen-decomposition graph matching algorithm is proposed for recognizing case history patterns.

Using set operations to deal with the frame problem

This paper presents a simple approach to the so-called frame problem based on some ordinary set operations, which does not require non-monotonic reasoning. Following the notion of the situation calculus, we shall represent a state of the world as a set of fluents, where a fluent is simply a Boolean-valued property whose truth-value is dependent on the time. High-level causal laws are characterised in terms of relationships between actions and the involved world states. An effect completion axiom is imposed on each causal law, which guarantees that all the fluents that can be affected by the performance of the corresponding action are always totally governed. It is shown that, compared with other techniques, such a set operation based approach provides a simpler and more effective treatment to the frame problem.