Cork Constraint Computation Centre applies Artificial Intelligence to Constraint Programming
by Eugene C. Freuder
The Cork Constraint Computation Centre at University College Cork is applying artificial intelligence methods to shift the burden of constraint programming from user to computer.
Difficult problems can offer too many choices, many of which are incompatible, few of which are optimal. Constraint programming makes it easier for computers to help us make these choices. For example, the problem of scheduling employees to shifts is a constraint satisfaction problem. Constraints may range from governmental regulations on working hours to specialized skills of individual workers. Constraints can also take into account costs, preferences, priorities and uncertainties. For example, a worker may prefer a certain shift, an employer may seek to provide sufficient coverage at minimal cost.
Constraints arise in design and configuration, planning and scheduling, diagnosis and testing, and in many other contexts. Constraint programming can solve problems in telecommunications, internet commerce, bioinformatics, transportation, network management, manufacturing, supply chain management, finance, and many other fields. Constraint programming already has wide commercial application, but much remains to be done to fully explore and exploit the technology.
The major scientific challenge and commercial bottleneck at present is the need for further automation. At present difficult constraint programming problems require Ph.D. level expertise. The Cork Constraint Computation Centre (4C) seeks to apply advances in artificial intelligence and other disciplines to make constraint programming easier to use and more useful. More specifically there is a need to assist users in:
- Acquiring: Acquiring the constraints from users or databases
- Modelling: Representing the constraints in a manner that supports efficient computation
- Solving: Determining the computational methods best suited for individual applications
- Interacting: Making choices, and understanding options when problems are overconstrained.
The provision of automated assistance in each of these areas is in its infancy. Europe is currently a world leader in constraint programming, academically and commercially, and 4C is one of the leading academic research laboratories in constraint programming. However, to maintain and build on this leadership we must make progress on automation and ease of use.
Artificial intelligence methods are well suited to support such progress. Among the projects 4C is pursuing, with support from Science Foundation Ireland and Enterprise Ireland:
ACE: The Automated Constraint Engine (ACE) harnesses the cognitively-oriented FORR architecture to learn to solve CSPs, and also provides a test-bed for empirical investigation on combinations of heuristics. ACE can select heuristics tailored to specific problem classes. ACE can learn new, efficient heuristics that can be readily used in other programming environments. ACE employs a variety of learning and reasoning methods to structure a decision making algorithm for a given class. ACE is coordinated at 4C by Rick Wallace in collaboration with Susan Epstein's FORR Study Group at The City University of New York.
ACOMME: Constraint programming is a proven, key technology in the optimisation of the activities of manufacturing enterprises. A large bottleneck, however, is the need for highly skilled, experienced consultants to build an optimisation solution for each enterprise. Customisation requires expertise in constraint programming as well as time, effort, and experimentation. This project directly addresses the bottleneck by automating the process of converting an enterprise model into a constraint programming model. This will allow reductions in time, effort, and expense as well as a significant increase in the uptake of constraint programming by small and medium sized manufacturing enterprises. ACOMME is coordinated at 4C by Chris Beck in a collaboration with Con Sheahan's group at the University of Limerick.
CAUSE: The Constraint Acquisition and Useful Explanation (CAUSE) project studies the critical user interaction that facilitates acquisition of the problem from the user, and assists the user in understanding the solution process. The latter is particularly important when a problem is initially overconstrained, and the user needs guidance on how to relax the problem to reach an acceptable conclusion. Machine learning techniques, eg version spaces, are being applied to constraint acquisition. CAUSE is coordinated at 4C by Barry O'Sullivan in collaboration with a group at LIRMM-CNRS in France led by Christian Bessiere.
O'CASEY: The objective of the O'CASEY project is to facilitate broader access to constraint programming by reducing the knowledge needed to write effective constraint programs. The O'CASEY project uses Case-Based Reasoning to encapsulate constraint programming knowledge in order to assist non-experts to write more effective constraint programs. O'CASEY is coordinated at 4C by Derek Bridge and Cormac Gebruers in collaboration with a group at the University of Bologna led by Michela Milano.
Link:
http://www.4c.ucc.ie
Please contact:
Eugene C. Freuder
University College Cork, Ireland
E-mail: e.freuder 4c.ucc.ie
|
