Monkey and Banana Problem

One of the standard AI toy search problems is the monkey and bananas problem. The variation of this problem that we will use is: A monkey is in a room containing a bunch of bananas and a wooden box. The bananas are hanging from the ceiling out of the monkey's reach, but he can reach them if he stands on the box. Unfortunately (for the monkey) the monkey, box, and bananas are all in different places in the room. What does the monkey have to do to get the bananas?

1. Formalize this problem using a state space representation, designed for a forward search (initial to goal states).

A state space representation formalizes a problem in terms of the following elements:

1. a description of how states will be represented and what legal states are; 2. a description of the initial state(s);
2. a description of the goal state(s); and
3. a description of the legal operators, showing what states they can be applied in and what the resulting state is.
4. A description of the sensors that the monkey has. Describe the relationship between checking the sensors and making a move. (Hint: Think about the state space representation for the vacuum world problem.)
5. Discuss the issues that arose in formalizing the problem:

a. What assumptions did you make about the problem that were not explicit in the problem

description?

b. What abstractions did you make in defining the states?

c. What abstractions did you make in defining the operators? (What knowledge about the

domain did you use to create the operators?)

3. Use your state space representation to solve the problem and list one solution (show the sequence of states and operators.)
4. Draw the search tree that gets generated by a BFS of the state space of your representation. Show the tree either to the depth where the minimal depth solution occurs, or a depth of 5, whichever is shallower (i.e., don't explore partial solutions involving sequences of more than 5 operators.) Also, label the nodes to show the order in which they are expanded, not the order generated.
5. Discuss the use of DFS rather than BFS for this problem, given the characteristics of the state space. Is one necessarily better? Why or why not? Consider the differences between these search strategies both when using your representation and for the problem in general (i.e., consider other possible representations.)

Sample Solution