Youve been given the job of programming a robot agent to exit a room filled with obstacles. The robot can face one of eight possible directions: north, south, east, west, northeast, northwest, southeast, and southwest. With each action the robot can either turn or move forward. Turning actions are left and right, both of which change the robots direction by 45. Move actions are move the robot forward by either one, two, or three distance units. The robots goal is to reach the exit from its starting point. You may refer to the robots position within the room with an x-y coordinate.

a. Describe a state representation, i.e. what is the minimum amount of information we must store to define the robots state.

b. If the room is an m x n grid what is the size of the state space? Assume all configurations are reachable from the start space.

c.What is the maximum branching factor of this problem?

d. Assume each action has the same cost. Is the Manhattan distance from the robots location to the exit an admissible heuristic? Why or why not?

e. Give a non-trivial admissible heuristic for this problem. Justify your answer. (Hint: consider the implications of the underlined text.)

f.(3 points) Suppose the robot must visit every location, (i, j), in the room before exiting.

i.Describe a state representation for the new problem.

ii.What is the size of the state space on an m x n grid?