Lab 3: Constraint Satisfaction

From 6.034 Wiki

Revision as of 12:39, 18 September 2017 by Landmann (Talk | contribs)
Jump to: navigation, search

This lab has not yet been released. It may change between now and the release time, and may contain inaccurate or misleading directions. You will certainly need to download the code again once it is released.

Contents


This lab is due by ??? at 10:00pm.

Before working on the lab, you will need to get the code. You can...

  • Use Git on your computer: git clone username@athena.dialup.mit.edu:/mit/6.034/www/labs/fall2020/lab4
  • Use Git on Athena: git clone /mit/6.034/www/labs/fall2020/lab4


All of your answers belong in the main file lab4.py. To submit your lab to the test server, you will need to download your key.py file and put it in either your lab4 directory or its parent directory. You can also view all of your lab submissions and grades here.


A Working Vocabulary

Before beginning, you may want to (re)familiarize yourself with the following terms:

  • variable
  • value
  • domain
  • constraint
  • assignment

Setting up a Constraint Satisfaction Problem

The Pokemon problem from 2012 Quiz 2, pages 2-4, is an example of a problem that can be solved using constrained search.

In this section, we will show you how to convert this problem into a ConstraintSatisfactionProblem instance using our constraint satisfaction API.

This problem requires two kinds of constraints:

  • the must-be-equal constraint requires that two things are equal
  • the must-not-be-equal constraint requires that two things are not equal

In this lab, a constraints is defined by a function that takes in two arguments, returning True or False depending on whether or not the given constraint is satisfied by the two arguments.

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 a problem, we first establish a new ConstraintSatisfactionProblem instance. For the Pokemon problem, there are five variables which we pass an an argument in a list: these are the five "questions" that need 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 named binary predicate (constraint function), not a lambda function:

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)

By default, the unassigned_vars list is initialized in alphabetical order.

To specify the order yourself, you can call .set_unassigned_vars_order with an ordered list of the unassigned variables:

# How to set the order of unassigned variables (not actually used for the Pokemon problem)
pokemon_problem.set_unassigned_vars_order(["Q4","Q2","Q3","Q1","Q5"])

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


We have finished setting up the variables, the domains, and the constraints.

Note that the Pokemon problem is already defined for you in test_problems.py. To get a copy of it, use the method get_pokemon_problem() in lab4.py.

This problem is now ready to be solved. All we need is a CSP solver...

Part 1: Writing a depth-first search solver

Your first task is to write a constraint solver that uses depth-first search to find a solution. Start by writing two helper functions, which may be useful within solve_constraint_dfs:

  • has_empty_domains(csp): returns True if the supplied problem has one or more empty domains. Otherwise, returns False.
  • check_all_constraints(csp): returns False if the problem's assigned values violate some constraint. Otherwise, returns True.

Each function takes in an argument csp, which is a ConstraintSatisfactionProblem instance.

Now you can use the helper functions to write the constraint solver:

def solve_constraint_dfs(problem) :

This is just like depth-first search as implemented in the search lab, but this time the items in the agenda are partially-solved problems instead of paths. Additionally, for this problem, we will also want to track the number of extensions so we can compare the different strategies for constraint propagation. At the end, instead of returning just a solution, you will return a tuple (solution, num_extensions), where

  • solution is the solution to this problem as a dictionary mapping variables to assigned values; or None if there is no solution to the problem
  • num_extensions is the number of extensions performed during the search

Here is a rough outline of how to proceed:

  1. Initialize your agenda and the extension count.
  2. Until the agenda is empty, pop the first problem off the list and increment the extension count.
  3. If any variable's domain is empty or if any constraints are violated, the problem is unsolvable with the current assignments.
  4. If none of the constraints have been violated, check whether the problem has any unassigned variables. If not, you've found a complete solution!
  5. However, if the problem has some unassigned variables:
    1. Take the first unassigned variable off the list using csp.pop_next_unassigned_var().
    2. For each value in the variable's domain, create a new problem with that value assigned to the variable, and add it to a list of new problems. Then, add the new problems to the appropriate end of the agenda.
  6. Repeat steps 2 through 6 until a solution is found or the agenda is empty.

Part 2: 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, we will write a helper function to eliminate inconsistent values from a variable's neighbors' domains:

For a given neighbor n of a variable v, if n has a value nval that violates a constraint with every value in v's domain, then nval is inconsistent with n and v and should be removed from n's domain.

This function should return an alphabetically sorted list of the neighbors whose domains were reduced, with each neighbor appearing at most once in the list. If no domains were reduced, return an empty list; if a domain is reduced to size 0, quit and immediately return None. This method should modify the input CSP.

def eliminate_from_neighbors(csp, var) :

Next, you will write a domain reduction algorithm. Recall that domain reduction utilizes a queue to keep track of the variables whose neighbors should be explored for inconsistent domain values. If you are not explicitly provided a queue from the caller, your queue should start out with all of the problem's variables in it, in their default order.

When doing domain reduction, you should keep track of the order in which variables were dequeued; the function should return this ordered list of variables that were dequeued.

If at any point in the algorithm a domain becomes empty, immediately return None.

def domain_reduction(csp, queue=None) :

