Practice Exercise 4.B
Constraint Satisfaction Problems

Back to practice exercises.

1: Background Reading

2: Constraint Satisfaction Problems

Imagine the following scenario: a family of four needs to figure out how each family member will commute to work or school given several constraints. The family consists of a mother, father, son and daughter. Each family member can bicycle or ride in the car. Additionally the son has a pogo stick he can use for commuting to school. The assignment of transportation modes to family members is subject to the following constraints:
  • There are only two bicycles.

  • The car can only hold three people.

  • The son and daughter must take the same mode of transportation.

  • The son and daughter can only go by car if at least one of the parents is going by car, i.e. the parent(s) driving them to school.
What are the variables in this problem? What values are in the domain of each variable? Write down your answers before continuing to the next section.

3: Commuting CSP

Open the consistency for CSP tool and load the file by clicking File → Load from URL. Inspect the CSP problem closely. Are these the variables you listed in the previous section? Look at the domain of each variable. Right-click on one of the constraints and select "Set Properties of Constraint." Examine the current constraint properties. Do the settings seem sensible given what you know about the constraints from section 2? Why or why not?

4: Arc Consistency

Given what you know about the values in the variable domains and the given constraints, do you expect that arc consistency will remove any values from any variable's domain?
  • Click the "Solve" tab.

  • We will now run arc consistency. You can adjust the arc consistency speed to be slower or faster depending on how closely you want to monitor the process, by selecting CSP Options → Arc-Consistency Speed from the menu.

  • Click the "Auto Arc-Consistency" button to begin.
Was the result what you expected? Why or why not?

5: Solving the CSP

Before we try to find a solution to the CSP, make a prediction about what solution(s) exist(s). List as many as you think we will find. You can now click "AutoSolve" to attempt to solve the CSP. If one solution is found, you can click "AutoSolve" again to search for a second, third, fourth, etc. How many solutions were found and what were they?

6: Unary Constraints

We'll now add an additional constraint. We want a unary constraint that says the daughter cannot go by car.
  • Go back to the "Create" tab.

  • Click the "Create Constraint" button at the top and then click on the canvas near the lower-right corner. Give the constraint a sensible name and click "Ok."

  • Click the "Add Variable to Constraint" button and link the constraint and relevant variable by left-clicking each.

  • Look at the constraint properties table and make sure you select/unselect the correct boxes for this constraint.

  • Move back to the "Solve tab." Make a prediction about how many solutions there will now be. Then go through the steps in sections 4 and 5 again.
How many solutions were found? Is there a simpler way of specifying that the daughter cannot go by car, instead of adding a unary constraint as we did?

Valid HTML 4.0 Transitional