Johan de Kleer

AAAI Conference 2025 Conference Paper

A Domain-Independent Agent Architecture for Adaptive Operation in Evolving Open Worlds

• Shiwali Mohan
• Wiktor Piotrowski
• Roni Stern
• Sachin Grover
• Sookyung Kim
• Jacob Le
• Johan de Kleer
• Yoni Sher

Model-based reasoning agents are ill-equipped to act in novel situations in which their model of the environment no longer sufficiently represents the world. We propose HYDRA, a framework for designing model-based agents operating in mixed discrete-continuous worlds that can autonomously detect when the environment has evolved from its canonical setup, understand how it has evolved, and adapt the agents' models to perform effectively. HYDRA is based upon PDDL+, a rich modeling language for planning in mixed, discrete-continuous environments. It augments the planning module with visual reasoning, task selection, and action execution modules for closed-loop interaction with complex environments. HYDRA implements a novel meta-reasoning process that enables the agent to monitor its own behavior from a variety of aspects. The process employs a diverse set of computational methods to maintain expectations about the agent's own behavior in an environment. Divergences from those expectations are useful in detecting when the environment has evolved and identifying opportunities to adapt the underlying models. HYDRA builds upon ideas from diagnosis and repair and uses a heuristics-guided search over model changes such that they become competent in novel conditions. The HYDRA framework has been used to implement novelty-aware agents for three diverse domains - CartPole++ (a higher dimension variant of a classic control problem), Science Birds (an IJCAI competition problem), and PogoStick (a specific problem domain in Minecraft). We report empirical observations from these domains to demonstrate the efficacy of various components in the novelty meta-reasoning process.

AIJ Journal 2024 Journal Article

A domain-independent agent architecture for adaptive operation in evolving open worlds

• Shiwali Mohan
• Wiktor Piotrowski
• Roni Stern
• Sachin Grover
• Sookyung Kim
• Jacob Le
• Yoni Sher
• Johan de Kleer

1 Angry Birds Competition. Model-based reasoning agents are ill-equipped to act in novel situations in which their model of the environment no longer sufficiently represents the world. We propose HYDRA, a framework for designing model-based agents operating in mixed discrete-continuous worlds that can autonomously detect when the environment has evolved from its canonical setup, understand how it has evolved, and adapt the agents' models to perform effectively. HYDRA is based upon PDDL+, a rich modeling language for planning in mixed, discrete-continuous environments. It augments the planning module with visual reasoning, task selection, and action execution modules for closed-loop interaction with complex environments. HYDRA implements a novel meta-reasoning process that enables the agent to monitor its own behavior from a variety of aspects. The process employs a diverse set of computational methods to maintain expectations about the agent's own behavior in an environment. Divergences from those expectations are useful in detecting when the environment has evolved and identifying opportunities to adapt the underlying models. HYDRA builds upon ideas from diagnosis and repair and uses a heuristics-guided search over model changes such that they become competent in novel conditions. The HYDRA framework has been used to implement novelty-aware agents for three diverse domains - CartPole++ (a higher dimension variant of a classic control problem), Science Birds (an IJCAI competition problem 1 ), and PogoStick (a specific problem domain in Minecraft). We report empirical observations from these domains to demonstrate the efficacy of various components in the novelty meta-reasoning process.

JMLR Journal 2023 Journal Article

Sensitivity-Free Gradient Descent Algorithms

• Ion Matei
• Maksym Zhenirovskyy
• Johan de Kleer
• John Maxwell

