Gregory Provan

AAAI Conference 2014 Conference Paper

Diagnosing Analogue Linear Systems Using Dynamic Topological Reconfiguration

• Alexander Feldman
• Gregory Provan

Fault diagnosis of analogue linear systems poses many challenges, such as the size of the search space that must be explored and the possibility of simulation instabilities introduced by particular fault classes. We study a novel algorithm that addresses both problems. This algorithm dynamically modifies the simulation model during diagnosis by pruning parametrized components that cause discontinuity in the model. We provide a theoretical framework for predicting the speedups, which depends on the topology of the model. We empirically validate the theoretical predictions through extensive experimentation on a benchmark of circuits.

IJCAI Conference 2013 Conference Paper

Machine-Learning-Based Circuit Synthesis

• Lior Rokach
• Meir Kalech
• Gregory Provan
• Alexander Feldman

Multi-level logic synthesis is a problem of immense practical significance, and is a key to developing circuits that optimize a number of parameters, such as depth, energy dissipation, reliability, etc. The problem can be defined as the task of taking a collection of components from which one wants to synthesize a circuit that optimizes a particular objective function. This problem is computationally hard, and there are very few automated approaches for its solution. To solve this problem we propose an algorithm, called Circuit-Decomposition Engine (CDE), that is based on learning decision trees, and uses a greedy approach for function learning. We empirically demonstrate that CDE, when given a library of different component types, can learn the function of Disjunctive Normal Form (DNF) Boolean representations and synthesize circuit structure using the input library. We compare the structure of the synthesized circuits with that of well-known circuits using a range of circuit similarity metrics.

AAAI Conference 2012 Conference Paper

Exploring the Duality in Conflict-Directed Model-Based Diagnosis

• Roni Stern
• Meir Kalech
• Alexander Feldman
• Gregory Provan

AAAI Conference 2011 Conference Paper

Stochastic Model Predictive Controller for the Integration of Building Use and Temperature Regulation

• Alie El-Din Mady
• Gregory Provan
• Conor Ryan
• Kenneth Brown

The aim of a modern Building Automation System (BAS) is to enhance interactive control strategies for energy efficiency and user comfort. In this context, we develop a novel control algorithm that uses a stochastic building occupancy model to improve mean energy efficiency while minimizing expected discomfort. We compare by simulation our Stochastic Model Predictive Control (SMPC) strategy to the standard heating control method to empirically demonstrate a 4. 3% reduction in energy use and 38. 3% reduction in expected discomfort.

IJCAI Conference 2009 Conference Paper

• Alexander Feldman
• Gregory Provan
• Arjan J. C. van Gemund

Model-Based Diagnosis (MBD) approaches often yield a large number of diagnoses, severely limiting their practical utility. This paper presents a novel active testing approach based on MBD techniques, called FRACTAL (FRamework for ACtive Testing ALgorithms), which, given a system description, computes a sequence of control settings for reducing the number of diagnoses. The approach complements probing, sequential diagnosis, and ATPG, and applies to systems where additional tests are restricted to setting a subset of the existing system inputs while observing the existing outputs. This paper evaluates the optimality of FRACTAL, both theoretically and empirically. FRACTAL generates test vectors using a greedy, next-best strategy and a low-cost approximation of diagnostic information entropy. Further, the approximate sequence computed by FRACTAL’s greedy approach is optimal over all poly-time approximation algorithms, a fact which we confirm empirically. Extensive experimentation with ISCAS85 combinational circuits shows that FRACTAL reduces the number of remaining diagnoses according to a steep geometric decay function, even when only a fraction of inputs are available for active testing.

IJCAI Conference 2009 Conference Paper

• Alexander Feldman
• Gregory Provan
• Arjan J. C. van Gemund

IJCAI Conference 2007 Conference Paper

• Gregory Provan
• Jun Wang

The task of model-based diagnosis is NP-complete, but it is not known whether it is computationally difficult for the "average" real-world system. There has been no systematic study of the complexity of diagnosing real-world problems, and few good benchmarks exist to test this. Real-world-graphs, a mathematical framework that has been proposed as a model for complex systems, have empirically been shown to capture several topological roperties of real-world systems. We describe the adequacy with which a real-world-graph can characterise the complexity of model-based diagnostic inference on real-world systems. We empirically compare the inference complexity of diagnosing models automatically generated using the real-world-graph framework with comparable models from well-known ISCAS circuit benchmarks. We identify parameters necessary for the real-world-graph framework to generate benchmark diagnosis circuit models with realistic properties.

KR Conference 2004 Conference Paper

Inferential Complexity Control for Model-Based Abduction

• Gregory Provan

We describe a technique for speeding up inference for model-based abduction tasks that trades off inference time and/or space for the fraction of queries correctly answered. We compile a knowledge base (for which inference may be intractable) into a set of rules that cover the most likely queries using simple criteria that do not entail extensive knowledge engineering effort, such as subset-minimal or most probable query-responses. We demonstrate this approach on the abduction task of model-based diagnosis, and show that this approach can predictably produce order-of-magnitude reductions in time and memory requirements for abductive tasks in which the queries have skewed distributions; for example, in diagnosis the faults are skewed towards being highly unlikely.

IJCAI Conference 2003 Conference Paper

A Novel Framework for Integrating Discrete Event System Control and Diagnosis

• Gregory Provan

KR Conference 2002 Conference Paper

A Model-Based Diagnosis Framework for Distributed Embedded Systems

• Gregory Provan

AIJ Journal 1996 Journal Article

The sensitivity of belief networks to imprecise probabilities: an experimental investigation

• Malcolm Pradhan
• Max Henrion
• Gregory Provan
• Brendan Del Favero
• Kurt Huang

Bayesian belief networks are being increasingly used as a knowledge representation for reasoning under uncertainty. Some researchers have questioned the practicality of obtaining the numerical probabilities with sufficient precision to create belief networks for large-scale applications. In this work, we investigate how precise the probabilities need to be by measuring how imprecision in the probabilities affects diagnostic performance. We conducted a series of experiments on a set of real-world belief networks for medical diagnosis in liver and bile disease. We examined the effects on diagnostic performance of (1) varying the mappings from qualitative frequency weights into numerical probabilities, (2) adding random noise to the numerical probabilities, (3) simplifying from quaternary domains for diseases and findings—absent, mild, moderate, and severe—to binary domains—absent and present, and (4) using test cases that contain diseases outside the network. We found that even extreme differences in the probability mappings and large amounts of noise lead to only modest reductions in diagnostic performance. We found no significant effect of the simplification from quaternary to binary representation. We also found that outside diseases degraded performance modestly. Overall, these findings indicate that even highly imprecise input probabilities may not impair diagnostic performance significantly, and that simple binary representations may often be adequate. These findings of robustness suggest that belief networks are a practical representation without requiring undue precision.