Task 1

The goal of this task is to investigate the AIMA CSP Solver, make some improvements to it, apply it to a toy problem, and apply it to a practical problem of your own choosing. You'l need to run some comparative experiments, showing how the Solver works on different size problems, with and without your improvements, and submit a report on what you did and the experimental results.

Set Up

See the CSP Setup Instructions for details on installing and testing the CSP Solver.

Toy Problem

Do cryptarithmetic problems in the CSP Solver. Do SEND + MORE = MONEY but don't hard-code just that problem. At a minimum, you should be able to handle any 2-addend problem. Invent at least one more example, which should have at least one solution.

One tricky part is representing the constraints in this kind of problem as binary constraints, which is all the CSP Solver can handle. You need to create additional variables that combine the input variables, and form constraints with them. See your class notes and the newsgroup for discussions on this.

A Real Problem

Puzzles are fine for testing and exploring, but in real life we need programs to solve real problems, like assigning resources to tasks, choosing parts for computers, and so on. Find a real world task that seems appropriate for CSP, represent one or two examples, and apply the CSP Solver to it.

Improving the Solver

The Solver is good code but it's very simple code. It's intended to have lots of room for improvement. As discussed in class, there appear to be two places where the CSP Solver may need improvement:

In both cases, any changes you make to the CSP code should be totally general and not assume any specific CSP problem.

Do not change csp.lisp. Create a file with the code you need to extend and redefine csp.lisp. This will be the file you send in.

Assignment Checking

The CSP Solver checks all assigned variables against all assigned variables on every new assignment. In all the examples we've seen, we only need to check the most recently assigned variable against the assigned variables.

Change the CSP code to take a flag check-all? that, if true (the default), causes the current behavior to occur, but, if false, causes the Solver to do the proposed new behavior.

As with the other flags for the CSP Solver, you should be able to give this flag:

N-ary Constraints

The other place where you may need to change the CSP Solver code is to better support problems like cryptarithmetic that have n-ary constraints. As noted in Exercise 5.11, class discussion, and the newsgroup, n-ary constraints can be converted to binary constraints by introducing new intermediate variables that unite several variables. Such variables have domains that are the cross-product of the domains of the variables they unite. Odds are (but experimental evidence would be good here) that we don't want to randomly assign values to such variables and see if they work out. Instead, the CSP code should automatically assign and unassign these intermediate variables as the variables they unite are assigned.

Experiments

Gather data on how the CSP Problem Solver runs for the different problems, with different combinations of the flags and search functions, including the check-all? flag. Draw some conclusions.

Note that the Solver code already gathers some statistics, and there's example code in test-search.lisp that shows how to generate comparative output. Use that and/or improve it.

The Report

Put your report in a Word document (or RTF file if you use something other than Word). Separate the document into clearly labeled sections based on the above, i.e., a section on how you changed the CSP Solver, a section on how you implemented the cryptarithmetic problem, a section on the experiments and results, and so on.

Create the following files:

Send the Zip file as an attachment in an email to c-riesbeck@northwestern.edu, with the Subject line: CS 348 Task 1.


Comments? comment image Send mail to Chris Riesbeck.