Engineering Commons^™

Understanding The Scalability Of Bayesian Network Inference Using Clique Tree Growth Curves, Ole J. Mengshoel

Ole J Mengshoel

One of the main approaches to performing computation in Bayesian networks (BNs) is clique tree clustering and propagation. The clique tree approach consists of propagation in a clique tree compiled from a BN, and while it was introduced in the 1980s, there is still a lack of understanding of how clique tree computation time depends on variations in BN size and structure. In this article, we improve this understanding by developing an approach to characterizing clique tree growth as a function of parameters that can be computed in polynomial time from BNs, specifically: (i) the ratio of the number of …

Portfolios In Stochastic Local Search: Efficiently Computing Most Probable Explanations In Bayesian Networks, Ole J. Mengshoel, D Roth, D Wilkins

Ole J Mengshoel

Portfolio methods support the combination of different algorithms and heuristics, including stochastic local search (SLS) heuristics, and have been identified as a promising approach to solve computationally hard problems. While successful in experiments, theoretical foundations and analytical results for portfolio-based SLS heuristics are less developed. This article aims to improve the understanding of the role of portfolios of heuristics in SLS. We emphasize the problem of computing most probable explanations (MPEs) in Bayesian networks (BNs). Algorithmically, we discuss a portfolio-based SLS algorithm for MPE computation, Stochastic Greedy Search (SGS). SGS supports the integration of different initialization operators (or initialization heuristics) …

Diagnosing Intermittent And Persistent Faults Using Static Bayesian Networks, Ole J. Mengshoel, Brian Ricks

Ole J Mengshoel

Both intermittent and persistent faults may occur in a wide range of systems. We present in this paper the introduction of intermittent fault handling techniques into ProDiagnose, an algorithm that previously only handled persistent faults. We discuss novel algorithmic techniques as well as how our static Bayesian networks help diagnose, in an integrated manner, a range of intermittent and persistent faults. Through experiments with data from the ADAPT electrical power system test bed, generated as part of the Second International Diagnostic Competition (DXC-10), we show that this novel variant of ProDiagnose diagnoses intermittent faults accurately and quickly, while maintaining strong …

Developing Large-Scale Bayesian Networks By Composition: Fault Diagnosis Of Electrical Power Systems In Aircraft And Spacecraft, Ole J. Mengshoel, Scott Poll, Tolga Kurtoglu

Ole J Mengshoel

In this paper, we investigate the use of Bayesian networks to construct large-scale diagnostic systems. In particular, we consider the development of large-scale Bayesian networks by composition. This compositional approach reflects how (often redundant) subsystems are architected to form systems such as electrical power systems. We develop high-level specifiations, Bayesian networks, clique trees, and arithmetic circuits representing 24 different electrical power systems. The largest among these 24 Bayesian networks contains over 1,000 random variables. Another BN represents the real-world electrical power system ADAPT, which is representative of electrical power systems deployed in aerospace vehicles. In addition to demonstrating the scalability …

Diagnosis And Reconfiguration Using Bayesian Networks: An Electrical Power System Case Study, W. Bradley Knox, Ole J. Mengshoel

Ole J Mengshoel

Automated diagnosis and reconfiguration are important computational techniques that aim to minimize human intervention in autonomous systems. In this paper, we develop novel techniques and models in the context of diagnosis and reconfiguration reasoning using causal Bayesian networks (BNs). We take as starting point a successful diagnostic approach, using a static BN developed for a real-world electrical power system. We discuss in this paper the extension of this diagnostic approach along two dimensions, namely: (i) from a static BN to a dynamic BN; and (ii) from a diagnostic task to a reconfiguration task.

More specifically, we discuss the auto-generation of …

The Diagnostic Challenge Competition: Probabilistic Techniques For Fault Diagnosis In Electrical Power Systems, Brian W. Ricks, Ole J. Mengshoel

Ole J Mengshoel

