PacMan: what kinds of heuristics are mainly used?

You comment says you are looking for shortest path. This problem is a variation of TSP on a planar graph, and thus is NP-Hard.

Possible heuristics function for A* that can solve the problem but is not admissible [thus the path found is not guaranteed to be optimal]:

Sum of manhattan distances from all fruits to the agent.

You can also use an edmissible heuristic, of #fruits – but it will take a long time.

If you are looking for optimal, well – it is hard. You can try all permutations of fruits, and check the total distance you need to travel. This solution is factorial in the number of fruits, and if it is greater then 20 – with naive bruteforce – it will take too long. You can somehow make it better by reducing the problem to TSP, and use dynamic-programming solution, which is also exponential, or some heuristical solutions to TSP.


One can also improve the non-admissible heuristic solution to provide an any-time algorithm:

iteratively run A* with a decreasing heuristic functionh(v) = h'(v) / m, where h' is the heuristic function on last iteration of A*, and m > 1. This guarantees that at some point, your heuristic function h will be admissible – and the solution found will be optimal. However, each iteration is expected to take much longer then the previous one [exponentially longer..]

Leave a Comment