Lab 3: Constraint Satisfaction

From 6.034 Wiki

(Difference between revisions)
Jump to: navigation, search
(Propagation through singleton domains)
(A generic CSP solver)
Line 558: Line 558:
<div class="org-src-container">
<div class="org-src-container">
-
<pre class="src src-python">def solve_constraint(problem, enqueue_condition=None) :
+
<pre class="src src-python">def solve_constraint_generic(problem, enqueue_condition=None) :
     raise NotImplementedError
     raise NotImplementedError
</pre>
</pre>
Line 564: Line 564:
</div>
</div>
 +
    """Solves the problem, calling propagate with the specified enqueue #todo formatting
 +
    condition (a function).  If enqueue_condition is None, uses DFS only.
 +
    Same return type as solve_constraint_dfs."""
 +
Answer:
 +
 +
# QUESTION 5: How many extensions does it take to solve the Pokemon problem #todo formatting
 +
#    with DFS and forward checking, but no propagation? (Don't use domain
 +
#    reduction before solving it.)
 +
 +
ANSWER_5 = None
 +
 +
<!--
<div id="outline-container-sec-1-7-1" class="outline-4">
<div id="outline-container-sec-1-7-1" class="outline-4">
<h4 id="sec-1-7-1"> TODO Comparing propagation strategies</h4>
<h4 id="sec-1-7-1"> TODO Comparing propagation strategies</h4>
Line 594: Line 606:
</div>
</div>
-
 
+
-->
Line 600: Line 612:
<div id="outline-container-sec-1-8" class="outline-3">
<div id="outline-container-sec-1-8" class="outline-3">
 +
=== Solving your own CSPs ===  
=== Solving your own CSPs ===  
<div class="outline-text-3" id="text-1-8">
<div class="outline-text-3" id="text-1-8">

Revision as of 06:34, 9 October 2015

Contents


This lab is due by Thursday, October 15 at 10:00pm.

Note: Online tests will be made available shortly. In the meantime, the local tester provides thorough unit tests for each section of the lab.

To work on this lab, you will need to get the code, much like you did for the first two labs.

Your answers for this lab belong in the main file lab4.py.

Problems

Setting up a Constraint Satisfaction Problem

Before beginning, you may want to familiarize yourself with the following terms: variable, value, domain, constraint, assignment.


Here is a problem that can be solved using constrained search:

[e.g. insert the Pokemon problem here] todo The Pokemon problem is in sample_csp.py.

This part of the lab will show you how to convert this problem into a ConstraintSatisfactionProblem instance using our constraint satisfaction API. The complete documentation is here: <a href="#sec-2">API Reference Documentation</a>.

This problem requires two kinds of constraint: a must-be-equal constraint and a must-not-be-equal constraint. In this lab, constraints are defined using functions that take the values of two variables as arguments and return True or False based on whether the constraint is satisfied or not.

Here are definitions for the must-be-equal and must-not-be-equal constraint functions. (These are defined in constraint_api.py.)


def constraint_equal(a,b) :
   return a == b
def constraint_different(a,b) :
   return a != b


To set up the problem, we first establish a new ConstraintSatisfactionProblem instance. There are five variables which we pass an an argument in a list — the five questions to be answered.

pokemon_problem = ConstraintSatisfactionProblem(["Q1","Q2","Q3","Q4","Q5"])

Here, we specify the values in each variable's domain.

pokemon_problem.set_domain("Q1",["A","B","C","D","E"])
pokemon_problem.set_domain("Q2",["A","B","C","D","E"])
pokemon_problem.set_domain("Q3",["A","B","C","D","E"])
pokemon_problem.set_domain("Q4",["A","B","C","D","E"])
pokemon_problem.set_domain("Q5",["A","B","C","D","E"])


Next, we set up constraints. Each constraint takes two variable names, and a binary predicate. (For more details on the binary predicate, see the API Reference Documentation.)

pokemon_problem.add_constraint("Q1","Q4", constraint_different)

pokemon_problem.add_constraint("Q1","Q2", constraint_equal)

pokemon_problem.add_constraint("Q3","Q2", constraint_different)
pokemon_problem.add_constraint("Q3","Q4", constraint_different)

