[SOLVED] Berkeley AI class - PacMan food heuristic without mazeDistance?

Introduction

Ok, so this is not a complete answer, since I have not implemented it, and so I do not know how it performs. However, I am basing my approach on the following:

The note "Make sure to complete Question 4 before working on Question 7, because Question 7 builds upon your answer for Question 4.". So A* search with Manhattan distance as the consistent heuristic is our basis.
The fact that "If your heuristic is inconsistent, you will receive no credit".

So they are definitely guiding us to A* search with a consistent heuristic that is more clever than Manhattan distance.

Reviewing your (sometimes inconsistent) heuristics

Your first two heuristics: "Manhattan distance to closet food" and "Manhattan distance to furthest food" are definitely consistent.

Your 3rd heuristic "adding to any of those amount of food left" is consistent for the first heuristic but NOT the second (e.g. if walking in a straight line to farthest food eats up all the food, then you will over-estimate the cost).

Your last heuristic ("Manhattan distance to furthest food + Manhattan distance from furthest food to its closet food") is also inconsistent for the same reason: again, picture walking in a straight line to the last pellet results in eating all the remaining food.

So your best consistent heuristic thus far is "Manhattan distance to closet food" + (total number of food pellets) - 1. I'd like to know: how many nodes did you have to expand with this heuristic?

Tighter Heuristic

So when I'm trying to find consistent heuristics, I usually do what you did: start with a basic computation, then add factors that are missing while still staying consistent. So for instance your first heuristic is great for one pellet, but not for multiple. Adding the number of remaining food pellets made it tighter without losing consistency.

Let's find cases where this heuristic does well, and ones where it doesn't. If I imagine a square of pellets (no walls), then this heuristic is pretty good: I get to the closest section of the wall first, and then I gobble up the pellets one at a time (with no wasted moves since I travel in a circle). If it was a single path of pellets instead of a square, then I might under-estimate substantially (e.g. the closest point is mid-path; eating in one direction requires heading back), but I don't see an easy way of modelling this.

Going back to the square, what if I deleted every second pellet? The estimate would be halved, but in reality the cost would be the same! So here is a substantial factor we are missing: the number of connected components.

No matter how you eat, you must always spend a move travelling from one connected component to another (e.g. imagine multiple disconnected paths; we eat one, then travel to next, gobble that one and repeat).

So my first recommended heuristic is the following:

Compute the number of connected components of food pellets = C. (This value can be updated incrementally as you go through the maze. Whenever you eat a pellet you may finish a component, so C' = C - 1, or you can divide a component into multiple components, so C' = C + 1 or C' = C + 2 or C' = C + 3; just do a flood-fill from the 4 neighbors of your current position).
Use the consistent heuristic (C - 1) + (F - 1) + Manhattan distance to closest pellet, where C is the number of components and F is the number of food pellets.

This is clearly tighter than your existing heuristic. The main idea was to capture gaps between pellets.

Even Tighter Heuristic

Now there could be large gaps between connected components (e.g. only keeping every Nth pellet in the square). It is far too complex to know what order we will visit the components but, except for the last component visited, we have to at least travel to our closest neighbor component.

So let's say TravelCost(C_i) is the Manhattan distance from pellet connected component C_i to its closest neighboring connected component (e.g. C_j). Then the TotalTravelCost would be sum(i=1..n)(TravelCost(C_i) - 1) - max(TravelCost(C_i) - 1, i=1..n). Note two things:

To stay consistent, we have to assume the maximum travel cost is the one that is skipped, and
TravelCost(C_i) >= 2 by definition, so TotalTravelCost >= (C-1). (If there's only one connected component left, then TotalTravelCost = C-1 = 0.)

Thus our even-tighter consistent heuristic would be TotalTravelCost + (F - 1) + Manhattan distance to closest pellet.

This is a bit of a pain to implement and definitely makes each node slower to evaluate, so I would personally try implementing my first suggestion and see how it performs before moving on to this. A couple tricks to make this last heuristic faster:

TravelCost(C_i) is not altered when your last move does not eat a pellet.
When you eat a pellet, you only need to update TravelCost(C_i) for the component C_i you altered, and those components whose closest neighbouring component is C_i.
When you split a component into multiple components (i.e. C' = C + 1 or C' = C + 2 or C' = C + 3), then the TravelCost of each of those components must be 2.

Explaining Heuristic Consistency

Based on a comment below, I'm going to elaborate on the consistency of the above heuristics. Remember that consistency means we never over-estimate costs.

Let's say we have a solution which lists the locations we visit in sequence, say L_0, L_1, L_2, ..., L_n where L_0 is our starting position and L_n is our final location (i.e. when we eat the last pellet). Note that at each location we are either eating a pellet or travelling between pellets (i.e. at a location with no pellet) and the final cost of this solution is n.

Now at some point we have to eat the furthest pellet. That is, there exists at least one L_i which specifies the location of the furthest pellet. Well we can conclude that i >= Manhattan distance to furthest pellet, since obviously we cannot get to this location faster from L_0 (since each L_i is adjacent to L_{i-1}). And since n >= i, the total cost must be at least the Manhattan distance to the furthest pellet, so furthest distance is clearly consistent.

Another way to generate a consistent heuristic is by thinking about when we eat the first pellet. The earliest time this can occur is L_i where i >= Manhattan distance to closest pellet. After eating the first pellet, we must still eat the remaining F - 1 remaining food pellets. Since each location has at most one food pellet, this requires at least F - 1 additional steps. So we can conclude that n >= (Manhattan distance to closest pellet) + (F - 1), where F is the number of food pellets. Thus we have another consistent heuristic.

[I will return to explain the more complex heuristics later, but hopefully this helps.]