Answers.Body: <p>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.</p>
  
  <p>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.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-03-02T11:20:43.397Z
Answers.Text: would you please explain more? You mean that my assumptions are wrong?
Answers.UserDisplayName: Mostafa Ghadimi
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-03-02T07:44:11.747Z
Answers.LastActivityDate: 2020-03-02T07:44:11.747Z
Answers.UserDisplayName: Nathan S.
Body: <p>Consider the following question:</p>
  <blockquote>
  <p><span class="math-container">$n$</span> vehicles occupy squares <span class="math-container">$(1, 1)$</span> through <span class="math-container">$(n, 1)$</span> (i.e., the bottom row) of an <span class="math-container">$n \times n$</span> grid. The vehicles must be moved to the top row but in reverse order; so the vehicle <span class="math-container">$i$</span> that starts in <span class="math-container">$(i, 1)$</span> must end up in <span class="math-container">$(n − i + 1, n)$</span>. On each time step, every one of the <span class="math-container">$n$</span> 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.</p>
  </blockquote>
  <p>Suppose that each heuristic function <em><span class="math-container">$h_i$</span></em> is both admissible and consistent. Now what I want to know is to check the admissibility and consistency of the following heuristics:</p>
  <ol>
  <li><p><span class="math-container">$h= \Sigma_i h_i$</span></p>
  </li>
  <li><p><span class="math-container">$h= \min_i (h_i)$</span></p>
  </li>
  <li><p><span class="math-container">$h= \max_i (h_i)$</span></p>
  </li>
  <li><p><span class="math-container">$h = \frac{\Sigma_i h_i}{n}$</span></p>
  </li>
  </ol>
  <p><strong>P.S:</strong> As a lemma, we know that consistency implies the admissibility of the heuristic function.</p>
  <p><strong>Problem Explanation</strong></p>
  <p>From <a href="https://ai.stackexchange.com/q/18310/2444">this link</a>, I have found that the first heuristic is neither admissible, nor consistent.</p>
  <p>I know that the second and the fourth heuristics are either consistent, or admissible.</p>
  <p>I have faced with one contradiction in the third heuristic:</p>
  <p><a href="https://i.sstatic.net/uPzPU.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/uPzPU.png" alt="contradiction example" /></a></p>
  <p>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 <span class="math-container">$\max(h_1, \dots, h_n) = 4$</span>.</p>
  <p><strong>Problem</strong></p>
  <p>So, <span class="math-container">$\max(h_1, ..., h_n)$</span> must be consistent and admissible, but the above example shows that it's not. What is my mistake?</p>
  
Tags: <admissible-heuristic><consistent-heuristic><heuristic-functions>
Title: If $h_i$ are consistent and admissible, are their sum, maximum, minimum and average also consistent and admissible?
UserDisplayName: Mostafa Ghadimi
ThreadText: # If $h_i$ are consistent and admissible, are their sum, maximum, minimum and average also consistent and admissible?
  
  (Asked by: username_0 on 2020-03-02)
  
  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](https://ai.stackexchange.com/q/18310/2444), 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](https://i.sstatic.net/uPzPU.png)](https://i.sstatic.net/uPzPU.png)
  
  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?
  
  **Tags:** admissible-heuristic, consistent-heuristic, heuristic-functions
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2020-03-02. Score: 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.
  
  > **Comments:**
  > **username_0**: would you please explain more? You mean that my assumptions are wrong?  
  
  ---
  
  