Here is a rough description outline of the algorithm:

  1. Establish a queue if it's not supplied by the caller. (Hint: csp.get_all_variables() will make a copy of the variables list.)
  2. Until the queue is empty, pop the first variable var off the queue.
  3. Iterate over that var's neighbors: if some neighbor n has values that are incompatible with the constraints between var and n, remove the incompatible values from n's domain. If you reduce a neighbor's domain, add that neighbor to the queue (unless it's already in the queue).
  4. If any variable has an empty domain, quit immediately and return None.
  5. When the queue is empty, domain reduction has finished. Return a list of all variables that were dequeued, in the order they were removed from the queue. Variables may appear in this list multiple times.

This method should modify the input CSP.

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:

Question 1
How many extensions does it take to solve the Pokemon problem with DFS if you DON'T use domain reduction before solving it?

Put your answer, as an integer, in for ANSWER_1.

Question 2
How many extensions does it take to solve the Pokemon problem with DFS if you DO use domain reduction before solving it?

Put your answer, as an integer, in for ANSWER_2.

Hint: Use get_pokemon_problem() to get a new copy of the Pokemon problem each time you want to solve it with a different search method.

Part 3: 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) :

You can reuse most of your code from your solve_constraint_dfs algorithm, as domain reduction adds only a single step: each time you assign a value to a variable, you must call your domain_reduction on the variable you just assigned. This will look for and eliminate incompatible values from that variable's neighbors' domains.

Note that if domain_reduction eliminates all values from a variable's domain, the problem will be recognized as unsolvable when it is next popped off the agenda.

Answer the following question in your lab4.py file:

Question 3
How many extensions does it take to solve the Pokemon problem with propagation through reduced domains? (Don't use domain reduction before solving it.)

Put your answer as an int in for ANSWER_3.

Part 4: Propagation through singleton domains

The domain_reduction 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) :

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.

Now, you can use domain_reduction_singleton_domains to write a constraint solver that propagates through singleton domains:

def solve_constraint_propagate_singleton_domains(problem) :

Answer the following question in your lab4.py file:

Question 4
How many extensions does it take to solve the Pokemon problem with propagation through singleton domains? (Don't use domain reduction before solving it.)

Put your answer, as an integer, into ANSWER_4.

Part 5: Forward checking

Forward checking is even more restrictive than propagation through singletons: it never adds variables to the queue.

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.

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

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

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

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

def condition_domain_reduction(csp, var) :

def condition_singleton(csp, var) :

def condition_forward_checking(csp, var) :


Part 6: 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.

def solve_constraint_generic(problem, enqueue_condition=None) :

Answer the following question in your lab4.py file:

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

ANSWER_5 = None

Part 7: 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) :

Also write one for being non-adjacent.

def constraint_not_adjacent(m, n) :

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. Instead, write a function that takes a list of variables and returns a list containing, for each pair of variables, a constraint object requiring the variables to be different from each other. (You can model the constraints on the example above.) Note that order does NOT matter in a constraint, so you should only have one constraint between each pair of variables (e.g. have a constraint between A and B, OR, have a constraint between B and A).

def all_different(variables) :

Note: You should only use constraint functions that have already been defined. Don't try to create a new constraint function and use it in this function, because our tester will get confused.


API

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, in alphabetical order.
  • .domains: A dictionary associating each variable in the problem with its list of remaining values.
  • .assignments: A dictionary. Each variable that has already been assigned a value is associated with that value here. When the problem is entirely solved, assignments 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.

Note: 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) Returns the list of values in the variable's domain.
  • csp.set_domain(var, domain) Sets the domain of the variable to the specified list of values, sorted alphabetically/numerically.
  • csp.set_all_domains(domains_dict) Sets the .domains attribute to the specified dictionary. Does not sort domains.
  • csp.get_all_variables() Returns a list of all the variables in the problem.
  • csp.get_all_constraints() Returns a list of all the constraints in the problem.
  • csp.pop_next_unassigned_var() Returns first unassigned variable, or None if all variables are assigned. Modifies unassigned_vars list.
  • csp.set_unassigned_vars_order() Given an ordered list of unassigned variables, sets the list of unassigned vars. (By default, the unassigned_vars list is initialized in alphabetical order.)
  • csp.eliminate(var, val) Removes the value from the variable's domain, returning True if the value was found in the domain, otherwise False if the value wasn't found.
  • csp.get_assignment(var) If the variable has been assigned a value, retrieve it. Returns None if the variable hasn't been assigned yet.
  • csp.set_assignment(var, val) Sets 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. For convenience, also modifies the variable's domain to contain only the assigned value.
  • csp.constraints_between(var1, var2) Returns 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. Note: 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.get_neighbors(var) Returns a list of all the variables that share constraints with the given variable, ordered alphabetically.
  • csp.add_constraint(var1, var2, constraint_fn) Given two variables and a function to act as a constraint between them, creates a Constraint object and adds it to the list csp.constraints. The function constraint_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(list_of_constraints) 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.
  • csp.copy() Return a (deep) copy of this constraint satisfaction problem. This method is particularly useful because you will want to make a copy of the csp every time you assign a value to a variable.

Constraint objects

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

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

Note: Due to certain limitations in our tester, a Constraint object constructor must take a named constraint_fn as an argument, NOT a lambda function.


Survey

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

  • NAME: What is your name? (string)
  • COLLABORATORS: Other than 6.034 staff, with whom did you work 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