How can I define a heuristic function for water jug?

Question

I am trying to put a water jug problem into a heuristic function but I am finding some problems.

There are 2 jugs, one that can hold 5(x) and other that can hold 3(y) gallons of water. The goal is (y,x)=(0,4).

I can't figure out how to put it into a heuristic function and also I have a doubt about the number of states. If I admit the actions (fill one from the faucet, empty one to the drain, and pour from one to the other until either the receiving jug is full or the pouring jug is empty), there are 15 possible states, but if I consider all the possibilities regarding the number of gallons, there are 24 possibilities. Is that correct?

(0,0)

(3,0)(0,5)

(0,3)(3,5)(3,2)

(3,3) (0,2)

(1,5) (2,0)

(1,0) (2,5)

(0,1) (3,4)

(0,4)

I think that the Heuristic function for this problem can be defined as:

h(x,y) = (x * 5) + (y * 3)

but I also found this answer for a question (Heuristic function for Water Jug) and now I am confused. Can anyone explain it to me please?

max(estimate_from_parent - action_cost, estimate_from_this_node)

Answer 1

Number of states and reachability:

You are correct about the theoretical number of states (assuming buckets can only have an integer number of gallons - otherwise it's infinite). Because there are 6 possible numbers of gallons that bucket X can contain and for 4 that bucket Y can contain, the total number of states is 6*4=24.

Technically, (3,1) is also reachable, after you find the solution, so there are 16 possible states.

Heuristic Function:

In terms of the heuristic function, you might want to take a second and think about your goal. You want to have four gallons in bucket x. So the closer you are to having four gallons in bucket x, the closer you are to your goal, and the lower the value of your heuristic function should be (since it's an estimated cost). The lowest value of your heuristic function, then, should occur when there are four gallons in bucket x. The heuristic function you proposed here, h(x,y) = (x * 5) + (y * 3), is lowest at (0,0). Since this is not your goal node, this isn't likely to be a good heuristic function.

In thinking of a heuristic function, it's often useful to find a constraint that makes your problem harder and then relax it. This facilitates coming up with a heuristic that is admissible and consistent, because your heuristic will basically be a best case estimate. For this problem, a pretty big constraint is that there are only certain amounts of water that you can add to bucket x (i.e. the amount in bucket y, or the amount that it would take to fill bucket x). We could relax this constraint, and basically end up with h(x,y) = |X-4| (the heuristic function discussed in the linked post, adapted to your problem). This is definitely admissible and consistent, as it is effectively the amount that it would cost to get to the goal from that node in one step if taking such a step were possible. If you are at the goal node, it will be equal to 0. Note that the way your costs are calculated is critical to making this a useful heuristic.

Does that clear up your confusion?