SpringerLink
Log in

Possibility theory in constraint satisfaction problems: Handling priority, preference and uncertainty

  • Published:
Applied Intelligence Aims and scope Submit manuscript

Abstract

In classical Constraint Satisfaction Problems (CSPs) knowledge is embedded in a set of hard constraints, each one restricting the possible values of a set of variables. However constraints in real world problems are seldom hard, and CSP's are often idealizations that do not account for the preference among feasible solutions. Moreover some constraints may have priority over others. Lastly, constraints may involve uncertain parameters. This paper advocates the use of fuzzy sets and possibility theory as a realistic approach for the representation of these three aspects. Fuzzy constraints encompass both preference relations among possible instantiations and priorities among constraints. In a Fuzzy Constraint Satisfaction Problem (FCSP), a constraint is satisfied to a degree (rather than satisfied or not satisfied) and the acceptability of a potential solution becomes a gradual notion. Even if the FCSP is partially inconsistent, best instantiations are provided owing to the relaxation of some constraints. Fuzzy constraints are thus flexible. CSP notions of consistency and k-consistency can be extended to this framework and the classical algorithms used in CSP resolution (e.g., tree search and filtering) can be adapted without losing much of their efficiency. Most classical theoretical results remain applicable to FCSPs. In the paper, various types of constraints are modelled in the same framework. The handling of uncertain parameters is carried out in the same setting because possibility theory can account for both preference and uncertainty. The presence of uncertain parameters leads to ill-defined CSPs, where the set of constraints which defines the problem is not precisely known.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
EUR 32.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or Ebook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. S. Benfehrat, D. Dubois and H. Prade, “Representing default rules in possibilistic logic”, in Proc. of the 3rd Inter. Conf. on Principles of Knowledge Representation and Reasoning (KR'92), Cambridge, USA, 1992, edited by B. Nebel, C. Rich, and W. Swartout, Morgan & Kaufmann: San Mateo, CA, 1992, pp. 673–684.

    Google Scholar 

  2. A. Borning, M. Maher, A. Marindale, and M. Wilson, “Constraint hierarchies and logic programming,” in Proc. of the Inter. Conf. on Logic Programming, Lisbon, Portugal, June 1989, pp. 149–164.

  3. P. Bosc and O. Pivert, “An approach for a hierarchical aggregation of fuzzy predicates,” in Proc. of the 2nd IEEE Inter. Conf. on Fuzzy Systems (FUZZ-IEEE'93), San Francisco, CA, March 28-April 1, 1993, pp. 1231–1236.

  4. J. Bowen, R. Lai, and D. Bahler, “Fuzzy semantics and fuzzy constraint networks,” in Proc. of the 1st IEEE Conf. on Fuzzy Systems, San Fransisco, 1992, pp. 1009–1016.

  5. J. Bowen, R. Lai, and D. Bahler, “Lexical imprecision in fuzzy constraint networks,” in Proc. of the National Conf. on Artificial Intelligence, 1992, pp. 616–620.

  6. G. Brewka, H. Guesgen, and J. Hertzberg, “Constraint relaxation and nonmonotonic reasoning,” German National Research Center (GMD), Report TR-92-02, 1992.

  7. R. Dchter and J. Pearl, “Tree clustering for constraint networks,” Artificial Intelligence, vol. 38, pp. 353–366, 1989.

    Google Scholar 

  8. R. Dechter and I. Meiri, “Experimental evaluation of preprocessing techniques in Constraint Satisfaction Problems,” in Proc. of the Inter. Joint Conf. on Artificial Intelligence, Detroit, USA, 1989, pp. 271–277.

  9. R. Dechter, “From local to global consistency,” Artificial Intelligence, vol. 55, pp. 87–107, 1992.

    Google Scholar 

  10. Y. Descottes and J.C. Latombe, “Making compromises among antagonist constraints,” Artificial Intelligence, vol. 27, pp. 149–164, 1985.

    Google Scholar 

  11. D. Dubois and H. Prade (with the collaboration of H. Farreny, R. Martin-Clouaire, and C. Testemale), Possibility theory: An Approach to Computerized Processing of Uncertainty, Plenum Press: New York, 1988.

    Google Scholar 

  12. D. Dubois and H. Prade, “Processing fuzzy temporal knowledge,” IEEE Trans. on Systems, Man and Cybernetics, vol. 19, no. 4, pp. 729–744, 1989.

    Google Scholar 

  13. D. Dubois and H. Prade, “Possibilistic logic, preferential models, non-monotonicity and related issues,” in Proc. of the Inter. Joint Conf. on Artificial Intelligence (IJCAI-91), Sydney, Australia, Aug. 24–30, 1991, pp. 419–424.

  14. D. Dubois and H. Prade, “Inference in possibilistic hypergraphs,” in Uncertainty in Knowledge Bases, edited by B. Bouchon et al., Springer-Verlag: LNCS 286 Berlin, pp. 250–259, 1991.

    Google Scholar 

  15. D. Dubois, H. Fargier, and H. Prade, “The calculus of fuzzy restriction as a basis for flexible constraint satisfaction,” in Proc. of the 2nd IEEE Inter. Conf. on Fuzzy Systems (FUZZ-IEEE'93), San Fransico, CA, March 28-April 1, 1993, pp. 1131–1136.

  16. D. Dubois, H. Fargier, and H. Prade, “Fuzzy constraints in jobshop scheduling,” Journal of Intelligent Manufacturing, vol. 6, pp. 215–235, 1995.

    Google Scholar 

  17. D. Dubois and H. Prade, “Tolerant fuzzy pattern matching: An introduction,” J. of Fuzzy Logic and Intelligent Systems, Seoul, Korea, vol. 3, no. 2, pp. 3–17, 1993.

    Google Scholar 

  18. D. Dubois and H. Prade, “Possibility theory as a basis for qualitative decision theory,” in Proc. of the 14th Inter. Joint Conf. on Artificial Intelligence (IJCAI'95), Montreal, Canada, Aug. 1995.

  19. D. Dubois, H. Fargier, and H. Prade, “Refinements to the maximin approach to decision-making in fuzzy environment,” Fuzzy Sets and Systems, vol. 81, pp. 103–122, 1996.

    Google Scholar 

  20. B. Faltings, D. Haroud, and I. Smith, “Dynamic constraint propagation with continuous variables,” in Proc. of the Europ. Conf. on Artificial Intelligence, 1992, pp. 754–758.

  21. H. Fargier, “Problèmes de satisfaction de contraintnes floues,” 091 Tech. Report, #IRIT/92–29-R, IRIT, Université Paul Sabatier, Toulouse, France, September 1992.

    Google Scholar 

  22. H. Fargier and J. Lang, “Uncertainty in constraint satisfaction problems: A probabilistic approach,” in Symbolic and Quantitative Approaches to Reasoning and Uncertainty (Proc. of the Europ. Conf. ECSQARU'93, Granada, Spain, Nov. 1993), edited by M. Clarke, R. Kruse, and S. Moral, Lecture Notes in Computer Science, vol. 747, Springer-Verlag: Berlin, pp. 97–104, 1993.

    Google Scholar 

  23. H. Fargier, J. Lang, and T. Schiex, “Selecting preferred solutions in Fuzzy Constraint Satisfaction Problems,” in Proc. of the 1st Europ. Conf. on Fuzzy Information Technologies (EUFIT'93), Aachen, Germany, Sept. 7–10, 1993, Published by ELITE-Foundation: Aachen, 1993, pp. 1128–1134.

    Google Scholar 

  24. H. Fargier, “Problemes de satisfaction de constraintes flexibles-application a l' ordonnancement de production,” These de l' Universite P. Sabatier, Toulouse, France, 1994.

  25. M. Fox, B. Allen, and Strohm, “Job-shop scheduling: An investigation in constraint-directed reasoning,” in Proc. of the National Conf. on Artificial Intelligence, Pittsburgh, USA, 1982, pp. 155–158.

  26. E.C. Freuder, “Synthetising constraint expression,” in Communications of the ACM, vol. 21, no. 11, pp. 958–966, 1978.

  27. E.C. Freuder, “A sufficient condition for backtrack-free search,” J. of the ACM, vol. 32, no. 4, pp. 755–761, 1982.

    Google Scholar 

  28. E.C. Freuder, “Partial constraint satisfaction,” in Proc. of the Inter. Joint Conf. on Artificial Intelligence, Detroit, USA, 1989, pp. 278–283.

  29. E.C. Freuder and P. Snow, “Improved relaxation and search methods for approximate constraint satisfaction with a maximin criterion,” in Proc. of the 8th Biennial Conf. of the Canadian Society for Computational Studies of Intelligence, University of Ottawa, Ontario, Canada, May 22–25, 1990, pp. 227–230.

  30. E.C. Freuder and R. Wallace, “Partial constraint satisfaction,” Artificial Intelligence, vol. 58, pp. 21–71, 1992.

    Google Scholar 

  31. J.A. Goguen “L-fuzzy sets,” J. of Mathematical Analysis and Application, vol. 18, pp. 145–174, 1967.

    Google Scholar 

  32. Q. Guan and G. Friedrich, “Extending constraint satisfaction problem solving in structural design,” in Proc. of the 5th Inter. Conf. IEA/AIE, Paderborn, Germany, June 1992, pp. 341–350.

  33. R. Hummel and S. Zucker, “On the foundations of relaxation labeling processes,” IEEE Trans. on Pattern Analysis and Machine Intelligence, vol. 5, no. 3, pp. 267–287, 1983.

    Google Scholar 

  34. R. Kruse and E. Schwecke, “Fuzzy reasoning in a multidimensional space of hypotheses,” Int. J. of Approximate Reasoning, vol. 4, pp. 47–68, 1990.

    Google Scholar 

  35. M. Lacroix and P. Lavency, “Preferences: Putting more knowledge into queries,” in Proc. of the 13rd Inter. Conf. on Very Large Data Bases, Brighton, UK, 1987, pp. 217–225.

  36. J. Lang, “Possibilistic logic as a logical framework for minmax discrete optimization problems and prioritized constraints,” in Proc. of the Inter Workshop on Fundamentals of Artificial Intelligence Research (FAIR'91), Smolenice, Czechoslovakia, Sept. 8–12, 1991, Lecture Notes in Computer Science, vol. 535, Springer-Verlag: Berlin, 1991, pp. 112–126.

    Google Scholar 

  37. D. Lehmann, “What does a conditional knowledge base entail?,” in Proc. of the 1st Inter. Conf. on Principles of Knowledge Representation and Reasoning, Toronto, 1989, pp. 212–221.

  38. A.K. Mackworth, “Consistency in networks of relations,” Artificial Intelligence, vol. 8, pp. 99–118, 1977.

    Google Scholar 

  39. R. Martin-Clouaire, “Dealing with soft constraints in a constraint satisfaction problem,” in Proc. of the Inter. Conf. on Information Processing and Management of Uncertainty in Knowledge-Based Systems (IPMU'92), Mallorca, Spain, July 6–10, 1992, pp. 37–40.

  40. R. Mohr and T. Henderson, “Arc and path consistency revisited,” Artificial Intelligence, vol. 28, pp. 225–233, 1986.

    Google Scholar 

  41. H. Moulin, “Axioms of cooperative decision making,” Cambridge University Press: Cambridge, MA, 1988.

    Google Scholar 

  42. A. Rosenfeld, R.A. Hummel, and S.W. Zucker, “Scene labeling by relaxation operations,” IEEE Trans. on Systems, Man and Cybernetics, vol. 6, pp. 420–433, 1976.

    Google Scholar 

  43. N. Sadeh, “Look-ahead techniques for micro-opportunistic job shop scheduling,” Carnegie Mellon University, Report CS-91-102, 1991.

  44. K. Satoh, “Formalizing soft constraint by interpretation ordering,” in Proc. of the Europ. Conf. on Artificial Intelligence, Stockhom, Sweden, 1990, pp. 585–590.

  45. T. Schiex, “Possibilistic constraint satisfaction problems or how to handle soft constraints,” in Proc. of the 8th Conf. on Uncertainty in Artificial Intelligence, Stanford, CA, July 17–19, 1992, edited by D. Dubois, M.P. Wellman, B. D'Ambrosio, and P. Smets, Morgan & Kaufmann: San Mateo, CA, 1992, pp. 268–275.

    Google Scholar 

  46. G. Shafer and P. Shenoy, “Axioms for probability and belief function propagation,” in Uncertainty in Artificial Intelligence, vol. 4, edited by R.D. Shachter, T.S. Levitt, L.N. Kanal, and S.F. Lemmer, North-Holland: Amsterdam, pp. 169–198, 1990.

    Google Scholar 

  47. P. Van Hentenryck, “Incremental constraint satisfaction in logic programming,” in Proc. ICLP 90, pp. 189–202.

  48. D. Waltz, “Understanding line drawings of scenes with shadows,” in The Psychology of Computer Vision, edited by P.H. Winston, McGraw-Hill: New York, pp. 19–92, 1975.

    Google Scholar 

  49. R.R. Yager, “Some extensions of constraint propagation of label sets,” Int. J. of Approximate Reasoning, vol. 3, pp. 417–435, 1989.

    Google Scholar 

  50. L.A. Zadeh, “Calculus of fuzzy restrictions,” in Fuzzy Sets and Their Applications to Cognitive and Decision Processes, edited by L.A. Zadeh et al., Academic Press: New-York, pp. 1–39, 1975.

    Google Scholar 

  51. L.A. Zadeh, “The concept of a linguistic variable and its application to approximate reasoning,” Information Science, Part 1: vol. 8, pp. 199–249; Part 2: vol. 8, pp. 301–357; Part 3: vol. 9, pp. 43–80, 1975.

    Google Scholar 

  52. L.A. Zadeh, “Fuzzy sets as a basis for a theory of possibility,” Fuzzy Sets and Systems, vol. 1, pp. 3–28, 1978.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Institut de Recherche en Informatique de Toulouse (I.R.I.T.), CNRS, Université Paul Sabatier, 118 route de Narbonne, 31062, Toulouse Cedex, France

    Didier Dubois, Hélène Fargier & Henri Prade

Authors
  1. Didier Dubois
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Hélène Fargier
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Henri Prade
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Dubois, D., Fargier, H. & Prade, H. Possibility theory in constraint satisfaction problems: Handling priority, preference and uncertainty. Appl Intell 6, 287–309 (1996). https://doi.org/10.1007/BF00132735

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF00132735

Keywords

Search

Navigation