SOLVED CS-331 Introduction to Artificial Intelligence Assignment 1

  Part 1 (theory): Question 1: [25 marks, 5 marks each] The search algorithms you have learnt in CS-331 can be used to traverse the graph shown in Fig 1.1. As you may already know, traversal from each algorithm will result into a different tree. Figure 1.1 was traversed using 7 different search algorithms, and the corresponding tree (R1 to R7) for each algorithm has been given below. In each of the 7 diagrams, where applicable, the cost calculated by that algorithm for each node visited is given next to it. Please note that the children of each node were traversed in an alphabetical fashion. A tabular depiction of the Heuristic functions used for some of the traversals is given in Fig 1.2. To help you correctly interpret Fig 1.2, I will interpret the first row of the table for you. The first row means that H1(A)=3 and H2(A)=3, where H1 and H2 are the two heuristic functions used. Your job is to find out for each tree diagram (R1 to R7) the search algorithm that was used to generate it. Mention whether or not the path generated is optimal (by showing that a path with lesser total cost exists or not) and whether or not any heuristic function (H1 or H2 and why do you think so?) was used. You are required to select one of the following algorithms for each tree: 1. Depth FS 2. Uniform Cost Search 3. Best FS (greedy) 4. A* 5. Breadth FS Fig 1.1 Fig 1.2 R1 R2 R3 R4 R5 R6 R7 Question 2: [20 marks, 5 marks each] Use search algorithms #1, #3, #4 and #5 mentioned in Question 1 to write down the ordered list(s) of visited nodes of the tree shown in Fig 2.1 for each of them. Question 3: [20 marks, 4 marks each] This question has several parts: i. Briefly compare Breadth-First Search (BFS) and Depth First Search (DFS). ii. What issue does Depth limited Search resolve? iii. Precisely describe A* search Algorithm. iv. How does uniform cost search differ from A* search? v. Which of the four algorithms mentioned so far are complete? Which ones are optimal? Part 2 (coding): Question 1: [85 marks, 15 marks each for A* search and recursive algorithms, 10 marks for each of the rest] In this part, you are required to implement the famous game Pacman with the help of the search algorithms you have learnt in class. All files for this part have been uploaded on LMS. You are required to edit the skeleton-code given in “search.py” using any text-editor of your choice (Sublime is recommended). An auto-grader for each question is given in “Pacman.ipynb”, which can be executed using Jupyter. Please do not edit the code in any of the other files. *** Z The goal node is Z! If the heuristic of a node is not given, assume it is zero! Fig 2.1