[1-24] Constraint Abstraction

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 To Previous