COMP341 -  Introduction to Artificial Intelligence - Assignment 1 - Solved

Make sure you read and understand every part of this document
This programming assignment will test your knowledge and your implementation abilities of what you have learned in the uninformed and informed search parts of the class. You are asked to complete a coding part and answer a few questions about how it runs. The coding part of the homework will follow the Berkeley CS188 Spring 2020 pacman project P1: Search at https://inst.eecs.berkeley. edu/~cs188/sp20/project1/. The questions for the report part are given in this document.

This homework must be completed individually. Discussion about algorithms, algorithm properties, code structure, and Python is allowed but group work is not. Coming up with the same approach and talking about the ways of implementation leads to very similar code which is treated as plagiarism! Furthermore, do not discuss the answers directly as it will lead to similar sentences which is treated as plagiarism. Any academic dishonesty, will not be tolerated. By submitting your assignment, you agree to abide by the Ko¸c University codes of conduct.

You may find yourself having trouble implementing the coding part. In this case, we are going to let you use someone else’s code to answer the given questions, as long as you credit the person or the website you take the code from.



Part 1: Programming
You are going to do the 8 programming questions about search given in the website. You are only required to change search.py and searchAgents.py. If you have any issues with other parts of the code let your instructor or TA know ASAP, even if you manage to solve your problem. Use the data structures in util.py for the autograder to work properly. If the you think you have the right answer but the autograder is not giving you any points, try to run it on individual questions (look at P0 for details on how to use the autograder.py).

Hints
•    We understand that having too many files to go through might be troublesome, however keep in mind that you do not need to go over all the files. Read the P1:Search documentation in the Berkeley Website and the comment sections of the relevant files/functions that you are going to work on. If you start worrying about implementation details of Pacman, you will get lost and lose track of how to handle the assignment requirements.

•    Always read the comment sections of the given code before starting your implementation. These comments are very useful and they will save you precious time later on.

Part 2: Report
This part includes answering the following questions based on your programs’ output on the given pacman tests. Look specfically at bigMaze and the openMaze for stark comparisons.

You are expected to answer the questions concisely. Five sentences is more than enough for most of them. Limit yourself to 200 words. It is okay if you over-generalize, as long as your direction is clear and correct. Note that some answers are already in the provided link to the Berkeley site.


Written Q1:

What are some differences between DFS and BFS in terms of path cost and number of expanded nodes?

When and why would you prefer BFS over DFS? When and why would you prefer DFS over BFS?

Written Q2:

What are some differences between UCS and A* in terms of path cost and number of expanded nodes?

When and why would you prefer UCS over A*? When and why would you prefer A* over UCS?

Written Q3:

Comment on your choice of state in the finding all the corners problem. Why does it allow you to solve the problem?

Written Q4:

Comment on your choice of heuristic in the finding all the corners problem.. Why did you settle on that heuristic? Why is it admissible and consistent?

Written Q5:

Comment on your choice of heuristic in the eating all the dots problem. Why did you settle on that heuristic? Why is it admissible and consistent?

Written Q6:

What are some practical differences between a consistent and an inadmissible heuristic, in terms of path cost and number of expanded nodes? When and why would you prefer an inadmissible heuristic over a consistent one? When and why would you prefer a consistent heuristic over an inadmissible one?