0
$\begingroup$

I was reading a research paper titled 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?

Improve this question
$\endgroup$
4
  • $\begingroup$ 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 ? $\endgroup$
    – user46328
    Commented Apr 17, 2021 at 4:56
  • 1
    $\begingroup$ But then i stumbled upon this article 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 ? $\endgroup$
    – user46328
    Commented Apr 17, 2021 at 5:04
  • $\begingroup$ 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 $\endgroup$
    – user46328
    Commented Apr 17, 2021 at 5:04
  • $\begingroup$ 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. $\endgroup$
    – nbro
    Commented May 11, 2021 at 10:24

0

Reset to default

You must log in to answer this question.