|
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 http://www.aispace.org/exercises/FamCommuteCSP.xml 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?
|
