Consider a grid with n rows and m columns. The agent will start at a particular cell and its job will be to move to a goal cell. The agent will have the following actions available to it:

I. Move up, the cost of this action is +3

II. Move down, the cost of this action is -2

III. Move Right, the cost of this action is -1.5

IV. Move Left, the cost of this action is +0.5

The agent wants to find a path between the starting cell and the goal cell in as low of a cost as possible. However, the grid has special cells marked as W and X, if your agent moves to the W cell, then the agent will be teleported a cell (randomly selected) next to the goal state, but the cost will be +7. If your agent moves to the X cell then your agent will be teleported to the starting cell, however, the cost will be -7.

Here the agent is at the position (0,0), and the goal is at the position (3,7). If the agent moves to the W cell at (4,2), then the agent will be transported to either (3,6) or (2,7) or (4,7).

Given the scenario above, answer the following questions:

I. What is the PEAS description of the agent?

II. Describe its task environment.

III. Model this problem as a search problem IV. What is the branching factor of this problem?

V. Can we use BFS or DFS on this problem? Explain your answer.

VI. Given the scenario above, write down the path that will be discovered by UCS?

VII. If we can run BFS on this problem, will BFS and UCS give the same answer? Explain

VIII. Will Euclidean distance be an admissible heuristic? Will Manhattan distance be an admissible heuristic? Prove your answer.

IX. Come up with your own admissible heuristic, and solve the problem above using your heuristic and A* search.

For example, take a look at a 7 x 8 grid below: X W X G W A For example, take a look at a 7 x 8 grid below: X W X G W A