1. R&N 2.9

a) [2 points]

No, a simple reflex agent will not be completely rational for this environment. Let us assume that the only percepts being received by the agent are the current square that it is in, and whether or not the square is dirty. In this case, the agent can only decide whether or not to clean the square and decide which adjacent square to move.  Without knowledge of which squares contain dirt, the agent would either make cyclic moves, thereby being penalized more, or choose not to move at all avoiding any penalty but leaving the floor dirty.

I was looking for a complete answer with a discussion of at least two ways the agent might react to the given stimulus which cause it to not be rational.

(b) [2 points]

Explain how a sense of state could help the agent know when the entire floor must be clean.  A small discussion of something extra (the floor getting dirty again or how the agent might optimize its path) was required for full points.

if (dirt) {Suck}
else if (already_moved) {NoOp}
else if (in_location_A) {already_moved = true; Right}
else {already_moved = true; Left}

(c) [2 points to new answer to (a); 2 points to new answer to (b)]

Given knowledge of the entire environment, a simple reflex agent can be perfectly rational; state gives no advantage. If the current square is dirty, clean it. Otherwise, if the other square is dirty, go to the other square. In this case, since it can observe the state of the environment directly, it doesn't need to record it internally. This will perform better than the reflex agent with the state if the other square started out clean.

2. R&N 12a [3 points]

Description of reasonable modifications to the agent program (such as repeated sensor reading) and some kind of analytical justification (based on probability) was required.

3. R&N 3.9a [2 points]

I checked for a complete state diagram with labels on the transitions.  Representation of the people and the boat was required to correctly map out the problem.  No point taken off for small errors.

4. R&N 3.9c [1 point]

Anything reasonable is fine.

Here are two of my favories: The difficulty is in the fact that this problem is not so rigorously formulated, and the lack of formalism does not enable one to visualize the fact that there really are very few actual configurations of the missionaries and cannibals that are valid, and searching for a sequence of operations from among them is very easy.  

What makes this problem challenging for people is probably the lack of a good heuristic, the depth of the solution, and the complexity of the operators, all of which make it very easy to backtrack unwittingly. If you list all the states you've been in to avoid backtracking, the problem is fairly simple; however, most people don't do that when solving puzzles.

5. Integration [3 points]

A good discussion of operations and how they might be applied was required.  Just saying apply integration by parts was not enough, you need to explain how it would be applied, how you know when it can be applied, etc.  Also detecting the goal state needed to be explained.  Checking that this state is the derivative of the start state was not enough unless the inefficiency of this solution was discussed. 

6. TSP as a MST problem

a [3 points]

Again, I was looking for a full description of the representation of the problem.  Many of you mentioned nodes and edges without describing what they represented.  Strong representation of this problem made the solution to part (b) more convincing. 

b [2 points]

To create a relaxed version of TSP, many people simply remove the constraint, "visiting each city exactly once", alone. That is not enough to justify the spanning tree to be a minimum path of the salesman. People who answere correctly to this question often use words like "teleport" or "return without cost" etc. to permit the salesman to go back to a previously visited city without a cost.

HereÕs a nice solution:

The TSP requires that the salesman travel from the last city visited to the next. If this assumption is relaxed so that the salesman is permitted to teleport to a previously visited city, then the salesman's travels will be a spanning tree. Since a spanning path is a special case of a spanning tree, the sum of the edge weights in the minimum spanning tree will never exceed those in a minimum spanning path. Therefore, this is an admissible heuristic, since it underestimates.