Artificial Intelligence
I worked on two projects this last semester in the realm of Artificial Intelligence - one was an analysis on various incomplete algorithms for the propositional satisfiability problem, and the other investigated using linear programming (LP) to guide local search in constraint satisfaction problems.
Satisfiability: An Analysis of Local Search Algorithms
In this paper I discuss three prominent, incomplete algorithms that combine randomization and local search techniques to discover a satisfying assignment to hard 3-SAT instances with high probability. In my analysis I aim to determine the respective utilities of three elements to such procedures: greediness, randomness, and memory. I found that tabu lists, or memory-based techniques, achieve the greatest reduction in runtime out of the algorithms tested. [PDF]
LP-guided Search for Constraint Satisfaction Problems
In this paper, I develop a framework for using Linear Programming relaxations of constraint satisfaction problems (CSPs) to guide local, combinatorial search. In particular, I evaluate this technique on the Quasigroup Completion Problem (QCP). I compare the performance of pure CSP techniques with a pure Linear Programming solution, and various hybrids of the two. In comparison to traditional CSP local search procedures, I found that the hybrid solutions yield significant improvements in computational complexity (i.e. the number of backtracks), but the runtime is considerably slower. Hence, the next step in this work is to identify (dynamically) the appropriate balance between the value of the LP output and the cost of more elementary search techniques. [PDF]