A 1968 Robot Accidentally Invented the "Brain" for All AI — The A* Algorithm Powers Everything from Navigators to ChatGPT via Pathfinding
Any task is a route from one point to another. And this is the foundation of every intelligent machine.
Any task is a route from one point to another. And this is the foundation of every intelligent machine.
Almost everything artificial intelligence does today is based on a simple but fundamental idea: any task can be reduced to a pathfinding problem—from a starting point to a goal. A computer considers different states, evaluates which ones are closer to the result, and moves forward step-by-step until it finds a solution.
The clearest analogy is navigation. When a person plots a route on the London Underground, for example from Bond Street to King's Cross, they mentally go through options: Central Line to Oxford Circus, transfer to the Victoria Line, stations Warren Street, Euston—and the final destination. A computer does the same thing, only faster and without guesswork. It systematically searches for a path, selecting the most efficient steps. One of the first and still most famous search algorithms of this kind is A* (pronounced "A-star"). It was invented in 1968 when engineers were trying to teach a robot to move autonomously around a room.
This robot was named Shakey. It was created at the Stanford Research Institute in Menlo Park. Externally, it looked clumsy, but it was a real breakthrough for its time: a camera, microphone, rangefinder, collision sensors, motorized wheels, and its own computer. If told, "go to the library and pick up an object," it would plot a route on its internal map, calculate the steps, and start moving, checking its path against sensor readings. Shakey became the first robot that made its own decisions, rather than just executing commands. In 2004, it was inducted into Carnegie Mellon University's Robot Hall of Fame—alongside HAL 9000, R2-D2, and other icons of the era.
The A* algorithm proved so effective that it quickly became a classic. If a path between points exists, it will find it. If there are several routes, it will choose the shortest one. At the same time, it doesn't waste resources on unnecessary detours—it acts as efficiently as possible. This is precisely the principle behind modern navigators: when your phone instantly plots a route considering traffic and road closures, an improved version of A* is working behind the scenes. The irony is that an algorithm invented for controlling robots now helps people navigate the real world every day.
But the idea of search doesn't only work in physical space. It can also be applied to logical problems, where there are no roads or maps, but there are possible states and transitions between them. A clear example is the "sliding eight" puzzle: a 3x3 grid, eight numbered tiles, and one empty cell. The goal is to slide the tiles until they are in numerical order. Each move creates a new state, and solving the puzzle boils down to finding a sequence of steps that leads from the initial configuration to the solved one.
In the 1950s, two American researchers—Allen Newell and Herbert Simon—decided that the same principle could be applied to human thinking. At the 1956 Dartmouth Conference, they presented a program called Logic Theorist—a system that searched for proofs of mathematical theorems. Newell was then working at the RAND Corporation and later moved to Carnegie Mellon, where he continued his collaboration with Simon. Simon, a professor of management science, later won the Nobel Prize in Economics for his research into how humans make decisions with limited knowledge and time. Their common goal was simple: to understand if a machine could be made to reason using the same principles as a human.
Logic Theorist became the first artificial "mathematician." The program treated proofs as chains of logical steps leading from axioms to a conclusion. It proved 38 of the 52 theorems from Bertrand Russell and Alfred North Whitehead's famous work Principia Mathematica, and some of them—in a shorter and more elegant way than the original. Essentially, Logic Theorist did the same thing as A*: it searched for a path, not on a map, but in the space of formulas.
Principia Mathematica itself, written in the early 20th century, attempted to create a logic upon which all of mathematics could be built. One example is the law of modus tollens: if the truth of P implies Q, then the falsity of Q implies that P is also false. A modern example: if winning the lottery makes a person happy, then an unhappy person definitely did not win. Logic Theorist could find such connections on its own, starting from initial premises and applying logical rules until it reached the desired conclusion.
This result was a milestone. For the first time, a machine wasn't just calculating, but reasoning—step-by-step proving statements that were considered the prerogative of the human mind. Historians of artificial intelligence later called Logic Theorist the moment when computation turned into reasoning. Newell and Simon's program showed that the thought process could be represented as a search for a solution in a vast space of possible steps.
Thus, the idea of search—moving from one point to another—became the heart of artificial intelligence. From the Shakey robot choosing a route through a lab, to a program capable of proving mathematical truths—all are manifestations of the same principle: to think and make decisions, one must be able to search for a path to the goal, even if the map exists only in the machine's imagination.
