“A Formal Basis for the Heuristic Determination of Minimum Cost Paths” was published by Peter E. Hart, Nils J. Nilsson, and Bertram Raphael in IEEE Transactions on Systems Science and Cybernetics, volume 4, number 2, pages 100 to 107, in July 1968. All three worked at Stanford Research Institute, where the algorithm was devised to help the Shakey robot find efficient routes through a world of obstacles. The paper introduced the search method the authors named A*.
The paper’s mathematical core is a way to fold heuristic knowledge into graph search without giving up guarantees. A* scores each candidate path by adding the known cost to reach a node to an estimate of the remaining cost to the goal. The authors proved that if the estimate never overstates the true remaining cost, a property later called admissibility, then A* is guaranteed to find a least-cost path, and that it does so while expanding no more nodes than any other algorithm with the same information. That combination of optimality and efficiency is what set A* apart from blind methods like breadth-first search and from purely greedy heuristics.
A* became one of the most widely taught and widely used algorithms in computer science. It is the workhorse behind route finding in maps and games, motion planning in robotics, and many planning and scheduling systems. The same idea, guiding a search with an informed but cautious estimate, recurs throughout artificial intelligence.
Why business readers should care: every navigation app, delivery-routing system, and game character that finds its way around an obstacle is leaning on this 1968 result. A* is a rare case of a single paper producing an algorithm that is still the default answer decades later.