We introduce two block coordinate descent algorithms for solving optimization problems with ordinary differential equations (ODEs) as dynamical constraints. In contrast to prior algorithms, ours do not need to implement sensitivity analysis methods to evaluate loss function gradients. They result from the reformulation of the original problem as an equivalent optimization problem with equality constraints. In our first algorithm we avoid explicitly solving the ODE by integrating the ODE solver as a sequence of implicit constraints. In our second algorithm, we add an ODE solver to reset the estimate of the ODE solution, but no sensitivity analysis method is needed. We test the proposed algorithms on the problem of learning the parameters of the Cucker-Smale model. The algorithms are compared with gradient descent algorithms based on ODE solvers endowed with sensitivity analysis capabilities. We show that the proposed algorithms are at least 4x faster when implemented in Pytorch, and at least 16x faster when implemented in Jax. For large versions of the Cucker-Smale model, the Jax implementation is thousands of times faster. Our algorithms generate more accurate results both on training and test data. In addition, we show how the proposed algorithms scale with the number of optimization variables, and how they can be applied to learning black-box models of dynamical systems. Moreover, we demonstrate how our approach can be combined with approaches based on sensitivity analysis enabled ODE solvers to reduce the training time. [abs] [ pdf ][ bib ] &copy JMLR 2023. ( edit, beta )

AAAI Conference 2020 Conference Paper

Efficient Model-Based Diagnosis of Sequential Circuits

• Alexander Feldman
• Ingo Pill
• Franza Wotawa
• Ion Matei
• Johan de Kleer

In Model-Based Diagnosis (MBD), we concern ourselves with the health and safety of physical and software systems. Although we often use different knowledge representations and algorithms, some tools like satisfiability (SAT) solvers and temporal logics, are used in both domains. In this paper we introduce Finite Trace Next Logic (FTNL) models of sequential circuits and propose an enhanced algorithm for computing minimal-cardinality diagnoses. Existing state-of-the-art satisfiability algorithms for minimal diagnosis use Sorting Networks (SNs) for constraining the cardinality of the diagnostic candidates. In our approach we exploit Multi-Operand Adders (MOAs). Based on extensive tests with ISCAS-89 circuits, we found that MOAs enable Conjunctive Normal Form (CNF) encodings that are significantly more compact. These encodings lead to 19. 7 to 67. 6 times fewer variables and 18. 4 to 62 times fewer clauses. For converting an FTNL model to CNF, we could achieve a speed-up ranging from 6. 2 to 22. 2. Using SNs fosters 3. 4 to 5. 5 times faster on-line satisfiability checking though. This makes MOAs preferable for applications where RAM and off-line time are more limited than on-line CPU time.

ECAI Conference 2016 Conference Paper

A Framework for Automatic Debugging of Functional and Degradation Failures

• Nuno Cardoso
• Rui Abreu 0001
• Alexander Feldman
• Johan de Kleer

Software diagnosis is a particularly challenging problem for modern systems, which may consist of dozens, if not hundreds, of components computing on concurrent and potentially distributed platforms, and using infrastructure and services built by many organizations. We propose a framework that generalizes state-of-the-art classical reasoning-based fault diagnosis which tolerates observation uncertainty and addresses degradation of quality of service. Empirical evaluation involving 27000 highly realistic synthetic scenarios demonstrates an average accuracy improvement of 20% (with 99% statistical significance) which is considerable in the domain of Software Fault Localization (SFL). We measure the improvement in accuracy on well-established SFL performance metrics.

AAAI Conference 2014 Conference Paper

Qualitative Reasoning with Modelica Models

• Matthew Klenk
• Johan de Kleer
• Daniel Bobrow
• Bill Janssen

IJCAI Conference 2009 Conference Paper

• Johan de Kleer

Almost all approaches to model-based diagnosis presume that the system being diagnosed behaves non-intermittently and analyze behavior over a small number (often only one) of time instants. In this paper we show how existing approaches to model-based diagnosis can be extended to diagnose intermittent failures as they manifest themselves over time. In addition, we show where to insert probe points to best distinguish among the intermittent faults those that best explain the symptoms and isolate the fault in minimum expected cost.

ICAPS Conference 2009 Conference Paper

Pervasive Model Adaptation: The Integration of Planning and Information Gathering in Dynamic Production Systems

• Juan Liu
• Lukas D. Kuhn
• Johan de Kleer
• Rong Zhou 0001

