My group has begun our research by doing background reading in Rina Dechta’s book, Constraint Processing, on Constraint Satisfaction Problems (CSPs) and the SAT problem. Our advisor, Dr. Choueiry, spent a fair amount of time during the first week making sure we had a clear understanding of these two problems. Our next step entailed utilizing a java CSP parser and creating classes to store that the CSP. This was a fairly simple task but came with a few issues mostly in trying to understand the parser.
With our initial program completed and thoroughly tested, we moved to studying Arc Consistency. In particular we studied the AC1, AC3, and AC2001 algorithms. We went through the pseudo code of all three of these algorithms and implemented AC1 and AC3. Each of us implemented these algorithms and recorded the number of consistency check, how many domain values were removed, the CPU time, and other information for each CSP instance. Once we separately implemented these algorithms, we compared results to make sure our implementations were correct and our results were consistent. We ran into quite a few issues with this and spent ample time debugging our programs and going through smaller problems manually to see what see what the actual number results should be.
After this step, we ran both AC3 and AC1 algorithms on 800 randomly created instances: we varied the tightness of the CSP and created 50 instances of each of these tightnesses. We compared the results of the CPU time and the consistency checks of both AC1 and AC3. We graphed the averages and ran the t test on each of the tightnesses. Our results showed that indeed AC3 performs better than AC1.
Our next step was to study algorithms to search for solutions to the CSP instances. We studied Patrick Prosser’s paper, “Hybrid Algorithms for the Constraint Satisfaction Problems”. We are in the process of implementing the backtrack search algorithm.
(We will be posting weekly on our progress)
-Mary Burke
