1Part I: Written Problems (50 points)0.1 Constraint Satisfaction (16 points)Consider a constraint satisfaction problem where there are six variables A, B, C, D, E, and F, each with domain 1, 2,...

1 answer below »
Artificial Intelligence : Constraint Satisfaction, Adversarial Search and
Propositional Logic


1 Part I: Written Problems (50 points) 0.1 Constraint Satisfaction (16 points) Consider a constraint satisfaction problem where there are six variables A, B, C, D, E, and F, each with domain 1, 2, 3, 4, 5, 6. There are six constraints: A > F, F > E, F = D, B > A, A = C, and B · D. (a) (8 pts) Show how backtracking can be use to solve this problem. To select variables, use the most constrained variable heuristic, breaking ties using the most constraining variable heuristic. If ties still exist, break them alphabetically. To select values, use the least constraining value heuristic, breaking ties by preferring smaller values. Indicate the first 20 branches visited in the search tree (or stop when the solution is reached). Write them in text form with each branch on one line. For example, suppose we had variables X, Y and Z with domains 0, 1, and constraints X ̸= Y, Y=Z. The first two branches visited in the search tree should be written as: Y = 0, X = 0 failure (1) Y = 0, X = 1, Z = 0 solution (2) (b) (5 pts) Show how forward checking can be used to solve this problem. To select variables, use the most constrained variable heuristic, breaking ties using the most constraining variable heuristic. If ties still exist, break them alphabetically. To select values, use the least constraining value heuristic, breaking ties by preferring smaller values. Indicate the first 20 branches visited in the search tree (or stop when the solution is reached). (c) (3 pts) Apply constraint propagation (arc consistency) to eliminate values from the initial do- mains of the variables. Show the resulting domain of each variable after constraint propagation is applied. 0.2 Problem Encoding and Propositional Logic (20 points) Recall that the Pigeonhole problem concerns putting n + 1 pigeons into n holes. The constraints on this problem are: (1) each pigeon is assigned a hole and (2) each hole can accommodate at most one pigeon. (a) (10 pts) Assuming that the binary variable xij is True if and only if pigeon i is in hole j, give the clauses that encode the constraints of the problem. Make sure that each set of clauses is accompanied by an English description. (b) (10 pts) How many clauses do you need? Express your answer in big-O notation. 0.3 Adversarial Search (14 points) Consider the game tree below. (a) (2 pts) What should be the next move for the maximizer? (b) (6 pts) Identify all the nodes that can be pruned using alpha-beta pruning. Assume a left-to- right evaluation of the nodes. (c) (6 pts) Identify all the nodes that can be pruned using alpha-beta pruning. Assume a right- to-left evaluation of the nodes. Part II: Programming (100 points) In this problem, you will implement a CSP solver that takes exactly three arguments from the com- mand line: 1. A .var file that contains the variables in the CSP to be solved and their domains. Each line of the file contains a variable (represented by a single letter), followed by a colon and its possible values, each of which is an integer. For instance, the line “A: 1 2 3” indicates that the possible values for variable A are 1, 2, and 3. Note that there is a space separating the domain values. 2. A .con file that contains the constraints. Each line corresponds to exactly one constraint, which involves two variables and has the form VAR1 OP VAR2. VAR1 and VAR2 are the names of the two variables involved, and OP can be one of four binary operators: = (equality), ! (inequality), > (greater than), and < (less than). 3. the consistency-enforcing procedure, which can take one of two values: none and fc. if none is used, no consistency-enforcing procedure is applied, and the solver simply uses backtracking to solve the problem. fc indicates that the solver will use forward checking to enforce consistency. note: · whenever the solver needs to choose a variable during the search process, apply the most con- strained variable heuristic, breaking ties using the most constraining variable heuristic. if more than one variable remains after applying these heuristics, break ties alphabetically · whenever the solver needs to choose a value during the search process, apply the least constrain- ing value heuristic. if more than one value remains after applying this heuristic, break ties by preferring smaller values. your program should allow exactly three arguments to be specified in the command line invocation of your program, in the order in which they are listed above. sample input files will be available in the assignment page of elearning. your program should write to stdout the branches visited in the search tree (or stop when the solution is reached). by branches we mean an assignment that violates a constraint or that leads to one or more unassigned variables having empty domains (when using forward checking). write them in text form with each branch on one line. for example, suppose we had variables x and y with domains 0, 1, 2, variable z with domain 1, 2, and constraint y=z. the branches visited in the search tree without forward checking should be written as: 1. z = 1, x = 0, y = 0 failure (3) 2. z = 1, x = 0, y = 1 solution (4) however, if forward checking is applied, the output should be: 1. z = 1, y = 1, x = 0solution(5) important: note that the printed branches should keep a consistent variable ordering. variables should be printed in the order they are assigned values. do not output anything else to stdout. any program that does not conform to the above specification will receive no credit. to implement the program, you should use python 3. you may not use external libraries. your code will be run on a linux distribution, so you should make sure that it runs/compiles on the utd linux server (see https://cs.utdallas.edu/about/computing-facilities/). if you have any questions, please send an email to the staff. 0.3.1 submission directly submit all your source files as a zip file to elearning. note that you must provide an entry point main.py for your code to run (these are the only files that we will directly run when grading). if you worked in a group, make sure to add your partner when you submit! 0.3.2 example files we will provide the corresponding .con and .var files for 3 test cases (ex1, ex2, and ex3), along with the correct output using both forward checking and no consistency enforcing procedure (fc, none). you should use these test cases to verify the basic functionality of your code and output formatting; however, remember that we will test your code on hidden test cases; so correctly solving ex1, ex2, and ex3 does not guarantee you will get all points. important note: we will be using moss for plagiarism detection on all programming assignments (you can look it up, it’s quite powerful). any students caught cheating will receive a 0 on the corre- sponding assignment and will be reported accordingly. (less="" than).="" 3.="" the="" consistency-enforcing="" procedure,="" which="" can="" take="" one="" of="" two="" values:="" none="" and="" fc.="" if="" none="" is="" used,="" no="" consistency-enforcing="" procedure="" is="" applied,="" and="" the="" solver="" simply="" uses="" backtracking="" to="" solve="" the="" problem.="" fc="" indicates="" that="" the="" solver="" will="" use="" forward="" checking="" to="" enforce="" consistency.="" note:="" ·="" whenever="" the="" solver="" needs="" to="" choose="" a="" variable="" during="" the="" search="" process,="" apply="" the="" most="" con-="" strained="" variable="" heuristic,="" breaking="" ties="" using="" the="" most="" constraining="" variable="" heuristic.="" if="" more="" than="" one="" variable="" remains="" after="" applying="" these="" heuristics,="" break="" ties="" alphabetically="" ·="" whenever="" the="" solver="" needs="" to="" choose="" a="" value="" during="" the="" search="" process,="" apply="" the="" least="" constrain-="" ing="" value="" heuristic.="" if="" more="" than="" one="" value="" remains="" after="" applying="" this="" heuristic,="" break="" ties="" by="" preferring="" smaller="" values.="" your="" program="" should="" allow="" exactly="" three="" arguments="" to="" be="" specified="" in="" the="" command="" line="" invocation="" of="" your="" program,="" in="" the="" order="" in="" which="" they="" are="" listed="" above.="" sample="" input="" files="" will="" be="" available="" in="" the="" assignment="" page="" of="" elearning.="" your="" program="" should="" write="" to="" stdout="" the="" branches="" visited="" in="" the="" search="" tree="" (or="" stop="" when="" the="" solution="" is="" reached).="" by="" branches="" we="" mean="" an="" assignment="" that="" violates="" a="" constraint="" or="" that="" leads="" to="" one="" or="" more="" unassigned="" variables="" having="" empty="" domains="" (when="" using="" forward="" checking).="" write="" them="" in="" text="" form="" with="" each="" branch="" on="" one="" line.="" for="" example,="" suppose="" we="" had="" variables="" x="" and="" y="" with="" domains="" 0,="" 1,="" 2,="" variable="" z="" with="" domain="" 1,="" 2,="" and="" constraint="" y="Z." the="" branches="" visited="" in="" the="" search="" tree="" without="" forward="" checking="" should="" be="" written="" as:="" 1.="" z="1," x="0," y="0" failure="" (3)="" 2.="" z="1," x="0," y="1" solution="" (4)="" however,="" if="" forward="" checking="" is="" applied,="" the="" output="" should="" be:="" 1.="" z="1," y="1," x="0" solution="" (5)="" important:="" note="" that="" the="" printed="" branches="" should="" keep="" a="" consistent="" variable="" ordering.="" variables="" should="" be="" printed="" in="" the="" order="" they="" are="" assigned="" values.="" do="" not="" output="" anything="" else="" to="" stdout.="" any="" program="" that="" does="" not="" conform="" to="" the="" above="" specification="" will="" receive="" no="" credit.="" to="" implement="" the="" program,="" you="" should="" use="" python="" 3.="" you="" may="" not="" use="" external="" libraries.="" your="" code="" will="" be="" run="" on="" a="" linux="" distribution,="" so="" you="" should="" make="" sure="" that="" it="" runs/compiles="" on="" the="" utd="" linux="" server="" (see="" https://cs.utdallas.edu/about/computing-facilities/).="" if="" you="" have="" any="" questions,="" please="" send="" an="" email="" to="" the="" staff.="" 0.3.1="" submission="" directly="" submit="" all="" your="" source="" files="" as="" a="" zip="" file="" to="" elearning.="" note="" that="" you="" must="" provide="" an="" entry="" point="" main.py="" for="" your="" code="" to="" run="" (these="" are="" the="" only="" files="" that="" we="" will="" directly="" run="" when="" grading).="" if="" you="" worked="" in="" a="" group,="" make="" sure="" to="" add="" your="" partner="" when="" you="" submit!="" 0.3.2="" example="" files="" we="" will="" provide="" the="" corresponding="" .con="" and="" .var="" files="" for="" 3="" test="" cases="" (ex1,="" ex2,="" and="" ex3),="" along="" with="" the="" correct="" output="" using="" both="" forward="" checking="" and="" no="" consistency="" enforcing="" procedure="" (fc,="" none).="" you="" should="" use="" these="" test="" cases="" to="" verify="" the="" basic="" functionality="" of="" your="" code="" and="" output="" formatting;="" however,="" remember="" that="" we="" will="" test="" your="" code="" on="" hidden="" test="" cases;="" so="" correctly="" solving="" ex1,="" ex2,="" and="" ex3="" does="" not="" guarantee="" you="" will="" get="" all="" points.="" important="" note:="" we="" will="" be="" using="" moss="" for="" plagiarism="" detection="" on="" all="" programming="" assignments="" (you="" can="" look="" it="" up,="" it’s="" quite="" powerful).="" any="" students="" caught="" cheating="" will="" receive="" a="" 0="" on="" the="" corre-="" sponding="" assignment="" and="" will="" be="" reported="">
Answered 4 days AfterOct 16, 2022

Answer To: 1Part I: Written Problems (50 points)0.1 Constraint Satisfaction (16 points)Consider a...

Raavikant answered on Oct 20 2022
47 Votes
SOLUTION.PDF

Answer To This Question Is Available To Download

Related Questions & Answers

More Questions »

Submit New Assignment

Copy and Paste Your Assignment Here