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

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?