Artificial intelligence · 1968
A* search
An optimal, efficient path-finding algorithm born from a robot's navigation needs.
Peter Hart, Nils Nilsson and Bertram Raphael published A* for Shakey's route planning. With an admissible heuristic it finds the cheapest path while exploring far fewer states than blind search. It now routes video game characters, GPS directions and robots.
What it built on 1
What it led to 1
Related measurements
The dashed line marks when it first worked.
Training compute of notable AI models Source: Epoch AI, Notable AI Models (CC BY 4.0)
Computation per constant dollar, 1850-2006 Latest: 7.3B million units of computer power per 2006 $ (2003) Source: Nordhaus 2007, Two Centuries of Productivity Growth in Computing, J. Econ. Hist. 67(1), Table 6