If $h_i$ are consistent and admissible, are their sum, maximum, minimum and average also consistent and admissible?

Question

Consider the following question:

$n$ vehicles occupy squares $(1, 1)$ through $(n, 1)$ (i.e., the bottom row) of an $n \times n$ grid. The vehicles must be moved to the top row but in reverse order; so the vehicle $i$ that starts in $(i, 1)$ must end up in $(n − i + 1, n)$. On each time step, every one of the $n$ vehicles can move one square up, down, left, or right, or stay put; but if a vehicle stays put, one other adjacent vehicle (but not more than one) can hop over it. Two vehicles cannot occupy the same square.

Suppose that each heuristic function $h_i$ is both admissible and consistent. Now what I want to know is to check the admissibility and consistency of the following heuristics:

1. $h= \Sigma_i h_i$

2. $h= \min_i (h_i)$

3. $h= \max_i (h_i)$

4. $h = \frac{\Sigma_i h_i}{n}$

P.S: As a lemma, we know that consistency implies the admissibility of the heuristic function.

Problem Explanation

From this link, I have found that the first heuristic is neither admissible, nor consistent.

I know that the second and the fourth heuristics are either consistent, or admissible.

I have faced with one contradiction in the third heuristic:

Here we see that if car 3 hops twice, the total cost of moving all the cars to their destinations is 3, whereas the heuristic $\max(h_1, \dots, h_n) = 4$.

Problem

So, $\max(h_1, ..., h_n)$ must be consistent and admissible, but the above example shows that it's not. What is my mistake?

Answer 1

The issue is that you must include assumptions about hopping into your heuristic. In particular, if you are considering individual cars then you must assume that they might be able to hop all of the way to the goal. Thus, your heuristic for each car should be Manhattan distance divided by 2. That's guaranteed to be admissible when you take the max.

If you consider all possible cars you can do better, but you'll need to reason out all the cases. (In general every car either waits or moves, and for every waiting car one car can hop. So, by looking at the minimum distance for any car to reach the goal you can start to reduce your heuristic.) But, that is a different question.