The A* algorithm
Three SRI researchers described a search combining the cost so far with an estimate of the rest, and proved that with an admissible estimate the path found is optimal.
Why it matters
A heuristic stopped being a guess: under a precise condition on the estimate, the search stays both fast and correct.
The algorithm grew out of route planning for the Shakey robot. Admissibility requires the estimate never to exceed the true cost. A* is still the standard path-planning algorithm, and the same idea of guided search runs through modern methods such as Monte Carlo tree search.