Weighting the heuristic function in A*

Question

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, let's take as a base the Manhattan distance heuristic, and the 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 the 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 - the 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 to the third question. As mentioned - I can't find anything better than Manhattan distance.

Answer 1

If your heuristic is not admissible, you will deceive a non-optimal result. If your heuristic is pessimistic in some places, then it avoids the best choices.

Now talking about scaling up and scaling down the heuristics as per your question, you are only scaling up the heuristic part of your formula, not the sunk cost part of the formula. 

If you are 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 aim and calculate the best path for each ghost in one go. And as you know 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. You can take a look at Collaborative Diffusion for sending each ghost a different way, by referring the following link: https://www.cs.colorado.edu/~ralex/papers/PDF/OOPSLA06antiobjects.pdf

If you wish to learn more about Artificial Intelligence then you can join the Artificial Intelligence Course.