Model-based planning often presumes a static system model, while in a practice physical system may evolve or drift over time. This paper proposes the idea of pervasive model adaptation in a production system, where the model is dynamically updated using observation of production output. The core idea is the interplay between model adaptation and production planning. We seek plans which simultaneously serve the goals of achieving high productivity for production, and information gathering for model adaptation. We use a modular printing example to illustrate issues such as formulation of the information criterion and search strategy for informative plans. The idea of pervasive adaptation can be further extended to improve long term productivity in production systems.

AAAI Conference 2008 Conference Paper

Pervasive Diagnosis: The Integration of Diagnostic Goals into Production Plans

• Lukas Kuhn
• Johan de Kleer

In model-based control, a planner uses a system description to create a plan that achieves production goals (Fikes & Nilsson 1971). The same description can be used by modelbased diagnosis to infer the condition of components in a system from partially informative sensors. Prior work has demonstrated that diagnosis can be used to adapt the control of a system to changes in its components. However diagnosis must either make inferences from passive observations of production, or production must be halted to take diagnostic actions. We observe that the declarative nature of model-based control allows the planner to achieve production goals in multiple ways. This flexibility can be exploited with a novel paradigm we call pervasive diagnosis which produces diagnostic production plans that simultaneously achieve production goals while uncovering additional information about component health. We present an efficient heuristic search for these diagnostic production plans and show through experiments on a model of an industrial digital printing press that the theoretical increase in information can be realized on practical real-time systems. We obtain higher long-run productivity than a decoupled combination of planning and diagnosis.

IJCAI Conference 2007 Conference Paper

• Johan de Kleer

Most AI diagnostic reasoning approaches model components and but not their interconnections, and when they do model interconnections, they model the possibility that a connection can break, not that two connections may join (e. g. , through fluid leakage or electrical short circuit). Two reasons for this limitation are (1) that modeling these interconnection failures could require an exponential number (in the number of interconnections) failure possibilities, and (2) that modeling interconnection failures requires modeling the system at a more precise level which requires far more complex models. A fundamental contribution of this paper is a more powerful approach to modeling connections which does not require special-case post-processing and is computationally tractable. We illustrate our approach in the context of digital systems.

IJCAI Conference 1995 Conference Paper

Trading off the costs of inference vs probing in diagnosis

• Johan de Kleer
• Olivier Raiman

This paper proposes a new algorithm which when provided the relative costs of computa­ tion vs. probing minimizes the total cost of diagnosis. During the diagnosis process the de­ cision of whether to probe or to compute is dependent on the expected costs and benefits of each alternative. It is unlikely that we will be able to find general analytic and simpleto-compute models for the costs and benefits. Therefore, we base our algorithm on simple em­ pirically derived models of costs and benefits. W i t h these models, our algorithm operates by continuously choosing the optimum action to make next. This algorithm will not blow up on the rare pathological cases and will always (on average) find diagnoses at equal to or better cost than a conventional GDE/Sherlock. When the cost of probing is high, then our algorithm behaves exactly the same as GDE/Sherlock. When the cost of computation is high, the algo­ rithm performs the diagnosis at far lower cost than GDE/Sherlock.

AIJ Journal 1993 Journal Article

A perspective on assumption-based truth maintenance

• Johan de Kleer

AIJ Journal 1993 Journal Article

A view on qualitative physics

• Johan de Kleer

IJCAI Conference 1993 Conference Paper

Critical Reasoning

• Olivier Raiman
• Johan de Kleer

AAAI Conference 1992 Conference Paper

An Improved Incremental Algorithm for Generating Prime Implicates

• Johan de Kleer

Prime implicates have become a widely used tool in AI. The prime implicates of a set of clauses can be computed by repeatedly resolving pairs of clauses, adding the resulting resolvents to the set and removing subsumed clauses. Unfortunately, this brute-force approach performs far more resolution steps than necessary. Tison provided a method to avoid many of the resolution steps and Kean and Tsiknis developed an optimized increment al version. Unfortunately, both these algorithms focus only on reducing the number of resolution steps required to compute the prime implicates. The actual running time of the algorithms depends critically on the number and expense of the subsumption checks they require. This paper describes a method based on a simplification of Kean and Tsiknis’ algorithm using an entirely different data structure to represent the data base of clauses. The new algorithm uses a form of discrimination net called tries to represent the clausal data base which produces an improvement in running time on all known examples with a dramatic improvement in running time on larger examples.

