A Diagnosis Algorithm for Inconsistent Constraint Sets
##plugins.themes.bootstrap3.article.main##
##plugins.themes.bootstrap3.article.sidebar##
Abstract
Constraint sets can become inconsistent in different contexts. For example, during a configuration session the set of customer requirements can become inconsistent with the configuration knowledge base. Another example is the engineering phase of a configuration knowledge base where the underlying constraints can become inconsistent with a set of test cases. In such situations we are in the need of techniques that support the identification of minimal sets of constraints that have to be adapted or deleted in order to restore consistency. In this paper we introduce a divide-and-conquer based diagnosis algorithm (FastDiag) which identifies minimal sets of faulty constraints in an over-constrained problem. This algorithm is specifically applicable in scenarios where the efficient identification of leading (preferred) diagnoses is crucial. We compare the performance of FastDiag with the conflict-directed calculation of hitting sets and present an in-depth performance analysis that shows the advantages of our approach.
How to Cite
##plugins.themes.bootstrap3.article.details##
Model-based diagnosis, Configuration, Constraint Satisfaction
(Belanger, 2005) F. Belanger. A conjoint analysis of online consumer satisfaction. Journal of Electronic Commerce Research, 6:95–111, 2005.
(Castillo et al., 2005) L. Castillo, D. Borrajo, and M. Salido. Planning, Scheduling and Constraint Satisfaction: From Theory to Practice. IOS Press, 2005.
(Chen and Suen, 2003) Z. Chen and C. Suen. Measuring the complexity of rule-based expert systems. Expert Systems with Applications, 7(4):467–481, 2003.
(DeKleer et al., 1992) J. DeKleer, A. Mackworth, and R. Reiter. Characterizing diagnoses and systems. AI Journal, 56(2–3):197–222, 1992.
(DeKleer, 1990) J. DeKleer. Using crude probability estimates to guide diagnosis. AI Journal, 45(3):381–391, 1990.
(Felfernig et al., 2004) A. Felfernig, G. Friedrich, D. Jannach, and M. Stumptner. Consistency-based diagnosis of configuration knowledge bases. AI Journal, 152(2):213–234, 2004.
(Felfernig et al., 2007) A. Felfernig, G. Friedrich, K. Isak, K. Shchekotykhin, E. Teppan, and D. Jannach. Automated debugging of recommender user interface descriptions. Journal of Applied Intelligence, 31(1):1–14, 2007.
(Felfernig et al., 2008) A. Felfernig, G. Friedrich, E. Teppan, and K. Isak. Intelligent debugging and repair of utility constraint sets in knowledge-based recommender applications. In 13th ACM International Conference on Intelligent User Interfaces (IUI’08), pages 218–226, 2008.
(Felfernig et al., 2009) A. Felfernig, G. Friedrich, M. Schubert, M. Mandl, M. Mairitsch, and E. Tep- pan. Plausible repairs for inconsistent requirements. In 21st International Joint Conference on Artificial Intelligence (IJCAI’09), pages 791–796, 2009.
(Fleischanderl et al., 1998) G. Fleischanderl, G. Friedrich, A. Haselboeck, H. Schreiner, and M. Stumptner. Configuring large systems using generative constraint satisfaction. IEEE Intelligent Systems, 13(4):59–68, 1998.
(Friedrich and Shchekotykhin, 2005) G. Friedrich and K. Shchekotykhin. A general diagnosis method for ontologies. In 4th International Semantic Web Conference (ISWC’05), pages 232–246, 2005.
(Junker, 2004) U. Junker. Quickxplain: Preferred explanations and relaxations for over-constrained problems. In 19th National Conference on Artifi- cial Intelligence (AAAI’04), pages 167–172, 2004.
(Marques-Silva and Sakallah, 1996) J. Marques-Silva and K. Sakallah. Grasp: A new search algorithm for satisfiability. In International Conference on Computer-Aided Design, pages 220–227, 1996.
(Mittal and Frayman, 1989) S. Mittal and F. Frayman. Towards a generic model of configuration tasks. In 11th International Joint Conference on Artificial Intelligence (IJCAI’89), pages 1395–1401, 1989.
(O’Sullivan et al., 2007) Barry O’Sullivan, A. Papdopoulos, B. Faltings, and P. Pu. Representative explanations for over-constrained problems. In 22nd National Conference on Artificial Intelligence (AAAI’07), pages 323–328, 2007.
(Reiter, 1987) R. Reiter. A theory of diagnosis from first principles. AI Journal, 23(1):57–95, 1987.
(Sinz and Haag, 2007) C. Sinz and A. Haag. Con- figuration. IEEE Intelligent Systems, 22(1):78–90, 2007.
(Tsang, 1993) E. Tsang. Foundations of Constraint Satisfaction. Academic Press, 1993.
(Winterfeldt and Edwards, 1986) D. Winterfeldt and W. Edwards. Decision analysis and behavioral research. Cambridge University Press, 1986.
The Prognostic and Health Management Society advocates open-access to scientific data and uses a Creative Commons license for publishing and distributing any papers. A Creative Commons license does not relinquish the author’s copyright; rather it allows them to share some of their rights with any member of the public under certain conditions whilst enjoying full legal protection. By submitting an article to the International Conference of the Prognostics and Health Management Society, the authors agree to be bound by the associated terms and conditions including the following:
As the author, you retain the copyright to your Work. By submitting your Work, you are granting anybody the right to copy, distribute and transmit your Work and to adapt your Work with proper attribution under the terms of the Creative Commons Attribution 3.0 United States license. You assign rights to the Prognostics and Health Management Society to publish and disseminate your Work through electronic and print media if it is accepted for publication. A license note citing the Creative Commons Attribution 3.0 United States License as shown below needs to be placed in the footnote on the first page of the article.
First Author et al. This is an open-access article distributed under the terms of the Creative Commons Attribution 3.0 United States License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.