Topic 6b – Reasoning and Search

How an AI agent thinks through a problem — by turning it into a map and finding a path.

Learning Objectives

By the end of this topic, you should be able to:

Learning Activities

To help you meet the learning objectives, we have prepared a combination of readings, activities, and videos.

Activity

For this topic we are going to start in a different order. Before you get to the readings, I want you to consider a little puzzle problem that will help lay the foundation for the readings.

Course Readings

These reading were designed to introduce the course topics to an audience of educators. They should be considered "required" and read in order.

Supplemental Readings

Some participants find it helpful to read about a topic from a source written for a slightly more technical audience. These supplemental readings cover similar material as the course readings but may not fully align with the course learning objectives. Use them as an optional complement to your study, not a substitute for the course readings.

Lesson Videos

These videos support the readings above and may present the material with some deeper connections and worked examples.

Checking for Understanding, Questions

Production Systems and State Spaces

  1. A librarian is trying to find a misfiled book. She starts in one section of the stacks, checks each shelf, and moves to an adjacent section if the book is not there. Describe this situation as a production system: what are the states? What are the productions? What is the start state? What is the goal state?
  2. GPS navigation, chess, email spam filtering, and solving a jigsaw puzzle can all be framed as production systems. For one of them, identify the states, productions, start state, and goal state.
  3. Why is it impractical to represent the entire state space for chess explicitly? What does this tell us about how AI systems must approach complex problems?

Search Trees and BFS

  1. Draw the first two levels of a BFS search tree for the following small problem: you are at city A, which connects directly to cities B and C. City B connects to D and E. City C connects to F and G. The goal is city F. Show each node, label the levels, and indicate where BFS would find the goal.
  2. What does it mean for BFS to be "complete"? What property of BFS guarantees that it will always find the shortest path to the goal?
  3. BFS found the goal in the previous question by checking cities in what order? List them. Explain why BFS checks them in that order rather than pursuing one path all the way to a dead end first.

Depth-First Search and Heuristics

  1. Using the same city map from question 4, trace how DFS would search for city F, assuming it always explores the leftmost branch first. In what order does it visit nodes? How does this compare to BFS?
  2. Give an example of a heuristic that you might use in everyday life when making a decision under uncertainty. What makes it a heuristic rather than a guaranteed correct answer?
  3. Your GPS estimates remaining travel time to your destination as you drive. How is this similar to a heuristic in a search algorithm? What could cause the estimate to be wrong — and how does the system recover when it is?

Checking for Understanding, Answers

You can compare your answers to the following answer key.

Show Answer Key

Production Systems and State Spaces

  1. States: each distinct location the librarian could currently be (e.g., Section A Shelf 1, Section A Shelf 2, Section B Shelf 1, etc.). Productions: the legal moves she can make — check the current shelf, move to the next shelf in the section, or move to an adjacent section. Start state: the section and shelf where she begins her search. Goal state: the shelf where the misfiled book is found.
  2. Many valid answers. Example for GPS navigation: States = every intersection the car could be at; productions = the roads connecting intersections (turn left onto Main St., continue on Elm Ave., etc.); start state = the current location; goal state = the destination address. The search problem is: find a sequence of productions (turns and road segments) connecting start to goal.
  3. The number of possible chess positions is estimated at around 1043. Storing all of them explicitly would require more memory than exists in the observable universe. This tells us that AI systems facing complex problems cannot enumerate the entire state space — they must search it selectively, using strategies like BFS, DFS, or heuristic-guided search to find a good path without examining every possibility.

Search Trees and BFS

  1. The tree structure: Level 0 = A (root); Level 1 = B, C (children of A); Level 2 = D, E (children of B), F, G (children of C). BFS visits nodes level by level: A, then B and C, then D, E, F, G. It would find F when it reaches Level 2 on the right side of C's subtree. Since both B and C are at Level 1, BFS would first expand B (producing D and E), then C (producing F and G), finding F when it processes C's children.
  2. BFS is complete because if a path to the goal exists, BFS will find it — it never gets stuck in an infinite branch without considering the goal node. It guarantees the shortest path because it expands all nodes at distance 1 before any node at distance 2, all nodes at distance 2 before distance 3, and so on. The first time it reaches the goal, it must have reached it via the fewest steps possible.
  3. BFS visits: A, B, C, D, E, F. It checks A (start), then generates B and C and checks them, then generates D and E from B and checks them, then generates F and G from C and checks F — goal found. BFS does this because it maintains a queue of nodes to visit in the order they were generated, always processing shallower nodes before deeper ones. It never dives down one branch entirely; it processes the entire frontier at each depth before going deeper.

Depth-First Search and Heuristics

  1. DFS visits: A, B, D (dead end, backtrack), E (dead end, backtrack), C, F (goal found). DFS pursues the leftmost branch all the way to a dead end before backtracking. Compared to BFS (which found F after visiting A, B, C, D, E, F), DFS found F after visiting only A, B, D, E, C, F — fewer nodes in this particular case, but only by luck of the tree structure. DFS can be much less efficient when the goal is on a branch far from the one explored first.
  2. Many valid examples. Sample: when entering a crowded grocery store, you head for the shortest-looking checkout line rather than counting items in every cart. This is a heuristic because it is a reasonable rule of thumb that usually leads to shorter wait times, but it is not guaranteed — the short line might have a price check, or someone might pay slowly. It is an educated estimate, not a computation of the optimal outcome.
  3. The GPS's time estimate functions like a heuristic: it gives an approximate measure of how far the current state is from the goal (remaining distance/time), without knowing exactly what traffic or delays lie ahead. The estimate can be wrong because of unpredictable events (accident, road closure, detour). The system recovers by continuously recalculating — updating its estimate at every step as new information arrives, essentially re-running its heuristic search from the current state whenever conditions change.

Extend Your Learning

The following resources go a little deeper on topics we touched on but did not fully explore in the readings. These are entirely optional — none of this material appears on the Competency Demo — but each one is a natural "next question" from something covered this week.

  • The A* algorithm
    A* combines a heuristic estimate of remaining cost with the actual cost already incurred to reach a node — making it more reliable than best-first search while remaining efficient. It is the algorithm behind most GPS routing systems. This article from Red Blob Games uses interactive visualizations to show how A* works step by step.
    Introduction to A* — Red Blob Games
  • Minimax search in game-playing AI
    Chess and other two-player games require a search strategy that accounts for an opponent who is actively trying to minimize your score. Minimax search and alpha-beta pruning are the foundational techniques. This article from freeCodeCamp walks through how minimax works with a clear example.
    Minimax Algorithm Guide — freeCodeCamp
  • The Traveling Salesman Problem
    A classic optimization problem — find the shortest route visiting a set of cities exactly once — that is simple to state but computationally explosive. It is a landmark example of a problem where exhaustive search is impossible and heuristics are essential. This overview from the University of Waterloo explains the problem and why it matters so much to computer science.
    The Traveling Salesman Problem — University of Waterloo