COMP3411/9814 Artificial Intelligence Term 1, 2022

and  start40. Run each of the following algorithms on each of the 5 start states:

(I)   [ucsdijkstra]

In each case, record in your table the number of nodes generated during the search.

If the algorithm runs out of memory,just write “Mem” in your table. If the code  runsforfive minutes without producing out- put, terminate the process by typing Control-C and then “a”, and write “Time” in your table. Note that you will need  to re-startprolog each time you switch to a different search.

b)  Briefly discuss the efficiency of these four algorithms (including both time and memory usage).

Question 2: Heuristic Path Search for 15-Puzzle

In this question you will be exploring an Iterative Deepening version of the Heuristic Path Search algorithm discussed in the Week 2 Tutorial. Draw up a table in the           following format:

The top row of the table has been filled in for you (to save you from running some rather long computations).

(a)  Run [greedy] for start50 , start60 and start64 , and record the values returned for G and N in the last row of your table (using the Manhattan Distance heuristic defined    in puzzle15.pl).

(b) Now copy idastar.pl to a new file heuristic.pl and modify the code of this new file  so that it uses an Iterative Deepening version of the Heuristic Path Search algorithm discussed in the Weak 3 Tutorial Exercise, with w = 1.2 .

In your submitted document, briefly show the section of code that was changed, and the replacement code.

(c) Run [heuristic] on start50 , start60 and start64 and record the values of G and N in your table. Now modify your code so that the value of w is 1.4, 1.6 ;  in each case,   run the algorithm on the same three start states and record the values of G and N in   your table.

(d) Briefly discuss the tradeoff between speed and quality of solution for these five algorithms.

Part 2 - Constraint Solving

Question 1: Arc Consistency

Consider a scheduling problem, similar to the one discussed in lectures, where there are five variables A , B , C, D , and E, each with domain {1, 2, 3, 4}. Suppose the constraints  are: E − A is even, C ̸= D , C > E, C ̸= A , B > D , D > E, B > C.

Show how arc consistency can be used to solve this problem. To do this you need to

•  draw the constraint graph,

•  show which elements of a domain are deleted at each step, and which arc is responsible for removing the element,

•  show explicitly the constraint graph after arc consistency has stopped.

•  show how splitting domains can be used to solve this problem. Include all arc consistency steps.

Question 2: Variable Elimination

Consider the constraint graph, below, with named binary constraints. r1 is a relation on A and B , which we can write as r1(A , B), and similarly for the other relations. Consider solving this network using VE.

(a) Suppose you were to eliminate variable A . Which constraints are removed? A

constraint is created on which variables? (You can call this r11).

(b) Suppose you were to subsequently eliminate B (i.e., after eliminating A). Which

relations are removed? A constraint is created on which variables?