nach oben

Erschienen in:

2013 | OriginalPaper | Buchkapitel

Constraint Relationships for Soft Constraints

verfasst von : Alexander Schiendorfer, Jan-Philipp Steghöfer, Alexander Knapp, Florian Nafz, Wolfgang Reif

Erschienen in: Research and Development in Intelligent Systems XXX

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

We introduce constraint relationships as a means to define qualitative preferences on the constraints of soft constraint problems. The approach is aimed at constraint satisfaction problems (CSPs) with a high number of constraints that make exact preference quantizations hard to maintain manually or hard to anticipate—especially if constraints or preferences change at runtime or are extracted from natural language text. Modelers express preferences over the satisfaction of constraints with a clear semantics regarding preferred tuples without assigning priorities to concrete domain values. We show how a CSP including a set of constraint relationships can linearly be transformed into a k-weighted CSP as a representative of c-semirings that is solved by widely available constraint solvers and compare it with existing techniques. We demonstrate the approach by using a typical example of a dynamic and interactive scheduling problem in AI.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Inferring Context from Users’ Reviews for Context Aware Recommendation

Nächstes Kapitel A Fuzzy Logic-Based Decision Support System for the Diagnosis of Arthritis Pain for Rheumatic Fever Patients

Andréka, H., Ryan, M., Schobbens, P.Y.: Operators and Laws for Combining Preference Relations. J. Log. Comput. 12(1), 13–53 (2002).

Bessière, C.: Arc-Consistency in Dynamic Constraint Satisfaction Problems. In: T.L. Dean, K. McKeown (eds.) Proc. \(9^\text{ th }\) Nat. Conf. Artificial Intelligence (AAAI’91), pp. 221–226. AAAI Press (1991).

Bistarelli, S., Montanari, U., Rossi, F.: Constraint Solving over Semirings. In: Proc. \(14^\text{ th }\) Int. Joint Conf. Artificial Intelligence (IJCAI’95), vol. 1, pp. 624–630. Morgan Kaufmann (1995).

Borning, A., Freeman-Benson, B., Wilson, M.: Constraint Hierarchies. LISP Symb. Comp. 5, 223–270 (1992).

Boutilier, C., Brafman, R.I., Domshlak, C., Hoos, H.H., Poole, D.: CP-nets: A Tool for Representing and Reasoning with Conditional Ceteris Paribus Preference Statements. J. Artif. Intell. Res. 21, 135–191 (2004).

Boutilier, C., Brafman, R.I., Geib, C., Poole, D.: A Constraint-based Approach to Preference Elicitation and Decision Making. In: AAAI Spring Symp. Qualitative Decision Theory, pp. 19–28 (1997).

Brafman, R., Domshlak, C.: Preference Handling - An Introductory Tutorial. AI Magazine 30(1), 58–86 (2009).

Dechter, R., Dechter, A.: Belief Maintenance in Dynamic Constraint Networks. In: H.E. Shrobe, T.M. Mitchell, R.G. Smith (eds.) Proc. \(7^\text{ th }\) Nat. Conf. Artificial Intelligence (AAAI’88), pp. 37–42. AAAI Press (1988).

Doyle, J., McGeachie, M.: Exercising Qualitative Control in Autonomous Adaptive Survivable Systems. In: Proc. \(2^\text{ nd }\) Int. Conf. Self-adaptive software: Applications (IWSAS’01), Lect. Notes Comp. Sci., vol. 2614, pp. 158–170. Springer (2003).

10.

Dubois, D., Fargier, H., Prade, H.: The Calculus of Fuzzy Restrictions as a Basis for Flexible Constraint Satisfaction. In: Proc. \(2^\text{ nd }\) IEEE Int. Conf. Fuzzy Systems, vol. 2, pp. 1131–1136 (1993).

11.

Freuder, E.C., Wallace, R.J.: Partial Constraint Satisfaction. Artif. Intell. 58(1–3), 21–70 (1992).

12.

Gelain, M., Pini, M.S., Rossi, F., Venable, K.B.: Dealing with Incomplete Preferences in Soft Constraint Problems. In: C. Bessière (ed.) Proc. \(13^\text{ th }\) Int. Conf. Principles and Practice of Constraint Programming (CP’07), Lect. Notes Comp. Sci., vol. 4741, pp. 286–300. Springer (2007).

13.

Jampel, M.: A Brief Overview of Over-constrained Systems. In: M. Jampel, E. Freuder, M. Maher (eds.) Over-Constrained Systems, Lect. Notes Comp. Sci., vol. 1106, pp. 1–22. Springer (1996).

14.

Larrosa, J.: Node and Arc Consistency in Weighted CSP. In: R. Dechter, R.S. Sutton (eds.) Proc. \(18^\text{ th }\) Nat. Conf. Artificial Intelligence (AAAI’02), pp. 48–53. AAAI Press (2002).

15.

Meseguer, P., Rossi, F., Schiex, T.: Soft Constraints. In: F. Rossi, P. van Beek, T. Walsh (eds.) Handbook of Constraint Programming, chap. 9. Elsevier (2006).

16.

Mittal, S., Falkenhainer, B.: Dynamic Constraint Satisfaction. In: H.E. Shrobe, T.G. Dietterich, W.R. Swartout (eds.) Proc. \(8^\text{ th }\) Nat. Conf. Artificial Intelligence (AAAI’90), vol. 1, pp. 25–32. AAAI Press (1990).

17.

Rossi, F.: Preferences, Constraints, Uncertainty, and Multi-Agent Scenarios. In: Proc. Int. Symp. Artificial Intelligence and Mathematics (ISAIM’08) (2008).

18.

Rossi, F., Venable, K.B., Walsh, T.: Preferences in Constraint Satisfaction and Optimization. AI Mag. 29(4), 58–68 (2008).

19.

Schiex, T., Fargier, H., Verfaillie, G.: Valued Constraint Satisfaction Problems: Hard and Easy Problems. In: Proc. \(14^\text{ th }\) Int. Joint Conf. Artificial Intelligence (IJCAI’95), vol. 1, pp. 631–639. Morgan Kaufmann (1995).

20.

Shapiro, L.G., Haralick, R.M.: Structural descriptions and inexact matching. IEEE Trans. Pattern Analysis and, Machine Intelligence PAMI-3(5), 504–519 (1981).

21.

Steghöfer, J.P., Anders, G., Siefert, F., Reif, W.: A System of Systems Approach to the Evolutionary Transformation of Power Management Systems. In: Proc. INFORMATIK 2013 Wsh. “Smart Grids”, Lect. Notes Inform. Bonner Köllen Verlag (2013).

Titel: Constraint Relationships for Soft Constraints
verfasst von: Alexander Schiendorfer
Jan-Philipp Steghöfer
Alexander Knapp
Florian Nafz
Wolfgang Reif
Verlag: Springer International Publishing
Buch: Research and Development in Intelligent Systems XXX
Print ISBN: 978-3-319-02620-6

Electronic ISBN: 978-3-319-02621-3

Copyright-Jahr: 2013
DOI: https://doi.org/10.1007/978-3-319-02621-3_17

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner