In this assignment you will implement a number of search and reinforcement learning algorithms. This assignment is worth 20% of your overall CS7IS2 mark. Please note this is an individual             assignment. You are allowed discuss the ideas with your colleagues but not share code.

The assignment heavily relies on the Pacman project developed by UC Berkley, specified at             https://inst.eecs.berkeley.edu/~cs188/sp20/projects/, with skeleton code available for download from individual project pages in that link.

Submissions are via Blackboard, and due by Friday March 11th 5pm.

You have an option to penalty-free submit assignment until Sunday evening (midnight) but please note there will be no blackboard/email/TA/lecturer support for assignment or any other technical issues past the official deadline.

Assignments submitted later than Sunday will be deducted 20% of the overall mark per day. Assignment specification and mark breakdown

1.    Part 1 – Search algorithms implementation - 25 points

2.    Part 2 – MDP and RL implementation - 50 points

3.    Part 3 – MDP and RL analysis - 25 points Total = 100 points

Part 1

In this part you will implement, DFS, BFS, UCS, and A* search. Please follow the instructions on

https://inst.eecs.berkeley.edu/~cs188/sp20/project1/

You are only required to answer questions Q1 to Q4 (but feel free to do others for fun!). You only have to edit and submit 2 files: search.py and searchAgents.py

Important: For each function you add, please in the comment in specify which problem/sub-problem it is addressing.

Part 2

In this part you will implement MDP and Reinforcement Learning algorithms. Please follow the instructions on https://inst.eecs.berkeley.edu/~cs188/sp20/project3/

You are only required to answer questions Q1 to Q9 (but feel free to Q10 for fun too!).                     You only have to edit and submit 3 files:  valueIterationAgents.py, qlearningAgents.py, analysis.py

Important: For each function you add, please in the comment in specify which problem/sub-problem is it addressing.

Part 3

This part consists of analysing performance of variations of value-iteration and RL algorithms from part 2. Please answer the following questions, including screenshots of your code execution and     explanations:

1.    Part 2-Q1 - Run value iteration on default BookGrid for 5, 10, 15, 20, 30, 50 iterations. Show screenshots and comment at which point did the values of states and actions converge

2.    Part 2-Q1 - Run value iteration on BridgeGrid for 10 iterations and show the result. Modify discount rate from the default 0.9 to 0.1, and run again for 10 iterations.  Comment if/why results differ.

3.    Part 2 – Q4 - Run value iteration on MazeGrid for 100 iterations. Show final screenshot. Then run asynchronous value iteration you just implemented on the same grid for 100 iterations.   Show screenshot. Explain the difference. Run it again for 1000 iterations and compare the      results.

4.    Part 2 – Q6 and Q7 - Run qQlearning agent for 100 iterations on default BookGrid and              compare the Q-values to those obtained when running value iteration. Run Q-learning with a few variations of noise, epsilon, and discount parameters. Show screenshots and explain the  behavior/influence of parameters.

5.    Part 2- Q9 - Run Q-learning in Pacman, as specified in Q9 from the Pacman RL project, using   the parameters specified in the question (2000 iterations, small grid). Show screenshots of     your results (average reward, and win/loses). Now run it for 2000 iterations in the                    mediumGrid in Pacman and show the results. What do you observe? Increase the number of training iterations (and if needed modify epsilon) to achieve desired Pacman performance in medium grid. Show screenshots of results and list which parameters/number of iterations      did you have to use.

To submit:

Please submit a single zip file named NAME_SURNAME_STUDENTID_assignment1.zip containing:

1.    Modified .py files from parts 1 and 2

2.    Pdf of a self-assessment marking sheet for parts 1 and 2 (instructions below)

3.    Pdf of your answers to part 3

Self-assessment instructions

You are also asked to perform self-assessment of your implementation. Autograding scripts are provided alongside each of the sections.