Body: <p>I was reading a research paper titled <a href="https://www.researchgate.net/publication/238009053_A_comparative_study_of_A-star_algorithms_for_search_and_rescue_in_perfect_maze" rel="nofollow noreferrer">A Comparative Study of A-star Algorithms for Search and rescue in Perfect Maze</a> (2011).</p>
  <p>I have some doubts regarding it:</p>
  <p>1.</p>
  <blockquote>
  <p>The Evaluation Function of <span class="math-container">$\mathrm{A}^{*}(2)[5]$</span> is:
  <span class="math-container">$$
  f_{2}(i)=g_{2}(i)+h_{2}(i)+h_{2}(j)
  $$</span>
  Where, <span class="math-container">$j$</span> is the father point of the current point, <span class="math-container">$h_{2}(j)$</span> is the Euclidean distance from the father point of the current point to the target point. This term is added to the father point for improving the search speed because it reduces the number of nodes.</p>
  </blockquote>
  <p>In this section (page 2 middle-right) it says that the father point is added to improve search speed as it reduces the number of nodes searched.
  Is this because the added father point in some way overestimates the cost function, similar to Greedy Best First Search. Can it be interpreted as something between <span class="math-container">$A^{*}$</span> and Greedy BFS? If not what is the reason for the increase in speed?</p>
  <p>2.</p>
  <blockquote>
  <p><span class="math-container">$\mathrm{A}^{*}(3)$</span> that employed a heuristic function with angle and distance has not been demonstrated well in this experiment, the reason is: in this experiment, we have added deviations not only on distance but also on an angle, so the <span class="math-container">$A^{*}(3)$</span> algorithm has no advantage in this searching.</p>
  </blockquote>
  <p>In this section (page 3 upper-right) it is saying that <span class="math-container">$\mathrm{A}^{*}(3)$</span> is not so useful as there are deviations in angle also. What does this statement mean how are deviations in angle added? Request help in understanding <span class="math-container">$\mathrm{A}^{*}(3)$</span>?</p>
  <p><strong>I need to understand why one heuristic is better than another. Is there some way to determine that apart from experimental evidence?</strong></p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-04-17T04:56:41.153Z
Comments.Text: At first while reading the paper i thought that a-star must have taken into account the distance of the goal from the father node while searching for it in the first place as only then it would be exploring it so how will it matter if it takes into account the distance of the father node from the goal again ?
Comments.UserDisplayName: user46328
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-04-17T05:04:19.143Z
Comments.Text: But then i stumbled upon this article http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html .  It says "If h(n) is sometimes greater than the cost of moving from n to the goal, then A* is not guaranteed to find a shortest path, but it can run faster." So by overcompensate I mean that is the heuristic cost greater than the actual cost of moving from the node to the goal so it  searches lesser nodes ?
Comments.UserDisplayName: user46328
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-04-17T05:04:35.940Z
Comments.Text: Is it in some way mirroring what Greedy BFS does, like is it giving more importance to the heuristic (here h(i) + h(j) ) by increasing its value ( as h(i) + h(j) > h(i) ) ? I am trying to compare A*(1) with A*(2) here
Comments.UserDisplayName: user46328
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-05-11T10:24:41.020Z
Comments.Text: Hello. I kindly ask you to edit your post to focus on 1 question at a time. If you have multiple questions (even though they are related to the same paper), I suggest that you create one post for each of them, so that people can focus on specific problems, one at a time. It seems to me that here you're asking 3 questions. 2 specific questions about the paper's content and a more general question about how to compare heuristics.
Comments.UserDisplayName: nbro
Tags: <comparison><papers><a-star><path-finding><heuristic-functions>
Title: Comparing heuristics in A* search and rescue operation
UserDisplayName: user46328
ThreadText: # Comparing heuristics in A* search and rescue operation
  
  (Asked by: username_0 on 2021-04-16)
  
  I was reading a research paper titled [A Comparative Study of A-star Algorithms for Search and rescue in Perfect Maze](https://www.researchgate.net/publication/238009053_A_comparative_study_of_A-star_algorithms_for_search_and_rescue_in_perfect_maze) (2011).
  
  I have some doubts regarding it:
  
  1.
  
  > The Evaluation Function of $\mathrm{A}^{\*}(2)[5]$ is:
  > $$
  > f\_{2}(i)=g\_{2}(i)+h\_{2}(i)+h\_{2}(j)
  > $$
  > Where, $j$ is the father point of the current point, $h\_{2}(j)$ is the Euclidean distance from the father point of the current point to the target point. This term is added to the father point for improving the search speed because it reduces the number of nodes.
  
  In this section (page 2 middle-right) it says that the father point is added to improve search speed as it reduces the number of nodes searched.
  Is this because the added father point in some way overestimates the cost function, similar to Greedy Best First Search. Can it be interpreted as something between $A^{\*}$ and Greedy BFS? If not what is the reason for the increase in speed?
  
  2.
  
  > $\mathrm{A}^{\*}(3)$ that employed a heuristic function with angle and distance has not been demonstrated well in this experiment, the reason is: in this experiment, we have added deviations not only on distance but also on an angle, so the $A^{\*}(3)$ algorithm has no advantage in this searching.
  
  In this section (page 3 upper-right) it is saying that $\mathrm{A}^{\*}(3)$ is not so useful as there are deviations in angle also. What does this statement mean how are deviations in angle added? Request help in understanding $\mathrm{A}^{\*}(3)$?
  
  **I need to understand why one heuristic is better than another. Is there some way to determine that apart from experimental evidence?**
  
  **Tags:** comparison, papers, a-star, path-finding, heuristic-functions
  > **Comments:**
  > **username_0**: At first while reading the paper i thought that a-star must have taken into account the distance of the goal from the father node while searching for it in the first place as only then it would be exploring it so how will it matter if it takes into account the distance of the father node from the goal again ?  
  > **username_0**: But then i stumbled upon this article http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html .  It says "If h(n) is sometimes greater than the cost of moving from n to the goal, then A* is not guaranteed to find a shortest path, but it can run faster." So by overcompensate I mean that is the heuristic cost greater than the actual cost of moving from the node to the goal so it  searches lesser nodes ?  
  > **username_0**: Is it in some way mirroring what Greedy BFS does, like is it giving more importance to the heuristic (here h(i) + h(j) ) by increasing its value ( as h(i) + h(j) > h(i) ) ? I am trying to compare A*(1) with A*(2) here  
  > **username_1**: Hello. I kindly ask you to edit your post to focus on 1 question at a time. If you have multiple questions (even though they are related to the same paper), I suggest that you create one post for each of them, so that people can focus on specific problems, one at a time. It seems to me that here you're asking 3 questions. 2 specific questions about the paper's content and a more general question about how to compare heuristics.  
  
  ---
  
  ## 0 answers
  
  