pokemon_problem.add_constraint("Q4","Q5", constraint_equal)


Finally, csp.init_unassigned_vars tells the problem which variables need to be assigned and in what order. If passed no argument, it simply includes all of the variables in the problem in some arbitrary order.

pokemon_problem.init_unassigned_vars()

Alternatively, you can also pass an argument to specify the order of the unassigned_vars yourself:

# (An alternative, which we won't use here.)
pokemon_problem.init_unassigned_vars(["Q4","Q2","Q3","Q1","Q5"])

(For some problems, efficiently re-ordering of the variables can make a large difference in performance.)


We have set up the variables, the domains, and the constraints. This problem is now ready to be solved — all we need is a CSP solver.


Writing a depth-first search solver

Please write a constraint solver that uses depth-first search to find a solution.

def solve_constraint_dfs(csp) :
    raise NotImplementedError


Hint: This is exactly depth-first search as in the search lab, but this time the items in the agenda are partially-solved problems, not paths.



Here is a rough outline of how to proceed:

  1. Create an agenda containing only the problem csp.

  2. Until the agenda is empty, pop the first problem off the list.

  3. For that problem, check all the constraints between the variables that have been assigned values so far. If any constraint is violated, the problem cannot be solved with the given assignments; skip the problem and proceed to the next iteration of the loop. (The addition of this constraint-checking step is where constrained search differs from ordinary search.)

  4. If none of the constraints have been violated, check whether the problem has any unassigned variables (csp.unassigned_vars). If the problem has no unassigned variables, you've found a complete solution! Return the assignments (csp.assigned_value). The return type should be a tuple (solution, extension_count), containing:

    1. the solution (csp.assigned_value, which is a dictionary mapping variables to assigned values), and
    2. the number of extensions made (the number of problems popped off the agenda).
    If no solution was found, return None as the first element of the tuple, instead of the solution. Note: extensions is the number of nodes popped off the agenda (dequeued), #todo format including root (original problem), csps with children, csps with no children, and final csp (which has all vars assigned)

  5. If the problem has some unassigned variables:

    • Take the first unassigned variable off the list (csp.unassigned_vars).
    • For each value in the variable's domain (csp.get_domain(var)), create a new copy of the problem. (csp_new = csp.copy()).
    • Using the copy, assign the value to the variable. ( csp_new.set_assigned_value(var, val) ).
    • Collect the list of copies and add the list to the front of the agenda (as is appropriate for depth-first search).


These are helper functions that you can use within solve_constraint_dfs. def has_empty_domains(csp): #todo format "Returns True if csp has one or more empty domains, otherwise False" return not all(csp.domains.values()) check_all_assignments should return False if the problem's assigned values violate some constraint, otherwise True.

def check_all_assignments(problem) :
    raise NotImplementedError


Domain reduction before search

Domain reduction is a strategy for eliminating impossible values in advance to cut down on the amount of search you have to do.

First, write a helper function to eliminate values from a variable's neighbors' domains. Each variable should appear AT MOST ONCE in the list; the list should contain no duplicates.

Hint: csp.constraints_between may help.

def eliminate_from_neighbors(csp, var) : #todo format (move docstring up to description)

   """Eliminates incompatible values from var's neighbors' domains, modifying
   the original csp.  Returns alphabetically sorted list of the neighboring
   variables whose domains were reduced, with each variable appearing at most
   once.  If no domains were reduced, returns empty list.  If a domain is
   reduced to size 0, quits and returns None."""

Next, you will need to write a domain-reduction algorithm.

def domain_reduction(csp, queue=None) :
    raise NotImplementedError

Here is a rough description of the domain reduction algorithm:

  1. Establish a queue — if the optional argument queue was passed as an argument, use that as your queue. Otherwise, queue should consist of all the variables in the problem.
  2. Until the queue is empty, pop the first variable off the queue.
  3. Iterate over the variable's constraints: if a neighbor has a value that violates a constraint with every value in the variable's domain, remove the neighbor's value and add the neighbor to the queue if and only if the neighbor is not already in queue<a id="fnr.1" class="footref" href="#fn.1">1</a>.
  4. If any variable has an empty domain, quit immediately and return None.
  5. If the queue is empty, domain reduction has finished. As a side-effect, please return: """Uses constraints to reduce domains, modifying the original csp. #todo format If queue is None, initializes propagation queue by adding all variables in alphabetical order. Returns a list of all variables that were dequeued, in the order they were removed from the queue. Variables may appear in the list multiple times. If a domain is reduced to size 0, quits immediately and returns None.""" break any ties lexicographically (probably natural)

