Computing Energy-Optimal Tests using DNNF Graphs

##plugins.themes.bootstrap3.article.main##

##plugins.themes.bootstrap3.article.sidebar##

Anika Schumann Martin Sachenbacher

Abstract

The goal of testing is to discriminate between multiple hypotheses about a system – for example, different fault diagnoses of an HVAC system – by applying input patterns and verifying or falsifying the hypotheses from the observed outputs. Definitely discriminating tests (DDTs) are those input patterns that are guaranteed to discriminate between different hypotheses of non-deterministic systems. Finding DDTs is important in practice, but can be very expensive . Even more challenging is the problem of finding a DDT that minimizes the energy consumption of the testing process, i.e., an input pattern that can be enforced with minimal energy consumption and that is a DDT. This paper addresses both problems. We show how we can transform a given problem into a Boolean structure in decomposable negation normal form (DNNF), and extract from it a Boolean formula whose models correspond to DDTs. This allows us to harness recent advances in both knowledge compilation and satisfiability for efficient and scalable DDT computation in practice. Furthermore, we show how we can generate a DNNF structure compactly encoding all DDTs of the problem and use it to obtain an energy-optimal DDT in time linear in the size of the structure.

How to Cite

Schumann, A. ., & Sachenbacher, M. . (2010). Computing Energy-Optimal Tests using DNNF Graphs. Annual Conference of the PHM Society, 2(2). https://doi.org/10.36001/phmconf.2010.v2i1.1912
Abstract 5 | PDF Downloads 1

##plugins.themes.bootstrap3.article.details##

Keywords

diagnosis, model-based testing, SAT, DNNF graphs

References
(Alur et al., 1995) R. Alur, C. Courcoubetis, and M. Yannakakis. Distinguishing tests for nondeter- ministic and probabilistic machines. In Proceedings of the ACM Symposium on Theory of Computing, pages 363–372, 1995.
(Boroday et al., 2007) S. Boroday, A. Petrenko, and R. Groz. Can a model checker generate tests for non-deterministic systems? Electronic Notes in Theoretical Computer Science, 190:3–19, 2007.
(Darwiche and Marquis, 2002) A. Darwiche and P. Marquis. A knowledge compilation map. Journal of Artificial Intelligence Research, 17:229–264, 2002.
(Darwiche, 1998) Adnan Darwiche. Model-based diagnosis using structured system descriptions. Journal of Artificial Intelligence Research, 8:165–222, 1998.
(Darwiche, 2001) A. Darwiche. Decomposable negation normal form. Journal of the ACM, 48(4):608– 647, 2001.
(Darwiche, 2005) A. Darwiche. The C2D compiler user manual. Technical report, Comp. Sci. UCLA, 2005.
(Esser and Struss, 2007) M. Esser and P. Struss. Fault-model-based test generation for embedded software. In Proceedings of the 20th International Joint Conference on Artificial Intelligence (IJCAI), pages 342–347, 2007.
(Heinz and Sachenbacher, 2009) S. Heinz and M. Sachenbacher. Using model counting to find optimal distinguishing tests. In Proceedings of the Sixth International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (CPAIOR), pages 117–131, 2009.
(Huang, 2007) J. Huang. A case for simple SAT solvers. In Proceedings of the 13th International Conference on Principles and Practice of Constraint Programming (CP), pages 839–846, 2007.
(Lunze and Nixdorf, 2001) J. Lunze and B. Nixdorf. Representation of hybrid systems by means of stochastic automata. Mathematical and Computer Modeling of Dynamical Systems , 4:383–422, 2001.
(Luo et al., 2007) J. Luo, K. Pattipati, L. Qiao, and S. Chigusa. An integrated diagnostic development process for automotive engine control systems. IEEE Trans. on Systems, Man, and Cybernetics, 37(6):1163–1173, 2007.
(Sachenbacher and Schwoon, 2008) M. Sachen- bacher and S. Schwoon. Model-based testing using quantified CSPs. In ECAI-08 Workshop on Model-based Systems, 2008.
(Schumann et al., 2009) A. Schumann, M. Sachen- bacher, and J. Huang. Constraint-based optimal testing using DNNF graphs. In Proceedings of the 15th International Conference on Principles and Practice of Constraint Programming (CP), pages 731–745, 2009.
(Schumann et al., 2010) A. Schumann, J. Huang, and M. Sachenbacher. Computing cost-optimal definitely discriminating tests. In Proceedings of the 24th National Conference on Artificial Intelligence (AAAI), 2010.
(Struss, 1994) P. Struss. Testing physical systems. In
Proceedings of the 12th National Conference on Artificial Intelligence (AAAI-94), pages 251–256, 1994.
(Struss, 2007) P. Struss. Model-based optimization of testing through reduction of stimuli. In Proceedings of the 20th International Joint Conference on Artificial Intelligence (IJCAI), pages 593–598, 2007.
(Torta and D. Theseider Dupré, 2008) G. Torta and L. Anselma D. Theseider Dupré. Hypothesis discrimination with abstractions based on observation and action costs. In Proceedings of the 19th International Workshop on Principles of Diagnosis (DX- 08), pages 189–196, 2008.
(Tseitin, 1968) G. Tseitin. On the complexity of derivation in propositional calculus. Studies in Constructive Mathematics and Mathematical Logic, pages 115–125, 1968.
(Venturini and Provan, 2008) A. Venturini and G. Provan. Incremental algorithms for approximate compilation. In Proceedings of the 23rd National Conference on Artificial Intelligence (AAAI-08), 2008.
(Walsh,2000) T.Walsh.SATvs.CSP.InProceedings of the Sixth International Conference on Principles and Practice of Constraint Programming (CP), pages 441–456, 2000.
Section
Poster Presentations