A* Tie Breaking

A* is one of the most widely-known search algorithms. A* or its variants are used in robotics, games, sequence alignment, and many other applications. These videos illustrate the difference a good heuristic and tie-breaking rule can make.

In these examples, we are only allowed to move diagonally and horizontally/vertically. The yellow state is the next state to be expanded. Red states are on the closed list and green states are on the open list.

In our first example we use euclidean distance as our heuristic. This means that the heuristic predicts that we can travel in a straight line from the start to the goal. Since we can't actually travel in a straight line, this isn't a particularly accurate heuristic, and it results in expanding quite a large number of nodes.

In our second example we switch to using an octile heuristic. This heuristic takes into account the fact that we can only travel on 45 degree diagonal edges. If the x-distance and y-distance to the goal are x and y, the octile heuristic is max(x, y) + (sqrt(2)-1)*min(x, y). [Note that 1.5 diagonal costs are also commonly used for efficiency reasons.] A* with the octile heuristic expands fewer nodes that with the euclidean heuristic, but in this example it still performs a lot of work.

The problem in the previous example is tie-breaking. There are many states with the same f-cost, and we have to choose the order in which to expand them. In the last example we expanded states with lowest g-cost first. That is, we preferred states closer to the start state than the goal state. Since the goal will be far from the start state, it would be better to reverse the tie-breaking rule, and instead expand states with highest g-cost first. The results are much better:

Permission is granted to download and use these videos for non-commercial use.

Euclidean Heuristic
Tie-Breaking Low g-cost
Tie-Breaking High g-cost