Logistics

Submission Guidelines

The due date for this assignment is 29th September 2023 at 23:59. You are allowed at most three late days. You lose 10% of the maximum points of the submission for every late day you use. The submission is tracked using Gradescope. The written section and programming section are graded and penalized separately.

For example, if you submit the programming section on time and the written section one day late, you will lose 10% of the maximum points for the written section (5 in this case).

You must submit the following files to Gradescope (note that there are two separate Gradescope submissions):

1. A (legible) PDF containing the solutions to the written section.  You can write your solutions by hand, use a tablet, or typeset your solutions in LATEX. We only ask that you make it easy to read and not too verbose so that graders don’t struggle to understand your writing.

2. The completed Agent.py file to the programming section

Grading Policy

You have one week to submit aregrade request once the grades for your homework are out. We will provide solutions, along with the exact grading rubric used.

Collaboration

Collaborating with people is encouraged, but plagiarism is strictly prohibited.

Generative AI

We acknowledge that generative AI models like ChatGPT are now easily available and that knowing how to use them is becoming increasingly important. While we do not encourage its use, we do not prohibit it either. ChatGPT can enhance your work, but it can border on plagiarism if used improperly. Whenever you use any generative AI models in EECS 492, please explicitly state so! Failure to do this will be considered an honor code violation. Also ensure that you do the following

•  State which model you used

• Include the prompt(s) that you gave the model

(b) Identify the characteristics of the environment and provide a brief justification as to why you characterized the environment in that way. [7 points]

As a reminder, the characteristics of the environments are as follows:

• Fully observable vs. partially observable

•  Single-agent vs. multi-agent

• Deterministic vs. nondeterministic

•  Episodic vs. sequential

•  Static vs. dynamic

• Discrete vs. continuous

• Known vs. unknown

1.2 Hands-On Search [12 Points]

Consider the search tree shown in Figure 2, including nodes A through J. The state of node A is our initial state (shown in yellow). Nodes F and I share the same state and are valid goals (shown in blue). The label by an edge is the cost associated with the path between the edge’s vertices.

Assume that when a node is expanded, its children are added to the frontier in al- phabetical order. For instance, when node A is expanded, node B will be added to the frontier first, and then node G. If the last element is popped, the node popped would be node G.

For frontiers that use a priority queue, nodes with the same priority (path-cost, heuristic value, or the sum of path-cost and heuristic value) will be popped in alphabetical order. For instance, if node B and node C have the same priority, node B is popped first, followed by node C.

An admissible heuristic function is provided to you in Figure 3, which gives the value of the heuristic function for each node’s state.

3.  Consider a grid world with a single goal, where the allowed moves are LEFT, RIGHT, UP, and DOWN (you are once again unable to move diagonally). Let M(s) be the Manhattan distance from state s to the goal, and let E(s) be the Euclidean distance from s to the goal.

You also have the following function h :

Function h(s):

r - a random number from 1 to 10, inclusive of both;

if r ≤ 6 then

return M(s);

end

return E(s);

Is ha consistent heuristic? Justify your answer.

1.5 Hill Climbing [10 Points]

Your friend guards each of their files with a 2-digit PIN code, but since they keep forgetting it, they decide to implement an AI agent that uses hill climbing to find it automatically. Each PIN comprises two integers, P1  and P2 , each of which can take values from 0 to 9. They implement the following agent - the agent automatically submits a candidate PIN, and if it’s correct, the file unlocks. If the guessed PIN is incorrect, the agent receives a score that measureshow good the guess was. If the two digits entered are x andy, then the score returned is

h(x, y) = −(|x − P1 | + |y − P2 |)

The agent then uses a hill-climbing algorithm to attempt to find the PIN. The algorithm generates neighbors by creating all guesses that are different by one digit. In other words, if the current state is (x, y), the neighbors generated are (x − 1, y), (x + 1, y), (x, y − 1), and (x, y + 1). The algorithm doesn’t generate any states outside the valid (0,0) to (9,9) range. In the event of a tie in the h value, the state with the lowest x value is selected.

(a) Assume that the initial guess for the PIN is (5,5) and that the actual PIN is (2,9). List the steps taken by the hill-climbing algorithm till it terminates. If it does not, explain why

(b) Is this algorithm guaranteed to find the correct PIN code? Feel free to use a graphing tool like GeoGebra to help you solve this.

(c) Now assume that the algorithm is hard-coded to terminate after steps.  Does your answer to part (b) change if

(i) = 10

(ii) = 20

(d)  It turns out that the code had a typo. The parenthesis around the first − sign was missing. The heuristic is now

ℎ(x, ) = −|x − 51 | + | − 52 |

Is this version of his hill-climbing search guaranteed to find a solution? Explain your answer.

2 Programming [50 Points]

2.1    Setup

All programming assignments for this course use Python.  If you’re new to Python or not very experienced with it, please come to office hours; we’re happy to help! Werecommend also checking out the Python Cheatsheet. The topics you’d need from here are: Basics, Built- in Functions, Control Flow, Functions, Lists, Tuples, Dictionaries, Sets, OOP, and Virtual Environments. There’salso a pinned Piazza postwith more Python resources.

This assignment was designed for Python 3.10 (though the newest version, 3.11 should also work out of the box).

We highly recommend creating a new virtual environmentfor the assignment. You can then simply install the requirements by running the command

python  -m  pip  install  -r  requirements.txt

2.2 Problem Statement

In this programming section, you’ll be coding an agent that searches amaze. More specifically, you’ll be implementing the following search algorithms -

•  BFS

•  DFS

• UCS

• A-Star

Unlike lectures and previous examples, these mazes may (or may not) have multiple goals. As such, we’ll be modifying our heuristic to be the Euclidean distance to the closest goal (See Q 1.4.1 in the Written Section)

Complete the Agent.py file and submit it to Gradescope. You will be evaluated using the Autograder on 10 test mazes onevery algorithm. In Agent.py, you must complete the following functions

i  heuristic_function : returning the minimum Euclidean (straight line) distance between the AStar Node’s coordinate and the end coordinates

ii the three comparator functions for A-star nodes __eq , lt , gt iii goal_test

iv  expand_node

v  bfs

vi dfs

vii  ucs

viii  astar

For simplicity, please add nodes to the frontier directly instead of updating an existing node. Please go through maze.py and agent.py before you begin! The files are annotated with TODO in every location where you need to add code and have multiple comments, tips, and recommendations for how to proceed. In addition, you will never need to modify maze.py.