Search code examples
artificial-intelligenceheuristics

Weighting the heuristic function in A*

Three AI newbie question:

  1. Why should a heuristic be admissible for A* to find an optimal path?
  2. What good is a tie braking technique if obstacles are in the way?
  3. What algorithm is good for finding a path on a grid with obstacles? (like pacman)

For the first question Lets take as a base the Manhattan distance heuristic, and call is h(x). Now why should A* find a non-optimal path with a new heuristic that is 8*h(x) + 5? (random numbers). As far as I understand in A* algorithm, the decision will be made according to the function f(x) = g(x) + h(x) so if I scale up h, why should the maximum \ minimum change?

I have read this article, and there they talked about multiplying by a small factor for tie braking, this is somehow for my theory, but they insisted that the factor should be small. So I don't know what to think about it.

For the second question I tried out the techniques in the link for solving a pacman game. Any change of the Manhattan distance heuristic resulted in more nodes expanded. I even "invented" a new weighting scheme where I prefer paths on the outer shell - same thing. Later I tried to take the maximum of all functions (that should also be admissible), but still got bad performance. What am I missing?

Nothing to add for the third question. As mentioned - I can't find anything better than Manhattan distance.

Solution

  • Question 3:

    If you are actually making a Pac Man game, where you have to find the path for each of the 'ghosts', you could also use Dijkstra's Algorithm, using Pac Man's position as the goal and calculating the best path for each ghost in one go. And since the cost for each "edge" (going from one cell to the next) is always the same, you can just as well use simple Breadth First Search. Finally, you might also have a look at Collaborative Diffusion for sending each ghost a different way.