by Chris Beck (chris@{cs,ie}.utoronto.ca) Given CSP C to solve, we would like to know how to transform it into CSP C' such that: 1) C' is more easily solved than C. 2) Solving C' provides knowledge that makes the subsequent search for a solution to C easier. 3) The transformation from C to C' can be efficiently achieved. The transformation of C to C' is the "abstraction" of C to the "higher-level" C'. Berthe Y. Choueiry (choueiry@liasun1.epfl.ch) notes: } Since a CSP has the following components: } - a set of variables } - a set of values per variable } - a set of constraints } } Abstraction techniques could potentially be applied to any of these } components. Here follows a *NON-EXHAUSTIVE* list of *examples*: } } Abstracting variables: } - good old techniques of graph reduction } - various strategies clustering (aggregations etc..) } } Abstracting values: } - (heuristic) domain reduction } - more formally, interchangeability (defined by Freuder, also } studied by Haselboeck, and applied to resource allocation } by myself). } } Constraint abstraction: } - such as scoping, localization, decomposition, conflict } isolation. etc.. } - generalization (mainly for explanation purposes..) } } These techniques could be probabilistic, heuristic, exact, etc.. } There is a trend to formally evaluate these techniques or the problems } they are being applied to, in terms of computational complexity. The following references provide a starting point: @InProceedings{ellman-ijcaij93, author = "Ellman, Thomas", title = "Abstraction by Approximate Symmetry", pages = "916-921", booktitle = "IJCAI'93: Proceedings of the 13th International Joint Conference on Artificial Intelligence", year = 1993 } @InProceedings{ellman-ml93, author = "Ellman, Thomas", title = "Synthesis of Abstraction Hierarchies for Constraint Satisfaction by Clustering Approximately Equivalent Objects", pages = "104-111", booktitle = "Proceedings of International Conference on Machine Learning", year = 1993 } @InProceedings{dalal-ccai92, author = "Dalal, M and Etherington, D.", title = "Tractable Approximate Deduction Using Limited Vocabularies", pages = "206-212", booktitle = "Proceedings of the 9th Canadian Conference on Artificial Intelligence", year = 1992 } @InProceedingsimiel-ijcaij87, author = "Imielinski, T.", title = "Domain Abstraction and Limited Reasoning", pages = "997-1003", booktitle = "IJCAI'87: Proceedings of the 10th International Joint Conference on Artificial Intelligence", year = 1987 } @Article{giunch-ai92, author = "Giunchiglia, F. and Walsh, T.", title = "A Theory of Abstraction", journal = "Artificial Intelligence", year = 1992, volume = 57, pages = "323-389" } @Article{schaerf-ai95, author = "Schaerf, M. and Cadoli, M.", title = "Tractable Reasoning via Approximation", journal = "Artificial Intelligence", year = 1995, volume = 74, number = 2, pages = "249-310" } @InProceedings{schrag-sara95, author = "Schrag, R. and Miranker, D.", title = "An Evaluation of Domain Reduction: Abstraction for Unstructured CSPs", pages = "126-133", booktitle = "Proceedings of the Symposium on Abstraction, Reformulation, and Approximation", year = 1992, note = "http://www.cs.utexas.edu/users/schrag/SARA.ps" } @InProceedings{schrag-saim95, author = "Schrag, R. and Miranker, D.", title = "Abstraction and the CSP Phase Transition Boundary", pages = "126-133", booktitle = "Proceedings of the 4th International Symposium on Artificial Intelligence and Mathematics", year = 1995, note = "http://www.cs.utexas.edu/users/schrag" } @InProceedings{freuder-sabin-sara95, author = "Freuder, E. C. and Sabin, D", title = "Interchangeability Supports Abstraction and Reformulation for Constraint Satisfaction ", booktitle = "Proceedings of Symposium on Abstraction, Reformulation and Approximation (SARA'95)", year = 1995, note = "http://www.cs.unh.edu/csprojects/csp/csp.html" } ---------------------------------------------------------------- ;;; *EOF*Go Back Up