2
$\begingroup$

Consider the following question:

n vehicles occupy squares (1, 1) through (n, 1) (i.e., the bottom row) of an n × 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 now 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:

contradiction example

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, ..., h_n) = 4$.

Problem:

As a lemma we now that, consistency of a heuristic function implies the admissibility. We now that all heuristics are both admissible and consistent. So $max(h_1, ..., h_n)$ must be consistent and admissible, but the above example shows that it's not. What is my mistake?

$\endgroup$
1
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ would you please explain more? You mean that my assumptions are wrong? $\endgroup$ – Mostafa Ghadimi Mar 2 at 11:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.