Hint: You can remove values from a variable's domain using csp.eliminate(var, val). (But don't eliminate values from a variable while iterating over its domain, or Python will get confused.)


Benchmarks

You can solve the pokemon problem by calling solve_constraint_dfs(pokemon_problem) directly. Using domain reduction first, however, should make search faster. Please answer the following questions in your lab file:

  1. QUESTION 1: How many extensions does it take to solve the Pokemon problem #todo format
  2. with dfs if you DON'T use domain reduction before solving it?
  1. Hint: Use get_pokemon_problem() to get a new copy of the Pokemon problem
  2. each time you want to solve it with a different search method.

ANSWER_1 = None

  1. QUESTION 2: How many extensions does it take to solve the Pokemon problem
  2. with dfs if you DO use domain reduction before solving it?

ANSWER_2 = None


Propagation through reduced domains

Domain reduction can be used not only before search, but also during search. When used during search, domain reduction can make use of the assignments you've made to progressively reduce the search space. The result is a new, faster, csp solution method: propagation through reduced domains.

def solve_constraint_propagate_reduced_domains(problem) :
    raise NotImplementedError

You can reuse most of your code from your solve_constraint_dfs algorithm, as domain reduction adds only a single conditional statement: every time you assign a value to a variable, you must call your domain_reduction function with the assigned variable as an argument. If the domain_reduction function returns None, the problem can't be solved with the given assignments — don't add the problem to the agenda. Otherwise, add the problem to the agenda as usual.

Note: domain_reduction should remove values from the assigned variable's neighbors' domains, not from the variable's domain.

Answer the following question in your lab4.py file:

  1. QUESTION 3: How many extensions does it take to solve the Pokemon problem #todo format
  2. with propagation through reduced domains? (Don't use domain reduction
  3. before solving it.)

ANSWER_3 = None

Propagation through singleton domains

The reduce_domains procedure is comprehensive, but expensive: it eliminates as many values as possible, but it continually adds more variables to the queue. As a result, it is an effective algorithm to use before solving a constraint satisfaction problem, but is often too expensive to call repeatedly during search.

Instead of comprehensively reducing all the domains in a problem, as reduce_domains does, you can instead reduce only some of the domains. This results in propagation through singleton domains — a reduction algorithm which does not detect as many dead ends, but which is significantly faster.

def domain_reduction_singleton_domains(csp, queue=None) :
    raise NotImplementedError

Propagation through singletons is like propagation through reduced domains, except that variables must pass a test in order to be added to the queue:

In propagation through singleton domains, you only append a variable to the queue if it has exactly one value left in its domain.

Common misconception: Please note that propagation never assigns values to variables; it only eliminates values. There is a distinction between variables with one value in their domain, and assigned variables: a variable can have one value in its domain without any value being assigned yet.

Then write:

def solve_constraint_propagate_singleton_domains(problem) : #todo formatting

   """Solves the problem using depth-first search with forward checking and
   propagation through singleton domains.  Same return type as
   solve_constraint_dfs."""
   raise NotImplementedError

and answer:

  1. QUESTION 4: How many extensions does it take to solve the Pokemon problem #todo format
  2. with propagation through singleton domains? (Don't use domain reduction
  3. before solving it.)

ANSWER_4 = None

Forward checking

Forward checking is even more restrictive than propagation through singletons: it never adds variables to the queue. (Later in this labs, we will perform tests to see which propagation algorithm performs best in terms of tradeoffs between performance and comprehensiveness.)

Instead of patterning our forward checking algorithm off of domain_reduction again, we'll write a fully general algorithm called propagate that encapsulates all three propagation strategies we've seen: propagation through reduced domains, propagation through singletons, and forward checking.

The function propagate will be similar to the propagation algorithms you've already defined. The difference is that it will take an argument enqueue_condition_fn which is the test that variables must pass in order to be added to the queue: before propagate adds a variable to the queue, it should call enqueue_condition_fn(csp, var) . If the function returns True, it should add the variable to the queue. Otherwise, it shouldn't.

