Uninformed Search - A Detailed Beginner's Guide

I’ll explain everything from scratch in extreme detail. Think of this as your complete study guide.

PART 1: THE FOUNDATION – What is Search in AI?

Why Do We Need Search?

Imagine you’re playing chess. You need to decide your next move. You could:

Move pawn to e4
Move knight to f3
Move bishop to c5
…and many other options

How do you choose? You think ahead:
“If I move here, then opponent might move there, then I could move here…”

This “thinking ahead” is SEARCH. You’re exploring different possibilities before actually moving.

Real-World Applications:

Google Maps – Searches through millions of possible routes to find the fastest way home
GPS in cars – Explores different paths when there’s traffic
Chess computers – Search through millions of board positions
Robot vacuum – Searches for the most efficient cleaning path
Airline booking – Searches through flight combinations

PART 2: THE BASICS – Agents and Environments

What is an Agent?

An agent is anything that perceives its environment through sensors and acts through actuators.

Real examples:

Human: Eyes/ears (sensors), hands/legs (actuators)
Robot: Cameras (sensors), motors (actuators)
Software: Keyboard input (sensor), screen display (actuator)

The Agent Function (Mathematical Description)

Think of it as a giant lookup table:

Percept (what you see) → Action (what you do)

Examples:
"See red light" → "Stop"
"See green light" → "Go"
"See empty road" → "Drive straight"

The Agent Program (Actual Code)

def agent_function(percept):
    if percept == "red_light":
        return "stop"
    elif percept == "green_light":
        return "go"
    elif percept == "obstacle":
        return "turn"

Performance Measure (How Good is the Agent?)

This is how we score the agent’s behavior:

Self-driving car: Reached destination safely? Fast? Smooth ride?
Chess program: Won the game? How many moves to win?
Robot vacuum: Cleaned entire room? Battery used?

PEAS Description – The Complete Problem Definition

Every AI problem can be described using PEAS:

Performance – What matters?
Environment – Where does it operate?
Actuators – What can it do?
Sensors – What can it perceive?

Example: Self-driving car

P: Safety, speed, comfort, fuel efficiency
E: Roads, traffic, weather, pedestrians
A: Steering wheel, brakes, accelerator, signals
S: Cameras, radar, GPS, speedometer

PART 3: ENVIRONMENT TYPES (Crucial for Midterm)

1. Observable vs. Partially Observable

Fully Observable: Agent can see everything about the current state

Example: Chess (you see all pieces)
Example: Tic-tac-toe (full board visible)

Partially Observable: Agent can’t see everything

Example: Poker (can’t see opponent’s cards)
Example: Real life (can’t see around corners)

2. Deterministic vs. Stochastic

Deterministic: Same action always produces same result

Example: Moving in chess (knight always moves in L-shape)
Example: Math calculation (2+2 always = 4)

Stochastic: Randomness involved

Example: Rolling dice (can’t predict exact outcome)
Example: Traffic (can’t predict exact arrival time)

3. Episodic vs. Sequential

Episodic: Each action independent of previous ones

Example: Quality control in factory (checking each item separately)
Example: Multiple-choice test (each question independent)

Sequential: Current action affects future decisions

Example: Chess (moving piece affects all future moves)
Example: Navigation (turning now affects route later)

4. Static vs. Dynamic

Static: Environment doesn’t change while agent thinks

Example: Solving a puzzle (pieces don’t move themselves)
Example: Planning a route (map doesn’t change mid-plan)

Dynamic: Environment changes during thinking

Example: Real-time game (enemies move while you decide)
Example: Stock trading (prices change constantly)

5. Discrete vs. Continuous

Discrete: Limited number of distinct states/actions

Example: Chess (finite number of board positions)
Example: Traffic lights (only red, yellow, green)

Continuous: Infinite possibilities

Example: Driving (infinite steering angles)
Example: Robot arm movement (infinite positions)

6. Single-agent vs. Multi-agent

Single-agent: Only one agent making decisions

Example: Solitaire
Example: Maze solving

Multi-agent: Multiple agents interacting

Example: Chess (two players)
Example: Traffic (many drivers)

PART 4: PROBLEM-SOLVING AGENTS

The Four-Step Process

Step 1: FORMULATE GOAL
        ↓
Step 2: FORMULATE PROBLEM
        ↓
Step 3: SEARCH (think)
        ↓
Step 4: EXECUTE (act)

Step 1: Formulate Goal

What do you want to achieve?

