1

HEURISTIC FUNCTIONS

INTRODUCTION
A Heuristic technique helps in solving problems, even though there is no guarantee that it will never lead in the wrong direction. There are heuristics of every general applicability as well as domain specific. The strategies are general purpose heuristics. In order to use them in a specific domain they are coupler with some domain specific heuristics. There are two major ways in which domain - specific, heuristic information can be incorporated into rule-based search procedure. A heuristic function is a function that maps from problem state description to measures desirability, usually represented as number weights. The value of a heuristic function at a given node in the search process gives a good estimate of that node being on the desired path to solution. Well designed heuristic functions can provides a fairly good estimate of whether a path is good or not. ( " The sum of the distances traveled so far" is a simple heuristic function in the traveling salesman problem) . the purpose of a heuristic function is to guide the search process in the most profitable directions, by suggesting which path to follow first when more than one path is available. However in many problems, the cost of computing the value of a heuristic function would be more than the effort saved in the search process. Hence generally there is a trade-off between the cost of evaluating a heuristic function and the savings in search that the function provides.

CSE DEPARTMENT | IMMANUEL ARASAR JJ COLLEGE OF ENGINEERING

HEURISTIC FUNCTIONS

CONTENTS

1 Shortest paths

1.1 Effect of heuristics on computational performance.

1.2 Finding heuristics.

1.3 Consistency and Admissibility.

CSE DEPARTMENT | IMMANUEL ARASAR JJ COLLEGE OF ENGINEERING

HEURISTIC FUNCTIONS

Shortest paths

For example, for shortest path problems, a heuristic is a function, h(n) defined on the nodes of a search tree, which serves as an estimate of the cost of the cheapest path from that node to the goal node. Heuristics are used by informed search algorithms such as Greedy best-first search and A* to choose the best node to explore. Greedy best-first search will choose the node that has the lowest value for the heuristic function. A* search will expand nodes that have the lowest value for g(n) + h(n), where g(n) is the (exact) cost of the path from the initial state to the current node. If h(n) is admissiblethat is, if h(n) never overestimates the costs of reaching the goal, then A* will always find an optimal solution. The classical problem involving heuristics is the n-puzzle. Commonly used heuristics for this problem include counting the number of misplaced tiles and finding the sum of the Manhattan distances between each block and its position in the goal configuration. Note that both are admissible.

CSE DEPARTMENT | IMMANUEL ARASAR JJ COLLEGE OF ENGINEERING

HEURISTIC FUNCTIONS

Effect of heuristics computational performance

on

In any searching problem where there are b choices at each node and a depth of d at the goal node, a naive searching algorithm would have to potentially search around bd nodes before finding a solution. Heuristics improve the efficiency of search algorithms by reducing the branching factor from b to a lower constant b', using a cutoff mechanism. The branching factor can be used for defining a partial order on the heuristics, such that h1(n) <h2(n) if h1(n) has a lower branch factor than h2(n) for a given node n of the search tree. Heuristics giving lower branching factors at every node in the search tree are preferred for the resolution of a particular problem, as they are more computationally efficient.

Finding heuristics

The problem of finding an admissible heuristic with a low branching factor for common search tasks has been extensively researched in the artificial intelligence community. Several common techniques are used:

Solution costs of sub-problems often serve as useful estimates of the overall solution cost. These are always admissible. For example, a heuristic for a 10-puzzle might be the cost of moving tiles 1-5 into their correct places. A common idea is to use a pattern database that stores the exact solution cost of every subproblem instance.

CSE DEPARTMENT | IMMANUEL ARASAR JJ COLLEGE OF ENGINEERING

HEURISTIC FUNCTIONS

The solution of a relaxed problem often serves as a useful admissible estimate of the original. For example, manhattan distance is a relaxed version of the n-puzzle problem, because we assume we can move each tile to its position independently of moving the other tiles. Given a set of admissible heuristic functions h1(n),h2(n),...,hi(n), the function h(n) = max{h1(n),h2(n),...,hi(n)} is an admissible heuristic that dominates all of them.

