Assume that the robot can be in any of the white squares, and can do one step up, down, left, or right at each time. It cannot step into one of the black squares or outside of the boundary. The cost of a path is the number of steps in the path. At the squares marked with Ci are coffee shops where, if the robot goes to the square, it will be given coffee. Suppose the robot starts at the square marked as S, without coffee, and must end up at the square marked G carrying coffee.

Represent the grid world as a state-space search problem.

(a) What is a state for this problem?

(b) How many states are there?

(c) What is the start state?

(d) What is the goal function?

(e) Define (in pseudo-code or Python) the neighbor function that, given a state, returns a list of the neighbors of that state.

(f) What is a least-cost solution?

2 3 1