A man is traveling to the market with a fox, a goose, and a bag of oats. He comes to a river. The only way across the river is a boat that can hold the man and exactly one of the fox, goose, or bag of oats. The fox will eat the goose if left alone with it, and the goose will eat the oats if left alone with it. How can the man get all his possessions safely across the river?

We will call states where something gets eaten illegal and consider them as part of the state space, but from which there is no return; i.e., there is no way to go to any other state (including back to the previous state) from such an illegal state.

One way to represent this problem is as a state vector with components (M, F, G, O) where M=man, F=fox, G=goose, and O=oats are binary variables that are 0 if the man/fox/goose/oats are on the near bank, and 1 if on the far bank. Thus, the start state is (0, 0, 0, 0). Note that the boat is always on the same side of the river as the man.

1. What is the goal state (using the (M, F, G, O) notation)? [10 points]
2. How many states (both legal and illegal) in this state-space? List them here. [20 points]
3. How many legal states in this state-space? List them here. [20 points]
4. What could be a good cost function for this problem [Action cost for moving from one state to another state (c(s, a, s)]? [20 points]