A* (pronounced “A-star”) is an algorithm for finding the shortest, or lowest-cost, path between two points in a network of possibilities, such as the roads between two cities or the squares a game character must cross. It was introduced by Peter Hart, Nils Nilsson, and Bertram Raphael in their 1968 paper “A Formal Basis for the Heuristic Determination of Minimum Cost Paths,” published in IEEE Transactions on Systems Science and Cybernetics. The work came out of the same Stanford Research Institute effort that built Shakey, an early mobile robot that needed to plan how to move around a room.
The key idea is the heuristic, an educated guess about how far each option is from the goal. A blind search would explore the network in every direction equally, wasting effort. A* instead always expands the option that looks most promising, scoring each by the cost already spent to reach it plus an estimate of the cost remaining. When the estimate never overshoots the true remaining cost, A* is guaranteed to find the genuinely shortest path while exploring far fewer possibilities than an exhaustive search. That combination of optimality and efficiency is why the paper became a cornerstone of artificial intelligence.
Business readers encounter A* and its descendants constantly, usually without knowing it. It is the engine behind turn-by-turn driving directions, the movement of characters in video games, route planning for warehouse robots and delivery fleets, and step-by-step planning in many automated systems. Whenever software has to choose a good sequence of moves through a space of options under a clear cost, A* or a variant is a likely candidate.
The honest limit is that A* needs a well-defined map of states and moves and a reasonable cost estimate. When the space of possibilities is astronomically large, poorly defined, or changes constantly, plain A* runs out of memory or time, and practitioners turn to approximations, sampling-based planners, or learned policies. Even so, it remains a standard tool taught in every introductory AI course and embedded in production systems decades after its introduction.