Consistency Based CSP Solver
Tutorial 3: Solving a CSP
For this tutorial, we will refer to the CSP created in Tutorial 1 shown below:
To start solving the CSP, switch over to 'Solve' mode by clicking on the 'Solve' tab. Some menu items which were previously unavailable in 'Create' mode are now enabled. Also, a 'Domain-splitting History' panel will appear at the bottom of the window. The toolbar buttons will change to give you solving options. The solve toolbar will initially look like the toolbar below:
Generally, with CSPs, you would first make a CSP arc-consistent and then check for solutions or, if necessary, recursively split a variable's domain and make the CSP arc-consistent again. An 'arc' between variables refers to the constraint relation between the variables. An arc is arc consistent if for each domain value in one variable, there exists a value in the domain of each other variable such that the constraint between the variables is satisfied. A CSP is 'arc consistent' if all of its arcs are arc consistent. A 'solution' to a CSP is an assignment of a unique value to each variable such that all of the constraints are satisfied.
This applet provides many ways to make a CSP arc-consistent:
You can stop Auto Arc-Consistency and AutoSolve at any time by clicking the 'Stop' button. To start solving again from the state in which you stopped, simply carry out any of the solving methods mentioned above. You can also change the speed of arc-consistency and select whether you want each fine step to be shown as the CSP is being solved or not. Both of these options are available in the 'CSP Options' menu.
You can reset the CSP to its initial state at any time by clicking on the 'Reset' button.
Once a CSP has been made arc consistent, there are three possibilities:
After making our example CSP arc consistent it looks like this:
This CSP needs domain splitting to find a solution. Click on any variable that has greater than one value in its domain to split it. The "Split the Domain..." dialog will be shown as below:
The domain values for this variable are displayed. You can manually select which domain values you would like to keep, to solve the CSP with, by clicking on the corresponding value checkboxes. You can also allow the applet to select the first half of the values to keep, or randomly select values to keep. Once you have a reduced domain, some of the arcs in the CSP that were green will have turned blue, meaning that the CSP has to be made arc consistent again. After each split the reduced domain values of a variable will appear in the 'Domain-splitting History' panel at the bottom of the applet window.
A solution to the CSP may not exist given a certain split. In this case a failure for that variable assignment will appear in the 'Domain-splitting History' panel. You can then recover the variable domain values that you discarded when you split a domain by clicking on the 'Backtrack' button and then try solving again.
You may have to split, solve, and backtrack through a CSP recursively until a solution is found.
The history of this process is kept for you in the 'Domain-splitting History' panel.
|Main Tools: Graph Searching | Consistency for CSP | SLS for CSP | Deduction | Belief and Decision Networks | Decision Trees | Neural Networks | STRIPS to CSP|