AI Explorers · lesson 9 of 24 · 25 min
Your map app finds a route across the city in less than a second, even though there are thousands of possible ways to go. It is not guessing. It is searching.
Search problems
Many AI problems can be described as a search problem. Every search problem has:
- A start: where you are now.
- A goal: where you want to end up.
- Actions: the moves you can make.
- A cost: what each move costs, like minutes, miles or money.
Finding directions is a search problem. So is solving a maze, planning moves in a board game, or a delivery driver planning stops.
Searching a map
Remember graphs from lesson 7? Here is a small neighborhood as a graph. The numbers are walking minutes.
| From | To | Minutes |
|---|---|---|
| Home | Corner store | 4 |
| Home | Park | 6 |
| Corner store | Library | 5 |
| Park | Library | 2 |
| Library | Rec center | 3 |
| Park | Rec center | 9 |
What is the fastest way from Home to Rec center? A simple way to search is to list every path and add up the costs:
- Home → Corner store → Library → Rec center = 4 + 5 + 3 = 12 minutes
- Home → Park → Library → Rec center = 6 + 2 + 3 = 11 minutes
- Home → Park → Rec center = 6 + 9 = 15 minutes
The fastest is through the park and library: 11 minutes. Notice that the path with the fewest stops (Home → Park → Rec center) was actually the slowest.
Smarter searching
Listing every path works for a tiny map. A real city has so many paths that listing them all would take far too long, even for a fast computer. So AI uses smarter search methods.
One smart trick is to always explore the cheapest path found so far before trying more expensive ones. Another is to use a heuristic, a helpful rule of thumb, like “prefer roads that head toward the goal.” Heuristics let the computer skip paths that are clearly bad, like heading the opposite direction.
Game AI uses search too. A chess program imagines moves, then the other player’s replies, then its own next moves, and so on, picking the move that leads to the best outcome it can find.
Search shows up beyond maps. A delivery company plans the order of stops so drivers waste less time. A video game character finds its way around walls to reach you. A school scheduling program searches for a class schedule where no teacher is in two rooms at once. Whenever there are many possible choices and one goal, there is probably a search behind the scenes.
Try it
- Draw a map of your own neighborhood or school with five or six places as nodes: home, a store, a friend’s house, a park, a church, a bus stop.
- Connect places that are directly reachable and write an estimated walking time on each line.
- Pick a start and a goal. List at least three possible paths and add up each one’s time.
- Circle the fastest path. Was it the one with the fewest stops?
- Add a “road closed” by crossing out one line. Find the new best path.
Check yourself
What four parts does every search problem have?
A start, a goal, actions (possible moves), and a cost for each move.
Why can’t computers just list every path in a big city?
There are far too many possible paths, so it would take too long. Smarter methods skip bad paths.
What is a heuristic?
A helpful rule of thumb that guides the search, like preferring roads that head toward the goal.
Key words
- Search problem: finding a way from a start to a goal.
- Cost: what a move takes, like time or distance.
- Path: a sequence of moves from start to goal.
- Heuristic: a rule of thumb that helps search faster.
Previous lesson: Rules and decision trees
Back to AI Explorers
Next lesson: Learning from examples, not rules