Constraint Handling Using Tournament Selection: Abductive Inference In Partly Deterministic Bayesian Network, Severino F. Galan, Ole J. Mengshoel

Ole J Mengshoel

Constraints occur in many application areas of interest to evolutionary computation. The area considered here is Bayesian networks (BNs), which is a probability-based method for representing and reasoning with uncertain knowledge. This work deals with constraints in BNs and investigates how tournament selection can be adapted to better process such constraints in the context of abductive inference. Abductive inference in BNs consists of finding the most probable explanation given some evidence. Since exact abductive inference is NP-hard, several approximate approaches to this inference task have been developed. One of them applies evolutionary techniques in order to find optimal or close-to-optimal …

Methods For Probabilistic Fault Diagnosis: An Electrical Power System Case Study, Brian Ricks, Ole J. Mengshoel

Ole J Mengshoel

Health management systems that more accurately and quickly diagnose faults that may occur in different technical systems on-board a vehicle will play a key role in the success of future NASA missions. We discuss in this paper the diagnosis of abrupt continuous (or parametric) faults within the context of probabilistic graphical models, more specifically Bayesian networks that are compiled to arithmetic circuits. This paper extends our previous research, within the same probabilistic setting, on diagnosis of abrupt discrete faults. Our approach and diagnostic algorithm ProDiagnose are domain-independent; however we use an electrical power system testbed called ADAPT as a case …

A Framework For Systematic Benchmarking Of Monitoring And Diagnostic Systems, Tolga Kurtoglu, Ole J. Mengshoel, Scott Poll

Ole J Mengshoel

In this paper, we present an architecture and a formal framework to be used for systematic benchmarking of monitoring and diagnostic systems and for producing comparable performance assessments of different diagnostic technologies. The framework defines a number of standardized specifications, which include a fault catalog, a library of modular test scenarios, and a common protocol for gathering and processing diagnostic data. At the center of the framework are 13 benchmarking metric definitions. The calculation of metrics is illustrated on a probabilistic model-based diagnosis algorithms utilizing Bayesian reasoning techniques. The diagnosed system is a real-world electrical power system, namely the Advanced …

Using Bayesian Networks For Candidate Generation In Consistency-Based Diagnosis, Sriram Narasimhan, Ole J. Mengshoel

Ole J Mengshoel

Consistency-based diagnosis relies on the computation of discrepancies between model predictions and sensor observations. The traditional assumption that these discrepancies can be detected accurately (by means of thresholding for example) is in many cases reasonable and leads to strong performance. However, in situations of substantial uncertainty (due, for example, to sensor noise or model abstraction), more robust schemes need to be designed to make a binary decision on whether predictions are consistent with observations or not. However, if an accurate binary decision is not made, there are risks of occurrence of false alarms and missed alarms. Moreover when multiple sensors …

Understanding The Role Of Noise In Stochastic Local Search: Analysis And Experiments, Ole J. Mengshoel

Ole J Mengshoel

Stochastic local search (SLS) algorithms have recently been proven to be among the best approaches to solving computationally hard problems. SLS algorithms typically have a number of parameters, optimized empirically, that characterize and determine their performance. In this article, we focus on the noise parameter. The theoretical foundation of SLS, including an understanding of how to the optimal noise varies with problem difficulty, is lagging compared to the strong empirical results obtained using these algorithms. A purely empirical approach to understanding and optimizing SLS noise, as problem instances vary, can be very computationally intensive. To complement existing experimental results, we …

Sensor Validation Using Bayesian Networks, Ole J. Mengshoel, Adnan Darwiche, Serdar Uckun

Ole J Mengshoel

One of NASA’s key mission requirements is robust state estimation. Sensing, using a wide range of sensors and sensor fusion approaches, plays a central role in robust state estimation, and there is a need to diagnose sensor failure as well as component failure. Sensor validation techniques address this problem: given a vector of sensor readings, decide whether sensors have failed, therefore producing bad data. We take in this paper a probabilistic approach, using Bayesian networks, to diagnosis and sensor validation, and investigate several relevant but slightly different Bayesian network queries. We emphasize that onboard inference can be performed on a …

