Problems as State-Space Search

Unit 3: Search Techniques for Problem Solving — Section 3.1

Imagine you’re using a GPS to navigate from your home to a new restaurant across town. The app needs to consider every possible route, weigh the options, and find the best path. This is exactly how AI search algorithms work — they explore possibilities to find solutions.

Learn how AI agents formulate and solve search problems.

Search Algorithms Introduction

What Is a Search Problem?

A search problem is a formal way of describing a task where an agent must find a sequence of actions that leads from a starting situation to a desired goal. Rather than trying every random action, we structure the problem so that an algorithm can systematically explore options.

Every search problem has five core components:

  1. Initial state — where the agent begins

  2. Actions — what the agent can do in each state

  3. Transition model — how actions change the current state

  4. Goal test — how to recognize when the agent has reached its objective

  5. Path cost — a numeric measure of the cost of a sequence of actions

State Space

The set of all states reachable from the initial state by any sequence of actions. It defines the "world" that the search algorithm explores.

Transition Model

A function that describes what each action does — given a state and an action, it returns the resulting new state.

The 8-Puzzle: A Classic Example

The 8-puzzle is one of the most studied search problems in AI. You have a 3x3 grid with 8 numbered tiles and one blank space. The goal is to slide tiles until they reach a target configuration.

8-Puzzle Formulation:

  • Initial state: Any configuration of tiles on the board

  • Actions: Slide a tile up, down, left, or right into the blank

  • Transition model: Moving a tile swaps it with the blank space

  • Goal test: Tiles are in order (1-2-3 / 4-5-6 / 7-8-blank)

  • Path cost: Each move costs 1 (we want the fewest moves)

The state space for the 8-puzzle contains 181,440 reachable states — too many to check by hand, but manageable for a computer.

Formulating Real-World Problems

The power of state-space search comes from its generality. Almost any problem can be formulated this way if you can define the five components clearly.

Formulating a Search Problem:

  1. Identify what a "state" looks like — what information fully describes the current situation?

  2. List the possible actions available in each state

  3. Define how each action transforms one state into another (transition model)

  4. Specify what success looks like (goal test)

  5. Assign costs if some actions are more expensive than others

Consider route planning: states are intersections, actions are taking a road, the transition model maps roads to destination intersections, the goal test checks if you’ve arrived, and path cost is driving time or distance.

The quality of your problem formulation determines how efficiently an algorithm can find a solution. A well-chosen state representation keeps the state space small while retaining all information needed to reach the goal.

Abstraction: Keeping It Manageable

Real-world problems have enormous detail. When formulating a search problem, we abstract away irrelevant details. For route planning, we ignore the color of traffic lights, the songs on the radio, and the weather — we only track location and travel cost.

Good abstraction removes detail that doesn’t affect the solution while preserving enough information to find valid paths.

Think about a puzzle or game you enjoy. How would you define its state space? What are the actions, and how would you know when you’ve "won"?

Try formulating Tic-Tac-Toe as a search problem. How many states does it have?

Key Takeaways

Search problems provide a universal framework for AI problem-solving. By defining states, actions, transitions, goals, and costs, we transform vague tasks into precise computational problems that algorithms can solve systematically.

Test your understanding of state-space search components.

Next: 3.2 Search Trees vs. Search Graphs →

Based on the UC Berkeley CS 188 Online Textbook by Nikhil Sharma, Josh Hug, Jacky Liang, and Henry Zhu, licensed under CC BY-SA 4.0.

This work is licensed under CC BY-SA 4.0.