Approximate Compilation for Embedded Model-based Reasoning

Barry O'Sullivan, Gregory M. ProvanAAAI 2006

Introduction

Embedded systems, the computational cores of devices ranging from medical monitors to spacecraft, frequently need to perform complex reasoning tasks such as self-diagnosis and autonomous reconfiguration. These tasks are typically NP-hard, making real-time execution challenging. To overcome this, researchers often employ knowledge compilation, a technique that pre-processes a problem into a compact, query-efficient format.

However, these compiled "cheat sheets" can grow exponentially in size, often exceeding the limited RAM and flash storage available in embedded hardware. This paper introduces approximate compilation, a method that trades off the completeness of a knowledge base for significant memory savings by focusing on the most likely or "preferred" solutions.

Methodology: Valuation-Based Pruning

The authors propose a valuation-based approach to compilation. Instead of treating every possible solution as equally critical, they assign a "valuation" to each environment—representing probability (e.g., the likelihood of a specific component failure), cost, or user preference.

The core mechanism is thresholding: a parameter (often denoted as $\phi$ or $\epsilon$) is defined, and only solutions with a valuation exceeding this threshold are included in the final compiled form. This allows for the creation of "Threshold Prime Implicates," which are the simplest logical consequences of a theory that meet the importance criteria.

Comparison between a Full DNNF and a Threshold-Bounded DNNF where low-valuation edges are pruned.

To evaluate the effectiveness of this approximation, the authors define two key metrics:

  • Valuation Coverage Ratio ($\eta$): The percentage of the total "importance" or probability mass captured by the approximate compilation.
  • Memory Reduction Ratio ($\lambda$): The size of the approximate version relative to the full compilation.

Experimental Evaluation

The technique was tested using synthetically generated Probabilistic Constraint Satisfaction Problems (CSPs). These problems involved 10 variables with binary domains, with solution sets ranging from 10% to 50% of all possible assignments. Random probabilities were assigned to variable assignments to simulate the "skewed" likelihoods often found in real-world diagnostic scenarios.

Key Results and Tradeoffs

The empirical results confirm that approximate compilation enables a "graceful tradeoff" between reasoning power and resource consumption. As shown in the performance curves, significant memory savings are possible with minimal loss in coverage.

Tradeoff between Coverage Ratio and Memory Ratio across different threshold values.

Key findings include:

  • High Efficiency in Skewed Distributions: The method is most effective when a few solutions are much more likely than others. In many scenarios, the authors achieved over 80% coverage while using only 20% of the space required for a full compilation.
  • Soundness: The resulting knowledge base remains sound. It never provides an incorrect answer; it simply may not have an answer for extremely rare, low-probability events that fell below the pruning threshold.
  • Engineering Flexibility: This approach allows engineers to "dial back" the threshold until the knowledge base fits the specific hardware constraints of a target device, preventing compilation failure due to memory overflow.

Conclusion and Future Work

Approximate compilation offers a practical solution for deploying advanced model-based reasoning on resource-constrained embedded systems. While this study utilized synthetic datasets to establish baseline performance, the results suggest that the technique is robust, especially for systems with skewed probability distributions.

Future research will focus on scaling these algorithms to handle real-world problems with hundreds or thousands of variables. Additionally, the authors plan to explore more advanced compilation targets, such as Decomposable Negation Normal Form (DNNF) and Ordered Binary Decision Diagrams (OBDDs), to further enhance compression ratios.

Summary updated

BibTeX
@inproceedings{osullivan2006approximate,
  author = {Barry O'Sullivan and Gregory M. Provan},
  title = {{Approximate Compilation for Embedded Model-based Reasoning}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2006},
}
Figure