Studying some variants of the A* algorithm

user_14657113 0
Viewed 318

I recently started learning about the A* algorithm and its variants and came across this paper [1]. It basically has three variants of the algorithm with the heuristic value changed in each one of them.

For the A*(1) it has f(i) = g(i) + h(i), where g(i) denotes the path-cost function from the start point to the current position i, heuristic function h(i) is the Euclidean distance from the current point to the target point.

And for the A*(2) it has f(i) = g(i) + h(i) + h(j), where j the parent node of current point, h(j) is the Euclidean distance from the partent node of current point to target point.

The results show that A*(2) is generally faster than A*(1) when tried on randomly generated mazes. I am not able to explain why is this the case. I tried to compare the two heuristics and was able to conclude the contrary.

My logic says that if we travel from a point that is farther from the target to a nearer point, the f(i) value would be higher than when we travel from a point closer to the target to one that is far because we are considering the Euclidean distance of the parent node. Basically, to reach a specific node the path that is leading away from the target will have a lower f(i).

And since the f(i) value is lower, it would go up on the priority queue. This is against our goal, as a path that is going away from the target is prioritized over the path that is getting closer.

What is wrong with this logic and why does it not align with the results cited in the paper?

[1] - https://www.researchgate.net/publication/238009053_A_comparative_study_of_A-star_algorithms_for_search_and_rescue_in_perfect_maze

a-star maze graph algorithm
1 Answers

In a perfect maze like they use in the paper, A* has little advantage over depth-first search, breadth-first search and Dijkstra. They all perform more or less the same.

The power of A* is that the heuristic can encode a 'sense of direction' into the algorithm. If your target node is north of you, then it makes sense to start searching for a path northwards. But in a perfect maze, this sense of direction is useless. The northward path may be a dead-end and you'd be forced to backtrack. A* is much better suited to wide open grids with sparse obstacles.

Setting it to h(i) + h(j) more-or-less doubles the weight factor of the heuristic. I think that you'll see the same performance improvements if you use something like f(i) = g(i) + h(i) * 1.5 or f(i) = g(i) + h(i) * 2 This will make the algorithm more greedy, more likely to examine nodes closer to the target. The downside is, that you are no longer guaranteed to find the shortest path, you'll find /any/ path. But in a perfect maze, there is only one path to find, so this is not a real problem in this scenario.

I wrote an online widget that allows you to experiment with a few path finding algorithms. Use it to draw a maze, and see the effect of the "greedy" option.

user_33060
Related