| EPSRC Reference: |
GR/J42878/01 |
| Title: |
ADAPTIVE CONSTRAINT SATISFACTION |
| Principal Investigator: |
Tsang, Professor E |
| Other Investigators: |
|
| Researcher Co-Investigators: |
|
| Project Partners: |
|
| Department: |
Computer Sci and Electronic Engineering |
| Organisation: |
University of Essex |
| Scheme: |
Standard Research (Pre-FEC) |
| Starts: |
01 March 1994 |
Ends: |
28 February 1997 |
Value (£): |
121,970
|
| EPSRC Research Topic Classifications: |
|
| EPSRC Industrial Sector Classifications: |
|
| Related Grants: |
|
| Panel History: |
|
|
Summary on Grant Application Form |
|
To develop efficient constraint satisfaction techniques by:(1) mapping problems to algorithms and heuristics which are most effective for them; and(2) developing strategies for dynamically choosing problem solving algorithms.Progress:The major development of this project in the first year has been the completion of the ACE (which stands for Algorithm Comparison and Evaluation) system, which allows us to test a large number of algorithms and heuristics systematically. The current version of ACE system (Version 1.0) implements 8 algorithms, 6 heuristics and one preprocessing algorithm (AC6). The user is allowed to combine them freely, and more algorithms and preprocessing algorithms are planned to be added to the system. This system will be used as a tool in the next phase of the project for evaluating algorithms. We have tested the algorithms and heuristics in the ACE system extensively on randomly generated binary constraint satisfaction problems. These problems were generated using the method that most other researchers in this field use. The results have been put into a map showing the effectiveness of different algorithm-heuristic combinations. A paper reporting our first results has been accepted for publication: Tsang, E.P.K., Borrett, J.E. & Kwan, A.C.M., An attempt to map the performance of a range of algorithm and heuristic combinations, Proc., Artificial Intelligence and Simulated Behaviour Conference, 1995 (to appear) More papers reporting our results are under preparation. The ACE system will be made available to students and collaborating research groups in the near future. We have also identified a set of problem characteristics which we believe are relevant to the mapping of problems to algorithms and heuristics. A tentative decision tree has been constructed for testing. We are on course to achieve the targets that we set in the proposal. The following ftp site has been set up, and will be used to disseminate our results (only technical reports so far): solb1.essex.ac.uk://usr/local/ftp/pub/csp
|
|
Key Findings |
|
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
|
|
Potential use in non-academic contexts |
|
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
|
|
Impacts |
|
| Description |
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk |
| Summary |
|
| Date Materialised |
|
|
|
|
Sectors submitted by the Researcher |
|
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
|
| Project URL: |
|
| Further Information: |
|
| Organisation Website: |
http://www.sx.ac.uk |