Consistency Based Constraint Satisfaction (UBC, V4.0)
Constraint satisfaction problems (CSPs) are pervasive in AI problems. A constraint satisfaction problem is the problem of assigning values to variables that satisfy some constraints. This constraint satisfaction problem solver (arc consistency) applet is designed to help you learn about solving CSPs with a systematic search technique called arc consistency.
If you're having trouble using the CSP applet, try reading the Quickstart (below) instructions or the CSP Tutorial. Both can be accessed from the "Help" menu. If you notice any obvious shortcomings, please check out our Bug List page. This applet seems to run well on Netscape 4.5+ and IE 4+. It has been tested on Windows and Linux.
Quick Start
Creating Problems:
Building a problem yourself should be straightforward--just make sure that you're in "Create Mode". To create nodes, click on the "Create Variable" button, then click on the white canvas to bring up a dialog box where you can specify all the variable information. Creating Constraints is just as easy. You can also load a ready made sample CSP from the many available. Just Click on Load Sample CSP from the "File" menu and select one to load. Check the extended help if you're having problems, or if you don't understand what all the terminology means.
Solving Problems:
There are three ways to perform the arc-consistency algorithm:
- Select blue arcs you want to process simply by clicking on them.
- Step through arc-consistency using the "Step" button, letting the program automatically pick one of the arcs on the queue at each step.
- Let the program do all the work by clicking "Auto Arc-Consistency". You can adjust the speed of Auto Arc-Consistency by checking one of the checkboxes in the "AutoAC Speed" menu under the "CSP Options" menu.
To perform domain splitting, click on any variable. This will bring up a dialog box where you can specify which domain elements you want to keep. Once you've split a domain, you can perform arc-consistency on the smaller problem. At any time, you can get the "other half" of the split domain by clicking on the "Backtrack" button.
More Help
Can be found at: http://www.cs.ubc.ca/labs/lci/CIspace/Version4/Constraint/help/index.html