Hostname: page-component-78c5997874-lj6df Total loading time: 0 Render date: 2024-11-09T05:47:06.007Z Has data issue: false hasContentIssue false
  • English
  • Français

The KB paradigm and its application to interactive configuration*

Published online by Cambridge University Press:  01 July 2016

PIETER VAN HERTUM ,
INGMAR DASSEVILLE ,
GERDA JANSSENS  and
MARC DENECKER
PIETER VAN HERTUM
Affiliation:
Department of Computer Science, KU LEUVEN, Leuven, BELGIUM (e-mail: [email protected], [email protected], [email protected], [email protected])
INGMAR DASSEVILLE
Affiliation:
Department of Computer Science, KU LEUVEN, Leuven, BELGIUM (e-mail: [email protected], [email protected], [email protected], [email protected])
GERDA JANSSENS
Affiliation:
Department of Computer Science, KU LEUVEN, Leuven, BELGIUM (e-mail: [email protected], [email protected], [email protected], [email protected])
MARC DENECKER
Affiliation:
Department of Computer Science, KU LEUVEN, Leuven, BELGIUM (e-mail: [email protected], [email protected], [email protected], [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

The knowledge base (KB) paradigm aims to express domain knowledge in a rich formal language, and to use this domain knowledge as a KB to solve various problems and tasks that arise in the domain by applying multiple forms of inference. As such, the paradigm applies a strict separation of concerns between information and problem solving. In this paper, we analyze the principles and feasibility of the KB paradigm in the context of an important class of applications: interactive configuration problems. In interactive configuration problems, a configuration of interrelated objects under constraints is searched, where the system assists the user in reaching an intended configuration. It is widely recognized in industry that good software solutions for these problems are very difficult to develop. We investigate such problems from the perspective of the KB paradigm. We show that multiple functionalities in this domain can be achieved by applying different forms of logical inferences on a formal specification of the configuration domain. We report on a proof of concept of this approach in a real-life application with a banking company.

Keywords

interactive configurationknowledge base paradigminferencesapplications of declarative systems
Type
Regular Papers
Information
Theory and Practice of Logic Programming , Volume 17 , Issue 1 , January 2017 , pp. 91 - 117
Copyright
Copyright © Cambridge University Press 2016 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

*

This is an extended version of a paper presented at the international symposium on Practical Aspects of Declarative Languages (PADL 2016), invited as a rapid communication in TPLP. The authors acknowledge the assistance of the conference program chairs Marco Gavanelli and John Reppy. This research was supported by the project GOA 13/010 Research Fund KU Leuven and projects G.0489.10, G.0357.12, and G.0922.13 of the Research Foundation - Flanders.

References

Adaptive Planet 2015. Adaptive planet. http://www.adaptiveplanet.com/.Google Scholar
Axling, T. and Haridi, S. 1996. A tool for developing interactive configuration applications. Journal of Logic Programming 26, 2, 147–168.Google Scholar
Barker, V. E. and O'Connor, D. E. 1989. Expert systems for configuration at digital: XCON and beyond. Communications of the ACM 32, 3, 298–318.Google Scholar
Bogaerts, B., Jansen, J., Bruynooghe, M., De Cat, B., Vennekens, J. and Denecker, M. 2014. Simulating dynamic systems using linear time calculus theories. TPLP 14, 4–5 (7), 477–492.Google Scholar
Bruynooghe, M., Blockeel, H., Bogaerts, B., De Cat, B., De Pooter, S., Jansen, J., Labarre, A., Ramon, J., Denecker, M. and Verwer, S. 2015. Predicate logic as a modeling language: Modeling and solving some machine learning and data mining problems with IDP3. TPLP 15, 783–817.Google Scholar
Calimeri, F., Ianni, G. and Ricca, F. 2014. The third open answer set programming competition. TPLP 14, 1, 117–135.Google Scholar
Dasseville, I., van der Hallen, M., Janssens, G. and Denecker, M. 2015. Semantics of templates in a compositional framework for building logics. TPLP 15, 4–5, 681–695.Google Scholar
De Cat, B., Bogaerts, B., Bruynooghe, M., Janssens, G. and Denecker, M. 2016. Predicate logic as a modelling language: The IDP system. CoRR abs/1401.6312v2.Google Scholar
Denecker, M., Lierler, Y., Truszczyński, M. and Vennekens, J. 2012. A Tarskian informal semantics for answer set programming. In ICLP (Technical Communications), Dovier, A. and Costa, V. S., Eds. LIPIcs, vol. 17. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, ACM TOCL: New York, NY, USA, 277–289.Google Scholar
Denecker, M. and Ternovska, E. 2008. A logic of nonmonotone inductive definitions. ACM Transactions on Compututaional Logic 9, 2 (Apr.), 14:1–14:52.Google Scholar
Denecker, M. and Vennekens, J. 2008. Building a knowledge base system for an integration of logic programming and classical logic. In Proc. of ICLP, de la Banda, M. García and Pontelli, E., Eds. LNCS, vol. 5366. Springer: Heidelberg, Germany, 71–76.Google Scholar
Falkner, A. A. and Haselböck, A. 2013. Challenges of knowledge evolution in practice. AI Communications 26, 1, 3–14.Google Scholar
Felfernig, A., Hotz, L., Bagley, C. and Tiihonen, J. 2014. Knowledge-based Configuration: From Research to Business Cases, 1st ed. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA.Google Scholar
Fleischanderl, G., Friedrich, G., Haselböck, A., Schreiner, H. and Stumptner, M. 1998. Configuring large systems using generative constraint satisfaction. IEEE Intelligent Systems 13, 4, 59–68.CrossRefGoogle Scholar
Gelfond, M. and Lifschitz, V. 1988. The stable model semantics for logic programming. In Proc. of ICLP/SLP, Kowalski, R. A. and Bowen, K. A., Eds. MIT Press, Springer: Heidelberg, Germany, 1070–1080.Google Scholar
Hadzic, T. 2004. A BDD-based approach to interactive configuration. In Proc. of Principles and Practice of Constraint Programming - CP 2004, 10th International Conference, CP 2004, Toronto, Canada, September 27–October 1, 2004, Wallace, M., Ed. LNCS, vol. 3258. Springer: Heidelberg, Germany, 797.Google Scholar
Hadzic, T. and Andersen, H. R. 2005. Interactive reconfiguration in power supply restoration. In Proc. of Principles and Practice of Constraint Programming - CP 2005, 11th International Conference, CP 2005, Sitges, Spain, October 1–5, 2005, van Beek, P., Ed. Lecture Notes in Computer Science, vol. 3709. Springer: Heidelberg, Germany, 767–771.Google Scholar
Heras, F., Morgado, A. and Marques-Silva, J. 2011. Core-guided binary search algorithms for maximum satisfiability. In Proc. of the 25th AAAI Conference on Artificial Intelligence, AAAI 2011, San Francisco, California, USA, August 7–11, 2011.Google Scholar
Hotz, L., Krebs, T., Deelstra, S., Sinnema, M. and Nijhuis, J. 2006. Configuration in Industrial Product Families - the ConIPF Methodology. IOS Press, Inc: Amsterdam, The Netherlands.Google Scholar
Immerman, N. and Vardi, M. Y. 1997. Model checking and transitive-closure logic. In Proc. of Computer Aided Verification, 9th International Conference, CAV '97, Haifa, Israel, June 22–25, 1997, Grumberg, O., Ed. Lecture Notes in Computer Science, vol. 1254. Springer: Heidelberg, Germany, 291–302.Google Scholar
Janota, M. 2008. Do SAT solvers make good configurators? In Proc. of Software Product Lines, 12th International Conference, SPLC 2008, Limerick, Ireland, September 8–12, 2008, Second Volume (Workshops), Thiel, S. and Pohl, K., Eds. Lero Int. Science Centre, University of Limerick, Ireland, 191–195.Google Scholar
Jansen, J., Dasseville, I., Devriendt, J. and Janssens, G. 2014. Experimental evaluation of a state-of-the-art grounder. In Proc. of the 16th International Symposium on Principles and Practice of Declarative Programming, Kent, Canterbury, United Kingdom, September 8–10, 2014, Chitil, O., King, A., and Danvy, O., Eds. ACM, 249–258.Google Scholar
Junker, U. 2004. QUICKXPLAIN: Preferred explanations and relaxations for over-constrained problems. In Proc. of the 19th National Conference on Artificial Intelligence, 16th Conference on Innovative Applications of Artificial Intelligence, July 25–29, 2004, San Jose, California, USA, McGuinness, D. L. and Ferguson, G., Eds. AAAI Press/The MIT Press: Cambridge, Massachusetts, USA, 167–172.Google Scholar
Junker, U. and Mailharro, D. 2003. Preference programming: Advanced problem solving for configuration. AI EDAM 17, 1, 13–29.Google Scholar
Kang, K. 1990. Feature-oriented Domain Analysis (FODA): Feasibility Study; Technical Report CMU/SEI-90-TR-21 - ESD-90-TR-222. Software Engineering Inst., Carnegie Mellon University: Pittsburgh, Pennsylvania, USA.Google Scholar
Karatas, A. S., Oguztüzün, H. and Dogru, A. H. 2010. Mapping extended feature models to constraint logic programming over finite domains. In Proc. of Software Product Lines: Going Beyond - 14th International Conference, SPLC 2010, Jeju Island, South Korea, September 13–17, 2010, Bosch, J. and Lee, J., Eds. Lecture Notes in Computer Science, vol. 6287. Springer: Heidelberg, Germany, 286–299.Google Scholar
Kiziltan, Z., Flener, P. and Hnich, B. 2001. Towards inferring labelling heuristics for CSP application domains. In KI 2001: Advances in Artificial Intelligence, Joint German/Austrian Conference on AI, Vienna, Austria, September 19–21, 2001, Proceedings, Baader, F., Brewka, G., and Eiter, T., Eds. LNCS, vol. 2174. Springer: Cambridge, Massachusetts, USA, 275–289.Google Scholar
Kleene, S. C. 1952. Introduction to Metamathematics. Van Nostrand: New York, New York, USA.Google Scholar
Li, B., Chen, L., Huang, Z. and Zhong, Y. 2005. Product configuration optimization using a multiobjective genetic algorithm. The International Journal of Advanced Manufacturing Technology 30, 1, 20–29.Google Scholar
Lynce, I. and Silva, J. P. M. 2004. On computing minimum unsatisfiable cores. In Proc. of SAT 2004 - The 7th International Conference on Theory and Applications of Satisfiability Testing, 10–13 May 2004, Vancouver, BC, Canada, Online Proceedings.Google Scholar
Marques-Silva, J. and Planes, J. 2008. Algorithms for maximum satisfiability using unsatisfiable cores. In Proc. of Design, Automation and Test in Europe, DATE 2008, Munich, Germany, March 10–14, 2008, 408–413.Google Scholar
McDermott, J. P. 1982. R1: A rule-based configurer of computer systems. Artificial Intelligence 19, 1, 39–88.Google Scholar
McGuinness, D. L. and Wright, J. R. 1998. An industrial-strength description-logics-based configurator platform. IEEE Intelligent Systems 13, 4, 69–77.Google Scholar
Mitchell, D. G. and Ternovska, E. 2005. A framework for representing and solving NP search problems. In Proc. of AAAI, Veloso, M. M. and Kambhampati, S., Eds. AAAI Press/The MIT Press: Cambridge, Massachusetts, USA, 430–435.Google Scholar
Mittal, S. and Falkenhainer, B. 1990. Dynamic constraint satisfaction problems. In Proc. of the 8th National Conference on Artificial Intelligence. Boston, Massachusetts, July 29–August 3, 1990, vol. 2, Dieterich, T. and Swartout, W., Eds. AAAI/MIT Press, Morgan Kaufmann: Burlington, Massachusetts, USA, 25–32.Google Scholar
Mittal, S. and Frayman, F. 1989. Towards a generic model of configuraton tasks. In Proc. of the 11th International Joint Conference on Artificial Intelligence. Detroit, MI, USA, August 1989, Sridharan, N. S., Ed. Morgan Kaufmann, 1395–1401.Google Scholar
Pelov, N., Denecker, M. and Bruynooghe, M. 2007. Well-founded and stable semantics of logic programs with aggregates. TPLP 7, 3, 301–353.Google Scholar
Piller, F. T., Harzer, T., Ihl, C. and Salvador, F. 2014. Strategic capabilities of mass customization based e-commerce: Construct development and empirical test. In Proc. of 47th Hawaii International Conference on System Sciences, HICSS 2014, Waikoloa, HI, USA, January 6–9, 2014. IEEE, 3255–3264.Google Scholar
Pontelli, E. and Son, T. C. 2006. Justifications for logic programs under answer set semantics. In Proc. of ICLP, Etalle, S. and Truszczyński, M., Eds. LNCS, vol. 4079. Springer: Heidelberg, Germany, 196–210.Google Scholar
QML 2015. Qml. http://qmlbook.org/.Google Scholar
Reiter, R. 1987. A theory of diagnosis from first principles. Artificial Intelligence 32, 1, 57–95.Google Scholar
Schneeweiss, D. and Hofstedt, P. 2011. Fdconfig: A constraint-based interactive product configurator. In Proc. of Applications of Declarative Programming and Knowledge Management - 19th International Conference, INAP 2011, and 25th Workshop on Logic Programming, WLP 2011, Vienna, Austria, September 28–30, 2011, Revised Selected Papers, Tompits, H., Abreu, S., Oetsch, J., Pührer, J., Seipel, D., Umeda, M., and Wolf, A., Eds. Lecture Notes in Computer Science, vol. 7773. Springer: Heidelberg, Germany, 239–255.Google Scholar
Shchekotykhin, K. M., Friedrich, G., Rodler, P. and Fleiss, P. 2014. Interactive ontology debugging using direct diagnosis. In Proc. of the 3rd International Workshop on Debugging Ontologies and Ontology Mappings, WoDOOM 2014, co-located with 11th Extended Semantic Web Conference (ESWC 2014), Anissaras/Hersonissou, Greece, May 26, 2014, Lambrix, P., Qi, G., Horridge, M. and Parsia, B., Eds. CEUR Workshop Proceedings, vol. 1162. CEUR-WS.org, 39–50.Google Scholar
Shlyakhter, I., Seater, R., Jackson, D., Sridharan, M. and Taghdiri, M. 2003. Debugging overconstrained declarative models using unsatisfiable cores. In Proc. of ASE, IEEE Computer Society: Washington, D.C., United States, 94–105.Google Scholar
Syrjänen, T. 2006. Debugging inconsistent answer set programs. In Proceedings of the 11th International Workshop on Non-Monotonic Reasoning, NMR 2006, Lake District, UK, 30 May–1 June, Dix, J. and Hunter, A., Eds. 77–84.Google Scholar
Tiihonen, J., Heiskala, M., Anderson, A. and Soininen, T. 2013. Wecotin - A practical logic-based sales configurator. AI Communications 26, 1, 99–131.Google Scholar
Vanden Bossche, M., Ross, P., MacLarty, I., Van Nuffelen, B. and Pelov, N. 2007. Ontology driven software engineering for real life applications. In Proc. of 3rd International Workshop on Semantic Web Enabled Software Engineering (SWESE), June 6–7 2007, Innsbruck, Austria. Springer: Heidelberg, Germany.Google Scholar
Vlaeminck, H., Vennekens, J. and Denecker, M. 2009. A logical framework for configuration software. In Proc. of the 11th International ACM SIGPLAN Conference on Principles and Practice of Declarative Programming, September 7–9, 2009, Coimbra, Portugal, Porto, A. and López-Fraguas, F. J., Eds. ACM, 141–148.Google Scholar
Wittocx, J., Mariën, M. and Denecker, M. 2008. The idp system: A model expansion system for an extension of classical logic. In Proc. of LaSh, M. Denecker, Ed. ACCO: Leuven, Belgium, 153–165.Google Scholar
Wittocx, J., Vlaeminck, H. and Denecker, M. 2009. Debugging for model expansion. In Proc. of ICLP, Hill, P. M. and Warren, D. S., Eds. LNCS, vol. 5649. Springer: Heidelberg, Germany, 296–311.Google Scholar
Zhang, J., Li, S. and Shen, S. 2006. Extracting minimum unsatisfiable cores with a greedy genetic algorithm. In Proc. of AI 2006: Advances in Artificial Intelligence, 19th Australian Joint Conference on Artificial Intelligence, Hobart, Australia, December 4–8, 2006, Springer: Heidelberg, Germany, 847–856.Google Scholar