AIJ Journal 1992 Journal Article

Characterizing diagnoses and systems

• Johan de Kleer
• Alan K. Mackworth
• Raymond Reiter

Most approaches to model-based diagnosis describe a diagnosis for a system as a set of failing components that explains the symptoms. In order to characterize the typically very large number of diagnoses, usually only the minimal such sets of failing components are represented. This method of characterizing all diagnoses is inadequate in general, in part because not every superset of the faulty components of a diagnosis necessarily provides a diagnosis. In this paper we analyze the concept of diagnosis in depth exploiting the notions of implicate/implicant and prime implicate/implicant. We use these notions to consider two alternative approaches for addressing the inadequacy of the concept of minimal diagnosis. First, we propose a new concept, that of kernel diagnosis, which is free of this problem with minimal diagnosis. This concept is useful to both the consistency and abductive views of diagnosis. Second, we consider restricting the axioms used to describe the system to ensure that the concept of minimal diagnosis is adequate.

AAAI Conference 1991 Conference Paper

Focusing on Probable Diagnoses

• Johan de Kleer

Model-based diagnosis is based on first-principles reasoning using the behavioral specifications of the primitive components of a device. Unless the computational architecture of the model-based reasoning engine is carefully designed, combinatorial explosion renders the approach useless for devices consisting of more than a handful of components. This paper analyzes the diverse origins of this combina torial explosion and outlines strategies to cope with each one. The resulting computational architecture for model-based diagnosis provides orders of magnitude performance improvement on large examples, making model-based approach practical for devices consisting of on the order of 3000 components.

AIJ Journal 1991 Journal Article

Qualitative reasoning about physical systems: A return to roots

• Brian C. Williams
• Johan de Kleer

AAAI Conference 1990 Conference Paper

Characterizing Diagnoses

• Johan de Kleer

Most approaches to model-based diagnosis describe a diagnosis for a system as a set of failing components that explains the symptoms. In order to characterize the typically very large number of diagnoses, usually only the minimal such sets of failing components are represented. This method of characterizing all diagnoses is inadequate in general, in part because not every superset of the faulty components of a diagnosis necessarily provides a diagnosis. In this paper we analyze the notion of diagnosis in depth exploiting the notions of implicate/implicant and prime implicate/implicant. We use these notions to propose two alternative approaches for addressing the inadequacy of the concept of minimal diagnosis. First, we propose a new concept, that of kernel diagnosis, which is free of the problems of minimal diagnosis. Second, we propose to restrict the axioms used to describe the system to ensure that the concept of minimal diagnosis is adequate.

AAAI Conference 1990 Conference Paper

Exploiting Locality in a TMS

• Johan de Kleer

This paper presents a new approach for exploiting Truth Maintenance Systems(TMSs) which makes them simpler to use without necessarily incurring a substantial performance penalty. The basic intuition behind this approach is to convey the locality of the knowledge representation of the problem solver to the TMS. The TMS then uses this locality information to control and restrict its inferences. The new TMSs accept arbitrary propositional formulae as input and use general Boolean Constraint Propagation(BCP) t o answer queries about whether a particular literal follows from the formulae. Our TMS exploits the observation that if the set of propositional formulae are converted to their prime implicates, then BCP is both efficient and logically complete. This observation allows the problem solver to influence the degree of completeness of the TMS by controlling how many implicates are constructed. This control is exerted by using the locality in the original task to guide which combinations of formulae should be reduced to their prime implicates. This approach has been implemented and tested both within Assumption-Based Truth Maintenance Systems and Logic-Based Truth Maintenance Systems.

AIJ Journal 1990 Journal Article

Using crude probability estimates to guide diagnosis

• Johan de Kleer

