Three AI newbie question:
Why should a heuristic be admissible for A* to find an optimal path?
What good is a tie braking technique if obstacles are in the way?
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.