| Summary | This assignment covers most of the basic principles and techniques involved in solving constraint satisfaction problems. The student is required to first represent and solve a simple problem with the help of AIspace, an interactive tool for teaching and learning AI (http://www.aispace.org/). After that, the student is asked to implement several CSP techniques (Arc consistency, Search by domain splitting, Stochastic Local Search) and apply them to solve more realistic problems ranging from games (sudoku) to configuration and scheduling problems. |
| Topics | CSP, Search, Stochastic Local Search (SLS) |
| Audience | First undergraduate AI course (focusing on Representation and Reasoning, not Learning) |
| Difficulty | This is a very challenging assignment. Students are strongly encouraged to work in pairs on the programming questions. The assignment has never been offered in this form, but from past experience with similar formats it should take students between 15 and 20 hours. |
| Strengths | Smooth increase in the complexity of the problems. AIspace helps students to interactively explore the relevant R&R techniques before they have to implement and apply those to more challenging problems. It is comprehensive, covering techniques to solve CSP by systematic search, by constraint propagation as well as by local search. |
| Weaknesses | Maybe too long. Require students to learn how to use AIspace, but once they have done it, they can really benefit from all the other applets. |
| Dependencies | Search. AIspace. Java. |
| Variants | The code for arc consistency could be given to the students; same
for the code for the SLS algorithms. This would make for an assignment
more focused on representation than reasoning, and on the interpretation
of results. The representation of the coloring problem in AIspace could
also be given to students and the focus for that question would be more
on following the step by step execution of arc consistency. This would
also require less AIspace learning. As for the design, our approach is to use AIspace to scaffold learning of basic principles and techniques before moving to more challenging questions |
AIspace model for question 1 (to be loaded in AIspace CSP applet)