Abstract
Effective re-use of knowledge bases requires the identification of plausible combinations of both problem solvers and knowledge bases, which can be an expensive task. Can we identify impossible combinations quickly? The capabilities of combinations can be represented using constraints, and we propose using constraint relaxation to help eliminate impossible combinations. If a relaxed constraint representation of a combination is inconsistentthen we know that the original combination is inconsistent as well. We examine different relaxation strategies based on constraint graph properties, and we show that removing constraintsof low tightness is an efficientstrategywhich is also simple to implement
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
White, S. & Sleeman, D., A Constraint-Based Approach to the Description & Detection of Fitness-for-Purpose, ETAI, vol. 4, pp. 155–183,2000.
White, S. & Sleeman, D., Providing Advice on the Acquisition and Reuse of Knowledge Bases in Problem Solving, 11th Banff Knowledge Acquisition Workshop. SRDG Publications, Calgary Canada, 1998, pp. 21.
AKT, Reuse Knowledge, [WWW],Available from: http://www.aktors.org/publications/reuse/, [Accessed 1 June 2003].
Kolodner, J., Case-BasedReasoning. San Mateo, CA: Morgan Kaufinann, 1993.
Hayes-Roth, F., Waterman, D. & Lenat, D., Building Expert Systems. London: Addison-Wesley, 1983.
Bennett, J. & Engelmore, R., Experience using EMYCIN. In Rule-Based Expert Systems, in Experience using EMYCIN. In Rule-Based Expert Systems, B. Buchanan and E. Shortliffe, Eds. London: Addison-Wesley, 1983, pp. 314–328.
Gennari J. H., Musen, M. A., Fergerson, R., et al., The Evolution of Protégé: An Environment for Knowledge-Based Systems Development., International Journal ofHuman-Computer Studies, vol. 58, pp. 89–123, 2003.
Bartak, R., Online Guide to Constraint Programming, [WWW], Available from: http://kti.ms.mff.cuni.cz/-bartak/constraintslbinarv.html/-bartak/constraintslbinarv.html, [Accessed March 2003 1998].
Tsang, E., Foundations of Constraint Satisfaction. London & San Diego: Academic Press, 1993.
ILOG Solver, 5.3 ed. Paris: ILOG Inc., http://www.ilog.coml.. 2003
SICStus Prolog, 3.9.1 ed. Kista: Swedish Institute of Computer Science, http://www.sics.se/sicstus/./sicstus/. 2001
Freuder, E., Synthesizing constraint expressions, CACM, 1978, pp. 958–966.
Freuder, E. & Wallace, R., Partial Constraint Satisfaction, Artificial Intelligence, vol. 58, pp. 2170, 1992.
Bistarelli, S., Montanari, U. & Rossi, F., Constraint Solving over Semirings, IJCAI’95, 1995, pp. 624–630.
Schiex, T., Fargier, H. & Verfaillie, G., Valued Constraint Satisfaction Problems: hard and easy problems, IJCAI’95, 1995, pp. 631–637.
Hooker, J., Logic-based methods for optimization: combining optimization and constraint satisfaction. New York, 2000, pp. 209.
MacIntyre, E., Prosser, P., Smith, B., et al., Random Constraint Satisfaction: Theory meets Practice, CP-98, 1998, pp. 325–339.
Bacchus, F., Chen, X., Beek, P. V., et al., Binary vs. non-binary constraints, Artificial Intelligence, vol. 140, pp. 1–37, 2002.
Prosser, P., Binary constraint satisfaction problems: Some are harder than others, Proceedings ECAI-94 (11 th European Conference on Artificial Intelligence), 1994, pp. 95–99.
CSP-Suite, 1.90 ed. Aberdeen: University of Aberdeen, http://www.csd.abdn.ac.uk/-tnordlanIProglog%20programs/-tnordlanIProglog%20programs. 2002
SICStus, Constraint Logic Programming over Finite Domains, in SICStus Prolog User’s Manual, vol. Release 3.9.1, R. 3.9.1, Ed. Kista: Intelligent Systems Laboratory Swedish Institute ofComputer Science, 2002, pp. 345–381.
Nordlander, T., First Year Report, Aberdeen University, 2002.
Walsh, T., Search on high degree graphs, IJCAl-2001, 2001, pp. 266–274.
Rajpathak, D., Motta, E. & Roy, R., The Generic Task Ontology For Scheduling Applications, International Conference on Artificial Intelligence, Las Vegas, 2001.
Smith, S. F. & Becker, M. A., An Ontology for Constructing Scheduling Systems, AAAI Symposium on Ontological Engineering, Mars 1997.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag London
About this paper
Cite this paper
Nordlander, T., Brown, K., Sleeman, D. (2004). Constraint Relaxation Techniques to Aid the Reuse of Knowledge Bases and Problem Solvers. In: Coenen, F., Preece, A., Macintosh, A. (eds) Research and Development in Intelligent Systems XX. SGAI 2003. Springer, London. https://doi.org/10.1007/978-0-85729-412-8_24
Download citation
DOI: https://doi.org/10.1007/978-0-85729-412-8_24
Publisher Name: Springer, London
Print ISBN: 978-1-85233-780-3
Online ISBN: 978-0-85729-412-8
eBook Packages: Springer Book Archive