September, 2011

Research has been very engaging so far. Over the last month, I have been gradually learning the methods and processes of research as well as getting a lot of coding experience. First, we familiarized ourselves with the concept of the constraint satisfaction problem (CSP). We researched the structure of the problem and examined microstructures, macrostructures, graphs, networks, and hypergraphs used in CSP representation. We explored some of the applications for this type of problem as well. We then implemented code to parse and interpret an instance of a CSP and design a data structure for storing and manipulating it.  I used Java for this particular task, as Java lends itself well to object-oriented code and CSPs are very modular in nature.

We then developed methods for traversing the vertices of the CSP via its constraints. In my CSP data structure, I allowed each variable to have a set of pointers to each of the neighboring variables in order to make node-traversal simpler. We then expanded our code to include a dynamic domain for each variable of the CSP, allowing us to keep track of each variable’s initial domain as well as its current, modified domain. With this addition to the program, we were able to first implement a node-consistency algorithm to limit the domain of each variable (based on variable constraints), and then implement arc-consistency to eliminate elements of the domains for variable-value pairs based on their shared constraints. For this project, we limited ourselves to binary CSPs because they represent a wide variety of problems and can be more easily conceptualized.

We first implemented an arc-consistency algorithm called AC-1, which removes all inconsistent domain values but is not the most efficient algorithm, as it reiterates through all variable-value pairs each time a node’s domain is reduced. So, we implemented an algorithm called AC-3 which is an improvement on AC-1 in that it reduces the number of constraint checks for CSPs with a moderate tightness level. AC-3 implements a dynamic queue that minimizes the number of variable domains checked and additionally reduces CPU-time for moderately-difficult problems. AC-3 was also slightly more difficult to implement.

We then tested our algorithms through a graphical performance analysis on hundreds of random binary constraint satisfaction problems. We were able to graph this data to determine trends in the number of constraint checks and computation time for both algorithms. We were able to prove that AC-3 did, in fact, perform better than AC-1 in terms of handling moderately difficult problems. We performed a t-test on the number of constraint checks done by each algorithm at different tightness levels of the random CSP instances in order to show that AC-3 performed better on average for CSPs with a moderate-to-high tightness level. This testing was also a useful debugging tool, as it allowed us to ensure that both algorithms were removing the same number of values from the variable domains of the CSP instance.

As this is the first research project I have worked on, I still have much to learn about research methods and tons of background material to delve into. Nevertheless, I am looking forward to implementing new algorithms and gaining a lot from this research opportunity!

--Maggie Krause