Using these techniques a program called ABSOLVER was written (1993) by A.E. Prieditis for automatically generating heuristics for a given problem. ABSOLVER generated a new heuristic for the 8-puzzle better than any pre-existing heuristic and found the first useful heuristic for solving the Rubik's Cube.

Consistency and Admissibility

If a Heuristic function never over-estimates the cost reaching to goal, then it is called an Admissible heuristic function. If H(n) is consistent then the value of H(n) for each node along a path to goal node are non decreasing.

CSE DEPARTMENT | IMMANUEL ARASAR JJ COLLEGE OF ENGINEERING

HEURISTIC FUNCTIONS

Example:

One might be interested in finding a heuristic to estimate the number of steps required to solve an 8-puzzle from a given state. Two simple heuristic functions are: h1 = the number of misplaced tiles. This is also known as the Hamming Distance. In the pictured example, the start state has h1 = 8. Clearly, h1 is an admissible heuristic because any tile that is out of place will have to be moved at least once. h2 = the sum of the distances of the tiles from their goal positions. Because tiles cannot be moved diagonally, the distance counted is the sum of horizontal and vertical distances. This is also known as the Manhattan Distance. In the pictured example, the start state has h2 = 3 + 1 + 2 + 2 + 2 + 3 + 3 + 2 = 18. Clearly, h2 is also an admissible heuristic because any move can, at best, move one tile one step closer to the goal.

CSE DEPARTMENT | IMMANUEL ARASAR JJ COLLEGE OF ENGINEERING

HEURISTIC FUNCTIONS

As expected, neither heuristic overestimates the true number of moves required to solve the puzzle, which is 26. Additionally, it is easy to see from the definitions of the heuristic functions that for any given state, h2 will always be greater than or equal to h1. Thus, we can say that h2 dominates h1. The heuristic function h(n) tells A* an estimate of the minimum cost from any vertex n to the goal. Its important to choose a good heuristic function.

A*s Use of the Heuristic:

At one extreme, if h(n) is 0, then only g(n) plays a role, and A* turns into Dijkstras algorithm, which is guaranteed to find a shortest path. If h(n) is always lower than (or equal to) the cost of moving from n to the goal, then A* is guaranteed to find a shortest path. The lower h(n) is, the more node A* expands, making it slower. If h(n) is exactly equal to the cost of moving from n to the goal, then A* will only follow the best path and never expand anything else, making it very fast. Although you cant make this happen in all cases, you can make it exact in some special cases. Its nice to know that given perfect information, A* will behave perfectly. If h(n) is sometimes greater than the cost of moving from n to the goal, then A* is not guaranteed to find a shortest path, but it can run faster.
CSE DEPARTMENT | IMMANUEL ARASAR JJ COLLEGE OF ENGINEERING

HEURISTIC FUNCTIONS

At the other extreme, if h(n) is very high relative to g(n), then only h(n) plays a role, and A* turns into BestFirst-Search.

Note:
Technically, the A* algorithm should be called simply A if the heuristic is an underestimate of the actual cost. However, I will continue to call it A* because the implementation is the same and the game programming community does not distinguish A from A*. So we have an interesting situation in that we can decide what we want to get out of A*. At exactly the right point, well get shortest paths really quickly. If were too low, then well continue to get shortest paths, but itll slow down. If were too high, then we give up shortest paths, but A* will run faster. In a game, this property of A* can be very useful. For example, you may find that in some situations, you would rather have a good path than a perfect path. To shift the balance between g(n) and h(n), you can modify either one.

Speed or accuracy?

A*s ability to vary its behavior based on the heuristic and cost functions can be very useful in a game. The tradeoff between speed and accuracy can be exploited to make your game faster. For most games, you dont really need the best path between two points. You just need something thats close. What you need

CSE DEPARTMENT | IMMANUEL ARASAR JJ COLLEGE OF ENGINEERING

HEURISTIC FUNCTIONS

