You (represented as a smiley face on the diagram below) are trapped in a maze and needs to escape from it. Unfortunately there is a locked door ( ) between you and the exit (), and you have to take the key () before you can unlock the door. You are not facing any special direction and can move one step in any direction at any time step, as long as there is no wall in the way. Alternatively you can pick up the key (if you are in the right location), or you can unlock the door (if you have the key and are in the right location). Neither the key nor the door can move around on their own. Your goal is to find a plan for escaping the maze using as few moves as possible. Assume that the grid has size M N .

a) Define the task environments and their properties. b) Write the algorithm for a utility-based agent to solve the above maze problem.

c) Describe 5 advantages of hill climbing search algorithm.

d) Using the hill climbing search approach, find the best path for the tree described below. Use 'a' as starting point. Show your workings.

[10] [4] d) a [0] b) k [0] i [6] k [0]