Sound, Complete, Linear-Space, Best-First Diagnosis Search

• URL: http://arxiv.org/abs/2009.12190v2
• Date: Thu, 4 Aug 2022 13:22:56 GMT
• Title: Sound, Complete, Linear-Space, Best-First Diagnosis Search
• Authors: Patrick Rodler
• Abstract summary: We propose RBF-HS, a diagnostic search method based on Korf's well-known RBFS algorithm. RBF-HS can enumerate an arbitrary fixed number of fault explanations in best-first order within linear space bounds.
• Score: 0.0
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: Various model-based diagnosis scenarios require the computation of the most preferred fault explanations. Existing algorithms that are sound (i.e., output only actual fault explanations) and complete (i.e., can return all explanations), however, require exponential space to achieve this task. As a remedy, to enable successful diagnosis on memory-restricted devices and for memory-intensive problem cases, we propose RBF-HS, a diagnostic search method based on Korf's well-known RBFS algorithm. RBF-HS can enumerate an arbitrary fixed number of fault explanations in best-first order within linear space bounds, without sacrificing the desirable soundness or completeness properties. Evaluations using real-world diagnosis cases show that RBF-HS, when used to compute minimum-cardinality fault explanations, in most cases saves substantial space (up to 98 %) while requiring only reasonably more or even less time than Reiter's HS-Tree, a commonly used and as generally applicable sound, complete and best-first diagnosis search.

Related papers

• CFaults: Model-Based Diagnosis for Fault Localization in C Programs with Multiple Test Cases [0.0]
  This paper introduces a novel fault localization approach for C programs with multiple faults. CFaults leverages Model-Based Diagnosis (MBD) with multiple observations and aggregates all failing test cases into a unified MaxSAT formula. Experimental results on two benchmark sets of C programs, TCAS and C-Pack-IPAs, show that CFaults is faster than other FBFL approaches.
  arXiv  Detail & Related papers  (2024-07-12T15:14:49Z)
• A More General Theory of Diagnosis from First Principles [2.693342141713236]
  We generalise Reiter's theory to be agnostic to the types of systems and diagnoses considered. computing the minimal diagnosis is achieved by exploring the space of diagnosis hypotheses. We present two implementations of these algorithms, using test solvers based on satisfiability and search.
  arXiv  Detail & Related papers  (2023-09-28T05:47:52Z)
• FastDiagP: An Algorithm for Parallelized Direct Diagnosis [64.65251961564606]
  FastDiag is a typical direct diagnosis algorithm that supports diagnosis calculation without predetermining conflicts. We propose a novel algorithm, so-called FastDiagP, which is based on the idea of speculative programming. This mechanism helps to provide consistency checks with fast answers and boosts the algorithm's runtime performance.
  arXiv  Detail & Related papers  (2023-05-11T16:26:23Z)
• MissDAG: Causal Discovery in the Presence of Missing Data with Continuous Additive Noise Models [78.72682320019737]
  We develop a general method, which we call MissDAG, to perform causal discovery from data with incomplete observations. MissDAG maximizes the expected likelihood of the visible part of observations under the expectation-maximization framework. We demonstrate the flexibility of MissDAG for incorporating various causal discovery algorithms and its efficacy through extensive simulations and real data experiments.
  arXiv  Detail & Related papers  (2022-05-27T09:59:46Z)
• Anytime Diagnosis for Reconfiguration [52.77024349608834]
  We introduce and analyze FlexDiag which is an anytime direct diagnosis approach. We evaluate the algorithm with regard to performance and diagnosis quality using a configuration benchmark from the domain of feature models and an industrial configuration knowledge base from the automotive domain.
  arXiv  Detail & Related papers  (2021-02-19T11:45:52Z)
• An Efficient Diagnosis Algorithm for Inconsistent Constraint Sets [68.8204255655161]
  We introduce a divide-and-conquer based diagnosis algorithm (FastDiag) which identifies minimal sets of faulty constraints in an over-constrained problem. We compare FastDiag with the conflict-directed calculation of hitting sets and present an in-depth performance analysis.
  arXiv  Detail & Related papers  (2021-02-17T19:55:42Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  This paper investigates the classical integer least-squares problem which estimates signals integer from linear models. The problem is NP-hard and often arises in diverse applications such as signal processing, bioinformatics, communications and machine learning. We propose a general hyper-accelerated tree search (HATS) algorithm by employing a deep neural network to estimate the optimal estimation for the underlying simplified memory-bounded A* algorithm.
  arXiv  Detail & Related papers  (2021-01-07T08:00:02Z)
• DynamicHS: Streamlining Reiter's Hitting-Set Tree for Sequential Diagnosis [0.0]
  We propose DynamicHS, a variant of HS-Tree that maintains state throughout the diagnostic session. We prove the reasonability of DynamicHS and testify its clear superiority to HS-Tree wrt. computation time.
  arXiv  Detail & Related papers  (2020-12-21T01:59:19Z)
• RBF-HS: Recursive Best-First Hitting Set Search [0.0]
  We propose two novel diagnostic search algorithms. RBF-HS (Recursive Best-First Hitting Set Search) and HBF-HS (Hybrid Best-First Hitting Set Search) For the computation of minimum-cardinality fault explanations, we find that RBF-HS reduces memory requirements substantially.
  arXiv  Detail & Related papers  (2020-10-08T22:09:39Z)
• Progressively Pretrained Dense Corpus Index for Open-Domain Question Answering [87.32442219333046]
  We propose a simple and resource-efficient method to pretrain the paragraph encoder. Our method outperforms an existing dense retrieval method that uses 7 times more computational resources for pretraining.
  arXiv  Detail & Related papers  (2020-04-30T18:09:50Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.