may depend on whats going on in the game, or how fast the computer is. Suppose your game has two types of terrain, Flat and Mountain, and the movement costs are 1 for flat land and 3 for mountains, A* is going to search three times as far along flat land as it does along mountainous land. This is because its possible that there is a path along flat terrain that goes around the mountains. You can speed up A*s search by using 1.5 as the heuristic distance between two map spaces. A* will then compare 3 to 1.5, and it wont look as bad as comparing 3 to 1. It is not as dissatisfied with mountainous terrain, so it wont spend as much time trying to find a way around it. Alternatively, you can speed up up A*s search by decreasing the amount it searches for paths around mountainsjust tell A* that the movement cost on mountains is 2 instead of 3. Now it will search only twice as far along the flat terrain as along mountainous terrain. Either approach gives up ideal paths to get something quicker. The choice between speed and accuracy does not have to be static. You can choose dynamically based on the CPU speed, the fraction of time going into pathfinding, the number of units on the map, the importance of the unit, the size of the group, the difficulty level, or any other factor. One way to make the tradeoff dynamic is to build a heuristic function that assumes the minimum cost to travel one grid space is 1 and then build a cost function that scales: g'(n) = 1 + alpha * (g(n) - 1)
9

CSE DEPARTMENT | IMMANUEL ARASAR JJ COLLEGE OF ENGINEERING

10

HEURISTIC FUNCTIONS

If alpha is 0, then the modified cost function will always be 1. At this setting, terrain costs are completely ignored, and A* works at the level of simple passable/unpassable grid spaces. If alpha is 1, then the original cost function will be used, and you get the full benefit of A*. You can set alpha anywhere in between. You should also consider switching from the heuristic returning the absolute minimum cost to returning the expected minimum cost. For example, if most of your map is grasslands with a movement cost of 2 but some spaces on the map are roads with a movement cost of 1, then you might consider having the heuristic assume no roads, and return 2 * distance. The choice between speed and accuracy does not have to be global. You can choose some things dynamically based on the importance of having accuracy in some region of the map. For example, it may be more important to choose a good path near the current location, on the assumption that we might end up recalculating the path or changing direction at some point, so why bother being accurate about the faraway part of the path? Or perhaps its not so important to have the shortest path in a safe area of the map, but when sneaking past an enemy village, safety and quickness are essential.

Scale
10

A* computes f(n) = g(n) + h(n). To add two values, those two values need to be at the same scale. If g(n) is measured in hours and h(n) is measured in meters, then A* is

CSE DEPARTMENT | IMMANUEL ARASAR JJ COLLEGE OF ENGINEERING

11

HEURISTIC FUNCTIONS

going to consider g or h too much or too little, and you either wont get as good paths or you A* will run slower than it could.

Exact heuristics

If your heuristic is exactly equal to the distance along the optimal path, youll see A* expand very few nodes, as in the diagram shown in the next section. Whats happening inside A* is that it is computing f(n) = g(n) + h(n) at every node. When h(n) exactly matches g(n), the value of f(n) doesnt change along the path. All nodes not on the right path will have a higher value of f than nodes that are on the right path. Since A* doesnt consider higher-valued f nodes until it has considered lower-valued f nodes, it never strays off the shortest path.

Heuristics for grid maps:

On a grid, there are well-known heuristic functions to use. Use the distance heuristic that matches the allowed movement:

On a square grid that allows 4 directions of movement, use Manhattan distance (L1). On a square grid that allows 8 directions of movement, use Diagonal distance (L). On a square grid that allows any direction of movement, you might or might not want Euclidean distance (L2). If A* is finding paths on the grid but you are allowing movement

11

CSE DEPARTMENT | IMMANUEL ARASAR JJ COLLEGE OF ENGINEERING

12

HEURISTIC FUNCTIONS

not on the grid, you may want to consider other representations of the map. On a hexagon grid that allows 6 directions of movement, use Manhattan distance adapted to hexagonal grids.

Manhattan distance

