Heuristic function weighting in *

Question

Three questions about the AI ​​rookie:

• Why is heuristic acceptable for determining A * optimal path?
• What good is the braking technique if there are obstacles in the way?
• What algorithm is suitable for finding a path on a grid with obstacles? (e.g. pacman)

For the first question, let's take the Manhattan distance heuristic as the basis, and the call is h (x). Now why does 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 in accordance with the function f(x) = g(x) + h(x) , therefore, if I increase h, why is the maximum / minimum change?

I read this article , and there they talked about reproduction as a small factor to inhibit communication, it was somehow for my theory, but they insisted that this factor should be small. Therefore, I do not know what to think about it.

For the second question, I tried the methods in the link to solve the pacman game. Any change in heuristic distance in Manhattan has led to an increase in the number of nodes. I even “invented” a new weighing scheme, where I prefer the paths on the outer shell - the same thing. Later I tried to take the maximum of all the functions (which should also be acceptable), but still got poor performance. What am I missing?

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

Answer 1

Question 3:

If you are really making a Pac Man game where you need to find a path for each of the “ghosts”, you can also use the Dijkstra Algorithm , using the position of Pac Man as a target and calculating the best path for each ghost at a time. And since the cost of each “edge” (transition from one cell to another) is always the same, you can simply use a simple width search. Finally, you can also take a look at Collaborative Diffusion to send each ghost in a different way.

Answer 2

1) A close answer: if your heuristic is unacceptable, you may get a non-optimal result. I think you knew that. For intuition, recall the definition of acceptable heuristics: it is a heuristic that is never more pessimistic than reality. (We usually say, “It's always optimistic,” since if you had a heuristic that was neither optimistic nor pessimistic, you would basically have your answer.) If your heuristic is pessimistic in some places, it’s in ultimately avoids a better choice.

Regarding scaling and scaling the heuristic according to your question, remember that you only increase the heuristic part of your formula, and not part of the cost of the partial cost of the formula. If you could scale them in exactly the same way, you could not see the difference, but you cannot always do it. Even in your example, the extra bit that you superimposed spoils it.

2-3) I do not understand what you mean by the "decision" of the pacman. If this is something more complicated than finding the shortest path to eat all the points in an empty grid, you seem to go beyond A *. Even then A * would not be my tool of choice.

Answer 3

• If heuristic is unacceptable, then your heuristic will (sometimes) estimates the cost of achieving the goal so that it is higher than the minimum possible cost. Thus, the final path may not be optimal, as it may not have explored a path that turned out to be too costly due to “poor” listening. In your case, using 8*h(x) + 5 monotonically increases all estimated costs, therefore, although the costs for all calculation paths will be larger, they will still be ordered the same way (for example, path A used as length 5 and path B length 3, using your heuristic B (cost 29) will still be less than A (cost 45)).
• As shown in the article , Manhattan distance + the first tie-break mentioned works well for obstacles. Did you leave a maximum path length of 1000 or was this value higher for your Pac-Man implementation?

Answer 4

Usually, if your heuristic function is unacceptable, you can find a "non-optimal" solution in less time (this is a kind of "relaxation problem"). If you do not have strict restrictions on the "optimality" of the solution, you can use an invalid heuristic function. (For example, in an AI game, you want a quick solution not to be optimal).

Now the answer is for Pac-Man AI. There is no A * in the original Pac-Man AI , there is no complicated path planning, no space navigation. In Iann Millington's Artificial Intelligence for Games book, there is a simple Pac-Man AI algorithm that is very simple but very efficient.

• The ghost moves in a straight line until it reaches the connection .
• At the junction, they semi-randomly chose the direction to move on.

Stop. It's all.

For the semi-random, I mean that there are two cases:

• x/10 times when he selects a random direction.
• (10-x)/x times when he chooses a route in the direction of the player (calculated by a simple offset between the player and the ghostly position).

You can choose a different x for each ghost to achieve a different “personality” for each of them.

If you still want to use A * for Pac-Man AI, my advice is to represent only the nodes (the graph in which each node is a connection), and not the whole world with a square grid. The area in the corridor is almost useless .;)