Nov. 28, 2011

Recently I’ve been working on implementing AC2001 as and MAC.  The implementation of AC2001 went fairly smoothly especially since I had already implemented AC1 and AC3 previously this semester.  I had a few debugging problem most of which came from confusion about when to I was adding arcs to the queue. I tested my implementation of AC2001 on about 15 instances (including the 3,4,5,6-queens problems and a few different instances of the zebra problem).  The next step was implementing MAC (Maintaining Arc Consistency) with my currently implemented forward checking algorithm.  At first it seemed simple: run FC and if it does not fail form a queue with all constraints between the future variables and run AC2001.  This task has been a lot more challenging than I expected.   I currently have the algorithm working  correctly for finding one solution both with dynamic and static ordering.  I’ve noticed that in comparison to FC and FCCBJ, MAC seems to have quite a few more consistency checks but less nodes visited, backtracks, and CPU time.  Right now I am working on finding all solutions.

-Mary

Weeks 8 and 9

The last couple weeks have been spent mostly implementing the FC-CBJ algorithm.  We are testing this algorithm using both static and dynamic orderings and finding one and all solutions.  This algorithm has been particularly challenging to implement since it seems to have a few more methods to implement. Also, one of the most difficult parts about this assignment has been the dynamic ordering portion.  Once again, I learned the importance of good design!  I originally programmed using a static list of variables and simply ordered the list at the beginning then used the same ordering to solve the problem originally (I obviously was not thinking about having to eventually do dynamic ordering!).  It would have been a better idea to have two separate structures: one for the uninstantiated variables and one for the instantiated variables.  Static ordering for finding one solution was challenging, but I did not run into many debugging issues until I got to the portion of finding all solutions using dynamic ordering.  I found that my program found one complete solution, then found several partial solutions.  Again, this issue came back to the way I had originally designed my program to find all solution by simply using the static variable list.  Overall, this has been the most beneficial task so far!  I’m excited to continue learning about CSP’s and plan on designing my programs a little more carefully in the future.  

-Mary

October, 2011

The last several weeks, we’ve begun exploring and implementing our first CSP solvers. Our first solver implemented the simplest backtracking algorithm, BT, and used several forms of static variable ordering. We studied Patrick Prosser’s paper on types of back-checking, forward-checking, and hybrids of the two. 

We then began work on CBJ (Conflict-Directed Backjumping), one of the most efficient backtracking algorithms mentioned in Prosser’s paper. We are now moving on to forward checking and dynamic variable ordering, which I expect will be a lot more difficult to implement, but I am looking forward to the challenge. 

 The last few weeks, I have been spending some extra time improving and debugging by AC and NC algorithms from earlier. NC reduces a problem that has unary constraints, a case not handled by my AC algorithm, which is why it is important to run NC before AC, or your domains will not be properly filtered. I discovered a bug in my NC algorithm that I only discovered when testing on instances of the Zebra problem—our only test cases in which NC altered the resulting domains. 

Once correcting this, I was able to catch a bug in my implementation of AC-3 and work to correct it. Implementing algorithms is what I find to be the most time-consuming aspect of research, but also the most rewarding aspect. 

My main frustration lately has been time constraints—having a heavy course-load this semester makes it difficult to find extended periods of time to devote to coding and studying. I am happy to say that I have recently registered for spring classes, and have arranged for a lighter schedule that would allow me to devote more time to research. 

-Maggie