“Get from Arad to Bucharest”
“Solve the 8-puzzle”
“Win the chess game”

Step 2: Formulate Problem

Break it down into:

States: All possible situations
Actions: What you can do
Transition: What happens when you act
Cost: How “expensive” each action is

Step 3: Search

Think through possibilities without actually acting

Like playing “what-if” in your head
Build a tree of possibilities
Find a path to the goal

Step 4: Execute

Actually perform the actions you planned

“Eyes closed” execution (assuming world doesn’t change)
Follow the plan step by step

Assumptions in Basic Search (Important!)

World is static: Nothing changes while we think
World is discretizable: We can break it into states
World is observable: We know current state
Actions are deterministic: Same action always same result

Real world often violates these! But search is still useful.

PART 5: FORMAL SEARCH PROBLEM DEFINITION

The 6 Components You MUST Know

1. State Space (S)        : All possible configurations
2. Initial State (s₀)      : Where we start
3. Actions A(s)            : What we can do in each state
4. Transition Model         : Result(s,a) = new state
5. Goal Test               : Is this a goal state?
6. Action Cost c(s,a,s')   : Cost of taking action a

Example: 8-Puzzle

State Space: All arrangements of 8 tiles + empty on 3×3 board
Initial: [1 2 3]    Goal: [1 2 3]
         [4 5 6]          [4 5 6]
         [7 8 _]          [7 8 _]

Actions: Move empty space: UP, DOWN, LEFT, RIGHT
Transition: Slide adjacent tile into empty space
Cost: Usually 1 per move

Example: Traveling in Romania

State Space: All cities in Romania
Initial: Arad
Actions: Drive to adjacent city
Transition: You're now in that city
Goal Test: Are you in Bucharest?
Cost: Distance in km

PART 6: STATE SPACE SIZE – Why Search is Hard

The Explosion Problem

Pacman Example (from slides):

Agent positions: 120 possibilities
Food: 30 pieces (each can be eaten or not) = 2³⁰ possibilities
Ghost positions: 12² possibilities
Direction: 4 possibilities

Total = 120 × (2³⁰) × (12²) × 4

Let’s calculate roughly:

2³⁰ ≈ 1 billion
12² = 144
120 × 144 × 4 = 69,120
Total ≈ 69,120 × 1 billion = 69 trillion states!

Why this matters:

Can’t list all states explicitly
Need smart algorithms that don’t explore everything
Must be clever about which states to explore

PART 7: STATE GRAPHS VS SEARCH TREES

State Graph

Nodes: All possible states
Edges: Legal moves between states
One node per state (unique)
Usually too big to draw/build

Search Tree

Nodes: Paths to states (same state can appear multiple times)
Shows how we get to each state
Can be infinite even with finite graph (cycles!)
Built on-the-fly during search

Critical Insight:

The same physical state (e.g., being in Bucharest) can appear many times in the search tree if you reached it through different paths.

PART 8: UNINFORMED SEARCH ALGORITHMS

Now we get to the core of your midterm. These algorithms explore the search space blindly – they have no information about which states are promising.

ALGORITHM 1: DEPTH-FIRST SEARCH (DFS)

How It Works

Imagine exploring a maze:

Start at entrance
Pick a path and follow it
If you hit dead end, backtrack to last junction
Try next path

In Computer Terms

Uses a stack (LIFO – Last In First Out)
Always expand deepest node first
Go deep before going wide

Visual Example

Start → A → B → C (dead end)
              → D → E (found goal!)
              → F (dead end)
       → G → H (dead end)

Implementation

def depth_first_search(initial_state, goal_test, successors):
    fringe = [initial_state]  # Stack
    explored = set()

    while fringe:
        state = fringe.pop()  # Get last element (LIFO)

        if goal_test(state):
            return "Solution found!"

        if state not in explored:
            explored.add(state)
            for next_state in successors(state):
                fringe.append(next_state)

    return "No solution"

Properties

Complete?

Without cycle checking: NO (can get stuck in infinite loops)
With cycle checking: YES (won’t revisit states)

Optimal? NO (finds first solution, not cheapest)

Time Complexity: O(b^m)

b = branching factor (max children per node)
m = maximum depth of tree
Exponential! Could be huge

Space Complexity: O(bm)

Only store one path from root to current node
Plus siblings along that path
Linear in depth! (This is DFS’s biggest advantage)

Example Calculation

If b = 10, m = 5:

Space: ~50 nodes stored
Time: up to 100,000 nodes explored

When to Use DFS

✅ Memory is limited
✅ Solutions are deep
✅ Many solutions exist
❌ Don’t use if tree has infinite paths
❌ Don’t use if you need shortest path

ALGORITHM 2: BREADTH-FIRST SEARCH (BFS)

How It Works

Like searching a building floor by floor:

Check all rooms on current floor
Then go to next floor
Never go deeper until current level fully explored

In Computer Terms

Uses a queue (FIFO – First In First Out)
Expand all nodes at depth d before depth d+1
Guarantees shallowest solution first

Visual Example

Level 0: Start
Level 1: A, B, C
Level 2: A1, A2, B1, B2, C1, C2
Level 3: A1a, A1b, ... (until goal found)

Implementation

def breadth_first_search(initial_state, goal_test, successors):
    fringe = [initial_state]  # Queue
    explored = set()

    while fringe:
        state = fringe.pop(0)  # Get first element (FIFO)

        if goal_test(state):
            return "Solution found!"

        if state not in explored:
            explored.add(state)
            for next_state in successors(state):
                fringe.append(next_state)

    return "No solution"

Properties

Complete? YES (if branching factor finite)

Will eventually find solution if exists

Optimal? YES for uniform step cost

Finds shallowest solution (fewest steps)
NOT optimal for general costs (e.g., roads with different lengths)

Time Complexity: O(b^(s+1))

s = depth of shallowest solution
Explores all nodes up to depth s
Exponential!

Space Complexity: O(b^(s+1))

Stores entire frontier
Also exponential! (BFS’s biggest weakness)

Example Calculation

If b = 10, s = 5:

Space: ~1,111,110 nodes stored
Time: ~1,111,110 nodes explored
This could be gigabytes of memory!

When to Use BFS

✅ Solution is shallow
✅ Need shortest path (in steps)
✅ Memory not a problem
❌ Don’t use if tree is very deep
❌ Don’t use with high branching factor

ALGORITHM 3: DEPTH-LIMITED SEARCH (DLS)

Why We Need It

DFS can go infinitely deep. DLS says “stop at depth L.”

How It Works

Exactly like DFS, but:

Keep track of current depth
If depth = L, treat as dead end (don’t expand further)

Implementation

def depth_limited_search(state, goal_test, successors, limit, depth=0):
    if goal_test(state):
        return "Solution found!"

    if depth >= limit:
        return "cutoff"  # Reached limit

    for next_state in successors(state):
        result = depth_limited_search(next_state, goal_test, 
                                     successors, limit, depth+1)
        if result == "Solution found!":
            return "Solution found!"

    return "failure"

The Problem

What if solution is deeper than limit L? Then DLS fails even though solution exists!

ALGORITHM 4: ITERATIVE DEEPENING SEARCH (IDS)

The Genius Solution

Combine BFS’s completeness with DFS’s memory efficiency:

Try depth limit = 0: DFS to depth 0 → fail
Try depth limit = 1: DFS to depth 1 → fail
Try depth limit = 2: DFS to depth 2 → fail
Try depth limit = 3: DFS to depth 3 → SUCCESS!

Why This Works

Yes, we regenerate nodes many times, but:

Shallow nodes are regenerated many times (but they’re few)
Deep nodes are generated only once (and they’re most numerous)

Analysis

For a tree with branching factor b and solution depth d:

Nodes generated by BFS:

b + b² + b³ + ... + b^d ≈ O(b^d)

Nodes generated by IDS:

(d)b + (d-1)b² + ... + (1)b^d ≈ O(b^d)

The difference is only a constant factor! But memory is O(bd) instead of O(b^d).

Properties

Complete? YES
Optimal? YES for uniform step cost
Time: O(b^d) – same as BFS!
Space: O(bd) – linear like DFS!

Implementation

def iterative_deepening(initial_state, goal_test, successors):
    depth = 0
    while True:
        result = depth_limited_search(initial_state, goal_test, 
                                     successors, depth)
        if result == "Solution found!":
            return "Solution found!"
        if result == "failure":  # No solution at any depth
            return "No solution"
        depth += 1

ALGORITHM 5: UNIFORM COST SEARCH (UCS)

The Problem with BFS

BFS finds shortest path in number of steps, but what if steps have different costs?

Example:

Path A: 10 steps of 1 km each = 10 km
Path B: 2 steps of 100 km each = 200 km
BFS would choose Path A (fewer steps), but Path A is actually shorter!

How UCS Works

Instead of expanding shallowest node, expand cheapest node
“Cheapest” = lowest cumulative cost from start
Uses priority queue (sorted by cost)

Visual Example

Start(0)
  ↓ cost 5
Node A(5)
  ↓ cost 10
Node B(15) ← Goal found, but is it optimal?

Start(0)
  ↓ cost 8
Node C(8)
  ↓ cost 2
Node D(10) ← This is actually cheaper!

UCS would find Node D (cost 10) before Node B (cost 15).

Properties

Complete? YES (if all costs > 0)
Optimal? YES (finds least-cost path)
Time: O(b^(C*/ε))
C* = optimal solution cost
ε = minimum edge cost
Exponential in cost, not depth!
Space: Same as time

The Problem with UCS

Explores in all directions equally:

No guidance toward goal
Might explore paths away from goal if they’re cheap
Think of it as expanding in “cost contours”

PART 9: COMPLETE COMPARISON TABLE

Algorithm	Complete?	Optimal?	Time	Space	Strategy
DFS	No*	No	O(b^m)	O(bm)	Deepest first
BFS	Yes	Yes*	O(b^(s+1))	O(b^(s+1))	Shallowest first
DLS	No	No	O(b^l)	O(bl)	Depth-limited
IDS	Yes	Yes*	O(b^d)	O(bd)	Iterative deepening
UCS	Yes	Yes	O(b^(C*/ε))	O(b^(C*/ε))	Cheapest first

Notes:

*DFS complete only with cycle checking
*BFS optimal only for uniform step cost
*IDS optimal only for uniform step cost
m = maximum depth
s = shallowest solution depth
d = solution depth
l = depth limit
C* = optimal cost
ε = minimum edge cost

PART 10: WHEN TO USE EACH ALGORITHM

Choose DFS when:

Memory is extremely limited
Many solutions exist (first one is fine)
Tree depth is manageable
You can add cycle checking

Choose BFS when:

Need shortest path (in steps)
Solution is shallow
Memory is plentiful
All step costs equal

Choose IDS when:

You want BFS’s completeness but can’t afford memory
Step costs are uniform
Don’t know solution depth
This is often the best choice for uninformed search!

Choose UCS when:

Actions have different costs
Need guaranteed optimal solution
Can afford exponential time/memory
Don’t have heuristic guidance

PART 11: COMMON MIDTERM QUESTIONS

Q1: Compare BFS and DFS

BFS Pros:

Complete
Optimal for uniform cost
Finds shallowest solution

BFS Cons:

Exponential memory
Slow if solution deep

DFS Pros:

Linear memory
Fast if solution deep
Simple to implement

DFS Cons:

Not complete without cycle checking
Not optimal
Can get stuck in infinite paths

Q2: Why is IDS considered optimal for memory?

Because it combines:

BFS’s completeness (tries all depths)
DFS’s linear memory (only stores one path)
Only pays constant factor time penalty

Q3: When is BFS not optimal?

When actions have different costs:

BFS finds path with fewest steps
Not necessarily lowest total cost
Example: 10 steps of 1 mile vs 1 step of 100 miles

Q4: What makes UCS different?

Uses path cost, not depth
Guarantees optimal solution with non-uniform costs
Explores in cost contours
Can waste time exploring away from goal

PART 12: KEY CONCEPTS TO REMEMBER

Search is about exploring alternatives before acting
State space can be huge – need efficient algorithms
Uninformed = no guidance toward goal
Four properties: complete, optimal, time, space
Trade-off: Time vs Space vs Optimality
IDS often best for uninformed search
UCS needed for non-uniform costs

PRACTICE PROBLEMS

Problem 1:

You have unlimited memory but need the shortest path in steps. Which algorithm?

Answer: BFS – it’s optimal for steps and you have the memory for it.

Problem 2:

You have very little memory, actions have equal cost, and you don’t know solution depth.

Answer: IDS – gives optimal solution with linear memory.

Problem 3:

Actions have different costs, you need optimal solution, memory not an issue.

Answer: UCS – only algorithm that guarantees optimal with non-uniform costs.

Problem 4:

Tree might have infinite depth, memory limited, just need any solution.

Answer: DFS with cycle checking – prevents infinite loops, uses little memory.

The key is understanding the trade-offs between algorithms and knowing when to use each one. Practice drawing search trees for small examples and calculating which nodes each algorithm would explore.