Can anyone answer task 6.. if yes message +919852719784
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
- 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.
- 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. - 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? - 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. - 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?
- 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.
- 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*