The standard heuristic for a square grid is the Manhattan distance. Look at your cost function and find the minimum cost D for moving from one space to an adjacent space. The heuristic on a square grid where you can move in 4 directions should be D times the Manhattan distance: h(n) = D * (abs(n.x-goal.x) + abs(n.ygoal.y)) How do you pick D? Use a scale that matches your cost function. For the best paths, and an admissible heuristic, set D to the lowest cost between adjacent squares. In the absence of obstacles, and on terrain that has the minimum movement cost D, moving one step closer to the goal should increase g by D and decrease h by D. When you add the two, f (which is set to g + h) will stay the same; thats a sign that the heuristic and cost function scales match. You can also give up optimal paths to make A* run faster by increasing D, or by decreasing the ratio between the lowest and highest edge costs.

12

CSE DEPARTMENT | IMMANUEL ARASAR JJ COLLEGE OF ENGINEERING

13

HEURISTIC FUNCTIONS

(Note: the above image has a tie-breaker added to the heuristic.}

Diagonal distance

If your map allows diagonal movement you need a different heuristic (sometimes called the Chebyshev distance). The Manhattan distance for (4 east, 4 north) will be 8*D. However, you could simply move (4 northeast) instead, so the heuristic should be 4*D. This function handles diagonals, assuming that both straight and diagonal movement costs D: h(n) = D abs(n.y-goal.y)) * max(abs(n.x-goal.x),

13

CSE DEPARTMENT | IMMANUEL ARASAR JJ COLLEGE OF ENGINEERING

14

HEURISTIC FUNCTIONS

If the cost of diagonal movement is not D, but something like D2 = sqrt(2)*D, the above heuristic wont be right for you. You will instead want something more sophisticated: h_diagonal(n) = min(abs(n.x-goal.x), abs(n.y-goal.y)) h_straight(n) = (abs(n.x-goal.x) + abs(n.y-goal.y)) h(n) = D2 * h_diagonal(n) + D * (h_straight(n) - 2*h_diagonal(n))) Here we compute h_diagonal(n) = the number of steps you can take along a diagonal, h_straight(n) = the Manhattan distance, and then combine the two by considering all diagonal steps to cost D2, and then all remaining straight steps (note that this is the number of straight steps in the Manhattan distance, minus two straight steps for each diagonal step we took instead) cost D.

Euclidean distance

If your units can move at any angle (instead of grid directions), then you should probably use a straight line distance: h(n) = D * sqrt((n.x-goal.x)^2 + (n.ygoal.y)^2) However, if this is the case, then you may have trouble with using A* directly because the cost function g will not match the heuristic function h. Since Euclidean distance is

14

CSE DEPARTMENT | IMMANUEL ARASAR JJ COLLEGE OF ENGINEERING

15

HEURISTIC FUNCTIONS

shorter than Manhattan or diagonal distance, you will still get shortest paths, but A* will take longer to run:

Euclidean distance, squared

