2.5 Defining Problems as State Space Search (BT104CO)
1. What is a State Space?
In Russell and Norvig's framework, a goal-based agent must first formalize its goal into a "problem" that can be solved using search algorithms.
State: A configuration of the agent and its environment at a specific moment.
State Space: The set of all possible states reachable from the initial state by any sequence of actions.
2. The 5 Components of a Formal Problem
To define a problem for an AI, you must specify these five elements:
I
Initial State
The state the agent starts in (e.g., initial piece arrangement in Chess).
II
Actions
Possible actions available. $Actions(s)$ returns all legal moves from state $s$.
III
Transition Model
What each action does. $Result(s, a)$ returns the state resulting from action $a$ in state $s$.
IV
Goal Test
Condition determining if a state is a Goal State (e.g., checkmate).
V
Path Cost
Assigns a numeric cost to each path. Agents seek the lowest cost (e.g., distance, time).
3. Real-World vs. Toy Problems
Toy Problems
Precise descriptions used to exercise search methods.
- 8-puzzle / Sudoku
- Vacuum-world
- The 8-queens problem
Real-World Problems
Complex, "noisy" problems that solutions are actually needed for.
- Airline travel planning
- VLSI layout design
- Robot navigation
4. Key Concepts in Search
A. State Space Graph: A visualization where nodes are states and edges are actions.
B. Solution: An action sequence leading from Initial to Goal state.
C. Optimal Solution: The path with the lowest path cost among all solutions.
D. Abstraction: Removing irrelevant details (e.g., tile color) to keep only necessary data.
5. Example: Formalizing the 8-Puzzle
| Component | 8-Puzzle Description |
|---|---|
| Initial State | Any specific configuration of tiles on the $3 \times 3$ board. |
| Actions | Move the "blank" space {Left, Right, Up, Down}. |
| Transition Model | The new board configuration after sliding a tile. |
| Goal Test | Does the board match the target state (e.g., $1, 2, 3...$)? |
| Path Cost | Each move costs 1. Path cost is the total number of moves. |