Diagnosing Faults In Electrical Power Systems Of Spacecraft And Aircraft, Ole J. Mengshoel, Adnan Darwichse, Keith Cascio, Mark Chavira, Scott Poll, Serdar Uckun

Ole J Mengshoel

Electrical power systems play a critical role in spacecraft and aircraft. This paper discusses our development of a diagnostic capability for an electrical power system testbed, ADAPT, using probalistic techniques. In the context of ADAPT, we present two challenges, regarding modelling and real-time performance, often encountered in real-world diagnostic applications. To meet the modelling challenge, we discuss our novel high-level specification language which supports auto-generation of Bayesian networks. To meet the real-time challenge, we compile Bayesian networks intro arithmetic circuits. Arithmetic circuits typically have small footprints and are optimized for the real-time avionics systems found in spacecraft and aircraft. Using …

The Crowding Approach To Niching In Genetic Algorithms, Ole J. Mengshoel, David E. Goldberg

Ole J Mengshoel

A wide range of niching techniques have been investigated in evolutionary and genetic algorithms. In this article, we focus on niching using crowding techniques in the context of what we call local tournament algorithms. In addition to deterministic and probabilistic crowding, the family of local tournament algorithms includes the Metropolis algorithm, simulated annealing, restricted tournament selection, and parallel recombinative simulated annealing. We describe an algorithmic and analytical framework which is applicable to a wide range of crowding algorithms. As an example of utilizing this framework, we present and analyze the probabilistic crowding niching algorithm. Like the closely related deterministic crowding …

Designing Resource-Bounded Reasoners Using Bayesian Networks: System Health Monitoring And Diagnosis, Ole J. Mengshoel

Ole J Mengshoel

In this work we are concerned with the conceptual design of large-scale diagnostic and health management systems that use Bayesian networks. While they are potentially powerful, improperly designed Bayesian networks can result in too high memory requirements or too long inference times, to they point where they may not be acceptable for real-time diagnosis and health management in resource-bounded systems such as NASA’s aerospace vehicles. We investigate the clique tree clustering approach to Bayesian network inference, where increasing the size and connectivity of a Bayesian network typically also increases clique tree size. This paper combines techniques for analytically characterizing clique …

Controlled Generation Of Hard And Easy Bayesian Networks: Impact On Maximal Clique Size In Tree Clustering, Ole J. Mengshoel, David C. Wilkins, Dan Roth

Ole J Mengshoel

This article presents and analyzes algorithms that systematically generate random Bayesian networks of varying difficulty levels, with respect to inference using tree clustering. The results are relevant to research on efficient Bayesian network inference, such as computing a most probable explanation or belief updating, since they allow controlled experimentation to determine the impact of improvements to inference algorithms. The results are also relevant to research on machine learning of Bayesian networks, since they support controlled generation of a large number of data sets at a given difficulty level. Our generation algorithms, called BPART and MPART, support controlled but random construction …

Probabilistic Crowding: Deterministic Crowding With Probabilistic Replacement, Ole J. Mengshoel, David E. Goldberg

Ole J Mengshoel

This paper presents a novel niching algorithm, probabilistic crowding. Like its predecessor deterministic crowding, probabilistic crowding is fast, simple, and requires no parameters beyond that of the classical GA. In probabilistic crowding, subpopulations are maintained reliably, and we analyze and predict how this maintenance takes place.

This paper also identifies probabilistic crowding as a member of a family of algorithms, which we call integrated tournament algorithms. Integrated tournament algorithms also include deterministic crowding, restricted tournament selection, elitist recombination, parallel recombinative simulated annealing, the Metropolis algorithm, and simulated annealing.