Go deeper · How machines learn
How does a computer plan without learning?
By searching. The computer lists the moves it could make, the moves after those, and so on, and looks through those options for one that reaches the goal. No training data is needed: a person writes the rules of the problem and the search method. Clever shortcuts called heuristics keep the search from drowning in options.
What you will be able to do
Describe a problem as states, moves and a goal; compare breadth-first search, greedy search and A* by squares checked and path length; and explain why a hand-written expert system is brittle.
Before you start
Read Is every AI a chatbot? first. It places search and hand-written rules on the map of AI, next to machine learning.
1 · You have already seen this
Directions that appear in a moment
Most people have asked a map app how to get somewhere and watched a route appear.
Between any two places there are many possible ways, with roads that branch off other roads, and the app has to pick one. The route itself comes from a search: the app looks through the roads that join where you are to where you want to go, adding up their lengths as it goes.
That is search and planning. A person writes down the rules of the problem, and the computer looks through the possible moves for a sequence that reaches the goal. It needs no training data and does not get better with practice. This page uses a robot on a warehouse floor and a small made-up map. It shows how that works, lets you try it, and shows where it goes wrong.
2 · What happens, step by step
From a start to a finished plan
Search in four steps. The next section goes deeper into steps 1 and 2, and the one after it into step 3. After the lab, a worked example on a road map runs all four steps when roads have different lengths.
How a search finds a plan
Four steps
- 1 · Describe the problemWrite down the states, the moves and the goal. For a warehouse robot, a state is the square it stands on, a move is one square up, down, left or right, and the goal is a test: is the robot at the loading dock?
- 2 · Grow the optionsFrom the start, list every possible move, then every move after those. Drawn out, these options form a search tree, and it grows so fast that nobody can check every branch of a long problem.
- 3 · Choose what to check nextWaiting states sit on a to-do list. Each search method has its own rule for which one comes off next: breadth-first search checks everything one step away before anything two steps away, and other methods use a heuristic, a quick estimate of how far is left.
- 4 · Stop at the goalWhen a checked state passes the goal test, the search stops. Following the moves back from the goal to the start gives the plan.
Going deeper · steps 1 and 2
States, moves and a goal
Many planning problems can be described in the same three parts, and then one search method solves them all.
A state is a snapshot of the situation: where the robot stands, what the chessboard looks like. Moves (often called actions) turn one state into another. The goal is a test: is the robot at the loading dock? Is the king checkmated? A plan is a sequence of moves from the start to a goal state.
Drawn out, the options form a search tree: the start at the top, one branch for each possible move, more branches under each of those. Trees grow fast. Tic-tac-toe has 9 possible first moves, 9 × 8 = 72 ways to play the first two moves, and 9 × 8 × 7 = 504 for the first three. In chess there are 20 possible first moves for each side, so 20 × 20 = 400 positions after just one move each. Nobody can check every branch of a long game.
So search methods differ in which branch to look at next. Breadth-first search (BFS) looks at everything one step away, then everything two steps away, like a ripple spreading on a pond. On a grid where every move costs the same, the first time the ripple reaches the goal it has found a shortest path, but it may have checked a lot of squares to get there.
You may have used one already. The ARQIV robot path planner in AI in engineering runs breadth-first search on a warehouse grid and shows the squares the planner checked. It is a hand-coded algorithm, not a trained model: it never saw an example and never gets better with practice. It is still AI in the classic sense, because it plans.
Going deeper · step 3
A good guess about what is left
A heuristic is a quick estimate of how far a state is from the goal. It lets a search head in a promising direction.
On a grid where the robot moves up, down, left or right, a natural estimate is the Manhattan distance: columns apart plus rows apart, like counting city blocks. From column 2, row 3 to column 7, row 1 it is (7 − 2) + (3 − 1) = 5 + 2 = 7. Walls can make the real trip longer, never shorter.
Greedy best-first search always checks the square with the smallest estimate next. It rushes toward the goal, which is fast, but it ignores how far it has already walked, so a wall can lead it into a long detour.
A* (say “A star”) checks the square with the smallest steps so far + estimate. It balances the two. If the estimate never overestimates, as Manhattan distance never does on this grid, A* is guaranteed to find a shortest path, usually after checking far fewer squares than breadth-first search.
Optional · why A* is safe
The estimate never lies upward
Suppose A* is about to finish with a route of length 16 while a better route of length 14 exists. Some square on that better route is still waiting on the to-do list, and its steps so far + estimate is at most 14, because the estimate never overestimates. 14 is smaller than 16, so A* would have checked that square first. It keeps doing this until the shorter route is found.
Predict first
On the open floor in the lab, breadth-first search checks 81 squares before reaching the goal. Guess: how many will A* check, and will its path be any longer?
Show the answer
19 squares, and the same 12-move path. The estimate points A* straight at the goal, so it barely looks sideways. Greedy search checks 16 here. The rubble field is where greedy search gets into trouble.
3 · Try it
Race three planners through a warehouse
Same robot, same floors, three ways of choosing which square to check next.
Lab
Which planner checks fewer squares?
Pick a floor and a planner. Cyan squares were checked, numbered in the order the planner examined them; the green route is its path. Drag the slider to replay the search one square at a time.
Runs in your browser on made-up floors. These planners are hand-written code, not trained models.
Three challenges
- On the open floor, replay breadth-first search with the slider. What shape does the checked area grow in?
- On the dead-end wall, why do greedy search and A* both check squares inside the pocket?
- On the rubble field, compare greedy search with A*. Which one would you trust to plan a delivery robot’s route, and why?
Each planner moves a robot from S to G on a grid, one square up, down, left or right; # is a shelf. “Checked” counts the squares the planner took off its to-do list and examined.
| Floor | Breadth-first | Greedy best-first | A* |
|---|---|---|---|
| Open floor | 81 checked · 12 moves | 16 checked · 12 moves | 19 checked · 12 moves |
| Dead-end wall | 76 checked · 13 moves | 25 checked · 13 moves | 30 checked · 13 moves |
| Rubble field | 63 checked · 14 moves | 32 checked · 24 moves | 23 checked · 14 moves |
Rubble field, greedy: o = checked, * = path (24 moves)
..#..#.#.... ..#...****o. .....#*#.*#. .S#..#**#**. #*##.##*o#G. .**##o**o##. ..***#*oo##. #.##***o#...
Rubble field, A*: o = checked, * = path (14 moves)
..#..#.#.... ..#.******o. .****#.#.*#. oS#oo#..#**. #o##o##..#G. .oo##....##. .....#...##. #.##....#...
Different step lengths
When roads are not all equal
On a grid every move costs one. On a road map, steps have different lengths, so the search must add up distances.
Worked example
The shortest way to school, by hand
- The mapFive made-up places joined by roads (lengths in km): Home–Park 2, Home–Library 4, Park–Library 1, Park–Bakery 6, Library–Bakery 2, Library–School 7, Bakery–School 2. Find the shortest route from Home to School.
- RuleAlways settle the unsettled place with the smallest total distance so far, then update its neighbors. This “cheapest first” search is Dijkstra’s algorithm, A* without an estimate.
- Step 1: Home (0)Neighbors get Park 0 + 2 = 2 and Library 0 + 4 = 4.
- Step 2: Park (2)Library via Park: 2 + 1 = 3, better than 4, so update it. Bakery via Park: 2 + 6 = 8.
- Step 3: Library (3)Bakery via Library: 3 + 2 = 5, better than 8. School via Library: 3 + 7 = 10.
- Step 4: Bakery (5)School via Bakery: 5 + 2 = 7, better than 10.
- Step 5: School (7)Done. Follow the updates backward: Home → Park → Library → Bakery → School = 2 + 1 + 2 + 2 = 7 km.
- CompareThe route with the fewest roads, Home → Library → School, is 4 + 7 = 11 km. Breadth-first search finds the fewest steps; when steps have different lengths, you need a search that adds up costs.
The map is made up. Map apps run searches like this on road networks with millions of junctions, using faster variants.
Rules and constraints
Expert systems and puzzles with rules
Search is one part of “symbolic AI”: methods that work with symbols and rules a person wrote down.
Constraints. Many problems are less about a route and more about fitting pieces together under rules: a school timetable where no student has two classes at once, a sudoku, a delivery schedule. A constraint solver tries values for each piece, checks the rules, and backs up as soon as one is broken, which skips huge parts of the search tree.
Expert systems. In the 1970s and 1980s, companies built systems from hundreds or thousands of IF–THEN rules collected by interviewing experts. They could explain every answer (“rule 12 fired”), which is still a strength. But they were brittle: they knew only what was written down, broke on cases nobody had thought of, and every new rule could clash with old ones. Getting experts to put everything they know into rules turned out to be very hard. Learning from examples became popular partly because it avoids writing every rule by hand.
Rules have not disappeared. Tax software, safety interlocks and many business systems are rule-based on purpose, because their behavior must be predictable and easy to check.
A tiny made-up expert system
The houseplant helper
- IF leaves are yellow AND soil is wet THEN “water less”
- IF leaves are yellow AND soil is dry THEN “water more”
- IF leaf tips are brown AND plant is near a heater THEN “move it away from the heat”
Now a plant in a dark corner has yellow leaves and wet soil. Rule 1 fires: “water less.” The real problem is too little light, which no rule mentions, so the system gives a confident wrong answer instead of saying “I don’t know.”
Search plus learning
Where the two work together
The strongest systems often search with rules and use machine learning for the part that is hard to write down.
Chess engines
Search, scored by a small network
Engines such as Stockfish search ahead through moves and replies and cut off branches that cannot matter. To judge a position at the end of a branch, recent versions use a small neural network trained on positions. Older versions used hand-tuned scoring rules.
AlphaGo
Tree search guided by learning
AlphaGo used networks trained with supervised and reinforcement learning to suggest promising moves and judge positions, and a tree search to look ahead. See How does a machine learn from rewards?
Map apps
Route search, learned travel times
The route itself comes from a graph search like the worked example. The travel time on each road can come from a model trained on traffic data; in 2020 DeepMind reported such a model improving arrival-time estimates in Google Maps.
4 · Common mix-ups
Four beliefs about search worth unlearning
Each one comes with what to think instead.
Mix-up: If it is AI, it must have learned from data.
Better: Search and rule-based systems are AI too. The robot planner in the lab never trained on anything; a person wrote its method.
Mix-up: A search tries every possibility.
Better: Only for tiny problems. Real searches skip branches using heuristics, constraints and pruning; chess has far too many games to check.
Mix-up: A heuristic is a guess, so A* can give wrong answers.
Better: If the estimate never overestimates, A* still finds a shortest path. Greedy search, which trusts only the estimate, can return a longer one, as in the rubble field.
Mix-up: Expert systems are dead.
Better: Rule-based systems are still everywhere where behavior must be predictable and checkable. Their weakness is cases nobody wrote a rule for.
5 · Check yourself
Three quick questions
Answer in your head or on paper before you open each one.
A robot is at column 2, row 3. The goal is at column 7, row 1. What is the Manhattan distance, and could the real path be shorter?
Check your answer
(7 − 2) + (3 − 1) = 5 + 2 = 7. The real path can be longer if shelves are in the way, but never shorter, because each move changes the column or the row by only 1. That is why A* can trust it.
On the rubble field, greedy search returns a 24-move path while A* returns 14 moves. Why?
Check your answer
Greedy search always checks the square that looks closest to the goal and ignores how many steps it took to get there. It followed promising-looking squares down a long detour and never reconsidered. A* adds the steps already taken, so a long detour looks worse and it keeps looking for a shorter route.
In the worked example, the road between the Library and the Bakery closes. What is the new shortest route to School?
Check your answer
Two routes tie at 10 km: Home → Park → Library → School (2 + 1 + 7) and Home → Park → Bakery → School (2 + 6 + 2). Home → Library → School is 11 km. A planner recomputes this instantly; it does not need retraining, just the new map.
For younger learners
A grades 3–5 version
Breadth-first search on paper, with numbers instead of code.
20 minutes · pairs
Flood the maze
- Draw a 6 × 6 grid maze with a few shaded walls, a start and a goal.
- Write 1 in every square next to the start, 2 in every empty square next to a 1, and so on.
- When a number lands on the goal, trace back down the numbers (… 3, 2, 1) to draw a shortest path.
Talk about it
Did the computer learn?
No. It followed the same counting rule you did. Good answers notice that the rule always works, and that you had to number a lot of squares that were nowhere near the goal.
Honest limits
What this page leaves out
What this page leaves out
Real planners deal with things this page skips: moving obstacles and other robots, uncertainty about where things are, actions that sometimes fail, and maps with millions of states. Game search uses methods such as minimax, alpha-beta pruning and Monte Carlo tree search. Logic, knowledge graphs and probabilistic reasoning are other symbolic tools. AIMA, the standard AI textbook, covers all of them.
Where to go next
Planning, learning and robots
Next in this branch
Why are there different kinds of neural networks?
The learning side of the map, family by family.
Search at work
Plan a robot’s path
ARQIV’s warehouse pathfinder: breadth-first search, step by step.
Previous in this branch
How does a machine learn from rewards?
Agents, rewards and AlphaGo’s learning half.
Sources
Where this comes from
- Stuart Russell and Peter Norvig, Artificial Intelligence: A Modern Approach, 4th edition, table of contents: search, heuristics, constraint satisfaction, game search, logic and knowledge-based systems.
- Peter E. Hart, Nils J. Nilsson and Bertram Raphael (1968), “A formal basis for the heuristic determination of minimum cost paths,” IEEE Transactions on Systems Science and Cybernetics: the original A* paper.
- Amit Patel, Red Blob Games, “Introduction to the A* algorithm”: interactive breadth-first search, Dijkstra’s algorithm, greedy best-first search and A* on grids.
- Chess Programming Wiki, “Stockfish NNUE”: a search-based chess engine that scores positions with a small neural network.
- David Silver et al. (2016), “Mastering the game of Go with deep neural networks and tree search,” Nature.
- DeepMind (2020), “Traffic prediction with advanced Graph Neural Networks”: learned travel-time estimates for Google Maps.
AI words on this page
Search and planning, Symbolic AI and expert systems, Algorithm, Artificial intelligence, Machine learning, Reinforcement learning, Neural network, Model
All definitions live in one place: AI words in plain language →
Review status
Written by ARQIV. Last checked October 2026. Independent subject review and classroom pilots are still to come, so treat the activities as drafts and tell us about anything that is wrong or unclear.