In order to identify the faulty components of a malfunctioning device in the fewest number of measurements, model-based diagnosis often uses a minimum entropy technique to select the next best measurement. This technique seems critically dependent on the availability of failure probabilities for components. Unfortunately, in many cases this information is unavailable or unknown. However, if we can assume that all components fail independently with equal probability and that components fail with very small probability, then it is possible to exploit the intuitions of the technique even when the exact probabilities are unknown. In addition, the computation required is much simpler. This approach can be generalized if the set of components can be partitioned such that each of the components of a partition fail with equal probability but are much more or less likely to fail than those of other partitions.

IJCAI Conference 1989 Conference Paper

Diagnosis with Behavioral Modes

• Johan de Kleer
• Brian C. Williams

Diagnostic tasks involve identifying faulty components from observations of symptomatic device behavior. This paper presents a general diagnostic theory that uses the perspective of diagnosis as identifying consistent modes of behavior, correct or faulty. Our theory draws on the intuitions behind recent diagnostic theories to identify faulty components without necessarily knowing how they fail. To derive additional diagnostic discrimination we use the models for behavioral modes together with probabilistic information about the likelihood of each mode of behavior.

AIJ Journal 1989 Journal Article

Eliminating the fixed predicates from a circumscription

• Johan de Kleer
• Kurt Konolige

Parallel predicate circumscription is the primary circumscriptive technique used in formalizing commonsense reasoning. In this paper we present a direct syntactic construction for transforming any parallel predicate circumscription using fixed predicates into an equivalent one which does not. Thus, we show that predicate circumscription is no more expressive with fixed predicates than without. We extend this result to prioritized circumscription. These results are expected to be useful for comparing circumscription to other nonmonotonic formalisms (such as autoepistemic logic and assumption-based truth maintenance) and for implementing fixed predicates.

NMR Workshop 1989 Conference Paper

Massively Parallel Assumption-Based Truth Maintenance

• Michael Dixon
• Johan de Kleer

Abstract De Kleer's Assumption-based Truth Maintenance System (ATMS) is a propositional inference engine designed to simplify the construction of problem solvers that search complex search spaces efficiently. The ATMS has become a key component of many problem solvers, and often the primary consumer of computational resources. Although considerable effort has gone into designing and optimizing the Lisp implementation, it now appears to be approaching the performance limitations of serial architectures. In this paper we show how the combination of a conventional serial machine and a massively parallel processor can dramatically speed up the ATMS algorithms, providing a very powerful general purpose architecture for problem solving.

AAAI Conference 1988 Conference Paper

A General Labeling Algorithm for Assumption-Based Truth Maintenance

• Johan de Kleer

AIJ Journal 1987 Journal Article

Diagnosing multiple faults

• Johan de Kleer
• Brian C. Williams

Diagnostic tasks require determining the differences between a model of an artifact and the artifact itself. The differences between the manifested behavior of the artifact and the predicted behavior of the model guide the search for the differences between the artifact and its model. The diagnostic procedure presented in this paper is model-based, inferring the behavior of the composite device from knowledge of the structure and function of the individual components comprising the device. The system (GDE—general diagnostic engine) has been implemented and tested on many examples in the domain of troubleshooting digital circuits. This research makes several novel contributions: First, the system diagnoses failures due to multiple faults. Second, failure candidates are represented and manipulated in terms of minimal sets of violated assumptions, resulting in an efficient diagnostic procedure. Third, the diagnostic procedure is incremental, exploiting the iterative nature of diagnosis. Fourth, a clear separation is drawn between diagnosis and behavior prediction, resulting in a domain (and inference procedure) independent diagnostic procedure. Fifth, GDE combines model-based prediction with sequential diagnosis to propose measurements to localize the faults. The normally required conditional probabilities are computed from the structure of the device and models of its components. This capability results from a novel way of incorporating probabilities and information theory into the context mechanism provided by assumption-based truth maintenance.

AIJ Journal 1986 Journal Article

An assumption-based TMS

• Johan de Kleer

