a) Imagine a treasure hunter agent who wishes to collect gold coins (indicated as numbered circles) in the maze shown below (Figure 1). The agent is not directional and can move one step in any direction (North, South, East, West) at any time step, as long as there is no wall in the way. The gold coins do not move. The agent's goal is to find a plan for collecting all coins using as few moves as possible. Assume that the grid has size M x N and there are 4 coins in the maze. Write the algorithm for a utility-based agent to solve the maze problem. Your algorithm should clearly define the state, possible states, rules and action for every step, as well as describe the following functions namely: UPDATE-STATE, RULE-MATCH and ACTION

b) Consider a graph search problem where for every action, the cost is at least E, with E > 0. Assume the used heuristic is consistent. State whether the following statements are true or false and give justifications for your choice.

i) Depth-first graph search is guaranteed to return an optimal solution.

ii) Breadth-first graph search is guaranteed to return an optimal solution.

iii) Uniform-cost graph search is guaranteed to return an optimal solution.

iv) Greedy graph search is guaranteed to return an optimal solution.

v) A* graph search is guaranteed to return an optimal solution.

vi) A* graph search is guaranteed to expand no more nodes than depth-first graph search.

viii) A* graph search is guaranteed to expand no more nodes than uniform cost graph search.

(1) & (4) (3)