5

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.

2
  • I have as a homework assignment to make AI for pacman, but I have to submit it in a few hours and I'm not sure that I'll get an answer quick enough.. so I have a real interest, but I'll just make a quick test according to answers and leave it. Sep 3, 2012 at 11:22
  • A* is two overlapping heuristics. Djikstra's favours nodes near the origin, and Best First favours those near the goal. A* acts like Djikstra (expand in all directions) until it encounters obstacles, then it begins to expand in straight lines to the goal. If you multiply the cost of distance from the goal, A* begins to focus on fast solutions. In 2 secs, my A* traveled 2500 nodes, by weighting it to favour the goal, (1.1x), it did 1750000 nodes. About a 700x increase in speed (at the expense of accuracy).
    – Aarowaim
    Mar 20, 2014 at 8:14

4 Answers 4

1

1) The terse answer is, if your heuristic is not admissible, you will (possibly) get a non-optimal result. I think you knew this. For the intuition, recall the definition of an admissible heuristic: It is a heuristic which is never more pessimistic than reality. (We usually say, "it is always optimistic," since if you had a heuristic that was neither optimistic nor pessimistic, you'd basically have your answer already.) If your heuristic is pessimistic in some places, then it ends up avoiding the best choices.

As for scaling up and scaling down the heuristics as per your question, remember, you are only scaling up the heuristic part of your formula, not the sunk cost part of the formula. If you could scale them up exactly the same, you couldn't see the difference, but you can't always do that. Even in your example, the additive bit you tacked on spoils it.

2-3) It's not clear to me what you mean by "solving" pacman. If it's anything more complex than finding a shortest path to eat all the dots in an empty grid, you're getting well beyond the scope of A*, I think. Even then, A* would not be my tool of choice.

0

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.

0
0
  1. If the heuristic is not admissible then your heuristic will (sometimes) estimate the cost to reach the goal to be higher then the lowest possible cost. The final path could thus be non-optimal as it might have not explored path which appeared to be too costly due the 'bad' hearistic. In your case using 8*h(x) + 5 monotonically increases all estimated costs, so while the costs of all the estimated paths will all be larger, they will still be ordered in the same way (e.g., path A used to be length 5 and path B length 3, using your heuristic B (cost 29) will still be estimated to be shorter then A (cost 45)).
  2. As shown in the article, Manhattan distance + the first mentioned tie breaker works well for obstacles. Did you leave the estimated maximum path length at 1000 or should this value be higher for your implementation of Pac-Man?
4
  • I have calculated the p while 1 is a step cost, and (height*width - width/3*(height-1)) is the expected maximum path. Actually the max path, is less but I though that is good enough. Something wrong with that? Sep 3, 2012 at 11:39
  • Is that the only p you've tried? Otherwise I would experiment a bit more with p, by calculating it as you describe and then try even smaller values (e.g. multiply it with 0.1, 0.01, 0.001).
    – Sicco
    Sep 3, 2012 at 11:44
  • In addition, if we talk about pacman specifically, then the whole terrain is full with obstacles, and no 'open area' is at the end. So the pacman maze actually makes these heuristics worthless - because they are good for open terrain with some "heavy" and some "light" cells. Not for going around obstacles. Sep 3, 2012 at 11:47
  • I just tried out this: problem.goal = foodNode ; w = problem.walls.width ; h = problem.walls.height ; p.append( min( min(w-foodNode [0], foodNode [0])/w, min(h-foodNode [1], foodNode [1])/h) ) ; p.append( 1/(h*w - w/3*(h-1)) * 0.001 ) ; distance = manhattanHeuristic(position, problem) * (1+ max(p)) ; And I got the same result like using just manhattanHeuristic - I put ; between the lines hope this will make some sense - Its python Sep 3, 2012 at 11:50
0

Usually, if your heuristic function is not admissible you can find a "non-optimal" solution in less time (is a kind of "problem relaxation"). If you don't have strict constraints on the solution "optimality" you can use not admissible heuristic function. (For example, in game AI you want a quick solution not the optimal one).

Now an answer for the Pac-Man AI. In the original Pac-Man AI there are no A*, no complex path-planning, no grid-space navigation. There is a simple Pac-Man AI algorithm in the book Artificial Intelligence for Games by Iann Millington that is very very simple but very effective.

  1. A ghost moves in a straight line until it reaches a junction.
  2. At a junction they semi-randomly chose a direction to move next.

Stop. That's all.

For semi-randomly I mean that there are two cases:

  1. x/10 times it choose a random direction.
  2. (10-x)/x times it choose the route in the direction of the player (calculated by a simple offset between player and ghost position).

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

If you still want to use A* to Pac-Man AI my advice is to represent only the junctions (a graph in which every node is a junction) and not all the square-grid world. The square in a corridor is essentially useless. ;)

2
  • That is not the algorithm that the ghosts in Pac-Man use. Each one has a different algorithm. The Pac-Man dossier goes into detail on how the ghosts navigate the maze: home.comcast.net/~jpittman2/pacman/pacmandossier.html
    – Matt Greer
    Sep 3, 2012 at 19:39
  • Oh. I used as reference the book Artificial Intelligence for Games by Iann Millington, I thought that it refer to the original algorithm. However... :) Thank you for the info. I fix my answer. :) Sep 4, 2012 at 8:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.