State spaces
Formulates the example problems (Romania, the vacuum world, the 8-puzzle, robot motion planning) as search problems, draws their state spaces, lists what the successor function returns for any state, and grows a breadth-first or uniform-cost search outward from the start state.
- Lecture reference: Solving Problems by Searching · slides 2–26
- Lecture reference: Uninformed Search · slide 40
Types of agents
Reflex agent
Consider how the world IS
- Choose action based on current percept
- Do not consider the future consequences of actions
Planning agent
Consider how the world WOULD BE
- Decisions based on (hypothesized) consequences of actions
- Must have a model of how the world evolves in response to actions
- Must formulate a goal
Can a reflex agent be rational?
Show answer
Search problem components
The optimal solution is the sequence of actions that gives the lowest path cost for reaching the goal.
Example: Romania
On vacation in Romania; currently in Arad. Flight leaves tomorrow from Bucharest.
- States
- The city the agent is in (not listed on the slide)
- Initial state
- Arad
- Actions
- Go from one city to another
- Transition model
- If you go from city A to city B, you end up in city B
- Goal state
- Bucharest
- Path cost
- Sum of edge costs (total distance traveled)
Not listed on the slide.
Successor function of Arad
| Action | Successor state | Step cost |
|---|---|---|
| Go to Sibiu | 140 | |
| Go to Timisoara | 118 | |
| Go to Zerind | 75 |
Select a state here or in the state space; select a successor to apply the successor function to it.
State space 20 states · 23 roads
The initial state, actions, and transition model define the state space of the problem: the set of all states reachable from the initial state by any sequence of actions. It can be represented as a directed graph where the nodes are states and the links between nodes are actions.
What is the state space for the Romania problem?
Show answer
Search: basic idea BFS from Arad
- Begin at the start state and expand it by making a list of all possible successor states (with the successor function).
- Maintain a frontier: a list of unexpanded states.
- At each step, pick a state from the frontier to expand.
- Keep going until you reach a goal state.
- Try to expand as few states as possible.
Frontier
1 node FIFO queue- next Arad
Explored set
0 statesEmpty
Graph search: a state enters the explored set when it is expanded and is not put on the frontier again. Lecture reference: Solving Problems by Searching · slide 36
With focus in the search: ← → previous and next step, Home End first and last step, Space play or pause.
Why not build the state space and use Dijkstra’s algorithm?
Given the initial state, actions, transition model, goal state, and path cost: how do we find the optimal solution? How about building the state space and then using Dijkstra’s shortest path algorithm?
- Complexity of Dijkstra’s algorithm is O(E + V log V), where V is the size of the state space (and E the number of actions).
- The state space may be huge: the table lists the example problems.
Uniform-cost search is equivalent to Dijkstra’s algorithm in general Lecture reference: Uninformed Search · slide 40, but it generates states with the successor function only when it expands them, and stops when it takes a goal state off the frontier.
| Problem | States V | Actions E | E + V log₂ V |
|---|---|---|---|
| Vacuum world, 2 squares | 8 | 24 | ~48 |
| Romania | 20 | 46 (23 roads, both ways) | ~132 |
| Vacuum world, 10 squares | 10,240 | 30,720 | ~167,137 |
| 8-puzzle | 181,440 | 483,840 | ~3.7 million |
| 15-puzzle | ~1.3 trillion | 3.9 trillion | ~56.2 trillion |
| 24-puzzle | ~10²⁵ | 3.2 × 10²⁵ | ~8.6 × 10²⁶ |
| Robot motion planning | Infinite (continuous) | Infinite | ∞ |