def propagate(enqueue_condition_fn, csp, queue = None) : 
    raise NotImplementedError

To review, the three enqueueing conditions we've seen are:

domain reduction</dt>
always add the variable to the queue </dd>
singleton propagation</dt>
add the variable if its domain has exactly one value in it. </dd>
forward checking</dt>
never add the variable to the queue. </dd>

Write functions for each of these tests. Hint: some of these functions may ignore some of their arguments.

def condition_domain_reduction(csp, var) :
    raise NotImplementedError

def condition_singleton(csp, var) :
    raise NotImplementedError

def condition_forward_checking(csp, var) :
    raise NotImplementedError

And thus we can define:

domain_reduction_forward_checking = 
lambda csp, queue=None: propagate(condition_forward_checking, csp, queue)

A generic CSP solver

Write an algorithm that can solve a problem using any enqueueing strategy. As a special case, if the enqueue_condition is None, don't use any propagation at all (i.e. the algorithm should perform only depth-first search in this case.)

def solve_constraint_generic(problem, enqueue_condition=None) :
    raise NotImplementedError
   """Solves the problem, calling propagate with the specified enqueue #todo formatting
   condition (a function).  If enqueue_condition is None, uses DFS only.
   Same return type as solve_constraint_dfs."""

Answer:

  1. QUESTION 5: How many extensions does it take to solve the Pokemon problem #todo formatting
  2. with DFS and forward checking, but no propagation? (Don't use domain
  3. reduction before solving it.)

ANSWER_5 = None


Let's find out empirically.

</div>

-->



Solving your own CSPs

Defining new constraints

Assuming m and n are integers, write a function that returns True if m and n are adjacent values (i.e. if they differ by exactly one) and False otherwise.

def constraint_adjacent(m, n) :
    raise NotImplementedError

Also write one for being non-adjacent. There are simple ways to do it; feel free to call constraint_adjacent.

def constraint_not_adjacent(m, n) :
    raise NotImplementedError


The following example shows how you build a constraint object that requires two variables — call them A and B — to be different.

example_constraint = Constraint("A","B", constraint_different)

Some constraint problems include a constraint that requires all of the variables to be different from one another. It can be tedious to list all of the pairwise constraints by hand, so we won't. Write a function that takes a list of variables and returns a list containing, for each pair of variables, a constraint object requiring them to be different from each other. (You can model the constraints on the example above.) Note that order does NOT matter, so you don't need to produce two different constraints for (A,B) and (B,A).

def all_different(vars) :
    raise NotImplementedError

Defining a new problem

Design and solve a constraint satisfaction problem for the following word problem.

! You will need some new constraint functions.

Baker, Cooper, Fletcher, Miller, and Smith live on different floors of an apartment house that contains only five floors. Baker does not live on the top floor. Cooper does not live on the bottom floor. Fletcher does not live on either the top or the bottom floor. Miller lives on a higher floor than does Cooper. Smith does not live on a floor adjacent to Fletcher's. Fletcher does not live on a floor adjacent to Cooper's. Where does everyone live?


Interpret constraints that only mention one person (e.g. "Baker does not live on the top floor.") as an indication that you should leave out those values from the variable's domain — you won't need to make a constraint to represent those kinds of constraints.

apartment_problem = ConstraintSatisfactionProblem(["Baker", "Cooper", "Fletcher", "Miller", "Smith"])


Establish the domains of the variables. Each variable will have a domain that's a subset of [1,2,3,4,5].

Establish the constraints. Remember the constraint that says that all of the variables must be assigned a different value. You may want to use csp.add_constraints(list).



TODO Resource allocation

Find out what size domain you need using binary search.


TODO Counting solutions

Use "yield" to count the number of solutions.

</div>


API Reference Documentation

In this lab, we provide an API for representing and manipulating partial solutions to constraint satisfaction problems.


Constraint Satisfaction Problems