This paper presents a new view of problem solving motivated by a new kind of truth maintenance system. Unlike previous truth maintenance systems which were based on manipulating justifications, this truth maintenance system is, in addition, based on manipulating assumption sets. As a consequence it is possible to work effectively and efficiently with inconsistent information, context switching is free, and most backtracking (and all retraction) is avoided. These capabilities motivate a different kind of problem-solving architecture in which multiple potential solutions are explored simultaneously. This architecture is particularly well-suited for tasks where a reasonable fraction of the potential solutions must be explored.

AAAI Conference 1986 Conference Paper

Back to Backtracking: Controlling the ATMS

• Johan de Kleer

The ATMS (Assumption-Based Truth Maintenance System) provides a very general facility for all types of default reasoning. One of the principal advantages of the ATMS is that all of the possible (usually mutually inconsistent) solutions or partial solutions are directly available to the problem solver. By exploiting this capability of the ATMS, the problem solver can efficiently work on all solutions simultaneously and avoid the computational expense of backtracking. However, for some applications this ATMS capability is more of a hindrance than a help and some form of backtracking is necessary. This paper first outlines some of the reasons why backtracking is still necessary, and presents a powerful backtracking algorithm which we have implemented which backtracks more efficiently than other approaches.

AIJ Journal 1986 Journal Article

Extending the ATMS

• Johan de Kleer

The basic assumption-based truth maintenance (ATMS) architecture provides a foundation for implementing various kinds of default reasoning. This paper shows how the basic ATMS is extended to handle defaults and disjunctions of assumptions. These extensions are used to encode disjunctions of nodes, nonmonotonic justifications, normal defaults, nonnormal defaults, and arbitrary propositional formulas.

AIJ Journal 1986 Journal Article

Problem solving with the ATMS

• Johan de Kleer

An assumption-based truth maintenance system provides a very general facility for all types of default reasoning. However, the ATMS is only one component of an overall reasoning system. This paper presents a set of concerns for interfacing with the ATMS, an interface protocol, and an example of a constraint language based on the protocol. The paper concludes with a comparison of the ATMS and the view of problem solving it entails with other approaches.

AAAI Conference 1986 Conference Paper

Reasoning about Multiple Faults

• Johan de Kleer

Diagnostic tasks require determining the differences between a model of an artifact and the artifact itself The differences between the manifested behavior of the artifact and the predicted behavior of the model guide the search for the differences between the artifact and its model. The diagnostic procedure presented in this paper is model-based, inferring the behavior of the composite device from knowledge of the structure and function of the individual components comprising the device. The system (GDE - General Diagnostic Engine) has been implemented and tested on examples in the domain of troubleshooting digital circuits. This research makes several novel contributions: First, the system diagnoses failures due to multiple faults. Second, failure candidates are represented and manipulated in terms of minimal sets of violated assumptions, resulting in an efficient diagnostic procedure. Third, the diagnostic procedure is incremental, reflecting the iterative nature of diagnosis. Finally, a clear separation is drawn between diagnosis and behavior prediction, resulting in a domain (and inference procedure) independent diagnostic procedure.

AIJ Journal 1986 Journal Article

Theories of causal ordering

• Johan de Kleer
• John Seely Brown

This paper is a response to Iwasaki and Simon [14] which criticizes de Kleer and Brown [8]. We argue that many of their criticisms, particularly concerning causality, modeling and stability, originate from the difference of concerns between engineering and economics. Our notion of causality arises from considering the interconnections of components, not equations. When no feedback is present, the ordering produced by our qualitative physics is similar to theirs. However, when feedback is present, our qualitative physics determines a causal ordering around feedback loops as well. Causal ordering is a general technique not only applicable to qualitative reasoning. Therefore we also explore the relationship between causal ordering and propagation of constraints upon which the methods of qualitative physics are based.

AIJ Journal 1985 Journal Article

Building expert systems

• Johan de Kleer

AIJ Journal 1984 Journal Article

A qualitative physics based on confluences

• Johan de Kleer
• John Seely Brown

