The A∗ algorithm does not define what happens when multiple elements on the frontier have the same f-value. Compare the following tie-breaking conventions by first conjecturing which will work better, and then testing it on some examples. Try it on some examples where there are multiple optimal paths to a goal (such as finding a path from the bottom left of a rectangular grid to the top right of the grid, where the actions are step-up and step-right). Of the paths on the frontier with the same minimum f-value, select one:

(i) uniformly at random

(ii) that has been on the frontier the longest

(iii) that was most recently added to the frontier

(iv) with the smallest h-value

(v) with the least cost.

The last two may require other tie-breaking conventions when the cost and h values are equal.