A ConstraintSatisfactionProblem is an object representing a partially-solved constraint satisfaction problem. Its fields are:


  • variables A list containing the names of all the variables in the problem.
  • domains A dictionary associating each variable in the problem with its list of remaining values so far<a id="fnr.2" class="footref" href="#fn.2">2</a>.
  • assigned_values A dictionary. Each variable which has already been assigned a value is associated with that value here. When the problem is entirely solved, assigned_value contains the solution.
  • unassigned_vars An ordered list of all the variables that still need to have a value assigned to them.
  • constraints A list of the constraints between the variables in the problem. Each constraint is a Constraint object; Constraint objects are described in the next section.

Please note that while you may read any of the above variables, you should probably not modify them directly; instead, you should use the following API methods. (Below, csp stands for some ConstraintSatisfactionProblem instance that you want to manipulate.)

  • csp.get_domain(var) Return the list of values in the variable's domain.
  • csp.set_domain(var, domain) Set the domain of the variable to the particular list of values.
  • csp.eliminate(var, val) Remove the value from the variable's domain. Note that as a helpful side-effect, this function returns True if the value was found in the domain, or False if the value wasn't found.


  • csp.get_assigned_value(var) If the variable has been assigned a value, retrieve it. Returns None if the variable hasn't been assigned yet<a id="fnr.3" class="footref" href="#fn.3">3</a>.
  • csp.set_assigned_value(var, val) Set the assigned value of the variable to val, returning a modified copy of the constraint satisfaction problem. Throws an error if val is not in the domain of the variable, or if var has already been assigned a value.


  • csp.constraints_between(var1, var2)

    Return a list of all the constraints between var1 and var2. Arguments that are None will match anything: for example, constraints_between('X',None) will return all constraints involving X any any other variable, and constraints_between(None, None) will return all of the constraints in the problem.

    ! Please note that for your convenience, the constraints returned will always be altered to match the order of the arguments you passed to this method. For example, csp.constraints_between(None, 'Y') will return a list of all constraints involving 'Y' — and the constraints will be altered so that 'Y' is their second variable (var2) in every case.

  • csp.add_constraint(var1, var2, test_fn)

    Takes two variables and a function to act as a constraint between them, creating a Constraint object and adding it to the list csp.constraints.

    The function test_fn must take two arguments — a value for the first variable, and a value for the second variable — and return True if the values satisfy the constraint, or False otherwise.

  • csp.add_constraints(constraint_list)

    Add a list of Constraint objects to the list csp.constraints. Useful for when you want to add several constraints to the problem at once, rather than one at a time using csp.add_constraint.



Constraints

A Constraint is a fairly basic object. It has three variables— var1, var2, and constraint_fn — and one method, check(val1, val2).

const.check(val1, val2) simply applies the Constraint's constraint function to the two arguments, returning True if the values satisfy the constraint, or False otherwise.


TODO Worked examples

</div>


Footnotes:

<a id="fn.1" class="footnum" href="#fnr.1">1</a>

Naming the variables may make this easier: you have

popped Alice off of the queue and are iterating over Alice's constraints. One of those constraints involves a neighbor, Bob. If Bob has a value that is incompatible with all of Alice's values,

remove Bob's value and add Bob to the queue.

<a id="fn.2" class="footnum" href="#fnr.2">2</a>

Constraint

satisfaction involves ruling out as many values as

possible in order to limit search.

<a id="fn.3" class="footnum" href="#fnr.3">3</a>

Please note that there is a distinction between

a variable being assigned a value, and a variable having only one value left in its domain: a variable can have one value in its

domain without having an assigned value yet.

Survey

Please answer these questions at the bottom of your lab3.py file:

  • NAME: What is your name? (string)
  • COLLABORATORS: Other than 6.034 staff, whom did you work with on this lab? (string, or empty string if you worked alone)
  • HOW_MANY_HOURS_THIS_LAB_TOOK: Approximately how many hours did you spend on this lab? (number or string)
  • WHAT_I_FOUND_INTERESTING: Which parts of this lab, if any, did you find interesting? (string)
  • WHAT_I_FOUND_BORING: Which parts of this lab, if any, did you find boring or tedious? (string)
  • (optional) SUGGESTIONS: What specific changes would you recommend, if any, to improve this lab for future years? (string)


(We'd ask which parts you find confusing, but if you're confused you should really ask a TA.)

When you're done, run the online tester to submit your code.
Personal tools