A qualitative physics predicts and explains the behavior of mechanisms in qualitative terms. The goals for the qualitative physics are (1) to be far simpler than the classical physics and yet retain all the important distinctions (e. g. , state, oscillation, gain, momentum) without invoking the mathematics of continuously varying quantities and differential equations, (2) to produce causal accounts of physical mechanisms that are easy to understand, and (3) to provide the foundations for commonsense models for the next generation of expert systems. This paper presents a fairly encompassing account of qualitative physics. First, we discuss the general subject of naive physics and some of its methodological considerations. Second, we present a framework for modeling the generic behavior of individual components of a device based on the notions of qualitative differential equations (confluences) and qualitative state. This requires developing a qualitative version of the calculus. The modeling primitives induce two kinds of behavior, intrastate and interstate, which are governed by different laws. Third, we present algorithms for determining the behavior of a composite device from the generic behavior of its components. Fourth, we examine a theory of explanation for these predictions based on logical proof. Fifth, we introduce causality as an ontological commitment for explaining how devices behave.

AAAI Conference 1984 Conference Paper

Choices Without Backtracking

• Johan de Kleer

Artificial Intelligence problem solvers are frequently confronted with the necessity to make choices among equally plausible alternatives. These may concern the choice of which goal to try to achieve next, which priority to assign to a task or which plausible inference to draw from incomplete data. Choices can be wrong: later problem solving may determine that an earlier choice was incorrect. In such cases most problem solvers invoke some form of backtracking to undo the faulty choice, retract the inferences that were made from that choice and make some other choice. This paper discusses a method of dealing with choice that does not involve any backtracking yet explores no more alternatives than the best backtracking schemes. It has an additional advantage over backtracking schemes that it is possible to easily compare two alternative incompatible choices - this cannot be done in backtracking schemes because of their necessity of requiring a globally consistent set of assertions.

AIJ Journal 1984 Journal Article

How circuits work

• Johan de Kleer

This paper presents a theory of commonsense understanding of the behavior of electronic circuits. It is based on the intuitive qualitative reasoning electrical engineers use when they analyze circuits. This intuitive reasoning provides a great deal of important information about the operation of the circuit, which although qualitative in nature, describes important quantitative aspects of circuit functioning (feedback paths, stability, impedance and gain estimates, etc.). One aspect of the theory, causal analysis, describes how the behavior of the individual components can be combined to explain the behavior of composite systems. Another aspect of the theory, teleological analysis, describes how the notion that the system has a purpose can be used to structure and aid this causal analysis. The theory is implemented in a computer program, EQUAL, which, given a circuit topology, can construct by qualitative causal analysis a description of the mechanism by which the circuit operates. This mechanism is then parsed by a grammar for circuit functions.

AAAI Conference 1984 Conference Paper

Qualitative Reasoning With Higher-Order Derivatives

• Johan de Kleer

The goals of qualitative physics are to identify the distinctions and laws which govern qualitative behavior of devices such that it is possible to predict and explain the behavior of physical devices without recourse to quantitative methods. Although qualitative analysis lacks quantitative information, it predicts significant characteristics of device functioning such as feedback, ringing oscillation, etc. This paper defines higher-order qualitative derivatives and uses them to formulate six fundamental laws which govern the gross-time behavior of physical devices. These qualitative laws are based on the Mean Value Theorem and Taylor’s Expansion of the quantitative calculus. They substitute for what often requires sophisticated problem-solving. We claim they are the best that can be achieved relying on qualitative information.

AIJ Journal 1984 Journal Article

The fifth generation: Artificial intelligence and Japan's computer challenge to the world

• Johan de Kleer

AAAI Conference 1982 Conference Paper

Foundations of Envisioning

• Johan de Kleer

This paper explores a particular kind of qualitative reasoning, called envisioning, that is capable of producing causal explanations for device behavior. It has been implemented in a computer program, ENVISION, which can analyze a wide variety of thermal, fluid, electrical, translational and rotational devices. Rather than present the technical details of the envisioning process, this paper examines the theoretical foundations upon which it is built. Many of these considerations are ones that any builder of qualitative reasoning systems must pay attention to. Two such considerations are explanation and robustness: What notion of causality is adequate for causal explanations of device behavior? How can there be any confidence in the analysis of a novel device?