Among the many applications of the constraint satisfaction problem (CSP) paradigm, one of the first was to perform a process called line-labeling to attempt to use a 2-dimensional image of a “blocks-world” environment to infer its 3-dimensional structure so that a robot can reconfigure the blocks to achieve a goal. In this task, you will utilize code that we provide to you, and extend it with code that you write, to develop a deeper understanding of the CSP paradigm and its application to line labeling.

As an introduction to the line-labeling problem, see the separate document provided that summarizes it.

Part of the line labeling code has been written for you (Python 2.7). Parts a to i will provide more instruction on finishing the code.

Many of the utility functions written in diagram.py will be helpful. The class Vertex is used extensively in diagram.py and is defined in vertex.py.

You will use main.py to run the code. Example commands: python main.py examples/cube.txt propagation -p ac_3 # only run AC3 on cube.txt

python main.py examples/cube.txt backtracking -p ac_3 -o mrv # find all solutions of AC3 and MRV

python main.py examples/cube.txt backtracking -s -p ac_3 -o mrv # find ONE solution using backtracking with AC3 and MRV

python main.py examples/cube.txt backtracking -p forward_checking -o first_unassigned # find ONE solution using backtracking with forward checking and the first unassigned heuristic

Run python main.py -h for detailed usage instructions.

row#

#solns

propagation

ordering

# assignments TOWER

# assignments POIUYT

1

all

No-prop

First-unassigned

2

all

Forward-checking

First-unassigned

3

all

Arc-consistency

First-unassigned

4

all

No-prop

MRV

5

all

Forward-checking

MRV

6

all

Arc-consistency

MRV

7

one

No-prop

First-unassigned

8

one

Forward-checking

First-unassigned

9

one

Arc-consistency

First-unassigned

10

one

No-prop

MRV

11

one

Forward-checking

MRV

12

one

Arc-consistency

MRV

13

all

Arc-consistency**

MRV

1. a. The method for backtracking, search_solutions in diagram.py was left unfinished. Finish the code to fill in the first 2 rows of the table.
2. b. Implement arc consistency and fill in the 3rd row of the table. Fill in the ac_3 method of the D iagram class in diagram.py.
   For each of the diagrams, briefly explain the extent to which it did (or did not) affect the number of variable assignments compared to forward-checking, and why.
3. c. In class, we will have talked about how the order in which variables are assigned can make a difference to the search effort. In the current code the first_unassigned method chooses based on alphabetical order. As a first step at considering this, modify first_unassigned to return a random unassigned vertex instead. Test out the new random heuristic and record the number of variable assignments for 10 trials for both diagrams and each of the 3 propagation methods.
   What do your results tell you about the impact of variable ordering on the search effort for each of these diagrams?
4. d. One way of ordering vertices that heuristically can decrease the number of (tentative) assignments needed to find solutions, as discussed in class, is to assign the variable next that has the fewest number of possible values to assign – the Minimum Remaining Values (MRV) heuristic.
   Implement this heuristic and add it to your code in the method mrv. Break ties based alphabetical ordering (as was done in first_unassigned). With your new code, fill in rows 4-6 of the Table.
5. e. Use observation(s) from the answer to part c to explain the impact of the MRV heuristic in rows 4-6 you just filled in. Particularly address the fourth row performance on the TOWER diagram. What do the results tell you about the mrv heuristic?
6. f. As you did in part d, experiment with a “random” MRV heuristic (break ties randomly). Comment on whether the variance in the number of tentative assignments differs from part c, and briefly (in a sentence or two) explain why or why not.
7. g. In most applications of constraint satisfaction where there might be multiple solutions, the user only cares about getting one legal solution (for example, for scheduling a conference room, packing a box, the n-queens problem in class). Fill in rows 7-12 using the -s command line argument in main.py (see examples). For each of the TOWER and POIUYT diagrams, briefly explain how searching for just one solution (rows 7-12) impacts the number of variable assignments performed compared to the first 6 rows where all solutions were found.

h. Finally, create a version where you modify the search_solutions method to apply arc-consistency (ac_3) to every vertex before any search is done. Fill in row 13 of the table, and briefly explain any difference(s) with row 6. 

*STARTER CODE ATTACHED*