Ive seen several A* web pages recommend that you avoid the expensive square root in the Euclidean distance by just using distance-squared: h(n) = goal.y)^2) D * ((n.x-goal.x)^2 + (n.y-

Do not do this! This definitely runs into the scale problem. The scale of g and h need to match, because youre adding them together to form f. When A* computes f(n) = g(n) + h(n), the square of distance will be much higher than the cost g and you will end up with an overestimating heuristic. For longer distances, this will approach the extreme of g(n) not contributing to f(n), and A* will degrade into (Greedy) BestFirst-Search:
CSE DEPARTMENT | IMMANUEL ARASAR JJ COLLEGE OF ENGINEERING

15

16

HEURISTIC FUNCTIONS

To attempt to fix this you can scale the heuristic down. However, then you run into the opposite problem: for shorter distances, the heuristic will be too small compared to g(n) and A* will degrade into Dijkstras algorithm. If, after profiling, you find the cost of the square root is significant, either use a fast square root approximation with Euclidean distance or use the diagonal distance as an approximation to Euclidean.

Breaking ties

In some maps there are many paths with the same length. For example, in flat areas without variation in terrain, using a grid will lead to many equal-length paths. A* might explore all the paths with the same f value, instead of just one. (If you do have lots of such areas, there might be other techniques that are better than using A* on a grid.)

16

CSE DEPARTMENT | IMMANUEL ARASAR JJ COLLEGE OF ENGINEERING

17

HEURISTIC FUNCTIONS

To solve this problem, we need to either adjust the g or h values; it is usually easier to adjust h. The tie breaker needs to be deterministic with respect to the vertex (i.e., it shouldnt just be a random number), and it needs to make the f values differ. Since A* sorts by f value, making them different means only one of the equivalent f values will be explored. One way to break ties is to nudge the scale of h slightly. If we scale it downwards, then f will increase as we move towards the goal. Unfortunately, this means that A* will prefer to expand vertices close to the starting point instead of vertices close to the goal. We can instead scale h upwards slightly (even by 0.1%). A* will prefer to expand vertices close to the goal. heuristic *= (1.0 + p) The factor p should be chosen so that p <(minimum cost of taking one step)/(expected maximum path length). Assuming that you dont expect the paths to be more than 1000 steps long,
CSE DEPARTMENT | IMMANUEL ARASAR JJ COLLEGE OF ENGINEERING 17

18

HEURISTIC FUNCTIONS

you can choose p = 1/1000. The result of this tie-breaking nudge is that A* explores far less of the map than previously:

Tie-breaking scaling added to heuristic. When there are obstacles of course it still has to explore to find a way around them, but note that after the obstacle is passed, A* explores very little:

Tie-breaking scaling added to heuristic, works nicely with obstacles.

Steven van Dijk suggests that a more straightforward way to do this would to pass h to the comparison function. When the
CSE DEPARTMENT | IMMANUEL ARASAR JJ COLLEGE OF ENGINEERING

19

HEURISTIC FUNCTIONS

f values are equal, the comparison function would break the tie by looking at h. Another way to break ties is to compute a hash of the coordinates, and use that to adjust the heuristic. This breaks more ties than adjusting h as above. Thanks to Cris Fuhrman for suggesting this. A different way to break ties is to prefer paths that are along the straight line from the starting point to the goal: dx1 = current.x - goal.x dy1 = current.y - goal.y dx2 = start.x - goal.x dy2 = start.y - goal.y cross = abs(dx1*dy2 - dx2*dy1) heuristic += cross*0.001 This code computes the vector cross-product between the start to goal vector and the current point to goal vector. When these vectors dont line up, the cross product will be larger. The result is that this code will give some slight preference to a path that lies along the straight line path from the start to the goal. When there are no obstacles, A* not only explores less of the map, the path looks very nice as well:

19

CSE DEPARTMENT | IMMANUEL ARASAR JJ COLLEGE OF ENGINEERING

20

HEURISTIC FUNCTIONS

Tie-breaking cross-product added to heuristic, produces pretty paths. However, because this tie-breaker prefers paths along the straight line from the starting point to the goal, weird things happen when going around obstacles (note that the path is still optimal; it just looks strange):

Tie-breaking cross-product added to heuristic, less pretty with obstacles. To interactively explore the improvement from this tie breaker, see James Macgills A* applet [or try this mirror or this mirror]. Use Clear to clear the map, and choose two points on
CSE DEPARTMENT | IMMANUEL ARASAR JJ COLLEGE OF ENGINEERING 20

21

HEURISTIC FUNCTIONS

opposite corners of the map. When you use the Classic A* method, you will see the effect of ties. When you use the Fudge method, you will see the effect of the above cross product added to the heuristic. You may also want to read about the AlphA* algorithm, which has a more sophisticated way to break ties, yet still maintain bounds on the optimality of the resulting path. AlphA* is adaptive and is likely to perform better than either of the two tie-breakers I described above. However, the tie-breakers I described are extremely easy to implement, so start with them first, and tryAlphA* if you need something better.

21

CSE DEPARTMENT | IMMANUEL ARASAR JJ COLLEGE OF ENGINEERING